cat-states

Minimal proofs-of-concept for compiler-invented loads — situations where a single C-level read of memory compiles to two or more architectural reads of the same address.

We call these cat-states – if the pattern is used across a check/use boundary, the compiler may emit a time-of-check time-of-use vulnerability (TOCTOU). Similar to the Schrödinger's cat thought experiment, the C code could either be vulnerable, or not vulnerable – the only way to decide which is to "measure" it with compilation.

Whether that second load actually appears is a decision of the compiler's backend cost model, not of the C language — it turns on the exact compiler, version, target architecture, and optimization flags, none of which the source reveals. The same file reads clean under one toolchain and double-reads under another (Clang loads once where GCC loads twice; -flto revives a double-read a module boundary had suppressed). There is no source-level signal to audit for — the only way to know whether a given build is vulnerable is to compile it and look at the loads it emits.

Each .c file is one minimal cat-state, annotated with the exact assembly it emits and the compiler / arch / flags that trigger it. The files are driven by alpha-lab/matrix_runner.py through the // @key: value front-matter described in SPEC.md.

Anatomy of a cat-state

m0_signext_reload.c is the example that opens the top-level README. The C source reads *p exactly once:

unsigned int g(unsigned short *p)
{
  short t = *p;  /* copy p into a local for safekeeping */
  return (unsigned short)t - t;
}

The C code appears to have no TOCTOU: t is a local variable and cannot be modified by an attacker. The developer's mental model is that short t = *p takes a single, stable snapshot of the memory, and that every later use of t — both the zero-extended (unsigned short)t and the sign-extended t — reads back that one captured value.

But the compiler quietly breaks that model:

GCC targeting the 32-bit ARM family (and MIPS) at -O1/-O2/-O3 instead emits two loads of the same address:

g:
        ldrh    r2, [r0]     ; load *p, once  — zero-extended view
        ldrsh   r0, [r0]     ; load *p, twice — sign-extended view (INVENTED)
        subs    r0, r2, r0
        bx      lr

*p is read twice — once by the ldrh, once by the standalone ldrsh — with a double-read (divergence) window between them. The two views of t are no longer guaranteed to agree: if the memory at *p changes between the two loads (another thread, DMA, attacker-controlled MMIO), the zero-extended half holds the old value and the sign-extended half the low halfword of the new one.

This minimal example only subtracts them, so the inconsistency is harmless — it has no check/use boundary to straddle. But drop the same reload into a validate-then-use shape — snapshot a value, check a field of the snapshot, then act on the snapshot — and the two loads land on opposite sides of the check, introducing a TOCTOU.

cat-states by Compiler

Invented-loads are observed in all major C compilers, with some compilers more likely to emit the vulnerable pattern than others:

cat-states by Architecture

Invented-loads impact most CPU architectures:

The classes group by the ISA property that makes the second load look cheap:

• Memory-operand ALU (CISC) → Class 7. m68k, MSP430, VAX, s390x, 6502. The ISA can compute directly against memory, so the backend folds each use of a value into its own op reg, [mem] instruction instead of caching it in a register.
• Rich narrow loads on a load/store RISC → Class 2. ARM, MIPS. Sized and signed load variants (ldrb/ldrh/ldrsh) plus pipelined loads make a second independent narrow load cheaper than an in-register extend (uxtb/sxth).
• Single-instruction global addressing → Class 1. x86-64, i386, m68k, VAX, MSP430. A global re-reads in one instruction (RIP-relative on x86, absolute or memory-to-memory on the CISC arches), so the allocator rematerializes it across a register-clobbering event rather than spilling.
• Split FP/GPR register files + memory-operand FP ALU → Class 4. x86-64, s390x. A union consumed in both register classes loads twice — once folded into addss / aeb [mem], once as the GPR load it needs anyway.
• Bulk struct-copy lowering → Class 3 (mostly arch-agnostic). The one class not tied to an ISA family: the struct-copy form fires on most GCC targets wherever a struct copy lowers to a wide / vector / rep movs / mem-to-mem load that overlaps a scalar field load — but GCC splices it to a single read on 32-bit RISC (RV32, MIPS32, SPARC, ARM) and Xtensa. A sub-word RMW is a second Class-3 driver that word-loads a neighbor even on those word-atomic RISCs (SPARC / RV32 / MIPS64).

Takeaway: ISA capability gates a class but does not determine it. x86-64 has memory-operand ALU (add [mem], reg) yet GCC never emits the Class-7 fold there, while it does on m68k / MSP430 / s390x — so "most CISC" is not "most vulnerable"; the backend cost model decides. Exposure is widest where a permissive ISA and a reload-preferring GCC cost model coincide: x86-64 exhibits three distinct classes (1, 3, 4) and s390x five (2, 3, 4, 7, 8), and s390x is the only target that is at once an FP cross-class, a CISC mem-op-fold, and a byte-order-reload target.

The memcpy cat-state

A good compiler is smart enough to reason through functions, including memcpy. This means the invented-load and Schrödinger TOCTOU can be emitted across function boundaries, including the common defensive-copy idiom most security-concious programmers reach for to prevent a TOCTOU:

memcpy(&copy, untrusted, sizeof(copy));    // take a private snapshot
if (copy.len <= MAX)                       // validate the snapshot...
    use(&copy);                            // ...and use that same snapshot

This is the Class 3 cat-state. The compiler can copy the untrusted data into copy as requested, but then reload the copy.len field directly from the original untrusted memory — so "checked" and "used" come from two different loads of attacker-controllable data, and a race between them defeats the check.

The volatile cat-state

volatile is the textbook fix for a double-read TOCTOU, so it's tempting to think that to prevent the TOCTOU we can just mark our data as volatile. But volatile is a property of the lvalue access, not of the object, and it is silently cast away anywhere the pointer is converted to a non-volatile type. The conversion to const void * at a memcpy call is exactly such a place, so the qualifier is discarded with no diagnostic:

volatile struct msg *m = mmio;            // source marked volatile
struct msg snap;
memcpy(&snap, m, sizeof(snap));           // volatile silently dropped at the const void * param
if (snap.cmd <= MAX) dispatch(snap.cmd);  // validate the snapshot, then use it

There is no volatile-preserving memcpy overload, so passing volatile struct msg * to its const void * parameter strips the qualifier — with no source-level cast and no diagnostic at any warning level, not even Clang's -Weverything. The compiler can then read m->cmd twice, as in (volatile_memcpy_overlap.c). The mitigation is intact in the source and gone in the asm.

An LTO cat-state

A cross-translation-unit call boundary is a real defense against Class 3. Factor the validate-and-use step into another module — the encouraged, modular way to write it —

S u = *p;          // one C read: the private snapshot
if (ok(&u))        // validate     (defined in another TU)
    use(&u);       // ... and use  (defined in another TU)

and at -O2 the compiler cannot see those helper bodies, so it must emit real calls. It materializes the snapshot once on the stack and hands both helpers its address; the check and the copy read that private copy, never *p again. The module boundary pins the snapshot to memory — exactly the protection the source intends.

Turn on -flto and the barrier evaporates. The linker inlines ok and use into the caller, SRA scalarizes the now-unneeded stack snapshot, and the validated field is read twice — once for the check, once by the bulk copy — the Class 3 TOCTOU, back from the dead. No new mechanism is invented: LTO is a new trigger that dissolves a boundary which otherwise suppressed the double-read. The defensive copy that was a single read across the module boundary becomes a double-fetch the instant LTO is enabled — increasingly the distribution default, applied to code that never changed and that reviewed as safe. (For the boundary to hold without LTO, both the check and the copy must live across it; if the check is inlined in the caller, the caller re-reads the field on its own and the double-read needs no LTO at all — that is callee_split_extern.c.)

See lto_cross_tu_overlap.c (the snapshot TU) and lto_cross_tu_overlap_defs.c (the helper TU) for both asm forms — single read without LTO, double read with it.

cat-state Catalog

Rematerialization (Class 1)

int x, y, z;

int f(void) {
    int t = x;                              // one read of x
    asm volatile("" ::: CLOBBER_ALL_GPR);   // clobbers every GPR, no "memory"
    y = t;
    asm volatile("" ::: CLOBBER_ALL_GPR);
    z = t;                                   // t reloaded from x[rip] here
    return 0;
}

