The 30-Year-Old Bug: How Modern Compiler Optimizations Broke a 1994 PRNG

A Deep-Dive Compiler Forensics Case Study

1. The Context: RPM Default Flags and xfstests

The investigation began with compiling xfstests-dev, a standard Linux filesystem testing suite, using Red Hat’s default RPM build optimizations (%optflags).

Modern RPM builds inject a massive payload of performance and security flags, including:

-O2 -flto=auto -ffat-lto-objects -fexceptions -g -grecord-gcc-switches -pipe -Wall -Werror=format-security -Wp,-D_FORTIFY_SOURCE=3 -fstack-protector-strong -m64 -march=x86-64-v3 -mtune=generic ...

When building an Autotools project, these flags must be passed to the ./configure script so they are properly tested and baked into the resulting Makefile, rather than passing them directly to make (which overwrites internal project include flags like -I).

# The correct way to inject RPM flags into Autotools
./configure CFLAGS="$(rpm --eval '%{optflags}')" CXXFLAGS="$(rpm --eval '%{optflags}')" LDFLAGS="$(rpm --eval '%{__global_ldflags}')"
make

2. The Mystery: Diverging Execution

Once compiled, a bizarre issue emerged in the nametest binary. Running the exact same code with the exact same pseudo-random number generator (PRNG) seed (-s 1) produced slightly different outputs depending on the compilation flags:

Unstripped (Standard Flags):

creates: 10 OK, 0 EEXIST (10 total, 0% EEXIST)

Stripped (RPM Flags with LTO & -O2):

creates: 10 OK, 1 EEXIST (11 total, 9% EEXIST)

Because the threshold for these operations relied on op = random() % 100, this divergence proved that the internal state of the PRNG was generating different mathematical sequences despite starting with the identical seed.

3. The Red Herrings

Debugging compiler differences is notoriously difficult. Several theories were tested and ultimately ruled out:

• Implicit Function Declarations (GCC 14): Did the strictness of GCC 14 cause ./configure to fail a feature check, silently falling back to glibc’s rand() instead of POSIX random()?

  • Ruled Out: nm output proved xfstests was statically compiling its own custom random.c implementation.

• char Signedness: Red Hat RPM flags include -funsigned-char. Did casting bytes from a signed array alter the PRNG state?

  • Ruled Out: Recompiling with -fsigned-char did not fix the issue.

• Missing -fwrapv: Was signed integer overflow causing the optimizer to alter the math?

  • Initial Test Failed: Passing -fwrapv to CFLAGS did not fix the issue. (Note: This was a false negative due to missing LDFLAGS, which became critical later.)

4. The Smoking Gun: Assembly Analysis

To bypass the compiler’s “black box,” the raw assembly of both binaries was dumped and compared:

objdump -d --no-show-raw-insn -M intel ./nametest-stripped > stripped.asm
objdump -d --no-show-raw-insn -M intel ./nametest-unstripped > unstripped.asm

The C code in nametest.c contained two back-to-back PRNG calls inside a loop:

ip = &table[ random() % totalnames ];
op = random() % 100;

Because of Link-Time Optimization (-flto), GCC merged random.c and nametest.c, allowing it to inline the PRNG math directly into the loop.

Looking at stripped.asm, the optimizer did something highly destructive:

1940: mov    edi,DWORD PTR [r12]       # edi = original_it
# ...
1777: lea    eax,[rdi*4+0x0]           # new_it = original_it * 4  <--- THE SMOKING GUN
177e: lea    edx,[rax-0x1]             
1781: mov    DWORD PTR [r12],eax       # save new_it to memory

The compiler had hardcoded original_it * 4 to handle both PRNG calls simultaneously, completely skipping a critical safety branch inside the random.c logic.

5. The Root Cause: Weaponized Undefined Behavior

The legacy 1994 PRNG code in random.c contained the following logic:

if (it <= 0)    
    it = (it + it) ^ MASK;
else
    it = it + it;

