Postdominator X post-dominates Y if X every possible program path from Y to End has to pass X. >Strict post-dominator,immediate post-dominance. 1: sum=0 (1) sum=0 2:ie1 (2) i=1 (3) while (i<N)do 3:while (i<N)do (4) i=j+1 (5) sumsum +i endwhile 4:j=+1 (6) print(sum) 5: sum=sum+I SPD0M(4)={3,6}IDOM(6)={3} 6:print(sum) 16
16 Postdominator • X post-dominates Y if X every possible program path from Y to End has to pass X. ➢ Strict post-dominator, immediate post-dominance. (1) sum = 0 (2) i = 1 (3) while (i<N) do (4) i = i+1 (5) sum = sum + i endwhile (6) print (sum) SPDOM(4) = {3,6} IDOM(6) = {3}
Back Edges A back edge is an edge whose head dominates its tail. Back edges often identify loops. 1:sum=0 2:ie1 3:while (i<N)do ↓ 4:=1+1 5: sum=sum+I 6:print(sum) 17
• A back edge is an edge whose head dominates its tail. ➢ Back edges often identify loops. 17 Back Edges
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 18
18 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
Program Dependence Graph(PDG) A PDG for program P exhibits different kinds of dependencies among statement in P.For the purpose of testing,we consider data dependence and control dependence. Data dependence Control dependence 19
19 Program Dependence Graph(PDG) • A PDG for program P exhibits different kinds of dependencies among statement in P. For the purpose of testing, we consider data dependence and control dependence. ➢ Data dependence ➢ Control dependence
Data Dependence ● X is data dependent on Y if there is a variable v that is defined at Y and used at X and there exists a path of nonzero length from Y to X along which v is not re-defined. 1:sum=0 2:i=1 3:while (i<N)do 4:i+1 5:sum=sum+i 6:print (sum) 20
20 Data Dependence • X is data dependent on Y if ➢ there is a variable v that is defined at Y and used at X and ➢ there exists a path of nonzero length from Y to X along which v is not re-defined