Buffer overruns

Level: 201 · for C and C++ programmers

One line: An off-by-one in a loop bound reads whatever is next on the stack, and the sum of three small numbers comes back as a different ten-digit value on every run.

The program

#include <stdio.h>

int main(void) {
    int scores[3] = {5, 4, 3};
    int total = 0;

    for (int i = 0; i <= 3; i++) {      /* <= : one step too far */
        total += scores[i];
    }

    printf("%d\n", total);
    return 0;
}

<= where < was meant. The whole bug.

What it did

Real runs — Apple clang 21.0.0, x86_64 macOS, -Wall (no warnings), three runs of each build

-O0   1433338037   620167213    1175781431
-O2   -1274314576  -1189662544  -1094442832

The right answer is 12. Every run gives a different wrong one, because the fourth read picks up whatever is at that stack address this time round.

Note the empty warning line. clang -Wall said nothing, and that is the interesting part, because on a constant index it does speak up:

Real output — clang -std=c17 -Wall -O0 constant_index.c, where the program says scores[3] directly

constant_index.c:5:20: warning: array index 3 is past the end of the array (that has type 'int[3]') [-Warray-bounds]
    5 |     printf("%d\n", scores[3]);
      |                    ^      ~

So the diagnostic exists, and it depends entirely on whether the optimizer's dataflow analysis can see the index. A loop bound, a value from argc, an index computed two functions away — each one takes you further from the warning, and the further you are the more likely the code is real.

AddressSanitizer catches the loop version, and this is the case where it is at its best — it knows the extent of a stack object, not just of a heap block:

Real output — clang -fsanitize=address -g -O0, abridged

==85883==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ff7b1e6594c
READ of size 4 at 0x7ff7b1e6594c thread T0
    #0 0x00010e0998d7 in main buffer_overruns.c:8

Why the standard allows it

Forming a pointer more than one past the end of an array, or dereferencing the one-past-the-end pointer, is undefined behaviour ↗. C has no bounds to check against at run time: scores[i] is defined as *(scores + i), and an array decays to a bare pointer with no length attached the moment it is passed anywhere. There is nothing at run time that knows the array had three elements.

That is the actual difference from the Rust rows below, and it is a data-layout difference rather than a checking one. A Rust slice is a pointer and a length, together, in one value.

What Rust does instead

The length travels with the data, so the check is possible — and there are two ways to ask, which is the part worth learning:

let scores = vec![5, 4, 3];

println!("{:?}", scores.get(3));    // None    — "is there one?"
println!("{}", scores[3]);          // panics  — "there is one, and I want it"

Verified output of buffer_overruns.rs — regenerated by tools/run_examples.py, never hand-typed.

sum of the three -> 12
scores.get(2)    -> Some(3)
scores.get(3)    -> None
scores[3]        -> index out of bounds: the len is 3 but the index is 3

The last line of that output is the panic message itself, caught so the example can finish. Uncaught, it ends the program with the same text, a line number, and no reading of memory that was not ours:

index out of bounds: the len is 3 but the index is 3

v[i] is the right choice when an out-of-range index is a bug in your program — you want the abort. v.get(i) is right when it is a question, and it hands you an Option so the empty answer has to be handled. Neither of them reads past the end.

The refusal

The check is at run time, so most out-of-range indexing is a panic rather than a build error. With a constant index into an array, though, rustc refuses outright — the mirror of the -Warray-bounds warning above, promoted to an error:

Real rustc output — constant_index.rs, --edition 2024

error: this operation will panic at runtime
 --> constant_index.rs:3:20
  |
3 |     println!("{}", scores[3]);
  |                    ^^^^^^^^^ index out of bounds: the length is 3 but the index is 3
  |
  = note: `#[deny(unconditional_panic)]` on by default

What the check costs

A bounds check is a compare and a branch, on a branch predictor that will get it right every time. Where it would be measurable — a tight loop over a slice — the ordinary idiom sidesteps it rather than paying it: for s in &scores and the iterator methods never index, so there is no bound to test; the iterator cannot go out of range by construction. That is the practical reason to write for x in &v instead of for i in 0..v.len(), and it is a better reason than style.

When you genuinely need indexing with the check gone, get_unchecked exists and is unsafe — you have written down that the bound is your responsibility, and grep unsafe finds it.

