Regex related queries causing out of memory exceptions?

[dotasek]

After one commit, our CodeQL github action began timing out. I could use some help finding out how to debug what specifically is causing the issue.

https://github.com/hapifhir/org.hl7.fhir.core/actions/runs/5509181979

As far as I can tell, this is the code diff at which these timeouts began:

hapifhir/org.hl7.fhir.core@do-20230705-codeql-d525281...do-20230710-codeql-284ad1c

After some experimentation with the CLI locally, I found three Regex related queries that were all running out of memory, and temporarily removed them:

java/polynomial-redos
java/redos
java/overly-large-range

They all produced issues such as the following:

2023-07-10 16:31:04] [ERROR] Exception collected asynchronously; saving it while cancelling everything
                              java.lang.OutOfMemoryError: Java heap space: failed reallocation of scalar replaced objects
[2023-07-10 16:31:04] [WARN] Evaluation of /Users/david.otasek/.codeql/packages/codeql/java-queries/0.6.4/Security/CWE/CWE-730/PolynomialReDoS.ql terminated abnormally.
                             java.util.concurrent.CompletionException: Query evaluation ran out of Java heap (Java heap maximum: 1228 MiB, Off-heap arrays maximum: 2048 MiB).
                             (eventual cause: OutOfMemoryError "Java heap space")
                             	at java.base/java.util.concurrent.CompletableFuture.encodeThrowable(Unknown Source)
                             	at java.base/java.util.concurrent.CompletableFuture.completeThrowable(Unknown Source)
                             	at java.base/java.util.concurrent.CompletableFuture.uniExceptionally(Unknown Source)
                             	at java.base/java.util.concurrent.CompletableFuture$UniExceptionally.tryFire(Unknown Source)
                             	at java.base/java.util.concurrent.CompletableFuture.postComplete(Unknown Source)
                             	at java.base/java.util.concurrent.CompletableFuture.completeExceptionally(Unknown Source)
                             	at com.semmle.inmemory.scheduler.CapstoneTask$1.doWork(CapstoneTask.java:97)
                             	at com.semmle.util.concurrent.RateLimitedAction.wokenUp(RateLimitedAction.java:76)
                             	at com.semmle.util.concurrent.RateLimitedAction.access$300(RateLimitedAction.java:15)
                             	at com.semmle.util.concurrent.RateLimitedAction$BackgroundThread.run(RateLimitedAction.java:196)
                             Caused by: com.semmle.util.ql.FailedQueryError: Query evaluation ran out of Java heap (Java heap maximum: 1228 MiB, Off-heap arrays maximum: 2048 MiB).
                             (eventual cause: OutOfMemoryError "Java heap space")
                             	at com.semmle.inmemory.MemoryBackend$QueryOrchestrator.handleException(MemoryBackend.java:547)
                             	... 8 common frames omitted
                             Caused by: java.lang.OutOfMemoryError: Java heap space
                             	at java.base/java.util.HashMap.resize(Unknown Source)
                             	at java.base/java.util.HashMap.computeIfAbsent(Unknown Source)
                             	at com.semmle.inmemory.caching.byhash.evict.Evictor.lambda$fullMemoryScan$9(Evictor.java:867)
                             	at com.semmle.inmemory.caching.byhash.evict.Evictor$$Lambda$746/0x00000008003d4958.weHaveItem(Unknown Source)
                             	at com.semmle.inmemory.caching.byhash.memory.InMemoryStore.lambda$scanEverything$1(InMemoryStore.java:160)
                             	at com.semmle.inmemory.caching.byhash.memory.InMemoryStore$$Lambda$747/0x00000008003d4b80.accept(Unknown Source)
                             	at java.base/java.util.concurrent.ConcurrentHashMap.forEach(Unknown Source)
                             	at com.semmle.inmemory.caching.byhash.memory.InMemoryStore.scanEverything(InMemoryStore.java:158)
                             	at com.semmle.inmemory.caching.byhash.evict.Evictor.fullMemoryScan(Evictor.java:866)
                             	at com.semmle.inmemory.caching.byhash.evict.Evictor.traceMemoryImportances(Evictor.java:902)
                             	at com.semmle.inmemory.caching.byhash.evict.Evictor.reduceMemoryUsage(Evictor.java:424)
                             	at com.semmle.inmemory.alloc.MemoryManager.ensureSpace(MemoryManager.java:295)
                             	at com.semmle.inmemory.alloc.MemoryManager.ensureHeapSpace(MemoryManager.java:275)
                             	at com.semmle.inmemory.alloc.MemoryManager.notifyHeapAllocation(MemoryManager.java:427)
                             	at com.semmle.inmemory.alloc.LocalAllocationTracker.notifyHeapAllocation(LocalAllocationTracker.java:26)
                             	at com.semmle.inmemory.alloc.JavaAllocationTracker.notifyIntArrayAllocation(JavaAllocationTracker.java:30)
                             	at com.semmle.inmemory.alloc.JavaAllocationTracker.allocIntArray(JavaAllocationTracker.java:18)
                             	at com.semmle.inmemory.relations.cbtree.AbstractNode.<init>(AbstractNode.java:66)
                             	at com.semmle.inmemory.relations.cbtree.Leaf.<init>(Leaf.java:15)
                             	at com.semmle.inmemory.relations.cbtree.Leaf.newNode(Leaf.java:30)
                             	at com.semmle.inmemory.relations.cbtree.Leaf.newNode(Leaf.java:7)
                             	at com.semmle.inmemory.relations.cbtree.AbstractNode.split(AbstractNode.java:236)
                             	at com.semmle.inmemory.relations.cbtree.Leaf.splitRight(Leaf.java:130)
                             	at com.semmle.inmemory.relations.cbtree.Branch.insert(Branch.java:128)
                             	at com.semmle.inmemory.relations.cbtree.Branch.insert(Branch.java:70)
                             	at com.semmle.inmemory.relations.cbtree.Branch.insert(Branch.java:66)
                             	at com.semmle.inmemory.relations.cbtree.CBTree.insert(CBTree.java:65)
                             	at com.semmle.inmemory.relations.writers.BTreeRelationWriter$WritingSink.flush(BTreeRelationWriter.java:142)
                             	at com.semmle.inmemory.relations.writers.BTreeRelationWriter$WritingSink.addOneTuple(BTreeRelationWriter.java:126)
                             	at com.semmle.inmemory.relations.writers.AdaptiveRelationWriter.addTupleToUnsorted(AdaptiveRelationWriter.java:383)
                             	at com.semmle.inmemory.relations.writers.AdaptiveRelationWriter$1.addBatch(AdaptiveRelationWriter.java:309)
                             	at com.semmle.inmemory.pipeline.RelationWritingStep$RelationWritingState.processBatch(RelationWritingStep.java:77)

