Verifying network protocols using temporal logic
Brent T. Hailpern, Susan S. Owicki · 1980
Programs that implement computer communications protocols can exhibit extremely complicated behavior, and neither informal reasoning nor testing is reliable enough to establish their correctness. In this paper we discuss the application of program verification techniques to protocols. This approach is more reliable than informal reasoning, but has the advantage over formal reasoning based on finite-state models that the complexity of the proof does not grow unmanageably as the size of the program increases. Certain tools of concurrent program verification that are especially useful for protocols are presented: history variables that record sequences of input and output values, temporal logic for expressing properties that must hold in a future system state (such as eventual receipt of a message), and module specification and composition rules. The use of these techniques is illustrated by verifying a simple data transfer protocol from the literature.
Cited by 57 works.
Authors
References
- The temporal logic of programs
- Operating System Principles
- On the temporal analysis of fairness
- A Unified Method for the Specification and Verification of Protocols.
- The temporal semantics of concurrent programs
- A data transfer protocol
- Proving monitors
- Verifying Concurrent Processes Using Temporal Logic
- Formal Techniques for Protocol Specification and Verification
- Principles of proving concurrent programs in Gypsy