1. Introduction to Software Analysis Flashcards
What is program analysis
Body of work to automatically discover useful facts about programs.
What are the three kinds of analyses?
- Dynamic (run-time) - discovers information by running the program
- Static (compile-time) - discovers information by inspecting the source code or binary code of the program
- Hybrid (combines dynamic + static)
What is Dynamic Program Analysis?
What kinds of problems can it identify and what are some example tools?
Infers facts about a program by monitoring its runs. B/c it runs a finite number of times it cannot discover information that requires observing an unbounded number of paths.
Examples:
- Array bound checking (e.g., Purify)
- Memory leak detection (e.g., Valgrind)
- Data race detection (e.g., Eraser)
- Finding likely invariants (e.g., Daikon)
What is Static Program Analysis?
What kinds of problems can it identify and what are some example tools?
Infers facts about a program by inspecting its code. Can discover invariants even for programs that have an unbounded number of paths.
Examples:
- Suspicious error patterns (e.g., Lint, FindBugs, Coverity)
- Checking API usage rules (e.g., Microsoft SLAM)
- Memory leak detection (e.g., Facebook Infer)
- Verifying invariants (e.g., ESC/Java)
Compare Dynamic vs Static Analysis on cost and effectiveness.
Cost
- Dynamic: proportional to program’s execution
- Static: Proportional to program’s size
Effectiveness
- Dynamic: Unsound (may miss errors - false negatives)
- Static: Incomplete (may report spurious errors - false positives)
Who are the primary consumers of program analysis?
- Compilers use program analysis to generate efficient code
- Software quality tools use program analysis to find errors, prove invariants, generate test cases, localize cause of errors
- Integrated Development Environments (IDEs) use program analysis to help programmers understand and refactor programs