RecStruct: Recovering Nested Struct Types from Stripped Binaries via Stack-Driven Unification

Recovering composite data types from stripped binaries is critical for reverse engineering and vulnerability analysis. Existing approaches either rely on heavyweight decompilers with limited type reasoning, or employ expensive constraint solvers that fail to scale. While some methods can handle nested structures, they struggle with large real-world binaries due to prohibitive computational costs. We present RecStruct, a fast type recovery framework that reconstructs nested structures without dependence on any decompiler. RecStruct lifts binaries directly, performs flow-insensitive symbolic execution to reduce memory aliases, and introduces Stack-Driven Unification—a novel union-find algorithm that maintains an offset stack during traversal to merge types only when their nesting depths align. This enables precise recovery of recursive structures. We implement an end-to-end pipeline and evaluate it on 418 binaries comprising 744,770 functions, including benchmarks from prior work and large-scale programs such as QEMU and OpenSSL. Experimental results demonstrate competitive accuracy compared to existing tools, with substantial improvements in efficiency and scalability, enabling analysis of binaries that were previously intractable.