ABSTRACT
There is a widely held belief that whole program analysis is intractable for large complex software systems, and there can be little doubt that this is true for program analyses based on model checking. Model checking selected program components that comprise a cohesive unit, however, can be an effective way of uncovering subtle coding errors, especially for components of multi-threaded programs. In this setting, one of the chief problems is how to safely approximate the behavior of the rest of the application as it relates to the unit being analyzed.Non-unit application components are collectively referred to as the environment. In this paper, we describe how points-to and side-effects analyses can be adapted to support generation of summaries of environment behavior that can be reified into Java code using special modeling primitives. The resulting abstract models of the environment can be combined with the code of the unit and then model checked against unit properties. We present our analysis framework, illustrate its flexibility in generating several types of models, and present experience that provides evidence of the scalability of the approach.
- J.-D. Choi, M. Burke, and P. Carini. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In Conference Record of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 232--245, Charleston, South Carolina, 1993.]] Google ScholarDigital Library
- J. M. Cobleigh, D. Giannakopoulou, and C. S. Puasuareanu. Learning assumptions for compositional verification. In Proceedings of the 9th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (LNCS 2619), 2003.]]Google ScholarDigital Library
- C. Colby, P. Godefroid, and L. J. Jagadeesan. Automatically closing open reactive programs. In SIGPLAN Conference on Programming Language Design and Implementation, pages 345--357, 1998.]] Google ScholarDigital Library
- J. C. Corbett, M. B. Dwyer, J. Hatcliff, S. Laubach, C. S. Puasuareanu, Robby, and H. Zheng. Bandera : Extracting finite-state models from Java source code. In Proceedings of the 22nd International Conference on Software Engineering, June 2000.]] Google ScholarDigital Library
- M. B. Dwyer, J. Hatcliff, R. Joehanes, S. Laubach, C. S. Puasuareanu, Robby, W. Visser, and H. Zheng. Tool-supported program abstraction for finite-state verification. In Proceedings of the 23rd International Conference on Software Engineering, May 2001.]] Google ScholarDigital Library
- M. B. Dwyer and C. S. Puasuareanu. Filter-based model checking of partial systems. In Proceedings of the Sixth ACM SIGSOFT Symposium on Foundations of Software Engineering, Nov. 1998.]] Google ScholarDigital Library
- D. Giannakopoulou, C. S. Puasuareanu, and H. Barringer. Assumption generation for software component verification. In Proceedings of the 17th IEEE Conference on Automated Software Engineering, 2002.]] Google ScholarDigital Library
- T. A. Henzinger, R. Jhala, R. Majumdar, and G. Sutre. Lazy abstraction. In Proceedings of the 29th ACM Symposium on Principles of Programming Languages, pages 58--70, Jan. 2002.]] Google ScholarDigital Library
- O. Kupferman and M. Y. Vardi. Modular model checking. In COMPOS (LNCS 1536), 1998.]] Google ScholarDigital Library
- W. Landi, B. G. Ryder, and S. Zhang. Interprocedural side effect analysis with pointer aliasing. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 56--67, 1993.]] Google ScholarDigital Library
- D. Liang and M. J. Harrold. Efficient computation of parameterized pointer information for interprocedural analyses. In Proceedings of the 8th International Static Analysis Symposium (LNCS 2126), page 279, 2001.]] Google ScholarDigital Library
- Z. Manna and A. Pnueli. The Temporal Logic of Reactive and Concurrent Systems: Specification. Springer-Verlag, 1991.]] Google ScholarDigital Library
- S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997.]] Google ScholarDigital Library
- A. Rountev and B. G. Ryder. Points-to and side-effect analyses for programs built with precompiled libraries. In Proceedings of the 10th International Conference on Compiler Construction (CC'01), 2001.]] Google ScholarDigital Library
- O. Tkachuk. Adapting side effects analysis for modular program model checking. Master's thesis, Kansas State University, 2003.]]Google Scholar
- O. Tkachuk, G. Brat, and W. Visser. Using code level model checking to discover automation surprises. In Proceedings of the 2002 Digital Avionics Systems Conference, 2002.]]Google ScholarCross Ref
- R. Valle-Rai, L. Hendren, V. Sundaresan, P. Lam, E. Gagnon, and P. Co. Soot - a Java optimization framework. In Proceedings of CASCON'99, Nov. 1999.]] Google ScholarDigital Library
- W. Visser, K. Havelund, G. Brat, and S. Park. Model checking programs. In Proceedings of the 15th IEEE Conference on Automated Software Engineering, Sept. 2000.]] Google ScholarDigital Library
- J. Whaley and M. Rinard. Compositional pointer and escape analysis for Java programs. In OOPSLA'99 ACM Conference on Object-Oriented Systems, Languages and Applications, volume 34(10) of ACM SIGPLAN Notices, pages 187--206, Denver, CO, Oct. 1999. ACM Press.]] Google ScholarDigital Library
Index Terms
- Adapting side effects analysis for modular program model checking
Recommendations
Adapting side effects analysis for modular program model checking
There is a widely held belief that whole program analysis is intractable for large complex software systems, and there can be little doubt that this is true for program analyses based on model checking. Model checking selected program components that ...
Modular Model Checking of Large Asynchronous Designs with Efficient Abstraction Refinement
Divide-and-conquer is essential to address state explosion in model checking. Verifying each individual component in a system, in isolation, efficiently requires an appropriate context, which traditionally is obtained by hand. This paper presents an ...
Bounded model checking of high-integrity software
HILT '13: Proceedings of the 2013 ACM SIGAda annual conference on High integrity language technologyModel checking [5] is an automated algorithmic technique for exhaustive verification of systems, described as finite state machines, against temporal logic [9] specifications. It has been used successfully to verify hardware at an industrial scale [6]. ...
Comments