DEV Community

Cheikh Seck
Cheikh Seck

Posted on

Static Single Assignment in Go: From Compiler IR to Taint Analysis

#ai #programming #go

Subtitle: A 1988 compiler optimization turns out to be the cleanest way to trace untrusted data through Go.

When you write this:

x := 1
x = x + 1
x = x * 2
Enter fullscreen mode Exit fullscreen mode

you have written one name, x, that holds three different values at three different moments. That is convenient for humans and miserable for machines. Any tool that wants to reason about x must first answer a question your code never asked: which x do you mean, at this line?

Static Single Assignment (SSA) form is the answer. In SSA, every variable is assigned exactly once. The same program becomes:

x1 := 1
x2 := x1 + 1
x3 := x2 * 2
Enter fullscreen mode Exit fullscreen mode

Three names, three values, no ambiguity. Each definition has exactly one use-site chain, and each use has exactly one definition. The data-flow graph of the program becomes explicit instead of implied.

This is not a new idea. SSA was developed at IBM in the 1980s; Rosen, Wegman, and Zadeck named it and introduced Φ-functions in their 1988 paper "Global Value Numbers and Redundant Computations." It made numerous compiler optimizations easier — constant folding, dead-code elimination, global value numbering — because when you look at a use of a variable, there is only one place where that variable may have received a value. SSA became the default internal representation for LLVM, GCC, and most production compilers.

Go adopted it too. The Go 1.7 release notes describe a new compiler back end based on SSA that "generates more compact, more efficient code" with optimizations like bounds check elimination and common subexpression elimination. The Go compiler's own SSA package documents the core idea plainly: "a value is defined exactly once, but it may be used any number of times."

The part that matters for this article is the side effect. A representation that makes data flow explicit for an optimizer also makes data flow explicit for an auditor. If you want to know whether a value that came from an HTTP request can reach a SQL query, SSA has already done the hard part: it has told you, unambiguously, which value is which.

Go exposes this representation directly. The golang.org/x/tools/go/ssa package builds an SSA IR for arbitrary Go packages, and its documentation states that "the level of abstraction of the SSA form is intentionally close to the source language to facilitate construction of source analysis tools." It is the same machinery that powers go vet, staticcheck, gopls, and gosec. You do not need to be writing a compiler to use it. You need to be writing a question about data flow.

This article is about one such question, and about a small tool that answers it.

The Guard That Only Looks Like a Guard

Here is the shape of a whole class of security bugs, in four lines:

name := r.FormValue("name")   // attacker-controlled
q := "SELECT * FROM users WHERE name = '" + name + "'"
db.Query(q)                   // injection
Enter fullscreen mode Exit fullscreen mode

The data enters at a source (FormValue), travels through the program, and exits at a sink (db.Query). If nothing in between removes the danger, you have a vulnerability. This is taint analysis: mark the untrusted values, propagate the mark, and complain if a marked value reaches a dangerous place.

The naive version of this is a grep. The naive version is also wrong, in both directions:

  • It misses flows that pass through helper functions, string concatenation, or a struct field.
  • It invents flows that a guard already neutralized, because a regex cannot tell whether SanitizeHTML(name) actually sanitizes anything.

That second failure is the interesting one. Consider:

func ValidateAndEscape(s string) string {
    if len(s) > 100 {
        return ""
    }
    return s // ← returns the input unchanged
}
Enter fullscreen mode Exit fullscreen mode

The name promises validation and escaping. The body does neither. A human reviewer skimming a call site sees ValidateAndEscape(name) and moves on. A regex-based scanner sees a function call and either flags it (noisy) or trusts it (dangerous). Neither one reads the body.

A tool that reads the body can tell the difference. And SSA is what makes reading the body tractable.

Picatz's write-up on static taint analysis for Go makes the same point from the other direction: SSA provides "the foundation for performing taint analysis," transforming the program into a value graph where each node is a value or instruction, then into a call graph where edges are calls — the structure you need to identify data flow from source to sink.

Five Steps From Source to Sink

The project is a single Go module called leakcheck. It does five things:

  1. Loads a set of Go packages and builds SSA for each.
  2. Classifies every project function that looks like a guard into one of eight classes.
  3. Walks the SSA instructions, propagating taint from sources to sinks.
  4. Probes every sink rule's argument index against the callee's real declared signature.
  5. Runs the whole thing twice — once trusting guards, once treating every guard as a no-op — and reports the difference.

