Bending microarchitectural weird machines towards practicality

Bending microarchitectural weird machines towards practicality

Speakers: Ping-Lun Wang

Conference: USENIX Security '24

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

Overview

In a groundbreaking presentation at USENIX Security '24, Ping-Lun Wang unveiled Flexo, a novel design that significantly advances the practicality and scalability of microarchitectural weird machines. This talk shifts focus from discovering new microarchitectural side channels to leveraging existing ones as a computational substrate. Flexo demonstrates how to construct fully functional, albeit unconventional, computers within the microarchitectural layer of a processor, using transient execution and cache side effects to perform complex computations.

The core challenge addressed by Flexo lies in the inherent limitations of previous microarchitectural weird machine designs, which suffered from low accuracy, poor scalability for complex circuits, and extreme difficulty in programming. By introducing a new circuit construction paradigm, an innovative error correction mechanism, and the first-ever compiler for these machines, Flexo transforms a theoretical curiosity into a tangible threat, capable of executing real-world applications like the UPX packer and AES encryption.

This work is particularly significant because microarchitectural weird machines operate beneath the conventional Instruction Set Architecture (ISA) interface, making their computational states invisible to architectural-level analysis. Their reliance on low-level logic gates implemented via microarchitectural components renders both static and dynamic program analysis exceedingly difficult. Flexo's advancements elevate these capabilities to a practical level, opening new avenues for program obfuscation, malware development, and other attacks that demand stealth and resilience against traditional security tools.

Background

▶ Watch: Existing weird machines are not scalable or programmable (1:30)

Traditionally, software developers perceive a processor as a black box, interacting with it solely through the Instruction Set Architecture (ISA). However, opening this black box reveals a rich tapestry of microarchitectural components—caches, branch predictors, out-of-order execution engines—that, while designed for performance, can inadvertently leak information or be coerced into unintended computational states. Microarchitectural weird machines exploit these low-level behaviors to perform computations, effectively building a "computer inside a microarchitectural world."

Prior research in this domain, notably the "Gate of Time" paper presented at USENIX the previous year, demonstrated the potential of these weird machines for tasks like amplifying cache signals and enabling advanced cache attacks. However, these early designs faced significant hurdles. They lacked scalability, meaning they struggled to correctly compute even moderately complex operations like AES encryption. Furthermore, their construction involved deeply intricate, low-level code snippets, making them extraordinarily difficult to program and requiring specialized expertise to create new weird machines.

The fundamental building blocks of these weird machines are weird gates and weird registers. Weird gates are constructed from memory operations that occur during transient execution. Transient execution happens when the processor speculatively executes instructions based on a prediction (e.g., a branch prediction) but ultimately squashes these instructions if the prediction was wrong. Crucially, any architectural changes (e.g., register or memory modifications) made during transient execution are reverted. However, microarchitectural side effects, such as cache line accesses, persist. Weird registers, therefore, are not stored in architectural memory or registers but are built from cache residency information: a value of '1' signifies a cache hit (data is in the cache), and '0' signifies a cache miss (data is out of the cache).

A concrete example of a weird gate involves an if statement designed to trigger transient execution. Within the if condition, the branch predictor is intentionally misled, forcing the processor to mispredict into a speculative path. In this path, a weird gate, such as an AND gate, is transiently executed. This AND gate takes two weird registers as input and outputs to another weird register. The computation relies on the timing differences of cache accesses:

• If both input weird registers are '1' (both in cache), their access latency is very short (cache hit). The AND gate can then speculatively fetch the output weird register into the cache, setting its value to '1'.
• If any input weird register is '0' (out of cache), its access latency is much longer (cache miss). This longer latency prevents the AND gate from fetching the output weird register into the cache during the transient window, effectively setting its value to '0'.

While prior work successfully constructed basic logic gates like AND, OR, and NOT using similar techniques, their approach to circuit construction and error correction proved inefficient for scaling to real-world applications. The inherent difficulty in managing these transient microarchitectural interactions limited their practical utility, underscoring the need for a more robust and programmable framework like Flexo.

Key Findings

▶ Watch: Concrete example of a microarchitectural 'wear end gate' (3:34)

Flexo introduces several groundbreaking innovations that fundamentally address the limitations of prior microarchitectural weird machine designs, significantly enhancing their scalability, accuracy, and programmability. The key findings and contributions are:

1. Novel Circuit Construction with Differential Encoding: Flexo proposes a new method for representing binary values using differential encoding. Instead of a single cache line representing a bit, two "wires" (cache lines), a plus wire and a minus wire, are used. This encoding not only allows for much more scalable gate construction but also inherently supports error detection.
2. Truth Table-Based Gate Generation: Leveraging differential encoding, Flexo can construct complex weird gates directly from their truth tables, similar to how Lookup Tables (LUTs) function in FPGAs. This allows for the creation of single weird gates capable of performing operations like XOR or even a "huge full adder" with up to four inputs, a stark contrast to previous methods limited to basic AND, OR, NOT gates.
3. Dynamic Voting Error Correction: Flexo implements a novel dynamic voting mechanism for error correction. Unlike prior work's fixed-overhead majority voting (e.g., 3-out-of-5), Flexo only reruns a circuit when an error is detected (i.e., when a differentially encoded bit enters an invalid state). This results in a significantly smaller, dynamic overhead and demonstrates remarkable error-fixing capabilities, improving circuits with 0.3% accuracy to 99.9%.
4. First Compiler for Microarchitectural Weird Machines: A major contribution is the development of the first compiler specifically designed for microarchitectural weird machines. This compiler abstracts away the low-level microarchitectural details, allowing programmers to write high-level code. It also incorporates optimizations to improve circuit accuracy and performance, making the creation of new weird machines accessible beyond a small group of experts.
5. Achieving Real-World Program Execution: With these advancements, Flexo enables the successful and practical execution of complex, real-world programs within the microarchitectural domain. This includes the full SHA-1 hash function and AES encryption, achieving near 100% accuracy on various Intel microarchitectures.
6. Superior Performance and Efficiency: Experimental results demonstrate that Flexo-generated circuits are 4 to 8 times smaller than those from prior work (e.g., "Gate of Time"). They exhibit significantly higher accuracy, even without error correction, and are substantially faster. For instance, the SHA-1 circuit computes 20 times faster than the previous state-of-the-art, and the overhead of Flexo's dynamic error correction is notably smaller.

These findings collectively establish microarchitectural weird machines as a more practical and potent tool, moving them from a research curiosity to a capability with significant implications for security and defense.

Technical Deep Dive

▶ Watch: Constructing complex gates directly from truth tables (5:55)

Flexo's technical prowess stems from its innovative approach to encoding, gate construction, error correction, and overall circuit compilation. These elements work in concert to overcome the inherent limitations of prior microarchitectural weird machine designs.

Differential Encoding for Scalability

At the heart of Flexo's circuit construction is differential encoding. Instead of representing a binary bit with a single cache line's residency state (e.g., in cache = 1, out of cache = 0), Flexo uses two distinct "wires" or cache lines for each bit: a plus wire and a minus wire.

• To represent a binary value of 1: The plus wire is set to '1' (in cache), and the minus wire is set to '0' (out of cache).
• To represent a binary value of 0: The plus wire is set to '0' (out of cache), and the minus wire is set to '1' (in cache).

Any other combination (e.g., both in cache, both out of cache) is considered an invalid state. This provides an immediate mechanism for error detection, as an invalid state indicates a computation error. While seemingly more complex, this dual-rail encoding offers significant benefits, particularly in building more robust and scalable gates.

Truth Table-Based Gate Construction

One of the most impactful benefits of differential encoding is the ability to construct weird gates directly from their truth tables. This paradigm shift is analogous to how Lookup Tables (LUTs) are used in Field-Programmable Gate Arrays (FPGAs). Instead of laboriously crafting each basic logic gate (AND, OR, NOT) from individual transient execution sequences, Flexo can synthesize a single, complex weird gate that implements any logic function with up to four inputs.

Under the hood, this synthesis still relies on composing basic OR and AND gates. However, the compiler handles this complexity, abstracting it away from the programmer. This capability allows Flexo to implement functions like an XOR gate or even a huge full adder as a single weird gate, dramatically reducing the circuit size and complexity compared to prior work, which could only assemble these from multiple basic gates. The ability to directly map truth tables to weird gates is a cornerstone of Flexo's improved scalability.

Dynamic Voting Error Correction

Microarchitectural operations are inherently noisy, leading to potential errors in weird machine computations. Prior work employed a 3-out-of-5 majority voting scheme, rerunning the entire circuit five times and taking the majority result. This approach had a fixed 5x overhead and was not always effective, especially for circuits with very low inherent accuracy.

