Skip to the content ForoHackers
Log inJoin

Static analysis: start here

Static analysis
#3045 · · Quote · Report

Static analysis examines a program without running it, to find bugs, enforce rules or prove properties. Type checkers, linters and compiler warnings are all static analysers. The core trade-off never goes away: a perfect analysis of a nontrivial property is impossible, so tools either miss some bugs or report some that are not real.

Key concepts

  • Control-flow graph: the program as blocks of code joined by the jumps between them.
  • Data-flow analysis: facts, such as which variables may be null, propagated along the graph until nothing changes.
  • Abstract interpretation: run the program on approximate values to get a sound over-approximation.
  • Soundness and completeness: a sound tool misses no real bug; a complete one reports no false alarm; you cannot have both.
  • Pattern and style checking: linters match known bad shapes of code cheaply.
  • Type systems: a lightweight, built-in static analysis.

Vocabulary

  • False positive: a warning about code that is actually fine.
  • False negative: a real bug the tool did not report.
  • Taint analysis: tracking where untrusted data can flow.
  • Lattice: the ordered set of abstract facts that an analysis climbs.

What to study, in order

  1. Turn on every warning of your compiler and linter, and read each one to decide if it is real.
  2. Build a control-flow graph for a small function by hand.
  3. Implement a simple data-flow analysis, such as unused variables, over a toy language.
  4. Learn the idea of abstract interpretation with an interval domain.
  5. Run an open source analyser on a project of yours and triage the results.

Related tags

#compilers #formal-methods #type-theory #secure-coding

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply