Efficient Verification of Programs with Complex Data Structures Using SMT Solvers
Complex data structures such as list, tree, and graph are mainly located on the heap. Verifying programs with complex data structures against the properties that constrain the configurations of the objects on the heap is particularly important for safety critical software systems with extensive heap manipulations. Erroneous heap manipulations may cause loss or unauthorized access to data, violate software security, and may eventually cause a system to crash. Program verification techniques like bounded and deductive program verification, in general, are capable of verifying a program against a property of complex data structures. However, there is always a trade off between the scope of their analyses, and their level of automation. Bounded program verification techniques are fully automatic, but they only analyze a program for a small scope. Deductive program verification, on the other hand, have no restriction on the scope, but they often require users to provide auxiliary specifications such as loop invariants and method contracts for sub routines. In this thesis, we present a verification infrastructure combing the benefits of different program verification techniques. To verify a program with respect to a specification specifying a property that is expected to be satisfied by the program, the envisioned verification process is as follow: 1. Bounded program verification. For gaining fast and initial confidence in the correctness of the program regarding the expected property, we first check whether the property holds for a small scope without providing any auxiliary specification. If a counterexample to the correctness of the program is found, no further analysis is required. Otherwise, the property holds but only for the scope; thus a deductive verification an unbounded program verification, is still needed. 2. Abstraction. Construct a semantic slice of the program with respect to the property. The semantic slice is an abstract program which contains those statements of the original program that are relevant to the property.