Next Generation Virtualization-Based Obfuscators

Next Generation Virtualization-Based Obfuscators

Speakers: Tim Blazytko (Chief Scientist, Co-founder, emproof); Moritz Schloegel (Security Researcher, Ruhr University Bochum)

Conference: HITB Amsterdam

YouTube: https://www.youtube.com/watch?v=DRH0oRFvFiM

Overview

In the ever-escalating arms race between software obfuscation and deobfuscation, virtualization-based obfuscation (VBO) has long stood as a formidable defense mechanism. This talk, "Next Generation Virtualization-Based Obfuscators," delivered by Tim Blazytko, Chief Scientist and Co-founder of emproof, and Moritz Schloegel, a Security Researcher at Ruhr University Bochum, delves into the evolution of VBO, presenting a critical analysis of its current state and unveiling a new paradigm designed to counteract modern deobfuscation techniques. The speakers highlight that while existing VBO implementations have been significantly hardened, they are increasingly vulnerable to sophisticated automated attacks, necessitating a fundamental shift in design principles.

The core of their presentation introduces a "next generation" of VBO schemes, exemplified by their academic prototype, Loki. These advanced obfuscators move beyond simply complicating individual VM components, instead focusing on generating highly complex, target-specific instruction sets and interweaving VM components in a way that forces global, cross-handler analysis. By leveraging techniques such as polynomial encodings, mathematically hard problems for key checks, partial point functions, and advanced Mixed Boolean-Arithmetic (MBA) expressions, these novel designs aim to render current deobfuscation tools and methodologies ineffective, thereby reshaping the landscape of software protection for high-value intellectual property, DRM systems, mobile banking applications, and even malware.

This article provides a comprehensive exploration of the concepts, technical intricacies, and implications discussed in Blazytko and Schloegel's talk. It dissects the vulnerabilities of traditional VBOs, elaborates on the innovative design principles of next-gen obfuscators, and outlines the significant challenges these advancements pose for the deobfuscation community. The insights shared are crucial for both developers seeking to protect their software and security researchers striving to understand and bypass these advanced defenses.

Background

▶ Watch: Talk overview: VM obfuscation, attacks, and new schemes (0:50)

Virtualization-Based Obfuscation (VBO) is a potent software protection technique widely deployed across various industries, from digital rights management (DRM) in streaming services like Netflix and gaming platforms to mobile banking applications and even sophisticated malware. Its primary goal is to complicate reverse engineering attempts, thereby safeguarding sensitive algorithms and intellectual property embedded within software binaries.

At its core, VBO operates by translating critical segments of native code (e.g., x86 instructions) into a custom, made-up instruction set language for a software virtual machine (VM). This bytecode, unlike native machine code, holds no intrinsic meaning to standard disassemblers or human reverse engineers without prior knowledge of the VM's architecture. The original native code is replaced by a pointer to this bytecode, and a special function, the VM entry, initiates a software interpreter that processes the bytecode.

A typical VBO architecture comprises several key components:

• VM Entry and VM Exit: These are code components responsible for transitioning execution between the native environment and the VM. The VM entry prepares the VM's internal state (registers, keys), while the VM exit restores the native execution context.
• VM Dispatcher: This component acts as the software implementation of a CPU's fetch-decode-execute loop. It fetches bytes from the bytecode, decodes them into virtual instructions, increments the virtual instruction pointer, and then dispatches control to a specific handler.
• Handlers: These are small pieces of native code that implement the semantics of individual virtual instructions (e.g., a virtual addition, multiplication, or push operation).
• Handler Table: A data structure, typically a jump table or an array of function pointers, that stores the addresses of all individual VM handlers.

The traditional approach to deobfuscating such a VM involves a structured methodology:

1. Understand VM Architecture: Identify the VM entry, bytecode location, and handler structure.
2. Reverse Engineer Semantics: Determine what each handler does (e.g., "this is an addition").
3. Figure Out Instruction Encoding: Decipher the format of the custom bytecode instructions (e.g., opcode, operand registers).
4. Write Custom Disassembler: Create a tool to translate the raw bytecode into meaningful virtual instructions.
5. Reconstruct Control Flow and High-Level Code: Based on the disassembled virtual instructions, rebuild the program's logic.

