In this article, we explore the design and implementation of Rust-based hypervisors for memory introspection and reverse engineering on Windows. We cover two projects - illusion-rs, a UEFI-based hypervisor, and matrix-rs, a Windows kernel driver-based hypervisor. Both leverage Extended Page Tables (EPT) to implement stealthy control flow redirection without modifying guest memory.

We begin by identifying how to reliably detect when the System Service Descriptor Table (SSDT) is fully initialized within ntoskrnl.exe, allowing hooks to be safely installed without risking a system crash. Illusion and Matrix differ in how they trigger and redirect execution. Illusion uses a single EPT and in-place patching with VM-exit instructions like VMCALL, combined with Monitor Trap Flag (MTF) stepping to replay original bytes safely. In contrast, Matrix uses a dual-EPT model where the primary EPT maps read/write memory and the secondary EPT remaps execute-only shadow pages containing trampoline hooks. Execution is redirected using INT3 breakpoints and dynamic EPTP switching during EPT violations. Both approaches hide inline hooks from guest virtual memory and redirect execution flow to attacker-controlled code - such as shellcode or handler functions - using EPT-based remapping and VM-exits triggered by CPU instructions like INT3, VMCALL, or CPUID.

In hypervisor development, shadowing refers to creating a second, hypervisor-controlled view of guest memory. When a page is shadowed, the hypervisor creates a duplicate of the original page - typically referred to as a shadow page - and updates the EPT to redirect access to this copy. This allows the hypervisor to intercept, monitor, or redirect memory accesses without modifying the original guest memory. Shadowing is commonly used to inject hooks, conceal modifications, or control execution flow at a fine-grained level. The guest and shadow pages remain distinct: the guest believes it is accessing its own memory, while the hypervisor controls what is actually seen or executed.

We demonstrate how to use execute-only permissions to trap instruction fetches, read/write-only permissions to catch access violations, and shadow pages to inject trampoline redirections. For introspection and control transfer, we rely on instruction-level traps such as VMCALL, CPUID, and INT3, depending on the context. In Illusion, instruction replay is handled via Monitor Trap Flag (MTF) single-stepping to safely restore overwritten bytes.

While these techniques are well-known in the game hacking community, they remain underutilized in infosec. This article aims to bridge that gap by providing a practical, reproducible walkthrough of early boot-time and kernel-mode EPT hooking techniques. All techniques used are public, stable, and do not rely on undocumented internals or privileged SDKs.

The approach taken prioritizes minimalism and reproducibility. We assume readers have a working understanding of paging, virtual memory, and the basics of Intel VT-x and EPT. While some concepts may apply to AMD SVM and NPT, this article focuses exclusively on Intel platforms. Both hypervisors avoid modifying guest memory entirely, preserving system integrity and navigating around kernel protections like PatchGuard. This enables stealth monitoring of functions like NtCreateFile and MmIsAddressValid from outside the guest’s control using EPT-backed remapping.

Table of Contents

• Illusion: UEFI-Based Hypervisor with EPT-Based Hooking
  • Setting up IA32_LSTAR MSR hook during Initialization (initialize_shared_hook_manager())
  • Setting Kernel Image Base Address and Size (set_kernel_base_and_size())
  • Detecting When SSDT Is Loaded Inside ntoskrnl.exe
    • On Intel processors, the execution path is reliable (verified via Binary Ninja analysis on Windows 11 build 26100):
    • On AMD processors, the path is conditional (verified via Binary Ninja analysis on Windows 11 build 26100):
  • Setting Up EPT Hooks (handle_cpuid())
  • Resolving Targets and Dispatching Hooks (manage_kernel_ept_hook())
  • Second-Level Address Translation (SLAT): EPT (Intel) and NPT (AMD)
  • EPT Hooking Overview (build_identity())
    • Installing the Hook Payload (ept_hook_function())
    • Mapping the Large Page (map_large_page_to_pt())
    • Step 1 - Splitting the Page (is_large_page() -> split_2mb_to_4kb())
    • Shadowing the Page (is_guest_page_processed() -> map_guest_to_shadow_page())
    • Step 2 - Cloning the Code (unsafe_copy_guest_to_shadow())
    • Step 3 - Installing the Inline Hook
    • Step 4 - Revoking Execute Rights (modify_page_permissions())
    • Step 5 - Invalidating TLB and EPT Caches (invept_all_contexts())
    • Step 6 and 7 - Catching Execution with EPT Violations (handle_ept_violation())
    • Step 8 - Handling VMCALL Hooks (handle_vmcall())
    • Step 9 - Single-Stepping with Monitor Trap Flag (handle_monitor_trap_flag())
    • Catching Read/Write Violations (handle_ept_violation())
  • Illusion Execution Trace: Proof-of-Concept Walkthrough
    • Controlling EPT Hooks via Hypercalls
• Matrix: Windows Kernel Driver-Based Hypervisor Using Dual EPT
  • Initializing Primary and Secondary EPTs (virtualize_system())
  • Step 1 and 2 - Creating Shadow Hooks and Setting Up Trampolines (hook_function_ptr())
  • Step 3, 4, 5 and 6 - Dual-EPT Remapping for Shadow Execution (enable_hooks())
  • Step 7 - Configuring VMCS for Breakpoint VM-Exits (setup_vmcs_control_fields())
  • Step 8 - Handling EPT Violations with Dynamic EPTP Switching (handle_ept_violation())
  • Step 9 - Redirecting Execution via Breakpoint Handlers (handle_breakpoint_exception())
  • Step 10 - Returning via Trampoline to Original Guest Function (mm_is_address_valid() and nt_create_file())
  • Matrix Execution Trace: Proof-of-Concept Walkthrough
• Hook Redirection Techniques: INT3, VMCALL, and JMP
• Hypervisor Detection Vectors
• Appendix
  • Guest-Assisted Hooking Model
  • Comparing EPT Hooking Models: Per-Core vs Shared
    • Matrix (Shared EPT Across All Logical Processors)
    • Illusion (Per-Logical-Processor EPTs with MTF)
• Conclusion
  • Acknowledgments, References, and Inspirations
    • Articles, Tools, and Research References
    • Community Research and Inspirations
    • Acknowledgments
    • Documentation and Specifications

Illusion: UEFI-Based Hypervisor with EPT-Based Hooking

Illusion is a UEFI-based hypervisor designed for early boot-time memory introspection and syscall hooking. It was developed after matrix-rs, with a simpler design, better structure, and a focus on controlling execution without touching guest memory.

Unlike matrix, which operates from kernel mode with dual-EPT support shared across all logical processors, illusion runs from UEFI firmware and uses a single EPT per-logical processor to shadow and detour guest execution. Some hypervisors extend this design further by using one, two, three, or more EPTs - for example, maintaining separate EPTs for different execution stages or process contexts. Others also implement per-logical processor EPT isolation for tighter control. Hooks in illusion are applied using execute-only shadow pages combined with VMCALL and Monitor Trap Flag (MTF) single-stepping for memory introspection. While Illusion prioritizes early boot visibility and minimal guest interference, it also supports runtime control via user-mode CPUID hypercalls. As with all EPT-based hooking techniques, the architecture comes with trade-offs in design, maintainability, complexity, and detection risk - but those nuances are out of scope for this post.

The following diagram shows how this technique is implemented in the illusion-rs hypervisor, specifically how EPT is used to hook kernel memory. While in this example it’s applied early in the boot process, the same hooking logic can also be triggered later - such as from user-mode - if the hypervisor is signaled to enable or disable the hooks.

Figure 1: Control flow of EPT-based function hooking in the Illusion UEFI hypervisor

Each step shown in the diagram is explained in detail in the sections below.

Setting up IA32_LSTAR MSR hook during Initialization (initialize_shared_hook_manager())

To resolve the physical and virtual base addresses and the size of the Windows kernel, we intercept writes to the IA32_LSTAR MSR. This register holds the address of the syscall handler, which Windows sets to its kernel-mode dispatcher, KiSystemCall64. When a WRMSR VM-exit occurs, we check if the MSR ID corresponds to IA32_LSTAR. If so, we extract the MSR value and scan memory backwards from that address to locate the MZ signature, which marks the start of the ntoskrnl.exe PE image, thereby determining its base virtual address. The purpose of intercepting IA32_LSTAR is not to modify syscall behavior, but to reliably extract the kernel’s loaded base address during early boot. It’s a reliable anchor point because Windows always writes to this MSR during early boot to set up KiSystemCall64.

It’s important to note that this is not an inline hook - rather, it’s a VM-exit-based intercept triggered by MSR writes. The following code shows how IA32_LSTAR interception is applied during hypervisor initialization:

Code Reference (hook_manager.rs)

trace!("Modifying MSR interception for LSTAR MSR write access");
hook_manager
    .msr_bitmap
    .modify_msr_interception(msr::IA32_LSTAR, MsrAccessType::Write, MsrOperation::Hook);

Handling WRMSR to IA32_LSTAR in [handle_msr_access()]: Unhook and Call [set_kernel_base_and_size()]

When a WRMSR VM-exit is triggered by the IA32_LSTAR hook during early kernel setup, the handle_msr_access() function unhooks the MSR and calls set_kernel_base_and_size() to resolve the kernel’s base addresses and size.

Code Reference (msr.rs)

if msr_id == msr::IA32_LSTAR {
    trace!("IA32_LSTAR write attempted with MSR value: {:#x}", msr_value);
    hook_manager.msr_bitmap.modify_msr_interception(
        msr::IA32_LSTAR,
        MsrAccessType::Write,
        MsrOperation::Unhook,
    );

    hook_manager.set_kernel_base_and_size(msr_value)?;
}

At this point in boot, the syscall entry point (KiSystemCall64) has been fully resolved by the kernel. We use its address as a scanning base to locate the start of the PE image and compute the physical base of ntoskrnl.exe.

Setting Kernel Image Base Address and Size (set_kernel_base_and_size())

We pass the MSR value to set_kernel_base_and_size, which internally calls get_image_base_address to scan memory backwards for the MZ (IMAGE_DOS_SIGNATURE) header. It then uses pa_from_va_with_current_cr3 to translate the virtual base address to a physical address using the guest’s CR3, and finally calls get_size_of_image to retrieve the size of ntoskrnl.exe from the OptionalHeader.SizeOfImage field. These operations are inherently unsafe, so it’s crucial that the correct values are passed in - otherwise, they may lead to a system crash.

Code Reference (hook_manager.rs)

self.ntoskrnl_base_va = unsafe { get_image_base_address(guest_va)? };
self.ntoskrnl_base_pa = PhysicalAddress::pa_from_va_with_current_cr3(self.ntoskrnl_base_va)?;
self.ntoskrnl_size = unsafe { get_size_of_image(self.ntoskrnl_base_pa as _).ok_or(HypervisorError::FailedToGetKernelSize)? } as u64;

Detecting When SSDT Is Loaded Inside ntoskrnl.exe

Before performing EPT-based hooks on kernel functions like NtCreateFile, it is important to ensure that the System Service Descriptor Table (SSDT) has been fully initialized by the Windows kernel. Otherwise, a race condition is introduced: if hooks are applied too early, there’s a risk of targeting invalid memory when the hypervisor attempts to resolve function addresses via syscall numbers through the SSDT - a fallback used only when the function is missing from ntoskrnl.exe’s export table. This can result in a system crash. Analysis of execution paths inside ntoskrnl.exe revealed a reliable point after SSDT initialization, but still early enough in kernel setup to monitor other software invoking those functions.

Analysis of KiInitializeKernel - the core routine responsible for initializing the kernel on each processor - shows that it finalizes the SSDT by invoking KeCompactServiceTable. From this point onward, it becomes safe to install hooks. However, a reliable and repeatable trigger is still needed - ideally, any unconditional VM-exit that occurs shortly after KeCompactServiceTable is called.

Figure 2: KeCompactServiceTable() and KiSetCacheInformation() observed in KiInitializeKernel() using Binary Ninja, confirming the post-SSDT call sequence.

This is where KiSetCacheInformation becomes useful. It is invoked immediately after SSDT setup and triggers a well-defined sequence that includes CPUID instructions. On Intel CPUs, KiSetCacheInformation calls KiSetStandardizedCacheInformation, which begins issuing cpuid(4, 0) to query cache topology. The CPUID instruction unconditionally causes a VM-exit on Intel processors, and may cause a VM-exit on AMD processors depending on the intercept configuration, offering a reliable and deterministic point to synchronize EPT hook installation. This makes CPUID a convenient instruction to synchronize state transitions or trigger early hypervisor logic without guest cooperation.

Figure 3: KiSetCacheInformation() and KiSetCacheInformationAmd() observed in Binary Ninja, both invoking KiSetStandardizedCacheInformation() which executes CPUID after SSDT setup.

Historically, Intel systems used the path KiSetCacheInformation -> KiSetCacheInformationIntel -> KiSetStandardizedCacheInformation. On recent Windows 10 and 11 builds, the intermediate call to KiSetCacheInformationIntel appears to have been removed - KiSetCacheInformation now calls KiSetStandardizedCacheInformation directly on Intel platforms.

On Intel processors, the execution path is reliable (verified via Binary Ninja analysis on Windows 11 build 26100):

KiInitializeKernel
-> KeCompactServiceTable
-> KiSetCacheInformation
-> KiSetStandardizedCacheInformation
-> cpuid(4, 0)

On AMD processors, the path is conditional (verified via Binary Ninja analysis on Windows 11 build 26100):

• If bit 22 (TopologyExtensions) in CPUID(0x80000001).ECX is set:

KiInitializeKernel
-> KeCompactServiceTable
-> KiSetCacheInformation
-> KiSetCacheInformationAmd
-> KiSetStandardizedCacheInformation
-> cpuid(0x8000001D, 0)

This bit indicates that the processor supports CPUID(0x8000001D), which enumerates cache and topology info in a standardized way. If unset, the OS must fall back to 0x80000005 / 0x80000006.

• Otherwise (fallback path without TopologyExtensions support):

KiInitializeKernel
-> KeCompactServiceTable
-> KiSetCacheInformation
-> KiSetCacheInformationAmd
-> cpuid(0x80000005) and cpuid(0x80000006)

Although cpuid(4, 0) on Intel and cpuid(0x8000001D, 0) on AMD are executed shortly after SSDT setup in tested Windows builds, this hypervisor uses cpuid(2, 0) instead. This was a mistake carried over from early development - cpuid(0x2) is not part of the same KiSetCacheInformation() path and isn’t a deterministic indicator of SSDT completion. It happened to fire reliably during boot on test systems, which made it “good enough” at the time. Since the project is no longer actively maintained, the code was left as-is - but for anyone adapting this for production use, hooking cpuid(4, 0) or cpuid(0x8000001D) is the correct path.

Setting Up EPT Hooks (handle_cpuid())

The CPUID instruction executes multiple times during early boot, which can lead to redundant VM-exits. To avoid repeated hook setup, the hypervisor uses a has_cpuid_cache_info_been_called flag. The hook only needs to run once, after SSDT initialization, making this a straightforward and stable timing marker.

Code Reference (cpuid.rs)

match leaf {
    leaf if leaf == CpuidLeaf::CacheInformation as u32 => {
        trace!("CPUID leaf 0x2 detected (Cache Information).");
        if !hook_manager.has_cpuid_cache_info_been_called {
            hook_manager.manage_kernel_ept_hook(
                vm,
                crate::windows::nt::pe::djb2_hash("NtCreateFile".as_bytes()),
                0x0055,
                crate::intel::hooks::hook_manager::EptHookType::Function(
                    crate::intel::hooks::inline::InlineHookType::Vmcall
                ),
                true,
            )?;
            hook_manager.has_cpuid_cache_info_been_called = true;
        }
    }
}

This ensures that we only apply our EPT function hook after the SSDT has been initialized and guarantees that subsequent CPUID calls won’t re-trigger the hook logic.

Resolving Targets and Dispatching Hooks (manage_kernel_ept_hook())

Let’s break down what the manage_kernel_ept_hook function does. It manages the installation or removal of an Extended Page Table (EPT) hook on a target kernel function, such as NtCreateFile.

The logic is straightforward: given a hashed function name and a syscall number, it first tries to resolve the function’s virtual address using get_export_by_hash, which checks the export table of ntoskrnl.exe. If that fails, it falls back to resolving the function using its syscall number through the System Service Descriptor Table (SSDT).

If enable == true, it calls ept_hook_function(), which installs the hook by shadowing the guest memory and modifying EPT permissions - more on this later. If enable == false, it calls ept_unhook_function() to restore the original mapping and unhook the function.

Code Reference (hook_manager.rs)

pub fn manage_kernel_ept_hook(
    &mut self,
    vm: &mut Vm,
    function_hash: u32,
    syscall_number: u16,
    ept_hook_type: EptHookType,
    enable: bool,
) -> Result<(), HypervisorError> {
    let action = if enable { "Enabling" } else { "Disabling" };
    debug!("{} EPT hook for function: {:#x}", action, function_hash);

    trace!("Ntoskrnl base VA: {:#x}", self.ntoskrnl_base_va);
    trace!("Ntoskrnl base PA: {:#x}", self.ntoskrnl_base_pa);
    trace!("Ntoskrnl size: {:#x}", self.ntoskrnl_size);

    let function_va = unsafe {
        if let Some(va) = get_export_by_hash(self.ntoskrnl_base_pa as _, self.ntoskrnl_base_va as _, function_hash) {
            va
        } else {
            let ssdt_function_address =
                SsdtHook::find_ssdt_function_address(syscall_number as _, false, self.ntoskrnl_base_pa as _, self.ntoskrnl_size as _);
            match ssdt_function_address {
                Ok(ssdt_hook) => ssdt_hook.guest_function_va as *mut u8,
                Err(_) => return Err(HypervisorError::FailedToGetExport),
            }
        }
    };

    if enable {
        self.ept_hook_function(vm, function_va as _, function_hash, ept_hook_type)?;
    } else {
        self.ept_unhook_function(vm, function_va as _, ept_hook_type)?;
    }

    Ok(())
}

Second-Level Address Translation (SLAT): EPT (Intel) and NPT (AMD)

Before we get into the specifics of syscall hooks and memory interception, it’s worth covering how this all works under the hood - especially for readers who aren’t already familiar with memory virtualization.

Second-Level Address Translation (SLAT) - also known as nested paging - is a hardware virtualization feature that allows the hypervisor to define a second layer of page translation. The CPU then uses this hypervisor-defined mapping to translate guest physical addresses to host physical addresses without requiring software intervention on each memory access. Second-Level Address Translation (SLAT) introduces an additional layer of address translation between guest physical addresses (GPAs) and host physical addresses (HPAs).

The guest OS configures its own page tables to translate guest virtual addresses (GVAs) to guest physical addresses (GPAs), while the hypervisor configures extended or nested page tables (e.g., EPT or NPT) to translate those GPAs to HPAs. Both stages are carried out by the hardware MMU during memory access, not by software.

The two most common SLAT implementations are Intel’s Extended Page Tables (EPT) under VT-x, and AMD’s Nested Page Tables (NPT) under SVM. These technologies allow guest operating systems to manage their own page tables independently, while the hypervisor handles the second level of memory translation.

To illustrate the first stage of this process - from guest virtual address (GVA) to guest physical address (GPA) - the diagram below shows how a 48-bit x64 virtual address is resolved using traditional paging inside the guest. This is exactly what the guest OS configures, regardless of whether SLAT is enabled.

Figure 4: Traditional x64 virtual address translation as performed by the guest OS (source: Guided Hacking, YouTube)

EPT Hooking Overview (build_identity())

When the hypervisor starts, it sets up Extended Page Tables (EPT) to create a 1:1 identity map - guest physical addresses are mapped directly to the same host physical addresses. This identity mapping allows the guest to run normally, while the hypervisor controls memory access at the page level without interfering with the guest’s own page tables.

The function responsible for setting this up is build_identity(). The first 2MB of memory is mapped using 4KB EPT page tables. All remaining guest physical addresses are mapped using 2MB large pages, unless finer granularity is required - such as when placing hooks.

While it’s also possible to use 1GB pages, illusion-rs opts for 2MB mappings to simplify EPT management and ensure compatibility with platforms like VMware, which do not support 1GB EPT pages. Since Illusion was tested under VMware, 2MB pages were the most practical choice for early boot introspection and syscall hooking.

Code Reference (ept.rs)

/// Represents the entire Extended Page Table structure.
///
/// EPT is a set of nested page tables similar to the standard x86-64 paging mechanism.
/// It consists of 4 levels: PML4, PDPT, PD, and PT.
///
/// Reference: Intel® 64 and IA-32 Architectures Software Developer's Manual: 29.3.2 EPT Translation Mechanism
#[repr(C, align(4096))]
pub struct Ept {
    /// Page Map Level 4 (PML4) Table.
    pml4: Pml4,
    /// Page Directory Pointer Table (PDPT).
    pdpt: Pdpt,
    /// Array of Page Directory Table (PDT).
    pd: [Pd; 512],
    /// Page Table (PT).
    pt: Pt,
}

