Go Static Analysis with SSA

SSA Value Graph

An interesting aspect about SSA is that it is actually a graph. Each node in the graph can either be an ssa.Value, ssa.Instruction, or both. The contents of a node can be inspected, including its type information or the values it uses or references.

To make this idea more concrete, let's look at the following function:

func add(a, b int) int {
    return a + b
}

The function takes two function arguments, a and b of type int; it returns a value of type int. The function body is a single return statement, which returns the sum of a and b. The SSA form of this function is:

add
0: entry
  a = Arg[0] (a int)
  b = Arg[1] (b int)
  t0 = *a (int)
  t1 = *b (int)
  t2 = t0 + t1 (int)
  t3 = *t2 (int)
  return t3

The first ssa.BasicBlock object in the graph is the entry block (0). The entry block is the first block to be executed when the function is called. This entry block starts with two ssa.Instruction objects:

1. An ssa.Store which stores the value of the first function argument (a) into a variable named t0.
2. Another ssa.Store which stores the value of the second function argument (b) into a variable named t1.

They are connected to the next ssa.Value object by an ssa.Instruction object for a binary operation which adds the values of t0 and t1 together. The result of the addition is stored in a variable named t2.

t2 is connected to the next ssa.Value object by another ssa.Instruction, a unary operation which returns the value of t2. It is connected with another ssa.Instruction object that stores the value of t3. This value is used in a return statement using the value of t3, the last ssa.Value object in the function subgraph.

While we were able to easily visualize the SSA value graph for the add function, it is important to note that the graph is not limited to just a single function. Other functions are likely involved in the program you are trying to analyze, with more even more ssa.Value and ssa.Instruction objects. These objects may be passed as arguments to other functions, or returned as the result of a function call. Functions may also call other functions, building a related graph called a "call graph".

Most static analysis is a combination of a data flow analysis and control flow analysis. Generally speaking, an SSA value graph is a data flow graph, and a call graph is a control flow graph.

Function Call Graphs from SSA

We can construct a call graph by traversing the ssa.Value graph, keeping track of the functions we have visited, and how they are connected. This can be modeled using the golang.org/x/tools/go/callgraph package.

It provides a callgraph.Graph object which contains a callgraph.Node object for each function in the program. Each callgraph.Node object keeps track of the functions that call it ("in"), and the functions it calls ("out").

Building a callgraph.Graph can be performed using several different algorithms with off-the-shelf packages.

Each of these algorithms have their advantages and disadvantages. The cha package is the most accurate, and is a good place to start. If you are analyzing a large and complex program, you may want to use the rta or vta packages.

You may need to experiment with different algorithms to find the best one for your targets or use case.

Once you have a callgraph.Graph object, you can use it to anser questions like:

Taint Analysis

A call graph path can be used as the foundation for additional analysis such as tainted data flow analysis (or " taint analysis") to find security vulnerabilities in a program.

For example, if a function takes a string as an argument from an HTTP request, and that string is used in a SQL query, the string is tainted. If the tainted string is then used in a function that takes a string as an argument, the string is passed to the function tainted. This is the foundation for finding exploitable SQL injection vulnerabilities in a program.

Tainted data flow analysis is a fairly complex topic, and is beyond the scope of this blog post. However, I look forward to writing about it in depth in the near future. But, the key insight is that the call graph is a building block for this type of analysis, which is used along with an SSA value graph to perform the full analyis. We find where the SQL queries happen through the call graph (the "sink"), then use the SSA value graph to walk back to the tainted data (the "source"). The terms "source" and "sink" are common in the world of taint analysis, and are used to describe the start and end of the data flow.

The graphs would also indicate how the tainted data is used in the SQL query, which is important for determining if the vulnerability is exploitable. If using a prepared statement (an ssa.Const), then there is no exploit. The SQL query is safe. If using a string concatenation (an ssa.BinOp), then there is an exploit. The SQL query is unsafe.

These two types of graph-based analysis techniques are complementary and can be used to accurately inspect programs to find vulnerabilities. SSA provides the substrate for the analysis. This is generally a better interface to inspect a program than using the underlying Abstract Syntax Tree (AST) directly. The SSA value graph and call graph provide additional lenses to view the program.