To counter these deobfuscation efforts, VBO implementers have developed several hardening techniques:

• Obfuscating Individual VM Components: Handlers, which are semantically simple, are made syntactically complex using common code obfuscation techniques like code substitution, predicate introduction, and junk code insertion. This increases the "instructions per handler."
• Duplicating Handlers: Instead of a limited set of 50 distinct handlers, obfuscators might create thousands of syntactically unique but semantically identical handler copies. This massively increases the manual analysis workload and forces automation.
• Inlining the Dispatcher: To eliminate a central point of instrumentation, the dispatcher's logic is inlined at the end of each handler. This removes the "central dispatcher" as an easy target for breakpoints.
• Encoding Next Handler Address: The address of the next handler to be executed is embedded directly into the bytecode instruction itself. This removes the "global handler table" as a central data structure to analyze.
• Bytecode Blinding/Encryption: The bytecode is encrypted or encoded in a control-flow sensitive manner. This means the decryption key for a given instruction depends on the execution path taken and the state left by previous handlers. A handler might decrypt the next instruction and then update the key for the subsequent one, making static disassembly impossible without simulating execution.

Despite these hardening measures, existing VM-based obfuscation schemes have proven vulnerable to advanced automated deobfuscation techniques:

• Compiler Optimizations: Techniques like dead code elimination (removing unused instructions), constant folding (pre-computing constant expressions), constant propagation (replacing variables with their constant values), and peephole optimization (local instruction sequence simplification) can significantly simplify obfuscated handlers. Tools that lift binaries to an Intermediate Representation (like LLVM IR) can apply these optimizations and then recompile the simplified code.
• Symbolic Execution: This technique executes code symbolically, propagating symbolic values rather than concrete ones. By symbolically executing a handler, its underlying semantic function can be automatically derived, even if syntactically complex. This provides a "symbolic summary" of the handler's operation.
• Program Synthesis: Treating the obfuscated code as a black box, program synthesis uses I/O sampling (feeding random inputs and observing outputs) to learn the underlying mathematical function. Stochastic learning algorithms then attempt to synthesize equivalent, simpler mathematical formulas.
• Codebook Attacks: Given that VMS have a predictable set of instruction semantics (addition, multiplication, XOR), attackers can generate a "codebook" of pre-computed handler semantics. By I/O sampling an unknown handler and comparing its behavior to the codebook, its function can be identified. SMT solvers can even be used to formally prove the semantic equivalence between a derived symbolic expression and a known template.

The fundamental shortcomings of these traditional and hardened VMS lie in their predictable instruction semantics (handlers still perform easily identifiable operations like addition) and the independence of individual VM components, meaning obfuscation is often applied locally to handlers, allowing them to be analyzed and simplified in isolation. These limitations paved the way for the sophisticated attacks described above, setting the stage for the necessity of a "next generation" of obfuscators.

Key Findings

▶ Watch: Common hardening techniques for existing VM obfuscation (10:10)

The central revelation of this talk is the critical vulnerability of even highly hardened, current-generation virtualization-based obfuscation schemes to modern, automated deobfuscation techniques. Despite employing measures like junk code, dispatcher inlining, and bytecode blinding, these VMS suffer from predictable instruction semantics and component independence, rendering them susceptible to compiler optimizations, symbolic execution, program synthesis, and codebook attacks. This means that the industry's existing VBO solutions, while complex, are increasingly being outmaneuvered.

In response to this escalating threat, the speakers unveil the emergence of a next generation of VM-based obfuscators. These advanced designs, exemplified by their academic prototype Loki, fundamentally rethink VBO by introducing two core design principles:

1. Complex and Target-Specific Instruction Sets: Instead of generic, simple operations (like ADD or MUL), handlers are generated with highly intricate and diverse semantics, often derived directly from instruction sequences found within the target program itself. This eliminates predictable mnemonics and creates handlers that are inherently resistant to synthesis-based attacks due to their complexity and unique nature.
2. Intervened VM Components: Obfuscation is no longer applied locally to individual handlers. Instead, VM components are tightly interlocked, forcing deobfuscators to perform cross-handler analysis or even cross-function analysis across potentially thousands of instructions. This can involve arithmetic encodings where the output of one handler partially encodes data for subsequent handlers, or data flow/control flow dependencies that span multiple VM instructions.

