Sound Control-Flow Graph Extraction for Java Programs with Exceptions

Abstract. We present an algorithm to extract control-flow graphs from Java bytecode, considering exceptional flows. We then establish its cor-rectness: the behavior of the extracted graphs is shown to be a sound over-approximation of the behavior of the original programs. Thus, any temporal safety property that holds for the extracted control-flow graph also holds for the original program. This makes the extracted graphs suit-able for performing various static analyses, in particular model checking. The extraction proceeds in two phases. First, we translate Java bytecode into BIR, a stack-less intermediate representation. The BIR transforma-tion is developed as a module of Sawja, a novel static analysis framework for Java bytecode. Besides Sawja’s efficiency, the resulting intermediate representation is more compact than the original bytecode and provides an explicit representation of exceptions. These features make BIR a nat-ural starting point for sound control-flow graph extraction. Next, we for-mally define the transformation from BIR to control-flow graphs, which (among other features) considers the propagation of uncaught excep-tions within method calls. We prove the correctness of the two-phase extraction by suitably combining the properties of the two transforma-tions with those of an idealized control-flow graph extraction algorithm, whose correctness has been proved directly. The control-flow graph ex-traction algorithm is implemented in the ConFlEx tool. A number of test-cases show the efficiency and the utility of the implementation.