Analyzing data flow in C/C++

Overview

This topic describes how data flow analysis is implemented in the CodeQL libraries for C/C++ and includes examples to help you write your own data flow queries. The following sections describe how to utilize the libraries for local data flow, global data flow, and taint tracking.

For a more general introduction to modeling data flow, see Introduction to data flow analysis with CodeQL.

Local data flow

Local data flow is data flow within a single function. Local data flow is usually easier, faster, and more precise than global data flow, and is sufficient for many queries.

Using local data flow

The local data flow library is in the module DataFlow, which defines the class Node denoting any element that data can flow through. Nodes are divided into expression nodes (ExprNode) and parameter nodes (ParameterNode). It is possible to map between data flow nodes and expressions/parameters using the member predicates asExpr and asParameter:

class Node {
  /** Gets the expression corresponding to this node, if any. */
  Expr asExpr() { ... }

  /** Gets the parameter corresponding to this node, if any. */
  Parameter asParameter() { ... }

  ...
}

or using the predicates exprNode and parameterNode:

/**
 * Gets the node corresponding to expression `e`.
 */
ExprNode exprNode(Expr e) { ... }

/**
 * Gets the node corresponding to the value of parameter `p` at function entry.
 */
ParameterNode parameterNode(Parameter p) { ... }

The predicate localFlowStep(Node nodeFrom, Node, nodeTo) holds if there is an immediate data flow edge from the node nodeFrom to the node nodeTo. The predicate can be applied recursively (using the + and * operators), or through the predefined recursive predicate localFlow, which is equivalent to localFlowStep*.

For example, finding flow from a parameter source to an expression sink in zero or more local steps can be achieved as follows:

DataFlow::localFlow(DataFlow::parameterNode(source), DataFlow::exprNode(sink))

Using local taint tracking

Local taint tracking extends local data flow by including non-value-preserving flow steps. For example:

int i = tainted_user_input();
some_big_struct *array = malloc(i * sizeof(some_big_struct));

In this case, the argument to malloc is tainted.

The local taint tracking library is in the module TaintTracking. Like local data flow, a predicate localTaintStep(DataFlow::Node nodeFrom, DataFlow::Node nodeTo) holds if there is an immediate taint propagation edge from the node nodeFrom to the node nodeTo. The predicate can be applied recursively (using the + and * operators), or through the predefined recursive predicate localTaint, which is equivalent to localTaintStep*.

For example, finding taint propagation from a parameter source to an expression sink in zero or more local steps can be achieved as follows:

TaintTracking::localTaint(DataFlow::parameterNode(source), DataFlow::exprNode(sink))

Examples

The following query finds the filename passed to fopen.

import cpp

from Function fopen, FunctionCall fc
where fopen.hasQualifiedName("fopen")
  and fc.getTarget() = fopen
select fc.getArgument(0)

Unfortunately, this will only give the expression in the argument, not the values which could be passed to it. So we use local data flow to find all expressions that flow into the argument:

import cpp
import semmle.code.cpp.dataflow.DataFlow

from Function fopen, FunctionCall fc, Expr src
where fopen.hasQualifiedName("fopen")
  and fc.getTarget() = fopen
  and DataFlow::localFlow(DataFlow::exprNode(src), DataFlow::exprNode(fc.getArgument(0)))
select src

Then we can vary the source, for example an access to a public parameter. The following query finds where a public parameter is used to open a file:

import cpp
import semmle.code.cpp.dataflow.DataFlow

from Function fopen, FunctionCall fc, Parameter p
where fopen.hasQualifiedName("fopen")
  and fc.getTarget() = fopen
  and DataFlow::localFlow(DataFlow::parameterNode(p), DataFlow::exprNode(fc.getArgument(0)))
select p

The following example finds calls to formatting functions where the format string is not hard-coded.

import semmle.code.cpp.dataflow.DataFlow
import semmle.code.cpp.commons.Printf

from FormattingFunction format, FunctionCall call, Expr formatString
where call.getTarget() = format
  and call.getArgument(format.getFormatParameterIndex()) = formatString
  and not exists(DataFlow::Node source, DataFlow::Node sink |
    DataFlow::localFlow(source, sink) and
    source.asExpr() instanceof StringLiteral and
    sink.asExpr() = formatString
  )
select call, "Argument to " + format.getQualifiedName() + " isn't hard-coded."

Exercises

Exercise 1: Write a query that finds all hard-coded strings used to create a host_ent via gethostbyname, using local data flow. (Answer)

Global data flow

Global data flow tracks data flow throughout the entire program, and is therefore more powerful than local data flow. However, global data flow is less precise than local data flow, and the analysis typically requires significantly more time and memory to perform.

Using global data flow

The global data flow library is used by extending the class DataFlow::Configuration as follows:

import semmle.code.cpp.dataflow.DataFlow

class MyDataFlowConfiguration extends DataFlow::Configuration {
  MyDataFlowConfiguration() { this = "MyDataFlowConfiguration" }

  override predicate isSource(DataFlow::Node source) {
    ...
  }

  override predicate isSink(DataFlow::Node sink) {
    ...
  }
}

The following predicates are defined in the configuration:

  • isSource—defines where data may flow from
  • isSink—defines where data may flow to
  • isBarrier—optional, restricts the data flow
  • isBarrierGuard—optional, restricts the data flow
  • isAdditionalFlowStep—optional, adds additional flow steps

