A precision-tunable CFG reconstruction algorithm
Jing Jing, Liehui Jiang, Tieming Liu, Wang Zhen-Yu, Ruimin Wang · 2013
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).