Static Analysis
Static analysis examines software without executing it, finding defects through automated inspection of source code, bytecode, or binaries. It complements testing by catching entire classes of bugs early and efficiently.
What is Static Analysis?
Static analysis uses automated tools to examine code structure, data flow, and control flow to detect:
- Potential bugs and errors
- Security vulnerabilities
- Code style violations
- Performance issues
- Maintainability problems
Unlike testing, which finds specific instances of failures, static analysis identifies patterns that might cause problems. It reasons about all possible executions rather than observing a single run.
Why Static Analysis Matters
Static analysis provides unique advantages over dynamic techniques:
| Benefit | Detail |
|---|---|
| Early defect detection | Find issues before code runs; finding defects during development is 10x cheaper than finding them in testing [1] |
| Comprehensive coverage | Analyze all code paths, not just executed ones |
| Fast feedback | Runs in seconds or minutes, not hours |
| Consistent standards | Enforce coding rules automatically across teams |
| Zero runtime overhead | No performance impact on production |
Industrial evidence: Automated static analysis (ASA) achieves a defect yield of 23-37%, comparable to manual inspection, at 60-72% of the cost [2]. When combined with testing and inspection, static analysis catches fault types that the other techniques miss.
The Soundness-Completeness Tradeoff
A fundamental theoretical result constrains what static analysis can achieve.
Rice’s Theorem [3]: For any non-trivial semantic property of programs, no algorithm can decide whether an arbitrary program has that property. In other words, perfect static analysis is undecidable.
This forces every practical tool to make a choice:
| Property | Meaning | Guarantee | Trade-off |
|---|---|---|---|
| Sound | Over-approximates program behavior | No false negatives (all real bugs found) | May report false positives |
| Complete | Under-approximates program behavior | No false positives (all reports are real) | May miss real bugs |
| Neither | Practical balance | Efficient and useful | Some bugs missed, some false alarms |
Most practical tools – Coverity, SonarQube, CodeQL, SpotBugs – are neither perfectly sound nor complete. They balance precision and recall through heuristics, pattern matching, and configurable sensitivity levels.
No tool can simultaneously find all bugs, report only real bugs, and always terminate. Understanding this tradeoff is essential for setting realistic expectations about what static analysis can and cannot do.
Topics in This Section
Analysis Techniques
The building blocks of static analysis, from simple lexical pattern matching to sophisticated taint tracking:
- Lexical analysis and style checking
- AST pattern matching
- Type checking and null safety
- Control flow and dataflow analysis
- Taint analysis for security
Dataflow Analysis
Track variable states through program execution paths to detect bugs that simpler techniques miss:
- Abstract domains and lattices (zero analysis, null analysis)
- Transfer functions and fixed-point computation
- Step-by-step walkthrough: detecting divide-by-zero
- Industrial tools: Facebook Infer, Coverity, Clang Static Analyzer
Symbolic Execution
Treat inputs as symbolic variables and use constraint solving to explore paths systematically:
- Path conditions and SMT solvers
- Concolic testing (concrete + symbolic)
- KLEE: 90%+ coverage on GNU COREUTILS, 56 bugs found
- Challenges: path explosion, constraint solving, environment modeling
Model Checking
Exhaustive state exploration for verifying temporal properties of concurrent systems:
- Safety and liveness properties in temporal logic (LTL)
- SPIN, SLAM, Java PathFinder, CBMC
- CEGAR: Counter-Example Guided Abstraction Refinement
- Detailed locking discipline example with product automaton
Modern Tools
Industrial static analysis tools and platforms for real-world deployment:
- Google Tricorder: 93,000 findings/day with <10% false positive threshold
- Facebook Infer: separation logic for memory safety at diff time
- The tool agreement problem: <0.4% overlap between tools
- LLM-assisted analysis: IRIS achieves +103% detection over CodeQL alone
The Technique Continuum
Static analysis techniques form a continuum from fast and shallow to slow and deep. Choosing the right level depends on the criticality of the software and the budget for analysis [4].
| Technique | Precision | Recall | Cost |
|---|---|---|---|
| Style checking | High | Low | Cheap |
| AST patterns | Medium | Medium | Cheap |
| Type checking | High | Low | Medium |
| Dataflow analysis | Medium-High | Medium | Medium |
| Control flow analysis | Medium | Medium | Medium |
| Taint analysis | Medium | Medium | Medium |
| Model checking | High | High | Expensive |
| Theorem proving | Very High | Variable | Very Expensive |
Key insight: There is no single “best” technique. Shallow techniques catch surface-level issues cheaply across large codebases, while deep techniques provide stronger guarantees for critical components. Industrial practice combines multiple techniques at different levels [5].
Further Exploration
- V&V Overview – The broader landscape of verification and validation techniques
- Inspection – Manual review techniques that complement automated analysis
- Test Coverage Criteria – Measuring thoroughness of dynamic testing
References
- C. Jaspan, I.-C. Chen, and A. Sharma, “Understanding the Value of Program Analysis Tools,” in Companion to the 22nd ACM SIGPLAN Conference on Object-Oriented Programming Systems and Applications (OOPSLA), 2007, pp. 963–970. doi: 10.1145/1297846.1297964.
- J. Zheng, L. Williams, N. Nagappan, W. Snipes, J. P. Hudepohl, and M. A. Vouk, “On the Value of Static Analysis for Fault Detection in Software,” IEEE Transactions on Software Engineering, vol. 32, no. 4, pp. 240–253, 2006, doi: 10.1109/TSE.2006.38.
- H. G. Rice, “Classes of Recursively Enumerable Sets and Their Decision Problems,” Transactions of the American Mathematical Society, vol. 74, no. 2, pp. 358–366, 1953, doi: 10.2307/1990888.
- B. Chess and J. West, Secure Programming with Static Analysis. Addison-Wesley, 2007.
- C. Sadowski, J. van Gogh, C. Jaspan, E. Söderberg, and C. Winter, “Tricorder: Building a Program Analysis Ecosystem,” in Proceedings of the 37th International Conference on Software Engineering (ICSE), 2015, pp. 598–608. doi: 10.1109/ICSE.2015.76.
Disclaimer: AI is used for text summarization, polishing and explaining. Authors have verified all facts and claims. In case of an error, feel free to file an issue.