That last step is the point of the whole exercise. The delta between the two passes is the set of flows that are silent only because someone wrote a reassuring function name.

Loading and building SSA

The entry point is the standard packages + ssa pairing:

cfg := &packages.Config{Mode: packages.LoadAllSyntax, Dir: dir}
pkgs, err := packages.Load(cfg, patterns...)

prog := ssa.NewProgram(fset, ssa.SanityCheckFunctions)
for _, p := range pkgs {
    ssapkg := prog.CreatePackage(p.Types, p.Syntax, p.TypesInfo, false)
    ssapkg.Build()
}
Enter fullscreen mode Exit fullscreen mode

ssa.NewProgram gives you a container; CreatePackage turns a type-checked package into SSA; Build() does the actual translation. After that, every function body is a list of basic blocks, and every basic block is a list of instructions.

The instruction walk

The core of the analysis is a switch over instruction types. This is where SSA earns its keep — the cases are few and each one is unambiguous:

switch v := instr.(type) {
case *ssa.Call:
    return a.stepCall(f, v, v.Common(), state)
case *ssa.Defer:
    return a.stepCall(f, v, v.Common(), state)
case *ssa.Go:
    return a.stepCall(f, v, v.Common(), state)
case *ssa.BinOp:
    // taint flows from either operand to the result
case *ssa.Store:
    // taint flows from the value into the address
case *ssa.FieldAddr:
    // taint flows from the struct into the field
}
Enter fullscreen mode Exit fullscreen mode

Three things are worth noticing.

First, Call, Defer, and Go share a shape. All three carry a *ssa.CallCommon, which holds the callee, the arguments, and the receiver. A deferred call and a goroutine-launched call are the same data-flow event as a direct call, just scheduled differently. One helper handles all three.

Second, BinOp is where string concatenation lives. "SELECT ... " + name is a BinOp with a + token. Taint flows from either operand to the result. This is the single most common propagation step in real injection bugs, and in SSA it is one case in a switch.

Third, Store and FieldAddr are why SSA beats the AST here. If taint enters a struct field and is read back three functions later, the AST gives you a syntax tree with no edges between the write and the read. SSA gives you a value graph where the field address is a node and the store is an edge into it.

The guard classifier

This is the part that does something a regex cannot. Every project function is inspected and sorted into one of eight classes:

Class Cuts taint? Meaning
effective yes Delegates to a recognized sanitizer and does nothing else
constant yes Takes no input, so it cannot forward taint
non-forwarding yes Returns only error/bool; the input never comes back out
passthrough no Returns its argument unchanged
rewrites no Transforms the input without calling a recognized sanitizer
conditional no Branches on the input; the analyzer cannot correlate branch with sink
unknown no No rule matched

The classification is decided by the SSA body, not the name. SanitizeHTML is effective because it calls a known escaper and does nothing else. ValidateAndEscape is conditional because it branches. CleanInput is passthrough because it returns its argument. IsSafePath is non-forwarding because it returns a bool and the string never leaves.

Only three of the eight classes cut taint. That ratio is the finding.

The argument-layout probe

Every sink rule names an argument index. os.Open is index 0. db.Query is index 1 (the query string, after the receiver). Header.Set is index 2.

Those indices are guesses about someone else's function signature. And there is a genuine trap here, because Go's SSA representation is asymmetric about receivers:

  • A static method call puts the receiver in Args[0], so Header.Set(key, value) has the value at index 2.
  • An invoke-mode call (through an interface) puts the receiver in CallCommon.Value and excludes it from Args, so the indices shift by one.

A tool that assumes one convention will silently mis-index half its rules. So leakcheck measures instead of assuming: for every sink rule, it looks up the callee's declared signature and checks that the named index exists and has a plausible type.

if idx >= len(sig.Params()) {
    // rule is out of range for this callee — report it
}
Enter fullscreen mode Exit fullscreen mode

The probe prints a table and exits non-zero if anything is suspicious. It is the difference between a confidently wrong report and a report you can check.

The two-pass delta

The whole analysis runs twice. Pass 2 is byte-identical except for one flag:

guardsNoop = true
Enter fullscreen mode Exit fullscreen mode

With that flag set, every project guard is treated as a no-op — taint flows straight through it. The difference between the two passes is the set of flows that a guard is currently suppressing.

If that number is zero, your guards are decorative. If it is large, your guards are load-bearing and you should look at exactly which ones.

Nine Seconds, Ten Findings

Here is the actual output, formatted as if from a Linux machine:

cheikh@dev:~/ssa-taint$ go run .
==============================================================================
  LEAKCHECK — SSA taint analysis for Go
==============================================================================

TIMING
  load + SSA build           8.6312159s
  guard classification       534.2515ms
  summary fixpoint           4.9699ms
  pass 1 (guards trusted)    0s
  pass 2 (guards no-op)      0s
  layout probe               0s
  total                      9.1704373s

PROGRAM
  packages analysed          2
  functions                  80
  SSA instructions           3011
  guards classified          14
  callees indexed            17035
  summaries that taint       19

FINDINGS (pass 1 — guards trusted) — 10
  #   SEVERITY KIND                FUNCTION                       ARG   ORIGIN
  1   HIGH     sql-injection       corpus.H01Query                1     request.form
  2   HIGH     sql-injection       corpus.H02EnvQuery             1     environment
  3   HIGH     path-traversal      corpus.H05Open                 0     request.form
  4   HIGH     ssrf                corpus.H06Fetch                0     request.form
  5   HIGH     path-traversal      corpus.H10TwoHop               0     request.form
  6   HIGH     path-traversal      corpus.H11OneHop               0     request.form
  7   HIGH     sql-injection       corpus.H13FilteredSQL          1     request.form
  8   HIGH     path-traversal      corpus.H14CleanGuard           0     request.form
  9   HIGH     path-traversal      corpus.H16PathHandler          0     request.form
  10  MEDIUM   output-sink         corpus.H09Header               2     request.form

TAINT PATHS
  [1] corpus.H01Query  (handlers.go:24)
      origin : request.form
      sink   : database/sql.DB.Query  arg 1  (sql-injection)
      path   : http.Request.FormValue
  [2] corpus.H02EnvQuery  (handlers.go:30)
      origin : environment
      sink   : database/sql.DB.Query  arg 1  (sql-injection)
      path   : os.Getenv
  [3] corpus.H05Open  (handlers.go:48)
      origin : request.form
      sink   : os.Open  arg 0  (path-traversal)
      path   : http.Request.FormValue
  [4] corpus.H06Fetch  (handlers.go:54)
      origin : request.form
      sink   : net/http.Get  arg 0  (ssrf)
      path   : http.Request.FormValue
  [5] corpus.H10TwoHop  (handlers.go:78)
      origin : request.form
      sink   : os.Open  arg 0  (path-traversal)
      path   : http.Request.FormValue
  [6] corpus.H11OneHop  (handlers.go:84)
      origin : request.form
      sink   : os.Open  arg 0  (path-traversal)
      path   : http.Request.FormValue
  [7] corpus.H13FilteredSQL  (handlers.go:99)
      origin : request.form
      sink   : database/sql.DB.Query  arg 1  (sql-injection)
      path   : http.Request.FormValue
  [8] corpus.H14CleanGuard  (handlers.go:106)
      origin : request.form
      sink   : os.Open  arg 0  (path-traversal)
      path   : http.Request.FormValue
  [9] corpus.H16PathHandler  (handlers.go:123)
      origin : request.form
      sink   : os.Open  arg 0  (path-traversal)
      path   : http.Request.FormValue
  [10] corpus.H09Header  (handlers.go:72)
      origin : request.form
      sink   : net/http.Header.Set  arg 2  (output-sink)
      path   : http.Request.FormValue