The characteristic predicate MyDataFlowConfiguration() defines the name of the configuration, so "MyDataFlowConfiguration" should be replaced by the name of your class.

The data flow analysis is performed using the predicate hasFlow(DataFlow::Node source, DataFlow::Node sink):

from MyDataFlowConfiguration dataflow, DataFlow::Node source, DataFlow::Node sink
where dataflow.hasFlow(source, sink)
select source, "Data flow to $@.", sink, sink.toString()

Using global taint tracking

Global taint tracking is to global data flow as local taint tracking is to local data flow. That is, global taint tracking extends global data flow with additional non-value-preserving steps. The global taint tracking library is used by extending the class TaintTracking::Configuration as follows:

import semmle.code.cpp.dataflow.TaintTracking

class MyTaintTrackingConfiguration extends TaintTracking::Configuration {
  MyTaintTrackingConfiguration() { this = "MyTaintTrackingConfiguration" }

  override predicate isSource(DataFlow::Node source) {
    ...
  }

  override predicate isSink(DataFlow::Node sink) {
    ...
  }
}

The following predicates are defined in the configuration:

  • isSource—defines where taint may flow from
  • isSink—defines where taint may flow to
  • isSanitizer—optional, restricts the taint flow
  • isSanitizerGuard—optional, restricts the taint flow
  • isAdditionalTaintStep—optional, adds additional taint steps

Similar to global data flow, the characteristic predicate MyTaintTrackingConfiguration() defines the unique name of the configuration, so "MyTaintTrackingConfiguration" should be replaced by the name of your class.

The taint tracking analysis is performed using the predicate hasFlow(DataFlow::Node source, DataFlow::Node sink).

Examples

The following data flow configuration tracks data flow from environment variables to opening files in a Unix-like environment:

import semmle.code.cpp.dataflow.DataFlow

class EnvironmentToFileConfiguration extends DataFlow::Configuration {
  EnvironmentToFileConfiguration() { this = "EnvironmentToFileConfiguration" }

  override predicate isSource(DataFlow::Node source) {
    exists (Function getenv |
      source.asExpr().(FunctionCall).getTarget() = getenv and
      getenv.hasQualifiedName("getenv")
    )
  }

  override predicate isSink(DataFlow::Node sink) {
    exists (FunctionCall fc |
      sink.asExpr() = fc.getArgument(0) and
      fc.getTarget().hasQualifiedName("fopen")
    )
  }
}

from Expr getenv, Expr fopen, EnvironmentToFileConfiguration config
where config.hasFlow(DataFlow::exprNode(getenv), DataFlow::exprNode(fopen))
select fopen, "This 'fopen' uses data from $@.",
  getenv, "call to 'getenv'"

Exercises

Exercise 2: Write a query that finds all hard-coded strings used to create a host_ent via gethostbyname, using global data flow. (Answer)

Exercise 3: Write a class that represents flow sources from getenv. (Answer)

Exercise 4: Using the answers from 2 and 3, write a query which finds all global data flows from getenv to gethostbyname. (Answer)

Answers

Exercise 1

import semmle.code.cpp.dataflow.DataFlow

from StringLiteral sl, FunctionCall fc
where fc.getTarget().hasName("gethostbyname")
  and DataFlow::localFlow(DataFlow::exprNode(sl), DataFlow::exprNode(fc.getArgument(0)))
select sl, fc

Exercise 2

import semmle.code.cpp.dataflow.DataFlow

class LiteralToGethostbynameConfiguration extends DataFlow::Configuration {
  LiteralToGethostbynameConfiguration() {
    this = "LiteralToGethostbynameConfiguration"
  }

  override predicate isSource(DataFlow::Node source) {
    source.asExpr() instanceof StringLiteral
  }

  override predicate isSink(DataFlow::Node sink) {
    exists (FunctionCall fc |
      sink.asExpr() = fc.getArgument(0) and
      fc.getTarget().hasName("gethostbyname"))
  }
}

from StringLiteral sl, FunctionCall fc, LiteralToGethostbynameConfiguration cfg
where cfg.hasFlow(DataFlow::exprNode(sl), DataFlow::exprNode(fc.getArgument(0)))
select sl, fc

Exercise 3

import cpp

class GetenvSource extends FunctionCall {
  GetenvSource() {
    this.getTarget().hasQualifiedName("getenv")
  }
}

Exercise 4

import semmle.code.cpp.dataflow.DataFlow

class GetenvSource extends DataFlow::Node {
  GetenvSource() {
    this.asExpr().(FunctionCall).getTarget().hasQualifiedName("getenv")
  }
}

class GetenvToGethostbynameConfiguration extends DataFlow::Configuration {
  GetenvToGethostbynameConfiguration() {
    this = "GetenvToGethostbynameConfiguration"
  }

  override predicate isSource(DataFlow::Node source) {
    source instanceof GetenvSource
  }

  override predicate isSink(DataFlow::Node sink) {
    exists (FunctionCall fc |
      sink.asExpr() = fc.getArgument(0) and
      fc.getTarget().hasName("gethostbyname"))
  }
}

from DataFlow::Node getenv, FunctionCall fc, GetenvToGethostbynameConfiguration cfg
where cfg.hasFlow(getenv, DataFlow::exprNode(fc.getArgument(0)))
select getenv.asExpr(), fc