Static Analysis
Answering questions about every possible execution without running any of them. A compiler frontend is already a static analyser; the interesting part is not the machinery but the two ways it fails — noise you turn off, and silence you trust.
What can a tool tell me about my program before it runs, and how much should I believe it?
The program as the frontend already holds it — an AST with a symbol table, lowered to a control-flow graph — plus a set of *facts* claimed to hold at each program point: this variable is definitely null here, this value came from user input, this block is unreachable, this file handle is still open. The facts are the object of study; the program is only their carrier. That is why the same framework answers questions about types, nulls, taint and leaks without changing shape.
An analysis is entitled to assume what earlier phases established: the file parsed, names resolved, and (in a statically typed language) the program type-checked, so an expression annotated int really is one on every execution that reaches it. It is *not* entitled to assume anything it has not derived — that a function has no side effects, that two pointers do not alias, that a default branch is unreachable. For a sound analysis there is one further precondition: every fact it reports must hold on every concrete execution, which forces it to over-approximate at every point where it cannot decide. An analysis that abandons that precondition is still useful; it is just no longer allowed to say "cannot happen".
Key points
- A static analysis computes facts that hold at every program point without running the program; a type checker is one instance of the machinery, not a different thing.
- Sound means it never misses a real problem, and therefore produces false positives. Complete means every report is real, and therefore misses things.
- Rice's theorem is the reason you cannot have both: every non-trivial semantic property of programs in a Turing-complete language is undecidable.
- False positives kill a tool socially — suppression, then disablement, then irrelevance. The precision budget is an attention budget.
- False negatives kill a tool epistemically: a clean run means "this configuration saw nothing", and silence looks the same as safety.
- The families are nullability, data flow, taint, reachability, resource/typestate and syntactic patterns — one framework, different lattices.
- Ask what class a check covers, whether it is sound or complete for that class, and where it bailed out. "Did it find anything" is the wrong question.
It is the same machine as the type checker
A type checker is a static analysis. It walks a representation the frontend built, computes a fact per program point ("this expression has type string"), combines facts where control flow merges, and reports where the facts contradict the rules. Change the fact from a type to "may be null", "is tainted by user input", "holds a lock", "owns an open file" and nothing structural changes — the same traversal, the same merge at joins, the same fixed point over loops. [[type-checking]] is the instance everyone already accepts; the rest of this module is the same machinery pointed elsewhere.
That is the reason this lesson exists in a compilers domain at all. Static analysis is usually taught as a separate product category — buy a scanner, run it in CI — and the effect is that engineers treat its findings as opinions from outside. They are not. They are the frontend telling you what it derived, and it derived them from the same [[symbol-table]], the same [[control-flow-graph]] and the same [[data-flow-framework]] that decide whether your code compiles.
The families worth naming, because each answers a different question and fails differently:
- Nullability / definite assignment — is this reference definitely non-null, definitely null, or unknown at this point? Kotlin, C# and TypeScript run this in the type checker; C and Java run it in a separate tool, if at all. See
[[nullability]]. - Data-flow facts — reaching definitions, liveness, available expressions, constant propagation. The optimizer's analyses, reused for diagnostics: an unused variable is a liveness result, an always-true condition is a
[[constant-propagation]]result. - Taint / information flow — does a value derived from an untrusted source reach a sink that must not receive one? Sources, sinks and sanitizers are configuration; the propagation is ordinary data flow.
- Reachability — can control reach this statement at all? Unreachable code after a return is trivial; unreachable because a condition is provably false requires the value analysis to have run first.
- Resource / typestate — is every acquired handle released on every path, including the exceptional ones? This is the one where the CFG matters most, because the interesting paths are the ones nobody wrote.
- Structural / pattern rules — this API is misused, this comparison is between incompatible units, this loop index shadows an outer one. Cheap, syntactic, and the bulk of what a linter actually ships.
Soundness and completeness, and why you cannot have both
any, non-null assertions) in exchange for usability on existing JavaScript; Infer runs a sound analysis internally and then filters the results to a complete-ish report, because shipping every over-approximation would be unusable. Ask which claim a tool makes about which check, not whether "it is sound".Two words that get used loosely and mean precise, opposite things. An analysis is sound if it never misses a real problem: if it says "no null dereference here", there is none on any execution. It is complete if it never reports a problem that is not real: every warning corresponds to an execution that actually does the bad thing. Sound analyses over-approximate — they consider executions that cannot happen — and therefore produce false positives. Complete analyses under-approximate and therefore miss things.
You cannot have both for a Turing-complete language, and the reason is one sentence: Rice's theorem says every non-trivial semantic property of programs is undecidable, so any terminating analyser must either report things that will not happen or stay silent about things that will. Every real tool picks a point on that line, and the honest ones tell you which.
The vocabulary matters because the two failure modes have completely different organisational consequences, and mixing them up is how teams end up with a scanner that runs in CI and blocks nothing.
| Stance | Guarantees | Failure you experience | Who ships this |
|---|---|---|---|
| Sound (over-approximate) | If it is silent, the property holds on every execution | False positives — warnings on code that is fine, in proportion to how little the tool can prove | Type checkers, borrow checkers, Astrée, Frama-C's value analysis |
| Complete (under-approximate) | Every report is a real, reachable defect | False negatives — quiet on real bugs, and quiet in a way that looks like a clean bill of health | Most bug-finders: Coverity, Infer's default mode, go vet |
| Neither, deliberately | Nothing formal; a curated set of high-value heuristics | Both, in a ratio tuned by the maintainers against real codebases | Linters, clang-tidy, ESLint, Clippy |
The two ways it dies
A static analysis fails in production in exactly two ways, and both are social rather than technical.
Too many false positives, and people turn it off. Not formally — nobody files a ticket saying "we are disabling correctness". It decays: first a suppression comment on one line, then a rule disabled in one directory, then a blanket --disable in the CI invocation with a commit message that says "unblock the build", then two years later nobody remembers the tool exists. The tool's precision budget is not a technical parameter; it is the rate at which engineers will keep reading its output. A checker at 30% precision is worse than no checker, because it consumes attention and then gets ignored along with the 30% that were real.
Too many false negatives, and it becomes a false comfort. A clean run reads as "no bugs of this class", and it almost never means that. It means "no bugs of this class that this analysis, with this configuration, on the paths it explored, within its time budget, was able to see". The gap is invisible from the outside: silence looks identical whether the code is clean or the analyser gave up on a function that exceeded its complexity limit. Tools that quietly bail out on large functions — most of them do, because interprocedural analysis has a compile-time budget — are the sharp edge here.
The practical consequence is that "did it find anything?" is the wrong question to ask of a static analysis. The right ones are: what class of defect does this check claim to cover, is it sound or complete for that class, what is its measured precision on our code, and where did it give up?
1char *read_name(int fd, int n) {2 char *buf = malloc(n); /* [1] n may be <= 0; malloc may return NULL */3 read(fd, buf, n); /* [2] buf dereferenced without a null check */4 if (n > 0 && buf[0] == 0) {5 return NULL; /* [3] buf leaks on this path */6 }7 return buf;8}Finding [1] needs a value/interval analysis of n. Finding [2] needs nullability plus the knowledge that malloc may fail — a *modelled* fact about a library function, not something derived from source. Finding [3] needs the CFG, because the leak exists only on the early-return path that nobody wrote a test for. Three questions, three lattices, one frontend. And a tool that models malloc as never failing reports none of them and looks clean.
The same id, two domains
This lesson shares an id with Security Engineering's static-analysis, and the collision is deliberate rather than an oversight. There, the subject is finding vulnerabilities: the taxonomy of injection, traversal and deserialization flaws, the SAST tools that hunt them, the triage workflow, and how findings enter a security programme. Here, the subject is the machinery — what a frontend has already computed, what a lattice is, why over-approximation forces false positives, and where the analysis gives up.
Both readings are correct where they live, and they are complementary rather than competing. A security engineer who understands why a taint analysis has false negatives at reflection boundaries triages better; a compiler engineer who understands what a sink is builds a more useful checker. What neither should do is assume the other's framing: "the scanner found nothing" is a statement about an analysis's precision and coverage, not about the code.
How it works
The steps, in the order the compiler takes them.
- The frontend produces the representations the analysis runs on: an AST with resolved symbols, and for anything path-sensitive, a control-flow graph over basic blocks.
- The analysis picks a domain of facts — a lattice — and a transfer function saying how each statement changes the fact.
- It initialises every program point to the lattice bottom (or top, for a backward may-analysis) and iterates the transfer functions to a fixed point, merging facts at control-flow joins with the lattice meet.
- Library and framework behaviour that is not in the source is supplied as *models*:
mallocmay return null,assertdoes not return on failure, this ORM method executes SQL. Coverage of the real world is mostly model coverage. - Where the lattice cannot decide, the analysis takes the conservative element —
Unknown,Maybe— which is exactly where over-approximation and therefore false positives enter. - Results are filtered and ranked before display: confidence thresholds, deduplication across paths, suppression of findings in generated or vendored code, and a diff-only mode so a new tool does not report ten thousand pre-existing issues on day one.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- A team turns on a new analyser, gets four thousand findings on the existing codebase, and disables it the same week. Nothing is ever analysed again, including the code written afterwards.
- A check reports a null dereference on a path that a domain invariant makes impossible, an engineer adds a defensive null check that can never fire, and the codebase slowly fills with dead defensive code that future readers cannot distinguish from necessary checks.
- A security scan reports nothing on a service that has an injection flaw, because the flaw crosses a reflective call the analyser does not model, and the clean report is quoted in a review as evidence of safety.
- The analyser silently exceeds its time or complexity budget on the largest function in the repository — reliably the one with the most bugs — and reports nothing about it, with no message that it gave up.
- A findings backlog is imported as tickets, ages, and becomes a permanent yellow dashboard that nobody reads, at which point new findings are indistinguishable from old ones.
- A suppression comment written for one specific line survives a refactor that moved real code under it, and the suppression now hides a genuine defect nobody can see.
When it helps
- Defect classes with a mechanical signature and a high cost: null dereferences, resource leaks on exceptional paths, missing
await, format-string mismatches, comparisons that are always true. - Codebases too large for review to cover uniformly, where the value is not depth but the fact that the check runs on every line every time.
- Enforcing a project-specific invariant that no general tool knows about — "no direct
Date.now()calls in domain code", "every handler must call the audit logger" — written as a custom rule against the AST the compiler already builds. - Onboarding and consistency, where the analyser encodes conventions a new contributor could not know and would otherwise learn through review comments.
When it hurts
- On a legacy codebase, adopted all at once. The only workable path is diff-only enforcement with a frozen baseline, and teams that skip that step usually abandon the tool.
- For properties the language cannot express and the analyser must guess at — business-logic correctness, authorization decisions, whether a value is *the right* user id. The signature is not mechanical, and precision collapses.
- When findings are treated as a compliance count rather than as engineering signal, at which point the incentive is to suppress rather than to fix and the numbers stop meaning anything.
- In build-time-sensitive pipelines: interprocedural and path-sensitive analyses cost minutes to hours, and running them on every push trades developer latency for a signal that is fine to receive nightly.
What it costs
Every one of these is paid by something.
- Soundness buys the ability to say "cannot happen" and pays in false positives, engineer attention, and defensive code written to silence warnings that could never fire.
- Completeness buys trust in every report and pays in silence about real defects, plus the far worse cost that the silence is read as a guarantee.
- Path sensitivity buys precision and pays in analysis time that grows with the number of paths — exponential in the worst case — which is why real tools bound it and stop being sound at the bound.
- Modelling more library behaviour buys coverage and pays in a model corpus that must be maintained against every framework upgrade, and that is wrong silently when it drifts.
- Running the analysis in CI buys enforcement and pays in build latency plus a standing maintenance stream of suppressions, baselines and rule-tuning that somebody has to own.
- Custom rules buy exactly the checks your codebase needs and pay in a rule set written against a specific tool's AST API, which is the least portable code you will ever write.
What else you could do
What a different compiler or language does instead, and when that is better.
- Move the check into the type system, so it is enforced at compile time with no separate tool: non-nullable types,
Resultinstead of exceptions, newtypes for units, ownership for resource lifetimes. Stronger and cheaper to run, and it costs language expressiveness and a migration — see[[nullability]]and[[ownership-types]]. - Dynamic analysis instead: sanitizers, assertions and property tests observe real executions, so every report is real and the coverage is only what you exercised. It is the complete-but-incomplete-coverage counterpart, and the two find genuinely different bugs.
- Runtime enforcement — bounds checks, contracts, invariant assertions — which converts an undecidable static question into a decidable dynamic one, paying in runtime cost and in failing late rather than early.
- Code review and design constraints for the properties that are not mechanical. A rule that "no handler talks to the database directly" is enforceable by an architecture test or a module boundary far more reliably than by a pattern-matching lint.
- Verification for the parts that justify it: model checking or proof over a small critical core gives a guarantee no heuristic analysis can, at a cost that only pays back where the consequence of a defect is extreme.
See it for yourself
The flag, dump or tool that shows you this directly.
- C and C++:
clang --analyze(orscan-build makefor a whole project,scan-viewfor the HTML report),clang-tidy --checks='-*,bugprone-*,clang-analyzer-*' file.cpp --,gcc -fanalyzer(GCC 10+, and-fanalyzer-verbosity=3prints the path it followed),cppcheck --enable=all. - Warnings are the analysis you already have:
-Wall -Wextra -Wshadow -Wconversionfor C/C++, and-Werroronly behind a baseline you have already cleared. - Rust:
cargo clippy -- -W clippy::pedantic; the borrow checker itself is the sound analysis, andcargo buildis how you run it. - Go:
go vet ./...is in the toolchain;staticcheck ./...is the broader third-party set. - Python:
mypy --strict,pyright --outputjson,ruff check,bandit -r .for the security subset. - Java/Kotlin/C#:
infer run -- ./gradlew build(separation-logic-based, interprocedural), SpotBugs, Error Prone as a javac plugin, and Roslyn analyzers as build-integrated rules. - Cross-language, query-based: CodeQL —
codeql database createthencodeql database analyze— where you write the analysis as a query over a relational encoding of the program rather than configuring a fixed checker. - Whatever tool you use, run it once with its verbosity turned up and read the *paths* it prints rather than the summary. The path is where you find out what it assumed.
Plausible wrong readings
Stated the way a confident engineer states them.
- "The static analyser found no issues, so the code is clean." It found no issues of the classes it checks, on the paths it explored, within its budget, with the models it has. Silence and safety are not distinguishable from the outside.
- "False positives mean the tool is broken." For a sound analysis they are a mathematical consequence of over-approximation. The question is the *rate*, and whether the tool tells you which assumption it could not discharge.
- "Static analysis is a security thing." Type checking, unused-variable warnings, exhaustiveness checking and dead-code detection are all static analysis. Security scanning is one application of a framework the compiler already runs.
- "We can just make it sound and precise if we throw more compute at it." Rice's theorem is not an engineering budget. Undecidability does not yield to a bigger machine; it yields only to restricting the language or accepting one of the two errors.
- "A finding in a file I did not touch is not my problem." Baselines exist for exactly this and are the right answer — but a baseline is a debt register, not a deletion.
Misconceptions
The claim, and what is actually true.
Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
Static analysis answers questions about your program without running it — is this null, is this unreachable, does this file get closed. Your type checker is one of these, which is why the machinery feels familiar. The catch is that no tool can be both complete and never wrong: it either warns about things that will never happen (false positives) or stays quiet about things that will (false negatives). Knowing which one a given tool chose is more useful than knowing how it works.
practical
Adopt in this order. Turn the compiler's own warnings up first — they are free and already precise. Add one analyser in diff-only mode against a frozen baseline so the existing codebase does not block the change. Curate the rule set down to checks whose findings your team actually fixes, and delete the rest rather than suppressing them one file at a time. Put the fast checks on every push and the expensive interprocedural run nightly. Then, once a quarter, take one real bug from production and ask which check would have caught it — that is how a rule set stays worth its noise.
advanced
The interesting design question is where the *approximation* is placed, because it is not optional and every tool places it somewhere. Flow-insensitive analyses approximate over statement order and are near-linear. Path-sensitive ones approximate at a path budget and become precise-but-bounded. Interprocedural ones approximate at the call graph and become as precise as their context sensitivity. The design skill is choosing an abstraction whose imprecision falls where your codebase does not care — which is the entire argument of [[abstract-interpretation]], and the reason a domain-specific checker written against your own invariants routinely outperforms a general one that has to be correct for everybody.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
strictNullChecks), and in a separate tool in Java and C. Exhaustiveness is a compiler error in Rust, a lint in Swift, and absent in older TypeScript targets. A claim about "what the compiler catches" is a claim about one language at one version.If you were asked this in an interview
- Explain sound versus complete for a static analysis, and say which one a false positive comes from.
- A security scan comes back clean on a service you know has a bug. Give me three reasons that can happen that are not "the tool is bad".
- Your team has four thousand findings on a legacy codebase. What do you do on Monday?
Connections
- Testing & Reliability Engineering — Where a static check belongs in the pipeline relative to unit tests, sanitizers and property testsStatic and dynamic analysis find genuinely different bug classes — one covers every path shallowly, the other one path deeply — and deciding which gate blocks a merge is a testing-strategy decision with a latency budget attached. That decision is owned there; what each analysis can and cannot prove is ours.
- DevOps / Production Engineering — Baselines, diff-only enforcement and findings triage as a CI workflowThe reason most static-analysis adoptions fail is operational rather than technical: no baseline, no diff mode, no owner for the rule set. Running it as a pipeline stage with a debt register is a delivery-engineering practice owned there, and it is the difference between a tool that is used and one that was installed.