Architecture-Agnostic Vulnerability Research: Linear Lattice Predicate Detection Across CPU Architectures

Written By Blake De Garza

Table of Contents

  1. Introduction
  2. The P-Code Abstraction Layer
  3. Architecture-Agnostic LLPD Framework
  4. x86-64 Deep Dive
  5. ARM Deep Dive
  6. PowerPC Deep Dive
  7. MIPS Deep Dive
  8. RISC-V: Emerging Architecture Considerations
  9. Cross-Architecture Predicate Comparison Matrix
  10. Emulation-Based Detection Implementation
  11. Constraint Solving and Exploit Synthesis
  12. Practical Considerations and Limitations

1. Introduction

Linear Lattice Predicate Detection (LLPD) was originally developed for detecting concurrency bugs in distributed and multi-threaded systems. The core insight -- that the set of consistent global states forms a lattice, and properties of interest (predicates) can be efficiently evaluated over this lattice -- generalizes far beyond concurrency bugs.

This document presents the extension of LLPD to architecture-agnostic vulnerability research: applying the lattice framework to detect exploitable memory corruption across different CPU architectures. The key innovation is that by operating on Ghidra's P-Code intermediate representation rather than raw machine instructions, the same LLPD predicates detect buffer overflows, return address overwrites, and register control on x86-64, ARM, PowerPC, MIPS, and RISC-V without modification to the core algorithm.

However, architecture-agnostic analysis is necessary but not sufficient. Each architecture has unique calling conventions, stack layouts, hardware mitigations, and instruction semantics that affect whether a detected predicate violation is actually exploitable. This document provides deep dives into each architecture's specific characteristics, how they interact with the LLPD framework, and how to implement architecture-aware predicate evaluators that produce actionable results.

Prerequisites: Familiarity with the LLPD framework as described in deep_dive.md, basic understanding of CPU architecture concepts (registers, stack frames, calling conventions), and reverse engineering fundamentals.

2. The P-Code Abstraction Layer

Ghidra's P-Code is a register-transfer language (RTL) that decomposes every machine instruction into a sequence of atomic operations. A single x86-64 PUSH RBP becomes multiple P-Code operations:

RSP = INT_SUB RSP, 8        ; decrement stack pointer
STORE [RSP], RBP             ; write RBP to stack