The original author explicitly relied on signed integer overflow. When it + it exceeded the 32-bit integer limit, it would wrap around and become a negative number. The next time the function was called, the if (it <= 0) branch would catch the negative number and apply the MASK.

How Modern GCC Handled It:

In the C standard, signed integer overflow is Undefined Behavior (UB).

When LTO inlined both random() calls, GCC’s value-range analysis looked at the second call and assumed: “If it was positive in the first call, it + it cannot mathematically be negative because signed overflow is illegal. Therefore, the < 0 branch is impossible code.”

GCC completely deleted the safety branch and simply multiplied the variable by 4. Once the seed reached 1,073,741,824, it * 4 overflowed into 0. The MASK was missed, permanently altering the mathematical sequence of the PRNG for the rest of the test.

6. The Fix

The correct way to preserve 1994 logic in a 2024 compiler pipeline is to remove the Undefined Behavior entirely. In C, unsigned integer overflow is 100% legal and defined to wrap modulo $2^n$.

By casting the variables to unsigned integers for the arithmetic, the compiler is forced to respect the wrap-around, preserving the original signed check without triggering the optimizer’s UB deletion.

The Patched Code (random.c):

it = is[0];
leh = is[1];

/* Use unsigned arithmetic to safely wrap the overflow without triggering UB */
uint32_t u_it = (uint32_t)it;

if (it <= 0)	
    u_it = (u_it + u_it) ^ MASK;
else
    u_it = u_it + u_it;
    
it = (int32_t)u_it;

With this patch, the PRNG safely survives Link-Time Optimization (-flto) and aggressive -O2 heuristics, ensuring the stripped and unstripped binaries generate the exact same random sequence.

7. Standalone Reproduction

The bug was reproduced in isolation to confirm the root cause without involving xfstests. The reproduction lives in:

randtest/
├── random.c       — PRNG implementation (_irandm, _random, random, srandom, get_it)
├── random.h       — declarations
├── randtest.c     — main: two sequential random() calls per iteration with diagnostics
└── bug_demo.c     — self-contained single-file reproduction (see below)

7.1 Two-file reproduction (random.c + randtest.c)

randtest.c calls random() twice per iteration and reads saved_seed[0] via get_it() before and after each call, so the corrupted PRNG state is visible directly:

# correct behaviour
gcc -O0 -o randtest_plain randtest.c random.c

# triggers the bug via LTO cross-file inlining
gcc $(rpm --eval '%{optflags}') $(rpm --eval '%{build_ldflags}') \
    -o randtest_rpm randtest.c random.c

Output diverges at iteration 16 — the first iteration after it crosses 2^30 and the doubled value wraps past INT32_MAX:

# plain (correct)
iter 16:  it=1187941550  r1=138120522  it=-1919084196  r2=1734299348  it=945648879   <-- OVERFLOW

# RPM (buggy)
iter 16:  it=1187941550  r1=138120522  it=-1919084196  r2=2084125751  it=456798904

r1 is still identical (both calls share the same entry state for that iteration), but r2 diverges because the inlined second call skips the MASK branch and writes a corrupted value to saved_seed[0].

7.2 Single-file reproduction (bug_demo.c)

The bug does not require LTO. A single translation unit compiled with plain -O2 is enough — the compiler inlines _irandm freely within the file and applies the same cross-call value-range analysis.

gcc -O2 -fno-lto -o bug_demo_O2 bug_demo.c   # triggers the bug
gcc -O0          -o bug_demo_O0 bug_demo.c   # correct reference

Same divergence, same iteration, no linker flags involved.

7.3 Why the printf inside _irandm masks the bug

During development a diagnostic printf was placed inside _irandm itself. This silently cured the bug: printf is an external call with side effects, which GCC treats as a full memory barrier. The optimizer can no longer track it across the call boundary, so it conservatively keeps both branches. The numbers stayed identical across builds.

