The arithmetic of integer overflows

shl $0x4,%r13d. That single instruction is what gcc 13.3 emitted for count * 16 in the allocator below, and it is the entire bug. A 32-bit left shift, no overflow check, the wrap handled silently by the CPU. I built the target on Ubuntu 24.04 to see exactly where the length check stops protecting you, and the answer is: one instruction earlier than you’d think.

This is a reproducible demo, not a finding from a real audit. Everything below is real output from a binary I compiled, but I picked the bug to make a point, I didn’t trip over it in production.

The bug that isn’t in the source

Here’s the allocator. It takes a record count, refuses obviously absurd values, sizes a buffer, and copies into it.

void *make_table(uint32_t count, const char *src, size_t src_len) {
    if (count > 0x10000000) {           // the "check"
        fprintf(stderr, "count too large\n");
        return NULL;
    }
    size_t bytes = count * 16;          // the bug lives here
    void *table = malloc(bytes);
    if (!table) return NULL;
    memcpy(table, src, src_len);
    return table;
}

Read it the way a reviewer reads it: there’s a bound on count, bytes is derived from count, malloc is checked for NULL. Nothing looks wrong. The check even has a comfortable margin, 0x10000000 is 256M records, far more than any real table.

That margin is the problem. count is uint32_t and 16 is int, so count * 16 is computed in 32-bit arithmetic before it’s widened to the 64-bit size_t. Pass count = 0x10000000: the check passes (it’s not strictly greater than 0x10000000), then 0x10000000 * 16 = 0x100000000, which doesn’t fit in 32 bits and wraps to 0. You get malloc(0), a valid tiny chunk, followed by a copy that assumes a full-size buffer.

$ ./vuln 4
requested count=4  ->  malloc(64)
ok, table at 0x558a73d902a0

$ ./vuln 0x10000000
*** buffer overflow detected ***: terminated
Aborted

The bound you wrote is real. It just guards the wrong number.

The compiler is not on your side here

I expected to find a multiply in the disassembly. There isn’t one. gcc strength-reduced * 16 to a shift, and the shift operates on the 32-bit sub-register:

$ objdump -d --no-show-raw-insn vuln2
    1271:   shl    $0x4,%r13d
    1275:   mov    %r13,%rdi
    1278:   call   10a0 <malloc@plt>

%r13d is the low 32 bits of %r13. The shift discards anything above bit 31 and the subsequent mov %r13,%rdi zero-extends the wrapped result into the 64-bit argument register. There is no jo, no seto, no comparison. The C standard says unsigned overflow wraps, so the compiler is correct to emit exactly this and nothing more. Worth noting: this is the well-behaved case. Had count been signed, the overflow would be undefined and the optimizer would be free to assume it never happens, which is its own category of pain.

The lesson I’d push on: you cannot review allocation size math by reading the C. The types decide the width, the width decides the wrap, and the wrap is invisible until you look at the register the shift lands in.

Where the safety net actually catches

Here’s what surprised me. I assumed the naive build would corrupt the heap and limp on. It didn’t, glibc 2.39 aborted before the copy finished. Even when I made the copy length a runtime value that the compiler can’t see:

$ gcc -O2 -o vuln2 vuln2.c        # _FORTIFY_SOURCE on by default
$ ./vuln2 0x10000000 64
*** buffer overflow detected ***: terminated
Aborted

The catch is that memcpy to a fortifiable destination compiles to __memcpy_chk, and on a malloc(0) chunk glibc knows the usable size is far below 64 bytes. The check fires on the destination capacity, not on the integer math. That’s a real mitigation and it’s on by default on Ubuntu, but lean on what it actually does: it catches the overflow at the copy, after the undersized allocation already happened. Change the access pattern, write in a loop with per-element bounds derived from the same wrapped count, and __memcpy_chk never enters the picture. The mitigation is downstream of the bug, so it only covers the shapes it recognizes.

ASan, predictably, names it precisely:

$ gcc -O1 -fsanitize=address -o vuln_asan vuln2.c
$ ./vuln_asan 0x10000000 64
==554==ERROR: AddressSanitizer: heap-buffer-overflow
WRITE of size 64 at 0x502000000010 thread T0
  ... in make_table