Similarly, an ARM STP X29, X30, [SP, #-16]! becomes:

SP = INT_SUB SP, 16          ; pre-decrement stack pointer
STORE [SP], X29              ; write frame pointer
STORE [SP + 8], X30          ; write link register (return address)

Despite the surface-level differences, both sequences perform the same semantic operation: save a return-related value to the stack. At the P-Code level, the LLPD framework sees STORE operations writing to stack memory and can reason about them uniformly.

P-Code operations relevant to LLPD:

P-Code Op LLPD Event Type Description
STORE Write event Any write to memory (stack, heap, global)
LOAD Read event Any read from memory
COPY Taint propagation Data movement between registers/varnodes
INT_ADD, INT_SUB, etc. Taint propagation Arithmetic on potentially tainted values
BRANCH, CBRANCH Path fork Creates new paths in the CFG lattice
BRANCHIND Sink (indirect branch) Computed jump -- potential control flow hijack
CALLIND Sink (indirect call) Computed call -- potential control flow hijack
CALL Happens-before edge Call establishes ordering between caller and callee
RETURN Sink (ret instruction) Pops saved return address -- if corrupted, hijack

The P-Code abstraction means that the LLPD event model needs only one mapping layer: from P-Code operations to LLPD events. All architecture-specific instruction decoding is handled by Ghidra's language modules, which are already battle-tested across hundreds of processor variants.

3. Architecture-Agnostic LLPD Framework

3.1 Unified Event Model

In the runtime Java LLPD system, events are captured by EventCollector calls inserted into the program. In the binary analysis LLPD system, events are extracted from P-Code by walking the function's control flow graph. The unified event model maps both domains to the same structure:

Event {
    type:        STORE | LOAD | BRANCH | CALL | RETURN
    address:     the P-Code operation address (SeqNum)
    target:      the memory address being accessed (for STORE/LOAD)
    value:       the value being written (for STORE) or read (for LOAD)
    taintState:  set of input bytes that influence this value
    vectorClock: causal ordering relative to other events on this path
    pathId:      which CFG path this event belongs to
}

The taintState field is the critical addition for exploit detection. It tracks which bytes of the original input influence the current value through a chain of P-Code operations. When a STORE event writes a tainted value to the saved return address location, the taintState tells us exactly which input bytes to control.

3.2 Cross-Architecture Vector Clocks

In the runtime LLPD system, vector clocks track causal ordering across threads. In the binary analysis system, vector clocks track causal ordering across CFG paths. Each path through the function's control flow graph is treated as a "process" with its own clock.

At branch points (CBRANCH), the path forks and each fork inherits the parent's vector clock. At join points (where control flow from multiple paths converges), the lattice builder takes the element-wise maximum of the converging clocks, establishing a happens-before relationship.

This mapping is exact:

Runtime LLPD Binary Analysis LLPD
Thread CFG path
Thread fork (Thread.start()) Conditional branch (CBRANCH)
Thread join (Thread.join()) Path convergence at a basic block with multiple predecessors
Shared memory access Stack/heap memory access visible across paths
Lock acquire/release Not applicable (single-threaded emulation)

The vector clock mechanism ensures that the lattice builder only considers consistent combinations of path states. A cut that includes a post-branch state from the true path and a pre-branch state from the fall-through path would be inconsistent -- the branch decision happens atomically, so both paths start from the same pre-branch state.

3.3 Architecture-Independent Consistent Cuts

A consistent cut through the CFG lattice represents a reachable program state at a specific point in the function's execution. The cut includes one position from each active path, and the consistency condition requires that all happens-before relationships are respected.

For exploit detection, the interesting cuts are those where:

  1. A STORE event writes tainted data to a stack location
  2. That stack location is at or beyond the saved return address offset
  3. The path from the input source to the corrupted store is feasible (all branch conditions are satisfiable)

The lattice traversal systematically enumerates these cuts, and at each cut, the exploit predicates evaluate whether the current state represents a exploitable condition. This is the same BFS algorithm used in the runtime system (LatticeBuilder), operating on CFG paths instead of thread timelines.

4. x86-64 Deep Dive

4.1 Stack Frame Layout and RIP Semantics

x86-64 (AMD64 / Intel 64) uses the most straightforward stack-based return address mechanism. The CALL instruction pushes the 8-byte return address (RIP) onto the stack, and the RET instruction pops it back into RIP. The standard prologue:

push rbp          ; save caller's frame pointer (8 bytes)
mov  rbp, rsp     ; establish new frame pointer
sub  rsp, N       ; allocate N bytes for local variables

Produces this stack layout (growing downward):

Higher addresses
+------------------+
| caller's frame   |
+------------------+
| return address   | <- RBP + 8   (SAVED RIP - the primary target)
+------------------+
| saved RBP        | <- RBP       (frame pointer - secondary target)
+------------------+
| local var N      | <- RBP - 8
| local var N-1    | <- RBP - 16
| ...              |
| local buffer[0]  | <- RBP - K   (buffer base)
+------------------+
| (red zone/pad)   | <- RSP
+------------------+
Lower addresses

The overwrite distance from a buffer at RBP - K to the saved RIP at RBP + 8 is K + 8 bytes (K bytes of buffer + 8 bytes of saved RBP). This is the value the LLPD RIP Control Predicate computes.

Key x86-64 characteristics for LLPD:

  • Endianness: Little-endian. The byte at the lowest address is the least significant byte of the return address. Writing \x41\x41\x41\x41\x41\x41\x41\x41 places 0x4141414141414141 in RIP.
  • Red zone: The System V ABI reserves 128 bytes below RSP that leaf functions can use without adjusting RSP. This means buffer overflows in leaf functions may need to cross the red zone before reaching the return address.
  • Stack canaries: GCC's -fstack-protector inserts a random canary value between local variables and the saved RBP. The LLPD predicate should detect canary presence (look for xor with fs:[0x28] in the prologue and a comparison before the epilogue) and note that exploitation requires a canary leak.
  • Shadow stack (CET): Intel CET maintains a separate, hardware-protected shadow stack containing a copy of each return address. Even if the main stack's return address is overwritten, RET compares against the shadow stack and faults on mismatch. The LLPD predicate should check for CET enablement via ENDBR64 markers.

4.2 LLPD Predicates for x86-64

RIP Control Predicate (x86-64 specialization):

PREDICATE RIPControl_x86_64:
  INPUT:  function F, stack frame layout, tainted STORE events
  FOR EACH buffer B in F's stack frame:
    distance = offset(saved_RIP) - offset(B)
    IF distance > 0 AND distance < max_overflow_size:
      FOR EACH STORE event E that writes to B with taint:
        IF E.taintState covers bytes [distance .. distance+7]:
          REPORT "RIP control via buffer '%s': %d bytes overflow needed"
                 % (B.name, distance + 8)
          EXTRACT constraint: input[distance..distance+7] -> RIP value

RBP Control Predicate (x86-64 specialization):

Controlling RBP (the saved frame pointer) enables a stack pivot attack. If the attacker overwrites saved RBP with a chosen value, the caller's LEAVE instruction (MOV RSP, RBP; POP RBP) will set RSP to the attacker's value, redirecting the stack to an attacker-controlled memory region. This predicate is secondary to RIP control but can be more powerful in some scenarios:

PREDICATE RBPControl_x86_64:
  distance_to_rbp = offset(saved_RBP) - offset(B)
  IF distance_to_rbp > 0 AND taint covers [distance_to_rbp .. distance_to_rbp+7]:
    REPORT "Stack pivot via RBP overwrite: %d bytes overflow" % (distance_to_rbp + 8)

Format String Predicate (x86-64 specialization):

x86-64's calling convention passes the first 6 integer/pointer arguments in registers (RDI, RSI, RDX, RCX, R8, R9). Additional arguments go on the stack. When printf-family functions are called with a user-controlled format string, the attacker can read stack values with %x / %p and write arbitrary values with %n. The LLPD predicate detects when a tainted varnode flows into the first argument (RDI) of a printf-family call:

PREDICATE FormatString_x86_64:
  FOR EACH CALL to printf/sprintf/fprintf/snprintf:
    IF RDI is tainted at call site:
      REPORT "Format string vulnerability: tainted format argument"
      NOTE: first 5 format args from RSI, RDX, RCX, R8, R9; rest from stack

4.3 x86-64 Specific Attack Surfaces

Beyond standard buffer overflows, x86-64 presents several architecture-specific attack surfaces that the LLPD framework can model:

  • Partial RIP overwrites: Because x86-64 uses little-endian byte order, overwriting only the lowest 1-3 bytes of the saved return address can redirect execution within the same binary (since the upper bytes of code addresses are typically consistent). The LLPD predicate can detect partial taint coverage of the return address and report the range of achievable redirect targets.

  • Stack-based exception handler corruption (SEH on Windows): Windows x86-64 uses table-based structured exception handling rather than stack-based SEH chains (which was the classic attack vector on 32-bit Windows). However, the LLPD framework should still check for .pdata and .xdata entries to understand exception handling semantics.

  • GOT/PLT overwrites: If a heap overflow can corrupt a Global Offset Table entry, subsequent calls through the PLT will jump to the attacker's address. The LLPD predicate evaluates whether tainted heap writes can reach GOT entries by computing distances in the virtual address space.

4.4 Implementation: x86-64 Predicate Evaluator

The x86-64 predicate evaluator integrates with Ghidra by querying the program's language ID and activating x86-64-specific logic:

FUNCTION evaluate_x86_64(function, events):
  frame = function.getStackFrame()
  ret_offset = frame.getReturnAddressOffset()   // typically +8 from frame base
  canary_present = detectStackCanary(function)
  cet_enabled = detectCET(function)

  FOR EACH stack_variable V in frame:
    IF V.length >= 4:  // potential buffer
      dist = ret_offset - V.stackOffset
      IF dist > 0:
        result = new RIPControlResult()
        result.overwriteBytes = dist + 8
        result.canaryBypass = canary_present
        result.cetProtected = cet_enabled
        result.rbpControlAt = dist  // RBP control is dist bytes into overflow

        IF canary_present:
          result.note = "Stack canary detected. Exploitation requires canary leak."
        IF cet_enabled:
          result.note += " CET shadow stack active. RIP overwrite will fault."

        EMIT result

5. ARM Deep Dive

5.1 ARMv7 (32-bit) Stack and Link Register

ARMv7 uses a link register (LR / R14) to hold the return address. When a BL (Branch with Link) instruction executes, it saves the return address in LR rather than pushing it onto the stack. This creates a fundamental difference from x86:

Leaf functions (functions that don't call other functions) never save LR to the stack. The return is simply BX LR or MOV PC, LR. A buffer overflow in a leaf function's local variables cannot overwrite the return address via the stack, because it was never there.

Non-leaf functions must save LR because calling a sub-function would overwrite it. The standard prologue:

PUSH {R4-R11, LR}    ; save callee-saved registers and LR
SUB  SP, SP, #N       ; allocate N bytes for locals

Stack layout:

Higher addresses
+------------------+
| caller's frame   |
+------------------+
| saved LR         | <- SP + N + 32  (return address)
| saved R11 (FP)   | <- SP + N + 28
| saved R10        | <- SP + N + 24
| ...              |
| saved R4         | <- SP + N
+------------------+
| local var N      | <- SP + N - 4
| ...              |
| local buffer[0]  | <- SP
+------------------+
Lower addresses

The overwrite distance depends on how many callee-saved registers were pushed. The LLPD predicate must parse the function prologue to count the PUSHed registers and compute the correct offset.

Thumb mode: ARMv7 supports interworking between 32-bit ARM instructions and 16-bit Thumb instructions. The LSB of a code address determines the mode: 0 = ARM, 1 = Thumb. If a buffer overflow corrupts a code pointer, setting or clearing the LSB switches the processor mode, causing instruction misalignment. The LLPD predicate should flag Thumb mode transitions as a potential exploitation complication.

5.2 AArch64 Stack and Register Model

AArch64 (ARMv8 64-bit) refines the ARM model significantly:

STP X29, X30, [SP, #-16]!   ; save FP and LR, pre-decrement SP
MOV X29, SP                   ; establish frame pointer
SUB SP, SP, #N                ; allocate locals

Stack layout:

Higher addresses
+------------------+
| caller's frame   |
+------------------+
| saved X30 (LR)   | <- X29 + 8   (return address)
| saved X29 (FP)   | <- X29       (frame pointer)
+------------------+
| local variables   |
| ...               |
| local buffer[0]  | <- SP
+------------------+
Lower addresses

AArch64 has a 16-byte stack alignment requirement. All STP/LDP operations must be 16-byte aligned, which means the compiler may insert padding between variables. The LLPD predicate must account for this alignment when computing overwrite distances.

Key difference from x86-64: The saved return address (X30/LR) and frame pointer (X29/FP) are stored together in a single 16-byte slot via STP. This means controlling FP and LR requires overwriting exactly the right 16-byte boundary, not two separate 8-byte writes.

5.3 LLPD Predicates for ARM

PC Control Predicate (ARM specialization):

PREDICATE PCControl_ARM:
  IF function.isLeaf():
    REPORT "Leaf function: LR not saved to stack. Stack overflow cannot control return."
    EVALUATE indirect_branch_sinks_only()
  ELSE:
    prologue_regs = parsePrologue(function)  // count PUSH'd registers
    lr_offset = compute_lr_stack_offset(prologue_regs)
    FOR EACH buffer B:
      dist = lr_offset - B.stackOffset
      IF dist > 0:
        IF isAArch64:
          // Must overwrite aligned 16-byte pair (FP, LR)
          REPORT "LR control: %d bytes + 16-byte aligned STP pair" % dist
        ELSE:
          REPORT "LR control: %d bytes overflow needed" % (dist + 4)

Thumb Mode Transition Predicate:

PREDICATE ThumbTransition_ARM:
  FOR EACH tainted code pointer P:
    IF P.taintState covers LSB of target address:
      REPORT "Thumb/ARM mode control: LSB of code pointer is tainted"
      NOTE: "Setting LSB=1 forces Thumb mode; LSB=0 forces ARM mode"

5.4 PAC, BTI, and MTE: Hardware Mitigations as Predicate Modifiers

ARMv8.3+ introduces hardware mitigations that modify the exploitability of detected predicate violations:

Pointer Authentication Codes (PAC):

PAC signs code pointers using a per-process key and a context value (typically SP). Before using a signed pointer, the CPU verifies the signature. If the signature is invalid, the pointer is corrupted with an error value that causes a fault.

For LLPD, PAC modifies the RIP Control Predicate: even if tainted data reaches the saved LR location, the AUTIA / RETAA instruction will detect the invalid signature. The predicate should report:

PREDICATE PACModifier:
  IF function uses PACIA/PACIB on LR:
    FOR EACH RIPControl hit:
      DOWNGRADE severity to "requires PAC bypass"
      NOTE: "PAC key: %s, context: SP=%s" % (key_register, sp_value)
      NOTE: "Exploitation requires: PAC oracle, key leak, or signing gadget"

Branch Target Identification (BTI):

BTI marks valid indirect branch targets with BTI instructions. An indirect branch to an address without a BTI marker faults. This constrains the set of gadgets available after gaining control of a code pointer. The LLPD Register Control Predicate should filter potential branch targets to only BTI-marked addresses.

Memory Tagging Extension (MTE):

MTE assigns 4-bit tags to every 16-byte memory granule and to every pointer. If a pointer's tag doesn't match its target memory's tag, the access faults. For buffer overflows, this means the overflow crosses a tag boundary and the tag mismatch is detected. The LLPD predicate should note MTE coverage:

PREDICATE MTEModifier:
  IF target binary is MTE-enabled:
    FOR EACH BufferOverflow hit:
      compute tag_boundaries_crossed = overflow_length / 16
      REPORT "MTE: overflow crosses %d tag boundaries" % tag_boundaries_crossed
      NOTE: "Exploitation requires tag bruteforce (4-bit = 1/16 probability per boundary)"

5.5 Implementation: ARM Predicate Evaluator

FUNCTION evaluate_ARM(function, events):
  is_aarch64 = (pointerSize == 8)
  is_leaf = !function.hasCalledFunctions()
  pac_enabled = detectPAC(function)
  bti_enabled = detectBTI(function)
  mte_enabled = detectMTE(currentProgram)

  IF is_leaf:
    // Only evaluate register control, not stack-based return overwrites
    EVALUATE RegisterControl_only(function, events)
    RETURN

  IF is_aarch64:
    // Parse STP-based prologue
    (fp_offset, lr_offset) = parseAArch64Prologue(function)
    alignment = 16  // AArch64 requires 16-byte aligned stack ops
  ELSE:
    // Parse PUSH-based prologue
    pushed_regs = parseARMv7Prologue(function)
    lr_offset = len(pushed_regs) * 4  // 4 bytes per register
    alignment = 4   // ARMv7 uses 4-byte alignment

  FOR EACH buffer B:
    dist = lr_offset - B.stackOffset
    result = new PCControlResult()
    result.overwriteBytes = dist + pointerSize
    result.alignment = alignment
    result.leafFunction = false
    result.pacProtected = pac_enabled
    result.btiConstrained = bti_enabled
    result.mteProtected = mte_enabled
    EMIT result

6. PowerPC Deep Dive

6.1 Stack Frame Conventions and LR Save Area

PowerPC has one of the most structured stack frame layouts of any major architecture. The stack frame is defined by the ABI (ELF v1 for 32-bit, ELF v1 or v2 for 64-bit), and every frame has a fixed layout:

Higher addresses (toward caller)
+---------------------------+
| Caller's frame            |
+---------------------------+
| LR save area              | <- SP + 4 (32-bit) or SP + 16 (64-bit)
| Back-chain pointer        | <- SP (points to caller's SP)
+---------------------------+
| Saved GPRs                |
| Saved FPRs                |
| Local variables           |
| Parameter area            |
+---------------------------+
| LR save area (for callee) | <- new SP + 4/16
| Back-chain pointer        | <- new SP
+---------------------------+
Lower addresses (toward callee)

The critical difference from other architectures: the caller saves LR, not the callee. The sequence is:

mflr  r0           ; copy LR to r0
stw   r0, 4(r1)    ; store r0 to LR save area (32-bit: offset 4 from SP)
stwu  r1, -N(r1)   ; create new stack frame (decrement SP by N, store back-chain)

This means the saved return address is in the caller's stack frame, above the current frame's back-chain pointer. A buffer overflow in the current function overwrites:

  1. The current function's local variables
  2. The current function's saved registers
  3. The back-chain pointer (at the top of the current frame)
  4. The caller's LR save area (in the caller's frame)

The overwrite distance is therefore: frame_size + pointer_size (frame_size to reach the back-chain pointer, then 4 or 8 more bytes to reach the LR save area in the caller's frame).

6.2 TOC Pointer and Function Descriptors

PowerPC 64-bit (ELF v1 ABI) uses function descriptors: a function's address is not the address of its first instruction, but the address of a 3-word descriptor containing:

Function Descriptor {
    .entry:  address of the function's entry point
    .toc:    TOC (Table of Contents) pointer value
    .env:    environment pointer (typically unused)
}

When calling through a function pointer, the runtime loads all three values. If an attacker overwrites a function pointer, they control not just the entry point but also the TOC pointer (r2), which points to the function's global data. This is a significantly more powerful primitive than simple RIP control on x86-64.

The LLPD predicate for PowerPC function pointer corruption should report:

PREDICATE FunctionDescriptor_PPC:
  FOR EACH tainted function pointer overwrite:
    REPORT "Function descriptor control: entry + TOC + env (24 bytes)"
    NOTE: "Attacker controls r2 (TOC), enabling GOT-relative data corruption"
    NOTE: "This is equivalent to RIP control + arbitrary read/write on x86-64"

ELF v2 ABI (used by modern PowerPC64LE) eliminates function descriptors and uses a global entry point / local entry point scheme instead. The LLPD predicate should detect which ABI is in use by checking the ELF header's e_flags.

6.3 LLPD Predicates for PowerPC

LR Control Predicate (PowerPC specialization):

PREDICATE LRControl_PPC:
  // LR save area is in the CALLER's frame
  current_frame_size = function.getStackFrame().getFrameSize()
  lr_save_offset = current_frame_size + (pointerSize == 8 ? 16 : 4)

  FOR EACH buffer B:
    dist = lr_save_offset - B.stackOffset
    IF dist > 0:
      REPORT "LR control: %d bytes to reach caller's LR save area" % dist
      NOTE: "Back-chain pointer at offset %d (intermediate overwrite)" % current_frame_size

Back-Chain Predicate (PowerPC specific):

The back-chain pointer at the top of each frame creates a linked list of frames. Corrupting it can redirect the stack unwinder and, in some exploitation techniques, chain to arbitrary memory:

PREDICATE BackChain_PPC:
  backchain_offset = 0  // always at offset 0 in the frame
  FOR EACH buffer B:
    dist = current_frame_size - B.stackOffset
    IF dist > 0 AND taint covers backchain:
      REPORT "Back-chain corruption: stack linked list broken at %d bytes" % dist
      NOTE: "May enable stack pivoting on next function return"

TOC Corruption Predicate (PowerPC 64-bit specific):

PREDICATE TOCCorruption_PPC64:
  // Check if r2 (TOC pointer) is loaded from a tainted memory location
  FOR EACH LOAD into r2:
    IF load source is tainted:
      REPORT "TOC pointer corruption: r2 loaded from tainted memory"
      NOTE: "Controls global data access for subsequent function"

6.4 Implementation: PowerPC Predicate Evaluator

FUNCTION evaluate_PPC(function, events):
  is_64bit = (pointerSize == 8)
  abi_version = detectELFABIVersion(currentProgram)  // v1 or v2

  // Parse prologue: mflr r0; st[w|d] r0, offset(r1); st[w|d]u r1, -N(r1)
  (lr_saved, lr_save_offset, frame_size) = parsePPCPrologue(function)

  IF NOT lr_saved:
    // Leaf function: LR not saved
    EVALUATE RegisterControl_only(function, events)
    RETURN

  // LR save area is in the caller's frame
  dist_to_lr = frame_size + (is_64bit ? 16 : 4)

  // Back-chain is at offset 0 in the current frame
  dist_to_backchain = frame_size

  FOR EACH buffer B:
    IF B.stackOffset < frame_size:
      result_backchain = new BackChainResult()
      result_backchain.distance = frame_size - B.stackOffset
      EMIT result_backchain

      result_lr = new LRControlResult()
      result_lr.distance = dist_to_lr - B.stackOffset
      result_lr.abiVersion = abi_version
      IF abi_version == "v1" AND is_64bit:
        result_lr.functionDescriptorControl = true
        result_lr.note = "ELF v1: function descriptor gives entry+TOC+env control"
      EMIT result_lr

7. MIPS Deep Dive

7.1 MIPS Calling Convention and $ra Handling

MIPS uses $ra (register 31) as the return address register. The JAL (Jump And Link) instruction saves the return address in $ra and jumps to the target. Return is via JR $ra.

Non-leaf function prologue:

addiu $sp, $sp, -N      ; allocate frame
sw    $ra, N-4($sp)     ; save return address
sw    $fp, N-8($sp)     ; save frame pointer (if used)
move  $fp, $sp           ; establish frame pointer

Stack layout:

Higher addresses
+------------------+
| caller's frame   |
+------------------+
| saved $ra        | <- $sp + N - 4   (return address)
| saved $fp        | <- $sp + N - 8   (frame pointer, if used)
| saved $s0-$s7    |                   (callee-saved registers)
| local variables  |
| local buffer[0]  | <- $sp
+------------------+
Lower addresses

The save location of $ra is function-specific: the compiler chooses the offset based on the frame size. Unlike x86-64 where the return address is always at RBP+8, on MIPS it could be at any offset. The LLPD predicate must parse the function prologue to find the SW $ra, offset($sp) instruction and extract the offset.

7.2 Branch Delay Slots and Lattice Implications

MIPS executes the instruction after a branch before the branch takes effect. This is the branch delay slot. For example:

jr   $ra            ; return (branch takes effect AFTER the next instruction)
addiu $v0, $zero, 1 ; THIS EXECUTES BEFORE THE RETURN

For the LLPD lattice, this creates a subtle ordering requirement. The delay slot instruction is part of the same atomic operation as the branch. In the P-Code representation, Ghidra handles this correctly: the delay slot instruction's P-Code operations appear before the branch's P-Code operation. However, the LLPD event model must ensure that the delay slot is not separated from its branch in the lattice -- they must be in the same consistent cut position.

If the delay slot contains a memory write:

jr   $ra
sw   $t0, 0($t1)    ; writes to memory in the delay slot

The LLPD predicate sees a STORE event that happens atomically with the RETURN. If $t1 is tainted (points to a controlled address) and $t0 is controlled, this is an arbitrary write primitive that executes on every function return. The predicate should flag this pattern:

PREDICATE DelaySlotWrite_MIPS:
  FOR EACH JR/JALR instruction with a STORE in its delay slot:
    IF delay_slot_store.address_operand is tainted:
      REPORT "Arbitrary write in branch delay slot"
      NOTE: "Write at %s executes atomically with branch to %s"
            % (store_addr, branch_target)

7.3 PIC, $t9, and GOT-Based Attacks

MIPS position-independent code (PIC) uses a unique convention: the callee's address must be in $t9 at function entry. The prologue uses $t9 to compute $gp, which points to the Global Offset Table (GOT):

lui   $gp, %hi(_gp_disp)
addiu $gp, $gp, %lo(_gp_disp)
addu  $gp, $gp, $t9      ; $gp = GOT base, computed from $t9

If an attacker controls $t9 before a JALR $t9 call, they control:

  1. The jump target (code execution)
  2. The subsequent $gp computation (GOT-relative data access)

This is analogous to PowerPC's function descriptor attack but achieved through a different mechanism. The LLPD predicate should track taint flow into $t9:

PREDICATE T9Control_MIPS:
  FOR EACH tainted value flowing into $t9:
    IF followed by JALR $t9:
      REPORT "$t9 control: code execution + GOT base corruption"
      NOTE: "Subsequent $gp computation derives from tainted $t9"
      NOTE: "All GOT-relative loads/stores in callee use corrupted base"

7.4 LLPD Predicates for MIPS

$ra Control Predicate (MIPS specialization):

PREDICATE RAControl_MIPS:
  // Parse prologue to find SW $ra, offset($sp)
  ra_offset = parseMIPSPrologue_findRA(function)
  IF ra_offset == NOT_FOUND:
    // Leaf function
    EVALUATE RegisterControl_only(function, events)
    RETURN

  FOR EACH buffer B:
    dist = ra_offset - B.stackOffset
    IF dist > 0:
      REPORT "$ra control: %d bytes overflow needed" % (dist + 4)

  // Check for NX bypass potential
  IF NOT hasNXBit(currentProgram):
    NOTE: "No hardware NX. Stack shellcode execution is viable."
    NOTE: "Severity: CRITICAL (no DEP equivalent on this MIPS implementation)"

$gp Corruption Predicate (MIPS PIC):

PREDICATE GPCorruption_MIPS:
  IF function saves $gp to stack:
    gp_offset = find_saved_gp_offset(function)
    FOR EACH buffer B:
      dist = gp_offset - B.stackOffset
      IF dist > 0 AND taint covers saved $gp:
        REPORT "$gp corruption: GOT base controlled after %d bytes overflow" % dist
        NOTE: "Affects all global variable access in this function after restore"

7.5 Implementation: MIPS Predicate Evaluator

FUNCTION evaluate_MIPS(function, events):
  // Detect MIPS sub-architecture
  has_delay_slots = true  // all MIPS variants
  is_pic = detectPIC(function)
  has_nx = detectNXBit(currentProgram)
  is_mips64 = (pointerSize == 8)

  // Parse prologue for register save locations
  (ra_offset, fp_offset, gp_offset, frame_size) = parseMIPSPrologue(function)

  IF ra_offset == NOT_FOUND:
    // Leaf function: $ra lives in register only
    EVALUATE RegisterControl_only(function, events)
    RETURN

  // Scan for delay slot writes
  FOR EACH branch instruction BR in function:
    delay_instr = getInstructionAfter(BR)
    IF delay_instr is STORE:
      evaluate_delay_slot_write(BR, delay_instr, taint_state)

  // Standard buffer distance calculations
  FOR EACH buffer B:
    // $ra control
    IF ra_offset > B.stackOffset:
      dist = ra_offset - B.stackOffset
      result = new RAControlResult()
      result.distance = dist + (is_mips64 ? 8 : 4)
      result.nxPresent = has_nx
      IF NOT has_nx:
        result.severity = "CRITICAL"
        result.note = "No NX: return-to-stack shellcode viable"
      EMIT result

    // $gp control (if PIC)
    IF is_pic AND gp_offset != NOT_FOUND AND gp_offset > B.stackOffset:
      dist_gp = gp_offset - B.stackOffset
      result_gp = new GPControlResult()
      result_gp.distance = dist_gp
      result_gp.note = "GOT base corruption enables global data manipulation"
      EMIT result_gp

  // $t9 control check
  IF is_pic:
    evaluate_t9_control(function, events, taint_state)

8. RISC-V: Emerging Architecture Considerations

RISC-V is increasingly relevant for embedded systems, IoT devices, and even server workloads. Its LLPD characteristics are similar to MIPS in many ways:

  • Return address register: ra (x1). Saved to stack by callee in non-leaf functions via sd ra, offset(sp).
  • No branch delay slots: Unlike MIPS, RISC-V does not have delay slots. This simplifies the lattice model.
  • No condition codes: Branches are compare-and-branch in a single instruction. This means there are no flag registers to corrupt for control-flow hijacking.
  • Compressed instructions (C extension): 16-bit compressed instructions interleave with 32-bit instructions. Like ARM Thumb, this affects gadget alignment.

RISC-V's key LLPD considerations:

PREDICATE RAControl_RISCV:
  ra_offset = parseRISCVPrologue_findRA(function)
  FOR EACH buffer B:
    dist = ra_offset - B.stackOffset
    IF dist > 0:
      REPORT "ra control: %d bytes overflow" % (dist + pointerSize)

  // Check for PMP (Physical Memory Protection)
  // RISC-V uses PMP for memory permissions, not page tables in some configs
  IF hasPMP(currentProgram):
    NOTE: "PMP may enforce W^X at granularity of PMP regions"

9. Cross-Architecture Predicate Comparison Matrix

Feature x86-64 ARM32 AArch64 PowerPC MIPS RISC-V
Return addr mechanism Stack (CALL pushes) LR register LR (X30) register LR register $ra register ra (x1) register
Ret addr on stack Always Non-leaf only Non-leaf only Always (caller saves) Non-leaf only Non-leaf only
Saved by Hardware (CALL) Callee (PUSH) Callee (STP) Caller (STW) Callee (SW) Callee (SD)
Ret addr stack offset Fixed: RBP+8 Variable (PUSH count) Fixed: FP+8 Fixed: caller SP+4/16 Variable (prologue) Variable (prologue)
Pointer size 8 bytes 4 bytes 8 bytes 4 or 8 bytes 4 or 8 bytes 4 or 8 bytes
Endianness Little Bi (usually LE) Bi (usually LE) Big (BE) or LE Big (BE) or LE Little
Branch delay slots No No No No Yes No
HW mitigations CET, shadow stack PAC, BTI, MTE PAC, BTI, MTE None standard None standard PMP
NX/DEP Yes (NX bit) Yes (XN bit) Yes (XN bit) Yes (NX) Often missing PMP-dependent
Stack canary fs:[0x28] __stack_chk_guard __stack_chk_guard __stack_chk_guard __stack_chk_guard __stack_chk_guard
PIC complications GOT/PLT GOT/PLT GOT/PLT TOC/func descriptors $t9/$gp/GOT GOT/PLT
Leaf func exploitable Yes (ret addr on stack) No (LR in register) No (LR in register) Yes (caller saves LR) No ($ra in register) No (ra in register)
LLPD predicate count 4 (RIP, RBP, GOT, fmt) 4 (PC, Thumb, PAC, reg) 4 (PC, PAC, BTI, reg) 4 (LR, chain, TOC, desc) 5 (ra, gp, t9, delay, NX) 3 (ra, PMP, reg)

10. Emulation-Based Detection Implementation

10.1 Ghidra EmulatorHelper Integration

Ghidra's EmulatorHelper provides a concrete execution engine operating on P-Code. For LLPD integration, the emulator is configured to:

  1. Initialize memory layout: Map the binary's segments, allocate a stack at a known address, and set up an initial heap region. The stack address is chosen to make overwrite detection easy: a sentinel pattern (e.g., 0xDEADBEEF repeated) is written to the return address location before emulation begins.

  2. Set symbolic inputs: Function parameters and buffer contents are marked with taint tags. Each input byte gets a unique taint identifier: taint[0] for the first byte, taint[1] for the second, etc. As the emulator executes P-Code operations, taint propagates through COPY, INT_ADD, LOAD, etc.

  3. Execute and trace: The emulator runs the function's P-Code, recording an LLPD event for each STORE and LOAD operation. At branch points, the emulator forks: one instance takes the branch, the other falls through. Each fork gets its own vector clock.

  4. Check sentinel: After emulation (or at each RETURN instruction), the emulator reads the return address location. If the sentinel value has been replaced with tainted data, the RIP Control Predicate is satisfied.

FUNCTION emulate_with_LLPD(function):
  emu = new EmulatorHelper(currentProgram)

  // Setup stack
  STACK_BASE = 0x7FFF0000
  STACK_SIZE = 0x10000
  emu.writeMemory(STACK_BASE, allocate(STACK_SIZE))
  emu.writeRegister(getStackPointerName(), STACK_BASE + STACK_SIZE - 256)

  // Write sentinel to return address location
  ret_addr_location = emu.readRegister(getStackPointerName()) + getRetAddrOffset()
  emu.writeMemory(ret_addr_location, SENTINEL_PATTERN)

  // Mark function parameters as tainted
  FOR EACH parameter P at index I:
    taint_tag = createTaintTag("param_" + I)
    emu.writeRegister(paramRegister(I), taint_tag)

  // Execute with event recording
  events = []
  emu.setBreakpoint(function.getEntryPoint())
  emu.run(function.getEntryPoint(), MAX_STEPS)

  WHILE emu.isRunning():
    pcode_op = emu.currentPCodeOp()
    IF pcode_op.opcode == STORE:
      events.add(new Event(STORE, pcode_op.address, getTaint(pcode_op.input)))
    IF pcode_op.opcode == RETURN:
      // Check if return address was corrupted
      current_ret = emu.readMemory(ret_addr_location, pointerSize)
      IF current_ret != SENTINEL_PATTERN:
        REPORT "Return address overwritten: sentinel replaced"
        EXTRACT taint from current_ret to determine which input bytes control it
    emu.step()

  RETURN events

10.2 Symbolic Taint Engine

The taint engine tracks data dependencies at byte granularity. Each byte in the emulated memory has an associated taint set: the set of input byte indices that influence its current value.

Taint propagation rules for P-Code operations:

P-Code Op Taint Rule
COPY A -> B taint(B) = taint(A)
INT_ADD A, B -> C taint(C) = taint(A) ∪ taint(B)
INT_SUB A, B -> C taint(C) = taint(A) ∪ taint(B)
INT_AND A, B -> C taint(C) = taint(A) ∪ taint(B)
LOAD [A] -> B taint(B) = taint(memory[A]) ∪ (taint(A) if A is tainted)
STORE A -> [B] taint(memory[B]) = taint(A)
SUBPIECE A, N -> B taint(B) = {t ∈ taint(A) : byte_index(t) in [N..N+sizeof(B))}
PIECE A, B -> C taint(C) = taint(A) ∪ taint(B)
INT_ZEXT A -> B taint(B) = taint(A)
CALL target taint(return_val) = ∪ taint(all_args) (conservative)

The taint engine is over-approximate: if any byte of an input influences any byte of a value, the entire value is considered tainted. This produces false positives but guarantees no false negatives. For constraint extraction, the precise byte-level taint mapping determines which input bytes to control.

10.3 Lattice Construction from Emulated Paths

After emulation, the collected events are organized into per-path event logs, identical in structure to the per-thread event logs in the runtime LLPD system. The LatticeBuilder receives these logs and performs the same BFS traversal:

FUNCTION buildLattice(pathEventLogs):
  numPaths = pathEventLogs.size()
  initialCut = new CFGCut(numPaths)  // all paths at position -1

  queue = new BFS_Queue()
  queue.add(initialCut)
  visited = new HashSet()
  violations = []

  WHILE queue is not empty AND visited.size() < MAX_CUTS:
    cut = queue.remove()
    IF visited.contains(cut): CONTINUE
    visited.add(cut)

    // Evaluate exploit predicates at this cut
    FOR EACH predicate P in [RIPControl, RegisterControl, FormatString, ...]:
      IF P.test(cut, pathEventLogs):
        violations.add(new Violation(P, cut))

    // Advance each path and add consistent successors
    FOR EACH pathId in 0..numPaths-1:
      nextCut = cut.advance(pathId)
      IF nextCut.isConsistent(pathEventLogs):
        queue.add(nextCut)

  RETURN violations

The lattice construction for binary analysis has one key advantage over runtime analysis: the number of paths is bounded by the function's cyclomatic complexity, which is typically much smaller than the number of threads in a concurrent program. A function with 10 conditional branches has at most 2^10 = 1024 paths, but in practice far fewer due to infeasible path combinations. This means the lattice is tractable for most functions without hitting the maxCuts limit.

11. Constraint Solving and Exploit Synthesis

When the LLPD lattice traversal identifies a predicate violation, the next step is to produce a concrete input that triggers it. This is where the taint state becomes actionable.

From taint to constraints:

Each satisfied predicate provides:

  1. The target location (e.g., saved return address at stack offset +40)
  2. The desired value (e.g., 0x4141414141414141 for proof-of-concept, or a specific gadget address for exploitation)
  3. The taint mapping: which input bytes flow to which bytes of the target

The constraint extraction produces a set of equations:

FOR RIP control with target value 0x4141414141414141:
  input[offset+0] = 0x41   // LSB of return address (little-endian x86-64)
  input[offset+1] = 0x41
  input[offset+2] = 0x41
  input[offset+3] = 0x41
  input[offset+4] = 0x41
  input[offset+5] = 0x41
  input[offset+6] = 0x41
  input[offset+7] = 0x41   // MSB of return address

WHERE offset = buffer_distance_to_ret_addr

For more complex cases where the input is transformed before reaching the target (e.g., through toupper(), character filtering, or arithmetic operations), the path constraints from emulation provide the necessary transformations. These can be encoded as SMT formulas and solved by Z3:

(declare-const input (Array Int (_ BitVec 8)))
; input[40] through input[47] must produce 0x4141414141414141 at ret addr
; after passing through: toupper(input[i]) for each byte
(assert (= (bvor (bvand (select input 40) #x5f) #x40) #x41))  ; toupper('a') = 'A'
; ... repeat for each byte
(check-sat)
(get-model)

De Bruijn pattern integration:

When the exact offset is unknown or needs verification, the LLPD script generates a De Bruijn (cyclic) pattern of the appropriate length. A De Bruijn sequence of order n over alphabet k contains every possible subsequence of length n exactly once. For exploit development, a cyclic pattern of length equal to the overflow distance allows precise offset identification from the crash value.

FUNCTION generateDeBruijnPayload(overflow_length, pointer_size):
  alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
  pattern = cyclic(overflow_length + pointer_size, alphabet)

  // The value in RIP/PC/$ra after the crash uniquely identifies the offset
  RETURN pattern

12. Practical Considerations and Limitations

Accuracy vs. completeness tradeoffs:

The LLPD binary analysis framework is sound but not complete: it will find every exploitable condition that falls within its predicate definitions, but it may report false positives where the path conditions are infeasible. This is inherent to static analysis -- resolving path feasibility perfectly is equivalent to the halting problem.

In practice, the false positive rate is manageable because:

  1. The lattice consistency check prunes most infeasible path combinations
  2. The taint engine's over-approximation is conservative (fewer false negatives)
  3. The emulation step provides concrete validation for high-confidence findings

Scalability:

  • Functions with fewer than 20 basic blocks: full lattice traversal in under 1 second
  • Functions with 20-100 basic blocks: lattice traversal with maxCuts=10000 in 5-30 seconds
  • Functions with 100+ basic blocks: fast-path predicates only, skip lattice traversal
  • Whole-program analysis: run per-function analysis in parallel across all functions, aggregating results

Obfuscated binaries:

Control-flow flattening, opaque predicates, and VM-based obfuscation significantly degrade the quality of Ghidra's P-Code output. The LLPD framework degrades gracefully: it will analyze whatever CFG Ghidra recovers, but the results may be incomplete. For heavily obfuscated binaries, dynamic analysis (running the binary in an emulator with full instrumentation) is more appropriate.

Stripped binaries:

Without symbol information, the LLPD script cannot identify function names for input source detection (e.g., it can't recognize calls to read or recv). The script falls back to:

  1. Heuristic function identification (calls to library functions by PLT address)
  2. Parameter-based source detection (any pointer parameter is a potential input source)
  3. User annotation (the analyst can pre-label functions in Ghidra's symbol table)

Multi-threaded binaries:

The per-function LLPD analysis treats execution as single-threaded. For binaries with threads, the runtime LLPD system (using the Java agent with EventCollector) is more appropriate. A future extension could combine both: use Ghidra's analysis to identify vulnerable functions, then use runtime LLPD to confirm that the vulnerability is reachable in a multi-threaded context.

Written and Tested by Oblivion Edge Vulnerability Research LLC © July 21, 2026

Blake De Garza
Previous
Next

Post-Quantum Cryptography and The Riddler Chat Application