Written in collaboration with an LLM. The ideas come from practice; the AI helped with prose, code examples, and diagrams.

Many problems in static analysis, on closer look, are tracking the same thing: where does a value come from, what happens to it along the way, and where does it end up? Problems of this kind have a common name: data flow analysis.

For example: "Does unsanitized user input reach a SQL query?" is a data flow question. So is "Can a reference be dereferenced before it's been assigned?" The first concerns security, the second robustness, but the tool underneath does much the same thing in both cases: reason about possible execution paths and track how a value's state changes.

In static security analysis, one of the most common forms of data flow analysis is taint analysis. The idea is direct: attach a label to each value in the program, then watch how those labels flow, merge, and pass forward as the analysis follows the program. States like tainted, safe, html-escaped, or sql-safe can all be expressed as labels.

The model looks simple. Building a real static-analysis tool on top of it is not.

Labels go well beyond tainted versus safe. A working engine uses them to encode where data came from, what transformations it has been through, and which validations it has passed — in effect, formalizing security-domain knowledge into something the analyzer can reason about.

Binary Labels: The Simplest Taint Model

Start with the canonical web-application scenario: take user input from an HTTP request, splice it into a SQL query, and execute the result against the database — with no sanitization or parameter binding in between. That is the textbook shape of SQL injection. In data-flow terms, the question is simple: where does an untrusted value enter the program, what happens to it along the way, and which dangerous API does it eventually reach?

How do you trace such a path? The key idea is that we do not need the concrete value of a variable. We only need to know whether it originated in untrusted external input. Attach that property to the value, let it propagate through assignments, parameter passing, and return values, and you can follow the whole path without ever running the program.

In practice, the label is attached at the point where external data enters the program. If a value comes from untrusted input, mark it tainted. The label then travels with the data flow: if a tainted value reaches a dangerous API without being sanitized, report a vulnerability; if not, then in this simple model no report is produced. That is the binary label model.

The point where external input enters is called a Source. The dangerous API where the flow ends is called a Sink. Here is the code:

String name = request.getParameter("name");   // Source: name → tainted
String query = "SELECT * FROM users WHERE name = '" + name + "'";  // query → tainted
Statement stmt = conn.createStatement();
stmt.execute(query);                          // Sink: tainted data reaches sink → report SQL injection

request.getParameter() reads user input from the HTTP request. Because that input is fully under external control, its return value is marked tainted. stmt.execute() sends the SQL statement to the database directly. If untrusted input has been mixed into that statement, there is an injection risk, so the call acts as a Sink. The tainted label follows the data flow into the Sink, and the engine reports SQL injection.

So where do these labels actually live? Not on the runtime values themselves. The analysis engine maintains its own abstract state in memory, recording not the value itself but its security property. At this level, you can think of it as keeping one label per tracked variable — a mapping that runs alongside the program's variables.

The propagation rules are equally simple. When data flows from A to B — through an assignment, an argument, or a return value — B inherits A's label. When several values combine, the result combines their labels with logical-OR semantics: if any input is tainted, the output is tainted as well. In the example above, name is tainted; the concatenation of a safe constant with name therefore makes query tainted too; and when query flows into stmt.execute(), the tainted label reaches the Sink. The whole process is just labels propagating one step at a time along the data flow.

Of course, not every flow from a Source is a vulnerability. If the data is handled appropriately before it reaches the Sink — for example, through parameterized binding in SQL, HTML escaping for XSS, or strict allowlist validation — the path may be safe. Operations that remove or neutralize the tainted label are called Sanitizers. Source, Sink, and Sanitizer are the three basic roles in taint analysis.

To see this in a concrete scenario, switch from the SQL example to XSS in an HTML body: escapeHtml plays the role of a Sanitizer. The full Source–Sanitizer–Sink data flow looks like this:

Top: no sanitizer, TAINTED travels all the way to the Sink and a vulnerability is reported. Bottom: escapeHtml flips the label to SAFE, and the Sink lets it through.

The idea has a long lineage. In 1976, Denning¹ proposed a lattice-based framework for reasoning about secure information flow. As early as 1989, Perl supported tainting in the language, tracking external input and preventing its direct use in dangerous operations. Implementations in other languages and platforms followed, and most modern security-focused static analysis engines treat taint analysis as a core capability. Modern engines, however, moved past the binary form long ago.

Binary labels have one clear limitation: they collapse every vulnerability category onto a single dimension. A value is either tainted or it is not — there is no way to tell which kind of vulnerability it is dangerous for.

Take a common example from legacy projects: a handwritten escapeHtml(input) that replaces only <, >, and & with HTML entities, while leaving quotes untouched. That turns out to be a problem.