A value read once must stay live across an event that clobbers every register but provably cannot touch the source memory. Rather than spill t to the stack and restore it, the register allocator rematerializes it by re-reading the global — so one C read becomes N+1 architectural reads. The reload is a single instruction on x86-64 (RIP-relative), i386, m68k, VAX, and MSP430 (absolute / memory-to-memory), and the "no memory effects" guarantee comes from an inline-asm clobber list, __attribute__((const)), __declspec(noalias), or a const-qualified global (which every major compiler treats as invariant).

Two conditions gate it: register pressure (for a mutable global, practically an all-GPR clobber — ordinary code keeps it in a callee-saved register; but a const global rematerializes under natural pressure across ordinary calls, with no inline asm) and a register-free-addressable source — a global or a stack slot. A pointer deref, TLS, or absolute address is read once (GCC reuses a stored copy rather than re-read it), so remat-TOCTOU is a global-variable concern, not an MMIO-via-pointer one.

• Inline-asm clobber — GCC, all-GPR clobber (x86-64, i386, m68k, VAX, MSP430)
• Const global — GCC / Clang / ICX / ICC / MSVC, a const-qualified global re-read under natural pressure (no inline asm; all five families)
• Const-attribute pressure — GCC / ICC, __attribute__((const))
• Volatile lvalue launder — GCC, volatile defeated by a non-volatile cast
• Noalias remat — MSVC, __declspec(noalias)
• Setjmp-triggered remat — GCC, a value live across setjmp can't stay in a callee-saved register (longjmp restores the file), so the const global is re-read at the common return instead of spilled (x86-64)
• Bounds-check TOCTOU — GCC / ICC, a const-global index rematerialized so the guard (unsigned)t < 64 and the use read it separately — a genuine check-vs-use divergence (x86-64, i386, m68k, VAX, MSP430)

Width-Mismatch Reload (Class 2)

unsigned short x;

unsigned short g(unsigned short *p) {
    unsigned short t = *p;           // one read of *p
    return t - (t >> 15);            // both views derive from the loaded word
}

The source reads a narrow value once and derives a second, differently-typed view of it (a byte mask, a sign extension). On ARM (whole 32-bit family) and MIPS, GCC's cost model prefers issuing the second view as an independent narrow load of the same address — ldrh+ldrsh, ldr+ldrb — over an in-register extend (uxtb/sxth), because two independent loads can pipeline. The two loads overlap, so the source byte(s) are read twice. A GCC cost-model artifact: Clang and MSVC derive the second view in-register and load once.

