Virtualization-based obfuscation is the strongest defense available to malware: the original code is compiled into bytecode for a custom virtual machine, and the VM interpreter — itself obfuscated — executes it. Reversing requires understanding not just the code but the virtual machine that runs it.
Existing deobfuscation tools work on execution traces — they run the binary, record what the VM does, and reconstruct the original logic from the trace. This has three problems. Traces are path-dependent: they capture one execution path but miss others. Symbolic execution to explore all paths requires solving path constraints, which is NP-hard and doesn't scale. And the recovered code is not well-formed enough for decompilers to produce readable output.
PUSHAN avoids all three by using VPC-sensitive, constraint-free symbolic emulation. Instead of executing the binary and recording traces, it emulates the virtual machine symbolically without accumulating path constraints. The key move: it doesn't ask “is this path feasible?” — it recovers the complete control flow graph without ever testing satisfiability. The NP-hard problem is sidestepped, not solved.
The result: over 1,000 binaries deobfuscated, including VMProtect and Themida (commercial-strength obfuscators). The recovered code decompiles to readable C pseudocode — human-friendly enough that an LLM can further simplify it.
The structural insight: scalability came from removing a question, not answering it faster. Path satisfiability is NP-hard because it asks whether each path is possible. Constraint-free emulation asks only what paths exist, without testing each one. The complete CFG is recoverable without ever determining which paths are reachable.
(arXiv:2603.18355)