Flexo introduces a more efficient and effective dynamic voting mechanism. Leveraging the differential encoding, errors are detected when a bit's plus and minus wires enter an invalid state (e.g., both in cache or both out of cache). When such an error is detected, only the specific portion of the circuit affected by the error is rerun. This leads to a dynamic overhead that is significantly smaller than the fixed overhead of previous methods. The effectiveness of dynamic voting is remarkable: Flexo demonstrated the ability to correct circuits with an initial accuracy as low as 0.3% to a highly reliable 99.9%. This adaptive error correction is crucial for making complex computations feasible.

The Flexo Compiler

Perhaps the most significant contribution to practicality is the first compiler for microarchitectural weird machines. Before Flexo, creating a new weird machine involved manually writing highly intricate, low-level code snippets that directly manipulated cache states and transient execution paths. This was a task only feasible for a handful of experts.

The Flexo compiler liberates programmers from these low-level details. Users can now write high-level programs, and the compiler automatically translates them into the necessary microarchitectural weird machine instructions. Beyond translation, the compiler also performs crucial optimizations on the generated circuits, enhancing both their accuracy and performance. This abstraction layer is what truly makes microarchitectural weird machines accessible and programmable, enabling their use in diverse applications.

Experimental Validation

Flexo's design was rigorously evaluated on eight shared Intel AD C2 instances across different microarchitectures (e.g., Skylake). Comparisons with the "Gate of Time" paper on Skylake demonstrated Flexo's superior performance:

• Circuit Size: Flexo-generated circuits were 4 to 8 times smaller.
• Accuracy: Flexo achieved significantly higher accuracy, even without error correction, and near 100% accuracy with dynamic voting.
• Runtime: Flexo was substantially faster. For example, a SHA-1 hash circuit took around 50 milliseconds, making it 20 times faster than the prior state-of-the-art. AES encryption, a highly complex operation, was implemented for the first time as a microarchitectural weird machine, taking between 200 to 350 milliseconds. While slower than architectural AES, this is fast enough for many targeted applications.

These technical advancements collectively represent a paradigm shift, transforming microarchitectural weird machines from a theoretical concept into a practical and powerful computational tool.

Demo / Proof of Concept

▶ Watch: Dynamic voting for superior error correction and accuracy (6:28)

To demonstrate the real-world applicability and potency of Flexo's advancements, a compelling proof-of-concept was presented: an obfuscated UPX packer powered by Flexo. UPX is a widely used executable packer, often employed by malware to compress code and data, thereby hindering static analysis. Flexo leverages this concept to create an even more formidable obfuscation technique.

In this demonstration, a standard Portable Executable (PE) binary is encrypted using either AES encryption (implemented as a Flexo weird machine) or a custom symmetric encryption scheme. When this obfuscated binary is executed, a Flexo microarchitectural weird machine is invoked at runtime to decrypt the packed binary. This decryption process occurs entirely within the microarchitectural domain, making the computational states and decryption key invisible to traditional architectural-level debuggers, static analysis tools, and dynamic analysis techniques.

The primary goal of this obfuscation is to significantly increase the difficulty of reverse engineering. By moving the critical decryption logic into a microarchitectural weird machine, attackers can evade many existing antivirus tools and analysis frameworks that rely on inspecting architectural instruction flows, memory contents, or API calls.

Regarding performance, unpacking a 132-kilobyte binary using this Flexo-obfuscated method took approximately:

• 1 minute with the custom symmetric decryption.
• 5 minutes with the AES encryption implemented as a weird machine.

While these times are considerably slower than a normal, un-obfuscated packer, the speaker emphasized that "slower execution speed does not really matter for attack scenarios like a malware attack." For malware, stealth and resilience against detection often outweigh minor performance penalties. The ability to defeat many existing antivirus tools by hiding critical operations in the microarchitectural layer presents a significant advantage for attackers.

Beyond the UPX packer, Flexo also demonstrated the successful implementation of other complex cryptographic primitives:

• The SHA-1 hash function was computed in approximately 50 milliseconds, which is 20 times faster than previous microarchitectural implementations.
• Full AES encryption was achieved in 200 to 350 milliseconds, marking the first time this complex encryption algorithm has been successfully implemented and executed as a microarchitectural weird machine in the literature.