The talk highlights several specific technical advancements that enable these principles:

• Polynomial encodings to merge instruction semantics into single, branchless basic blocks, creating tight interdependencies.
• The use of mathematically hard problems (e.g., factorization, quadratic residuosity) for key checks, making instruction selection SMT-hard and neutralizing SMT-solver based codebook attacks.
• Partial point functions that introduce "random garbage" into I/O samples, effectively breaking program synthesis.
• Generation of semantically complex operations directly from the target program's code, challenging synthesis algorithms that excel at finding short expressions.
• Extensive use of Mixed Boolean-Arithmetic (MBA) expressions, generated through advanced enumerative program synthesis and recursive rewriting, to create syntactically complex but semantically equivalent operations that significantly impede symbolic execution.

Collectively, these innovations represent a significant shift in the obfuscation landscape, placing obfuscation at a considerable advantage in the current arms race. The key finding is that the deobfuscation community must now contend with VMS that are not only harder to analyze locally but also demand entirely new tools and methodologies for global, context-sensitive analysis, pushing existing analysis tools to their limits.

Technical Deep Dive

▶ Watch: Next-generation VM design: complex, intertwined instruction sets (29:00)

The core innovation of next-generation virtualization-based obfuscation, as demonstrated by the Loki prototype, lies in its departure from predictable, isolated handler semantics towards highly complex, intertwined, and target-specific instruction sets. This section delves into the specific techniques employed to achieve this paradigm shift.

At the outset, Loki, like traditional VMS, operates on a mathematical notation to represent handler logic. Instructions can include embedded constants, denoted by C, allowing for more flexible instruction encoding. The goal is to make the instruction semantics (what a handler computes) far more intricate than simple X + Y operations.

Merging Instruction Semantics with Polynomial Encoding

A fundamental technique is merging instruction semantics. Instead of having separate handlers for X + Y and X - Y, Loki combines these into a single, larger handler. A key K is introduced, which allows the merged handler to select between the original semantics. Conceptually, this might appear as a conditional branch (e.g., if K then X+Y else X-Y). However, this conditional structure is still vulnerable to static analysis.

To overcome this, Loki employs polynomial encoding. This clever trick replaces explicit branches with a combination of additions and multiplications that achieve the same conditional behavior, but within a single, gigantic basic block. For example, (K (X+Y)) + ((1-K) (X-Y)) could emulate the conditional behavior if K is 0 or 1. This creates a tight interlocking of instruction semantics, making it impossible to trivially remove instructions or isolate branches, thereby complicating both static analysis and symbolic execution.

Mathematically Hard Problems for Key Checks

Traditional VMS often use simple comparisons for key checks, which are easily solved by SMT solvers during codebook attacks. Next-gen VMS, however, introduce mathematically hard problems to select instruction semantics. Two prominent examples are:

• Factorization: The key check might involve determining if K is a factor of a very large integer N. This problem is famously hard, forming the basis of RSA cryptography.
• Quadratic Residuosity: Another hard problem that involves determining if an integer is a quadratic residue modulo another integer.

The power of these problems lies in their huge search space and small solution space, with no easily exploitable partial solutions. This characteristic makes the instruction selection logic SMT-hard, meaning SMT solvers cannot efficiently prune the search space or find solutions, effectively neutralizing codebook attacks that rely on proving semantic equivalence.

Partial Point Functions for Synthesis Resilience

To specifically target program synthesis attacks, which rely on I/O sampling to learn function behavior, Loki utilizes partial point functions. These functions are specifically designed to return a defined value (e.g., 1) for the correct key and another defined value (e.g., 0) for an incorrect but expected key (e.g., the key for another merged handler). For all other inputs, however, the function's behavior is undefined, resulting in "random garbage" outputs.

