Gulavani, Bhargav S; Henzinger, Thomas AIST Austria ; Kannan, Yamini; Nori, Aditya V; Rajamani, Sriram K
We consider the problem if a given program satisfies a specified safety property. Interesting programs have infinite state spaces, with inputs ranging over infinite domains, and for these programs the property checking problem is undecidable. Two broad approaches to property checking are testing and verification. Testing tries to find inputs and executions which demonstrate violations of the property. Verification tries to construct a formal proof which shows that all executions of the program satisfy the property. Testing works best when errors are easy to find, but it is often difficult to achieve sufficient coverage for correct programs. On the other hand, verification methods are most successful when proofs are easy to find, but they are often inefficient at discovering errors. We propose a new algorithm, Synergy, which combines testing and verification. Synergy unifies several ideas from the literature, including counterexample-guided model checking, directed testing, and partition refinement.This paper presents a description of the Synergy algorithm, its theoretical properties, a comparison with related algorithms, and a prototype implementation called Yogi.
117 - 127
FSE: Foundations of Software Engineering
Gulavani B, Henzinger TA, Kannan Y, Nori A, Rajamani S. Synergy: A new algorithm for property checking. In: ACM; 2006:117-127. doi:10.1145/1181775.1181790
Gulavani, B., Henzinger, T. A., Kannan, Y., Nori, A., & Rajamani, S. (2006). Synergy: A new algorithm for property checking (pp. 117–127). Presented at the FSE: Foundations of Software Engineering, ACM. https://doi.org/10.1145/1181775.1181790
Gulavani, Bhargav, Thomas A Henzinger, Yamini Kannan, Aditya Nori, and Sriram Rajamani. “Synergy: A New Algorithm for Property Checking,” 117–27. ACM, 2006. https://doi.org/10.1145/1181775.1181790.
B. Gulavani, T. A. Henzinger, Y. Kannan, A. Nori, and S. Rajamani, “Synergy: A new algorithm for property checking,” presented at the FSE: Foundations of Software Engineering, 2006, pp. 117–127.
Gulavani B, Henzinger TA, Kannan Y, Nori A, Rajamani S. 2006. Synergy: A new algorithm for property checking. FSE: Foundations of Software Engineering, 117–127.
Gulavani, Bhargav, et al. Synergy: A New Algorithm for Property Checking. ACM, 2006, pp. 117–27, doi:10.1145/1181775.1181790.