Superset Disassembly:
Statically Rewriting x86 Binaries Without Heuristics
Erick Bauman, Zhiqiang Lin, Kevin W. Hamlen
University of Texas at Dallas
-
MULTIVERSE is a heuristic-free static rewriting framework that ensures total completeness and soundness by disassembling every possible byte offset.
It employs a brute-force superset disassembly strategy to recover all potential instructions and relies on mapping lookup mechanism to mediate all indirect control flow transfers (iCFTs). -
Limitations
-
Excessive Binary and Memory Bloat (Space Overhead)
By generating instruction sequences for every possible byte offset,
It increases the .newtext size by 4-5x and total binary size by up to 9x. -
Performance Degradation in Branch-Heavy Applications
Mapping Lookup for iCFTs introduces substantial latency.
The resulting average overhead of 60% is significantly higher
than that of heuristic-based rewriters or specialized hardening tools. -
Global Dependency and Interoperability Constraints
All shared libraries must be rewritten. This makes it difficult to interoperate with proprietary binary blobs, anti-debug protected libraries, or complex dynamically loaded modules (dlopen).
-
