Extracting safe and precise control flow from binaries

As a starting point for static program analysis, a control flow graph (CFG) is needed. If only the binary executable is available, this CFG has to be reconstructed from sequences of instructions. The usual way to do this is a top-down approach: the executable's information about routines is used to split the sequence into routines, and then each instruction is analysed for branch targets in order to compute basic block boundaries. When analysing safety-critical real-time systems, safe and precise results are needed. The CFG that the analyses traverse has to satisfy the same safety and precision requirements, because the analyses inherit all deficiencies. In this paper, a bottom-up approach for CFG approximation is presented. It starts at a set of entry points and clusters the sequence of instructions into larger units like blocks and routines. In this way, the algorithm is able to account for uncertainties early enough to generate a safe CFG.