The commit is largely auto-generated code, so it's difficult to figure out what specifically is causing the issue.

The amount of code that was added doesn't seem to be excessive:

New code:
|                   Metric                   | Value  |
+--------------------------------------------+--------+
| Total lines of Java code in the database   | 695738 |
| Total lines of Kotlin code in the database |      0 |

Old code:
|                   Metric                   | Value  |
+--------------------------------------------+--------+
| Total lines of Kotlin code in the database |      0 |
| Total lines of Java code in the database   | 692859 |

I'm able to run single instances of these queries, and they either run out of memory, or they do not resolve after many hours:

codeql query run --database ~/code-ql-database  --output ~/codeql_results.json --threads 20 --ram 11000 /Users/me/.codeql/packages/codeql/java-queries/0.6.4/Security/CWE/CWE-020/OverlyLargeRange.ql 

[jketema]

Hi @dotasek, Thanks for your question. We rolled out a new version of CodeQL today (2.14.0), would you mind re-trying with that version? I don't think this will actually solve the problem, but I'd like to check this before looping in someone from the relevant engineering team.

[dotasek]

@jketema I have triggered the code check action on the latest version of our repo with debug enabled:

https://github.com/hapifhir/org.hl7.fhir.core/actions/runs/5576139508

The logs indicate that it is using the new version (2.14.0)

17T13:18:14.216Z","status":"success","testing_environment":"","runner_os":"Linux","action_version":"2.20.4","completed_at":"2023-07-17T13:18:53.769Z","matrix_vars":"{\n  \"language\": \"java\",\n  \"module\": \"org.hl7.fhir.r5\"\n}","runner_arch":"X64","codeql_version":"2.14.0","tools_input":"","tools_resolved_version":"2.14.0","tools_source":"DOWNLOAD","workflow_languages":"java","disable_default_queries":"","languages":"java","ml_powered_javascript_queries":"false","paths":"","paths_ignore":"","queries":"","trap_cache_languages":"","trap_cache_download_size_bytes":0,"trap_cache_download_duration_ms":902,"tools_download_duration_ms":2946,"tools_feature_flags_valid":true}

[dotasek]

@jketema It looks like the process no longer times out, but instead reports the same out of memory exception: OutOfMemoryError "Java heap space"

https://github.com/hapifhir/org.hl7.fhir.core/actions/runs/5576139508/jobs/10187005314

That looks like what was happening with local execution.

[dotasek]

@jketema I actually tried that on my local machine (set to 11GB) and although it doesn't fail due to out of memory exceptions, it never terminated after 12+ ours. I COULD leave it running over the weekend and see if it completes with any interesting information.

But in general going from 1GB to 11GB without any termination has the smell of some specific condition outside of just a slightly larger codebase.

[jketema]

Likely it's taking such a long time because it's using the disk cache, because it doesn't have enough memory. You probably need to give it a lot more.

In any case, I let the responsible team know, and they will have a look.

[jketema]

The responsible team has opened an internal issue to investigate this further.

[erik-krogh]

This issue should be fixed with the following change: #13916

The fix should appear in a new release in a few weeks.

[dotasek]

@jketema @erik-krogh thank you! Looking forward to retrying those tests.

[dotasek]

This appears to be live via the GitHub action, and CodeQL now scans through all tests. Thank you very much!