1Dataflow Analysis in Practice:

Program Analysis Frameworks,

Analysis Scope and Approximation 1 Announcements n HW1 due today n HW2 posted n Your task is to set the infrastructure locally n Start as soon as you can

n Ask questions on Submitty, in class, in office

hours n Run Soot on toy programs and study Jimple IR CSCI 4450/6450, A Milanova 2 2 2So Far and Moving On… n Dataflow analysis n Four classical dataflow problems n Dataflow frameworks n CFGs, lattices, transfer functions and properties,

worklist algorithm, MFP vs. MOP solutions n Non-distributive analysis n Constant propagation n Points-to analysis (will cover in catchup week!) n Program analysis in practice CSCI 4450/6450, A Milanova 3 3 Outline of Today’s Class n Constant propagation (recap) n Program analysis in practice n Program analysis frameworks n Soot program analysis framework n Ghidra framework n Analysis scope and approximation n Class analysis CSCI 4450/6450, A Milanova 4 4 3Constant Propagation fits into

Monotone Dataflow Framework n Property space n Product lattice L = Lx x Ly x … x Lz n L satisfies the ACC and

n Function space F: Là L is monotone n Thus, analysis fits into the monotone

dataflow framework and can be solved using

the worklist algorithm CSCI 4450/6450, A Milanova 5 T T … -2

-1

0

1

2

... Lx: 5 Example CSCI 4450/6450, A Milanova 6 2. x=1 y=2 3. x=2 y=1 4. z=x+y 1.

if (b>0) 5. w=10*z out(2):

out(3):

in(4):

out(4):

in(5):

in(1) is T =

6 4Constant Propagation is

Monotone but Not Distributive!

n f4(f2(f1(T))) computes zà 3 n f4(f3(f1(T))) computes zà 3 n Thus, MOP at 5 f4(f2(f1(T))) V f4(f3(f1(T))) computes zà 3 MFP at 5 computes zà T (i.e., z is NOT a const)

7 2. x=1 y=2 3. x=2 y=1 4. z=x+y 1.

if (b>0) 5. w=10*z out(2): xà1, yà2 out(3): xà2, yà1 in(4): xà T, yà T

out(4): zà T

in(5): zà T in(1) is T 7 More Product Lattices n Problem statement: Is integer variable x odd

or even at program point n? n Lx: CSCI 4450/6450, A Milanova (Example program from MIT OCW Program Analysis) 8 x=x+1 y=y+2 … if (x≥10) T F xà T, yà T

y=0 T T odd

even

xà T, yà even

xà T, yà even

xà T, yà even

8 5More Product Lattices n Problem statement: What sign does a

variable hold at a given program point, i.e., is

it positive, negative, or 0 n Lx: E.g., < xà+,yàT,zà0 > CSCI 4450/6450, A Milanova 9 T T +

0

- 9 So far and moving on n Intraprocedural dataflow analysis n CFGs, lattices, transfer functions, worklist

algorithm, etc. n Classical analyses n Interprocedural analysis n Analysis scope and approximation CSCI 4450/6450, A Milanova 10 10 6Program Analysis in Practice n Program analysis frameworks n LLVM n Ghidra n Soot n WALA, other CSCI 4450/6450, A Milanova 11 11 Soot: a framework for analysis and

optimization of Java/Dalvik bytecode n https://soot-oss.github.io/soot/ n History n Overview of Soot n From Java bytecode/Dalvik bytecode to typed 3-address code (Jimple) n 3-address code analysis and optimization n From Jimple to Java/Dalvik n Jimple n Analysis 12 12 7History n https://soot-oss.github.io/soot/ n Started by Prof. Laurie Hendren at McGill n First paper on Soot came in 1999 n Patrick Lam n Ondřej Lhoták n Eric Bodden n and other… n Now developed by Eric Bodden and his

group: https://github.com/soot-oss/soot 13CSCI 4450/6450, A Milanova 13 Overview of Soot Class files/APK JIMPLIFY Some IR ANALYSIS/ OPTIMIZATION Optimized jimple Class files/APK 14CSCI 4450/6450, A Milanova 14 8Advantages of Jimple and Soot n Jimple n Typed local variables n 16 simple 3-address statements (1 operator per

statement). Bridges gap from analysis

abstraction to analysis implementation n Soot provides n Itraprocedural dataflow analysis framework n Points-to analysis for Java n IR from Dalvik and taint analysis n Other analyses and optimizations 15 15 n Run soot: java soot.Main –jimple A

(need paths) public class A { main(String[] args) { A a = new A(); a.m(); } public void m() { }

} public class A extends java.lang.Object

{

public void () {

A r0; r0 := @this: A; specialinvoke r0. ()>(); return;

} … (continues on next slide…) 16 Jimple CSCI 4450/6450, A Milanova 16 9public class A { main(String[] args) { A a = new A(); a.m(); } public void m() { }

} … public void m() { A r0; r0 := @this: A; return; }

… Jimple CSCI 4450/6450, A Milanova 17 Java: Jimple: 17 public class A { main(String[] args) { A a = new A(); a.m(); } public void m() { }

} … main(java.lang.String[]) { java.lang.String[] r0; A $r1, r2; r0 := @parameter0: java.lang.String[]; $r1 = new A; specialinvoke $r1.()>(); r2 = $r1; virtualinvoke r2.(); return;

}

} Jimple CSCI 4450/6450, A Milanova 18 Java: Jimple: 18 10 n Abstracts program constructs n Some basic Soot classes and interfaces

