Most security bugs are really questions about where a value came from and where it ends up. Data flow analysis is the technique that answers those questions by hand off to a machine: it tracks how values move through a program and what facts hold true at each point in the code. This post teaches the general idea, walks a small example, and shows how one famous security check, taint tracking, is just data flow analysis with a specific fact.
What data flow analysis actually tracks
A program is a set of statements connected by control flow. Between any two statements there is a program point, a spot where you can pause and ask a question. Data flow analysis attaches a set of facts to every program point and works out which are true there. A fact is small and precise. Examples: “x holds a value assigned on line 3″, “count is definitely not zero here”, or “this string came from the network and nobody cleaned it”.
The machinery does not run your code. It reads the structure, the control flow graph, and reasons about every path at once. That is why it can catch a branch your test suite never exercised. The method rests on two directions and two flavors of certainty.
Forward and backward: which way the facts travel
Some facts flow with the program, from the start toward the end. Some flow against it, from the end back toward the start. The direction you pick depends on the question.
Reaching definitions (a forward analysis)
A reaching definition asks: at this point, which assignments could have produced the current value of a variable? Facts start at the top of a function and travel down. Consider this:
1 x = read_input()
2 if flag:
3 x = 0
4 use(x)At line 4, two definitions of x reach the point: the one from line 1 and the one from line 3. If flag is false, the line 1 value survives. If it is true, line 3 overwrites it. Both reach line 4 because we do not know flag ahead of time. Reaching definitions run forward because a definition made earlier flows down into the code that uses it.
Live variables (a backward analysis)
A variable is live at a point if its current value gets read later before it is overwritten. The facts travel backward, from where variables get used toward where they get set.
1 a = compute()
2 b = compute()
3 return bAt line 1, is a live? Walk forward: line 3 returns b, and a is never read. So a is not live after line 1, and the assignment on line 1 is dead code you can delete. To learn that, the analysis starts at the return and pushes the fact “b is needed” backward up the function. Same graph, opposite direction.
May versus must: two kinds of true
Facts come with a strength. A may fact holds on at least one path into a point. A must fact holds on every path. That distinction decides what a tool is allowed to claim.
- May analysis is for finding danger. “This value may be untrusted” means at least one path delivers dirty input, and one bad path is enough to be a bug. When paths meet, you take the union of their facts, so nothing dangerous gets dropped.
- Must analysis is for proving safety. “This pointer must be non null here” has to survive every incoming path, or you cannot rely on it. When paths meet, you take the intersection, keeping only what every path agrees on.
Security work leans on may analysis, because a vulnerability that shows up on one path in a thousand is still a vulnerability.
The worklist: repeat until nothing changes
How does a tool compute these facts across loops and branches? With a plain loop of its own, called the worklist algorithm. The idea is stubborn and simple.
- Start every program point with an empty or default set of facts.
- Put every node on a worklist.
- Take a node off the list. Compute its facts from its neighbors, using the direction and the meet rule (union for may, intersection for must).
- If that node’s facts changed, put its affected neighbors back on the list so they get recomputed.
- Stop when the list is empty. Nothing changed, so you are done.
That stopping state is called a fixed point: a set of facts so stable that running the rules again produces the same answer. Loops are the reason you need to iterate. The first pass through a loop body may add a fact that, on the second pass, changes what the loop entry sees, which changes the body again. The worklist keeps chasing those ripples until they settle.
Data flow analysis is patient bookkeeping over the control flow graph: push facts along the edges, take the union or the intersection where paths meet, and repeat until the numbers stop moving.
Walking one fact through a small function
Let us track the reaching definition of total through a tiny function in an invented billing service called Acme Invoices.
1 def price(items, discount):
2 total = 0
3 for item in items:
4 total = total + item.cost
5 if discount:
6 total = total - 5
7 return totalStart the worklist. After line 2, the only definition of total is D2 (the assignment on line 2). Enter the loop. Line 4 defines total again, call it D4. Now here is the loop subtlety: at the top of the loop body, total could be D2 (first time in) or D4 (came back around). So the reaching set at line 4 becomes {D2, D4}. The first pass only knew {D2}, so the fact changed, so the worklist reruns the body. Second pass: same set {D2, D4}. No change. Fixed point reached inside the loop.
At line 5, after the loop, total reaches as {D2, D4}: either the loop ran and D4 holds, or the list was empty and D2 survives. Line 6 adds D6 on the branch where discount is set. So at the return on line 7, the reaching definitions of total are {D4, D2, D6}, a may set, because different paths deliver different last writes. That short walk is the whole technique in miniature.
The security payoff: taint is data flow analysis
Now the connection. Pick one fact and make it the thing you track: “this value is untrusted”. Untrusted values enter at sources, like a request parameter or an uploaded file. Certain functions are dangerous sinks, like a database query or an HTML response. Run a forward, may style data flow analysis carrying the taint fact, and you learn every point where dirty data could arrive. If tainted data reaches a sink with no cleaning in between, you have a candidate injection bug.
That applied pattern, source to sink, is its own subject with its own subtleties, so we treat it separately in source to sink data flow analysis. The one thing to hold onto here: taint tracking invents no new machinery. It is the worklist, the control flow graph, the may union, and the fixed point you just saw, with “untrusted” as the fact.
These facts also need a place to live. A code property graph stores the control flow, the data flow, and the syntax in one queryable structure, which is what makes running these analyses at scale practical. For the broader argument about why understanding a program beats matching fixed patterns, see scanners versus research.
At UnboundCompute we build on this kind of analysis to understand how an application is meant to work, then test where those assumptions break, which is a natural fit for a technique whose whole job is to follow where a value can go. You can read more about that on our about page.
Frequently asked questions
What is data flow analysis?
Data flow analysis is a technique that tracks how values move through a program and what facts are true at each program point. It reads the control flow graph without running the code, attaches a set of facts to every point, and computes which facts hold there. Reaching definitions and live variables are classic examples, and taint tracking is the security application of the same idea.
What is the difference between forward and backward data flow analysis?
Forward analysis pushes facts along the program, from the start toward the end, which suits questions like reaching definitions, where an assignment flows down into the code that uses it. Backward analysis pushes facts against the program, from later uses toward earlier statements, which suits questions like live variables, where you look ahead to see if a value gets read before it is overwritten.
What is the difference between may and must analysis?
A may fact holds on at least one path into a program point, so it is used to find danger, since one bad path is enough to be a bug and paths meet with a union. A must fact holds on every path, so it is used to prove safety, and paths meet with an intersection that keeps only what all paths agree on. Security work leans on may analysis.
How is taint tracking related to data flow analysis?
Taint tracking is data flow analysis where the tracked fact is that a value is untrusted. Untrusted data enters at sources like a request parameter, and dangerous functions like a database query are sinks. A forward may style analysis carries the taint fact through the control flow graph, and if tainted data reaches a sink with no cleaning in between, you have a candidate injection bug.
Put an autonomous researcher on your own systems
UnboundCompute is an autonomous security researcher that reasons about how an application fits together and proves the access control and injection bugs it finds. We are opening a small number of founding design partner seats: private early access pointed at a staging target you choose, and a say in what it looks for. If your team ships software worth pressure testing, apply to the design partner program.