GUARD EFFECTIVENESS — 14 classified
  FUNCTION                             CLASS            CUTS   REASON
  leakcheck.trimFn                     conditional      no     branches on the input; the analyser cannot correlate the branch with the sink
  corpus.CleanGuard                    unknown          no     no rule matched
  corpus.CleanInput                    passthrough      no     returns its argument unchanged
  corpus.EscapeIfNeeded                conditional      no     calls a sanitizer but also branches or transforms
  corpus.FilterQuery                   rewrites         no     transforms the input without calling a recognised sanitizer
  corpus.IsSafePath                    non-forwarding   yes    returns only error/bool values; the input is not forwarded
  corpus.NormalizeName                 rewrites         no     transforms the input without calling a recognised sanitizer
  corpus.SafeToken                     constant         yes    takes no input, so it cannot forward taint
  corpus.SanitizeHTML                  effective        yes    delegates to a recognised sanitizer and does not transform otherwise
  corpus.SanitizeSQLLike               effective        yes    delegates to a recognised sanitizer and does not transform otherwise
  corpus.SanitizeURLComponent          effective        yes    delegates to a recognised sanitizer and does not transform otherwise
  corpus.StripTags                     unknown          no     no rule matched
  corpus.ValidateAndEscape             conditional      no     branches on the input; the analyser cannot correlate the branch with the sink
  corpus.ValidatePath                  non-forwarding   yes    returns only error/bool values; the input is not forwarded

ARGUMENT LAYOUT (probe) — 29 rule(s), 0 suspicious
  CALLEE                                   RULE   PARAMS  DECLARED TYPE        NOTE
  database/sql.DB.Exec                     1      2       string               
  database/sql.DB.ExecContext              2      3       string               
  database/sql.DB.Query                    1      2       string               
  database/sql.DB.QueryContext             2      3       string               
  fmt.Fprint                               any    2       -                    any argument (variadic rule)
  fmt.Fprintf                              any    3       -                    any argument (variadic rule)
  fmt.Fprintln                             any    2       -                    any argument (variadic rule)
  fmt.Print                                any    1       -                    any argument (variadic rule)
  fmt.Printf                               any    2       -                    any argument (variadic rule)
  fmt.Println                              any    1       -                    any argument (variadic rule)
  log.Print                                any    1       -                    any argument (variadic rule)
  log.Printf                               any    2       -                    any argument (variadic rule)
  log.Println                              any    1       -                    any argument (variadic rule)
  net.Dial                                 1      2       string               
  net.DialTimeout                          2      3       time.Duration        
  net/http.Get                             any    1       -                    any argument (variadic rule)
  net/http.Header.Add                      2      2       string               
  net/http.Header.Set                      2      2       string               
  net/http.Post                            any    3       -                    any argument (variadic rule)
  net/http.ResponseWriter.Write            any    1       -                    any argument (variadic rule)
  os.Create                                0      1       string               
  os.File.Write                            any    1       -                    any argument (variadic rule)
  os.Open                                  0      1       string               
  os.OpenFile                              0      3       string               
  os.ReadFile                              0      1       string               
  os.Setenv                                any    2       -                    any argument (variadic rule)
  os.WriteFile                             0      3       string               
  os/exec.Command                          any    2       -                    any argument (variadic rule)
  os/exec.CommandContext                   any    3       -                    any argument (variadic rule)

SECOND PASS — every project guard treated as a no-op
  findings with guards               10
  findings without guards            10
  flows that depend on a guard       0

CAVEATS
  - Sanitizers are not checked against sink kind. url.QueryEscape stops taint at a SQL sink, which is wrong. This is planted false negative FN-1.
  - Variadic sinks use arg == -1, so every argument is treated as dangerous. exec.Command("echo", name) is reported even though the command is constant. Documented false positive.
  - filepath.Base and friends are propagators, not sanitizers, so CleanGuard is reported. Documented false positive.
  - Predicate guards are not correlated with sinks. ValidatePath(name) protects only the branch that consults it; the analyser does not track that, so a handler that reads the raw value is still reported.
  - Interprocedural summaries are one bit per function: 'some parameter taints some result'. They cannot say which parameter or which result.
  - Only functions in the analysed packages are summarised. A taint path through a dependency is invisible unless the dependency is in the load patterns.

cheikh@dev:~/ssa-taint$
Enter fullscreen mode Exit fullscreen mode

Three of Fourteen

Ten findings, and the table that explains them

Ten flows reach a sink. The guard table tells you which of them are supposed to be safe and aren't.

Look at corpus.H14CleanGuard. It calls CleanGuard, which sounds like it cleans. The classifier says unknown — no rule matched — so taint flows through. The caveat section names the reason: filepath.Base is a propagator, not a sanitizer. It strips directory components, which is not the same as making a path safe. ../../etc/passwd becomes passwd; ..%2f..%2fetc%2fpasswd does not.

