Polynima: Practical Hybrid Recompilation for Multithreaded Binaries

The maintenance of software distributed in its binary form can become challenging over time, due to the lack of vendor support or obsolete build environments. This can be costly when dealing with critical security vulnerabilities that are difficult to fix on a binary level. Moreover, advances in compiler technologies of the past decades remain unavailable to the users of such legacy binaries for performing optimizations and transformations. Binary recompilers aim to bridge this divide by "lifting" binary executables to compilerlevel intermediate representations (IR) and "lowering" them back again. But, current recompilers fail on that promise as they rely on unsound heuristics or impose high tracing overheads. Crucially, no existing recompiler addresses the specific challenges imposed by multithreaded programs that are ubiquitous in the modern software space.

To address these challenges, we present Polynima, a binary recompiler that supports the lifting and recompilation of x86/x64 multithreaded binaries while introducing a moderate 1.23x slowdown. We propose a hybrid control flow recovery approach that combines the benefits of static and dynamic techniques while providing an efficient strategy to handle unknown paths. Polynima enables the use of the rich LLVM compiler ecosystem to fix and improve legacy multithreaded binaries, which we demonstrate by mitigating a critical synchronization issue in a FTP server binary. We also leverage its functional IR to introduce a novel dynamic analysis to detect implicit synchronization primitives in binaries, which we use to further improve performance of the output. Finally, we evaluate the generality and correctness of