• Word + byte reload — Cortex-M0, ldr+ldrb
• Sign-extension reload — ARM family + MIPS, ldrh+ldrsh
• RV64 bitfield reload — RV64 lw+ld, bulk-copy-into-local + bitfield extract (CSE fails on the mismatched RTL widths)
• Int→long dual-extension reload — MIPS64 / s390x, lw+lwu (sign- and zero-extended 32→64 views of one int; the short in the sign-ext file was incidental — any sub-register-width type on an ISA where in-register widening isn't cheaper than a second load)

Bulk-vs-Scalar Overlap (Class 3)

typedef struct { int target; int rest[34]; } S;
S dst;

int g(S *p) {
    S u = *p;              // one bulk read of *p (the defensive snapshot)
    if (u.target > 0) {    // should read the local copy u...
        dst = u;
        return 1;
    }
    return 0;
}

A struct is snapshotted into a local with one bulk copy, then a scalar field of the local is validated. The compiler bypasses the local: it emits a scalar field-direct load of *p for the compare and a bulk load (XMM / rep movsq / vector) of *p for the copy, so the field's bytes ride both loads. The validated value (scalar read) and the stored value (bulk read) come from two distinct reads of the same address — the canonical divergence double-fetch. Triggers turn on the copy lowering (struct-size thresholds, vector type, RV64 ld width) and on whether the split straddles a call boundary.

• Buffer-tail overlap — scalar field + char[] tail, any field type; broad across GCC backends (the common real-world shape)
• Field-compare overlap — DWORD cmp + XMM bulk (140 B, word tail)
• Tail-field overlap — same, scalar field moved to the struct end; collapses the field-compare size threshold from 140 B to 24 B (GCC)
• Rep-movs overlap — rep movsq regime (264 B)
• Byte struct-assign — S u = *p + byte field (17 B)
• Byte memcpy — explicit memcpy + byte field
• Volatile memcpy — same, volatile source (qualifier dropped)
• Callee split (noinline) — inter-procedural, __attribute__((noinline))
• Callee split (fn-pointer) — inter-procedural, indirect call

Cross-Class Reload (Class 4)

typedef union { float as_float; long long as_int; } v_t;
v_t x;

long long g(v_t *p) {
    v_t u = *p;                       // one read of *p
    if (u.as_float + 1.0f > 0.0f)     // needs the bytes in an XMM register...
        return u.as_int;              // ...and in a GPR
    return 0;
}

A union read once is consumed in two register classes — an FP/vector register for the float-domain op, a GPR for the integer view. Instead of one load plus a cross-class transfer (movd / vmovw), GCC loads the bytes twice: once folded into an ALU-with-memory op (addss / vaddsh [mem]), once as the GPR load it needs anyway. Gated on a width mismatch between the two views and on the ALU-memory fold (the +1.0f is load-bearing). GCC only — x86_64, and s390x.

• Cross-class reload (float) — float / long long, addss+mov (x86_64; also s390x aeb+lg)
• Cross-class reload (half) — _Float16 / int, vaddsh+cmova

CISC ALU Mem-Op Fold (Class 7)

unsigned int x;

unsigned int g(unsigned int *p) {
    unsigned int t = *p;       // one read of *p
    return t + (t & 0xff);     // two uses of the loaded value
}

On CISC targets with memory-operand ALU instructions (m68k, MSP430), GCC folds each use of t into its own ALU-with-memory instruction — and.l x,%d0 + add.l x,%d0 — rather than caching the loaded value in a register. Two uses of one loaded value become two independent memory accesses. A pure backend (RTL) choice; on m68k the operand must resolve to a global symbol (after inlining) for the fold to fire. Mostly GCC; the one non-GCC instance is the 6502 via llvm-mos (Clang).

• CISC mem-op fold — m68k / MSP430 / s390x, and/add with [mem]
• VAX mem-op fold — VAX, movzbl+addl2 (byte overlaps word; GCC 12)
• 6502 mem-op fold — 6502 via llvm-mos (Clang), and/adc with [mem] — the one non-GCC Class 7

Byte-Order-Divergent Reload (Class 8)

unsigned int x;

unsigned int g(unsigned int *p) {
    unsigned int t = *p;              // one read of *p
    return t ^ __builtin_bswap32(t);  // native view ^ byte-reversed view
}

The source needs one word in two byte orders — native and byte-swapped — and GCC on s390x materializes each with its own memory read: a byte-reversed load (lrv) for the swapped view and a native load folded into an ALU-with-memory op (x / a) for the other, so the word is read twice on one straight-line path. Both reads are full width; only the byte order differs (no narrow type, unlike Class 2). This is the byte-order axis of the same divergent-representation reload meta-pattern as Class 2 (extension) and Class 4 (register class): the ISA can load each representation directly, and the cost model prefers two loads to one-load-plus-convert. It fires only where the ISA has both a byte-reversed load and ALU-from-memory folding, so lrv+x (2 insns) beats load+register-bswap+xor (3) — s390x has both. x86-64 (movbe) and PPC64 (lwbrx) have the byte-reversed load but their cost models still pick one load + a register reverse; load/store RISCs (AArch64, MIPS64, RISC-V) have only a register reverse and single-load. GCC, s390x only (so far). The native view must ride the ALU-memory operand, so this is a Class-8/Class-7 hybrid, never a pure dual-load: ^ / + / == reload, but a conditional select single-loads.

• s390x byte-order reload — lrv+x (32-bit; also lrvg+xg at 64-bit)

Other shapes of interest

We additionally track two classes match the cat-state shape but are not compiler-choice same-address double-reads. They are kept because they exercise the same detection machinery.

Volatile Bitfield RMW (Class 5)

volatile struct { unsigned a : 3; unsigned b : 5; unsigned c : 24; } x;

void f(void) {
    x.a = 1;   // RMW — hidden read of the storage word
    x.b = 2;   // RMW — second hidden read (the double-load)
}

The source has zero syntactic reads — only two writes. But each volatile bit-field write reads the storage unit, modifies the targeted bits, and writes it back. Here, the two reads are spec-mandated, not a compiler choice: a partial write to a volatile storage unit is defined as a read-modify-write. Any conformant compiler must do this. We capture the pattern here for completeness.

• Volatile bitfield RMW — spec-mandated RMW (all compilers / arches)

Speculative Select-from-Memory (Class 6)

int secret;

int f(int authorized) {
    return authorized ? secret : -1;   // C reads secret only when authorized
}

The C source reads secret only on the authorized path. Lowering the ternary to a branchless conditional select makes the memory the select's source operand — cmov reg, [mem] (ICC / MSVC) or an sbb+or reg, [mem] mask (Clang / ICX) — and both read secret unconditionally. The unauthorized path, where C predicts zero reads, touches the memory anyway: an info-leak / MMIO / cache-timing surface that source-level audit misses. The canonical select above is not a same-address double-read and does not fit the threat model of this research; we capture it for completeness. One variant is the exception — speculative field reload hoists a field that is also read later, re-reading the same address (a genuine divergence double-fetch).

• Speculative cmov load — cmov reg, [mem]
• Speculative OR-mask load — sbb+or reg, [mem]
• Speculative field reload — GCC / MSVC, c ? x.a : x.b hoists both fields (cmov [mem] / ldp); unlike the two above, the hoisted field is also read later across a clobber, so the same address is read twice (x86-64 / arm64)

Source File Annotations

Each .c file's compilation and analysis is configured by a front-matter block of // @key: value comments. The full annotation reference — @arch, @compilers, @flags (dimensions and expression syntax), @entry, @buffer, @buffer-size, @files, and worked examples — lives in SPEC.md.

python3 alpha-lab/matrix_runner.py path/to/file.c

Finding More

[!WARNING] There are almost certainly many more undiscovered cat-states – the current corpus is not exhaustive. The steps below walk through how to discover more.

The catalog in cat-states/ is just the reload patterns we happened to find. The search space — every compiler × arch × flag × C idiom — is enormous, and the lab does the measuring for you. Your challenge: find a cat-state that isn't in the catalog yet.

1. Write a candidate. The recipe is read once, derive twice: snapshot a value into a local, then consume it two ways that tempt the backend to re-fetch instead of reuse. Keep it minimal — one global, one entry function; mutate the smallest example, m0_byte_reload.c. Aim where the catalog is thin: idioms the classes skip (a double/int union, a bitfield with two-width uses), arch cells nobody swept (PowerPC, SPARC, s390x), or clean-at--O2 shapes that go dirty under -ffast-math/-flto/-march. Add the // @key: value front-matter the lab reads (reference: cat-states/SPEC.md):

// @arch:   x86_64, arm, arm64, riscv64, mips
// @compilers: gcc, clang
// @flags:  opt          // sweep -O0..-Og
// @entry:  f            // emulation entry point
// @buffer: x            // the global to watch for re-reads
// @buffer-size: 4

unsigned int x;
unsigned int f(void) {
    unsigned int t = x;   // the one and only source read of x
    return /* ...two derived views of t that might force a reload... */;
}

2. Measure it. python3 alpha-lab/matrix_runner.py cat-states/your_candidate.c sweeps the matrix (rows = compilers, columns = flags) and marks each cell . clean / D double-read / X compile-fail / ! emu-fail. A D is a byte of x loaded more than once — a cat-state. Confirm a hit with compile.py ... --arch arm --compiler g142 and eyeball two loads of the same address. All clean? Mutate and resweep — widen the type mismatch, add a Class-4 ALU-with-memory fold, split the use across a non-inlinable call. Negative results are cheap; the cache absorbs reruns.

3. Pin the cause. When a source is clean at one opt level but dirty at a higher one, flag_search.py ... --reference -O0 --baseline -O2 delta-debugs the -f... delta to a one-line reproducer like gcc -O0 -ftree-pre <source>. (No flag isolates it? The cost model itself is the cause — still a finding.) The per-file flag causes, the flag-dependency structures, and the searchability preconditions live in alpha-lab/README's "Breakdown by cause"; each cat-state also records its own result in a // Flag search (...) header (format in SPEC.md).

4. Claim it. A D on a (source, compiler, arch, flags) tuple the catalog doesn't list is a new cat-state. Annotate the file with its assembly and class — or a new class — and it joins cat-states/. Whether it becomes an exploitable TOCTOU depends only on whether someone places the same shape across a check/use boundary in real code; the lab proves the compiler is willing.