Expensive Tasks in CodeQL

[ppashakhanloo]

What are the most expensive tasks (queries/vulnerabilities/etc.) that CodeQL deals with? Global taint tracking is one example. Are there more?

[tausbn]

This is a very broad question (and it depends on the definition of "expensive"), but yes, global data flow and taint tracking is certainly one of the more expensive parts of the analysis. Moreover, each queries essentially calculates its own variant of global data flow (since the sources and sinks and additional taint steps may be specific to that query).

Another part that is expensive (and disjoint from global data flow) are the queries that have to do with detecting ReDoS attacks (e.g. for JavaScript, Python, and Ruby).

Finally, although a single global data flow may be expensive, in many cases this is dwarfed by some of the shared calculations that take place. For interpreted languages like Python and JavaScript, this includes calculating the call graph (which is then shared by all global data flow queries).

[ppashakhanloo]

Thank you for your thorough response. I agree with your point about the vagueness of "expensiveness". I mostly mean in terms of running time, i.e., "how long a developer has to wait to get the results of that specific analysis".

Is it fair to draw this conclusion based on what you said?:
If we ignore ReDoS attacks, there are no intra-procedural (local) tasks that are expensive?

[tausbn]

If we ignore ReDoS attacks, there are no intra-procedural (local) tasks that are expensive?

I would say that that is more or less a fair conclusion to draw. Purely locally, the most expensive task is probably calculating the relevant SSA variables, in order to infer local definitions and uses. Some languages also do things like synthesising additional AST nodes, and creating the control-flow graph (with things like splitting, pruning, and loop unrolling) based on the AST, and this also takes up some time even if it is a purely local task.

(I should also say that if you have a function with, say, 100,000 lines of code, then even such a local analysis could still take a non-negligible amount of time!)