[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

The software model checker Blast

Applications to software engineering

  • Special section FASE'04/05
  • Published:
International Journal on Software Tools for Technology Transfer Aims and scope Submit manuscript

Abstract

Blast is an automatic verification tool for checking temporal safety properties of C programs. Given a C program and a temporal safety property, Blast either statically proves that the program satisfies the safety property, or provides an execution path that exhibits a violation of the property (or, since the problem is undecidable, does not terminate). Blast constructs, explores, and refines abstractions of the program state space based on lazy predicate abstraction and interpolation-based predicate discovery. This paper gives an introduction to Blast and demonstrates, through two case studies, how it can be applied to program verification and test-case generation. In the first case study, we use Blast to statically prove memory safety for C programs. We use CCured, a type-based memory-safety analyzer, to annotate a program with run-time assertions that check for safe memory operations. Then, we use Blast to remove as many of the run-time checks as possible (by proving that these checks never fail), and to generate execution scenarios that violate the assertions for the remaining run-time checks. In our second case study, we use Blast to automatically generate test suites that guarantee full coverage with respect to a given predicate. Given a C program and a target predicate p, Blast determines the program locations q for which there exists a program execution that reaches q with p true, and automatically generates a set of test vectors that cause such executions. Our experiments show that Blast can provide automated, precise, and scalable analysis for C programs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Alur R., Itai A., Kurshan R.P. and Yannakakis M. (1995). Timing verification by successive approximation. Inf. Comput. 118(1): 142–157

    Article  MATH  MathSciNet  Google Scholar 

  2. Andrews, T., Qadeer, S., Rajamani, S.K., Rehof, J., Xie, Y.: Zing: A model checker for concurrent software. In: Proc. CAV, LNCS, vol. 3114, pp. 484–487. Springer, Berlin (2004)

  3. Balarin, F., Sangiovanni-Vincentelli, A.L.: An iterative approach to language containment. In: Proc. CAV, LNCS, vol. 697, pp. 29–40. Springer, Berlin (1993)

  4. Ball, T., Rajamani, S.K.: The Slam project: Debugging system software via static analysis. In: Proc. POPL, pp. 1–3. ACM, New York (2002)

  5. Ball, T., Rajamani, S.K.: SLIC: A specification language for interface checking (of C). Tech. Rep. MSR-TR-2001-21, Microsoft Research (2002)

  6. Beyer, D., Chlipala, A.J., Henzinger, T.A., Jhala, R., Majumdar, R.: Generating tests from counterexamples. In: Proc. ICSE, pp. 326–335. IEEE, Los Alamitos (2004)

  7. Beyer, D., Chlipala, A.J., Henzinger, T.A., Jhala, R., Majumdar, R.: The Blast query language for software verification. In: Proc. SAS, LNCS, vol. 3148, pp. 2–18. Springer, Berlin (2004)

  8. Beyer, D., Henzinger, T.A., Jhala, R., Majumdar, R.: An Eclipse plug-in for model checking. In: Proc. IWPC, pp. 251–255. IEEE, Los Alamitos (2004)

  9. Beyer, D., Henzinger, T.A., Jhala, R., Majumdar, R.: Checking memory safety with Blast. In: Proc. FASE, LNCS, vol. 3442, pp. 2–18. Springer, Berlin (2005)

  10. Beyer, D., Henzinger, T.A., Théoduloz, G.: Lazy shape analysis. In: Proc. CAV, LNCS, vol. 4144, pp. 532–546, Springer, Berlin (2006)

  11. Beyer, D., Henzinger, T.A., Théoduloz, G.: Configurable software verification: concretizing the convergence of model checking and program analysis. In: Proc. CAV, LNCS, vol. 4590, pp. 504–518. Springer, Berlin (2007)

  12. Blanchet, B., Cousot, P., Cousot, R., Feret, J., Mauborgne, L., Mine, A., Monniaux, D., Rival, X.: Design and implementation of a special-purpose static program analyzer for safety-critical real-time embedded software. In: The Essence of Computation, Complexity, Analysis, Transformation: Essays Dedicated to Neil D. Jones, LNCS, vol. 2566, pp. 85–108. Springer, Berlin (2002)

  13. Bodik, R., Gupta, R., Sarkar, V.: ABCD: eliminating array bounds checks on demand. In: Proc. PLDI, pp. 321–333. ACM, New York (2000)

  14. Bodik, R., Gupta, R., Soffa, M.L.: Interprocedural conditional branch elimination. In: Proc. PLDI, pp. 146–158. ACM, New York (1997)

  15. Boyapati, C., Khurshid, S., Marinov, D.: Korat: automated testing based on Java predicates. In: Proc. ISSTA, pp. 123–133. ACM, New York (2002)

  16. Carlisle, M.C.: Olden: parallelizing programs with dynamic data structures on distributed memory machines. Ph.D. thesis, Princeton University (1996)

  17. Chaki, S., Clarke, E.M., Groce, A., Jha, S., Veith, H.: Modular verification of software components in C. IEEE Trans. Softw. Eng. 30(6), 388–402. Wiley, New York (2004)

    Google Scholar 

  18. Chen, H., Wagner, D.: MOPS: An infrastructure for examining security properties of software. In: Proc. CCS, pp. 235–244. ACM, New York (2002)

  19. Chen, H., Wagner, D., Dean, D.: Setuid demystified. In: Proc. USENIX Security Symp., pp. 171–190 (2002)

  20. Clarke, E.M., Emerson, E.A.: Design and synthesis of synchronization skeletons using branching-time temporal logic. In: Proc. Logic of Programs 1981, LNCS, vol. 131, pp. 52–71. Springer, Berlin (1982)

  21. Clarke, E.M., Grumberg, O., Jha, S., Lu, Y., Veith, H.: Counterexample-guided abstraction refinement. In: Proc. CAV, LNCS, vol. 1855, pp. 154–169. Springer, Berlin (2000)

  22. Clarke E.M., Grumberg O. and Peled D. (1999). Model Checking. MIT, Cambridge

    Google Scholar 

  23. Clarke, E.M., Kroening, D., Sharygina, N., Yorav, K.: SatAbs: SAT-based predicate abstraction for ANSI-C. In: Proc. TACAS, LNCS, vol. 3440, pp. 570–574. Springer, Berlin (2005)

  24. Clarke L.A. (1976). A system to generate test data and symbolically execute programs. IEEE Trans. Softw. Eng. 2(3): 215–222

    Article  Google Scholar 

  25. Clarke, L.A., Richardson, D.J.: Symbolic evaluation methods for program analysis. In: Program Flow Analysis: Theory and Applications, pp. 264–300. Prentice-Hall, Boston (1981)

  26. Condit, J., Harren, M., McPeak, S., Necula, G.C., Weimer, W.: CCured in the real world. In: Proc. PLDI, pp. 232–244. ACM, New York (2003)

  27. Cook, B., Kroening, D., Sharygina, N.: Cogent: accurate theorem proving for program verification. In: Proc. CAV, LNCS, vol. 3576, pp. 296–300. Springer, Berlin (2005)

  28. Corbett, J.C., Dwyer, M.B., Hatcliff, J., Pasareanu, C., Robby, Laubach, S., Zheng, H.: Bandera: Extracting finite-state models from Java source code. In: Proc. ICSE, pp. 439–448. ACM, New York (2000)

  29. Craig W. (1957). Linear reasoning. A new form of the Herbrand-Gentzen theorem. Symbolic Logic 22(3): 250–268

    MATH  MathSciNet  Google Scholar 

  30. Cytron R., Ferrante J., Rosen B.K., Wegman M.N. and Zadek F.K. (1991). Efficiently computing static single-assignment form and the program dependence graph. ACM Trans. Program. Languages Systems 13(4): 451–490

    Article  Google Scholar 

  31. Das, M., Lerner, S., Seigle, M.: ESP: Path-sensitive program verification in polynomial time. In: Proc. PLDI, pp. 57–68. ACM, New York (2002)

  32. Detlefs D., Nelson G. and Saxe J.B. (2005). Simplify: A theorem prover for program checking. J. ACM 52(3): 365–473

    Article  MathSciNet  Google Scholar 

  33. Esparza, J., Kiefer, S., Schwoon, S.: Abstraction refinement with Craig interpolation and symbolic pushdown systems. In: Proc. TACAS, LNCS, vol. 3920, pp. 489–503. Springer, Berlin (2006)

  34. Floyd, R.W.: Assigning meanings to programs. In: Mathematical Aspects of Computer Science, pp. 19–32. AMS (1967)

  35. Godefroid, P.: Model checking for programming languages using VeriSoft. In: Proc. POPL, pp. 174–186. ACM, New York (1997)

  36. Godefroid, P., Klarlund, N., Sen, K.: Dart: Directed automated random testing. In: Proc. PLDI, pp. 213–223. ACM, New York (2005)

  37. Gotlieb, A., Botella, B., Rueher, M.: Automatic test data generation using constraint solving techniques. In: Proc. ISSTA, pp. 53–62. ACM, New York (1998)

  38. Gulavani, B., Henzinger, T.A., Kannan, Y., Nori, A., Rajamani, S.K.: Synergy: a new algorithm for property checking. In: Proc. FSE. ACM, New York (2006)

  39. Gunter, E., Peled, D.: Temporal debugging for concurrent systems. In: Proc. TACAS, LNCS, vol. 2280, pp. 431–444. Springer, Berlin (2002)

  40. Gupta, N., Mathur, A.P., Soffa, M.L.: Generating test data for branch coverage. In: Proc. ASE, pp. 219–228. IEEE, Los Alamitos (2000)

  41. Hallem, S., Chelf, B., Xie, Y., Engler, D.: A system and language for building system-specific static analyses. In: Proc. PLDI, pp. 69–82. ACM, New York (2002)

  42. Havelund K. and Pressburger T. (2000). Model checking Java programs using Java PathFinder. STTT 2(4): 366–381

    MATH  Google Scholar 

  43. Henglein, F.: Global tagging optimization by type inference. In: Proc. LISP and Functional Programming, pp. 205–215. ACM, New York (1992)

  44. Henzinger, T.A., Jhala, R., Majumdar, R.: Race checking by context inference. In: Proc. PLDI, pp. 1–13. ACM, New York (2004)

  45. Henzinger, T.A., Jhala, R., Majumdar, R.: Permissive interfaces. In: Proc. ESEC/FSE, pp. 31–40. ACM, New York (2005)

  46. Henzinger, T.A., Jhala, R., Majumdar, R., McMillan, K.L.: Abstractions from proofs. In: Proc. POPL, pp. 232–244. ACM, New York (2004)

  47. Henzinger, T.A., Jhala, R., Majumdar, R., Necula, G.C., Sutre, G., Weimer, W.: Temporal-safety proofs for systems code. In: Proc. CAV, LNCS, vol. 2404, pp. 526–538. Springer, Berlin (2002)

  48. Henzinger, T.A., Jhala, R., Majumdar, R., Sanvido, M.A.A.: Extreme model checking. In: International Symposium on Verification: Theory and Practice, LNCS, vol. 2772, pp. 332–358. Springer, Berlin (2003)

  49. Henzinger, T.A., Jhala, R., Majumdar, R., Sutre, G.: Lazy abstraction. In: Proc. POPL, pp. 58–70. ACM, New York (2002)

  50. Hoare C.A.R. (1969). An axiomatic basis for computer programming. Commun. ACM 12(10): 576–580

    Article  MATH  Google Scholar 

  51. Hoare C.A.R. (2003). The verifying compiler: a grand challenge for computing research. J. ACM 50(1): 63–69

    Article  Google Scholar 

  52. Holzmann G.J. (1997). The Spin model checker. IEEE Trans. Softw. Eng. 23(5): 279–295

    Article  MathSciNet  Google Scholar 

  53. Hong, H.S., Cha, S.D., Lee, I., Sokolsky, O., Ural, H.: Data flow testing as model checking. In: Proc. ICSE, pp. 232–243. IEEE, Los Alamitos (2003)

  54. Ivancic, F., Yang, Z., Ganai, M.K., Gupta, A., Shlyakhter, I., Ashar, P.: F-Soft: Software verification platform. In: Proc. CAV, LNCS, vol. 3576, pp. 301–306. Springer, Berlin (2005)

  55. Jackson, D., Vaziri, M.: Finding bugs with a constraint solver. In: Proc. ISSTA, pp. 14–25. ACM, New York (2000)

  56. Jasper, R., Brennan, M., Williamson, K., Currier, B., Zimmerman, D.: Test data generation and infeasible path analysis. In: Proc. ISSTA, pp. 95–107. ACM, New York (1994)

  57. Jhala, R., Majumdar, R.: Path slicing. In: Proc. PLDI, pp. 38–47. ACM, New York (2005)

  58. Khurshid, S., Pasareanu, C.S., Visser, W.: Generalized symbolic execution for model checking and testing. In: Proc. TACAS, LNCS, vol. 2619, pp. 553–568. Springer, Berlin (2003)

  59. King J.C. (1976). Symbolic execution and program testing. Commun. ACM 19(7): 385–394

    Article  MATH  Google Scholar 

  60. Kroening, D., Groce, A., Clarke, E.M.: Counterexample guided abstraction refinement via program execution. In: Proc. ICFEM, LNCS, vol. 3308, pp. 224–238. Springer, Berlin (2004)

  61. Kurshan, R.P.: Computer Aided Verification of Coordinating Processes. Princeton University Press (1994)

  62. Lev-Ami, T., Sagiv, M.: Tvla: A system for implementing static analyses. In: Proc. SAS, LNCS, vol. 2280, pp. 280–301. Springer, Berlin (2000)

  63. Manna Z. (1974). Mathematical Theory of Computation. McGraw-Hill, New York

    MATH  Google Scholar 

  64. McCarthy, J.: Towards a mathematical science of computation. In: Proc. IFIP Congress, pp. 21–28. North-Holland (1962)

  65. McMillan K.L. (2005). An interpolating theorem prover. Theor. Comput. Sci. 345(1): 101–121

    Article  MATH  MathSciNet  Google Scholar 

  66. Musuvathi, M., Park, D.Y.W., Chou, A., Engler, D.R., Dill, D.L.: CMC: A pragmatic approach to model checking real code. In: Proc. OSDI. USENIX (2002)

  67. Myers, G.J.: The Art of Software Testing. Wiley (1979)

  68. Necula, G.C.: Proof carrying code. In: POPL 97: Principles of Programming Languages, pp. 106–119. ACM, New York (1997)

  69. Necula, G.C., Lee, P.: Efficient representation and validation of proofs. In: Proc. LICS, pp. 93–104. IEEE, Los Alamitos (1998)

  70. Necula, G.C., McPeak, S., Rahul, S.P., Weimer, W.: CIL: Intermediate language and tools for analysis and transformation of C programs. In: Proc. CC, LNCS, vol. 2304, pp. 213–228. Springer, Berlin (2002)

  71. Necula, G.C., McPeak, S., Weimer, W.: CCured: Type-safe retrofitting of legacy code. In: Proc. POPL, pp. 128–139. ACM, New York (2002)

  72. Nelson, G.: Techniques for program verification. Tech. Rep. CSL81-10, Xerox Palo Alto Research Center (1981)

  73. Peled D. (2001). Software Reliability Methods. Springer, Berlin

    MATH  Google Scholar 

  74. Peled, D.: Model checking and testing combined. In: Proc. ICALP, LNCS, vol. 2719, pp. 47–63. Springer, Berlin (2003)

  75. Queille, J.P., Sifakis, J.: Specification and verification of concurrent systems in CESAR. In: Proc. Symposium on Programming, LNCS, vol. 137, pp. 337–351. Springer, Berlin (1982)

  76. Ramamoorthy C.V., Ho S.B.F. and Chen W.T. (1976). On the automated generation of program test data. IEEE Trans. Softw. Eng. 2(4): 293–300

    Article  Google Scholar 

  77. Reps, T.W., Horwitz, S., Sagiv, M.: Precise interprocedural dataflow analysis via graph reachability. In: Proc. POPL, pp. 49–61. ACM, New York (1995)

  78. Saidi, H.: Model-checking-guided abstraction and analysis. In: Proc. SAS, LNCS, vol. 1824, pp. 377–396. Springer, Berlin (2000)

  79. Schneider, F.B.: Enforceable security policies. Tech. Rep. TR98-1664, Cornell (1999)

  80. Sen, K., Marinov, D., Agha, G.: Cute: A concolic unit testing engine for C. In: Proc. ESEC/FSE, pp. 263–272. ACM, New York (2005)

  81. Suzuki, N., Ishihata, K.: Implementation of an array bound checker. In: Proc. POPL, pp. 132–143. ACM, New York (1977)

  82. Young M. and Pezze M. (2005). Software Testing and Analysis: Process, Principles and Techniques. Wiley, New York

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Simon Fraser University, Surrey, BC, Canada

    Dirk Beyer

  2. EPFL, Lausanne, Switzerland

    Thomas A. Henzinger

  3. University of California, San Diego, USA

    Ranjit Jhala

  4. University of California, Los Angeles, USA

    Rupak Majumdar

Authors
  1. Dirk Beyer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Thomas A. Henzinger
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ranjit Jhala
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Rupak Majumdar
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Beyer, D., Henzinger, T.A., Jhala, R. et al. The software model checker Blast . Int J Softw Tools Technol Transf 9, 505–525 (2007). https://doi.org/10.1007/s10009-007-0044-z

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10009-007-0044-z

Keywords

Search

Navigation