[C/CPP] Alias Analysis

[xlauko]

Hi,

I was exploring the capabilities of CodeQL, and I come to a situation when neither dataflow nor taint tracking propagates through aliased pointers. I tried to detect use after free; however, I could not detect the following use. The simplified example of the code I analyzed:

void test()
{
    char* p = (char*)malloc(1);
    if (!p)
        return;

    *p = 'x';
    char* cpy = p;
    free(p);

    char use_after_free = *cpy;
    putchar(use_after_free);
}

The query I used (same with TaintTracking).
If I put the copy of the pointer after free, the use is detected. Do I need to augment the isSource predicate somehow?

import cpp

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

class UseAfterFreeConfig extends DataFlow::Configuration {
    UseAfterFreeConfig() { this = "Use after free config" }

    override predicate isSource(DataFlow::Node arg) {
        exists( FunctionCall call |
            call.getArgument(0) = arg.asDefiningArgument() and
            call.getTarget().hasGlobalOrStdName("free")
        )
    }

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

from DataFlow::PathNode source, DataFlow::PathNode sink, UseAfterFreeConfig useAfterFree
where useAfterFree.hasFlowPath(source, sink)
select sink, source, sink, "use after free"

[MathiasVP]

Hi @xlauko,

This is indeed a known limitation of our alias analysis which we perform before computing dataflow. If I understand this sentence correctly:

If I put the copy of the pointer after free, the use is detected. Do I need to augment the isSource predicate somehow?

you're saying that your query does detect this case:

void test()
{
    char* p = (char*)malloc(1);
    if (!p)
        return;

    *p = 'x';
    free(p);
    char* cpy = p;

    char use_after_free = *cpy;
    putchar(use_after_free);
}

which is expected. For various reasons we sometimes treat a read or write to a pointer (i.e., p) as a read or write to the dereferenced value (i.e., *p). So in the case where we do detect the use-after-free we see that data flows from out of free to p, and from p to cpy, and then to a dereference of cpy.

But in your original code example:

void test()
{
    char* p = (char*)malloc(1);
    if (!p)
        return;

    *p = 'x';
    char* cpy = p;
    free(p);

    char use_after_free = *cpy;
    putchar(use_after_free);
}

the aliasing relationship between cpy and p is established "too early" (i.e., before data flows out of p) for us to detect it.

If you really need to detect this case you can implement the isAdditionalFlowStep predicate to provide flow from the value of p after it has been freed to any expression that we can detect will alias with p at the point of calling free. A quick way of doing this is to use GlobalValueNumbering like this:

import cpp
import semmle.code.cpp.dataflow.DataFlow
import semmle.code.cpp.valuenumbering.GlobalValueNumbering
import DataFlow::PathGraph

class UseAfterFreeConfig extends DataFlow::Configuration {
  UseAfterFreeConfig() { this = "Use after free config" }

  override predicate isSource(DataFlow::Node arg) {
    exists(FunctionCall call |
      call.getArgument(0) = arg.asDefiningArgument() and
      call.getTarget().hasGlobalOrStdName("free")
    )
  }

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

  override predicate isAdditionalFlowStep(DataFlow::Node node1, DataFlow::Node node2) {
    globalValueNumber(node1.asDefiningArgument()) = globalValueNumber(node2.asExpr())
  }
}

from DataFlow::PathNode source, DataFlow::PathNode sink, UseAfterFreeConfig useAfterFree
where useAfterFree.hasFlowPath(source, sink)
select sink, source, sink, "use after free"

This is likely not the final version of isAdditionalFlowStep that you want to use: its performance will likely be bad as it adds quite a lot of flow. (Maybe the performance will be acceptable if you limit the predicate to only arguments of free, but it's difficult to tell.)

[xlauko]

Thanks for the quick answer, but now the query recognizes all uses of the pointer as use after free (even the accesses that happens before the free call).
I have tried to filter those sinks. However, it does not seem to work. Can I somehow encode the happens after relation in the CodeQL to filter only those sinks? My try was something like this:

override predicate isSink(DataFlow::Node sink) {
  dereferenced(sink.asExpr())
  and
  not exists( DataFlow::Node free |
    isSource(free) and
    DataFlow::localFlow(DataFlow::exprNode(sink.asExpr()),
                        DataFlow::exprNode(free.asExpr()))
  )
}

[MathiasVP]

Thanks for the quick answer, but now the query recognizes all uses of the pointer as use after free (even the accesses that happens before the free call).

Oh, right. That'll happen with the globalValueNumber-approach since we're using it here to transfer flow to all kinds of places containing the aliased pointer value.

I have tried to filter those sinks. However, it does not seem to work. Can I somehow encode the happens after relation in the CodeQL to filter only those sinks? My try was something like this:

You're on the right track. You want to filter out those nodes that happens-before the call to free. I'm not exactly sure why (a version) of your isSink doesn't work, but I was able to use another library we have called semmle.code.cpp.controlflow.StackVariableReachability like this:

import cpp
import semmle.code.cpp.dataflow.DataFlow
import semmle.code.cpp.valuenumbering.GlobalValueNumbering
import semmle.code.cpp.controlflow.StackVariableReachability
import DataFlow::PathGraph

class DerefToFreeReachability extends StackVariableReachability {
  DerefToFreeReachability() { this = "DerefToFreeReachability" }

  override predicate isSource(ControlFlowNode node, StackVariable v) {
    exists(VariableAccess acc |
      acc = v.getAnAccess() and
      dereferenced(acc) and
      node = acc
    )
  }

  override predicate isSink(ControlFlowNode node, StackVariable v) {
    exists(FunctionCall call |
      call.getArgument(0) = v.getAnAccess() and
      call.getTarget().hasGlobalOrStdName("free") and
      node = call
    )
  }

  override predicate isBarrier(ControlFlowNode node, StackVariable v) { none() }
}

class UseAfterFreeConfig extends DataFlow::Configuration {
  UseAfterFreeConfig() { this = "Use after free config" }

  override predicate isSource(DataFlow::Node arg) {
    exists(FunctionCall call |
      call.getArgument(0) = arg.asDefiningArgument() and
      call.getTarget().hasGlobalOrStdName("free")
    )
  }

  override predicate isSink(DataFlow::Node sink) {
    dereferenced(sink.asExpr()) and
    not exists(DerefToFreeReachability r | r.reaches(sink.asExpr(), _, _))
  }

  override predicate isAdditionalFlowStep(DataFlow::Node node1, DataFlow::Node node2) {
    globalValueNumber(node1.asDefiningArgument()) = globalValueNumber(node2.asExpr())
  }
}

You can read more about StackVariableReachability here: https://codeql.github.com/codeql-standard-libraries/cpp/semmle/code/cpp/controlflow/StackVariableReachability.qll/type.StackVariableReachability$StackVariableReachability.html