Thomas Ball
Todd Millstein
ABSTRACT
Model checking has been widely successful in validating and debugging designs in the hardware and protocol domains. However, state-space explosion limits the applicability of model checking tools, so model checkers typically operate on abstractions of systems.
Recently, there has been significant interest in applying model checking to software. For infinite-state systems like software, abstraction is even more critical. Techniques for abstracting software are a prerequisite to making software model checking a reality.
We present the first algorithm to automatically construct a predicate abstraction of programs written in an industrial programming language such as C, and its implementation in a tool — C2BP. The C2BP tool is part of the SLAM toolkit, which uses a combination of predicate abstraction, model checking, symbolic reasoning, and iterative refinement to statically check temporal safety properties of programs.
Predicate abstraction of software has many applications, including detecting program errors, synthesizing program invariants, and improving the precision of program analyses through predicate sensitivity. We discuss our experience applying the C2BP predicate abstraction tool to a variety of problems, ranging from checking that list-manipulating code preserves heap invariants to finding errors in Windows NT device drivers.
- 1.G. Ammons and J. R. Larus. Improving data- flow analysis with path profiles. In PLDI 98: Programming Language Design and Implementation, pages 72-84. ACM, 1998.]] Google Scholar
Digital Library
- 2.T. Ball, S. Chaki, and S. K. Rajamani. Parameterized verification of multithreaded software libraries. In TACAS 01: Tools and Algorithms for Construction and Analysis of Systems, LNCS 2031. Springer-Verlag, 2001.]] Google ScholarDigital Library
- 3.T. Ball, T. Millstein, and S. K. Rajamani. Polymorphic predicate abstraction. Technical Report MSR Technical Report 2001-10, Microsoft Research, 2000.]]Google Scholar
- 4.T. Ball, A. Podelski, and S. K. Rajamani. Boolean and cartesian abstractions for model checking C programs. In TACAS 01: Tools and Algorithms for Construction and Analysis of Systems, LNCS 2031. Springer-Verlag, 2001.]] Google ScholarDigital Library
- 5.T. Ball and S. K. Rajamani. Bebop: A symbolic model checker for Boolean programs. In SPIN 00: SPIN Workshop, LNCS 1885, pages 113-130. Springer-Verlag, 2000.]] Google ScholarDigital Library
- 6.T. Ball and S. K. Rajamani. Automatically validating temporal safety properties of interfaces. In SPIN 2001: SPIN Workshop, LNCS 2057, May 2001.]] Google ScholarDigital Library
- 7.D. Blei and et al. Vampyre: A proof generating theorem prover - http://www.eecs.berkeley.edu/~rupak/vampyre.]]Google Scholar
- 8.R. Bodik and S. Anik. Path-sensitive value- flow analysis. In POPL 98: Principles of Programming Languages, pages 237-251. ACM, 1998.]] Google ScholarDigital Library
- 9.R. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers, C-35(8):677- 691, 1986.]] Google ScholarDigital Library
- 10.J. Corbett, M. Dwyer, J. Hatcliff, C. Pasareanu, Robby, S. Laubach, and H. Zheng. Bandera : Extracting finitestate models from Java source code. In ICSE 00: Software Engineering, 2000.]] Google ScholarDigital Library
- 11.P. Cousot and R. Cousot. Abstract interpretation: a unified lattice model for the static analysis of programs by construction or approximation of fixpoints. In POPL 77: Principles of Programming Languages, pages 238-252. ACM, 1977.]] Google ScholarDigital Library
- 12.M. Das. Unification-based pointer analysis with directional assignments. In PLDI 00: Programming Language Design and Implementation, pages 35-46. ACM, 2000.]] Google ScholarDigital Library
- 13.S. Das, D. L. Dill, and S. Park. Experience with predicate abstraction. In CAV 00: Computer-Aided Verification, LNCS 1633, pages 160-171. Springer-Verlag, 1999.]] Google ScholarDigital Library
- 14.R. DeLine and M. Fahndrich. Enforcing high-level protocols in low-level software. In PLDI 01: Programming Language Design and Implementation. ACM, 2001.]] Google ScholarDigital Library
- 15.D. Detlefs, G. Nelson, and J. Saxe. Simplify theorem prover - http://research.compaq.com/src/esc/simplify.html.]]Google Scholar
- 16.E. Dijkstra. A Discipline of Programming. Prentice-Hall, 1976.]] Google ScholarDigital Library
- 17.M. Dwyer, J. Hatcliff, R. Joehanes, S. Laubach, C. Pasareanu, Robby, W. Visser, and H. Zheng. Tool-supported program abstraction for finite-state verification. In ICSE 01: Software Engineering (to appear), 2001.]] Google ScholarDigital Library
- 18.C. Flanagan, R. Joshi, and K. R. M. Leino. Annotation inference for modular checkers. Information Processing Letters (to appear), 2001.]] Google ScholarDigital Library
- 19.S. Graf and H. Sadi. Construction of abstract state graphs with PVS. In CAV 97:Computer-aided Verification, LNCS 1254, pages 72-83. Springer-Verlag, 1997.]] Google ScholarDigital Library
- 20.D. Gries. The Science of Programming. Springer-Verlag, 1981.]] Google ScholarDigital Library
- 21.N. Heintze. Set-based analysis of ML programs. In LFP 94: LISP and Functional Programming, pages 306-317. ACM, 1994.]] Google ScholarDigital Library
- 22.S. Ishtiaq and P. O'Hearn. BI as an assertion language for mutable data structures. In POPL 01: Principles of Programming Languages, pages 14-26. ACM, 2001.]] Google ScholarDigital Library
- 23.L. Lamport. Proving the correctness of multiprocess programs. IEEE Transactions on Software Engineering, SE- 3(2):125-143, 1977.]]Google ScholarDigital Library
- 24.W. Landi, B. G. Ryder, and S. Zhang. Interprocedural side effect analysis with pointer aliasing. In PLDI 93: Programming Language Design and Implementation, pages 56-67. ACM, 1993.]] Google ScholarDigital Library
- 25.J. M. Morris. A general axiom of assignment. In Theoretical Foundations of Programming Methodology, Lecture Notes of an International Summer School, pages 25-34. D. Reidel Publishing Company, 1982.]]Google ScholarCross Ref
- 26.G. Necula. Proof carrying code. In POPL 97: Principles of Programming Languages, pages 106-119. ACM, 1997.]] Google ScholarDigital Library
- 27.G. Nelson. Techniques for program verification. Technical Report CSL81-10, Xerox Palo Alto Research Center, 1981.]]Google Scholar
- 28.T. Reps, S. Horwitz, and M. Sagiv. Precise interprocedural data ow analysis via graph reachability. In POPL 95: Principles of Programming Languages, pages 49-61. ACM, 1995.]] Google ScholarDigital Library
- 29.J. C. Reynolds. Intuitionistic reasoning about shared mutable data structure. In Millenial Perspectives in Computer Science, pages 303-321. Palgrave, 2001.]]Google Scholar
- 30.M. Sagiv, T. Reps, and R. Wilhelm. Parametric shape analysis via 3-valued logic. In POPL 99: Principles of Programming Languages, pages 105-118. ACM, 1999.]] Google ScholarDigital Library
- 31.M. Sharir and A. Pnueli. Two approaches to interprocedural data dalow analysis. In Program Flow Analysis: Theory and Applications, pages 189-233. Prentice-Hall, 1981.]]Google Scholar
- 32.N. Suzuki and K. Ishihata. Implementation of an array bound checker. In POPL 77: Principles of Programming Languages, pages 132-143. ACM, 1977.]] Google ScholarDigital Library
- 33.Z. Xu, B. P. Miller, and T. Reps. Safety checking of machine code. In PLDI 00: Programming Language Design and Implementation, pages 70-82. ACM, 2000.]] Google ScholarDigital Library
Index Terms
- Automatic predicate abstraction of C programs
Recommendations
Automatic predicate abstraction of C programs
Model checking has been widely successful in validating and debugging designs in the hardware and protocol domains. However, state-space explosion limits the applicability of model checking tools, so model checkers typically operate on abstractions of ...
Automatic predicate abstraction of C programs
Supplemental issueModel checking has been widely successful in validating and debugging designs in the hardware and protocol domains. However, state-space explosion limits the applicability of model checking tools, so model checkers typically operate on abstractions of ...
Transition predicate abstraction and fair termination
POPL '05: Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languagesPredicate abstraction is the basis of many program verification tools. Until now, the only known way to overcome the inherent limitation of predicate abstraction to safety properties was to manually annotate the finite-state abstraction of a program. We ...
Comments