When program synthesis tools perform I/O sampling with random inputs, they will encounter this undefined behavior for the vast majority of samples. This influx of "random garbage" makes it impossible for the synthesis algorithm to learn a consistent mathematical expression for the function, thus breaking the synthesis process. This technique is particularly effective in scenarios where the attacker does not have runtime access to the actual keys.

Semantically Complex Operations from Target Programs

A key principle of next-gen VMS is to generate target-specific handlers. Instead of generic operations, handlers are constructed from complex instruction sequences found within the program being obfuscated. This involves analyzing the target program, often converting it into Static Single Assignment (SSA) form, and then recursively replacing users by their definitions to build progressively more complex expressions.

For example, a simple sequence like EDX2 = EDX1 0x10; EDX3 = EDX2 + 0x5; could be collapsed into a single handler that computes EDX3 = (EDX1 0x10) + 0x5. By applying this recursively, highly intricate arithmetic operations can be derived directly from the program's logic. This results in semantically complex arithmetic operations that introduce significant diversity, making handlers non-predictable. While program synthesis excels at finding short expressions, its success rate drops rapidly as the complexity of the target expression increases, effectively rendering it useless against these custom, deep computations.

Syntactically Complex Expressions using Mixed Boolean-Arithmetic (MBAs)

To specifically target symbolic execution, Loki employs Mixed Boolean-Arithmetic (MBA) expressions. MBAs replace simple expressions with more complex, but semantically equivalent, ones. For instance, X + Y can be rewritten as (X XOR Y) + 2 * (X AND Y). The underlying computation remains identical, but the syntactic representation becomes significantly more convoluted, making symbolic simplification difficult.

The generation of MBAs has evolved:

