Abstract
We present a model-checker for boolean programs with (possibly recursive) procedures and the temporal logic LTL. The checker is guaranteed to terminate even for (usually faulty) programs in which the depth of the recursion is not bounded. The algorithm uses automata to finitely represent possibly infinite sets of stack contents and BDDs to compactly represent finite sets of values of boolean variables. We illustrate the checker on some examples and compare it with the Bebop tool of Ball and Rajamani.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
T. Ball and S. K. Rajamani. Bebop: A symbolic model checker for boolean programs. In SPIN 00: SPIN Workshop, LNCS 1885, pages 113–130, 2000.
T. Ball and S. K. Rajamani. Automatically validating temporal safety properties of interfaces. Technical report, 2001.
A. Bouajjani, J. Esparza, and O. Maler. Reachability analysis of pushdown automata: Application to model-checking. In Proceedings of CONCUR’ 97, LNCS 1243, pages 135–150, 1997.
J. Esparza, D. Hansel, P. Rossmanith, and S. Schwoon. Efficient algorithms for model checking pushdown systems. In Proceedings of CAV’ 00, LNCS 1855, 2000.
J. Esparza and S. Schwoon. A BDD-based Model Checker for Recursive Programs. Technical report, Institut für Informatik, Technische Universitöt München, 2001. Available at http://www7.in.tum.de/gruppen/theorie/publications/.
T. Jensen, D. L Méetayer, and T. Thorn. Verification of control flow based security properties. In Proceedings of 1999 IEEE Symposium on Security and Privacy, IEEE Press, 1999.
J.R. Burch, E.M. Clarke, D.E. Long, K.L. MacMillan, and D.L. Dill. Symbolic model checking for sequential circuit verification. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 13(4):401–424, 1994.
F. Somenzi. Colorado University Decision Diagram Package. Technical report, University of Colorado, Boulder, 1998.
R. E. Tarjan. Depth first search and linear graph algorithms. In SICOMP 1, pages 146–160, 1972.
A. Xie and P. A. Beerel. Implicit enumeration of strongly connected components. In Proceedings of ICCAD, pages 37–40, San Jose, CA, 1999
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Esparza, J., Schwoon, S. (2001). A BDD-Based Model Checker for Recursive Programs. In: Berry, G., Comon, H., Finkel, A. (eds) Computer Aided Verification. CAV 2001. Lecture Notes in Computer Science, vol 2102. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44585-4_30
Download citation
DOI: https://doi.org/10.1007/3-540-44585-4_30
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42345-4
Online ISBN: 978-3-540-44585-2
eBook Packages: Springer Book Archive