Performances / accuracy of Recursion query

[DarkaMaul]

Trying to debug some performance issues following #14 (comment)

Testing setup:

Command:

codeql database analyze --rerun --threads=-1 codeqldb-elasticsearch-817 java/src/security/Recursion/Recursion.ql --format=sarif-latest --output=recursion.sarif

Test on elasticsearch codebase version 8.17 ( I generated the DB myself).

Test 1

Without isBarrierOut: 52s

Test 2

With isBarrierOut: none() : 51.8s
Idea: Does adding isBarrierOut change anything?

Test 3

Warning: wrong predicate

Idea: Check that accessing the state is not too costly

  predicate isBarrierOut(DataFlow::Node node, FlowState state) {
     node.asExpr().(MethodCall).getCallee().getName() = state.getName()
  }

Execution time: 34s

Test 4

Idea: String comparison

predicate isBarrierOut(DataFlow::Node node, FlowState state) {
  node.asExpr().(MethodCall).getCallee().getName() > state.getName()
}

Execution time: Timeout (+ 5min)

Test 5

Warning: wrong predicate

Idea: String comparison is expensive, use integers

  predicate isBarrierOut(DataFlow::Node node, FlowState state) {
    node.asExpr().(MethodCall).getCallee().getLocation().getStartLine() = state.getLocation().getStartLine()
  }
}

Execution time: Timeout (+ 5min)

Test 6

Idea: not multiplying methods and merge barrier function

  predicate isBarrier(DataFlow::Node node, FlowState state) {
    exists(MethodCall ma |
      ma = node.asExpr() and
      (
        exists(Expr e | e = ma.getAnArgument() and e instanceof ParameterOperation) or
        ma.getCaller().getName() > state.getName()
      )
    )
  }

Execution time: Timeout (+ 5min)

[evandowning]

This query also didn't find this recursion bug: NationalSecurityAgency/ghidra#9120

Commit: https://github.com/NationalSecurityAgency/ghidra/tree/08d4fcba59f0749f3e8584720aaa3c5f9342483f

Reproducing:

codeql database create database-ghidra.db --language=java -s ~/Downloads/ghidra/
codeql database analyze database-ghidra.db --format=sarif-latest --output=./ghidra.sarif -- trailofbits/java-queries

[DarkaMaul]

Ok I've triaged this with Claude help.

The query uses node.asExpr().(MethodCall) inside both isSource and isSink. Java's CodeQL dataflow library does not create a DataFlow::Node for expressions whose value is void so there is no value to flow. Empirically confirmed with a probe over the test database.

The problem is the fix if we want to keep the path query because wee need to keep a DataFlow::Node but we must anchor it somehow differently... I have not yet found a working solution.