Model checking for programming languages using VeriSoft
Patrice Godefroid · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · 1997
Verification by state-space exploration, also often referred to as "model checking", is an effective method for analyzing the correctness of concurrent reactive systems (e.g., communication protocols). Unfortunately, existing model-checking techniques are restricted to the verification of properties of models, i.e., abstractions, of concurrent systems.In this paper, we discuss how model checking can be extended to deal directly with "actual" descriptions of concurrent systems, e.g., implementations of communication protocols written in programming languages such as C or C++. We then introduce a new search technique that is suitable for exploring the state spaces of such systems. This algorithm has been implemented in VeriSoft, a tool for systematically exploring the state spaces of systems composed of several concurrent processes executing arbitrary C code. As an example of application, we describe how VeriSoft successfully discovered an error in a 2500-line C program controlling robots operating in an unpredictable environment.
Cited by 825 works. doi:10.1145/263699.263717
Authors
References
- The Design and Analysis of Computer Algorithms
- Compilers: Principles, Techniques, and Tools
- Automatic verification of finite-state concurrent systems using temporal logic specifications
- Abstract interpretation
- Proving the Correctness of Multiprocess Programs
- Symbolic model checking: 1020 States and beyond
- Symbolic model checking
- Design and validation of computer protocols
- The Temporal Logic of Reactive and Concurrent Systems
- Symbolic Boolean manipulation with ordered binary-decision diagrams