Help with control-flow taint propagation

[marpom]

Hello,

I'm trying to expand the taint analysis module to also track control flow tainting. What this means is that if there are tainted values in the condition of an if/switch/loop statement, then any variables that change value in the body also become tainted.
To give a trivial example in the following example, not_tainted_before should become tainted:

if (tainted)
   not_tainted_before = 5

I've written the query and I can see that such variables become tainted within the body, but it looks like the taint is not propagated outside of the body. This is a minimal example:

library.cc:

#include "absl/base/casts.h"

void outside_fun(uint64_t arg);

class ExampleClass {
 private:
  void HandleWrite(uint64_t value) {
    uint64_t tainted;
    for (uint64_t i = 0; i < value; i++)
      tainted = i+1;

    outside_fun(tainted);
  }
};

BUILD:

cc_library(
    name = "library",
    srcs = ["library.cc"],
    deps = [
        "@com_google_absl//absl/base:base",
    ],
)

and query.ql:

import cpp
import semmle.code.cpp.dataflow.new.DataFlow
import semmle.code.cpp.dataflow.new.TaintTracking
import semmle.code.cpp.ir.implementation.unaliased_ssa.Instruction

module SampleConfig implements DataFlow::ConfigSig {
  predicate isSource(DataFlow::Node source) { 
    exists( Function function | 
      function.getName() = "HandleWrite" and
      source.asParameter() = function.getParameter(0)
    )
  }

  predicate isSink(DataFlow::Node sink) {
    any()
  }

  additional VariableAccess getAccessFromAssignment(Expr expr) {
    (
      expr instanceof CrementOperation and
      result = expr.(CrementOperation).getOperand()
    ) or 
    (
      expr instanceof Assignment and
      result = expr.(Assignment).getLValue()
    )
  }
  
  additional VariableAccess getAccessFromFunction(Expr expr) {
    exists(Function fn, ExprStmt fn_stmt, BlockStmt fn_block |
      expr instanceof FunctionCall and
      fn = expr.(FunctionCall).getTarget() and
      fn_block = fn.getEntryPoint() and
      fn_block.getAStmt*() = fn_stmt and
      result = getAccessFromAssignment(fn_stmt.getExpr())
    )
  }
  
  additional VariableAccess getModifiedVariable(Stmt stmt) {
    // { expressions; }
    exists (
      BlockStmt block, ExprStmt expr_stmt|
      (
        block = stmt and
        expr_stmt = block.getAStmt*() and
        (
          result = getAccessFromAssignment(expr_stmt.getExpr())
          or
          result = getAccessFromFunction(expr_stmt.getExpr())
        ) 
      )
    )
    // single expressions
    or
    exists (
      ExprStmt expr_stmt |
      expr_stmt = stmt and
      (
        result = getAccessFromAssignment(expr_stmt.getExpr())
        or
        result = getAccessFromFunction(expr_stmt.getExpr())
      )
    )
  }
  predicate isAdditionalFlowStep(DataFlow::Node nodeFrom, DataFlow::Node nodeTo) {
    exists(Loop loopStmt, VariableAccess access |
      loopStmt.getCondition().getAChild*() = nodeFrom.asExpr() and
      access = getModifiedVariable(loopStmt.getStmt()) and
      access = nodeTo.asExpr()
    )
  }
}


module SampleFlow = TaintTracking::Global<SampleConfig>;
import SampleFlow::PathGraph

from SampleFlow::PathNode source, SampleFlow::PathNode sink
where SampleFlow::flowPath(source, sink)
select sink, sink.getLocation()

Create the db with:
codeql database create database --language=cpp --command='bazel build --spawn_strategy=local --nouse_action_cache --noremote_accept_cached --noremote_upload_local_results //library:library'

and execute the query with:
codeql query run --database=<path>/database -- <path>/query.ql

In this example, we would expect tainted at line 12 to be reported but it's not, even though it is reported at line 10. Do you have any ideas on how to fix this?

Thanks!

[jketema]

Hi @marpom,

Thanks for your question.

Looking at your imports, it seems that you already briefly explored the IR. The IR would indeed provided the easiest solution here, by looking at the StoreInstructions that happen in the body, and which will derive from the expressions in the body. Limiting myself to loop statements, slightly generalising the sources (for my own testing pusposes), and making the sink more specific. I would do something like the following:

/**
 * @id cpp/test
 * @kind path-problem
 * @problem.severity warning
 */

import cpp
import semmle.code.cpp.dataflow.new.TaintTracking
import semmle.code.cpp.ir.IR
import SampleFlow::PathGraph

module SampleConfig implements DataFlow::ConfigSig {
  predicate isSource(DataFlow::Node source) {
    exists(Function f | f.getName().matches("HandleWrite%") |
      source.asParameter() = f.getParameter(0)
    )
  }

  predicate isSink(DataFlow::Node sink) {
    exists(FunctionCall c | c.getTarget().getName() = "outside_fun" |
      c.getArgument(0) = sink.asExpr()
    )
  }

  predicate isAdditionalFlowStep(DataFlow::Node nodeFrom, DataFlow::Node nodeTo) {
    exists(Loop loopStmt |
      loopStmt.getCondition().getAChild*() = nodeFrom.asExpr() and
      nodeTo.asInstruction() instanceof StoreInstruction and
      nodeTo.asInstruction().getAst().getEnclosingElement*() = loopStmt.getStmt()
    )
  }
}

module SampleFlow = TaintTracking::Global<SampleConfig>;

from SampleFlow::PathNode source, SampleFlow::PathNode sink
where SampleFlow::flowPath(source, sink)
select sink.getNode(), source, sink, "<message>"

[marpom]

Thanks a lot @jketema, this does exactly what I wanted.
If the explanation is simple enough and not related to something very deep in the internals, could you please explain why my approach failed to propagate the taint?
I'm mainly asking in case something like this happens again in a different context.

Thanks a lot again!

[jketema]

If the explanation is simple enough and not related to something very deep in the internals, could you please explain why my approach failed to propagate the taint?

I must admit I didn't look in detail at your solution, as I knew there would be a simpler one. Probably the easiest way to figure out why it failed is to use VSCode, install the CodeQL extension, load the database, and use the "Quick Evaluation" feature described here: https://docs.github.com/en/code-security/codeql-for-vs-code/getting-started-with-codeql-for-vs-code/running-codeql-queries#running-a-specific-part-of-a-query-or-library. If the quick evaluation does not produce the results you expect that's likely the place there something is amiss in your query.

[marpom]

Makes sense, thank you!