Filter result by number of steps in path

[Hug0Vincent]

Is it possible to filter path-based problem query results by the number of steps in the path from the source to the sink? I have numerous results, making it impossible to display them all in VSCode. I want to retain only those paths with a length of 30 steps or fewer. Is this feasible? In VSCode, the number of steps is displayed, but I'm unsure if I can directly filter this in my CodeQL query.

[Hug0Vincent]

I made this but is there a better way to do this ? Because it takes a lot of time on some databases. I tried to pass an integer as a parameter but I got some issues regarding inlining / recursion and constraints.

int pathLengthBetweenNodes(MyFlow::PathNode src, MyFlow::PathNode dst) {
  (result = 0 and src = dst)
  or
  exists(MyFlow::PathNode intermediate |
      intermediate.getASuccessor() = dst and
      result <= 42 and
      result = pathLengthBetweenNodes(src, intermediate) + 1
    )
}

module MyFlow = TaintTracking::Global<MyConfig>; // or DataFlow::Global<..>

from MyFlow::PathNode source, MyFlow::PathNode sink
where MyFlow::flowPath(source, sink)
pathLengthBetweenNodes(source, sink) <= 42
select sink.getNode(), source, sink, "Sample TaintTracking query"

[owen-mc]

The CodeQL query doesn't have any access to the path length. It doesn't actually construct any paths - this is done in a later step, before the results are shown in VS code. The closest thing that I can think of is that when using partial flow (where you specify the source but not the sink, or vice versa) you can specify some kind of length (I think it might be steps into function calls.) But using partial flow generally increases the number of results massively, so probably wouldn't help you.

Note that there are two slightly different things here: you might have lots of results, with one path each, or you might have one result with lots of paths. By default only 4 paths are constructed and shown for each result, though this can be adjusted. So I assume what you are seeing is lots of results. And you say that there are too many to show in VS code? Could you share more about what the query you are running is? Is it possible to apply some heuristic to reduce the number of results, other than path length?

[owen-mc]

Access path limit has this documentation: Gets a limit on the number of reads out of sources and number of stores into sinks. I believe this is pretty much what you said about object.Field1.ArrayElement.Field2.MapValue - limiting how long the access path that we keep track of is.

Field flow branch limit has this documentation: Gets the virtual dispatch branching limit when calculating field flow. I believe "field flow" here is "keeping track of the access path". If a particular call has too many possible callees then we do not follow any flow with access paths through it, as that would lead to a lot more possible flow to follow.

[Hug0Vincent]

Alright thank you so much for the explanation.

[owen-mc]

Another though: using local flow rather than a global data flow has a similar effect to limiting the path length. It isn't helpful if you want to find paths that don't stay in one function, though.

[hvitved]

As @owen-mc writes, we are not actually computing paths in QL, but only the graph from which paths are then derived by the CodeQL CLI. Attempting to restrict results based on path length in QL is probably a symptom that the query is simply too imprecise; that being said, if you still want to try it out, I suggest using the built-in shortestDistances primitive (see e.g.

codeql/shared/controlflow/codeql/controlflow/BasicBlock.qll

Line 341 in 5722084

shortestDistances(startsBB/1, intraBBSucc/2)(bbStart, cfn, i)

).

[Hug0Vincent]

I'll take a look thank you for all the information!