Static and Dynamic Analysis
Christopher Parnin
Esprima for Static and Dynamic Analysis
https://www.youtube.com/watch?v=ACYZFkvq0Sk
Watching 5:00-14:30, 28:00-34:00
Bad Smells
Duplicated Code
Long Method
Message Chains
More Smells
Primitive Obsession
Long Parameter List
Data Clumps
Temporary Field
Refused Bequest
Divergent Change
Shotgun Surgery
Speculative Generality
Feature Envy
Static Analysis Tools
Coverity (http://cacm.acm.org/magazines/2010/2/69354-a-few-billion-lines-of-code-later/fulltext)
FindBugs,, PyLint, JsLint, CheckStyle
Parse Tools: Roslyn (.NET), Esprima, Eclipse JDT (Have headless parser)
Activity
Describe some other “bad smells” or properties you would detect?
Parsing JSON (White Board)
Mini-Workshop
Data Flow Analysis
A framework for proving facts about a program.
Examines how information propagates through blocks and paths of a program.
Content: http://www.seas.harvard.edu/courses/cs252/2011sp/slides/Lec02-Dataflow.pdf,
https://www.cs.umd.edu/class/spring2014/cmsc430/lectures/lec19.pdf
Reaching Definitions
A definition of a variable x is a statement that may modify the value of x.
A use of a variable x is a statement that reads from x.
A definition at node k reaches node n if there is a definition-free path from k to n.
Def-Use/Use-Def Chains
DU-Chain: Links each def to uses it reaches
UD-Chain: Links each use to reaching defs
foo(b) {
x = 1;
if( b < 0 )
{
x = 2;
}
b = x;
}
| Gen | Kill | Flow | RD |
B1 | entry(B) | B | entry(B) U ( ∅ - B ) | entry(B) |
B2 | B2(X) | X | B2(X) U ( entry(B) - X ) | B2(X), entry(B) |
B3 | | | ∅ U ({B2(X),entry(B)} - ∅ ) | B2(X), entry(B) |
B4 | B4(X) | X | B4(X) U ({B2(X),entry(B)} - X) | B4(X), entry(B) |
B5 | B5(B) | B | B5(B) U {B2(X),B4(X),entry(B) - B} | B2(X), B4(X), B5(B), |
Worklist Algorithm
OUT[ENTRY] = empty_set;
for (each block B other than ENTRY)
OUT[B] = empty_set;
while (changes to any OUT occur)
for (each block B other than ENTRY)
{
IN[B] = ∪P a predecessor of B OUT[P]; OUT[B] = genB ∪ (IN[B] ─ killB);
}
Dynamic Analysis
Coverage… using instrumentation… probes
Important later for testing...performance...
Other Techniques:
Slicing
Performance, Memory Load
Taint Analysis
Random Testing
Random Testing
Activity: Why not just randomly generated input and see what happens?
Fuzzing
Applying Analysis to Deployment
Discuss how you might apply any of these techniques as a “Quality Gate” in a deployment pipeline.