How can I find all of the access of a pointer?

[Just1ceP4rtn3r]

Given a global linked list List

struct Link{
    int a;
    struct Link* next;
};

struct Link* List = (struct Link*)malloc(sizeof(struct Link));

Then, there are some pointers that point to one of the nodes of List

struct Link* ptr_1 = List->next->next;

I have some trouble with finding out any access to the nodes of List. Here is my code

import semmle.code.cpp.dataflow.TaintTracking

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

  override predicate isSource(DataFlow::Node source) {
    exists(VariableAccess local_roles |
      local_roles.getTarget().hasName("List") and source.asExpr() = local_roles
    )
  }

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

from DataFlow::Node source, DataFlow::Node sink, EnvironmentToFileConfiguration config
where config.hasFlow(source, sink)
select source, sink

But I can not find the access of node with ptr_1, e.g.

ptr_1->a = 0;

[geoffw0]

Hi @Just1ceP4rtn3r,

Your code looks incomplete (neither the source nor the sink in EnvironmentToFileConfiguration is bound) but I think I can see what you're trying to do. Which taint tracking library are you using?

[Just1ceP4rtn3r]

Oh, sorry for that, and I have completed the code. semmle.code.cpp.dataflow.TaintTracking is used.

[geoffw0]

Hi,

This is a bit tricky for subtle reasons. For an expression such as a->b, the taint library tracks taint of the pointer a separately from its content accessed by a->b. In your case, List may be tainted while List->next->next is not. We can work around this by adding a custom taint step (isAdditionalTaintStep).

Additionally, the taint library doesn't (yet) fully support taint flows from global variable initializers, so we will get better results if we start from accesses to those variables instead.

This is the best I've come up with:

import cpp
import semmle.code.cpp.dataflow.TaintTracking
import DataFlow::PathGraph

/**
 * Holds if `v` is a global variable called `List`, or another global variable initialized using it.
 */
predicate listGlobal(GlobalVariable v) {
  v.hasName("List") or
  listGlobal(v.getInitializer().getExpr().getAChild*().(VariableAccess).getTarget())
}

/**
 * Flow from accesses to a `listGlobal`.
 */
class EnvironmentToFileConfiguration extends TaintTracking::Configuration {
  EnvironmentToFileConfiguration() { this = "EnvironmentToFileConfiguration" }

  override predicate isSource(DataFlow::Node source) {
    // `node` is an access to a `listGlobal`
    listGlobal(source.asExpr().(VariableAccess).getTarget())
  }

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

  override predicate isAdditionalTaintStep(DataFlow::Node node1, DataFlow::Node node2) {
    // flow out of the qualifier `ptr` to `next` in an expression `ptr->next`
    node2.asExpr().(VariableAccess).getTarget().hasName("next") and
    node1.asExpr() = node2.asExpr().(VariableAccess).getQualifier()
  }
}

from EnvironmentToFileConfiguration config, DataFlow::PathNode source, DataFlow::PathNode sink
where config.hasFlowPath(source, sink)
select source, sink, source

I've tried to write isAdditionalTaintStep such that it won't create a very large number of additional taint steps on a real world project. You will also need to constrain isSink at some point to make this code practical.

[Just1ceP4rtn3r]

Thanks very much! It works for me.