Constraining DataFlow::ConfigSig sources and sinks inside the query, rather than in isSource/isSink

[pruzko]

Hi,

I am trying to determine whether a DataFlow::Node a globally flows into a DataFlow::Node b. This is typically done by defining a custom DataFlow::ConfigSig like this:

private module MyConfig implements DataFlow::ConfigSig {
    predicate isSource(DataFlow::Node n) {
        constrainSource(n)
    }
    predicate isSink(DataFlow::Node n) {
        constrainSink(n)
    }
}
private module MyFlow = DataFlow::Global<MyConfig>;
from DataFlow::Node a, DataFlow::node b
where MyFlow::flow(a, b)
select ...

The key point here is that the search space is constrained within isSource and isSink. This is what I do not want, instead I'd like to constrain the space within the query like so:

private module MyConfig implements DataFlow::ConfigSig {
    predicate isSource(DataFlow::Node n) {
        any()
    }
    predicate isSink(DataFlow::Node n) {
        any()
    }
}
private module AnyFlow = DataFlow::Global<MyConfig>;
from DataFlow::Node a, DataFlow::node b
where
    constrainSource(a) and constrainSink(b) and
    AnyFlow::flow(a, b)
select ...

In theory, both MyFlow and AnyFlow solve the same reachability problem over the same space. However, the second approach is prohibitively slow on real-sized applications (tested with CQL 2.22.1).

Please, is there a way to check flows only for nodes that are constrained in the where clause?

---

To provide more context, I'm writing a tool that identifies items that satisfy a set of (variable) constraints. Some constraints are structural and can be expressed with predicates (e.g., constrainSource/Sink in the example) but others are flow-related and must be handled with DataFlow::Global. I'm trying to define constraint primitives in an .qll library and then use those to generate the final query. I'd like the library to expose (and internally use) a "flowsTo" primitive, so that I can produce something like:

from DataFlow::Node n1, DataFlow::Node n2, DataFlow::Node n3
where
    someConstr(n1) and
    otherConstr(n2) and
    (yetAnotherConstr(n3) or thatConstr(n3)) and
    flowsTo(n1, n3) and not flowsTo(n1, n2)

I am looking for any working solution (e.g., transitively stepping the data-flow graph) that would allow me to factor out the flow logic into the library. I'm aware of that localFlowStep* trick, but I need to search globally. All help is greatly appreciated.

[hvitved]

Hi 👋

Constraining sources and sinks inside a data flow/taint tracking config module is indeed crucial for performance. The data flow library works by performing a set of reachability calculations ("which nodes can be reached from a source", "which nodes that can be reached from a source can reach a sink") before computing the actual data flow graph. So the short answer is that using isSource() { any() } or isSink() { any() } will not be able to scale.

[pruzko]

Thank you for your response.

I take it as there is no generic "flowsTo" primitive and defining sources and sinks in the configuration is inevitable. That said, I wonder if this is a design choice or there is a technical reason behind this. After all, all constraints (whether in isSink/Source or inside where) are known at compile time, so the compiler could infer the search space itself.

Also a follow-up, do you think that globalFlowStep* will appear in the future?