Control Flow:Representation,Extraction and Applications
Control Flow: Representation, Extraction and Applications
Program needs a representation for the analysis 1 #include <stdio.h> 2 int main(){ 3 printf("pid=%d\n",getpid()); 4 return 0; 5} c17f093d: 55 push %ebp c17f093e: 89e5 mov %esp,%ebp c17f0940: 83ec08 sub $0x8,%esp c17f0943: e8402d81ff call c1003688 <mcount> Original representations Source code(cross languages). Binaries (cross machines and platforms). >Source code binaries test cases. They are hard for machines to analyze. ● Software is translated into certain representation before analyses are applied. 2
2 Program needs a representation for the analysis • Original representations ➢ Source code(cross languages). ➢ Binaries (cross machines and platforms). ➢ Source code / binaries + test cases. • They are hard for machines to analyze. • Software is translated into certain representation before analyses are applied. 1 #include <stdio.h> 2 int main(){ 3 printf("pid=%d\n",getpid()); 4 return 0; 5 } c17f093d: 55 push %ebp c17f093e: 89 e5 mov %esp,%ebp c17f0940: 83 ec 08 sub $0x8,%esp c17f0943: e8 40 2d 81 ff call c1003688 <mcount>
Outline Static Program Representation >Control Flow Graph Program Dependence Graph >Points-to Graph >Call Graph Control Flow Graph Extraction >Source Code to CFG >ELF/PE File to CFG 。Applications >Control Flow Integrity -Principles and Implementations(CFI) >Practical Control Flow Integrity Randomization for Binary Executables(CCFIR) ●Summary 3
3 Outline • Static Program Representation ➢ Control Flow Graph ➢ Program Dependence Graph ➢ Points-to Graph ➢ Call Graph • Control Flow Graph Extraction ➢ Source Code to CFG ➢ ELF/PE File to CFG • Applications ➢ Control Flow Integrity – Principles and Implementations(CFI) ➢ Practical Control Flow Integrity & Randomization for Binary Executables(CCFIR) • Summary
Outline Static Program Representation >Control Flow Graph Program Dependence Graph >Points-to Graph >Call Graph Control Flow Graph Extraction >Source Code to CFG ELF/PE File to CFG 。Applications >Control Flow Integrity -Principles and Implementations(CFI) Practical Control Flow Integrity Randomization for Binary Executables(CCFIR) ●Summary 4
4 Outline • Static Program Representation ➢ Control Flow Graph ➢ Program Dependence Graph ➢ Points-to Graph ➢ Call Graph • Control Flow Graph Extraction ➢ Source Code to CFG ➢ ELF/PE File to CFG • Applications ➢ Control Flow Integrity – Principles and Implementations(CFI) ➢ Practical Control Flow Integrity & Randomization for Binary Executables(CCFIR) • Summary
Basic Blocks ●Definition A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point,and no internal branches Control always enters a basic block at its entry point and exits from its exit point.There is no possibility of exit or a halt at any point inside the basic block except at its exit point.The entry and exit points of a basic block coincide when the block contains only one statement. 5
5 Basic Blocks • Definition ➢ A basic block is a maximal sequence of consecutive statements with a single entry point, a single exit point, and no internal branches • Control always enters a basic block at its entry point and exits from its exit point. There is no possibility of exit or a halt at any point inside the basic block except at its exit point. The entry and exit points of a basic block coincide when the block contains only one statement