For XSS in an HTML body, the output is safe: <script> has become <script>. But the single quote ' is untouched. Concatenated into "WHERE name = '" + escaped + "'", the quote can still break out of the SQL string literal and enable SQL injection. Placed inside an attribute like <img src='...' onerror='...'>, it can close the quote and enable XSS in an attribute context.

Binary labels cannot express the middle ground of "safe for HTML body text, but unsafe for SQL and HTML attributes." This escapeHtml is either marked as a Sanitizer as a whole — in which case both SQL injection and attribute-context XSS go unreported — or it is not marked, in which case HTML-body XSS becomes a false positive.

Security is inherently multi-dimensional: different vulnerability classes have different dangerous paths and different sanitization requirements. A single bit cannot encode those dimensions, and that is where the binary model's expressiveness ends.

Label Propagation: From the CFG to a Fixed Point

Before introducing multi-label models, we need to look at the infrastructure that moves labels through a program. Binary models use it, and multi-label models will use it too.

The analysis engine does not actually run the program. Instead, it maintains an abstract state in its own memory: a model of the runtime stack and the local-variable table, with each slot holding a label rather than a real value. This abstract state is called a Frame. At each program point, the Frame records the label state of the local variables and operand-stack slots.

The key design choice is that the label takes the place of the value entirely. The engine does not need to know whether name holds "rm -rf /" or "hello world". It only needs to know which label is attached to that value. The program's runtime semantics have been compressed into label semantics.

What does this look like in an industrial implementation? Take SpotBugs: its edu.umd.cs.findbugs.ba.Frame<T> is generic. The type parameter T can be replaced with different abstract value types to perform different analyses.

As a concrete example, feed the earlier SQL injection code into a SpotBugs-style analysis. When the engine reaches the bytecode for:

String name = request.getParameter("name");

the INVOKEVIRTUAL getParameter() instruction produces a return value on the operand stack. The following ASTORE_n instruction then stores that value into the local-variable slot for name. Slot 0 is usually this in an instance method; the exact slot number for name depends on the method's parameters and earlier locals.

After the return value of getParameter() is stored into the local slot for name, the same Frame structure can carry different meanings depending on what T is:

null analysis  : T = IsNullValue  →  MAYBE_NULL
type analysis  : T = Type         →  java.lang.String
taint analysis : T = Taint        →  TAINTED      (via plugins such as Find Security Bugs)

After the same bytecode sequence executes, the slot for name goes from ⊥ to [T]. Plugging in T as IsNullValue, Type, or Taint yields three different analyses. The Frame structure is invariant; the label semantics are pluggable.

The Frame structure, the CFG decomposition, and the merge rules at join points all stay the same. What changes is the specific form of T in each slot. The Frame is general infrastructure; the label is pluggable semantics. The same propagation mechanism drives many kinds of data-flow analysis.

The next section will upgrade taint analysis's T from a single bit to a richer set of labels, but it will still run on this same Frame infrastructure. The engine will propagate Frames along the CFG and keep merging them at join points until the abstract state stops changing — that is, until the analysis reaches a fixed point.

A Frame answers the question "where do labels live?", but the labels still need a path to move along. Program flow is not linear: branches and loops split and reconnect the execution path, so propagation cannot be a linear scan either. The engine first slices a method into a CFG — a control-flow graph. A basic block is a straight-line run of instructions with no internal branches, and blocks are connected by directed edges that represent possible flow of control.

Within a block, propagation is mostly mechanical. Each bytecode instruction updates the Frame according to its stack semantics: ALOAD copies a local variable's label onto the operand stack, ASTORE does the reverse, and a method call consumes the receiver and argument labels and produces a return-value label according to the call's transfer model. For the model here, the essential control-flow complexity sits at the block boundaries, in two specific places: branch merge, where several incoming edges flow into the same block, and loop back edge, where an edge points back to an earlier block.

Consider branch merge first. The Frames arriving along different predecessor edges must be merged at the join point. The engine cannot know at analysis time which branch will be taken at runtime, so it conservatively combines every possibility: if name carries TAINTED on any incoming path, TAINTED survives in the merged Frame. In the binary model, the merge is logical OR.

This is the conservative rule behind taint analysis: when different paths disagree, keep the dangerous possibility. The cost is potential false positives — at runtime the program might take the clean branch and never see tainted data at the sink. The benefit is that a tainted possibility represented in the model is not lost at the merge.

