The Use of PDG ● A program dependence graph consists of control dependence graph and data dependence graph. Why it is so import to software reliability? In debugging,what could possibly induce the failure? In security (1) p getpassword(); (1) p getpassword(); (2) … (2) (3) send(p); (3) if(p=“zhang")X (4) send(m); (5) } 26
26 The Use of PDG • A program dependence graph consists of control dependence graph and data dependence graph. • Why it is so import to software reliability? ➢ In debugging, what could possibly induce the failure? ➢ In security (1) p = getpassword(); (2) … (3) send(p); (1) p = getpassword(); (2) … (3) if (p == “zhang”){ (4) send (m); (5) }
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 27
27 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
Points-to Graph Pointer-to Graph:At a program point,compute a set of pairs of the from p->x,where p MAY MUST pointer to x. m(p){ r=new C(); p->f=r; t=new C(); p if (.. q=p; r->f=t; p->f->f and t are aliases 28
28 Points-to Graph • Pointer-to Graph: At a program point, compute a set of pairs of the from p -> x, where p MAY / MUST pointer to x. m (p) { r = new C(); p -> f = r; t = new C(); if (…) q = p; r -> f = t; } r f p t q f p->f->f and t are aliases
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 29
29 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
Call Graph Each node represents a function;each edge represents a function invocation. Void A () Void B(){ A B0; D0; c(0: D(0; } B Voidc(){ Void D(){ D(0; A(); D } 30
30 Call Graph • Each node represents a function; each edge represents a function invocation. Void A () { B(); C(); } Void C () { D(); A(); } Void B () { D(); D(); } Void D () { }