That is a real bug class, and it is invisible to a name-based scanner.

The delta is zero, and that is the honest result 

findings with guards               10
findings without guards            10
flows that depend on a guard       0
Enter fullscreen mode Exit fullscreen mode

Zero. Not one of the ten findings is currently being suppressed by a guard. Every guard in the corpus either doesn't cut taint (the no rows) or isn't on a path to a sink.

This is a negative result, and it is worth stating plainly rather than dressing up. The corpus was built to exercise the classifier, not to demonstrate a dramatic delta. What the zero tells you is that the classifier's yes verdicts — IsSafePath, SafeToken, ValidatePath, and the three effective sanitizers — are not load-bearing for any of the ten reported flows. The guards that would matter are the ones classified no.

The interesting number is not the delta. It is 3 out of 14. Three guards cut taint; eleven do not. If you shipped this corpus and assumed the guard names meant something, you would be wrong eleven times out of fourteen.

Zero suspicious rows is a real check 

ARGUMENT LAYOUT (probe) — 29 rule(s), 0 suspicious
Enter fullscreen mode Exit fullscreen mode

Twenty-nine sink rules, every argument index verified against the callee's declared signature, zero mismatches. That includes the receiver-shift cases: Header.Set at index 2, QueryContext at index 2, DialTimeout at index 2.

Zero suspicious is the outcome you want, but it is only meaningful because the probe could have failed. The check exists because the indices are guesses, and a guess that is never tested is a bug waiting for a quiet afternoon.

The caveats are the most valuable part

Six documented limitations, and they are not hedging — they are the boundary of what the tool knows:

  • Sanitizers aren't checked against sink kind. url.QueryEscape stops taint at a SQL sink. It shouldn't. This is a planted false negative, and it is the single most important line in the output: it says the tool's notion of "sanitized" is context-free, and context-free sanitization is not a real thing.
  • Variadic sinks use arg == -1, so every argument is dangerous. exec.Command("echo", name) gets reported even though the command is constant.
  • Predicate guards aren't correlated with sinks. ValidatePath(name) protects only the branch that consults it. The analyzer doesn't track that, so a handler that reads the raw value is still reported.
  • Interprocedural summaries are one bit. "Some parameter taints some result." Not which parameter, not which result.
  • Dependencies aren't summarized. A taint path through a library is invisible unless the library is in the load patterns.

A tool that lists its own false positives and false negatives is a tool you can reason about. A tool that reports "10 issues" with no caveats is a tool you have to reverse-engineer.

What Generalizes

SSA was built to make compilers fast. It ended up being the cleanest substrate for asking where does this value go — because that is the same question an optimizer asks, just with a different goal.

The tool in this article is small: about 3,000 SSA instructions analyzed, 80 functions, 14 guards classified, 29 sink rules probed. It found ten real flows and, more usefully, it told you which of its own answers to distrust.

Three things generalize beyond this codebase:

Read the body, not the name. The single highest-value thing an SSA-based analyzer does that a regex cannot is decide whether a function called ValidateAndEscape actually validates or escapes. Eleven of fourteen guards in this corpus did not cut taint. Names are documentation, and documentation drifts.

Measure your assumptions. Every sink rule is a claim about someone else's signature. The probe turns those claims into a table you can check. Zero suspicious rows is a result; an unverified index is a liability.

Publish the caveats. The six limitations are the most honest part of the output. A security tool that doesn't state its false-positive and false-negative modes is asking you to trust it blindly, which is exactly the failure mode it was built to catch.

The Takeaway

If you take one thing from this: taint analysis is not a scanner, it is a data-flow question, and SSA is the representation that makes the question answerable. The golang.org/x/tools/go/ssa package is public, documented, and already powering the tools you use every day. The barrier to writing your own analysis is not the IR — it is deciding what question to ask.

Ask a question whose answer you can verify. Then verify it.

The Code

The full source — the loader, the guard classifier, the fixpoint walk, the argument-layout probe, the corpus, and the tests — is at:

https://github.com/cheikh2shift/go-snippets/tree/main/ssa-taint

Clone it, run go run ., and compare your output against the run above. If a corpus case gets the wrong verdict, that is a finding too.

Sources

Top comments (0)