Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Checking JML specifications using an extensible software model checking framework

  • Special section on Tools and Algorithms for the Construction and Analysis of Systems
  • Published:
International Journal on Software Tools for Technology Transfer Aims and scope Submit manuscript

Abstract

The use of assertions to express correctness properties of programs is growing in practice. Assertions provide a form of lightweight checkable specification that can be very effective in finding defects in programs and in guiding developers to the cause of a problem. A wide variety of assertion languages and associated validation techniques have been developed, but run-time monitoring is commonly thought to be the only practical solution. In this paper, we describe how specifications written in the Java Modeling Language (JML), a general purpose behavioral specification and assertional language for Java, can be validated using a customized model checker built on top of the Bogor model checking framework. Our experience illustrates the need for customized state-space representations and reduction strategies in model checking frameworks in order to effectively check the kind of strong behavioral specifications that can be written in JML. We discuss the advantages and tradeoffs of model checking relative to other specification validation techniques and present data that suggest that the cost of model checking strong specifications is practical for several real 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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Floyd, R.: Assigning meaning to programs. In: Proceedings of the Symposium on Applied Mathematics, Mathematical Aspects of Computer Science, vol. 19, pp. 19–32. American Mathematical Society (1967)

  2. Meyer, B.: Object-oriented Software Construction. Prentice-Hall (1988)

  3. Rosenblum, D.S.: A practical approach to programming with assertions. IEEE Trans. Software Eng. 21(1), 19–31 (1995)

    Article  Google Scholar 

  4. Flanagan, C., Leino, K.R.M., Lillibridge, M., Nelson, G., Saxe, J.B., Stata, R.: Extended static checking for Java. In: Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, pp. 234–245. ACM Press (2002)

  5. Visser, W,., Havelund, K., Brat, G., Park, S.: Model checking programs. In: Proceedings of the 15th IEEE Conference on Automated Software Engineering, vol. 10, no. 2, pp. 203–232. Springer-Verlag, Berlin (2000)

  6. Leavens, G.T., Baker, A.L., Ruby, C.: JML: a notation for detailed design. In: Kilov, H., Rumpe, B., Simmonds, I. (eds.) Behavioral Specifications of Businesses and Systems, pp. 175–188. Kluwer Academic Publishers, Boston (1999)

  7. Robby, Dwyer, M.B., Hatcliff, J.: Bogor: an extensible and highly-modular model checking framework. In: Proceedings of the 9th European Software Engineering Conference held jointly with the 11th ACM SIGSOFT Symposium on the Foundations of Software Engineering. SIGSOFT Software Engineering Notes, vol. 28, no. 5, pp. 267–276. ACM Press (2003)

  8. Holzmann, G.J.: The model checker SPIN. IEEE Trans. Software Eng. 23(5), 279–294 (1997)

    Article  MathSciNet  Google Scholar 

  9. Robby, Dwyer, M.B., Hatcliff, J., Iosif, R.: Space-reduction strategies for model checking dynamic systems. In: Proceedings of the 2003 Workshop on Software Model Checking. Electronic Notes on Theoretical Computer Science, vol. 89, no. 3. Elsevier (2003)

  10. Dwyer, M.B., Hatcliff, J., Robby, Prasad, V.R.: Exploiting object escape and locking information in partial order reduction for concurrent object-oriented programs. Formal Methods Syst. Des. 25(2/3), 199–240 (2004)

    Article  Google Scholar 

  11. SAnToS. SpEx Website. http://spex.projects.cis.ksu.edu (2003)

  12. Wing, J.M.: Writing Larch interface language specifications. ACM Trans. Program Lang. Syst. 9(1), 1–24 (1987)

    Article  MathSciNet  Google Scholar 

  13. Lea, D.: Concurrent Programming in Java. 2nd ed. Addison-Wesley (2000)

  14. Dwyer, M.B., Robby, Deng, X., Hatcliff, J.: Space reductions for model checking quasi-cyclic systems. In: Proceedings of the 3rd International Conference on Embedded Software (EMSOFT 2003). Lecture Notes in Computer Science, vol. 2855, pp. 173–189. Springer-Verlag, Berlin (2003)

  15. Gamma, E., Helm, R., Johnson, R., Vlissides, J.: Design Patterns. Addison-Wesley (1995)

  16. Brat, G., Havelund, K., Park, S., Visser, W.: Java PathFinder – a second generation of a Java model-checker. In: Proceedings of the Workshop on Advances in Verification (2000)

  17. Clarke, E., Grumberg, O., Peled, D.: Model Checking. MIT Press (2000)

  18. Cheon, Y., Leavens, G.T.: A runtime assertion checker for the Java Modeling Language (JML). In: Proceedings of The International Conference on Software Engineering Research and Practice, pp. 322–328. CSREA Press (2002)

  19. van den Berg, J., Jacobs, B.: The LOOP compiler for Java and JML. In: Proceedings of the 7th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science, vol. 2031, pp. 299–312. Springer-Verlag, Berlin (2001)

  20. Hatcliff, J., Robby, Dwyer, M.: Verifying atomicity specifications for concurrent object oriented software using model checking. In: Proceedings of the 5th International Conference on Verification, Model Checking, and Abstract Interpretation. Lecture Notes in Computer Science, vol. 2937, pp. 175–190. Springer-Verlag, Berlin (2004)

  21. Leavens, G.T., Cheon, Y., Clifton, C., Ruby, C., Cok, D.: How the design of JML accommodates both runtime assertion checking and formal verification. In: Proceedings of the 1st International Symposium on Formal Methods for Components and Objects. Lecture Notes in Computer Science, vol. 2852, pp. 262–84. Springer-Verlag, Berlin (2002)

  22. Ball, T., Rajamani, S.K.: The slam toolkit. In: Proceedings of the 13th International Conference on Computer Aided Verification, pp. 260–264. Springer-Verlag, Berlin (2001)

  23. Henzinger, T.A., Jhala, R., Majumdar, R., Sutre, G.: Lazy abstraction. In: Proceedings of the 29th ACM Symposium on Principles of Programming Languages, pp. 58–70 (2002)

  24. Hartley, S.: Concurrent Programming – The Java Programming Language. Oxford University Press (1998)

  25. Dwyer, M.B., Wallentine, V.: A framework for parallel adaptive grid simulations. Concurrency: Pract Exp 9(11), 1293–1310 (1997)

    Article  Google Scholar 

  26. Burdy, L., Cheon, Y., Cok, D., Ernst, M., Kiniry, J., Leavens, G.T., Leino, K.R.M., Poll, E.: An overview of JML tools and applications. In: Proceedings of the Eighth International Workshop on Formal Methods for Industrial Critical Systems. Electronic Notes in Theoretical Computer Science, vol. 80. Elsevier (2003)

  27. Owre, S., Rushby, J.M., Shankar, N.: PVS: A prototype verification system. In: Kapur, D. (ed.) 11th International Conference on Automated Deduction (CADE). Lecture Notes in Artificial Intelligence, vol. 607, pp. 748–752. Springer-Verlag, Saratoga, NY (1992)

  28. NIII. ESC/Java2 Website. http://www.cs.kun.nl/sos/research/escjava/index.html

  29. Hussmann, H., Demuth, B., Finger, F.: Modular architecture for a toolset supporting OCL. In: The Third International Conference on The Unified Modeling Language. Lecture Notes in Computer Science, vol. 1939, pp. 278–293. Springer-Verlag, Berlin (2000)

  30. Richters, M., Gogolla, M.: Validating UML models and OCL constraints. In: The Third International Conference on The Unified Modeling Language. Lecture Notes in Computer Science, vol. 1939, pp. 265–277. Springer-Verlag, Berlin (2000)

  31. Khurshid, S., Marinov, D., Jackson, D.: An analyzable annotation language. In: Proceedings of the 17th ACM conference on Object-oriented Programming, Systems, Languages, and Applications, pp. 231–245. ACM Press, New York, NY, USA(2002)

  32. Penix, J., Visser, W., Engstrom, E., Larson, A., Weininger, N.: Verification of time partitioning in the deos scheduler kernel. In: Proceedings of the 22nd International Conference on Software Engineering, pp. 488–497. ACM Press (2000)

  33. Tkachuk, O., Dwyer, M., Pasareanu, C.: Automated environment generation for software model checking. In: Proceedings of the 18th International Conference on Automated Software Engineering, pp. 116–129. IEEE Computer Society (2003)

  34. Tkachuk, O., Dwyer, M.B.: Adapting side effects analysis for modular program model checking. In: Proceedings of the Fourth Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering (2003)

  35. Rodríguez, E., Dwyer, M.B., Hatcliff, J., Robby.: A flexible framework for the estimation of coverage metrics in explicit state software model checking. In: Proceedings of the International Workshop on Construction and Analysis of Safe, Secure and Interoperable Smart Devices (CASSIS 2004). Lecture Notes in Computer Science, vol. 3362, pp. 210–228. Springer-Verlag, Berlin (2004)

  36. SAnToS. MAnTA Website. http://manta.projects.cis.ksu.edu (2004)

  37. Stoller, S.D.: Domain partitioning for open reactive systems. In: Proceedings of the International Symposium on Software Testing and Analysis, pp. 44–54. ACM Press (2002)

  38. Rodríguez, E., Dwyer, M., Flanagan, C., Hatcliff, J., Leavens, G.T., Robby.: Extending sequential specification techniques for modular specification and verification of multi-threaded programs. In: Proceedings of the 19th European Conference on Object-Oriented Programming (ECOOP 2005). Springer-Verlag, Berlin (in press)

  39. Flanagan, C.: Verifying commit-atomicity using model-checking. In: Proceedings of the 11th International SPIN Workshop on Model Checking of Software. Lecture Notes in Computer Science, vol. 2989, pp. 252–266. Springer-Verlag, Berlin (2004)

Download references

Author information

Authors and Affiliations

  1. Department of Computing and Information Sciences, Kansas State University, 234 Nichols Hall, Manhattan, KS, 66506, USA

    Robby, Edwin Rodríguez & John Hatcliff

  2. Department of Computer Science and Engineering, University of Nebraska-Lincoln, 256 Avery Hall, Lincoln, NE, 68588, USA

    Matthew B. Dwyer

Authors
  1. Robby
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Edwin Rodríguez
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Matthew B. Dwyer
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. John Hatcliff
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Edwin Rodríguez.

Additional information

This is an extended version of the paper Checking Strong Specifications Using An Extensible Model Checking Framework that appeared in Proceedings of the 10th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2004. This work was supported in part by the U.S. Army Research Office (DAAD190110564), by DARPA/IXO’s PCES program (AFRL Contract F33615-00-C-3044), by NSF (CCR-0306607) by Lockheed Martin, and by Rockwell-Collins.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Robby, Rodríguez, E., Dwyer, M.B. et al. Checking JML specifications using an extensible software model checking framework. Int J Softw Tools Technol Transfer 8, 280–299 (2006). https://doi.org/10.1007/s10009-005-0218-5

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10009-005-0218-5

Keywords

Search

Navigation