pub fn build_identity(&mut self) -> Result<(), HypervisorError> {
    let mut mtrr = Mtrr::new();
    trace!("{mtrr:#x?}");
    trace!("Initializing EPTs");

    let mut pa = 0u64;

    self.pml4.0.entries[0].set_readable(true);
    self.pml4.0.entries[0].set_writable(true);
    self.pml4.0.entries[0].set_executable(true);
    self.pml4.0.entries[0].set_pfn(addr_of!(self.pdpt) as u64 >> BASE_PAGE_SHIFT);

    for (i, pdpte) in self.pdpt.0.entries.iter_mut().enumerate() {
        pdpte.set_readable(true);
        pdpte.set_writable(true);
        pdpte.set_executable(true);
        pdpte.set_pfn(addr_of!(self.pd[i]) as u64 >> BASE_PAGE_SHIFT);

        for pde in &mut self.pd[i].0.entries {
            if pa == 0 {
                pde.set_readable(true);
                pde.set_writable(true);
                pde.set_executable(true);
                pde.set_pfn(addr_of!(self.pt) as u64 >> BASE_PAGE_SHIFT);

                for pte in &mut self.pt.0.entries {
                    let memory_type = mtrr
                        .find(pa..pa + BASE_PAGE_SIZE as u64)
                        .ok_or(HypervisorError::MemoryTypeResolutionError)?;
                    pte.set_readable(true);
                    pte.set_writable(true);
                    pte.set_executable(true);
                    pte.set_memory_type(memory_type as u64);
                    pte.set_pfn(pa >> BASE_PAGE_SHIFT);
                    pa += BASE_PAGE_SIZE as u64;
                }
            } else {
                let memory_type = mtrr
                    .find(pa..pa + LARGE_PAGE_SIZE as u64)
                    .ok_or(HypervisorError::MemoryTypeResolutionError)?;

                pde.set_readable(true);
                pde.set_writable(true);
                pde.set_executable(true);
                pde.set_memory_type(memory_type as u64);
                pde.set_large(true);
                pde.set_pfn(pa >> BASE_PAGE_SHIFT);
                pa += LARGE_PAGE_SIZE as u64;
            }
        }
    }

    Ok(())
}

This identity map is later used when installing EPT hooks. It allows the hypervisor to shadow guest memory, modify EPT permissions (like making a page execute-only), and safely redirect execution to hook logic - all without modifying guest memory directly.

Installing the Hook Payload (ept_hook_function())

The ept_hook_function() is the heart of the EPT-based function hooking logic in Illusion. This is where a selected guest function is shadowed, modified, and hooked - all without touching the original memory. Execution is redirected by changing EPT permissions to point to a modified shadow page instead of the original, allowing introspection and control without altering guest state.

This section explains what the function does, which internal calls it makes, and why each step is necessary. Steps 1 through Step 9 correspond to the diagram shown earlier in the article.

Code Reference (hook_manager.rs)

Mapping the Large Page (map_large_page_to_pt())

We begin by ensuring the 2MB large page that contains the target function is registered in the hypervisor’s internal memory management structures. The illusion-rs hypervisor operates with a 1:1 identity mapping between Guest Physical Addresses (GPA) and Host Physical Addresses (HPA), but before any manipulation or permission control can occur, we must first associate this large page with a pre-allocated page table.

These pre-allocated page tables are not allocated dynamically at runtime - instead, a fixed-size pool is reserved at hypervisor startup as part of a pre-allocated heap defined by the user. This memory is shared across all logical processors and is used to back internal structures such as shadow pages and page tables. The heap uses a linked list-based allocator (similar to a classic free-list strategy, not slab or buddy), with allocations performed from a contiguous block of memory (defaulting to 64MB). While the exact number of supported allocations depends on user-defined sizing and workload patterns, all allocations are strictly bounded. If the pool is exhausted, further allocations will fail at the point of use, likely triggering a panic unless explicitly handled.

By calling map_large_page_to_pt(), we link the GPA of the large page to a known internal structure, allowing for controlled splitting, shadowing, and permission enforcement. This also makes it easier to track and restore the original page mappings when hooks need to be removed or toggled later.

self.memory_manager.map_large_page_to_pt(guest_large_page_pa.as_u64())?;

Step 1 - Splitting the Page (is_large_page() -> split_2mb_to_4kb())

When a target function resides within a 2MB large page, changing its permissions would affect the entire region - potentially disrupting unrelated code and triggering VM-exits across the full range. To avoid this, we check if the region is backed by a large page and, if so, split it into 512 individual 4KB entries using a pre-allocated page table. This provides the fine-grained control necessary for isolated function hooking, ensuring only the targeted page generates VM-exits.

if vm.primary_ept.is_large_page(guest_page_pa.as_u64()) {
    let pre_alloc_pt = self
        .memory_manager
        .get_page_table_as_mut(guest_large_page_pa.as_u64())
        .ok_or(HypervisorError::PageTableNotFound)?;

    vm.primary_ept.split_2mb_to_4kb(guest_large_page_pa.as_u64(), pre_alloc_pt)?;
}

Shadowing the Page (is_guest_page_processed() -> map_guest_to_shadow_page())

Before installing any detours, we first check whether a shadow page has already been allocated and mapped for the target guest page. If a mapping already exists, it means this page was previously processed and no further action is needed. Otherwise, we pull a shadow page from our pre-allocated pool and associate it with the guest page using map_guest_to_shadow_page(). This ensures hooks aren’t redundantly reinstalled and prevents multiple shadow pages from being created for the same target. It’s essential for correctness: when a VM-exit occurs due to an EPT violation, we must be able to reliably retrieve the shadow page associated with the faulting guest page.

if !self.memory_manager.is_guest_page_processed(guest_page_pa.as_u64()) {
    self.memory_manager.map_guest_to_shadow_page(
        guest_page_pa.as_u64(),
        guest_function_va,
        guest_function_pa.as_u64(),
        ept_hook_type,
        function_hash,
    )?;
}

Step 2 - Cloning the Code (unsafe_copy_guest_to_shadow())

Once the shadow page has been allocated and mapped, we clone the guest’s original 4KB page into it using unsafe_copy_guest_to_shadow(). This creates a byte-for-byte replica of the guest memory that we can safely modify. Because we perform all modifications in this isolated shadow copy - rather than directly in guest memory - we avoid detection by integrity verification checks like PatchGuard and preserve the original code for future restoration.

let shadow_page_pa = PAddr::from(
    self.memory_manager
        .get_shadow_page_as_ptr(guest_page_pa.as_u64())
        .ok_or(HypervisorError::ShadowPageNotFound)?,
);

Self::unsafe_copy_guest_to_shadow(guest_page_pa, shadow_page_pa);

Step 3 - Installing the Inline Hook

Once the shadow page is prepared, we compute the exact offset where the target function resides relative to the start of the page. This ensures the hook is applied at the correct instruction boundary. At that offset, we insert an inline detour - typically using a VMCALL opcode - which causes a controlled VM-exit whenever the hooked function is executed. This redirection is handled entirely within the hypervisor.

Traditional JMP-based hooks are avoided here because the hypervisor operates outside the guest’s address space in a UEFI context. While it is technically possible to inject hook logic into guest memory (as explored in early versions of illusion-rs), the EPT + VMCALL approach was chosen to keep logic fully on the host side and as a learning experience. For more background on the guest-assisted design, see Appendix: Guest-Assisted Hooking Model.

let shadow_function_pa = PAddr::from(Self::calculate_function_offset_in_host_shadow_page(shadow_page_pa, guest_function_pa));

InlineHook::new(shadow_function_pa.as_u64() as *mut u8, inline_hook_type).detour64();

Step 4 - Revoking Execute Rights (modify_page_permissions())

To ensure our detour is triggered, we revoke execute permissions on the guest’s original page via the EPT. This causes any instruction fetch from that page to generate a VM-exit due to an EPT violation. The hypervisor can then handle this event and reroute execution to the shadow page where our hook is installed. Importantly, we retain read and write permissions on the original page to maintain system stability and avoid triggering protection features like PatchGuard.

vm.primary_ept.modify_page_permissions(
    guest_page_pa.as_u64(),
    AccessType::READ_WRITE,
    pre_alloc_pt,
)?;

Step 5 - Invalidating TLB and EPT Caches (invept_all_contexts())

Once the execute permission is removed from the original guest page and replaced with a shadowed hook, the CPU’s internal caches may still contain stale translations. To ensure the updated EPT mappings take effect immediately, the hypervisor flushes the virtualization translation caches using the INVEPT instruction.

invept_all_contexts();

This call performs an All Contexts invalidation, instructing the CPU to discard all EPT-derived translations for the current EPT pointer (EPTP). Per Intel’s SDM, this ensures that stale mappings are removed regardless of any associated VPID or PCID values.

Because EPT translations are cached per logical processor, INVEPT must be executed on each vCPU, regardless of whether the hypervisor uses shared or per-core EPTs. Without proper synchronization, race conditions may occur during thread migration or instruction replay, potentially leading to stale mappings and inconsistent hook behavior across cores.

INVVPID is not necessary here. It’s used to invalidate guest-virtual mappings tied to VPIDs, which is unrelated to EPT-based translation. For our use case - modifying guest-physical EPT mappings - INVEPT alone is sufficient.

This step completes the hook installation pipeline. From this point forward, the guest kernel continues to operate normally, but any attempt to execute the hooked function will trigger an EPT violation, allowing the hypervisor to intercept the execution path - all without modifying guest memory.

Step 6 and 7 - Catching Execution with EPT Violations (handle_ept_violation())

After an EPT violation VM-exit occurs, the first step is identifying which page triggered the fault. We read the faulting Guest Physical Address (GPA) from the VMCS and align it to the 4KB and 2MB page boundaries. This lets us resolve which specific page was accessed and prepares us to look it up in the shadow page tracking structures.

Code Reference (ept_violation.rs)

let guest_pa = vmread(vmcs::ro::GUEST_PHYSICAL_ADDR_FULL);
let guest_page_pa = PAddr::from(guest_pa).align_down_to_base_page();
let guest_large_page_pa = guest_page_pa.align_down_to_large_page();

Once we have the faulting guest page address, we retrieve the corresponding shadow page that was previously mapped and prepared during hook installation. This page contains our modified copy of the function with a VMCALL detour inserted. Shadow page lookup failures indicate unexpected guest behavior - such as an EPT execute violation without a corresponding shadow mapping - and are treated as fatal errors. If no shadow page is found for the faulting guest page, it likely indicates an unexpected EPT violation not associated with an installed hook. In illusion-rs, this condition is treated as a fatal error and terminates VM-exit handling. In a production-grade hypervisor, such cases should be logged and handled more gracefully to detect guest misbehavior, memory tampering, or logic errors in hook tracking.

let shadow_page_pa = PAddr::from(
    hook_manager
        .memory_manager
        .get_shadow_page_as_ptr(guest_page_pa.as_u64())
        .ok_or(HypervisorError::ShadowPageNotFound)?
);

Before deciding how to respond, we inspect the cause of the violation by reading the EXIT_QUALIFICATION field. This tells us what kind of access the guest attempted - whether it was trying to read, write, or execute memory - and lets us act accordingly.

let exit_qualification_value = vmread(vmcs::ro::EXIT_QUALIFICATION);
let ept_violation_qualification = EptViolationExitQualification::from_exit_qualification(exit_qualification_value);

If the violation indicates an attempt to execute a non-executable page (i.e., it’s readable and writable but not executable), we swap in our shadow page and mark it as execute-only. This redirects execution to our tampered memory, where the inline hook (e.g., VMCALL) resides, allowing the hypervisor to take control.

if ept_violation_qualification.readable && ept_violation_qualification.writable && !ept_violation_qualification.executable {
    vm.primary_ept.swap_page(guest_page_pa.as_u64(), shadow_page_pa.as_u64(), AccessType::EXECUTE, pre_alloc_pt)?;
}

This redirection hands execution over to our shadow page - a byte-for-byte clone of the original memory - where the first few instructions have been overwritten with a VMCALL. At this point, guest execution resumes without advancing RIP, meaning the CPU re-executes the same instruction - but now from the shadow page. When the CPU reaches the VMCALL instruction, it triggers another VM-exit. Because we’ve displaced the function’s original prologue, those instructions must later be restored and replayed under Monitor Trap Flag (MTF) single-stepping. In the Matrix Windows kernel driver-based hypervisor, the shadow page contains an INT3 hook that triggers a VM-exit; the hypervisor sets the guest RIP to the hook handler, performs introspection, and then returns execution via a trampoline. In illusion (a UEFI-based hypervisor), EPT + MTF was chosen instead. This allowed execution redirection to occur entirely from host-side logic, as a simpler and educational approach, without requiring guest-mode memory allocation or in-guest control flow setup. (For alternative designs involving guest memory injection, see Appendix: Guest-Assisted Hooking Model.)

Step 8 - Handling VMCALL Hooks (handle_vmcall())

The VMCALL instruction is inserted by our inline hook as the first instruction in the shadowed function. When executed, it causes an unconditional VM-exit, transferring control to the hypervisor. This lets us detect exactly when the guest invokes the hooked function.

Code Reference (vmcall.rs)

We begin by resolving the guest physical page that triggered the VMCALL, and check whether it belongs to a shadow page previously registered by the hook manager. If the page is found in our shadow mapping infrastructure, we know execution originated from a function we’ve hooked. This conditional check ensures we’re handling a legitimate hook-triggered exit before proceeding with further memory transitions and state changes. At this point, we know exactly which function was called, and with full control in the hypervisor, we can inspect its arguments, trace its execution, and introspect guest memory or registers as needed.

