Title :
A precision-tunable CFG reconstruction algorithm
Author :
Jing Jing ; Liu Tie-Ming ; Jiang Lie-Hui ; Wang Zhen-Yu ; Wang Rui-Min
Author_Institution :
Inf. Sci. & Technol. Inst., Zheng Zhou, China
Abstract :
CFG (Control Flow Graph) is the cornerstone of reverse analysis, and how to determine the targets of indirect jumps is a challenge for CFG reconstruction. Based on BRIL (Binary Reverse Intermediate Language) and standard abstract interpretation framework, a K-set abstract domain based on abstract memory model was adopted. Control flow and data flow analysis could be executed on this abstract domain simultaneously and iteratively until a fix point was reached. Experimental evidence shows that the precision degree and the time cost are changing with the value of K. As long as K is set appropriately, the CFG reconstruction algorithm can resume accurate CFG in a moderate costs, and the average false positive rate of indirect jump destination address is less than one (<;1).
Keywords :
data flow analysis; flow graphs; BRIL; K-set abstract domain; abstract memory model; binary reverse intermediate language; control flow graph; data flow analysis; indirect jump destination address; precision degree; precision-tunable CFG reconstruction algorithm; reverse analysis; standard abstract interpretation framework; time cost; Abstracts; Algorithm design and analysis; Reconstruction algorithms; Registers; Semantics; Switches; abstract domain; constraint system; control flow graph; precision tunable; reconstruction;
Conference_Titel :
Mechatronic Sciences, Electric Engineering and Computer (MEC), Proceedings 2013 International Conference on
Conference_Location :
Shengyang
Print_ISBN :
978-1-4799-2564-3
DOI :
10.1109/MEC.2013.6885396