Now consider the loop back edge. A back edge feeds the merged state of a successor block back into the input of an earlier block. Take a while loop whose body assigns a tainted value to some variable. On the first pass, the merge at the loop header has not yet seen the tainted state produced inside the body. On the second pass, the back edge carries that state back to the header, and the merge has to be redone. The engine iterates until no Frame in the method changes anymore — that is, until the analysis reaches a fixed point.

Convergence is guaranteed in this binary model. The label set is finite — just TAINTED and SAFE — and once a label is added by OR-merge, no later round removes it. The state at every slot can therefore change only a bounded number of times, so the iteration must stabilize after a finite number of rounds.

Left: a loop CFG. Header is the merge point, and the back edge sends Body's state back to Header to be merged. Right: three rounds of iteration converge to a fixed point — round 2 picks up TAINTED from the back edge at Header, and round 3 produces the same state as round 2, signaling stability.

Multi-Label Models: Formalizing Security Knowledge

Recall the escapeHtml example from the binary-labels section. The binary model tracks only one question: "is this value dangerous at all?" Real security analysis, however, needs to track a whole family of questions at once. Has this value been HTML-escaped? SQL-escaped? Attribute-escaped? These properties are independent of each other, and one bit cannot capture them all.

This motivates a natural extension of the model: replace the single bit on each value with a label set. The original tainted / safe dichotomy breaks into a family of independent labels — XSS_TAINTED, SQL_TAINTED, PATH_TAINTED, and so on — that do not overlap. A given value may carry several labels at once: a string returned by request.getParameter() is dangerous in all of these dimensions. Or it may carry only one. The abstract state the engine maintains has not changed structurally. It is still a mapping that runs alongside the program's variables, but each slot now holds a set of labels rather than a single bit.

Once the label is a set, two natural categories emerge: labels that mark risk, and labels that mark safety. A risk label says "this value carries some specific kind of danger" — XSS_TAINTED, SQL_TAINTED, and so on — marking the value's origin as untrusted for that class of vulnerability. Risk labels are added by Sources. A safety label says "this value has been processed against some specific kind of danger" — XSS_HTML_ESCAPED, SQL_PARAM_BOUND, and so on — marking a safety guarantee the value has earned. Safety labels are added by Sanitizers. Both kinds can coexist in the same set.

In practice, a Sanitizer can be modeled in one of two ways. It can add a safety label to the set, such as XSS_HTML_ESCAPED, or it can remove the corresponding risk label, such as XSS_TAINTED. The first style preserves more processing history for later checks and audits; the second keeps the label set compact. Fortify-style rule systems expose related ideas through taint flags, cleanse rules, and partial-cleanse rules, though the exact internal representation is engine-specific.

With richer labels, the responsibility for deciding what counts as a vulnerability moves to the Sink. Each Sink declares its own trigger contract, of the form has(XSS_TAINTED) AND NOT has(XSS_HTML_ESCAPED): "I see the matching risk label, and I do not see the matching safety label." What counts as a vulnerability is no longer an implicit is_tainted query inside the engine. It becomes an explicit contract that each Sink can state precisely.

The same code traced through three stages under binary and multi-label representations. Binary flips the whole label to SAFE after the Sanitizer, losing the SQL and attribute-context dimensions, so the SQL Sink misses the injection. Multi-label appends XSS_HTML_ESCAPED to the existing set while keeping every risk label, so each Sink contract can make its own decision.

In a binary model, a Sanitizer can only be modeled as flipping tainted to safe wholesale. In the multi-label model, each Sanitizer's model becomes correspondingly more precise: it declares exactly which safety labels it adds. The escapeHtml(input) Sanitizer adds XSS_HTML_ESCAPED, leaves SQL_TAINTED alone, and does not add XSS_ATTR_ESCAPED. Returning to the dilemma from the binary-labels section, the same escaped value now produces three independent judgments at three different Sinks:

String input = request.getParameter("name");          // {XSS_TAINTED, SQL_TAINTED, ...}
String escaped = escapeHtml(input);                   // adds {XSS_HTML_ESCAPED} to the existing set

response.write("<div>" + escaped + "</div>");         // contract: has(XSS_TAINTED) AND NOT has(XSS_HTML_ESCAPED)
                                                      // result: not reported

stmt.execute("WHERE name='" + escaped + "'");         // contract: has(SQL_TAINTED) AND NOT has(SQL_PARAM_BOUND)
                                                      // result: SQL injection reported

response.write("<img src='" + escaped + "'>");        // contract: has(XSS_TAINTED) AND NOT has(XSS_ATTR_ESCAPED)
                                                      // result: attribute-context XSS reported

