Using CodeQL for Data Flow Analysis and Visualization

[sei-yhindka]

Background

My team and I have been experimenting with CodeQL for some time, and we need some guidance on filtering CodeQL's data flow analysis results and on using the graph making capabilities.

Below is the query we have come up with. It traces flow from a function parameter and its fields to any sink:

import cpp
import semmle.code.cpp.dataflow.new.TaintTracking

module StructDataFlowConfiguration implements DataFlow::ConfigSig 
{
    predicate isSource(DataFlow::Node source) 
    {
        exists(Function fxn, Parameter p |

            // scope to function
            fxn.getName() = "github_discussion_example"

            // scope to parameter within function
            and p.getFunction() = fxn
            and p.getName() = "status"

            and (
                // check if source is the parameter itself
                source.asExpr().getEnclosingDeclaration() = p.getEnclosingElement().(Declaration)

                // check if source is a field of the parameter
                or source.asExpr().(FieldAccess).getEnclosingDeclaration() = p.getEnclosingElement().(Declaration)
            )
        )
    }
    
    predicate isSink(DataFlow::Node sink)
    {
        any()
    } 
}

module StructDataFlow = TaintTracking::Global<StructDataFlowConfiguration>;
import StructDataFlow::PathGraph

from StructDataFlow::PathNode source, StructDataFlow::PathNode sink
where StructDataFlow::flowPath(source, sink)
select sink.getNode(), source, sink, "Found path"

Here is some minimal code that you can run the query on to produce results.

// .h file
struct status_msg_t {
        uint8_t tx;
        uint8_t status;
};

// .c file
void github_discussion_example(struct status_msg_t status)
{
    uint8_t status_bit = status.status;
    if (! status_bit) return;

    uint8_t tx_bit = status.tx;
    if (! tx_bit) return;
}

Issues

1. The above query produces good results but also many duplicates. For example, there are multiple flows that begin at status.status and end at if (! status_bit) return; In addition, there are multiple flows that start and end at if (! tx_bit) return; There are many more such examples. How can we refine this query to reduce/eliminate duplicates?
2. We would like to see only the flows that go to the deepest level. In the minimal example above, we would only like to see only 2 flows:

• status parameter -> status_bit -> if condition
• status parameter -> tx_bit -> if condition

3. We would like to rewrite the above query into an @kind graph query and then view the output as a visual graph (perhaps use bqrs interpret to convert the raw query output to a dot file). How can we go about doing this? We have seen How to use @kind graph query? #7437, but were not able to make much sense of it and documentation is scarce.

Thanks!

[smowton]

Do you care about interprocedural flows, or only within a single procedure?

[sei-yhindka]

We want the intermediate path nodes, but all incorporated into a single path. Not separate paths for each intermediate node.

[smowton]

Do you want the source to be the parameter status or a field read coming from it? If so that isn't working; at the moment the sources are every expression in a function named github_discussion_example that has a parameter status.

I think you probably want

                // check if source is the parameter itself
                source.asParameter() = p

                // check if source is a field of the parameter
                or source.asExpr().(FieldAccess).getQualifier() = p.getAnAccess()

which immediately cuts the paths down a lot.

[smowton]

Re: sinks that in turn flow on to other use sites, this can be a bit nuanced but I think you'd get quite a way by excluding various sorts of sink that obviously go somewhere else in the user program, such as:

    not DataFlow::localFlowStep(sink, _) and // Local flow
    not TaintTracking::localTaintStep(sink, _) and // Local taint flow (e.g. conversions, string concatenation, container store...)
    not isSource(sink) and // Eliminate zero-step paths
    not sink.asExpr() = any(ReturnStmt rs).getExpr() and // Returned and presumably flows onwards (refine: check if we know of any callers for this function)
    not sink.asExpr() = any(Call c | c.getTarget().hasDefinition()).getAnArgument() // Passed into a call with a definition (refine: check if the argument is unused)

[sei-yhindka]

You are correct, this does cut down the paths a lot: I only get 13 results now. However, for such a small toy example, 13 paths is still a lot. Especially when I would like there to be only ~2. Is there a way we can remove duplicates?

Also, I have another question. How can we output the results in a dot format? I think it would be very helpful to visualize this data flow.

[smowton]

Finally if you want path information I suspect @kind graph is not what you want. I would start by trying interpreting to SARIF since that has an expressive format for conveying sources, sinks and the paths in between them (and interpret-results flags for limiting how many paths are exported), and try scripting the conversion into whatever graph description format is useful to you.

