Extracting safe and precise control flow from binaries
- 7 November 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 894, 23-30
- https://doi.org/10.1109/rtcsa.2000.896367
Abstract
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.Keywords
This publication has 12 references indexed in Scilit:
- Cache modeling for real-time software: beyond direct mapped instruction cachesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Combining abstract interpretation and ILP for microarchitecture modelling and program path analysisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- PROPAN: A Retargetable System for Postpass Optimisations and AnalysesPublished by Springer Nature ,2001
- On loops, dominators, and dominance frontierPublished by Association for Computing Machinery (ACM) ,2000
- Cache behavior prediction by abstract interpretationScience of Computer Programming, 1999
- Run-Time Guarantees for Real-Time Systems—The USES ApproachPublished by Springer Nature ,1999
- OPTVIEWPublished by Association for Computing Machinery (ACM) ,1998
- Identifying loops using DJ graphsACM Transactions on Programming Languages and Systems, 1996
- Decompilation of binary programsSoftware: Practice and Experience, 1995
- EELPublished by Association for Computing Machinery (ACM) ,1995