converting IR to Z3 formula?

Question

I have some code in IR, and this code is already in SSA form. Now I am trying to convert this code to SMT formula, then feed it to Z3 to do some verification. I have some questions:

1. Is there any technical paper explains in detail how to convert SSA IR to SMT formula? I searched around, to no avail.

2. For those computational instructions, there is not much problems converting to Z3 formula. However, I am still struggling with unconditional and conditional branch instructions. Any suggestion on how to convert these instructions to Z3 formula?

Thanks so much!!!

Answer 1

I think it is fair to divide the SMT based program verification tools in two main groups:

• Fuzzers and Bug finders. These tools essentially encode one execution path of the program into a SMT formula. These tools use SMT to check whether a particular execution path is feasible or not. Examples or such tools are: Pex, EXE, Sage. Based on your question, it seems you already know how to encode one path into SMT.

• Extended Static Checkers and Verifying Compilers. These tools usually reduce the program to an intermediate form. Then, several verification conditions (VCs) are produced and sent to a SMT solver. Most of them (all?) try to do modular verification, since it is too expensive to verify the whole program as a single SMT problem. Boogie-PL is a very popular intermediate format. If you map your IR into Boogie-PL, you can then use Boogie to generate the VCs in SMT format. The article "Weakest-Precondition of Unstructured Programs" describes how Boogie-PL is encoded into formulas. Note that, Boogie is open-source, and the code is very readable. So, you may also browse the code to clarify details. Rustan Leino also has a bunch of slides explaining how to encode Boogie VCs into formulas. Other relevant projects are ESC/Java 2, Why3, VeriFast.

EDIT (handling loops): the simplest technique for handling loops just unfold them for a given number of times. When we do that, our verification tool becomes a "bug finder" since we are essentially giving up on analyzing all possible paths. In tools (such as ESC/Java, Why3, VeriFast), loop invariants are used. Rustan has a nice video and lectures notes about loop invariants. The loop invariants may be provided by the user, or automatically computed. There are many papers on "loop invariant synthesis".

Loop invariant example: the function duplet in this Why3 verification example.

Yet another possibility is to encode your IR into muZ. muZ is the fixedpoint engine available in Z3. In this approach, loops can be directly encoded (see the articles on the muZ page), and no loop invariants need to be provided. However, engines like muZ are not yet mature as state-of-the-art SMT solvers.