Module 1: What is Program Analysis? Overview of Dynamic, Static, Hybrid

Question 1

what is program analysis?

Answer 1

body of work to discover useful facts about programs (e.g. errors)

Question 2

3 types of program analysis

Answer 2

1. dynamic (execution time)
2. static (compile time)
3. hybrid (combines dynamic and static)

Question 3

dynamic program analysis

Answer 3

infers facts about the program by monitoring its runs

• purify: array bound checking
• memory leak detection: valgrind
• data race detection: eraser
• finding likely invariants: daikon

Question 4

static analysis

Answer 4

infers facts about the program by inspecting its source or binary code

• suspicious error patterns: lint, findbugs, coverity
• checking api usage rules: microsoft slam
• memory leak detection: facebook infer
• verifying invariants: ESC/Java

Question 5

program invariant

Answer 5

a fact that is true in every run of the program
static analysis: can determine that something is definitely an invariant
dynamic analysis: can determine that something is likely an invariant

Question 6

components of static analysis

Answer 6

1. program representation: e.g. control-flow graph, AST, or bytecode
2. abstract domain: e.g. how to approximate program values
3. transfer function: e.g. assignments, conditionals, merge points
4. fixed point computation algorithm: e.g. iterative approximation

Question 6

components of static analysis

Answer 6

1. program representation: e.g. control-flow graph, AST, or bytecode
2. abstract domain: e.g. how to approximate program values
3. transfer function: e.g. assignments, conditionals, merge points
4. fixed point computation algorithm: e.g. iterative approximation

Question 7

how can static analysis be sound even though it sacrifices completeness?

Answer 7

even though the abstraction causes us to lose some information, when the analysis concludes something about the program, it is true in all runs of the program

Question 8

when is a program sound?

Answer 8

if it never accepts bad programs

Question 9

when is a program complete?

Answer 9

if it never rejects a good program

Question 10

decide if the analysis (depicted by the blue oval) is sound or complete:

Answer 10

sound

not complete

Question 11

false positive

Answer 11

a good program that is rejected by an analysis

Question 12

is this analysis sound or complete?

Answer 12

not sound

complete

Question 13

false negative

Answer 13

bad program that is accepted by an analysis

Question 14

precision and recall (a method of measuring the usefulness of an analysis)

Answer 14

Question 15

f-measure

Answer 15

Question 16

f-measure of best possible program analysis

Answer 16

1

Question 17

f-measure of worst possible program analysis

Answer 17

0

Question 18

3 consumers of program ananlysis

Answer 18

compilers
IDE’s
software quality tools (testing, debugging, verification) - main focus of course