let exit_type = if let Some(shadow_page_pa) = hook_manager.memory_manager.get_shadow_page_as_ptr(guest_page_pa.as_u64()) {
    let pre_alloc_pt = hook_manager
        .memory_manager
        .get_page_table_as_mut(guest_large_page_pa.as_u64())
        .ok_or(HypervisorError::PageTableNotFound)?;

After completing any introspection or analysis - such as inspecting arguments, tracing execution, or examining guest memory - in the hypervisor, we begin restoring guest state. Specifically, we swap back the original (unmodified) guest page and temporarily restore READ_WRITE_EXECUTE permissions. This is required to safely execute the instructions that were originally overwritten by our inline VMCALL detour (typically 2 - 5 bytes at the prologue of the target function).

vm.primary_ept.swap_page(guest_page_pa.as_u64(), guest_page_pa.as_u64(), AccessType::READ_WRITE_EXECUTE, pre_alloc_pt)?;

Before enabling MTF, we retrieve the hook metadata and determine how many instructions were displaced by the inline VMCALL. Simply restoring the page and continuing execution would risk a crash - since the prologue was never executed - and leave the function unmonitored. To prevent this, we need to single-step through the displaced instructions using MTF. Before resuming the guest, we initialize a replay counter, set the Monitor Trap Flag (MTF), and disable guest interrupts to prevent unexpected interrupt handling during single-stepping, instruction-by-instruction re-execution. This step sets up the replay process that continues in the next section.

let instruction_count = HookManager::calculate_instruction_count(...);
vm.mtf_counter = Some(instruction_count);
set_monitor_trap_flag(true);
update_guest_interrupt_flag(vm, false)?;

If no shadow mapping is found for the faulting guest page, the VMCALL is assumed to be invalid or executed from an unexpected context. To emulate expected CPU behavior, illusion-rs injects a #UD (undefined instruction) exception, consistent with how the processor handles VMCALL outside VMX operation.

Step 9 - Single-Stepping with Monitor Trap Flag (handle_monitor_trap_flag())

Monitor Trap Flag (MTF) enables the hypervisor to single-step through the instructions that were displaced by the inline VMCALL. Each instruction executed by the guest causes a VM-exit, at which point we decrement the instruction replay counter.

Code Reference (mtf.rs)

*counter = counter.saturating_sub(1);

Execution continues one instruction at a time under hypervisor supervision until all overwritten bytes have been replayed. Once the counter reaches zero, we know the prologue has been fully restored. At this point, we reapply the hook by swapping the shadow page back in and setting it as execute-only, ensuring the next invocation of this function once again triggers a VMCALL.

vm.primary_ept.swap_page(guest_pa.align_down_to_base_page().as_u64(), shadow_page_pa.as_u64(), AccessType::EXECUTE, pre_alloc_pt)?;

Finally, we disable MTF - by simply omitting set_monitor_trap_flag(true) - and re-enable guest interrupts, allowing the guest to resume execution cleanly.

restore_guest_interrupt_flag(vm)?;

This completes the detour cycle. The guest continues uninterrupted, unaware that its control flow was temporarily redirected through our hypervisor.

Catching Read/Write Violations (handle_ept_violation())

Sometimes, the guest may attempt to read or write from a page that’s currently marked as execute-only. Since EPT enforces strict access permissions, this triggers an EPT violation VM-exit - this time due to a read or write on a page that lacks the appropriate permissions.

Code Reference (ept_violation.rs)

if ept_violation_qualification.executable && !ept_violation_qualification.readable && !ept_violation_qualification.writable {
    vm.primary_ept.swap_page(guest_page_pa.as_u64(), guest_page_pa.as_u64(), AccessType::READ_WRITE_EXECUTE, pre_alloc_pt)?;
    vm.mtf_counter = Some(1);
    set_monitor_trap_flag(true);
    update_guest_interrupt_flag(vm, false)?;
}

To handle this safely, we temporarily restore the original guest page with full read, write, and execute access. This ensures the instruction executes successfully - even if it uses RIP-relative addressing or accesses data on the same page - preventing a VM-exit loop, system crashes, or exposure of the hook. We then enable Monitor Trap Flag (MTF) and step forward a single instruction before reapplying the original hook, preserving stealth and stability.

Illusion Execution Trace: Proof-of-Concept Walkthrough

This Proof-of-Concept (PoC) demonstrates how the Illusion hypervisor integrates early boot-time EPT hooking with a user-mode control channel. After initializing the hypervisor from UEFI, a command-line utility communicates using intercepted CPUID instructions to toggle kernel hooks in real-time - without requiring kernel-mode drivers or directly modifying guest virtual or physical memory.

Controlling EPT Hooks via Hypercalls

Before testing the hook logic, we first launch the hypervisor directly from the UEFI shell. This ensures that the hypervisor is loaded at boot and remains isolated from the Windows kernel.

Figure 5: Booting the Illusion hypervisor directly from the UEFI shell

Once loaded, we can issue commands from user-mode using a simple client. This CLI utility interfaces with a password-protected backdoor exposed by the hypervisor. The communication channel is implemented using the CPUID instruction - a widely used and unprivileged x86 instruction that reliably causes a VM-exit when intercepted. Since CPUID is an unprivileged instruction available to user-mode, this allows us to implement stealthy hypercalls without needing any kernel-mode components.

Figure 6: Command-line utility controlling kernel hooks via CPUID hypercalls

The client can enable or disable hooks for specific syscall functions (like NtCreateFile) in real-time. This is especially useful for introspection tools where the hook lifecycle must be externally controlled.

The image below demonstrates a live EPT hook in action. On the left, we see the hypervisor logs tracking the hook process: the 2MB page is first associated with a pre-allocated page table, then split into 512 individual 4KB entries. A shadow page is pulled from a pre-allocated pool and mapped to the target guest page. The guest’s original 4KB memory is cloned into the shadow page, a VMCALL inline hook is inserted, and execute permissions are revoked on the original page. This detour is used to trigger a VM-exit when the function executes. On the right, WinDbg confirms that the shadow-mapped address (0xab0c360) correctly contains the VMCALL opcode (0f01c1), and that the original NtCreateFile at 0xfffff8005de16360 remains untouched.

This keeps the hook invisible at the virtual memory level: the original GVA still resolves to the same GPA, but the hypervisor rewires the final mapping to the HPA of the shadow page. From the guest’s typical perspective (unless inspecting physical memory), the memory appears unmodified - yet the hook is live.

Figure 7: Debug logs and WinDbg output demonstrating stealth EPT hook execution

Matrix: Windows Kernel Driver-Based Hypervisor Using Dual EPT

Matrix is a Windows kernel driver-based hypervisor built for runtime introspection and syscall redirection. It was developed before illusion-rs, but explores a different approach: instead of running from firmware, Matrix installs as a Windows driver and operates from kernel mode, leveraging two Extended Page Table (EPT) contexts - one for the original memory and another for shadowed pages that contain hook logic.

Unlike Illusion, which sets up a single EPT and uses MTF-based control at boot, Matrix uses dual EPTs to trap execution dynamically. This allows us to configure execute-only hooks, remap guest pages without modifying them, and control function redirection at runtime. Our implementation toggles between the two EPTs - the primary EPT for normal guest execution, and the secondary EPT for redirected flows - using dynamic EPTP switching triggered by VM-exits. Some hypervisors extend this design by using one, two, three, or more EPTs - for example, maintaining separate EPTs for different execution stages or process contexts. Some implementations also opt for per-logical processor EPT isolation. In contrast, matrix uses a minimal dual-EPT setup shared across all logical processors, focusing on simplicity and testability to demonstrate the core concept.

The diagram below shows how this works in Matrix: original pages lose execute permissions in the primary EPT, and are mirrored in the secondary EPT with EXECUTE-only rights, pointing to trampoline logic in a shadow copy. Runtime execution of the target function triggers a VM-exit, which we use to switch contexts and reroute control to the hook handler.

Figure 8: Control flow of dual-EPT based function hooking in the Matrix Windows kernel driver-based hypervisor

Each step shown in the diagram is explained in detail in the sections below.

Initializing Primary and Secondary EPTs (virtualize_system())

When our kernel-mode driver is loaded, we initialize virtualization by allocating and identity-mapping (1:1) two separate EPT contexts: one primary and one secondary. Both are initially set up with full READ_WRITE_EXECUTE permissions to mirror guest memory. The primary EPT provides a clean view of guest memory without interference, while the secondary EPT is where we apply shadowed pages for hooks. This dual mapping allows us to selectively redirect execution without touching the original memory, switching between EPTs as needed to trap and analyze function calls.

Code Reference (lib.rs)

primary_ept.identity_2mb(AccessType::READ_WRITE_EXECUTE)?;
secondary_ept.identity_2mb(AccessType::READ_WRITE_EXECUTE)?;

Step 1 and 2 - Creating Shadow Hooks and Setting Up Trampolines (hook_function_ptr())

Before enabling virtualization, we prepare our hooks by resolving target functions and setting up detours. We hook two kernel functions: MmIsAddressValid, resolved from the export table, and NtCreateFile, resolved from the SSDT by syscall number. For each, we create a trampoline to preserve the original prologue and allow clean return after our hook logic executes.

To do this, we copy the page containing the target function into a shadow region, calculate the function’s location within the copied page, and insert an inline INT3 breakpoint to trigger VM-exits. These hooks are added to our internal hook manager and remain dormant until the dual-EPT remapping is configured. While illusion-rs could have used the same approach, it instead uses VMCALL - partly to avoid breakpoint exceptions and partly just to try something different from what was already done in matrix-rs.

let mm_is_address_valid =
    Hook::hook_function("MmIsAddressValid", hook::mm_is_address_valid as *const ())
        .ok_or(HypervisorError::HookError)?;

if let HookType::Function { ref inline_hook } = mm_is_address_valid.hook_type {
    hook::MM_IS_ADDRESS_VALID_ORIGINAL
        .store(inline_hook.trampoline_address(), Ordering::Relaxed);
}

let ssdt_nt_create_file_addy = SsdtHook::find_ssdt_function_address(0x0055, false)?;

let nt_create_file_syscall_hook = Hook::hook_function_ptr(
    ssdt_nt_create_file_addy.function_address as _,
    hook::nt_create_file as *const (),
)
.ok_or(HypervisorError::HookError)?;

if let HookType::Function { ref inline_hook } = nt_create_file_syscall_hook.hook_type {
    hook::NT_CREATE_FILE_ORIGINAL.store(inline_hook.trampoline_address(), Ordering::Relaxed);
}

let hook_manager = HookManager::new(vec![mm_is_address_valid, nt_create_file_syscall_hook]);

We support hook creation using either a function name (hook_function) or a raw pointer (hook_function_ptr). The name-based method resolves a function from the kernel export table, while the pointer-based method is used for syscalls or undocumented routines where we locate the address via the SSDT. Internally, hook_function_ptr clones the 4KB page containing the target function into a shadow region, calculates the function’s offset within that page, and injects an inline INT3 (0xCC) breakpoint to trigger a VM-exit. To safely return to the original logic, FunctionHook::new builds a trampoline - a small stub that restores the overwritten bytes and performs a RIP-relative indirect jump (jmp qword ptr [rip+0]) back to the remainder of the original function. This ensures control flow resumes cleanly after our handler executes, without modifying guest memory.

Code Reference (hooks.rs)

let original_pa = PhysicalAddress::from_va(function_ptr);
let page = Self::copy_page(function_ptr)?;

let page_va = page.as_ptr() as *mut u64 as u64;
let page_pa = PhysicalAddress::from_va(page_va);

let hook_va = Self::address_in_page(page_va, function_ptr);
let hook_pa = PhysicalAddress::from_va(hook_va);

let inline_hook = FunctionHook::new(function_ptr, hook_va, handler)?;

Step 3, 4, 5 and 6 - Dual-EPT Remapping for Shadow Execution (enable_hooks())

Code Reference (hooks.rs)

After preparing our hooks, we configure the dual-EPT mappings to support shadow execution. For each hooked address, we split the containing 2MB page into 4KB entries in both EPTs. In the primary EPT, we mark the page as READ_WRITE, explicitly removing execute permissions. In the secondary EPT, we mark the same page as EXECUTE only and remap it to our shadow copy containing the inline hook and trampoline logic. This dual-view setup ensures that read and write accesses go through the original mapping in the primary EPT, while instruction fetches trigger execution from our detoured shadow page once we switch to the secondary EPT during an EPT violation later on.

primary_ept.split_2mb_to_4kb(original_page, AccessType::READ_WRITE_EXECUTE)?;
secondary_ept.split_2mb_to_4kb(original_page, AccessType::READ_WRITE_EXECUTE)?;

primary_ept.change_page_flags(original_page, AccessType::READ_WRITE)?;
secondary_ept.change_page_flags(original_page, AccessType::EXECUTE)?;

secondary_ept.remap_page(original_page, hooked_copy_page, AccessType::EXECUTE)?;

Step 7 - Configuring VMCS for Breakpoint VM-Exits (setup_vmcs_control_fields())

During VMCS setup, we configure the EXCEPTION_BITMAP to trap INT3 instructions, ensuring that breakpoint exceptions trigger a VM-exit. Execution starts with the primary_eptp loaded, providing the initial read/write view of guest memory.

Code Reference (vmcs.rs)

vmwrite(vmcs::control::EXCEPTION_BITMAP, 1u64 << (ExceptionInterrupt::Breakpoint as u32));
vmwrite(vmcs::control::EPTP_FULL, shared_data.primary_eptp);

Step 8 - Handling EPT Violations with Dynamic EPTP Switching (handle_ept_violation())

When the guest attempts to execute a page that has been marked non-executable in the primary EPT, we receive a VM-exit due to an EPT violation. In response, we switch to the secondary EPTP, which remaps the same GPA to an EXECUTE-only shadow page containing our detour. This allows the guest to continue executing from the hooked version of the function.

Code Reference (ept.rs)

let guest_physical_address = vmread(vmcs::ro::GUEST_PHYSICAL_ADDR_FULL);
let exit_qualification_value = vmread(vmcs::ro::EXIT_QUALIFICATION);
let ept_violation_qualification = EptViolationExitQualification::from_exit_qualification(exit_qualification_value);

if ept_violation_qualification.readable && ept_violation_qualification.writable && !ept_violation_qualification.executable {
    let secondary_eptp = unsafe { vmx.shared_data.as_mut().secondary_eptp };
    vmwrite(vmcs::control::EPTP_FULL, secondary_eptp);
}

If the guest later accesses the same page with a read or write operation - which is not permitted in the secondary EPT - we detect the violation and switch back to the primary EPTP, restoring full READ_WRITE access for data operations.

if !ept_violation_qualification.readable && !ept_violation_qualification.writable && ept_violation_qualification.executable {
    let primary_eptp = unsafe { vmx.shared_data.as_mut().primary_eptp };
    vmwrite(vmcs::control::EPTP_FULL, primary_eptp);
}

Matrix doesn’t currently handle mixed access patterns like RWX or RX within the same page, unlike Illusion which uses MTF to safely replay displaced instructions.

Step 9 - Redirecting Execution via Breakpoint Handlers (handle_breakpoint_exception())

When the guest executes the INT3 instruction embedded in the shadow page, a VM-exit is triggered due to the breakpoint exception. We resolve the guest’s current RIP and check if it matches any registered hook in our internal manager. If found, we redirect RIP to our hook handler, placing us in full control of execution. From here, we can inspect arguments, log activity, or introspect guest memory before returning to the original function using the preserved trampoline.

Code Reference (exceptions.rs)

if let Some(Some(handler)) = hook_manager.find_hook_by_address(guest_registers.rip).map(|hook| hook.handler_address()) {
    guest_registers.rip = handler;
    vmwrite(vmcs::guest::RIP, guest_registers.rip);
}

Step 10 - Returning via Trampoline to Original Guest Function (mm_is_address_valid() and nt_create_file())

After our hook logic runs, we forward execution back to the original kernel function using a trampoline. The handler retrieves the preserved entry point from an atomic global and safely casts it to the correct signature. This handoff ensures the guest continues as if uninterrupted, maintaining guest illusion.

Code Reference (hook.rs)

let fn_ptr = MM_IS_ADDRESS_VALID_ORIGINAL.load(Ordering::Relaxed);
let fn_ptr = unsafe { mem::transmute::<_, MmIsAddressValidType>(fn_ptr) };
fn_ptr(virtual_address as _)

let fn_ptr = NT_CREATE_FILE_ORIGINAL.load(Ordering::Relaxed);
let fn_ptr = unsafe { mem::transmute::<_, NtCreateFileType>(fn_ptr) };
fn_ptr(...)

Matrix Execution Trace: Proof-of-Concept Walkthrough

This screenshot captures a live EPT violation triggered when the guest executes MmIsAddressValid. The debug output (left) shows that an EXECUTE access on the original guest physical page at 0xfffff801695ad370 caused a VM-exit, as it had been stripped of execute permissions in the primary EPT. We respond by switching to the secondary EPT, where the guest physical address is remapped to a shadow copy located at 0x239d38370.

In the shadow page, we overwrite the function prologue with a single-byte INT3 instruction, causing a breakpoint exception. This results in another VM-exit, where we locate the hook, redirect guest RIP to the handler, and resume execution. After the handler completes, execution is transferred to a trampoline located at 0xffffdb0620809f90, which continues the original function. The trampoline performs this redirection via an indirect jmp qword ptr [0xffffdb0620809f9a], which resolves to 0xffffdb0620809f9a - the address immediately after the overwritten instruction - restoring execution flow.

Figure 9: Shadow Page Redirection and Trampoline Setup for MmIsAddressValid

The debug logs confirm that the MmIsAddressValid hook handler was successfully invoked, and its first parameter was printed, demonstrating that the redirection and handler execution worked as intended.

Figure 10: EPT Violation Handling and Hook Invocation for MmIsAddressValid

Unlike Illusion, we don’t currently support user-mode communication in Matrix, though adding it would be straightforward. What we demonstrate instead is a complete proof-of-concept for redirecting kernel execution using EPTP swaps, instruction trapping, and memory virtualization - all without modifying guest memory. This enables stealth introspection, syscall monitoring, and control flow redirection from a kernel driver-based hypervisor on Windows. While not hardened for real-world deployment, Matrix lays the foundation for advancing EPT-based evasion techniques, dynamic analysis, and memory protection research.

Hook Redirection Techniques: INT3, VMCALL, and JMP

While the use of INT3-based hooks offers a lightweight and minimally invasive method for redirecting control flow, it introduces two VM-exits per hook: one on the EPT violation and another on the breakpoint exception. This tradeoff, also seen in Illusion (which uses VMCALL), introduces an extra VM-exit during hook execution. An alternative is to use a 14-byte indirect jump, such as jmp qword ptr [rip+0], which performs an absolute jump by reading the target address from memory immediately following the instruction. This avoids the breakpoint entirely and reduces VM-exits to just one - from the EPT violation alone.

Matrix supports this form of JMP hook via a jmp [rip+0] stub, followed by an 8-byte target address. This method avoids clobbering registers (unlike the mov rax, addr; jmp rax sequence) and reduces the likelihood of introducing side effects. The implementation avoids using general-purpose registers by embedding the jump target inline, which simplifies redirection logic and maintains guest register integrity. By default, Matrix uses INT3 hooks for simplicity and reduced shellcode size.

However, the larger shellcode required for either JMP approach means overwriting more of the original function prologue, increasing complexity around instruction alignment and relative addressing. Other instructions like CPUID, VMCALL, or even undefined opcodes can also be used to trap into the hypervisor, offering future directions for configurable or hybrid hook techniques in Matrix or Illusion.

Hypervisor Detection Vectors

While this article focuses on EPT-based function redirection and stealth memory manipulation for memory introspection, it’s important to acknowledge that hypervisor-assisted hooks can be detected from usermode, even without elevated privileges. These detection techniques typically rely on timing discrepancies, fault-triggering behavior, or instruction-level profiling - usually caused by VM exits during memory access or privileged instruction handling.

Although out-of-scope for this post, here’s a non-exhaustive list of some known detection methods:

• Write-checks to unused code padding (e.g., 0xCC -> 0xC3)
• RDTSC-based timing checks to detect EPT page swaps
• Thread-based timing discrepancies across CPU cores
• CPUID execution profiling (e.g., latency measurement and vendor ID leaks)
• Instruction Execution Time (IET) divergence using APERF or similar counters
• Fault injection via invalid XSETBV, MSR, or control register (CR) access
• Synthetic MSR probing (e.g., reads to the 0x40000000 range)
• SIDT/SGDT descriptor length checks in WoW64 mode
• LBR stack mismatches during forced VM exits
• INVD/WBINVD misuse to test caching consistency
• VMCALL exception handling behavior (e.g., improper #GP injection)
• CR0/CR4 shadow mismatch or VMXE bit exposure
• Unusual exception/NMI delivery paths (e.g., unexpected #PF or #UD behavior)
• UEFI memory map analysis to reveal hidden hypervisor regions
• CR3 trashing to disrupt hypervisors that track or isolate memory mappings per process
• Descriptor table (GDT/IDT) integrity checks to detect hypervisors that fail to isolate or emulate guest-accessible structures correctly
• Page table consistency checks targeting hypervisors that do not fully separate guest and host memory contexts (e.g., shared CR3 or improper shadow paging)

For detailed explorations of these techniques (and many others), see:

• BattlEye Hypervisor Detection - @vmcall, @daax
• How Anti-Cheats Detect System Emulation - @daax, @iPower, @ajkhoury, @drew
• PatchGuard: Hypervisor-Based Introspection [Part 1] - Nick Peterson (@everdox), Aidan Khoury (@ajkhoury)
• PatchGuard: Hypervisor-Based Introspection [Part 2] - Nick Peterson (@everdox), Aidan Khoury (@ajkhoury)
• Syscall Hooking via Extended Feature Enable Register (EFER) - Nick Peterson (@everdox)
• Detecting Hypervisor-Assisted Hooking - Maurice Heumann (@momo5502)

While some of these resources are older, many of the underlying concepts remain valid. The broader topics of evasion, stealth, and hypervisor detection are left as an exercise to the reader.

Appendix

Guest-Assisted Hooking Model

During early development of illusion-rs, a guest-assisted hooking model was implemented and tested. This technique involved allocating memory in the guest, injecting helper code, and redirecting execution (RIP) to a payload from the hypervisor. While technically viable, it introduced additional complexity and detection risk.

Traditional JMP-based inline hooks were avoided because the hypervisor operates outside the guest’s address space in a UEFI context. Implementing them would have required modifying guest memory, resolving APIs manually, coordinating execution context, and managing synchronization across early kernel stages - all of which added exposure and fragility.

This model was similar to the approach explored by Satoshi Tanda, who implemented a GuestAgent in C to hijack control from within the guest during kernel initialization and perform in-guest syscall hooking.

Although functional, this technique complicated recovery and required delicate coordination with guest state. Ultimately, it was removed from illusion-rs in favor of a cleaner design: EPT shadowing combined with inline VMCALL detours and MTF single-stepping for restoration. This approach avoids modifying guest memory entirely by redirecting execution through hypervisor-controlled shadow pages, simplifying control flow and enabling precise redirection without in-guest code.

Comparing EPT Hooking Models: Per-Core vs Shared

The two hypervisors presented in this article - illusion-rs and matrix-rs - implement different EPT-based hooking models, each chosen to explore trade-offs in design, implementation complexity, and control granularity.

Use illusion-rs if you need precise control and fully host-side introspection without relying on in-guest code or memory allocation. It’s also ideal for scenarios requiring early boot-time visibility - such as monitoring or hijacking kernel behavior - before any drivers or security controls are initialized.

Use matrix-rs if you prefer a dynamically loadable Windows kernel driver-based hypervisor with a shared EPT model and no reliance on UEFI or firmware-level integration.

Matrix (Shared EPT Across All Logical Processors)

matrix-rs is a Windows kernel driver-based hypervisor that uses a single EPT shared across all logical processors. This design was inspired by not-matthias’s AMD hypervisor, and development began in late 2022 as a learning project. The shared EPT model made implementation simpler - EPT violations can trigger EPTP switching, and hook state is globally consistent.

Pros:

• Fewer EPT contexts to manage (single EPTP per system)
• Simpler hook setup - updates apply globally
• Only one INVEPT needed per hook change (such as adding or removing a hook)

Cons:

• Race conditions can occur across processors
• Harder to manage per-core or dynamic hook states
• Less precise control over per-CPU redirection

While both models require EPT cache invalidation during hook changes (such as adding or removing a hook), INVEPT must be issued on each logical processor because TLBs are per-logical processor. This applies whether the hypervisor uses per-core EPTs like illusion-rs or a shared EPT like matrix-rs.

Illusion (Per-Logical-Processor EPTs with MTF)

illusion-rs is a UEFI-based hypervisor that uses a separate EPT for each logical processor. Development began in late 2023 to explore a boot-time introspection model using Monitor Trap Flag (MTF) stepping for displaced instruction replay. This approach avoids allocating memory or injecting trampoline code into the guest entirely - everything remains under hypervisor control.

Pros:

• Hook logic remains fully on the host - no in-guest code needed
• Enables clean replay of overwritten instructions via MTF
• Fine-grained redirection per logical processor

Cons:

• Hook updates must be replicated to all EPT contexts
• Requires issuing INVEPT on each logical processor on every hook change (such as adding or removing a hook)
• Increased complexity from maintaining consistent hook state across processors
• MTF stepping incurs additional VM-exits per instruction replay, which may introduce performance overhead depending on the number of overwritten instructions, hook frequency, and placement

Unlike traditional hook models that resume immediately after a detour, the MTF-based approach introduces one VM-exit per replayed instruction. This may be negligible for single hooks but becomes measurable if hooking frequently-executed code paths or system-wide targets.

There are many additional trade-offs - such as design constraints, integration complexity, and guest compatibility - that are beyond the scope of this article and left as an exercise for the reader.

While illusion-rs introduces a cleaner memory manager with pre-allocated page tables and shadow pages, both hypervisors remain proof-of-concept designs. Each offers a foundation for low-level memory introspection and control flow redirection, and can serve as a starting point for deeper research or production-quality development.

For most dynamic or runtime hooking scenarios, the shared EPT model in matrix-rs may be easier to integrate. For firmware-level introspection and early boot control, illusion-rs offers tighter control over execution at the cost of added complexity.

Conclusion

This post covered how to build Rust-based hypervisors for stealth kernel introspection and function hooking using Extended Page Tables (EPT). We explored two proof-of-concept implementations: illusion-rs, a UEFI-based hypervisor that hooks syscalls during early boot, and matrix-rs, a Windows kernel driver-based hypervisor that uses dual-EPT context switching to redirect execution at runtime.

We demonstrated how to detect when the SSDT is fully initialized inside ntoskrnl.exe, how to install execute-only shadow pages, and how to safely redirect execution using VMCALL, CPUID, or INT3 without modifying guest memory. In Illusion, we relied on Monitor Trap Flag (MTF) single-stepping to replay displaced instructions, while Matrix used breakpoint exceptions and trampoline logic to forward control.

Both approaches preserve guest memory integrity and operate without triggering PatchGuard by relying on EPT-backed remapping instead of patching the kernel directly. The result is syscall hooking with fine-grained execution control, suitable for implants, introspection, or security research.

The examples shown here are not groundbreaking - they’re simply a reproducible starting point. Once control is established, these techniques can be extended to conceal threads, processes, handles, memory regions, or embed payloads like shellcode or reflective DLLs - all without modifying guest memory. However, Virtualization-Based Security (VBS) makes custom hypervisor-based hooking significantly harder - from preventing third-party hypervisors from loading at all, to disrupting EPT-based redirection techniques. Defenses like Intel VT-rp, nested virtualization barriers, and integrity enforcement make it difficult to establish control below or alongside Hyper-V - unless you’re prepared to pivot into hyperjacking Hyper-V at boot-time or run your own hypervisor on top of Hyper-V via nested virtualization. Still, building your own hypervisor offers greater control, flexibility, and understanding - and it’s often where the truly novel work begins.

Everything demonstrated was implemented using publicly documented techniques - no NDAs, no private SDKs, and no reliance on undocumented internals. These techniques have long been used in the game hacking scene and are increasingly adopted in security research and commercial products. However, practical guides and open-source implementations remain relatively uncommon, especially for early boot-time hypervisors.

Both illusion-rs and matrix-rs are open-source and available for experimentation. For those looking to explore more minimal or educational examples, barevisor by Satoshi Tanda provides a clean starting point for hypervisor development across Intel and AMD platforms - for both Windows kernel driver-based and UEFI-based hypervisors.

However, if you’re looking for a pre-built, modular, and extensible library for Virtual Machine Introspection, check out the recent project vmi-rs by Petr Beneš (@wbenny).

Acknowledgments, References, and Inspirations

Articles, Tools, and Research References

• Daax (@daaximus)

  • 7 Days to Virtualization
  • MMU Virtualization via Intel EPT

• Satoshi Tanda (@tandasat)

  • Hypervisor Development for Security Researchers
  • Hypervisor 101 in Rust
  • barevisor
  • Hello-VT-rp
  • MiniVisorPkg
  • Intel VT-rp - Part 1. remapping attack and HLAT
  • Intel VT-rp - Part 2. paging-write and guest-paging verification

• Sina Karvandi (@Intel80x86)

  • Hypervisor Development Tutorials
  • Hypervisor From Scratch (GitHub)

• Matthias (@not-matthias)

  • amd_hypervisor

• Nick Peterson (@everdox) and Aidan Khoury (@ajkhoury)

  • PatchGuard: Hypervisor-Based Introspection [Part 1]
  • PatchGuard: Hypervisor-Based Introspection [Part 2]
  • Syscall Hooking via Extended Feature Enable Register (EFER)

• Maurice Heumann (@momo5502)

  • Detecting Hypervisor-Assisted Hooking

• Alex Ionescu

  • SimpleVisor (Minimal x64 Hypervisor)

• Back Engineering (@_xeroxz / IDontCode)

  • AMD-V Hypervisor Development by Back Engineering
  • bluepill (GitHub)

• Guided Hacking

  • x64 Virtual Address Translation (YouTube)
• Namazso (@namazso)
  • UnKnoWnCheaTs forum post
• Petr Beneš (@wbenny)
  • vmi-rs

Community Research and Inspirations

• The Secret Club

  • System Emulation Detection by @daaximus, @iPower, @ajkhoury, @drew
  • BattlEye Hypervisor Detection by @vmcall, @daaximus
  • EAC Integrity Check Bypass by iPower (@iPower)

• DarthTon’s HyperBone Based on Alex Ionescu’s version, as shared on UnknownCheats

• Joanna Rutkowska

  • Introducing Blue Pill

Acknowledgments

• Daax
• Satoshi Tanda (@tandasat)
• Drew (@drew)
• iPower (@iPower)
• Namazso (@namazso)
• Jess (@jessiep_)
• Feli (@vmctx)
• Matthias @not-matthias
• Ryan McCrystal / @rmccrystal
• Wcscpy (@Azvanzed)

Documentation and Specifications

• Intel 64 and IA-32 Architectures Software Developer’s Manual

Compilers are complicated. You just won’t believe how vastly, hugely, mind-bogglingly complicated they are. I mean, you may think C build systems are painful, but they’re just peanuts to compilers.

- Douglas Adams, probably

This blog post assumes you have some knowledge of LLVM internals - I’ll try to fill in some of the lesser-known gaps but there are likely some other, better resources out there for learning about that.

I have only one other post on this blog at the time of writing. It describes a somewhat boring, easily-explained missed optimization in one of the core components of LLVM with some actual, real-world implications. This blog post, although it follows roughly the same format, is the exact opposite:

An exhaustive analysis of a miscompilation that impacted basically no-one

Introduction & disclaimer

Is all the complexity in modern-day optimizing compilers warranted? Probably not.

Take LLVM, for example - once you get to the backends it might as well be 200 compilers in a trench coat. Picture this: it’s two in the morning and you’ve figured out exactly what went wrong after several weeks of debugging. You’re on your fifth coffee and have an idea for a target-independent patch. There’s just one small problem - you’d have to reach out to other overworked people from other companies, convince them that giving you some of their extremely limited time is worthwhile, wait for a bit, address any and all potential concerns, wait a bit more, and Lord help you if something breaks on a piece of hardware you don’t have access to.

Alternatively, you could just add another if statement, ping a coworker to fast-track code review since the change is restricted to your little llvm/lib/Target sandbox, and be on your merry way. Repeat a few times a day and now your Modular™ framework ends up with a bunch of duplicated, convoluted, unnecessarily target-dependent code generation logic.

Yes, quite a bit of the complexity is the result of Conway’s Law and the inevitable bitrot of a decades-old codebase. That being said, there is still an incredible amount of inherent messiness when targeting dozens of architectures in a (mostly) correct and performant way. Nobody is ever going to have a full, deep view of the entire system at once, and even if they did it would be out of date by the next Revert "[NFC] ..." commit.

Every computer on the planet is a compiler fuzzer

We tame the combinatorial explosion of potentially-buggy interactions through the kind of extraordinarily exhaustive testing only possible in the information age. Even a simple “Hello, world!” is a reliability test of the compiler, the linker, the runtime, the operating system, the terminal, any rendering middleware (which might also be running LLVM to compile shaders!), display drivers, the underlying hardware itself, and all software used in the process of building any of that. As such, you can be reasonably confident that release versions of production compilers, when using the flags and target architectures everyone else does, will probably not break anything. That’s not to say stuff doesn’t get through the cracks - yarpgen, alive2, Csmith, and similar tools would not have a long list of trophies otherwise - but those tools are also now just a part of this testing process too.

A direct corollary of this is that bugs are regularly introduced in mainline branches, even by seasoned developers, and fixed whenever this exhaustive testing happens and people actually care about fixing them. Anyway, take a look at this commit:

https://github.com/llvm/llvm-project/commit/c6e01627acf8591830ee1d211cff4d5388095f3d

It is extremely important to emphasize: This committer knows what they’re doing! They’re good at their job! It’s just the nature of compilers and llvm-project/main; shit happens. The miscompile was found and fixed in roughly a week, and if this is all there was to it then we wouldn’t be here.

The funniest compiler bug

Here’s a bug.

https://issues.chromium.org/issues/336399264

Credits to @dougall.

As a summary, here’s what happened.

1. Compile clang with the commit right before the fix above - This is generally called a “stage 1” build
2. Bootstrap clang with the newly-compiled clang - This is a “stage 2” build
3. Build the repro script attached with ASAN and fuzzing harnesses on when targeting AArch64
4. Get a miscompile in the output.

Due to the Clang version being known-buggy and swapped out pretty much immediately, the stage 2 miscompile was noticed by pretty much nobody except people employed at companies that pay them to look at this stuff. This is the system working as intended! Unfortunately, I am a complete sucker for bugs like this but do not get paid to look at them. I wanted to figure out what went wrong here because it’s such a great example of the emergent complexity that comes with modern-day compilers.

hear that? it’s the sound of my free time going down the drain for the next week. fwsssssssshhhhhhhhhhhhhhhhhhhhhhhh

There’s some good news: this is a bug in the loop vectorizer, meaning our stage2 compiler is probably not going to be broken in the impossible-to-debug some-target-specific-register-allocation-thing-is-cooked-somehow way. That may not always be the case (especially if undef/poison are involved) but it seems like we’re going to get a nice, deterministic problem in the mostly-sorta-target-independent part of the pipeline.

undef and poison are, roughly, LLVM’s way of modelling the set of all possible values and a deferred form of undefined behavior. I will not be explaining how this is formalized or what the implications for compiler transforms are. It gets weird. Please do not ask.

Unfortunately, there is also some bad news: this is a bug in the loop vectorizer. The vectorizer is probably the single most per-target-tuned pass in the entirety of the generic optimization pipeline. That means we’re probably going to have some trouble convincing the compiler to deliberately emit the wrong instruction sequence on platforms without cross-compiling. Cross-compiling is not fun. I do not want to cross-compile, so I would like to try to coax the compiler into emitting the right (wrong?) code on X86 if possible.

Foreshadowing is a narrative device in which-

Reproducing the bug with somewhat-helpful debugging information

For now, it’s important to just reproduce the original bug with the aforementioned stage1/stage2 executables in exact the same build environment. While we’re at it, let’s tack on some useful debugging options that will hopefully help us down the line:

1. -print-after=loop-vectorize lets us print out a textual dump of the IR whenever the loop vectorizer pass has finished
2. -ir-dump-directory lets us redirect this output to a folder somewhere This is going to generate a lot of text files. That’s okay, though, because computers are really fast and it doesn’t impact the build times in any meaningful way if we use an SSD.

Simply run this easy-to-remember set of CMake incantations for the stage1 and stage2 builds:

LLVM_DIR=$(pwd)

cmake -S llvm -B build/stage1 -G Ninja -DCMAKE_BUILD_TYPE=Release -DLLVM_ENABLE_PROJECTS=clang -DLLVM_TARGETS_TO_BUILD=AArch64
cmake --build build/stage1

cmake -S llvm -B build/stage2 -G Ninja -DCMAKE_BUILD_TYPE=Release -DLLVM_ENABLE_PROJECTS=clang -DLLVM_TARGETS_TO_BUILD=AArch64 -DCMAKE_C_COMPILER="$(realpath build/stage1/bin)/clang" -DCMAKE_CXX_COMPILER="$(realpath build/stage1/bin)/clang++" -DCMAKE_C_FLAGS="-mllvm -print-after=loop-vectorize -mllvm -ir-dump-directory=$LLVM_DIR/build/stage2/ir_dump" -DCMAKE_CXX_FLAGS="-mllvm -print-after=loop-vectorize -mllvm -ir-dump-directory=$LLVM_DIR/build/stage2/ir_dump"
cmake --build build/stage2

Unfortunately, I do not have an Apple device – as such, I would like to thank an anonymous friend with an M3 laptop for taking the time to help me with this. Time to test.

$ ./build/stage1/bin/clang++ --target=arm64-apple-macos -O2 -fsanitize=fuzzer-no-link -fsanitize=address repro.cc -S -o - | sha256sum
b8dd73117741b08fddb6065fb9289f861f9375b63ebab3ee67edf547ecb0c17a  -

$ ./build/stage2/bin/clang++ --target=arm64-apple-macos -O2 -fsanitize=fuzzer-no-link -fsanitize=address repro.cc -S -o - | sha256sum
cf9f89efb0549051409d2559441404b1e627c73f11e763c975be20fcd7fcda34  -

Okay, we’ve successfully reproduced the bug! We’re not really interested in why this code specifically breaks at runtime - it’s just a minimized reproducer - we just wanted to make sure we could catch it at all. With a repro in hand, we immediately notice some funky changes:

<       .section        __TEXT,__literal16,16byte_literals
<       .p2align        4, 0x0                          ; -- Begin function _ZN3re28Compiler9PostVisitEPNS_6RegexpENS_4FragES3_PS3_i
< lCPI1_0:
<       .byte   255                             ; 0xff
<       .byte   255                             ; 0xff
<       .byte   255                             ; 0xff
<       .byte   255                             ; 0xff
<       .byte   255                             ; 0xff
<       .byte   255                             ; 0xff
<       .byte   255                             ; 0xff
<       .byte   255                             ; 0xff
<       .byte   8                               ; 0x8
<       .byte   9                               ; 0x9
<       .byte   10                              ; 0xa
<       .byte   11                              ; 0xb
<       .byte   12                              ; 0xc
<       .byte   255                             ; 0xff
<       .byte   255                             ; 0xff
<       .byte   255                             ; 0xff
< lCPI1_1:
<       .byte   16                              ; 0x10
<       .byte   17                              ; 0x11
<       .byte   18                              ; 0x12
<       .byte   19                              ; 0x13
<       .byte   20                              ; 0x14
<       .byte   21                              ; 0x15
<       .byte   22                              ; 0x16
<       .byte   23                              ; 0x17
<       .byte   8                               ; 0x8
<       .byte   9                               ; 0x9
<       .byte   10                              ; 0xa
<       .byte   11                              ; 0xb
<       .byte   12                              ; 0xc
<       .byte   29                              ; 0x1d
<       .byte   30                              ; 0x1e
<       .byte   31                              ; 0x1f
<       .section        __TEXT,__text,regular,pure_instructions
<       .globl  __ZN3re28Compiler9PostVisitEPNS_6RegexpENS_4FragES3_PS3_i
---
>       .globl  __ZN3re28Compiler9PostVisitEPNS_6RegexpENS_4FragES3_PS3_i ; -- Begin function _ZN3re28Compiler9PostVisitEPNS_6RegexpENS_4FragES3_PS3_i
63,71c26,34
<       sub     sp, sp, #192

[...]

<       ldr     q0, [x8, lCPI1_1@PAGEOFF]
<       str     q0, [sp]                        ; 16-byte Folded Spill
<       adrp    x28, l___sancov_gen_.2@PAGE+5
<       add     x8, sp, #48
<       ld1.2d  { v1, v2 }, [x8]                ; 32-byte Folded Reload
---
>       mov     w22, #4                         ; =0x4
>       mov     w27, #2                         ; =0x2
>       movi.2d v0, #0000000000000000
>       mov.d   x8, v0[1]
>       str     x8, [sp]

[...]

Something quite fishy has happened here: we’ve lost a whole bunch of data that looks a lot like some sort of vector mask. Good to know!

Since we’re diagnosing a miscompile in the stage2 build of Clang, we should also grab a known-good version of the textual IR of the compiler in the meantime. This just involves running the same set of commands with the fixed (Revert "...") commit. In the end, we have two sets of folders full of IR files, most of which are the same:

$ du -sh *
2.5G    ir_dump_bad
2.5G    ir_dump_good

All of this will be useful later; let’s table it for now and try to avoid using someone else’s computer, since nagging someone else to recompile LLVM constantly is painful for both parties.

It gets better

Okay, now that we’ve successfully captured at least some debugging info, let’s try this the easy way first despite knowing full-well God is laughing his ass off. This would mean compiling on X86 Windows to X86 windows and testing. Ideally, I wouldn’t need to do anything weird to get it to work.

Ha, Nope. Same output in both cases.

Alright, let’s try WSL2. System-V is a bit closer to AAPCS and maybe there’s some weird ABI stuff going on.

# (on X86-64 via WSL)
$ ./build/stage1/bin/clang++ --target=arm64-apple-macos -O2 -fsanitize=fuzzer-no-link -fsanitize=address repro.cc -S -o - | sha256sum
b8dd73117741b08fddb6065fb9289f861f9375b63ebab3ee67edf547ecb0c17a  -

$ ./build/stage2/bin/clang++ --target=arm64-apple-macos -O2 -fsanitize=fuzzer-no-link -fsanitize=address repro.cc -S -o - | sha256sum
b8dd73117741b08fddb6065fb9289f861f9375b63ebab3ee67edf547ecb0c17a  -

Nope.

Maybe the STL is involved - some change between libstdc++ and libc++.

$ ./build/stage2_lcxx/bin/clang++ --target=arm64-apple-macos -O2 -fsanitize=fuzzer-no-link -fsanitize=address repro.cc -S -o - | sha256sum
b8dd73117741b08fddb6065fb9289f861f9375b63ebab3ee67edf547ecb0c17a  -

Great. No taking the easy way out.

Fuck it, just cross-compile the thing

Alternate title: We live in a /usr/include/hell-gnueabihfelmnop of our own creation

C build systems are not fun. One might go so far as to say they’re really, really, really not fun. This is true for a variety of reasons, but one painfully obvious example is cross-compilation. Here’s how you compile Clang to target AArch64 on Linux with the useful IR debug information, assuming you have an AArch64 sysroot installed and an appropriate CMake toolchain file:

cmake -S llvm -B build/stage2 -DCMAKE_TOOLCHAIN_FILE=/home/user/aarch64.cmake -DLLVM_ENABLE_THREADS=OFF -DCMAKE_BUILD_TYPE=Release -DLLVM_USE_LINKER=lld -DLLVM_HOST_TRIPLE=aarch64-linux-gnu -DLLVM_ENABLE_PROJECTS=clang -DLLVM_TARGETS_TO_BUILD=AArch64 -DCMAKE_C_COMPILER="$(realpath build/stage1/bin)/clang" -DCMAKE_CXX_COMPILER="$(realpath build/stage1/bin)/clang++" -DCMAKE_C_FLAGS="-fPIC -fuse-ld=lld --target=aarch64-linux-gnu -mllvm -print-after=loop-vectorize -mllvm -ir-dump-directory=$(realpath build/stage2/ir_dump)" -DCMAKE_CXX_FLAGS="-fPIC -fuse-ld=lld --target=aarch64-linux-gnu -mllvm -print-after=loop-vectorize -mllvm -ir-dump-directory=$(realpath build/stage2/ir_dump)" -DCMAKE_ASM_FLAGS="-fPIC --target=aarch64-linux-gnu" -G Ninja

Yes, the --target options are necessary despite the AArch64 toolchain. Yes, -fuse-ld=lld is necessary despite -DLLVM_USE_LINKER=lld. There is no reason that this should be as complicated as it is today. None. Zero. No other language pulls shit like this and gets away with it.

Too much time later:

$ qemu-aarch64 ./build/stage2/bin/clang --target=arm64-apple-macos -O2 repro.cc -S -o - | sha256sum
cf9f89efb0549051409d2559441404b1e627c73f11e763c975be20fcd7fcda34  -

Success! I think I would’ve started to question my life choices if the stage2 compiler target had to be Apple-specific. To summarize:

1. Compile clang with the commit right before the fix above
2. Bootstrap clang with the newly-compiled clang <– AND TARGET AARCH64
3. Build the repro script attached with ASAN and fuzzing harnesses on when targeting AArch64

There may be some contrived way to convince the vectorizer to miscompile this on X86 by tweaking profitability heuristics but this is good enough for now. Back to bug hunting!

In which approximately 29,000 lines of textual IR diffs are checked by hand and we get extremely lucky

$ diff ir_dump_bad ir_dump_good > yeouch.diff
$ ls -lh yeouch.diff
-rw-r--r-- 1 user user 1.6M Sep 25 21:43 yeouch.diff

There’s a lot going on in there. I’m going to optimistically assume that there’s nothing fishy going on in the Clang frontend, which slashes a significant portion off. After this we manually go through anything remaining, find any suspicious differences, and then check the IR dumps by hand for the function names since those aren’t in the diff itself.

It would’ve also been pretty easy to check if the problem was actually in clang by using -emit-llvm and checking whether the two stages emit something different. I can retroactively say here that they don’t.

Eventually, close to the bottom, we find that SelectionDAG::getVectorShuffle has been messed with in some way:

; *** IR Dump After LoopVectorizePass on *ZN4llvm12SelectionDAG16getVectorShuffleENS_3EVTERKNS_5SDLocENS_7SDValueES5_NS_8ArrayRefIiEE ***
; Function Attrs: mustprogress nounwind ssp uwtable(sync)
define [2 x i64] @_ZN4llvm12SelectionDAG16getVectorShuffleENS_3EVTERKNS_5SDLocENS_7SDValueES5_NS_8ArrayRefIiEE

[...]

<   %306 = phi i64 [ 0, %300 ], [ %323, %305 ]
<   %307 = phi <16 x i64> [ <i64 0, i64 1, i64 2, i64 3, i64 4, i64 5, i64 6, i64 7, i64 8, i64 9, i64 10, i64 11, i64 12, i64 13, i64 14, i64 15>, %300 ], [ %324, %305 ]
<   %308 = phi <16 x i1> [ zeroinitializer, %300 ], [ %319, %305 ]
<   %309 = phi <16 x i1> [ zeroinitializer, %300 ], [ %322, %305 ]
---
>   %306 = phi i64 [ 0, %300 ], [ %321, %305 ]
>   %307 = phi <16 x i64> [ <i64 0, i64 1, i64 2, i64 3, i64 4, i64 5, i64 6, i64 7, i64 8, i64 9, i64 10, i64 11, i64 12, i64 13, i64 14, i64 15>, %300 ], [ %322, %305 ]
>   %308 = phi <16 x i1> [ <i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true>, %300 ], [ %318, %305 ]
>   %309 = phi <16 x i1> [ <i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true, i1 true>, %300 ], [ %320, %305 ]

[...]

… Okay, but what is the SelectionDAG?

On the subject of the SelectionDAG

You can skip the section explaining the SelectionDAG if you know what the SelectionDAG is.

LLVM IR, at this point, has been very well-documented elsewhere. The same is not true for the SelectionDAG.

When lowering instructions to machine code, LLVM will by default use an intermediate representation known internally as the SelectionDAG. As the name suggests, it’s an acyclic graph-based intermediate representation designed to be useful for instruction selection. Each basic block has gets own SelectionDAG. This is not very helpful without a concrete visualization. Luckily, LLVM provides some visualization tools for us. There are a lot of different passes that the SelectionDAG goes through before being passed through the instruction selection system, but we’re going to completely ignore most of them for the sake of this explanation.

Take the following code and compile it:

// ./build/stage1_debug/bin/clang -mllvm -view-isel-dags -mllvm -view-dag-combine1-dags -O2 -m32 test2.c
void test(int *b, long long *c) {
  *c = *b * 2345;
}

You’ll notice we’re compiling for x86_32 - this is important.

Note that LLVM will try to start graphviz or some other dotfile viewer. The reader may find this useful but WSL doesn’t seem to play nicely with them. Solution: apt uninstall graphviz

There are three distinct DAGs that are important to demonstrate roughly what the SelectionDAG does and how. They are quite large, but hopefully don’t mess the flow of this blog post up too much. The first one we’re going to look at is what LLVM IR initially gets translated to:

dotfile

There are multiple things you’ll notice about the SelectionDAG, but the most important takeaway is that the SelectionDAG is a dataflow graph that represents all dependencies of any given node as edges in an acyclic graph. To read the graph, consider GraphRoot the end of the block and go up. This makes intuitive sense, as we are essentially saying that the terminator instruction (a return in our case) depends on the results of the previous computations, including memory state. This is very helpful for instruction selection, as you get all valid orderings of instructions right off the bat.

Memory dependencies are normally implicit in LLVM IR. There is an analysis framework that bolts on explicit memory dependency information on top of LLVM IR. It’s very useful but notably not a core part of the intermediate representation.

In order for this to work, an explicit “state” edge must be added to all nodes that in some way manipulate memory. The way the SelectionDAG represents that is through the Chain operand, labeled ch in the graphs. Dependencies between blocks are modeled as stores to virtual registers with appropriate Chain operands. Note that the chain is marked in dotted blue lines. You’ll also notice that the chain is not fully sequential, meaning we can also represent non-volatile loads and stores that do not alias each other.

There is another “special” form of node called Glue. We are not going to be talking about Glue.

You’ll also notice that there’s already a target specific (X86ISD::) node in here. This is useful since it lets backends handle intrinsics or other wonky target-specific nonsense.

One other notable difference compared to LLVM IR is that SelectionDAG nodes can have multiple returns. This is used, for example, so that load instructions can return both the loaded value and the new Chain. It’s also used in cases like X86’s div instruction, as div simultaneously computes the quotient and the remainder.

With that being said, there’s a problem here: We’re doing 64-bit stores on a 32-bit platform! That’s not going to work. This is where the next phase of the SelectionDAG comes in: legalization. We need to turn the graph above into something that can map down to actual instructions on the hardware. Backends specify a list of legal operations, and all illegal operations are removed by the DAG “legalizer.” Once that’s done, we get output like this:

dotfile

A lot more stuff is happening in this graph, but it’s stuff that actually maps down to something in the hardware. Notably, the 64-bit store has been completely removed and replaced with two (reorderable!) 32-bit stores. TokenFactor nodes just merge separate state edges together, which is important if we have something like a store that potentially depends on two independent loads.

In between these two graphs, we’ve also run the DAGCombiner. This is essentially just a patently absurd amount of pattern matching, both target-independent and not.

After we’ve legalized the DAG and done some other transforms, we’re ready to do the initial instruction selection. This involves a bunch more stuff, including a TableGen-generated bytecode machine which I haven’t seen documented anywhere but is ridiculously cool to me, but we don’t have the space for that. Once that’s done, we get a graph that looks like this:

dotfile

Instruction selection (what instructions) now stops and instruction scheduling (where do they go) begins. From here, we use one of multiple different schedulers to map the SelectionDAG down to sequential code. That pretty much sums it up!

Much of the target-dependent optimization, legalization, and other logic is queried through the inherited TargetLowering classes, which are generally implemented in the *ILselLowering.cpp files. Fun fact: X86IselLowering.cpp is big enough that GitHub refuses to render it.

There is a very low-level explanation of the SelectionDAG on the LLVM website if you’re curious about more implementation specifics.

GlobalIsel eta 2045

every day I’m shufflin’

After some cranial percussive maintenance analysis of the LLVM IR, we find that one specific location has changed:

SDValue SelectionDAG::getVectorShuffle(EVT VT, const SDLoc &dl, SDValue N1,
                                       SDValue N2, ArrayRef<int> Mask) {
  // [...]
  
  // !!! THIS CODE CHANGED SOMEHOW !!!
  bool Identity = true, AllSame = true;
  for (int i = 0; i != NElts; ++i) {
    if (MaskVec[i] >= 0 && MaskVec[i] != i) Identity = false;
    if (MaskVec[i] != MaskVec[0]) AllSame = false;
  }

  if (Identity && NElts)
    return N1;
  
  // [...]
}

Note that at this point we’re not quite sure what the behavioral differences are here; I am not quite ready to read through dozens of lines of vectorized IR to figure out exactly what went wrong here. That doesn’t really matter, though; alarm bells are already going off in my head since the check in the resulting condition (Identity) is short-circuiting emission of a vector shuffle, which would generate data blobs like those removed completely in the miscompiled assembly. In addition, the code that was changed looks suspiciously like the reproducer in the GitHub issue, which also erroneously returns true. This is a neat coincidence – the original bug is in the loop vectorizer and seems to manifest itself as an entirely separate issue in vectorized code generated in a constructor for vector shuffles. yo dawg

Let’s make sure we’re not jumping to conclusions first, though.

Actually Doing the Thing

Remember that cross-compilation nightmare? We’re not done yet!

After building Clang once and testing some minor changes to SelectionDAG.cpp I realized that, to my horror, CMake marked the entire cross-compile build as stale and started the whole thing from scratch. This happened with both the default and Ninja generators. Turns out there’s a bug.. somewhere, that causes includes to constantly be marked as dirty under certain scenarios when using clang. Cool. tl;dr -

sudo ln -s /usr/include /include

Now that we’re not rebuilding the entirety of clang every time, it’s pretty easy to test whether our earlier hypothesis was correct. We can get rid of vectorization for this loop see whether anything changes:

- for (int i = 0; i != NElts; ++i)
+ for (volatile int i = 0; i != NElts; ++i)

$ qemu-aarch64 ./build/stage2/bin/clang --target=arm64-apple-macos -O2 -fsanitize=fuzzer-no-link -fsanitize=address repro.cc -S -o - | sha256sum
b8dd73117741b08fddb6065fb9289f861f9375b63ebab3ee67edf547ecb0c17a  -

Great! Bug gone, which confirms exactly what’s being miscompiled in the compiler.

Less debug info

We’re generating way too much textual IR every time we compile. Let’s use -filter-print-funcs, another useful debugging flag, to fix that:

-mllvm -filter-print-funcs=_ZN4llvm12SelectionDAG16getVectorShuffleENS_3EVTERKNS_5SDLocENS_7SDValueES5_NS_8ArrayRefIiEE

Definitely a mouthful, but helpful nonetheless. While we’re at it, we should enable lld as well for full end-to-end testing. For those keeping track, our CMake configure script now looks roughly like this:

cmake -S llvm -B build/stage2 -DCMAKE_TOOLCHAIN_FILE=/home/user/aarch64.cmake -DLLVM_ENABLE_THREADS=OFF -DCMAKE_BUILD_TYPE=Release -DLLVM_USE_LINKER=lld -DLLVM_HOST_TRIPLE=aarch64-linux-gnu -DLLVM_ENABLE_PROJECTS="clang;lld" -DLLVM_TARGETS_TO_BUILD=AArch64 -DCMAKE_C_COMPILER="$(realpath build/stage1/bin)/clang" -DCMAKE_CXX_COMPILER="$(realpath build/stage1/bin)/clang++" -DCMAKE_C_FLAGS="-fPIC -fuse-ld=lld --target=aarch64-linux-gnu -mllvm -print-after=loop-vectorize -mllvm -ir-dump-directory=$(realpath build/stage2/ir_dump) -mllvm -filter-print-funcs=_ZN4llvm12SelectionDAG16getVectorShuffleENS_3EVTERKNS_5SDLocENS_7SDValueES5_NS_8ArrayRefIiEE" -DCMAKE_CXX_FLAGS="-fPIC -fuse-ld=lld --target=aarch64-linux-gnu -mllvm -print-after=loop-vectorize -mllvm -ir-dump-directory=$(realpath build/stage2/ir_dump) -mllvm -filter-print-funcs=_ZN4llvm12SelectionDAG16getVectorShuffleENS_3EVTERKNS_5SDLocENS_7SDValueES5_NS_8ArrayRefIiEE" -DCMAKE_ASM_FLAGS="-fPIC --target=aarch64-linux-gnu" -G Ninja

More debug info

Let’s use the world’s best form of debugging to get some useful info about what’s going on here.

+ printf("identity: %d, nelts: %d\n", (int)Identity, NElts);

# Bad run:
identity: 1, nelts: 20
identity: 0, nelts: 16
identity: 1, nelts: 16
identity: 1, nelts: 20
identity: 0, nelts: 16
identity: 1, nelts: 16
identity: 0, nelts: 16

# Good run:
identity: 0, nelts: 20
identity: 0, nelts: 16
identity: 0, nelts: 16
identity: 0, nelts: 16
identity: 1, nelts: 16
identity: 0, nelts: 20
identity: 0, nelts: 16
identity: 0, nelts: 16
identity: 0, nelts: 16
identity: 1, nelts: 16
identity: 0, nelts: 16

All we’ve done here is add volatile and we’re even getting changes in how often the function is being called. The good news is that this confirms our hypothesis that Identity is erroneously being set to true in certain cases. The fact that these cases involve the number of vector elements being 20 is also important for later, but we’ll get to that.

Let’s go ahead and also print out all the elements of the vector:

+ for (int i = 0; i != NElts; ++i)
+   printf("[%08X] ", MaskVec[i]);

As a reminder, the Identity boolean is set to true if all elements of the vector are either less than zero or equal to their indices in the vector itself. For example, [0, 1, -1, 3] would return true and [0, 0, 0, 0] would return false.

$ qemu-aarch64 ./build/stage2/bin/clang --target=arm64-apple-macos -O2 -fsanitize=fuzzer-no-link -fsanitize=address repro.cc -S -o -
[FFFFFFFF] [FFFFFFFF] [FFFFFFFF] [FFFFFFFF] [FFFFFFFF] [FFFFFFFF] [FFFFFFFF] [FFFFFFFF] [00000000] [00000001] [00000002] [00000003] [00000004] [FFFFFFFF] [FFFFFFFF] [FFFFFFFF] [FFFFFFFF] [FFFFFFFF] [FFFFFFFF] [FFFFFFFF] -> identity: 1, nelts: 20

[...]

Now, I’m not exactly a mathematician…

Reproducing the vectorizer oopsie

We require a reasonably-representative reliable reproducer to avoid regular recompilation of clang. After a bit of tinkering with the runtime data we have, here’s a small piece of code that demonstrates the issue:

#include <cstdio>

int testarr[] = {
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  16 // index 16 (17th element!)
};

void do_the_thing(int *mask_vec, int n_elts) {
  asm volatile("":"+r"(mask_vec),"+r"(n_elts)); // optimization barrier for good luck

  bool identity = true;
  for (int i = 0; i != n_elts; ++i) {
    if (mask_vec[i] != i)
      identity = false;
  }

  printf("identity: %d, nelts: %d\n", (int)identity, n_elts);
}

int main() {
  do_the_thing(testarr, sizeof(testarr) / sizeof(testarr[0]));
}

$ ./build/stage1/bin/clang --target=aarch64-linux-gnu -O2 test.cpp -fuse-ld=lld -o test.out
$ qemu-aarch64 test.out
identity: 1, nelts: 17

Nifty. What’s going on internally, though? We can view the CFG of the output LLVM IR using the opt tool to find out. Rembember how I said I was not ready to read through dozens of lines of vectorized IR? Well, so, uh,

./build/stage1/bin/clang --target=aarch64-linux-gnu -O2 test.cpp -fuse-ld=lld -emit-llvm -S -o test.ll
./build/stage1/bin/opt -passes=-view-cfg test.ll

The original dotfile is here. A rendered version is located here for your viewing displeasure. It’s big enough that I’d rather not embed it in-line, so you should open it in a second window somewhere to follow along. If you squint hard enough, you’ll notice a 16-wide vector loop, an 8-wide vector loop, and a scalar loop. Really quickly, let’s take a look at some of the trickery that’s happened already. Here’s an annotated and shortened version of the 16-wide vector loop:

loop_block:
    %bool_phi = phi <16 x i1> [ zeroinitializer, %entry ], [ %bool_vec, %loop_block ]
    %idx_list = phi <16 x i32> [ ... ]
    %current_block_ptr = getelementptr inbounds ...
    %current_block = load <16 x i32>, ptr %current_block_ptr
    %cmp_result = icmp ne <16 x i32> %idx_list, %loaded_values
    %bool_vec = or <16 x i1> %bool_phi, %cmp_result

s/”shortened version of”/”deliberate lie about what’s in”/

If you’re paying really close attention, you’ll notice that the meaning of cmp_result has actually been inverted compared to identity! Now any element of bool_vec being true would mean that identity is false, rather than requiring all elements of bool_vec to be true in order for identity to be true. I hope that made sense. This inversion means it’s possible to use a simple comparison against zero to check whether our condition was satisfied, rather than needing to load -1 in various places afterwards. Neat, huh?

The phi node results of the 16-wide vector loop are, depending on whether we want to execute the 8-wide vector loop or not, are–

Wait a minute.

COMPUTER, ENHANCE!

27:                                               ; preds = %14
  %28 = bitcast <16 x i1> %23 to i16
  %29 = icmp eq i16 %28, 0
  %30 = icmp eq i64 %13, %8
  br i1 %30, label %64, label %31

31:                                               ; preds = %27
  %32 = and i64 %8, 8
  %33 = icmp eq i64 %32, 0
  br i1 %33, label %61, label %34

61:                                               ; preds = %7, %31, %57
  %62 = phi i64 [ 0, %7 ], [ %13, %31 ], [ %38, %57 ]
  %63 = phi i1 [ true, %7 ], [ true, %31 ], [ %59, %57 ]
  br label %70

Let’s annotate this a bit. Block %27 is executed immediately after %14 (the 16-wide loop) is done, %57 is executed immediately after the 8-wide loop, %13 is the current loop iteration index (i.e. how many iterations of the original operation the 16-wide loop has completed), and %8 is the required total iteration count.

; Executed immediately after 16-wide vector loop
27:                                               ; preds = %14
  ; %29 is set to whether 0 if all vector elements are false; i.e. the check in the vector loop always fails. Not shown: the vectorizer has inverted our condition from equality to inequality.
  %28 = bitcast <16 x i1> %23 to i16
  %29 = icmp eq i16 %28, 0

  ; Check whether we've iterated through the entire loop
  %30 = icmp eq i64 %big_loop_trip_count, %req_trip_count
  br i1 %30, label %64, label %31

; We have not, check whether we should execute 8-wide vector loop
31:                                               ; preds = %27
  %32 = and i64 %req_trip_count, 8
  %33 = icmp eq i64 %32, 0
  br i1 %33, label %61, label %34

; Do not want to execute 8-wide loop
61:                                               ; preds = %7, %31, %57
  ; Iteration count after vectorized loops
  %62 = phi i64 [ 0, %7 ], [ %big_loop_trip_count, %31 ], [ %38, %57 ]

  ; PHI node representing current status of `identity`. Always `true` after the entry block, `true` after block `%31`, dependent on `%59` after block `%57` (8-wide loop).
  %63 = phi i1 [ true, %7 ], [ true, %31 ], [ %59, %57 ]
  br label %70

true after block %31? That’s not good. It seems like, if the second vector loop is not executed and we go to the scalar loop, the results of the first vector loop are just.. ignored! We can test this out pretty easily:

int testarr[] = {
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 16
+ 16, 17, 18, 19, 20, 21, 22, 23
};

$ qemu-aarch64 test.out
identity: 0, nelts: 24

Then let’s try deliberately executing the scalar loop and the second vector loop:

int testarr[] = {
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 16
+ 16, 17, 18, 19, 20, 21, 22, 23, 24
};

$ qemu-aarch64 test.out
identity: 0, nelts: 25

Great! Or, well, not great, but we’ve successfully narrowed down the root cause of the stage2 bug. To be clear, to trigger this bug the vectorizer has to generate a very specific type of operation at compile time and at runtime we have to have somewhere between 17 and 23 total iterations done.

Fun.

… How are these vectors generated, anyway? What would generate a twenty-element vector?

Let’s take a look at the original reproducer and try to find anything useful in the LLVM IR:

$ qemu-aarch64 ./build/stage2/bin/clang --target=arm64-apple-macos -O2 -fsanitize=fuzzer-no-link -fsanitize=address repro.cc -S -emit-llvm -o - | grep "20 x "
$

Okay, so this has to be something done after all of the IR passes then. Fantastic. Let’s just print out everything with -debug and-

$ ./build/stage1/bin/clang --target=arm64-apple-macos -O2 -fsanitize=fuzzer-no-link -fsanitize=address -S repro.cc -mllvm -debug
clang (LLVM option parsing): Unknown command line argument '-debug'.  Try: 'clang (LLVM option parsing) --help'

Oh. Right. We didn’t compile Clang in debug mode. Time to kick off yet another from-scratch LLVM build. sigh

[more than one minute later]

$ ./build/stage1_debug/bin/clang --target=arm64-apple-macos -O2 -fsanitize=fuzzer-no-link -fsanitize=address -S repro.cc -mllvm -debug

[...]
Creating new node: t76: v20i8 = concat_vectors t74, undef:v5i8, undef:v5i8, undef:v5i8

I’m not even going to question why or how a vector with five elements is being generated for now - what’s important is that the 20-element vector is being created during instruction selection. The <5 x i8> vectors exist before instruction selection in the form of operands to vector shuffles, which is good:

;./build/stage1/bin/clang --target=aarch64-linux-gnu -O2 repro.cc -fsanitize=fuzzer-no-link -fsanitize=address -emit-llvm -S -o -
; ...
%133 = bitcast i40 %ref.tmp.sroa.4.0.extract.trunc to <5 x i8>
%retval.sroa.0.8.vec.expand62 = shufflevector <5 x i8> %133, <5 x i8> poison, ...
; ...

The fact that these vectors are in the IR emitted by -emit-llvm means we can assume they’ll be passed directly to the initial SelectionDAG builder, so we should take a look at that now.

Under complex macroarchitectural conditions…

Let’s take a look at SelectionDAGBuilder::visitShuffleVector:

void SelectionDAGBuilder::visitShuffleVector(const User &I) {
  // ...

  // Normalize the shuffle vector since mask and vector length don't match.
  if (SrcNumElts < MaskNumElts) {
    // ...

    unsigned PaddedMaskNumElts = alignTo(MaskNumElts, SrcNumElts);
    unsigned NumConcat = PaddedMaskNumElts / SrcNumElts;

    // Pad both vectors with undefs to make them the same length as the mask.
    SDValue UndefVal = DAG.getUNDEF(SrcVT);
    SmallVector<SDValue, 8> MOps1(NumConcat, UndefVal);
    SmallVector<SDValue, 8> MOps2(NumConcat, UndefVal);

    MOps1[0] = Src1;
    MOps2[0] = Src2;
    
    Src1 = DAG.getNode(ISD::CONCAT_VECTORS, DL, PaddedVT, MOps1);
    Src2 = DAG.getNode(ISD::CONCAT_VECTORS, DL, PaddedVT, MOps2);

    // Readjust mask for new input vector length.
    SmallVector<int, 8> MappedOps(PaddedMaskNumElts, -1);

    // ...

    SDValue Result = DAG.getVectorShuffle(PaddedVT, DL, Src1, Src2, MappedOps);

    // ...
  }

As a reminder, our source vector size is 5 and our mask vector size is 16. The SelectionDAG builder wants to normalize the source and mask vectors, such that:

1. The resulting output mask is a multiple of the number of elements in the source vector. Not quite sure why.
2. All vectors passed to getVectorShuffle are the same size as the mask.

This means that we get undef-padded 20-element vectors and multiple -1s at the end of the mask. Those -1s then get passed to getVectorShuffle, which then causes the miscompile as mentioned before. Neat.

Time to look a little at how that 5-element vector was generated. Looking for <5 x i8> in the debug logs tell us a bit more about what’s going on here:

rewriting [8,13) slice #8
  Begin:(8, 13) NewBegin:(8, 13) NewAllocaBegin:(0, 16)
  original:   store i40 %f1.sroa.5.0.extract.trunc.peel, ptr %9, align 8
  shuffle:   %retval.sroa.0.8.vec.expand = shufflevector <5 x i8> %10, ...
  blend:   %retval.sroa.0.8.vecblend = select <16 x i1> ...

SROA is a pass designed to optimize away (“promote”) alloca instructions and turn the values they reference directly into SSA registers. We can see SROA turning a store of a 40-bit integer(????) into a mess of shuffles. I’m not going to go through this bit line-by-line as, frankly, there isn’t anything particularly unique about how this part of the bug manifests itself. There are plenty of other ways in which weird-length vectors are generated - <20 x i8> and <5 x i8> show up a bunch of times in the test-cases.

Here’s a great overview of some of the passes in the LLVM mid-end optimization pipeline.

As an expedited summary, SROA runs, then a bunch of passes run, then SROA runs again and turns some stores into those i40 stores, then some other passes run, then SROA runs again and turns those stores into 5-element vector shuffles as seen above. Going through exactly why this happens would involve sifting through a bunch of implementation details with nothing much to say other than “this is what it does.” I don’t find that particularly engaging when nothing else is involved, and this post is long enough as-is. The code works as intended. The fact of the matter is that all modern-day compiler bugs have root cause chains this deep - one pass happens to generate some code which happens to cause another pass to generate some other code, and so on and so forth.

If you’d like, you can see the full diff here.

Conclusion

It’s entirely unnecessary for compiler engineers to go into this amount of detail about why something went wrong from start to finish. All that’s needed is what was given at the very start: Correct IR, buggy IR. Fix bug, add test-case, done. The underlying root cause of this bug was fixed a while ago – it’s very unlikely that anyone was ever concretely impacted by it outside of a few hours of type 2 fun.

With that being said, this silly bug will probably hold a special place in my heart for a while. The potential for a buggy bootstrapped compiler has always existed. In practice, however, it’s incredibly rare, and I didn’t think I’d ever actually see a real-world example. I hope whoever read to the end learned something. It’s a fantastic example of how things can go wrong in ridiculous, unexpected ways when so many moving parts are involved.

I love shit like this.

We briefly explored this idea that fuzzing has some limitations, looking specifically at problems associated with harnessing and input mutation. Sometimes, we can do everything right and yet the fuzzer still struggles to find bugs. Regex engines fall into this camp quite strongly; let’s figure out why by looking at PCRE2.

Target 2: PCRE2

PCRE2 is (likely!) the world’s most used regex library. It started as PCRE back in 1998, eventually upgrading to PCRE2 in 2014 due to major API changes. I highly recommend reading Joe Brockmeier’s article on the library and the primary developer, Philip Hazel – the library, and its author, have quite an incredible history.

A few months ago, now a few years after my exploration of rust-regex, I stumbled across a bug in PCRE2 during a research project. The bug suggested the presence of latent bugs in the just-in-time compiled component of PCRE2. At CISPA, we are encouraged to investigate such tangents and, being the fuzzing-oriented person I am, I started deep diving the fuzzers in PCRE2.

OSS-Fuzz, or: Learned Helplessness

There is a standing fear that if a project is in OSS-Fuzz, there is no point in fuzzing it. This is especially the case for PCRE2: it’s been in OSS-Fuzz since the very beginning! PCRE2 has likely been fuzzed for multiple centuries of CPU time at this point.

And yet, there are fuzzing-discoverable bugs in OSS-Fuzz projects. How could we miss them?

fuzz-introspector

Trying to understand this very problem, OpenSSF, led by David Korczynski, developed Fuzz Introspector in 2021. This tool inspects fuzzer performance over time by tracking various metrics and is most notably deployed on OSS-Fuzz.

With this tool, we can inspect how well (or, more frequently, how poorly) various harnesses are performing in OSS-Fuzz.

We can see that a majority of targets get very low coverage. This flies in the face of the assumption one might make regarding how well fuzzed targets in OSS-Fuzz are, and is a problem that Google spends a lot of money trying to solve. Yet PCRE2 has historically reached high code coverage, so what went wrong here?

One of the limitations of Fuzz Introspector is that it can only determine if something is uncovered if it can find the function within the binary. In the case of PCRE2, the JIT compiler was never actually included in the fuzz testing. As a result, once enabled, the true coverage of the source code was shown to be far lower:

So, even for programs with high code coverage, you cannot merely take it at face value that the code is well-covered. Similarly, coverage is not indicative of bug discovery, so we cannot take the coverage itself at face value.

You’re JIT-ing me

To improve the OSS-Fuzz harness, I submitted changes that enabled fuzzing of the JIT compiler in tandem with the normal executor. We do this because fuzzing the JIT compiler alone is insufficient.

Consider the mechanism by which code coverage is measured. In libFuzzer, this works via the SanitizerCoverage pass, which adds callbacks at code points which will track the traversal of certain edges. For the coverage to be tracked, the code must exist at compile-time.

In the presence of a JIT compiler, the code which is executed is not guaranteed to be produced at compile-time.

When a JIT compiler is used, some code is generated at runtime. This can lead to curious problems where we cover the JIT compilation code, but not the compiled code itself. For example: consider a regex like a|(0) (“match the literal a OR capture a literal 0”). The JIT compiler emits capturing code, but if we only execute this regex on the input a, we will never actually run the emitted code, meaning we will never execute the code performing the capture. In effect, the code coverage for the JIT compiler represents a superset of the coverage of the regex which is executed.

To get around this, when fuzzing regexes which are JIT’d, we must also execute each regex without JIT to get a sense of what code regions are actually used during execution, lest we overestimate what we’ve actually tested and not just generated. But even this can be misleading, because the JIT implementation does not necessarily strongly relate to the implementation of the “classic” implementation. There are likely specific optimisations in each which will need to be tested, and there are no guarantees that a corresponding code region exists in the coverage-measured code for a code region emitted by JIT. As such, this is an inescapable limitation.

But Addison, you can measure the code coverage in QEMU or something!

You do not want to do this. The JIT’d region will change every time you execute the program, and it effectively turns each tested regex into its own little program that must be covered. More importantly, it will not be trivial to distinguish whether two regexes are meaningfully different. Without serious investment into mapping which JIT regions are produced and affected by which JIT compiler regions, this would only lead to an explosion of inputs considered “interesting” without real progress.

TL;DR: don’t use emulated code coverage with JIT compilers.

Regex is more than just a parser

Fuzzers were originally crafted targeting parsing programs, like image parsers. These programs are generally simple; when you’re parsing an image, there’s only so many ways in which a given parsing region can be reached. Similarly, there’s only so much state which affects how the corresponding region of input is parsed by that code.

Regex engines first parse the pattern, then execute the (very limited) program represented by that pattern. When you explore the coverage of a parser, you typically explore most of the behaviours of the parser (with notable exceptions). When you explore the coverage of a regex engine, you explore very little of its behaviours because of the huge amount of impact that what has previously been processed by the pattern affects what will be parsed by the pattern yet. This is especially true for PCRE2, which supports referencing previously-captured data and context-specific control of execution behaviour.

More generally speaking, as program interpretation of inputs increases in complexity and more program state determines the behaviour of various code regions, their interactions become more important than their coverage alone. For this reason, while coverage has been historically effective at measuring the exploration of the program, it simply cannot express whether you’ve explored all the ways in which a code region can behave (and more relevantly, how it can fail). This is a strong limitation of coverage-guided fuzzing, and primarily affects highly-complex targets that require the most testing. So far, very few meaningful improvements have been made to fuzzers in this regard, and anyone who makes meaningful, generalisable, and performant improvements to our ability to explore complex programs beyond “did we ever hit a code region” will revolutionise our field.

Since we can’t rely on coverage exploration alone, let’s hope our mutations are strong enough to create inputs that cause combinations of program behaviour that might trigger more complex behaviour which is indistinguishable over code coverage.

The inescapable reinterpretation problem

Last time, we talked about how inputs may be reinterpreted if mutations do not preserve the meaning of an input. While rust-regex’s harness still does not have a stable interpretation (that is, a length change can still change the meaning of the input), PCRE2 does because it uses the tested pattern as the input to itself and only mutates the pattern. Yet, mutations still can corrupt (or significantly modify the interpretation of) the inputs because byte mutations on well-formed regexes do not sanely transform the inputs.

For example: the mere insertion of a ( into a pattern will nearly always cause the pattern to become invalid, as the brace is unmatched (with some exceptions, e.g.: [...(...]). We rely on luck to make meaningful modifications to the inputs.

Crossover as a magic bullet?

Crossover is the process by which two inputs are combined to make a new input that exhibits features from both original inputs. The strategy is imported from genetic algorithms but is sadly also affected by reinterpretation, since two inputs are crossed over without respect to the semantics of the patterns they represent. As a result, it cannot be relied upon to “mix” behaviour and thus better explore the program when coverage is not enough.

Okay, so why not make a grammar and mutate it from there?

Please do!

Findings

With the updates to the fuzzer to include JIT, I found several bugs and some privately reported issues with the JIT compiler. None of them were realistically exploitable in normal circumstances by attackers unable to control the pattern.

Differential fuzzing

Since we’re already executing both the “classic” implementation of regex and the JIT implementation of regex simultaneously, it should be trivial to compare their outputs.

Right?

Harnessing is hard

I won’t go into the details of comparing the two outputs, but there are quite a few corner cases that dramatically complicate comparing JIT with classic regex. Primarily, there are different optimisations and failure cases which cause one to fail when another succeeds, and iterating through the results is occasionally non-trivial as well. The hardest part, however, is communicating to the user what exactly the problem is – that is, what precisely about the two outputs produced differ. Developing a harness to do so was a multi-month process, but ultimately did find several bugs.

Fault localisation

Finding what exactly caused a difference can also be quite difficult. Take, for example, this issue, which stumped everyone involved for two weeks before we could even agree on interpretation of the input. Since tools which find the root cause of specifically bugs found by a differential oracle are not widely available, each testcase must be manually inspected and investigated. Sometimes, I was able to diagnose the cause, but not the relevant code region, myself, but there were many issues where I relied on the developers to discover the root cause from start to finish. This is a major usability failure in fuzzing: without localisation or remediation advice, developers suffer a form of alert fatigue from bugs found by differential fuzzers – especially since they are not easily discernable from each other.

I deeply appreciate the developers for bearing with my incessant bug reporting, and for being open to the new forms of testing even when the bugs seemed pointless.

Wait, pointless bugs?

What exactly is a bug? If a bug causes a program to crash, but no sane user is nearby to be affected by it, does it still matter?

Should you fix a bug if it reduces the performance in the normal case, and doesn’t affect realistic inputs?

Differential fuzzing finds any difference it can and complains about them all equally, regardless if any “real” user would be affected. When using such tools, it is necessary to be mindful of whether the developer will care, or even want to fix the bug, since it may not realistically affect anyone in practice.

Early Conclusion

I have long, long missed my own deadline for this post. But I think some of the findings are meaningful, and want to get it out there before it becomes irrelevant. Perhaps in the future, I will add some specialised fuzzers to measure and demonstrate some of the effects mentioned here rather than just telling you about what I found while debugging, but for now, that will have to wait.

I think the primary takeaway here is the same as part 1: you cannot rely on the fuzzer to magically find all the bugs for you, nor tell you what causes them. Each harness and target must be individually considered for what specific blockers or misrepresentations of fuzzer performance may occur. Moreover, don’t mistake lots of fuzzing time on one harness for an upper bound on what can be found by fuzzing – lots of harnesses are simply incapable of finding some bugs. Finally, when using these tools, be cognisant of how the developers will react; some 50-60 bugs were reported by the PCRE2 fuzzers, all in all, and were handled by two developers in their free time.

I hope this somewhat disconnected rumination helps others make better fuzzers, find more bugs, and help developers fix them.

The bugs I’m going to talk about in this post are not security critical. The targets and bugs described below are instead offered as a study for fuzzing design decisions and understanding where fuzzing fails. I think this might be useful for people considering fuzz testing in both security and non-security contexts. If anything is poorly explained or incorrect, please reach out and I will happily make corrections, links, or add explanations as necessary.

In this blog post, I’m going to talk about the fuzzing of two very different regular expression libraries. For each, I’ll detail how I went about designing fuzzers for these targets, the usage of the fuzzers against these targets, the analysis and reporting of the bugs, and the maintainence of the fuzzers as automated regression testing tools.

Targets

Okay, our PUTs for today are:

• rust-lang/regex
• PCRE2

We develop separate differential fuzzing harnesses for each that are dependent on the specific guarantees of each program.

Sidebar: What is regex?

If you have programmed anything dealing with string manipulation, you’ve almost certainly encountered regular expression (RegEx, or just regex) libraries. There are many forms of regular expressions, from the formal definitions to the many modern implementations, like the two discussed here. Modern “flavours” of regex often include quality-of-life features or extended capabilities not described in the original formal definitions, and as such actually represent greater formal constructs (e.g., I’m fairly confident that PCRE2 is capable of encoding something higher than a context-free grammar).

The purpose of these libraries is definitionally straightforward: to provide a language that can define patterns to search through text. Their implementation is rarely so straightforward, for two primary reasons:

1. Users demand expressive patterns by which to search text. Many different strategies must be made available by these libraries so that users may search and extract details from text effectively.
2. Text searching is often a hot path in text processing programs. Any implementation of regex must be implemented to process text extremely efficiently for any reasonable pattern.

I won’t give an overview of the writing and usage of regex here, as it’s mostly irrelevant for the rest of this. For those interested, you can find an overview of common features here.

Target 1: rust-lang/regex

The regex crate (hereon, rust-regex) is one of the most widely used crates in the entire Rust ecosystem. Its syntax is potentially more complex than some other engines due to its extended support of Unicode, but notably restricts itself to regular languages. rust-regex, unlike most other regex libraries, offers moderate complexity guarantees and is thus resistant (to a degree!) to certain malicious inputs.

I fuzzed rust-regex some time ago now (>2 years), but below is a brief summary of how I approached the software.

Analysis of the existing harness

A fuzzing harness (in most cases) is simply a function which accepts an input and runs it in the target. Ultimately, from the perspective of the user, the fuzzing process can be thought of as so:

1. the fuzzer runtime starts
2. the runtime produces some input
3. the harness is run with the new input; if an input causes a crash, stop
4. the runtime learns something about your program to make better inputs with
5. go to step 2

So, to be super explicit, we describe the fuzzer as the whole program which performs the fuzz testing, the fuzzer runtime as the code (typically not implemented by the user) which generates inputs and analyzes program behaviour, and the harness as the user code which actually manifests the test by calling the PUT. Having a poor fuzzer runtime means your program won’t be tested well. Having a poor harness means that the inputs produced by the runtime might not actually test much of the program, or may not test it very effectively.

Since we don’t want to make a custom fuzzer runtime and just want to test the program, let’s focus on improving the harness.

When I started looking into rust-regex, it was already in OSS-Fuzz. This means potentially thousands of CPU-years of fuzzing has already been performed on the target. Here, we’ll talk about two ways to find new bugs: better inputs and more ways to detect bugs. Both of these are directly affected by how one harnesses the PUT.

Here is the rust-regex harness as I originally saw it. This harness works by interpreting the first byte as a length field, then using that to determine where to split the remainder of the input as the search pattern and the “haystack” (text to be searched).

index                                      | meaning
------------------------------------------------------------
0                                          | length field
------------------------------------------------------------
[1, 1 + data[0] % (len(data) - 1))         | search pattern
------------------------------------------------------------
[1 + data[0] % (len(data) - 1), len(data)) | haystack

And, this works; for several years, this fuzzer was used in practice and found several bugs. But this harness has some problems, the biggest of which being: data reinterpretation over mutation.

Looking under the hood

Fuzzers, sadly, are not magic bug printers. The fuzzer runtime used here is libFuzzer, which performs random byte mutations and has no fundamental understanding of the program under test. In fact, the only thing the fuzzer really considers to distinguish the effects of different inputs is the coverage of the program². When an input is generated, it is only considered interesting (and therefore retained) if the program exhibits new coverage.

Moreover, inputs are not simply generated by libFuzzer. They are rather the result of mutation – the process of modifying an existing input to get a new input. Let’s break apart the loop we described earlier into finer steps (edits in bold):

1. the fuzzer runtime starts
2. the runtime selects some existing input from the corpus (the retained set of inputs); if none are available, generate one and go to 4
3. the runtime mutates the input
4. the harness is run with the new input; if an input causes a crash, stop
5. the runtime inspects the coverage of the last run; if the input caused a new code region to be explored, add it to the corpus
6. go to step 2

Understanding mutation

One of the underlying assumptions made about fuzzing with mutation is that a mutated input is similar to the input it’s based on, but different in interesting ways. But, what does it mean to be similar? What does it mean to be interestingly different?

In general, we would like to explore the PUT’s various ways of interpreting an input. We can’t³ magically generate inputs that get to places we haven’t explored before. Rather, we need to stepwise explore the program by slowly stepping across it.

Consider a classic demonstration program in fuzzing (pseudocode):

if (len(data) >= 1 && data[0] == 'a') {
 if (len(data) >= 2 && data[1] == 'b') {
  if (len(data) >= 3 && data[2] == 'c') {
   if (len(data) >= 4 && data[3] == 'd') {
    // bug!
   }
  }
 }
}

Suppose we want to hit the line that says “bug!”. We need to provide the program with an input that starts with abcd. If we simply generate random strings, the odds of producing such a string are at most 1 in 2^32 – roughly 1 in 4 billion. Not the best odds.

The promise of coverage-guided fuzzing is that, by mutation, we slowly explore the program and thus break down the problem into separate, easier to generate subproblems. Suppose that our runtime only applies mutations that randomly produce inputs with an edit distance of 1. Now, when we mutate our inputs, starting small, we can guess each 1 in 256 byte one at a time, and our runtime will progressively explore the program and get to the line that says “bug!” after solving this sequence of smaller subproblems.

The data reinterpretation problem

Let’s rewrite our harness slightly to be more representative of the rust-regex harness.

if (len(input) <= 1) {
 return;
}
data = input[1..];
offset = input[0] % len(data);
if (len(data) + offset >= 1 && data[offset] == 'a') {
 if (len(data) + offset >= 2 && data[offset + 1] == 'b') {
  if (len(data) + offset >= 3 && data[offset + 2] == 'c') {
   if (len(data) + offset >= 4 && data[offset + 3] == 'd') {
    // bug!
   }
  }
 }
}

This program is precisely the same “difficulty” as the original problem; we set input[0] = 0 and input[1..] to the solution from the original harness. Except, for coverage-guided fuzzers, this problem is orders of magnitude more difficult (reader encouraged to try!). Let’s look at how this program behaves over mutation; for clarity, raw bytes (like the offset field) will be written as [x] with x as the value in that byte.

Starting with some randomly generated input:

[123]c
  ^  ^
  |  |
  |  + first byte
  |
  + offset field; offset = 123 % len(input[1..]) = 123 % 1 = 0

This input is retained, because we have new coverage over the first few lines, but we don’t make it into the nested ifs just yet. Then, we mutate it until we find new coverage:

[123]a
  ^  ^
  |  |
  |  + first byte (passes our check!)
  |
  + offset field; offset = 123 % len(input[1..]) = 123 % 1 = 0

Great! We’ve hit the first if in the nested block. Unfortunately, with an edit distance of 1, we can now never trigger the bug. Suppose we get lucky and produce a b, which would have historically now passed the second condition:

[123]ab
  ^  ^^
  |  ||
  |  |+ first byte (fails the first check)
  |  |
  |  + skipped by offset
  |
  + offset field; offset = 123 % len(input[1..]) = 123 % 2 = 1

Because the offset is now reinterpreted by the program due to a change in length, the input is actually dissimilar to the original input from the perspective of the program. Even supposing we get lucky and get an a instead, the coverage of the resulting program doesn’t improve over the first mutated input and thus doesn’t get retained. If we change the offset to zero, then we don’t get new coverage because we still only have an a. With an edit distance of 1, we simply cannot actually produce any new coverage from this input.

This data reinterpretation problem is rampant across OSS-Fuzz harnesses, and mitigating the problems induced by this is a great place to start for people looking to improve existing harnesses. While, in practice, the edit distance of mutations is extremely large, the randomness produced by reinterpretation effectively reduces us all the way back to random generation (since we are nearly guaranteed to induce a reinterpretation by havoc mutations used by nearly all fuzzers). In rust-regex, the consequence of this reinterpretation problem is that regexes are wildly reinterpreted when inputs are small (as typically optimised-for by fuzzers) or when the first byte is mutated. Moreover, the pattern can never actually exceed 255 bytes (!).

Redesigning the harness

Okay, so we know that the existing harness has some problems. Let’s redesign the harness to clearly segment between “pattern” and “haystack” by structurally defining the input. We can use the handy dandy arbitrary crate to define a parser over arbitrary bytes to transform the input into a well-formed pattern and haystack. This, in turn, effectively makes mutations directly affect decisions made by the parser defined in arbitrary by making arbitrary act as an interpreter for the bits in the input, and mutations making changes to the decisions made by arbitrary⁴. As a user, this is simple, straightforward, and makes inputs much more “meaningful”; we now know that the bytes in our input represents a meaningful pattern.

You can find these changes in the merged changes by the author; change 1, change 2.

Did we solve the reinterpretation problem?

Interlude: grammar fuzzing vs byte fuzzing

Consider, for a second, a JSON parser. JSON is a very well-defined, structural language that aggressively rejects malformed inputs. Yet, byte-level mutational fuzzers with no awareness of the JSON format can produce well-formed JSON inputs by exploring the program space. That said, most mutations produced mangle the JSON input dramatically (e.g., in {"hello":"world"}, a mutation to {"hel"o":"world"} instantly makes the JSON parser reject the input). This limits the ability for byte-level mutational fuzzers to produce interesting inputs that test code behind a JSON interpreter.

Consider the following rendition of our earlier examples:

obj = JSON.loads(input); // lots of coverage in JSON to explore!

if (obj.a == 'a') {
  // bug!
}

Our byte-level mutational fuzzer will try to find as much code coverage as it can – and will mostly get lost in the weeds in the JSON step. Suppose we are “smart” and tell the fuzzer to magically ignore the coverage in JSON; now, the fuzzer will almost certainly never produce even a valid JSON input. As a result, we will never hit “bug!”.

But, suppose we wrote an arbitrary implementation that was capable of interpreting the random bytes produced by our mutational fuzzer valid objects with a field called “a”, before serialising it and handing it to the PUT. Now, we are effectively guaranteed to be able to produce an input that hits “bug!”, provided that our mutator is smart enough to figure out how to get the string “a” into that field.

Certainly, the mutator will easily do this, right?

Data Reinterpretation: Reloaded

Arbitrary, sadly, is not a magic input printer.

Internally, the parser itself defines various length fields throughout the parsing process which determine how the remainder of an input is processed. This makes the format of the input change dramatically with small changes to the input⁵, and thus, once again, the data reinterpretation problem emerges.

Worse, when we now deploy our fuzzer, the meaning of the inputs changes – so our thousands of CPU years of fuzzing in the past is now thrown away.

As it turns out, the data reinterpretation problem is probably unavoidable; without having mutations that are simply aware of the datatype, producing similar inputs is probably not possible. Even when directly mutating entries in the grammar (e.g., by simply replacing one subtree of the input with another), the edit distance is often huge. This invalidates the basic premise of our coverage-guided fuzzer, and as a result makes our fuzzer effectively useless.

Right?

Results

My arbitrary-based fuzzer was written in 30 minutes. I ran it for less than a minute before a testcase triggered CVE-2022-27413⁶ as a timeout in a release build of the fuzzer.

As it turns out, the mass reinterpretations of the input were not a problem – when arbitrary was used. Since the randomness induced by the mutations caused major reinterpretations of the input, a huge amount of the grammar of the inputs were explored. This effectively turned the mutator into a blackbox grammar generator, and the grammar was covered as a natural result of the covering of the program.

With the randomness constrained to valid inputs, it was only a matter of time before a valid input was spat out that met the exact preconditions for the bug. And, since, it’s found lots of other issues, too. I’ve even made differential fuzzers which have had success in identifying some consistency bugs between versions and sub-implementations.

So, we’ve found all the bugs now, right?

Takeaways

I recognise that this section is, frankly, a bit hard to interpret. We started out by saying that maintaining the similarity of inputs was important for coverage-based fuzzers, then ended by saying, “oh, it actually wasn’t if we were using arbitrary”. So, what is it?

The sad answer is simply that our testing is incomplete – and will always be incomplete. While we are now capable of producing well-formed, highly-complex, and interesting inputs quickly, we lack guidance when actually performing mutations. Our inputs are very dissimilar across mutations, and we likely suffer from the JSON loading problem I described earlier, where we can’t find the deeper bugs dependent on the result of the parsing.

It’s unclear whether we effectively test different matching strategies, too. While our inputs are now grand and complex, they may not be effectively testing the matching code since we don’t know how relevant our haystacks are to our patterns. The fuzzer has, resultantly, missed several crashes and incorrectnesses discovered by other users.

Finally, since the differential fuzzers are not actively in use, we rely entirely on assertions and crashes. In other words, we cannot find correctness issues at all. Even if differential fuzzers were enabled, there is no guarantee that they would catch all the issues, especially since we don’t explore the program space very well for matching.

I could ramble on for some time about other weaknesses of the fuzzers now in use here, but that’s neither here nor there. The main thing that you, dear reader, should consider is that how your fuzzer is internally trying to test the program and how much time you’re willing to spend to make the fuzzer work well. The fuzzer runtime is not magic and neither is the harness. You cannot expect it to reliably produce inputs that, as passed by your harness, will trigger bugs in your program. Moreover, you cannot expect that you will magically find bugs for which you have no means of detecting. You must critically think about how inputs will be generated, mutated, interpreted, and executed, and decide how much time you will spend to make the fuzzer effective for finding bugs in your target.

But almost certainly, byte-level mutations are not enough.

Target 2: PCRE2

Continued in Part 2, released 2024.07.15 2024.07.20 2024.08.24 (got a little busy!).

In recent years the interest in obfuscation has increased, mainly because people want to protect their intellectual property. Unfortunately, most of what’s been written is focused on the theoretical aspects. In this article, we will discuss the practical engineering challenges of developing a low-footprint virtual machine interpreter. The VM is easily embeddable, built on open-source technology and has various hardening features that were achieved with minimal effort.

Introduction

In addition to protecting intellectual property, a minimal virtual machine can be useful for other reasons. You might want to have an embeddable interpreter to execute business logic (shellcode), without having to deal with RWX memory. It can also be useful as an educational tool, or just for fun.

Creating a custom VM architecture (similar to VMProtect/Themida) means that we would have to deal with binary rewriting/lifting or write our own compiler. Instead, we decided to use a preexisting architecture, which would be supported by LLVM: RISC-V. This architecture is already widely used for educational purposes and has the advantage of being very simple to understand and implement.

Initially, the main contender was WebAssembly. However, existing interpreters were very bloated and would also require dealing with a binary format. Additionally, it looks like WASM64 is very underdeveloped and our memory model requires 64-bit pointer support. SPARC and PowerPC were also considered, but RISC-V seems to be more popular and there are a lot more resources available for it.

WebAssembly was designed for sandboxing and therefore strictly separates guest and host memory. Because we will be writing our own RISC-V interpreter, we chose to instead share memory between the guest and the host. This means that pointers in the RISC-V execution context (the guest) are valid in the host process and vice-versa.

As a result, the instructions responsible for reading/writing memory can be implemented as a simple memcpy call and we do not need additional code to translate/validate memory accesses (which helps with our goal of small code size). With this property, we need to implement only two system calls to perform arbitrary operations in the host process:

uintptr_t riscvm_get_peb();
uintptr_t riscvm_host_call(uintptr_t rip, uintptr_t args[13]);

The riscvm_get_peb is Windows-specific and it allows us to resolve exports, which we can then pass to the riscvm_host_call function to execute arbitrary code. Additionally, an optional host_syscall stub could be implemented, but this is not strictly necessary since we can just call the functions in ntdll.dll instead.

Toolchain and CRT

To keep the interpreter footprint as low as possible, we decided to develop a toolchain that outputs a freestanding binary. The goal is to copy this binary into memory and point the VM’s program counter there to start execution. Because we are in freestanding mode, there is no C runtime available to us, this requires us to handle initialization ourselves.

As an example, we will use the following hello.c file:

int _start() {
    int result = 0;
    for(int i = 0; i < 52; i++) {
        result += *(volatile int*)&i;
    }
    return result + 11;
}

We compile the program with the following incantation:

clang -target riscv64 -march=rv64im -mcmodel=medany -Os -c hello.c -o hello.o

And then verify by disassembling the object:

$ llvm-objdump --disassemble hello.o

hello.o:        file format elf64-littleriscv

0000000000000000 <_start>:
       0: 13 01 01 ff   addi    sp, sp, -16
       4: 13 05 00 00   li      a0, 0
       8: 23 26 01 00   sw      zero, 12(sp)
       c: 93 05 30 03   li      a1, 51

0000000000000010 <.LBB0_1>:
      10: 03 26 c1 00   lw      a2, 12(sp)
      14: 33 05 a6 00   add     a0, a2, a0
      18: 9b 06 16 00   addiw   a3, a2, 1
      1c: 23 26 d1 00   sw      a3, 12(sp)
      20: 63 40 b6 00   blt     a2, a1, 0x20 <.LBB0_1+0x10>
      24: 1b 05 b5 00   addiw   a0, a0, 11
      28: 13 01 01 01   addi    sp, sp, 16
      2c: 67 80 00 00   ret

The hello.o is a regular ELF object file. To get a freestanding binary we need to invoke the linker with a linker script:

ENTRY(_start)

LINK_BASE = 0x8000000;

SECTIONS
{
    . = LINK_BASE;
    __base = .;

    .text : ALIGN(16) {
        . = LINK_BASE;
        *(.text)
        *(.text.*)
    }

    .data : {
        *(.rodata)
        *(.rodata.*)
        *(.data)
        *(.data.*)
        *(.eh_frame)
    }

    .init : {
        __init_array_start = .;
        *(.init_array)
        __init_array_end = .;
    }

    .bss : {
        *(.bss)
        *(.bss.*)
        *(.sbss)
        *(.sbss.*)
    }

    .relocs : {
        . = . + SIZEOF(.bss);
        __relocs_start = .;
    }
}

This script is the result of an excessive amount of swearing and experimentation. The format is .name : { ... } where .name is the destination section and the stuff in the brackets is the content to paste in there. The special . operator is used to refer to the current position in the binary and we define a few special symbols for use by the runtime:

These symbols are declared as extern in the C code and they will be resolved at link-time. While it may seem confusing at first that we have a destination section, it starts to make sense once you realize the linker has to output a regular ELF executable. That ELF executable is then passed to llvm-objcopy to create the freestanding binary blob. This makes debugging a whole lot easier (because we get DWARF symbols) and since we will not implement an ELF loader, it also allows us to extract the relocations for embedding into the final binary.

To link the intermediate ELF executable and then create the freestanding hello.pre.bin:

ld.lld.exe -o hello.elf --oformat=elf -emit-relocs -T ..\lib\linker.ld --Map=hello.map hello.o
llvm-objcopy -O binary hello.elf hello.pre.bin

For debugging purposes we also output hello.map, which tells us exactly where the linker put the code/data:

             VMA              LMA     Size Align Out     In      Symbol
               0                0        0     1 LINK_BASE = 0x8000000
               0                0  8000000     1 . = LINK_BASE
         8000000                0        0     1 __base = .
         8000000          8000000       30    16 .text
         8000000          8000000        0     1         . = LINK_BASE
         8000000          8000000       30     4         hello.o:(.text)
         8000000          8000000       30     1                 _start
         8000010          8000010        0     1                 .LBB0_1
         8000030          8000030        0     1 .init
         8000030          8000030        0     1         __init_array_start = .
         8000030          8000030        0     1         __init_array_end = .
         8000030          8000030        0     1 .relocs
         8000030          8000030        0     1         . = . + SIZEOF ( .bss )
         8000030          8000030        0     1         __relocs_start = .
               0                0       18     8 .rela.text
               0                0       18     8         hello.o:(.rela.text)
               0                0       3b     1 .comment
               0                0       3b     1         <internal>:(.comment)
               0                0       30     1 .riscv.attributes
               0                0       30     1         <internal>:(.riscv.attributes)
               0                0      108     8 .symtab
               0                0      108     8         <internal>:(.symtab)
               0                0       55     1 .shstrtab
               0                0       55     1         <internal>:(.shstrtab)
               0                0       5c     1 .strtab
               0                0       5c     1         <internal>:(.strtab)

The final ingredient of the toolchain is a small Python script (relocs.py) that extracts the relocations from the ELF file and appends them to the end of the hello.pre.bin. The custom relocation format only supports R_RISCV_64 and is resolved by our CRT like so:

typedef struct
{
    uint8_t  type;
    uint32_t offset;
    int64_t  addend;
} __attribute__((packed)) Relocation;

extern uint8_t __base[];
extern uint8_t __relocs_start[];

#define LINK_BASE    0x8000000
#define R_RISCV_NONE 0
#define R_RISCV_64   2

static __attribute((noinline)) void riscvm_relocs()
{
    if (*(uint32_t*)__relocs_start != 'ALER')
    {
        asm volatile("ebreak");
    }

    uintptr_t load_base = (uintptr_t)__base;

    for (Relocation* itr = (Relocation*)(__relocs_start + sizeof(uint32_t)); itr->type != R_RISCV_NONE; itr++)
    {
        if (itr->type == R_RISCV_64)
        {
            uint64_t* ptr = (uint64_t*)((uintptr_t)itr->offset - LINK_BASE + load_base);
            *ptr -= LINK_BASE;
            *ptr += load_base;
        }
        else
        {
            asm volatile("ebreak");
        }
    }
}

As you can see, the __base and __relocs_start magic symbols are used here. The only reason this works is the -mcmodel=medany we used when compiling the object. You can find more details in this article and in the RISC-V ELF Specification. In short, this flag allows the compiler to assume that all code will be emitted in a 2 GiB address range, which allows more liberal PC-relative addressing. The R_RISCV_64 relocation type gets emitted when you put pointers in the .data section:

void* functions[] = {
    &function1,
    &function2,
};

This also happens when using vtables in C++, and we wanted to support these properly early on, instead of having to fight with horrifying bugs later.

The next piece of the CRT involves the handling of the init arrays (which get emitted by global instances of classes that have a constructor):

typedef void (*InitFunction)();
extern InitFunction __init_array_start;
extern InitFunction __init_array_end;

static __attribute((optnone)) void riscvm_init_arrays()
{
    for (InitFunction* itr = &__init_array_start; itr != &__init_array_end; itr++)
    {
        (*itr)();
    }
}

Frustratingly, we were not able to get this function to generate correct code without the __attribute__((optnone)). We suspect this has to do with aliasing assumptions (the start/end can technically refer to the same memory), but we didn’t investigate this further.

Interpreter internals

Note: the interpreter was initially based on riscvm.c by edubart. However, we have since completely rewritten it in C++ to better suit our purpose.

Based on the RISC-V Calling Conventions document, we can create an enum for the 32 registers:

enum RegIndex
{
    reg_zero, // always zero (immutable)
    reg_ra,   // return address
    reg_sp,   // stack pointer
    reg_gp,   // global pointer
    reg_tp,   // thread pointer
    reg_t0,   // temporary
    reg_t1,
    reg_t2,
    reg_s0,   // callee-saved
    reg_s1,
    reg_a0,   // arguments
    reg_a1,
    reg_a2,
    reg_a3,
    reg_a4,
    reg_a5,
    reg_a6,
    reg_a7,
    reg_s2,   // callee-saved
    reg_s3,
    reg_s4,
    reg_s5,
    reg_s6,
    reg_s7,
    reg_s8,
    reg_s9,
    reg_s10,
    reg_s11,
    reg_t3,   // temporary
    reg_t4,
    reg_t5,
    reg_t6,
};

We just need to add a pc register and we have the structure to represent the RISC-V CPU state:

struct riscvm
{
    int64_t  pc;
    uint64_t regs[32];
};

It is important to keep in mind that the zero register is always set to 0 and we have to prevent writes to it by using a macro:

#define reg_write(idx, value)        \
    do                               \
    {                                \
        if (LIKELY(idx != reg_zero)) \
        {                            \
            self->regs[idx] = value; \
        }                            \
    } while (0)

The instructions (ignoring the optional compression extension) are always 32-bits in length and can be cleanly expressed as a union:

union Instruction
{
    struct
    {
        uint32_t compressed_flags : 2;
        uint32_t opcode           : 5;
        uint32_t                  : 25;
    };

    struct
    {
        uint32_t opcode : 7;
        uint32_t rd     : 5;
        uint32_t funct3 : 3;
        uint32_t rs1    : 5;
        uint32_t rs2    : 5;
        uint32_t funct7 : 7;
    } rtype;

    struct
    {
        uint32_t opcode : 7;
        uint32_t rd     : 5;
        uint32_t funct3 : 3;
        uint32_t rs1    : 5;
        uint32_t rs2    : 5;
        uint32_t shamt  : 1;
        uint32_t imm    : 6;
    } rwtype;

    struct
    {
        uint32_t opcode : 7;
        uint32_t rd     : 5;
        uint32_t funct3 : 3;
        uint32_t rs1    : 5;
        uint32_t imm    : 12;
    } itype;

    struct
    {
        uint32_t opcode : 7;
        uint32_t rd     : 5;
        uint32_t imm    : 20;
    } utype;

    struct
    {
        uint32_t opcode : 7;
        uint32_t rd     : 5;
        uint32_t imm12  : 8;
        uint32_t imm11  : 1;
        uint32_t imm1   : 10;
        uint32_t imm20  : 1;
    } ujtype;

    struct
    {
        uint32_t opcode : 7;
        uint32_t imm5   : 5;
        uint32_t funct3 : 3;
        uint32_t rs1    : 5;
        uint32_t rs2    : 5;
        uint32_t imm7   : 7;
    } stype;

    struct
    {
        uint32_t opcode   : 7;
        uint32_t imm_11   : 1;
        uint32_t imm_1_4  : 4;
        uint32_t funct3   : 3;
        uint32_t rs1      : 5;
        uint32_t rs2      : 5;
        uint32_t imm_5_10 : 6;
        uint32_t imm_12   : 1;
    } sbtype;

    int16_t  chunks16[2];
    uint32_t bits;
};
static_assert(sizeof(Instruction) == sizeof(uint32_t), "");

There are 13 top-level opcodes (Instruction.opcode) and some of those opcodes have another field that further specializes the functionality (i.e. Instruction.itype.funct3). To keep the code readable, the enumerations for the opcode are defined in opcodes.h. The interpreter is structured to have handler functions for the top-level opcode in the following form:

bool handler_rv64_<opcode>(riscvm_ptr self, Instruction inst);

As an example, we can look at the handler for the lui instruction (note that the handlers themselves are responsible for updating pc):

ALWAYS_INLINE static bool handler_rv64_lui(riscvm_ptr self, Instruction inst)
{
    int64_t imm = bit_signer(inst.utype.imm, 20) << 12;
    reg_write(inst.utype.rd, imm);

    self->pc += 4;
    dispatch(); // return true;
}

The interpreter executes until one of the handlers returns false, indicating the CPU has to halt:

void riscvm_run(riscvm_ptr self)
{
    while (true)
    {
        Instruction inst;
        inst.bits = *(uint32_t*)self->pc;
        if (!riscvm_execute_handler(self, inst))
            break;
    }
}

Plenty of articles have been written about the semantics of RISC-V, so you can look at the source code if you’re interested in the implementation details of individual instructions. The structure of the interpreter also allows us to easily implement obfuscation features, which we will discuss in the next section.

For now, we will declare the handler functions as __attribute__((always_inline)) and set the -fno-jump-tables compiler option, which gives us a riscvm_run function that (comfortably) fits into a single page (0xCA4 bytes):

Hardening features

A regular RISC-V interpreter is fun, but an attacker can easily reverse engineer our payload by throwing it into Ghidra to decompile it. To force the attacker to at least look at our VM interpreter, we implemented a few security features. These features are implemented in a Python script that parses the linker MAP file and directly modifies the opcodes: encrypt.py.

Opcode shuffling

The most elegant (and likely most effective) obfuscation is to simply reorder the enums of the instruction opcodes and sub-functions. The shuffle.py script is used to generate shuffled_opcodes.h, which is then included into riscvm.h instead of opcodes.h to mix the opcodes:

#ifdef OPCODE_SHUFFLING
#warning Opcode shuffling enabled
#include "shuffled_opcodes.h"
#else
#include "opcodes.h"
#endif // OPCODE_SHUFFLING

There is also a shuffled_opcodes.json file generated, which is parsed by encrypt.py to know how to shuffle the assembled instructions.

Because enums are used for all the opcodes, we only need to recompile the interpreter to obfuscate it; there is no additional complexity cost in the implementation.

Bytecode encryption

To increase diversity between payloads for the same VM instance, we also employ a simple ‘encryption’ scheme on top of the opcode:

ALWAYS_INLINE static uint32_t tetra_twist(uint32_t input)
{
    /**
     * Custom hash function that is used to generate the encryption key.
     * This has strong avalanche properties and is used to ensure that
     * small changes in the input result in large changes in the output.
     */

    constexpr uint32_t prime1 = 0x9E3779B1; // a large prime number

    input ^= input >> 15;
    input *= prime1;
    input ^= input >> 12;
    input *= prime1;
    input ^= input >> 4;
    input *= prime1;
    input ^= input >> 16;

    return input;
}

ALWAYS_INLINE static uint32_t transform(uintptr_t offset, uint32_t key)
{
    uint32_t key2 = key + offset;
    return tetra_twist(key2);
}

ALWAYS_INLINE static uint32_t riscvm_fetch(riscvm_ptr self)
{
    uint32_t data;
    memcpy(&data, (const void*)self->pc, sizeof(data));

#ifdef CODE_ENCRYPTION
    return data ^ transform(self->pc - self->base, self->key);
#else
    return data;
#endif // CODE_ENCRYPTION
}

The offset relative to the start of the bytecode is used as the seed to a simple transform function. The result of this function is XOR’d with the instruction data before decoding. The exact transformation doesn’t really matter, because an attacker can always observe the decrypted bytecode at runtime. However, static analysis becomes more difficult and pattern-matching the payload is prevented, all for a relatively small increase in VM implementation complexity.

It would be possible to encrypt the contents of the .data section of the payload as well, but we would have to completely decrypt it in memory before starting execution anyway. Technically, it would be also possible to implement a lazy encryption scheme by customizing the riscvm_read and riscvm_write functions to intercept reads/writes to the payload region, but this idea was not pursued further.

Threaded handlers

The most interesting feature of our VM is that we only need to make minor code modifications to turn it into a so-called threaded interpreter. Threaded code is a well-known technique used both to speed up emulators and to introduce indirect branches that complicate reverse engineering. It is called threading because the execution can be visualized as a thread of handlers that directly branch to the next handler. There is no classical dispatch function, with an infinite loop and a switch case for each opcode inside. The performance improves because there are fewer false-positives in the branch predictor when executing threaded code. You can find more information about threaded interpreters in the Dispatch Techniques section of the YETI paper.

The first step is to construct a handler table, where each handler is placed at the index corresponding to each opcode. To do this we use a small snippet of constexpr C++ code:

typedef bool (*riscvm_handler_t)(riscvm_ptr, Instruction);

static constexpr std::array<riscvm_handler_t, 32> riscvm_handlers = []
{
    // Pre-populate the table with invalid handlers
    std::array<riscvm_handler_t, 32> result = {};
    for (size_t i = 0; i < result.size(); i++)
    {
        result[i] = handler_rv64_invalid;
    }

    // Insert the opcode handlers at the right index
#define INSERT(op) result[op] = HANDLER(op)
    INSERT(rv64_load);
    INSERT(rv64_fence);
    INSERT(rv64_imm64);
    INSERT(rv64_auipc);
    INSERT(rv64_imm32);
    INSERT(rv64_store);
    INSERT(rv64_op64);
    INSERT(rv64_lui);
    INSERT(rv64_op32);
    INSERT(rv64_branch);
    INSERT(rv64_jalr);
    INSERT(rv64_jal);
    INSERT(rv64_system);
#undef INSERT
    return result;
}();

With the riscvm_handlers table populated we can define the dispatch macro:

#define dispatch()                                       \
    Instruction next;                                    \
    next.bits = riscvm_fetch(self);                      \
    if (next.compressed_flags != 0b11)                   \
    {                                                    \
        panic("compressed instructions not supported!"); \
    }                                                    \
    __attribute__((musttail)) return riscvm_handlers[next.opcode](self, next)

The musttail attribute forces the call to the next handler to be a tail call. This is only possible because all the handlers have the same function signature and it generates an indirect branch to the next handler:

The final piece of the puzzle is the new implementation of the riscvm_run function, which uses an empty riscvm_execute handler to bootstrap the chain of execution:

ALWAYS_INLINE static bool riscvm_execute(riscvm_ptr self, Instruction inst)
{
    dispatch();
}

NEVER_INLINE void riscvm_run(riscvm_ptr self)
{
    Instruction inst;
    riscvm_execute(self, inst);
}

Traditional obfuscation

The built-in hardening features that we can get with a few #ifdefs and a small Python script are good enough for a proof-of-concept, but they are not going to deter a determined attacker for a very long time. An attacker can pattern-match the VM’s handlers to simplify future reverse engineering efforts. To address this, we can employ common obfuscation techniques using LLVM obfuscation passes:

• Instruction substitution (to make pattern matching more difficult)
• Opaque predicates (to hinder static analysis)
• Inject anti-debug checks (to make dynamic analysis more difficult)

The paper Modern obfuscation techniques by Roman Oravec gives a nice overview of literature and has good data on what obfuscation passes are most effective considering their runtime overhead.

Additionally, it would also be possible to further enhance the VM’s security by duplicating handlers, but this would require extra post-processing on the payload itself. The VM itself is only part of what could be obfuscated. Obfuscating the payloads themselves is also something we can do quite easily. Most likely, manually-integrated security features (stack strings with xorstr, lazy_importer and variable encryption) will be most valuable here. However, because we use LLVM to build the payloads we can also employ automated obfuscation there. It is important to keep in mind that any overhead created in the payloads themselves is multiplied by the overhead created by the handler obfuscation, so experimentation is required to find the sweet spot for your use case.

Writing the payloads

The VM described in this post so far technically has the ability to execute arbitrary code. That being said, it would be rather annoying for an end-user to write said code. For example, we would have to manually resolve all imports and then use the riscvm_host_call function to actually execute them. These functions are executing in the RISC-V context and their implementation looks like this:

uintptr_t riscvm_host_call(uintptr_t address, uintptr_t args[13])
{
    register uintptr_t a0 asm("a0") = address;
    register uintptr_t a1 asm("a1") = (uintptr_t)args;
    register uintptr_t a7 asm("a7") = 20000;
    asm volatile("scall" : "+r"(a0) : "r"(a1), "r"(a7));
    return a0;
}

uintptr_t riscvm_get_peb()
{
    register uintptr_t a0 asm("a0") = 0;
    register uintptr_t a7 asm("a7") = 20001;
    asm volatile("scall" : "+r"(a0) : "r"(a7) : "memory");
    return a0;
}

We can get a pointer to the PEB using riscvm_get_peb and then resolve a module by its’ x65599 hash:

// Structure definitions omitted for clarity
uintptr_t riscvm_resolve_dll(uint32_t module_hash)
{
    static PEB* peb = 0;
    if (!peb)
    {
        peb = (PEB*)riscvm_get_peb();
    }
    LIST_ENTRY* begin = &peb->Ldr->InLoadOrderModuleList;
    for (LIST_ENTRY* itr = begin->Flink; itr != begin; itr = itr->Flink)
    {
        LDR_DATA_TABLE_ENTRY* entry = CONTAINING_RECORD(itr, LDR_DATA_TABLE_ENTRY, InLoadOrderLinks);
        if (entry->BaseNameHashValue == module_hash)
        {
            return (uintptr_t)entry->DllBase;
        }
    }
    return 0;
}

Once we’ve obtained the base of the module we’re interested in, we can resolve the import by walking the export table:

uintptr_t riscvm_resolve_import(uintptr_t image, uint32_t export_hash)
{
    IMAGE_DOS_HEADER*       dos_header      = (IMAGE_DOS_HEADER*)image;
    IMAGE_NT_HEADERS*       nt_headers      = (IMAGE_NT_HEADERS*)(image + dos_header->e_lfanew);
    uint32_t                export_dir_size = nt_headers->OptionalHeader.DataDirectory[0].Size;
    IMAGE_EXPORT_DIRECTORY* export_dir =
        (IMAGE_EXPORT_DIRECTORY*)(image + nt_headers->OptionalHeader.DataDirectory[0].VirtualAddress);
    uint32_t* names = (uint32_t*)(image + export_dir->AddressOfNames);
    uint32_t* funcs = (uint32_t*)(image + export_dir->AddressOfFunctions);
    uint16_t* ords  = (uint16_t*)(image + export_dir->AddressOfNameOrdinals);

    for (uint32_t i = 0; i < export_dir->NumberOfNames; ++i)
    {
        char*     name = (char*)(image + names[i]);
        uintptr_t func = (uintptr_t)(image + funcs[ords[i]]);
        // Ignore forwarded exports
        if (func >= (uintptr_t)export_dir && func < (uintptr_t)export_dir + export_dir_size)
            continue;
        uint32_t hash = hash_x65599(name, true);
        if (hash == export_hash)
        {
            return func;
        }
    }

    return 0;
}

Now we can call MessageBoxA from RISC-V with the following code:

// NOTE: We cannot use Windows.h here
#include <stdint.h>

int main()
{
    // Resolve LoadLibraryA
    auto kernel32_dll = riscvm_resolve_dll(hash_x65599("kernel32.dll", false))
    auto LoadLibraryA = riscvm_resolve_import(kernel32_dll, hash_x65599("LoadLibraryA", true))

    // Load user32.dll
    uint64_t args[13];
    args[0] = (uint64_t)"user32.dll";
    auto user32_dll = riscvm_host_call(LoadLibraryA, args);

    // Resolve MessageBoxA
    auto MessageBoxA = riscvm_resolve_import(user32_dll, hash_x65599("MessageBoxA", true));

    // Show a message to the user
    args[0] = 0; // hwnd
    args[1] = (uint64_t)"Hello from RISC-V!"; // msg
    args[2] = (uint64_t)"riscvm"; // title
    args[3] = 0; // flags
    riscvm_host_call(MessageBoxA, args);
}

With some templates/macros/constexpr tricks we can probably get this down to something more readable, but fundamentally this code will always stay annoying to write. Even if calling imports were a one-liner, we would still have to deal with the fact that we cannot use Windows.h (or any of the Microsoft headers for that matter). The reason for this is that we are cross-compiling with Clang. Even if we were to set up the include paths correctly, it would still be a major pain to get everything to compile correctly. That being said, our VM works! A major advantage of RISC-V is that, since the instruction set is simple, once the fundamentals work, we can be confident that features built on top of this will execute as expected.

Whole Program LLVM

Usually, when discussing LLVM, the compilation process is running on Linux/macOS. In this section, we will describe a pipeline that can actually be used on Windows, without making modifications to your toolchain. This is useful if you would like to analyze/fuzz/obfuscate Windows applications, which might only compile an MSVC-compatible compiler: clang-cl.

Link-time optimization (LTO)

Without LTO, the object files produced by Clang are native COFF/ELF/Mach-O files. Every file is optimized and compiled independently. The linker loads these objects and merges them together into the final executable.

When enabling LTO, the object files are instead LLVM Bitcode (.bc) files. This allows the linker to merge all the LLVM IR together and perform (more comprehensive) whole-program optimizations. After the LLVM IR has been optimized, the native code is generated and the final executable produced. The diagram below comes from the great Link-time optimisation (LTO) post by Ryan Stinnet:

Compiler wrappers

Unfortunately, it can be quite annoying to write an executable that can replace the compiler. It is quite simple when dealing with a few object files, but with bigger projects it gets quite tricky (especially when CMake is involved). Existing projects are WLLVM and gllvm, but they do not work nicely on Windows. When using CMake, you can use the CMAKE_<LANG>_COMPILER_LAUNCHER variables and intercept the compilation pipeline that way, but that is also tricky to deal with.

On Windows, things are more complex than on Linux. This is because Clang uses a different program to link the final executable and correctly intercepting this process can become quite challenging.

Embedding bitcode

To achieve our goal of post-processing the bitcode of the whole program, we need to enable bitcode embedding. The first flag we need is -flto, which enables LTO. The second flag is -lto-embed-bitcode, which isn’t documented very well. When using clang-cl, you also need a special incantation to enable it:

set(EMBED_TYPE "post-merge-pre-opt") # post-merge-pre-opt/optimized
if(NOT CMAKE_CXX_COMPILER_ID MATCHES "Clang")
    if(WIN32)
        message(FATAL_ERROR "clang-cl is required, use -T ClangCL --fresh")
    else()
        message(FATAL_ERROR "clang compiler is required")
    endif()
elseif(CMAKE_CXX_COMPILER_FRONTEND_VARIANT MATCHES "^MSVC$")
    # clang-cl
    add_compile_options(-flto)
    add_link_options(/mllvm:-lto-embed-bitcode=${EMBED_TYPE})
elseif(WIN32)
    # clang (Windows)
    add_compile_options(-fuse-ld=lld-link -flto)
    add_link_options(-Wl,/mllvm:-lto-embed-bitcode=${EMBED_TYPE})
else()
	# clang (Linux)
    add_compile_options(-fuse-ld=lld -flto)
    add_link_options(-Wl,-lto-embed-bitcode=${EMBED_TYPE})
endif()

The -lto-embed-bitcode flag creates an additional .llvmbc section in the final executable that contains the bitcode. It offers three settings:

-lto-embed-bitcode=<value> - Embed LLVM bitcode in object files produced by LTO
    =none                  - Do not embed 
    =optimized             - Embed after all optimization passes
    =post-merge-pre-opt    - Embed post merge, but before optimizations

Once the bitcode is embedded within the output binary, it can be extracted using llvm-objcopy and disassembled with llvm-dis. This is normally done as the follows:

llvm-objcopy --dump-section=.llvmbc=program.bc program
llvm-dis program.bc > program.ll

Unfortunately, we discovered a bug/oversight in LLD on Windows. The section is extracted without errors, but llvm-dis fails to load the bitcode. The reason for this is that Windows executables have a FileAlignment attribute, leading to additional padding with zeroes. To get valid bitcode, you need to remove some of these trailing zeroes:

import argparse
import sys
import pefile

def main():
    # Parse the arguments
    parser = argparse.ArgumentParser()
    parser.add_argument("executable", help="Executable with embedded .llvmbc section")
    parser.add_argument("--output", "-o", help="Output file name", required=True)
    args = parser.parse_args()
    executable: str = args.executable
    output: str = args.output

    # Find the .llvmbc section
    pe = pefile.PE(executable)
    llvmbc = None
    for section in pe.sections:
        if section.Name.decode("utf-8").strip("\x00") == ".llvmbc":
            llvmbc = section
            break
    if llvmbc is None:
        print("No .llvmbc section found")
        sys.exit(1)

    # Recover the bitcode and write it to a file
    with open(output, "wb") as f:
        data = bytearray(llvmbc.get_data())
        # Truncate all trailing null bytes
        while data[-1] == 0:
            data.pop()
        # Recover alignment to 4
        while len(data) % 4 != 0:
            data.append(0)
        # Add a block end marker
        for _ in range(4):
            data.append(0)
        f.write(data)

if __name__ == "__main__":
    main()

In our testing, this doesn’t have any issues, but there might be cases where this heuristic does not work properly. In that case, a potential solution could be to brute force the amount of trailing zeroes, until the bitcode parses without errors.

Applications

Now that we have access to our program’s bitcode, several applications become feasible:

• Write an analyzer to identify potentially interesting locations within the program.
• Instrument the bitcode and then re-link the executable, which is particularly useful for code coverage while fuzzing.
• Obfuscate the bitcode before re-linking the executable, enhancing security.
• IR retargeting, where the bitcode compiled for one architecture can be used on another.

Relinking the executable

The bitcode itself unfortunately does not contain enough information to re-link the executable (although this is something we would like to implement upstream). We could either manually attempt to reconstruct the linker command line (with tools like Process Monitor), or use LLVM plugin support. Plugin support is not really functional on Windows (although there is some indication that Sony is using it for their PS4/PS5 toolchain), but we can still load an arbitrary DLL using the -load command line flag. Once we loaded our DLL, we can hijack the executable command line and process the flags to generate a script for re-linking the program after our modifications are done.

Retargeting LLVM IR

Ideally, we would want to write code like this and magically get it to run in our VM:

#include <Windows.h>

int main()
{
    MessageBoxA(0, "Hello from RISC-V!", "riscvm", 0);
}

Luckily this is entirely possible, it just requires writing a (fairly) simple tool to perform transformations on the Bitcode of this program (built using clang-cl). In the coming sections, we will describe how we managed to do this using Microsoft Visual Studio’s official LLVM integration (i.e. without having to use a custom fork of clang-cl).

The LLVM IR of the example above looks roughly like this (it has been cleaned up slightly for readability):

source_filename = "hello.c"
target datalayout = "e-m:w-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-windows-msvc19.38.33133"

@message = dso_local global [19 x i8] c"Hello from RISC-V!\00", align 16
@title = dso_local global [7 x i8] c"riscvm\00", align 1

; Function Attrs: noinline nounwind optnone uwtable
define dso_local i32 @main() #0 {
  %1 = call i32 @MessageBoxA(ptr noundef null, ptr noundef @message, ptr noundef @title, i32 noundef 0)
  ret i32 0
}

declare dllimport i32 @MessageBoxA(ptr noundef, ptr noundef, ptr noundef, i32 noundef) #1

attributes #0 = { noinline nounwind optnone uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #1 = { "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }

!llvm.linker.options = !{!0, !0}
!llvm.module.flags = !{!1, !2, !3}
!llvm.ident = !{!4}

!0 = !{!"/DEFAULTLIB:uuid.lib"}
!1 = !{i32 1, !"wchar_size", i32 2}
!2 = !{i32 8, !"PIC Level", i32 2}
!3 = !{i32 7, !"uwtable", i32 2}
!4 = !{!"clang version 16.0.5"}

To retarget this code to RISC-V, we need to do the following:

• Collect all the functions with a dllimport storage class.
• Generate a riscvm_imports function that resolves all the function addresses of the imports.
• Replace the dllimport functions with stubs that use riscvm_host_call to call the import.
• Change the target triple to riscv64-unknown-unknown and adjust the data layout.
• Compile the retargeted bitcode and link it together with crt0 to create the final payload.

Adjusting the metadata

After loading the LLVM IR Module, the first step is to change the DataLayout and the TargetTriple to be what the RISC-V backend expects:

module.setDataLayout("e-m:e-p:64:64-i64:64-i128:128-n32:64-S128");
module.setTargetTriple("riscv64-unknown-unknown");
module.setSourceFileName("transpiled.bc");

The next step is to collect all the dllimport functions for later processing. Additionally, a bunch of x86-specific function attributes are removed from every function:

std::vector<Function*> importedFunctions;
for (Function& function : module.functions())
{
	// Remove x86-specific function attributes
	function.removeFnAttr("target-cpu");
	function.removeFnAttr("target-features");
	function.removeFnAttr("tune-cpu");
	function.removeFnAttr("stack-protector-buffer-size");

	// Collect imported functions
	if (function.hasDLLImportStorageClass() && !function.getName().startswith("riscvm_"))
	{
		importedFunctions.push_back(&function);
	}
	function.setDLLStorageClass(GlobalValue::DefaultStorageClass);

Finally, we have to remove the llvm.linker.options metadata to make sure we can pass the IR to llc or clang without errors.

Import map

The LLVM IR only has the dllimport storage class to inform us that a function is imported. Unfortunately, it does not provide us with the DLL the function comes from. Because this information is only available at link-time (in files like user32.lib), we decided to implement an extra -importmap argument.

The extract-bc script that extracts the .llvmbc section now also has to extract the imported functions and what DLL they come from:

with open(importmap, "wb") as f:
	for desc in pe.DIRECTORY_ENTRY_IMPORT:
		dll = desc.dll.decode("utf-8")
		for imp in desc.imports:
			name = imp.name.decode("utf-8")
			f.write(f"{name}:{dll}\n".encode("utf-8"))

Currently, imports by ordinal and API sets are not supported, but we can easily make sure those do not occur when building our code.

Creating the import stubs

For every dllimport function, we need to add some IR to riscvm_imports to resolve the address. Additionally, we have to create a stub that forwards the function arguments to riscvm_host_call. This is the generated LLVM IR for the MessageBoxA stub:

; Global variable to hold the resolved import address
@import_MessageBoxA = private global ptr null

define i32 @MessageBoxA(ptr noundef %0, ptr noundef %1, ptr noundef %2, i32 noundef %3) local_unnamed_addr #1 {
entry:
  %args = alloca ptr, i32 13, align 8
  %arg3_zext = zext i32 %3 to i64
  %arg3_cast = inttoptr i64 %arg3_zext to ptr
  %import_address = load ptr, ptr @import_MessageBoxA, align 8
  %arg0_ptr = getelementptr ptr, ptr %args, i32 0
  store ptr %0, ptr %arg0_ptr, align 8
  %arg1_ptr = getelementptr ptr, ptr %args, i32 1
  store ptr %1, ptr %arg1_ptr, align 8
  %arg2_ptr = getelementptr ptr, ptr %args, i32 2
  store ptr %2, ptr %arg2_ptr, align 8
  %arg3_ptr = getelementptr ptr, ptr %args, i32 3
  store ptr %arg3_cast, ptr %arg3_ptr, align 8
  %return = call ptr @riscvm_host_call(ptr %import_address, ptr %args)
  %return_cast = ptrtoint ptr %return to i64
  %return_trunc = trunc i64 %return_cast to i32
  ret i32 %return_trunc
}