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?

[hvitved]

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.

The QL compiler actually does these kinds of transformations (referred to as "magic sets optimization"), but automatically applying constraints in cases like isSource and isSink is currently outside the scope of what is possible.

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

No; the problem is that it requires computing the entire data flow graph, which is not feasible.

[pruzko]

Apologies for the late reply.

it requires computing the entire data flow graph, which is not feasible

Or computing it lazily.

Either way, the matter is clear so thank you very much for your help.