Execution fails for sufficiently large programs

[JCRPaquin]

I was analyzing a 50MB executable and the analysis failed after ~18 hours. Analysis required ~50GB max heap size to maintain a stable state, with the vast majority of time spent in JGraphT's path enumeration code. I get the feeling that TypeFlow's propagation may be O(n^2) or similar, making it unsuitable for sufficiently large binaries.

Perhaps there's a way to re-write the code to only propagate from each graph node once, rather than enumerating overlapping paths? I haven't seriously looked at the code to determine the viability of the idea.

TypeFlow version: main branch
Ghidra version: 12.0
Java version: 25, OpenJDK

---

Ultimately the script failed with an OOM, detailed below:

Required array length 2147483639 + 135372 is too large
java.lang.OutOfMemoryError: Required array length 2147483639 + 135372 is too large
	at java.base/jdk.internal.util.ArraysSupport.hugeLength(ArraysSupport.java:914)
	at java.base/jdk.internal.util.ArraysSupport.newLength(ArraysSupport.java:907)
	at java.base/java.lang.AbstractStringBuilder.newCapacity(AbstractStringBuilder.java:344)
	at java.base/java.lang.AbstractStringBuilder.ensureCapacityNewCoder(AbstractStringBuilder.java:276)
	at java.base/java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:650)
	at java.base/java.lang.StringBuilder.append(StringBuilder.java:179)
	at java.base/java.lang.StringBuilder.append(StringBuilder.java:173)
	at java.base/java.util.AbstractMap.toString(AbstractMap.java:529)
	at java.base/java.util.Formatter$FormatSpecifier.printString(Formatter.java:3292)
	at java.base/java.util.Formatter$FormatSpecifier.print(Formatter.java:3170)
	at java.base/java.util.Formatter.format(Formatter.java:2761)
	at java.base/java.util.Formatter.format(Formatter.java:2698)
	at java.base/java.lang.String.format(String.java:4455)
	at typeforge.base.dataflow.TFG.TypeFlowPathManager.tryMergeLayoutFormSamePathsForward(TypeFlowPathManager.java:100)
	at typeforge.base.dataflow.solver.LayoutPropagator.processAllGraphsFirstPass(LayoutPropagator.java:95)
	at typeforge.base.dataflow.solver.LayoutPropagator.run(LayoutPropagator.java:32)
	at typeforge.base.dataflow.solver.InterSolver.typeHintPropagation(InterSolver.java:237)
	at typeforge.analyzer.TypeAnalyzer.run(TypeAnalyzer.java:155)
	at TypeForge.run(TypeForge.java:56)
	at ghidra.app.script.GhidraScript.executeNormal(GhidraScript.java:460)
	at ghidra.app.script.GhidraScript.doExecute(GhidraScript.java:314)
	at ghidra.app.script.GhidraScript.execute(GhidraScript.java:290)
	at ghidra.app.plugin.core.script.RunScriptTask.run(RunScriptTask.java:46)
	at ghidra.util.task.Task.monitoredRun(Task.java:134)
	at ghidra.util.task.TaskRunner.lambda$startTaskThread$0(TaskRunner.java:106)
	at java.base/java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1090)
	at java.base/java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:614)
	at java.base/java.lang.Thread.run(Thread.java:1474)

[JCRPaquin]

I'm also running the same binary through BTIGhidra to see how long that takes. It was also running into memory issues, but I've since upgraded to a higher capacity VM. Will comment back with results from that.

[JCRPaquin]

BTIGhidra fails to import the project due to missing storage for some proc arguments. Likely TypeForge just avoids those nodes (marks them as evil?). Might need to make/find an extra analysis pass to infer the storage for those args.

I'll look into alternative methods of type propagation after I have the rest of my TypeForge PRs up.

[noobone123]

Thank you so much for the testing!
A 50MB binary is actually quite massive (about half the size of a Linux kernel).
When performing whole-program analysis, I believe hitting Out-of-Memory (OOM) issues might be inevitable at this scale. Though, of course, there is always room for optimization.
Perhaps for binaries of this size, we could consider an alternative approach: instead of a full whole-program analysis, we could focus on targeted analysis of specific variables within certain functions (e.g., limiting the scope to within 10 function calls). This might provide better support for large-scale binaries.

In my experience, while $O(n^2)$ complexity is generally considered acceptable for program analysis algorithms, there are certainly further optimization opportunities we can explore.