endless loop of building ControlFlowSensitiveDFGPass when parsing a java file

[z2Z6]

Hi, Recently, I met with a file whose CPG can't be built successfully, because endless loop occured in ControlFlowSensitiveDFGPass when parsing it. The file is Runtime.java in https://github.com/RaiMan/SikuliX1/archive/refs/tags/1.1.3.zip

dump infomation(similar content in several times)

"ForkJoinPool.commonPool-worker-19" #25 daemon prio=5 os_prio=0 cpu=269812.50ms elapsed=272.34s tid=0x0000019868093000 nid=0x616c runnable  [0x0000008290cfd000]
   java.lang.Thread.State: RUNNABLE
        at de.fraunhofer.aisec.cpg.passes.ControlFlowSensitiveDFGPass.worklistHasSimilarPair(ControlFlowSensitiveDFGPass.kt:237)
        at de.fraunhofer.aisec.cpg.passes.ControlFlowSensitiveDFGPass.handleFunction(ControlFlowSensitiveDFGPass.kt:216)
        at de.fraunhofer.aisec.cpg.passes.ControlFlowSensitiveDFGPass.handle(ControlFlowSensitiveDFGPass.kt:72)
        at de.fraunhofer.aisec.cpg.passes.ControlFlowSensitiveDFGPass$$Lambda$784/0x00000008004f4c40.accept(Unknown Source)
        at de.fraunhofer.aisec.cpg.helpers.SubgraphWalker$IterativeGraphWalker.lambda$iterate$1(SubgraphWalker.java:366)
        at de.fraunhofer.aisec.cpg.helpers.SubgraphWalker$IterativeGraphWalker$$Lambda$741/0x0000000800428c40.accept(Unknown Source)
        at java.util.ArrayList.forEach(java.base@11.0.7/ArrayList.java:1540)
        at de.fraunhofer.aisec.cpg.helpers.SubgraphWalker$IterativeGraphWalker.iterate(SubgraphWalker.java:366)
        at de.fraunhofer.aisec.cpg.passes.ControlFlowSensitiveDFGPass.accept(ControlFlowSensitiveDFGPass.kt:59)
        at de.fraunhofer.aisec.cpg.passes.ControlFlowSensitiveDFGPass.accept(ControlFlowSensitiveDFGPass.kt:47)
        at de.fraunhofer.aisec.cpg.TranslationManager.analyze$lambda$2(TranslationManager.kt:102)
        at de.fraunhofer.aisec.cpg.TranslationManager$$Lambda$150/0x000000080024f440.get(Unknown Source)
        at java.util.concurrent.CompletableFuture$AsyncSupply.run(java.base@11.0.7/CompletableFuture.java:1700)
        at java.util.concurrent.CompletableFuture$AsyncSupply.exec(java.base@11.0.7/CompletableFuture.java:1692)
        at java.util.concurrent.ForkJoinTask.doExec(java.base@11.0.7/ForkJoinTask.java:290)
        at java.util.concurrent.ForkJoinPool$WorkQueue.topLevelExec(java.base@11.0.7/ForkJoinPool.java:1020)
        at java.util.concurrent.ForkJoinPool.scan(java.base@11.0.7/ForkJoinPool.java:1656)
        at java.util.concurrent.ForkJoinPool.runWorker(java.base@11.0.7/ForkJoinPool.java:1594)
        at java.util.concurrent.ForkJoinWorkerThread.run(java.base@11.0.7/ForkJoinWorkerThread.java:177)

configuration: v5.1.0

new TranslationConfiguration.Builder()
                .sourceLocations(new File(filename))
                .defaultPasses()
                .defaultLanguages()
                .build();

For ControlFlowSensitiveDFGPass.kt, worklist.size in func handleFunction keeps increasing when parsing Runtime.java, which causes endless loop. I guess the func worklistHasSimilarPair need to relax restrictions, which can avoid to add some similar pairs to worklist frequently.

[KuechA]

Hi, please check #1024 and let us know if it resolves the issue. I think it works in this specific case but as I say in the PR, it may not fix related problems.

[z2Z6]

Hi, please check #1024 and let us know if it resolves the issue. I think it works in this specific case but as I say in the PR, it may not fix related problems.

Thanks for quick fix. I test some files with solution #1024, it fixed most of endless loop problems I now encounter, but still leave one as above. the file is ApplicationMaster.java in https://github.com/Qihoo360/XLearning/blob/master/src/main/java/net/qihoo/xlearning/AM/ApplicationMaster.java. the worklist.size keeps fluctuating, it seems to never decrease to zero.

[KuechA]

That was exactly what I expected... I changed the PR a bit and the sample you sent should work with the new changes. Let me know if you encounter any other issues

[z2Z6]

That was exactly what I expected... I changed the PR a bit and the sample you sent should work with the new changes. Let me know if you encounter any other issues

All endless loop problems I now encounter are solved with new changes in #1024. There is no other new issue at present.

[z2Z6]

Hi @KuechA , There is a file(KDC.java) which has the same problem. It may need to relax the worklistHasSimilarPair condition further.

[KuechA]

Hi, #1088 should solve the problem for the mentioned file. If you encounter more problems, please reopen the issue or create a new one so we can keep track of the status more easily and your comments don't get lost ;)