Verifying Concurrent Message-Passing C Programs with Recursive Calls

Sagar Chaki, Edmund Clarke, Nicholas Kidd, Thomas Reps, Tayssir Touili, Proceedings of the 12th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), LNCS 3920, page 334-349, March 25-April 2, 2006

Abstract: We consider the model-checking problem for C programs with (1) data ranging over very large domains, (2) (recursive) procedure calls, and (3) concurrent parallel components that communicate via synchronizing actions. We model such programs using communicating pushdown systems, and reduce the reachability problem for this model to deciding the emptiness of the intersection of two context-free languages L₁ and L₂. We tackle this undecidable problem using a CounterExample Guided Abstraction Refinement (CEGAR) scheme. We implemented our technique in the model checker MAGIC and found a previously unknown bug in a version of a Windows NT Bluetooth driver.

PDF / Online © Springer