Skip to content

Taint Analysis Tutorial: Step-by-Step Guide

This tutorial guides you through implementing a taint analysis with SootUp's IFDS framework. You will learn how to track sensitive data from sources to sinks in Java programs.

All code snippets on this page are taken from TaintAnalysisTest.java, which is executed as part of SootUp's test suite - so the code you see here is guaranteed to compile and work.

What You'll Learn

  • How to define sources, sinks and flow functions
  • How to handle interprocedural taint propagation
  • How to run the IFDS solver and detect information leaks

Prerequisites

Add the following dependencies to your pom.xml:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
<dependencies>
    <dependency>
        <groupId>org.soot-oss</groupId>
        <artifactId>sootup.java.bytecode.frontend</artifactId>
        <version>2.0.0</version>
    </dependency>
    <dependency>
        <groupId>org.soot-oss</groupId>
        <artifactId>sootup.analysis.interprocedural</artifactId>
        <version>2.0.0</version>
    </dependency>
    <dependency>
        <groupId>de.upb.cs.swt</groupId>
        <artifactId>heros</artifactId>
        <version>1.2.3</version>
    </dependency>
</dependencies>

Step 1: Understanding the Problem

Taint analysis tracks the flow of sensitive information through a program. It identifies:

  • Sources: where sensitive data originates (e.g. user input, secrets)
  • Sinks: where data might be leaked (e.g. network calls, logs)
  • Flow: how data propagates through assignments and method calls

In this tutorial, the source is the String constant "SECRET" and every call to a method named sink is a sink.

Example Scenario

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public static class BasicTaint {
  static String c;

  public void entryPoint() {
    String a = "SECRET";
    String b = a;
    c = b;
    SinkClass sc = new SinkClass();
    sc.sink(c);
  }
}

In this example:

  • Source: String a = "SECRET"
  • Flow: a → b → c (the static field c becomes tainted)
  • Sink: sc.sink(c) - the secret leaks

The sink itself is an ordinary method:

1
2
3
4
5
public static class SinkClass {
  public void sink(String s) {
    // any tainted value reaching this method is a leak
  }
}

Step 2: The IFDS Problem

IFDS (Interprocedural, Finite, Distributive, Subset) problems are solved by propagating facts along the interprocedural control flow graph (ICFG). For a taint analysis, a fact is simply a tainted Value (a local variable or a static field).

2.1 The Problem Class

The analysis logic extends DefaultJimpleIFDSTabulationProblem. It keeps the entry method, i.e. the method where the analysis starts:

1
2
3
4
5
6
7
8
9
static class TaintAnalysisProblem
    extends DefaultJimpleIFDSTabulationProblem<Value, InterproceduralCFG<Stmt, SootMethod>> {

  private final SootMethod entryMethod;

  public TaintAnalysisProblem(InterproceduralCFG<Stmt, SootMethod> icfg, SootMethod entryMethod) {
    super(icfg);
    this.entryMethod = entryMethod;
  }

2.2 Initial Seeds

The seeds tell the solver where to start: the first statement of the entry method, holding only the zero value.

1
2
3
4
5
@Override
public Map<Stmt, Set<Value>> initialSeeds() {
  Stmt firstStmt = entryMethod.getBody().getControlFlowGraph().getStartingStmt();
  return DefaultSeeds.make(Collections.singleton(firstStmt), zeroValue());
}

2.3 Zero Value

The zero value (Λ) is a special fact which always holds. New facts are generated from it, e.g. when a source is encountered.

1
2
3
4
@Override
protected Value createZeroValue() {
  return new Local("<<zero>>", NullType.getInstance());
}

2.4 Flow Functions Factory

The solver asks the problem for a flow function for each edge in the ICFG. There are four kinds of edges:

IFDS Flow Functions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
@Override
protected FlowFunctions<Stmt, Value, SootMethod> createFlowFunctionsFactory() {
  return new FlowFunctions<Stmt, Value, SootMethod>() {

    @Override
    public FlowFunction<Value> getNormalFlowFunction(Stmt curr, Stmt succ) {
      return getNormalFlow(curr);
    }

    @Override
    public FlowFunction<Value> getCallFlowFunction(Stmt callStmt, SootMethod callee) {
      return getCallFlow(callStmt, callee);
    }

    @Override
    public FlowFunction<Value> getReturnFlowFunction(
        Stmt callSite, SootMethod callee, Stmt exitStmt, Stmt returnSite) {
      return getReturnFlow(callSite, exitStmt);
    }

    @Override
    public FlowFunction<Value> getCallToReturnFlowFunction(Stmt callSite, Stmt returnSite) {
      return getCallToReturnFlow(callSite);
    }
  };
}
  • normal flow: a statement inside a method, e.g. an assignment
  • call flow: from a call site into the called method
  • return flow: from the exit of the called method back to the caller
  • call-to-return flow: facts that bypass the called method at the call site

We will implement each of them in the next step.

Step 3: Implementing the Flow Functions

A flow function maps one incoming fact to the set of facts that hold afterwards. Heros provides some common ones, e.g. Identity (keep all facts) or Gen (additionally generate a new fact).

3.1 Sources

A helper which decides whether a value is a source:

1
2
3
4
static boolean isSource(Value value) {
  return value instanceof StringConstant
      && ((StringConstant) value).getValue().equals("SECRET");
}

3.2 Normal Flow Function

Handles statements within a method. Only assignments change the set of tainted values:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
FlowFunction<Value> getNormalFlow(Stmt curr) {
  if (!(curr instanceof JAssignStmt)) {
    return Identity.v();
  }
  JAssignStmt assign = (JAssignStmt) curr;
  Value leftOp = assign.getLeftOp();
  Value rightOp = assign.getRightOp();

  // x = "SECRET": x becomes tainted
  if (isSource(rightOp)) {
    return new Gen<>(leftOp, zeroValue());
  }

  return source -> {
    // x = ...: the old value of x is overwritten, so its taint is killed
    if (source.equivTo(leftOp)) {
      return Collections.emptySet();
    }
    Set<Value> out = new HashSet<>();
    out.add(source);
    // x = y: if y is tainted, x becomes tainted as well
    if (source.equivTo(rightOp)) {
      out.add(leftOp);
    }
    return out;
  };
}
  1. Generate: x = "SECRET" taints x.
  2. Kill: any other assignment x = ... removes the taint of x - this is how sanitization works.
  3. Propagate: x = y taints x if y is tainted.

3.3 Call Flow Function

Maps facts of the caller into the callee when a method is called:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
FlowFunction<Value> getCallFlow(Stmt callStmt, SootMethod callee) {
  if (!callee.hasBody()) {
    return source -> Collections.emptySet();
  }
  List<Immediate> args = callStmt.asInvokableStmt().getInvokeExpr().get().getArgs();

  return source -> {
    Set<Value> out = new HashSet<>();
    // tainted static fields are visible inside the callee as well
    if (source instanceof JStaticFieldRef) {
      out.add(source);
    }
    // a tainted argument taints the corresponding parameter of the callee
    for (int i = 0; i < args.size(); i++) {
      if (args.get(i).equivTo(source)) {
        out.add(callee.getBody().getParameterLocal(i));
      }
    }
    return out;
  };
}

A tainted argument taints the corresponding parameter of the callee. Local variables of the caller are not visible in the callee, so all other facts are dropped - except static fields, which are global.

3.4 Return Flow Function

Maps facts of the callee back to the caller when the called method returns:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
FlowFunction<Value> getReturnFlow(Stmt callSite, Stmt exitStmt) {
  // the variable receiving the return value at the call site, e.g. b in "b = id(a)"
  Value receiver =
      callSite instanceof AbstractDefinitionStmt
          ? ((AbstractDefinitionStmt) callSite).getLeftOp()
          : null;
  Value returnOp = exitStmt instanceof JReturnStmt ? ((JReturnStmt) exitStmt).getOp() : null;

  // return "SECRET": the receiver becomes tainted
  if (receiver != null && isSource(returnOp)) {
    return new Gen<>(receiver, zeroValue());
  }

  return source -> {
    Set<Value> out = new HashSet<>();
    // tainted static fields stay tainted after the call
    if (source instanceof JStaticFieldRef) {
      out.add(source);
    }
    // a tainted return value taints the receiver
    if (receiver != null && source.equivTo(returnOp)) {
      out.add(receiver);
    }
    return out;
  };
}
  • A tainted return value taints the variable that receives it at the call site.
  • return "SECRET" is a source as well.
  • Static fields keep their taint.

3.5 Call-to-Return Flow Function

Handles facts of the caller that are not affected by the call:

1
2
3
4
5
6
7
8
9
FlowFunction<Value> getCallToReturnFlow(Stmt callSite) {
  if (!(callSite instanceof AbstractDefinitionStmt)) {
    return Identity.v();
  }
  // b = foo(..): the old value of b is overwritten by the return value
  Value receiver = ((AbstractDefinitionStmt) callSite).getLeftOp();
  return source ->
      source.equivTo(receiver) ? Collections.emptySet() : Collections.singleton(source);
}

All local facts survive the call, except the taint of the variable that is overwritten by the return value.

Step 4: Running the Analysis

4.1 Loading the Program

Create a JavaView for the classes under analysis. We pass an empty list of BodyInterceptors so that the Jimple code stays close to the bytecode (e.g. no constant propagation that would inline "SECRET" into the sink call):

1
2
3
4
5
6
static JavaView createView() {
  AnalysisInputLocation inputLocation =
      new JavaClassPathAnalysisInputLocation(
          "target/test-classes", SourceType.Application, Collections.emptyList());
  return new JavaView(inputLocation);
}

Then look up the method the analysis starts from:

1
2
3
4
5
static SootMethod findEntryMethod(JavaView view, Class<?> targetClass) {
  JavaClassType classType = view.getIdentifierFactory().getClassType(targetClass.getName());
  JavaSootClass sootClass = view.getClass(classType).get();
  return sootClass.getMethodsByName("entryPoint").iterator().next();
}

4.2 Solving the IFDS Problem

Build the ICFG starting from the entry method, create the problem and let the JimpleIFDSSolver compute all facts:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
static JimpleIFDSSolver<Value, InterproceduralCFG<Stmt, SootMethod>> runAnalysis(
    JavaView view, SootMethod entryMethod) {
  JimpleBasedInterproceduralCFG icfg =
      new JimpleBasedInterproceduralCFG(
          view, Collections.singletonList(entryMethod.getSignature()), false, false);
  TaintAnalysisProblem problem = new TaintAnalysisProblem(icfg, entryMethod);
  JimpleIFDSSolver<Value, InterproceduralCFG<Stmt, SootMethod>> solver =
      new JimpleIFDSSolver<>(problem);
  solver.solve(entryMethod.getDeclaringClassType().getClassName());
  return solver;
}

4.3 Detecting Leaks

After solving, solver.ifdsResultsAt(stmt) returns all facts that hold at a statement. A leak exists if an argument of a sink(..) call is tainted:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static boolean leaksToSink(Class<?> targetClass) {
  JavaView view = createView();
  SootMethod entryMethod = findEntryMethod(view, targetClass);
  JimpleIFDSSolver<Value, InterproceduralCFG<Stmt, SootMethod>> solver =
      runAnalysis(view, entryMethod);

  for (Stmt stmt : entryMethod.getBody().getStmts()) {
    if (!stmt.isInvokableStmt() || !stmt.asInvokableStmt().getInvokeExpr().isPresent()) {
      continue;
    }
    AbstractInvokeExpr invokeExpr = stmt.asInvokableStmt().getInvokeExpr().get();
    if (!invokeExpr.getMethodSignature().getName().equals("sink")) {
      continue;
    }
    // the facts that hold right before the call to sink(..)
    Set<Value> taintedValues = solver.ifdsResultsAt(stmt);
    for (Immediate arg : invokeExpr.getArgs()) {
      if (taintedValues.stream().anyMatch(arg::equivTo)) {
        return true;
      }
    }
  }
  return false;
}

Step 5: Testing Different Scenarios

5.1 Sanitization

b is overwritten with a harmless value before it reaches the sink, so the normal flow function kills its taint:

1
2
3
4
5
6
7
8
9
public static class BasicTaintSanitized {
  public void entryPoint() {
    String a = "SECRET";
    String b = a;
    b = "..."; // sanitization: b is overwritten with a harmless value
    SinkClass sc = new SinkClass();
    sc.sink(b);
  }
}

5.2 Interprocedural Propagation

The taint enters id via the call flow function (a → s) and comes back via the return flow function (s → b):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public static class FunctionPropagatesTaint {
  private String id(String s) {
    return s;
  }

  public void entryPoint() {
    String a = "SECRET";
    String b = id(a);
    SinkClass sc = new SinkClass();
    sc.sink(b);
  }
}

5.3 Source in a Return Value

The secret is created by return "SECRET" inside source():

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public static class FunctionReturnsTaint {
  private String source() {
    return "SECRET";
  }

  private void sink(String s) {}

  public void entryPoint() {
    String a = source();
    String b = a;
    sink(b);
  }
}

5.4 The Tests

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
@Test
public void basicTaintLeaks() {
  assertTrue(leaksToSink(BasicTaint.class));
}

@Test
public void sanitizedTaintDoesNotLeak() {
  assertFalse(leaksToSink(BasicTaintSanitized.class));
}

@Test
public void taintPropagatesThroughFunction() {
  assertTrue(leaksToSink(FunctionPropagatesTaint.class));
}

@Test
public void taintReturnedFromFunctionLeaks() {
  assertTrue(leaksToSink(FunctionReturnsTaint.class));
}

Step 6: Extending the Analysis

This analysis is intentionally minimal. Some ideas to extend it:

  • Custom sources and sinks: recognize method calls like getUserInput() as sources in the call-to-return flow function, and methods like sendToServer(..) as sinks.
  • Sanitizers: treat calls like sanitize(x) as a kill of the receiver's taint.
  • Field sensitivity: track instance fields (JInstanceFieldRef) in addition to locals and static fields.
  • Aliasing: combine the analysis with a pointer analysis to handle taints via aliased objects.