【導(dǎo)讀】WhatisChord?Keygoals:. Analysesas“buildingblocks”。Part1:. Part2:. Part3:. DynamicAnalysis. –Chord?–test/(Chord?–…Requirements:. Optional:edit. ant–f<...>/[–Dkeyi=vali]*run. requiresApacheAnt. java–cp<…>/[–Dkeyi=vali]*. where<…>denotespathofChord?smain/directory. defaultvalue="[]/". tofinish???

　　

【正文】 Event List events floors Obj[] elems Obj[] elems Floor 0 Floor 1 Event 1 b el fl f e e f a a disjointreach(el, fl)? 0CFA Pointer Analysis for Java ? Flow sensitivity ? flowinsensitive: ignores intraprocedural control flow ? Call graph construction ? Heap abstraction ? Aggregate modeling ? Context sensitivity Example: Flow Insensitivity class List { Obj[] elems。 List() { Obj[] a = new Obj[…]。 = a。 } } class Bldg { List events, floors。 static void main(String[] a) { Bldg b = new Bldg()。 } Bldg() { List el = new List()。 = el。 List fl = new List()。 = fl。 Event e = new Event()。 [ ] = e。 Floor f = new Floor()。 [ ] = f。 } } for (int i = 0。 i K。 i++) for (int i = 0。 i M。 i++) * i* i0CFA Pointer Analysis for Java ? Flow sensitivity ? flowinsensitive: ignores intraprocedural control flow ? Call graph construction ? “onthefly”: mutually recursively with pointer analysis ? Heap abstraction ? Aggregate modeling ? Context sensitivity Example: Call Graph (Base Case) Code deemed reachable so far … class List { Obj[] elems。 List() { Obj[] a = new Obj[…]。 = a。 } } for (int i = 0。 i K。 i++) for (int i = 0。 i M。 i++) class Bldg { List events, floors。 static void main(String[] a) { Bldg b = new Bldg()。 } Bldg() { List el = new List()。 = el。 List fl = new List()。 = fl。 Event e = new Event()。 [*] = e。 Floor f = new Floor()。 [*] = f。 } } reachableM(0). 0CFA Pointer Analysis for Java ? Flow sensitivity ? flowinsensitive: ignores intraprocedural control flow ? Call graph construction ? “onthefly”: mutually recursively with pointer analysis ? Heap abstraction ? allocation sites: objects at same site indistinguishable ? Aggregate modeling ? Context sensitivity Example: Heap Abstraction class List { Obj[] elems。 List() { Obj[] a = new6 Obj[…]。 = a。 } } for (int i = 0。 i K。 i++) for (int i = 0。 i M。 i++) class Bldg { List events, floors。 static void main(String[] a) { Bldg b = new1 Bldg()。 } Bldg() { List el = new2 List()。 = el。 List fl = new3 List()。 = fl。 Event e = new4 Event()。 [*] = e。 Floor f = new5 Floor()。 [*] = f。 } } v = newh … Rule for Object Allocation Sites ? Before: ? After: v newh’ … … v newh newh’ … … VH(v, h) : reachableM(m), MobjValAsgnInst(m, v, h). v1 = v2 Rule for Copy Assignments ? Before: ? After: v1 newh’ … … v1 newh newh’ … … VH(v1, h) : reachableM(m), MobjVarAsgnInst(m, v1, v2), VH(v2, h). v2 newh … … v2 newh … … 0CFA Pointer Analysis for Java ? Flow sensitivity ? flowinsensitive: ignores intraprocedural control flow ? Call graph construction ? “onthefly”: mutually recursively with pointer analysis ? Heap abstraction ? allocation sites: objects at same site indistinguishable ? Aggregate modeling ? instance field sensitive but array element insensitive ? Context sensitivity = v b Rule for Heap Writes ? Before: ? After: newh1 … … v newh2 … … v newh2 … … newh3 newh1 … … newh1 f newh2 newh3 … … … … b newh1 … … f f f is instance field or [*] (array element) HFH(h1, f, h2) : reachableM(m), MputInstFldInst(m, b, f, v), VH(b, h1), VH(v, h2). v = v Rule for Heap Reads newh v newh2 newh … … … … … … b newh1 … … b newh1 … … newh2 newh1 … … f newh2 newh1 … … f f is instance field or [*] (array element) ? Before: ? After: VH(v, h2) : reachableM(m), MgetInstFldInst(m, v, b, f), VH(b, h1), HFH(h1, f, h2). 0CFA Pointer Analysis for Java ? Flow sensitivity ? flowinsensitive: ignores intraprocedural control flow ? Call graph construction ? “onthefly”: mutually recursively with pointer analysis ? Heap abstraction ? allocation sites: objects at same site indistinguishable ? Aggregate modeling ? instance field sensitive but array element insensitive ? Context sensitivity ? contextinsensitive: ignores interprocedural control flow (analyzes each method in single context) ? Before: ? After: () () () Rule for Dynamically Dispatching Calls v newh … … v newh … … T T i i () { …。 。 …。 } CHA(T, foo) = () { … } () { … } IM(i, m) : reachableM(n), MI(n, i), virtIM(i, m?), IinvkArg0(i, v), VH(v, h), HT(h, t), CHA(t, m?, m). reachableM(m) : IM(_, m). name=cipa0cfadlog .include .include ... .bddvarorder M0xI0_F0_V0xV1_T0_H0xH1 VT(v:V0, T0) input reachableM(m:M0) FH(f:F0, h:H0) output VH(v:V0, h:H0) output HFH(h1:H0, f:F0, h2:H1) output IM(i:I0, m:M0) output ... reachableM(m) : IM(_, m). ... Writing a Datalog Analysis analysis constraints (Horn clauses) solved via BDD operations input, intermediate, output program relations represented as BDDs BDD variable order program domains Running a Datalog Analysis chord_output/ bddbddb/ , , , name=cipa0cfadlog .include .include ... .bddvarorder M0xI0_F0_V0xV1_T0_