These demonstrations unequivocally establish that Flexo has elevated microarchitectural weird machines from a theoretical curiosity to a practical tool capable of executing complex, real-world cryptographic functions and serving as a potent technique for program obfuscation.

Defensive Implications

▶ Watch: Overview of experimental results and performance (8:00)

The advancements presented by Flexo signal a critical shift in the landscape of program analysis and security. Microarchitectural weird machines are no longer an academic exercise but a practical threat with profound defensive implications. Defenders must now contend with a new class of attacks that operate beneath the traditional software-hardware interface, rendering many existing security tools ineffective.

1. Evasion of Traditional Analysis Tools: The most immediate implication is that Flexo-enabled weird machines can effectively evade both static and dynamic analysis tools. Because computational states are hidden within the microarchitectural world and logic gates are implemented using transient execution, conventional debuggers, disassemblers, sandboxes, and antivirus engines will struggle to observe or interpret the true control flow and data manipulation. This makes malware analysis, intellectual property protection, and detection of sophisticated threats significantly more challenging.

1. Need for Microarchitectural Visibility: Defenders require new tools and techniques that can gain visibility into microarchitectural activity. This means moving beyond ISA-level monitoring to observe cache states, branch predictor behavior, and transient execution patterns. Developing such tools is complex and requires deep hardware understanding, potentially involving hardware performance counters, specialized instrumentation, or even modifications to processor designs.

1. Rethinking Program Obfuscation Detection: The use of Flexo for program obfuscation, as demonstrated with the UPX packer, means that traditional obfuscation detection techniques based on code entropy, API call patterns, or control flow graph analysis may become obsolete. New methods must be developed to identify the presence of microarchitectural computation within binaries.

1. Hardware-Level Mitigations: While Flexo leverages existing microarchitectural features, the increasing practicality of weird machines might necessitate hardware-level mitigations. These could include modifications to how transient execution is handled, stricter isolation of microarchitectural resources, or even hardware-assisted monitoring capabilities designed to detect anomalous microarchitectural computation. However, such changes are costly, complex, and could impact performance.

1. New Research Avenues: The talk opens up new avenues for security research. Defenders need to explore how to:

• Detect the presence of weird machines on a system.
• Analyze the logic and data flow of microarchitectural computations.
• Mitigate their impact without crippling legitimate performance.
• Understand the full range of attack scenarios beyond obfuscation, such as data exfiltration or integrity violations.

In conclusion, Flexo has made microarchitectural weird machines a potent, practical tool for adversaries. The security community must acknowledge this new threat vector and rapidly develop innovative defensive strategies to counter attacks that exploit the processor's hidden computational capabilities.

Key Takeaways

• Flexo revolutionizes microarchitectural weird machines: It significantly improves their scalability, accuracy, and ease of programming, moving them from theoretical concept to practical application.
• Differential encoding enhances gate construction: Using two "wires" per bit allows Flexo to build complex logic gates directly from truth tables, enabling single weird gates for operations like XOR or full adders, which were previously impossible.
• Dynamic voting provides efficient error correction: Flexo's adaptive error correction mechanism, triggered only upon error detection, offers a much smaller overhead and superior accuracy compared to fixed-overhead majority voting schemes.
• The first compiler democratizes weird machine development: By abstracting away low-level microarchitectural details, Flexo's compiler allows programmers to write high-level code, making the creation and optimization of weird machines accessible to a broader audience.
• Real-world applications are now feasible: Flexo successfully implemented complex functions like SHA-1 hashing (20x faster than prior work) and AES encryption (first in literature), demonstrating its capability for practical use cases.
• Microarchitectural weird machines pose a new security threat: The ability to execute programs and obfuscate code within the microarchitectural layer makes these machines a potent tool for evading traditional static and dynamic analysis, presenting significant challenges for defenders and requiring new security paradigms.

About the Speaker(s)

Ping-Lun Wang is the presenter of this talk at USENIX Security '24, focusing on his research into making microarchitectural weird machines practical. His work, as demonstrated by Flexo, centers on overcoming the significant challenges of scalability, accuracy, and programmability that have hindered the broader adoption and study of these novel computational paradigms. Through his contributions in differential encoding, truth table-based gate construction, dynamic error correction, and the development of the first compiler for microarchitectural weird machines, Ping-Lun Wang has significantly advanced the field, showcasing how these low-level processor behaviors can be harnessed for complex, real-world applications.