Regex related queries causing out of memory exceptions? #13752

dotasek · 2023-07-14T21:14:53Z

dotasek
Jul 14, 2023

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

Answered by erik-krogh

Aug 18, 2023

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

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

View full answer

jketema · 2023-07-14T23:35:46Z

jketema
Jul 14, 2023
Maintainer

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.

0 replies

dotasek · 2023-07-17T13:22:22Z

dotasek
Jul 17, 2023
Author

@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}

0 replies

dotasek · 2023-07-17T17:27:30Z

dotasek
Jul 17, 2023
Author

@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.

6 replies

dotasek Jul 18, 2023
Author

@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 Jul 18, 2023
Maintainer

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 Jul 19, 2023
Maintainer

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

erik-krogh Aug 18, 2023
Maintainer

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

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

Answer selected by dotasek

dotasek · 2023-08-18T14:27:21Z

dotasek
Aug 18, 2023
Author

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

0 replies

dotasek · 2023-09-01T18:03:34Z

dotasek
Sep 1, 2023
Author

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

0 replies

Regex related queries causing out of memory exceptions? #13752

Uh oh!

dotasek Jul 14, 2023

Replies: 5 comments · 6 replies

Uh oh!

jketema Jul 14, 2023 Maintainer

Uh oh!

dotasek Jul 17, 2023 Author

Uh oh!

dotasek Jul 17, 2023 Author

Uh oh!

dotasek Jul 18, 2023 Author

Uh oh!

Uh oh!

jketema Jul 18, 2023 Maintainer

Uh oh!

jketema Jul 19, 2023 Maintainer

Uh oh!

erik-krogh Aug 18, 2023 Maintainer

Uh oh!

dotasek Aug 18, 2023 Author

Uh oh!

dotasek Sep 1, 2023 Author

dotasek
Jul 14, 2023

Replies: 5 comments 6 replies

jketema
Jul 14, 2023
Maintainer

dotasek
Jul 17, 2023
Author

dotasek
Jul 17, 2023
Author

dotasek Jul 18, 2023
Author

jketema Jul 18, 2023
Maintainer

jketema Jul 19, 2023
Maintainer

erik-krogh Aug 18, 2023
Maintainer

dotasek
Aug 18, 2023
Author

dotasek
Sep 1, 2023
Author