XSS_HTML_ESCAPED satisfies only the HTML-body XSS contract; it has no effect on the SQL contract or the attribute-context XSS contract. Three Sinks yield three independent verdicts: the SQL false negative and the body-XSS false positive are eliminated at the same time.

The multi-label model's added complexity reaches into propagation as well. The branch-merge rule from the previous section — take the union — is no longer enough. Consider an if/else where one branch calls escapeHtml and the other does not. If we naively unioned both kinds of label at the join point, XSS_HTML_ESCAPED would survive into the merged set, the Sink contract would not fire, and a real body-XSS path — reachable when the else branch executes — would go unreported. The correct merge rule, previewed in the comment at the join point, treats the two categories asymmetrically:

String input = request.getParameter("name");      // {XSS_TAINTED, SQL_TAINTED, ...}
String x;
if (someCondition()) {
    x = escapeHtml(input);                        // {XSS_TAINTED, SQL_TAINTED, XSS_HTML_ESCAPED}
} else {
    x = input;                                    // {XSS_TAINTED, SQL_TAINTED}
}
// join point: x → {XSS_TAINTED, SQL_TAINTED}    (risk labels: union; safety labels: intersection)
response.write("<div>" + x + "</div>");           // contract triggers → body-XSS reported

The comment at the join point captures the rule that fixes this: risk labels and safety labels merge in opposite directions. Risk labels are unioned — if any incoming path carries XSS_TAINTED, the merge keeps it. Safety labels are intersected — a label like XSS_HTML_ESCAPED is kept only if every incoming path carries it. The merge biases toward preserving any vulnerability possibility represented in the model: risk labels lean toward more, safety labels toward less. This is the same conservative principle from the previous section, refined for a multi-label setting.

Another way to read the asymmetry: a risk label answers "could this value be dangerous on some path?" This is a may-analysis, which naturally uses union. A safety label answers "has this value been proven safe on every path?" This is a must-analysis, which naturally uses intersection.

When the Frames from an if/else are merged, risk labels and safety labels move in opposite directions: risk labels are unioned (XSS_TAINTED is present on both paths, so it survives), and safety labels are intersected (XSS_HTML_ESCAPED is only on the if branch, so it is dropped). The Sink receives a set with XSS_TAINTED but without XSS_HTML_ESCAPED, and the contract fires.

The multi-label model can sustain all of this because the labels have moved from one dimension to many, and the security domain is itself multi-dimensional. Vulnerability classes, the operations that mitigate them, and the contexts in which they apply are independent of each other. Under the binary model, every dimension collapses into a single bit, leaving false positives and false negatives as a forced trade-off. The multi-label model gives each dimension its own label, its own sanitizer effects, and its own sink contract.

Closing

Taint analysis has a structural blind spot: most production implementations focus on explicit data flow. Consider an example:

boolean secret = ...;     // sensitive source
int y = 0;
if (secret) y = 1;        // no direct assignment from secret to y
log(y);                   // sink: prints 0 or 1, leaking one bit of secret

The value of y depends on secret, but not through an assignment. It depends through the branch condition. This is control dependence. A taint analysis that tracks only explicit data flow will not mark y as tainted.

In principle, folding control dependence into propagation would cover this kind of implicit information flow. The idea goes back at least to Denning's 1976 lattice model for secure information flow.¹ In practice, full implicit-flow tracking is usually avoided in production taint analysis because it is too easy to lose precision.

The difficulty is the reach of control dependence. In real code, many values can be connected to some if or while condition that depends on external input. For example, if config.flag influences which assignment runs, then the assigned result may become tainted along with the flag, even when the flag is a benign configuration value. If applied too broadly, this channel makes taint spread like ink in water: large parts of the program become tainted, and real vulnerabilities get buried in a flood of false positives.

Language-based information-flow systems take a different route. Systems such as Jif and Paragon let programmers state security labels, policies, and permitted flows explicitly, so the checker has more information about which dependencies are allowed. That extra precision comes at a cost: the programmer must work within a heavier annotation and policy model. In practice, that adoption bar has kept these systems from becoming the common path for production SAST.

Looking back, taint analysis is one instance of a more general mechanism. Change the label dimension and you get a different analysis: {NULL, MAYBE_NULL, NON_NULL} becomes null-pointer analysis; {ENCRYPTED, PLAINTEXT} tracks encryption state; {RESOURCE_OPENED, RESOURCE_CLOSED} detects resource leaks. The underlying machinery — Frames, the CFG, merges at join points, fixed-point iteration — stays put. Only the label dimension changes.

This is program semantic modeling: choose the property you care about, encode it as labels, and let the data-flow engine compute how those labels move.