n SootClass n SootMethod n SootMethod sm; sm.isMain(), sm.isStatic(), etc. n Local n Local l; … l.getType() n InstanceInvokeExpr n Represents an instance (as opposed to static) invoke

expression n InstanceInvokeExpr iie; … receiver = iie.getBase(); Soot Abstractions. Look up API! CSCI 4450/6450, A Milanova 19 19 n Github project:

https://github.com/soot-oss/soot n Javadoc:

https://soot-build.cs.uni-paderborn.de/public/origin/develop/soot/soot- develop/jdoc/ (old) https://javadoc.io/doc/ca.mcgill.sable/soot/latest/index.html Resources CSCI 4450/6450, A Milanova 20 20 11 n Constructor/Super Call: n Virtual Call: n Static Call: n Interface Call: 1. We should not need to worry about dynamicInvoke. (Soot

does support it.) A a = new A(); $r1 = new A; specialinvoke $r1.()>(); a.m(); virtualinvoke r2.(); sm(); staticinvoke (); interfaceinvoke r0.();x.m(); 4 Kinds of Calls1 21 21 Outline of Today’s Class n Program analysis in practice n Program analysis frameworks n Soot program analysis framework n Ghidra framework n Analysis scope and approximation n Overview of class analysis framework (HW2) n Class analysis CSCI 4450/6450, A Milanova 22 22 12 Analysis Scope n Intraprocedural analysis n Scope is the CFG of a single subroutine n Assumes no call and returns in routine, or

models calls and returns n What we did so far n Interprocedural analysis n Scope of analysis is the ICFG (Interprocedural

CFG), which models flow of control between

routines CSCI 4450/6450, A Milanova 23 23 Analysis Scope n Whole-program analysis n Usually, assumes entry point “main” n Application code + libraries n Intricate interdependences, e.g., Android apps n Modular analysis n Scope either a library without entry point n or application code with missing libraries n … or a library that depends on other missing

libraries

CSCI 4450/6450, A Milanova 24 24 13 Approximations n Once we tackle the “whole program”

maintaining a solution per program point (i.e.,

in(j) and out(j) sets) becomes too expensive n Approximations n Transfer function space n Lattice

n Context sensitivity n Flow sensitivity CSCI 4450/6450, A Milanova 25 25 Context Sensitivity n So far, we studied intraprocedural analysis

n Once we extend to interprocedural analysis

the issue of “context sensitivity” comes up n Interprocedural analysis can be context- insensitive or context-sensitive n In our Java homework, we’ll work with context- insensitive analyses n We’ll talk more about context-sensitive analysis 26CSCI 4450/6450, A Milanova 26 14 Context Insensitivity n Context-insensitive analysis makes one big

CFG; reduces the problem to standard

dataflow, which we know how to solve n Treats implicit assignment of actual-to- parameter and return-to-left_hand_side as

explicit assignment n E.g., x = id(y) where id: int id(int p) { return p; } adds p = y // flow of values from arg to param and

x = ret // flow of return to left_hand_side n Can be flow-sensitive or flow-insensitive 27 27 Context Insensitivity int id(int p) { return p;

} a = 5; 2: b = id(a); x = b*b; c = 6; 5: d = id(c);

CSCI 4450/6450, A Milanova 28 1. a = 5 2. p = a call id 3. return id b = ret 5. p = c call id 6. return id d = ret 4. x = b*b c = 6 7. entry id

8. ret = p

9. exit id

28 15 Flow Sensitivity n Flow-sensitive vs. flow-insensitive analysis n Flow-sensitive analysis maintains the CFG

and computes a solution per each node in

CFG (i.e. each program point) n Standard dataflow analysis is flow-sensitive n For large programs, maintaining CFG and

solution per program point does not scale CSCI 4450/6450, A Milanova 29 29 Flow Insensitivity n Flow-insensitive analysis discards CFG

edges and computes a single solution S n A “declarative” definition, i.e., specification: n Least solution S of equations S = fj(S) V S n Points-to analysis is an example where such a

solution makes sense! CSCI 4450/6450, A Milanova 30 30 16 Flow Insensitivity n An “operational” definition. A worklist

algorithm: S = 0, W = { 1, 2, … n } /* all nodes */ while W ≠ Ø do { remove j from W S = fj(S) V S if S changed then

W = W U { k | k is ”successor” of j }

} n “successor” is not CFG successor nodes, but

more generally, nodes k whose transfer

function fk may be affected as a result of the

change in S by j 31 31 Your Homework n A bunch of flow-insensitive, context- insensitive analyses for Java n RTA, 0-CFA, PTA, other n Simple property space n Simple transfer functions n E.g., in fact, RTA gets rid of most CFG nodes,

processes just 2 kinds of nodes! n Millions of lines of code in seconds CSCI 4450/6450, A Milanova 32 32 17 Homework n Install and run starter code n Please let me as soon as possible if you have

issues n Frameworks are very fragile. They anger a lot n Look into your git_repo/sootOutput directory

and study Jimple n Study framework code and API n Soot API n Class analysis framework API CSCI 4450/6450, A Milanova 33 33 Homework n Overview of class analysis framework n We’ll discuss more on Thursday n Come prepared with questions CSCI 4450/6450, A Milanova 34 34