A 64-byte write into a zero-byte allocation. ASan sees the chunk size and the access, so it doesn’t care which integer wrapped, it catches the consequence either way. In practice that makes it the tool I trust to find this class; it doesn’t make the underlying arithmetic any safer in a shipping binary.

The signed case is worse: the check just disappears

The allocator above wrapped cleanly because count was unsigned, and unsigned wrap is defined. Signed overflow is undefined, and “undefined” means the optimizer gets to assume it never happens. That assumption deletes your safety checks.

Here’s the canonical broken guard, the one that ships in real code because it reads as obviously correct:

int safe_to_add(int a, int b) {
    if (a + b < a)      // "if it wrapped, the sum got smaller"
        return 0;       // overflow, refuse
    return 1;
}

The logic is sound for two’s-complement hardware: INT_MAX + 1 wraps negative, so a + b < a catches it. Except it doesn’t catch anything, at any optimization level:

$ gcc -O0 -o c0 signed_cert.c && ./c0
safe_to_add(INT_MAX, 1) = 1      # says "fine"

$ gcc -O2 -o c2 signed_cert.c && ./c2
safe_to_add(INT_MAX, 1) = 1      # also "fine"

INT_MAX + 1 reported as safe to add, at -O0 and -O2 both. When the overflowing expression is written straight into the if with no intermediate variable, gcc treats a + b < a as unconditionally false, because the only way it’s true is signed overflow, and signed overflow is defined not to happen. The -O2 disassembly is the whole function:

$ objdump -d --no-show-raw-insn c2
0000000000001180 <safe_to_add>:
    1184:   mov    %esi,%eax
    1186:   not    %eax
    1188:   shr    $0x1f,%eax
    118b:   ret

not %eax; shr $0x1f extracts the sign bit of ~b, which is b >= 0. gcc reasoned: signed overflow is UB, so I may assume it never occurs, so a + b < a can only be true when b < 0, so the whole thing is just “is b non-negative.” It rewrote the function around an assumption the C standard handed it for free. The overflow test you wrote was deleted because it could only trigger on overflow.

The part that genuinely bothered me: I went looking for a warning and there isn’t one.

$ gcc -O2 -Wstrict-overflow=5 -c signed_cert.c
$        # silent at every level, 2 through 5

No diagnostic at any -Wstrict-overflow level on gcc 13.3. The check vanishes and the compiler says nothing. This is the real argument for -fsanitize=undefined in test builds, UBSan flags the overflow at runtime where a static warning won’t. In practice, if you’re relying on post-hoc overflow detection in signed arithmetic, you’re not detecting overflow, you’re writing dead code that the optimizer has already noticed is dead.

Computing the size without the wrap

The fix isn’t “validate count harder.” Any bound on count alone is a bound on the wrong quantity. Compute the product in a width that can’t wrap, or detect the wrap explicitly:

size_t bytes;
if (__builtin_mul_overflow(count, (size_t)16, &bytes))
    return NULL;                      // wrap detected, refuse
void *table = malloc(bytes);

__builtin_mul_overflow does the multiply at full width and returns whether it overflowed the destination type, so the check is on the actual number that reaches malloc. The signed sibling __builtin_add_overflow fixes the previous section the same way, and unlike the hand-rolled sum < a, it survives -O2 because the compiler can’t assume away a builtin:

$ gcc -O2 -o fix fix.c && ./fix    # __builtin_add_overflow version
0                                   # INT_MAX + 1 correctly refused

gcc and clang both lower these to an instruction that reads the overflow flag directly, the seto/jo that was missing from every disassembly above. glibc’s own reallocarray exists for exactly this reason. If your allocator wrapper doesn’t take (nmemb, size) separately and check the product, it’s reimplementing the bug.

The thing I’d actually change in a codebase: ban bare malloc(a * b) in review and treat every multiplication feeding an allocation as a wrap until proven otherwise. The arithmetic is the attack surface, not the bounds check sitting above it. Which leaves the question worth chewing on: how many of your size calculations happen in int or uint32_t because that’s what the upstream API handed you, before anyone gets to the size_t you think you’re allocating?