[sei-yhindka]

You are correct, this does cut down the paths a lot: I only get 13 results now. However, for such a small toy example, 13 paths is still a lot. Especially when I would like there to be only ~2. Is there a way we can remove duplicates?

Also, I have another question. How can we output the results in a dot format? I think it would be very helpful to visualize this data flow.

Re: sinks that in turn flow on to other use sites, this can be a bit nuanced but I think you'd get quite a way by excluding various sorts of sink that obviously go somewhere else in the user program, such as:

    not DataFlow::localFlowStep(sink, _) and // Local flow
    not TaintTracking::localTaintStep(sink, _) and // Local taint flow (e.g. conversions, string concatenation, container store...)
    not isSource(sink) and // Eliminate zero-step paths
    not sink.asExpr() = any(ReturnStmt rs).getExpr() and // Returned and presumably flows onwards (refine: check if we know of any callers for this function)
    not sink.asExpr() = any(Call c | c.getTarget().hasDefinition()).getAnArgument() // Passed into a call with a definition (refine: check if the argument is unused)

This helped a lot, thanks!

[intrigus-lgtm]

Try this:
It correctly uses source.asParameter to only consider data flow nodes that are the "status" parameter.

Now for whatever reason while status_msg_t status is considered tainted, it appears that CodeQL does not consider its fields also tainted. (I personally would expect all fields to be tainted, when the whole actual struct is considered my source, but I guess there is probably a more than valid reason for this decision)

So without isAdditionalFlowStep, the taint flow would stop at *status in status.status.
We can teach CodeQL that whenever we have a field access (i.e. struct.field) that taint should flow to the field.
To prevent false positives, we only consider such flow for structs of the type status_msg_t.
With this and a restricted sink, we now get exactly the two flow paths that you described.
(I had to use getAChild* in the sink, because while status_bit is considered tainted, this taint does not flow to !status_bit, so just doing is.getCondition() = sink.asExpr() doesn't work)

/**
 * @kind path-problem
 */

import cpp
import semmle.code.cpp.dataflow.new.TaintTracking

module StructDataFlowConfiguration implements DataFlow::ConfigSig {
  predicate isSource(DataFlow::Node source) {
    exists(Function fxn, Parameter p |
      // scope to function
      fxn.getName() = "github_discussion_example" and
      // scope to parameter within function
      p.getFunction() = fxn and
      p.getName() = "status" and
      p = source.asParameter()
    )
  }

  predicate isSink(DataFlow::Node sink) {
    exists(IfStmt is | is.getCondition().getAChild*() = sink.asExpr())
  }

  predicate isAdditionalFlowStep(DataFlow::Node n1, DataFlow::Node n2) {
    exists(FieldAccess fa |
      n1.asIndirectExpr() = fa.getQualifier() and
      n2.asExpr() = fa and
      fa.getQualifier().getType().(UserType).hasQualifiedName("", "status_msg_t")
    )
  }
}

module Flows = DataFlow::Global<StructDataFlowConfiguration>;

import Flows::PathGraph

from Flows::PathNode source, Flows::PathNode sink
where Flows::flowPath(source, sink)
select sink.getNode(), source, sink, "This node receives flow from $@.", source.getNode(),
  "this source"

[sei-yhindka]

Thanks for the isAdditionalFlowStep implementation! That really helped!

[sei-yhindka]

@intrigus-lgtm @smowton Suppose that I modify the struct definition like so:

struct nested {
        uint8_t id;
};

struct status_msg_t {
        uint8_t tx;
        uint8_t status;
        struct nested;
};

Also suppose that there is some code that is accessing the struct like so:

status.nested.id

How can I modify the isAdditionalFlowStep predicate to include an edge from nested to id? I tried to modify the predicate like so but it did not produce any different results:

predicate isAdditionalFlowStep(DataFlow::Node node1, DataFlow::Node node2) 
    {
        exists(FieldAccess fa |

            // check node2 is the FieldAccess
            node2.asExpr() = fa

            and (

                // check node1 is a direct parent
                node1.asExpr() = fa.getQualifier()

                // or check node1 is an indirect parent
                or node1.asIndirectExpr() = fa.getQualifier()

            )

            and fa.getQualifier().getType().(UserType).hasQualifiedName("", "status_msg_t")

        )
    }