If you are coming from another language

• C++ — std::vector::at() throws and operator[] does not, which is the same pair of questions as get and [] here, with the default the other way round. std::span (C++20) is the same idea as a slice: pointer plus length in one value. The difference that remains is the default — reaching for the unchecked one is what [] does in C++ and what get_unchecked does here, and only one of those is a word you have to type.
• Python — lst[3] raises IndexError, so you already live in the checked world; .get() is the dict.get you know, and None is what it returns. Nothing about bounds is new. What changes is that a Rust index panic is not catchable as ordinary control flow — you choose get up front rather than wrapping in try.
• ABAP — READ TABLE itab INDEX 4 sets sy-subrc to 4 and leaves the work area alone, so this is the get behaviour with the answer in a separate variable you can forget to read. Option is that pair collapsed into one value the compiler will not let you unwrap silently. Reading past the end of a STRING or an internal table raises a catchable exception rather than reading memory, so the hardware half of this bug is not part of your world.

Practice

Four ways to read past the end. For a [u32; 3], work out what happens with a constant index of 3, a runtime index of 3, .get(3), and .iter().sum(). One of the four is rejected without running the program — say which and why it can be.

Then say what the bounds check costs, why the safe form is usually also the fast one, and what C has in place of all of this.

Solution

buffer_overruns_kata.rs in full — pasted here by tools/run_examples.py from the file CI compiles and runs.

//! Kata solution: the off-by-one, three ways.
//!
//!   rustc --edition 2024 buffer_overruns_kata.rs -o /tmp/bok && /tmp/bok

fn main() {
    let readings = [12u32, 7, 30];

    println!("THE C SHAPE");
    println!("  for (int i = 0; i <= 3; i++) sum += readings[i];");
    println!("  The fourth read is whatever sits after the array -- a saved");
    println!("  register, a frame pointer, part of another variable -- so the");
    println!("  sum is a different large number on every run, and at -O2 it may");
    println!("  be a different one again.");
    println!();

    println!("1. THE INDEX THAT PANICS");
    println!("  readings[3] -> index out of bounds: the len is 3 but the index is 3");
    println!("  A bounds check, at runtime, on a slice whose length is not known");
    println!("  at compile time. It costs a compare-and-branch, and the branch");
    println!("  predictor makes it very nearly free -- and it turns a silent");
    println!("  wrong answer into a stopped program with a line number.");
    println!();

    println!("2. THE ONE THE COMPILER CATCHES OUTRIGHT");
    println!("  On a fixed-size array with a constant index, rustc rejects it at");
    println!("  compile time: \"this operation will panic at runtime\". No");
    println!("  execution needed -- the length is part of the type [u32; 3].");
    println!();

    println!("3. THE FORM THAT CANNOT BE WRONG");
    let sum: u32 = readings.iter().sum();
    println!("  readings.iter().sum::<u32>() = {sum}");
    println!("  There is no index to get wrong. The iterator knows the length,");
    println!("  and the bounds check is usually optimised away entirely because");
    println!("  the compiler can prove the range -- so the safe form is also the");
    println!("  fast one.");
    println!();

    println!("4. AND THE ONE THAT ASKS INSTEAD OF ASSUMING");
    for i in [2usize, 3] {
        match readings.get(i) {
            Some(v) => println!("  get({i}) -> Some({v})"),
            None => println!("  get({i}) -> None    <- no panic, a value to handle"),
        }
    }
    println!("  .get() returns Option, so 'past the end' becomes a case in the");
    println!("  type rather than a decision about whether to trust the index.");
    println!();

    println!("WHAT C HAS INSTEAD");
    println!("  Nothing in the language. An array decays to a pointer at the");
    println!("  first opportunity and the length is gone -- which is why every");
    println!("  C API takes a separate count, and why every one of those counts");
    println!("  is a chance to disagree with the buffer it describes.");

    assert_eq!(sum, 49);
    assert_eq!(readings.get(3), None);
}

Verified output of buffer_overruns_kata.rs — regenerated by tools/run_examples.py, never hand-typed.