• Handcrafted Rewriting Rules: Initially, MBAs relied on a limited set of handcrafted rules (e.g., 47 rules from sources like Hacker's Delight).
• Enumerative Program Synthesis: Modern approaches, as used in Loki, leverage enumerative program synthesis to automatically discover a vast number of rewriting rules. By generating all possible expressions up to a certain depth and comparing their behavior, Loki's creators identified over 850,000 rewriting rules.
• Recursive Rewriting: Instead of applying a rule once, a recursive rewriting approach can be used. An expression is transformed, and then sub-expressions within the newly transformed expression are further rewritten, allowing for the creation of arbitrarily complex expressions.

An even more powerful category is Polynomial MBAs. These utilize invertible functions H and H^-1. An expression E is transformed into H(E) and then rewritten as H(E') where E' is a more complex form, finally resulting in H(E') * H^-1(E') which simplifies back to E. This technique allows for the generation of incredibly intricate and difficult-to-simplify expressions, further hindering symbolic execution.

The combination of these techniques—merging semantics with polynomial encodings, using hard mathematical problems for key checks, deploying partial point functions, generating semantically complex operations from the target program, and creating syntactically dense expressions via advanced MBAs—creates a robust, multi-layered defense. It is the synergistic effect of these methods, rather than any single "panacea," that elevates next-gen VMS beyond the reach of current deobfuscation tools and methodologies.

Demo / Proof of Concept

▶ Watch: Loki's advanced techniques: merging semantics, polynomial encoding, MBAs (35:00)

While the talk meticulously detailed the academic prototype Loki and its underlying techniques, it did not feature a live, interactive demonstration of the tool in action. Instead, Moritz Schloegel thoroughly explained the conceptual design and implementation strategies for each advanced obfuscation method within Loki. The presentation focused on the theoretical underpinnings and the architectural decisions that enable these next-generation virtualization-based obfuscators to achieve their resilience against modern deobfuscation attacks. Attendees were provided with an academic paper for further in-depth study of Loki's implementation.

Defensive Implications

▶ Watch: Conclusion: Current VMS breakable, next-gen shifts landscape (57:00)

For software developers and organizations seeking to protect their intellectual property, sensitive algorithms, and critical code, the insights from this talk are paramount. The emergence of next-generation virtualization-based obfuscators signifies a new standard in software protection, rendering older, even hardened, VBO techniques increasingly obsolete against determined attackers armed with automated deobfuscation tools.

The primary defensive implication is a call to adopt and implement these advanced obfuscation strategies. This means moving beyond simple code transformations and local handler obfuscation towards a holistic approach that fundamentally alters how the virtual machine operates. Defenders should focus on:

1. Developing Target-Specific Obfuscation: Instead of generic VM instruction sets, design custom handlers that are derived directly from the unique instruction sequences and data flows within the specific application being protected. This ensures maximum diversity and unpredictability, making it harder for attackers to apply generalized deobfuscation strategies.
2. Intertwining VM Components Globally: Implement obfuscation techniques that create dependencies across multiple handlers and VM components. This includes using arithmetic encodings that span several VM instructions and leveraging control-flow or data-flow dependencies that force deobfuscators to analyze the VM's state and execution path over extended sequences, rather than in isolated segments.
3. Leveraging Advanced Mathematical and Computational Techniques: Incorporate polynomial encodings to eliminate branches and create monolithic basic blocks, utilize mathematically hard problems (like factorization or quadratic residuosity) for critical key checks to thwart SMT-solver attacks, and employ partial point functions to confuse program synthesis attempts.
4. Implementing Sophisticated Mixed Boolean-Arithmetic (MBA) Expressions: Use MBAs, generated through enumerative program synthesis and recursive rewriting, to create syntactically complex but semantically equivalent code. This specifically targets and significantly impedes symbolic execution engines.

By integrating these next-generation design principles, organizations can deploy VBOs that are resilient against current automated deobfuscation tools, thereby significantly increasing the cost and effort required for reverse engineering. This is particularly crucial for industries like DRM, mobile banking, embedded systems, and high-value software applications where the security of intellectual property directly impacts business viability and user trust. The talk serves as a clear roadmap for advancing software protection in an increasingly sophisticated threat landscape.

Key Takeaways

• Current VBOs are Vulnerable: Existing virtualization-based obfuscation schemes, even with hardening techniques like dispatcher inlining and bytecode blinding, are increasingly susceptible to automated deobfuscation methods such as compiler optimizations, symbolic execution, program synthesis, and codebook attacks due to predictable semantics and local obfuscation.
• Next-Gen VMS Introduce New Design Principles: The future of VBO lies in two core tenets: creating complex and target-specific instruction sets (derived from the protected program's code) and intervening VM components through global, cross-handler obfuscation.
• Advanced Techniques Drive Resilience: Key innovations include polynomial encodings to merge handler semantics into branchless basic blocks, mathematically hard problems (e.g., factorization) for SMT-hard key checks, partial point functions to disrupt program synthesis, and extensive use of Mixed Boolean-Arithmetic (MBA) expressions (generated via enumerative synthesis) to complicate symbolic execution.
• Obfuscation Gains an Advantage: These next-generation techniques significantly shift the arms race, placing obfuscation at a considerable advantage by rendering current deobfuscation tools and methodologies ineffective against the increased complexity and interdependency.
• Deobfuscation Research Must Catch Up: To counter these advancements, deobfuscation research needs significant progress in developing better analysis tools for cross-function and multi-threaded environments, improved binary lifting to intermediate representations, smarter strategies for identifying analysis windows, and novel approaches for deobfuscating polynomial MBAs.
• The Future Landscape is Shaped by Next-Gen VMS: The widespread adoption of these advanced VBO designs will redefine the challenges and strategies in software protection and reverse engineering for the foreseeable future, demanding a fundamental rethink from the deobfuscation community.

About the Speaker(s)

Tim Blazytko is the Chief Scientist and Co-founder of emproof, an embedded security firm specializing in the design of robust software protection systems for embedded devices. With extensive expertise in the field, Tim also regularly conducts trainings on advanced code obfuscation and reverse engineering techniques, sharing his deep knowledge with the security community.

Moritz Schloegel is a Security Researcher and a last-year PhD assistant at CISPA in Saarbrücken. His research focuses on battery security and broader aspects of Google's Engineering. Moritz is an old coworker of Tim Blazytko, and together they collaborated on the development of the cutting-edge code obfuscation scheme discussed in this presentation.