The only visible artifact was that the RPM build silently dropped the "<-- OVERFLOW" label from its output — the ternary (it_old > 0 && it < 0) was statically eliminated because GCC knew (from UB reasoning in the else branch) that it < 0 is impossible after it = it + it with a positive it. Correct numbers, missing label: a subtler manifestation of the same UB exploitation.

Moving the printf to main (via get_it()) removed the barrier and restored the divergence.

8. Assembly Deep-Dive (bug_demo_O2.s)

The generated assembly (bug_demo_O2.s) shows the inlined loop. The critical section (annotated):

.L7:                                   ; loop top — load saved_seed
    leal  (%rdx,%rdx), %r8d            ; r8d = it + it  (call 1 new_it; may wrap!)
    testl %edx, %edx                   ; test ORIGINAL it (before doubling)
    jg    .L2                          ; it > 0 → fast path, NO branch check for call 2

    xorl  $593970775, %r8d             ; MASK applied (call 1, it ≤ 0 path)
    ...
    testl %r8d, %r8d                   ; call 2 gets its own branch — but only from
    jg    .L4                          ;   the it ≤ 0 entry path
    xorl  $593970775, %esi             ; MASK for call 2 if needed

.L2:                                   ; entered when original it was positive
    leal  -1(%r8), %esi                ; nit1 = (it+it) - 1
    andl  $127, %esi
    imull mt(,%rsi,4), %eax            ; leh *= mt[nit1 & 127]
    leal  0(,%rdx,4), %esi             ; THE BUG: esi = it * 4
                                        ;   GCC assumed it+it > 0 (signed overflow = UB)
                                        ;   so it*2 again needs no sign check.
                                        ;   When it = 2^30: it*4 = 2^32 → truncates to 0.
    ...
    ; falls straight into call 2 with esi = it*4, no branch, no MASK

The testl %edx, %edx / jg .L2 pair is the only branch serving both calls. It tests the pre-doubling it, not the result of the doubling (%r8d). Once jg .L2 is taken, call 2’s if (it <= 0) check is gone entirely — replaced by the hardcoded leal 0(,%rdx,4).

In contrast, -O0 emits two independent call _random instructions. Each is a black box; no cross-call value-range analysis is possible and _irandm executes its branch correctly on every invocation.

Trigger conditions summary

9. Compiler Options Reference

Flags that trigger the bug

Flags in %{optflags} relevant to this bug

-O2 -flto=auto -ffat-lto-objects -fexceptions -g -grecord-gcc-switches -pipe
-Wall -Wno-complain-wrong-lang -Werror=format-security
-Wp,-U_FORTIFY_SOURCE,-D_FORTIFY_SOURCE=3 -Wp,-D_GLIBCXX_ASSERTIONS
-specs=/usr/lib/rpm/redhat/redhat-hardened-cc1
-fstack-protector-strong
-specs=/usr/lib/rpm/redhat/redhat-annobin-cc1
-m64 -march=x86-64 -mtune=generic
-fasynchronous-unwind-tables -fstack-clash-protection
-fcf-protection -mtls-dialect=gnu2
-fno-omit-frame-pointer -mno-omit-leaf-frame-pointer

Of these, -O2 and -flto=auto are the two flags directly responsible for the bug. The rest add security hardening and debug info but do not influence the PRNG optimization.

Flags in %{build_ldflags} relevant to this bug

-Wl,-z,relro -Wl,--as-needed -Wl,-z,pack-relative-relocs -Wl,-z,now
-specs=/usr/lib/rpm/redhat/redhat-hardened-ld
-specs=/usr/lib/rpm/redhat/redhat-hardened-ld-errors
-specs=/usr/lib/rpm/redhat/redhat-annobin-cc1
-Wl,--build-id=sha1

The hardened-ld specs activate the LTO linker plugin. Without passing LDFLAGS correctly, -flto in CFLAGS compiles LTO IR into the objects but the link step discards it — which is why early -fwrapv tests appeared to fix the issue (the LTO IR was never linked).

Flags that suppress the bug

Security hardening visible in the RPM binary (unrelated to the bug)