Infinite recursion in deserialization of CPG

[JulianSchuette]

When deserializing a fairly complex project, the OGM deserialization in OverflowDatabase gets into an infinite recursion of creating edges for vertices, leading to a StackOverflowError.

Steps to reproduce:

• git clone https://github.com/11112222/WebGoat5_0_32555lines.git webgoat
• build/install/codyze/bin/codyze -c -s webgoat/WebGoat5.0/JavaSource/ -m src/dist/mark

Result:

java.util.concurrent.ExecutionException: java.lang.StackOverflowError
	at java.base/java.util.concurrent.CompletableFuture.reportGet(CompletableFuture.java:395)
	at java.base/java.util.concurrent.CompletableFuture.get(CompletableFuture.java:2093)
	at de.fraunhofer.aisec.analysis.Main.call(Main.java:84)
	at de.fraunhofer.aisec.analysis.Main.call(Main.java:27)
	at picocli.CommandLine.executeUserObject(CommandLine.java:1783)
	at picocli.CommandLine.access$900(CommandLine.java:145)
	at picocli.CommandLine$RunLast.handle(CommandLine.java:2141)
	at picocli.CommandLine$RunLast.handle(CommandLine.java:2108)
	at picocli.CommandLine$AbstractParseResultHandler.execute(CommandLine.java:1975)
	at picocli.CommandLine.execute(CommandLine.java:1904)
	at de.fraunhofer.aisec.analysis.Main.main(Main.java:54)
Caused by: java.lang.StackOverflowError
	at java.base/java.util.concurrent.ConcurrentHashMap.get(ConcurrentHashMap.java:936)
	at org.ehcache.sizeof.util.WeakIdentityConcurrentMap.get(WeakIdentityConcurrentMap.java:91)
	at org.ehcache.sizeof.ObjectGraphWalker.shouldWalkClass(ObjectGraphWalker.java:248)
	at org.ehcache.sizeof.ObjectGraphWalker.walk(ObjectGraphWalker.java:170)
	at org.ehcache.sizeof.SizeOf.deepSizeOf(SizeOf.java:71)
	at org.ehcache.impl.internal.sizeof.DefaultSizeOfEngine.sizeof(DefaultSizeOfEngine.java:52)
	at org.ehcache.impl.internal.store.heap.OnHeapStore.getSizeOfKeyValuePairs(OnHeapStore.java:982)
	at org.ehcache.impl.internal.store.heap.OnHeapStore.makeValue(OnHeapStore.java:1527)
	at org.ehcache.impl.internal.store.heap.OnHeapStore.makeValue(OnHeapStore.java:1514)
	at org.ehcache.impl.internal.store.heap.OnHeapStore.newUpdateValueHolder(OnHeapStore.java:1444)
	at org.ehcache.impl.internal.store.heap.OnHeapStore.lambda$put$6(OnHeapStore.java:352)
	at org.ehcache.impl.internal.concurrent.ConcurrentHashMap.compute(ConcurrentHashMap.java:1958)
	at org.ehcache.impl.internal.store.heap.SimpleBackend.compute(SimpleBackend.java:101)
	at org.ehcache.impl.internal.store.heap.OnHeapStore.put(OnHeapStore.java:334)
	at org.ehcache.core.Ehcache.doPut(Ehcache.java:94)
	at org.ehcache.core.EhcacheBase.put(EhcacheBase.java:189)
	at de.fraunhofer.aisec.crymlin.connectors.db.OverflowDatabase.getSuperclasses(OverflowDatabase.java:780)
	at de.fraunhofer.aisec.crymlin.connectors.db.OverflowDatabase.createVertex(OverflowDatabase.java:467)
	at de.fraunhofer.aisec.crymlin.connectors.db.OverflowDatabase.connect(OverflowDatabase.java:652)
	at de.fraunhofer.aisec.crymlin.connectors.db.OverflowDatabase.createEdges(OverflowDatabase.java:631)
	at de.fraunhofer.aisec.crymlin.connectors.db.OverflowDatabase.createVertex(OverflowDatabase.java:483)
	at de.fraunhofer.aisec.crymlin.connectors.db.OverflowDatabase.connect(OverflowDatabase.java:652)
	at de.fraunhofer.aisec.crymlin.connectors.db.OverflowDatabase.connectAll(OverflowDatabase.java:674)
	at de.fraunhofer.aisec.crymlin.connectors.db.OverflowDatabase.createEdges(OverflowDatabase.java:626)
	at de.fraunhofer.aisec.crymlin.connectors.db.OverflowDatabase.createVertex(OverflowDatabase.java:483)
	at de.fraunhofer.aisec.crymlin.connectors.db.OverflowDatabase.connect(OverflowDatabase.java:652)
        ...

[JulianSchuette]

Increasing stack size from 1MB to 10MB (VM arg -Xss10M) avoids the error. This is even more of a problem, as it means that this is not a buggy infinite recursion but simply that the CPG is too deep to traverse recursively. The code must be re-written to an iterative approach.

[Masrepus]

I see, that's what I suspected. It's basically the same behavior that we had when the passes were still recursive.

[oxisto]

Can you check, whether this is still a problem with the recent version of the CPG. It might have been fixed by Fraunhofer-AISEC/cpg#213 which closed Fraunhofer-AISEC/cpg#185

[fwendland]

Still a problem. Our own OverflowDatabase saves the graph recursively. This can overflow the stack.

[oxisto]

It seems that those creep up again in recent tests

RealBotanTest > testCorrecKeySize() FAILED
    java.util.concurrent.ExecutionException at RealBotanTest.java:39
        Caused by: java.lang.StackOverflowError at Preconditions.java:-1

RealBotanTest > testSimple() FAILED
    java.util.concurrent.ExecutionException at RealBotanTest.java:26
        Caused by: java.lang.StackOverflowError at NodeRef.java:-1

[oxisto]

Looks like this is still an issue to some degree:

RealBCTest > testSimple() FAILED
    java.util.concurrent.ExecutionException at RealBCTest.java:20
        Caused by: java.lang.StackOverflowError at Class.java:1550

[oxisto]

It seems some other bug, not related to graph serialisation, closing this one.