What predicate will be evaluated in a query?

[iiins0mn1a]

If I am running this query, and what predicate will be evaluated?

predicate A( ... ) { ... }

predicate B( ... ) { ... }

from ...
where A( ... )
select ...

I thought that only predicate A will be evaluated, before. But while checking the log, I find that a non-related predicate B is evaluated too.

Is this normal? In a more specific scenario, B is a predicate called by isAdditionalTaintStep in TaintTracking::Configuration, and A is a predicate about TaintTracking3::Configuration, calling some gadget predicates in the same lib with predicate B. They are supposed to be different, non-relavant.

[d10c]

Hi @iiins0mn1a. In general, any predicate that is (directly or indirectly) demanded by your query will be evaluated.

For example, if the query were something like from int i where A(i) select i, and there is no call path from A to B, then B should not be evaluated.

But in this case, if this is a standard taint tracking query, and your TaintTracking::Configuration subclass calls B from its isAdditionalTaintStep predicate, then that would explain why B is being evaluated. Is that the case?

Another possibility is if you have another query predicate imported into your .ql file, such as a PathGraph module, which exports edges, nodes, and subpaths predicates that do call into your configuration class. All query predicates in the top-level scope of a .ql file are evaluated alongside the from ... where ... select ... query.

To be extra sure of where your B predicate is used, you can follow its transitive uses in the evaluator log (Query History panel > right click a query run > menu item Show Evaluator Log ...), or even in DIL ("datalog intermediate language", via menu item View DIL, which you may find more readable).

[iiins0mn1a]

First of all, appreciate~ and hi @d10c !

Yes, it's standard taint tracking query.

TaintTracking::Configuration subclass calls B from its isAdditionalTaintStep predicate, then that would explain why B is being evaluated. Is that the case?

Actually there is no call path to TaintTracking::Configuration, my A predicate only uses TaintTracking3::Configuration, that's why I'm a little shocked...

Another possibility is if you have another query predicate imported into your .ql file, such as a PathGraph module, which exports edges, nodes, and subpaths predicates that do call into your configuration class. All query predicates in the top-level scope of a .ql file are evaluated alongside the from ... where ... select ... query.

Yes, it's a path explaination query. I coded import DataFlow3::PathGraph in my top .ql. Will this module trigger a subclass evaluation of another module TaintTranking::Configuration?

I'm running these queries with codeql-cli, and in the evaluator log, if i am not mistaken, I find the compiled version of predicate B in
a predicateName field, then I search for its caller, but no any predicate has a dependencies field with B contained.

Is this mean that, there is no call path to predicate B at all?

And this is the evaluator log of predicate B, actually I know exactly that predicate B is a predicate would ruin everything XD.
It's a cartesian product from two huge sets, and it perfroms even worse on my linux kernel database, literally, catastrophe.

{
  "time" : "2023-06-14T13:23:20.693Z",
  "type" : "PREDICATE_STARTED",
  "eventId" : 141061,
  "raHash" : "e83bb6gv775sskeb7rpm0gtoa22",
  "predicateName" : "m#functionpointer#fa913283::sameType#2#bb",
  "appearsAs" : {
    "m#functionpointer#fa913283::sameType#2#bb" : [ 25 ]
  },
  "predicateType" : "SIMPLE_INTENSIONAL",
  "position" : "<somewhere>/lib/functionpointer.qll:100,1-107,2",
  "ra" : {
    "pipeline" : [
      "    {2} r1 = JOIN Call#39248e3c::ExprCall::getArgument#1#dispred#fff_12#join_rhs WITH project#Function#65d29029::Function::getParameter#1#dispred#fff ON FIRST 1 OUTPUT Lhs.1, Rhs.1",
      "    return r1"
    ]
  },
  "dependencies" : {
    "Call#39248e3c::ExprCall::getArgument#1#dispred#fff_12#join_rhs" : "f0eb722eb2kukcl09edtfbolbq4",
    "project#Function#65d29029::Function::getParameter#1#dispred#fff" : "31f5bea7c318jot87mgpl4m5386"
  },
  "queryCausingWork" : 10
}

And some related evaluate summary:

[2023-06-13 18:37:47] Evaluated non-recursive predicate m#functionpointer#fa913283::sameType#2#bb@e83bb6gv in 16563512ms (evaluation was halted due to CatastrophicError).
Evaluated relational algebra for predicate m#functionpointer#fa913283::sameType#2#bb@e83bb6gv with tuple counts:
        27938857000  ~4%    {2} r1 = JOIN Call#39248e3c::ExprCall::getArgument#1#dispred#fff_12#join_rhs WITH project#Function#65d29029::Function::getParameter#1#dispred#fff ON FIRST 1 OUTPUT Lhs.1, Rhs.1
                            return r1

27938857000, bomb!

(failed) 276m4s |       |              | m#functionpointer#fa913283::sameType#2#bb@e83bb6gv

And of course it failed. This is why I didn't call it. But it still being evaluated, I don't know the reason still.

[iiins0mn1a]

Sincerely sorry for my dumb.

A class I use in the call path of predicate A is defined by TaintTranking::Configuration, and this is why the predicate B is evaluated. Really sorry for wasting your time. I should double check before creating a new discussion.

Sorry for disturbing, and thank you for your answering.

[d10c]

No worries :) Glad to see it's resolved.