THE C SHAPE
  for (int i = 0; i <= 3; i++) sum += readings[i];
  The fourth read is whatever sits after the array -- a saved
  register, a frame pointer, part of another variable -- so the
  sum is a different large number on every run, and at -O2 it may
  be a different one again.

1. THE INDEX THAT PANICS
  readings[3] -> index out of bounds: the len is 3 but the index is 3
  A bounds check, at runtime, on a slice whose length is not known
  at compile time. It costs a compare-and-branch, and the branch
  predictor makes it very nearly free -- and it turns a silent
  wrong answer into a stopped program with a line number.

2. THE ONE THE COMPILER CATCHES OUTRIGHT
  On a fixed-size array with a constant index, rustc rejects it at
  compile time: "this operation will panic at runtime". No
  execution needed -- the length is part of the type [u32; 3].

3. THE FORM THAT CANNOT BE WRONG
  readings.iter().sum::<u32>() = 49
  There is no index to get wrong. The iterator knows the length,
  and the bounds check is usually optimised away entirely because
  the compiler can prove the range -- so the safe form is also the
  fast one.

4. AND THE ONE THAT ASKS INSTEAD OF ASSUMING
  get(2) -> Some(30)
  get(3) -> None    <- no panic, a value to handle
  .get() returns Option, so 'past the end' becomes a case in the
  type rather than a decision about whether to trust the index.

WHAT C HAS INSTEAD
  Nothing in the language. An array decays to a pointer at the
  first opportunity and the length is gone -- which is why every
  C API takes a separate count, and why every one of those counts
  is a chance to disagree with the buffer it describes.

See also

• Partial functions — get as the total version of a function that has no answer for some inputs
• What a panic costs — what scores[3] actually does, and when that is the right choice
• Signed overflow — the other run-time check, and the one whose default changes with the build profile
• The bugs Rust is a reply to — the other eight

Po polsku

Klasyczny „błąd o jeden” (off-by-one): <= zamiast <, czyli czwarty odczyt z trzyelementowej tablicy. Poprawna suma to 12, a program wypisał 1433338037, potem 620167213, potem 1175781431 — za każdym razem co innego, bo czyta to, co akurat leży dalej na stosie. Uwaga na polską nazwę: „przepełnienie bufora” kojarzy się u nas przede wszystkim z zapisem poza koniec i z exploitami, a tutaj nic nie jest zapisywane. To czysty odczyt poza zakresem — tak samo niezdefiniowany, a znacznie trudniejszy do zauważenia, bo program się nie wywraca, tylko zwraca liczbę.

Warto zapamiętać, czego -Wall nie powiedziało. Przy stałym indeksie (scores[3] wypisanym wprost) clang ostrzega przez -Warray-bounds, ale przy granicy pętli milczy — a im dalej indeks od miejsca, w którym optymalizator potrafi go policzyć (wartość z argc, indeks wyliczony dwie funkcje wcześniej), tym ciszej i tym bardziej realistyczny kod. Po stronie Rusta widać dokładnie to samo rozróżnienie: zwykłe indeksowanie sprawdzane jest w czasie działania, ale stały indeks poza zakresem rustc odrzuca już przy kompilacji, lintem unconditional_panic.

Różnica nie polega jednak na liczbie sprawdzeń, tylko na układzie danych. Tablica w C rozpada się do gołego wskaźnika i długość nigdzie z nią nie jedzie — w czasie działania nie ma czego sprawdzać. Wycinek (slice) &[i32] jest grubym wskaźnikiem (fat pointer): adres i długość w jednej wartości, więc pytanie „czy jest element numer 3?” w ogóle ma sens. Stąd dwa sposoby pytania i to jest właściwa lekcja tej strony: scores[3] znaczy „na pewno jest, dawaj” i przy pomyłce panikuje komunikatem index out of bounds: the len is 3 but the index is 3, a scores.get(3) znaczy „a jest?” i oddaje None w Option, którego nie da się przeoczyć. W pętli i tak zwykle nie indeksujemy — for s in &scores nie liczy żadnego indeksu, więc nie ma tam czego sprawdzać, i to jest lepszy argument za tą formą pętli niż estetyka.

Szukaj po polsku: przepełnienie bufora · błąd o jeden · odczyt poza zakresem tablicy · rust index out of bounds · rust slice get vs index · -Warray-bounds