Skip to content

When the UTF-8 invariant broke

Level: 301 · deep dive

One line: Three published CVEs in the string library, and all three are the same shape — std skipped a check because a String is always valid UTF-8, and safe code with no unsafe anywhere in it could make that stop being true.

A String is a Vec<u8> plus a promise. The promise is that the bytes are valid UTF-8, and it is what lets chars() decode without validating and &s[a..b] return a &str without re-checking. A promise that load-bearing is also an invitation: the code that writes into the buffer can go faster by assuming it, and every such assumption is a place where safe code, somewhere else, gets to be wrong.

Three times it was. Each fix is a few lines, and each is in the source already on your disk — $(rustc --print sysroot)/lib/rustlib/src/rust/library/alloc/src/.

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

CVE-2018-1000810  str::repeat  — capacity by multiplication
  "ab".len() * n, wrapped   = 0
  "ab".len().checked_mul(n) = None
  "ab".repeat(3)            = "ababab"
  "ab".repeat(n)            = panic "capacity overflow"

CVE-2020-36317  String::retain  — a predicate that panics
  before        "0è0"  [30, C3, A8, 30]  len 4
  panic         "the predicate gave up"
  after         "è"  [C3, A8]  len 2
  the buffer held [C3, A8, A8, 30]
  as UTF-8      Err(Utf8Error { valid_up_to: 2, error_len: Some(1) })

CVE-2020-36323  [Borrow<str>]::join  — a Borrow that changes its mind
  consistent            Ok("x-a")
  1 byte, then 12       Err("mid > len")
  12 bytes, then 1      Ok("x-a")

The three

Advisory Function What safe code did Affected Fixed in
CVE-2018-1000810 ↗ str::repeat asked for enough copies that the capacity multiplication wrapped 1.26.0 – 1.29.0 1.29.1
CVE-2020-36317 ↗ String::retain panicked inside the predicate 1.26.0 – 1.48.0 1.49.0
CVE-2020-36323 ↗ [Borrow<str>]::join wrote a Borrow impl that answers differently each call 1.28.0 – 1.51.0 1.52.0

None of the three needs unsafe in the caller. That is what makes them soundness bugs rather than bugs: the library offered a safe API that could be driven into undefined behaviour, so the fault is std's and the fix has to be std's.

It is worth separating this from the other thing that goes by the same word. When the type checker is wrong is about compiler soundness — rustc accepting a program it should have rejected. Here the compiler was right about every line. What went wrong is one layer up: a hand-written unsafe block inside std, resting on a fact that safe Rust does not guarantee. Same symptom, different owner, and a different fix — a compiler soundness bug is fixed in the type checker, and these three were fixed by adding a check to the library.

str::repeat — the capacity was a multiplication

str::repeat hands the work to the slice version and re-labels the bytes:

pub fn repeat(&self, n: usize) -> String {
    unsafe { String::from_utf8_unchecked(self.as_bytes().repeat(n)) }
}

[T]::repeat allocates once and then doubles the buffer with ptr::copy_nonoverlapping, writing into capacity it believes it already has. The belief comes from one line:

let capacity = self.len().checked_mul(n).expect("capacity overflow");

Before 1.29.1 that multiplication was unchecked. len * n wraps like any other usize arithmetic, so a large enough n produced a small capacity — 2 * (usize::MAX / 2 + 1) is 0 — and then the copies ran off the end of it. The advisory is blunt about why one arithmetic slip became a heap overflow:

The rest of the implementation of str::repeat contains unsafe code that relies on a preallocated vector having the capacity calculated earlier.

n is often not a constant. A template engine repeating a padding string, a protocol handler honouring a length field, anything that reaches repeat with a number from outside — that is the reachable path, and it is why this one scored 9.8.

String::retain — the predicate is allowed to panic

retain does not build a new string. It walks the existing buffer and shifts every kept character left over the deleted ones, then sets the final length at the end. In between, the String's length still describes the old contents while the bytes underneath are half-moved.

A panic out of the predicate lands exactly there. The program above deletes the leading 0 of "0è0", keeps the è — which moves two bytes left, over the 0 that just went — and then gives up. The buffer at that instant holds [C3, A8, A8, 30]: the moved è, then the tail nobody has reached yet, whose first byte is now a stray continuation byte. Before 1.49.0 the length stayed at 4, so the String handed all four bytes to the caller. The program asks from_utf8 what they are: Utf8Error { valid_up_to: 2, error_len: Some(1) }.

The fix is a destructor:

struct SetLenOnDrop<'a> {
    s: &'a mut String,
    idx: usize,
    del_bytes: usize,
}

impl<'a> Drop for SetLenOnDrop<'a> {
    fn drop(&mut self) {
        let new_len = self.idx - self.del_bytes;
        debug_assert!(new_len <= self.s.len());
        unsafe { self.s.vec.set_len(new_len) };
    }
}

Drop runs during unwinding, so the length is corrected on the way out whether the loop finished or the predicate exploded. The caller gets "è" — truncated at the last character that was fully moved, which is a value, not a corruption.

This is panic safety, and it is a distinct discipline from memory safety: the question is not can this code have a dangling pointer but is every intermediate state of this mutation a legal value of the type. Mutex poisoning is the same question answered a different way — there the type cannot fix itself, so it refuses to be used again.

[Borrow<str>]::join — a safe trait that is not required to be consistent

join wants one allocation. So it borrows every element to add up the exact total length, allocates that, and then borrows them again to copy the bytes in without bounds checks. Two borrows, one assumption: that an element is the same length both times.

Borrow<str> is a safe trait. Nothing in it promises determinism, and interior mutability makes an inconsistent impl about six lines long — the Shifty in the program above returns one string the first time it is asked and a different one afterwards, with no unsafe and no cleverness. The report ↗ came with a playground link and one sentence: a non-UTF-8 string "by only using safe Rust".

The fix is not a promise extracted from Borrow. You cannot fix a safe trait's contract by writing documentation at it, because the compiler will keep accepting impls that ignore you. The fix is to stop trusting it, and alloc/src/str.rs now says so in the source, above the function, as a threat model:

// `Borrow` is a safe trait, and implementations are not required
// to be deterministic. An inconsistent `Borrow` implementation could return slices
// of different lengths on consecutive calls (e.g. by using interior mutability).

Three defences follow from it, and the program's output shows each one:

  • The first element is borrowed once, and the result is reused. It is the only element that can be, because the length pass takes it before the loop.
  • If a later element grows, the copy is a bounds-checked split_at_mut into a target sized from the original total, so it panics — mid > len. A panic is a correct outcome here; the alternative is a write past the end.
  • If a later element shrinks, the spare capacity is simply never written, and the final length counts what actually was:
let result_len = reserved_len - remain.len();
result.set_len(result_len);

"x-a", not "x-a" plus eleven bytes of whatever the allocator last had there.

What the three have in common

Every one of them is a fast path. repeat doubles rather than pushes, retain shifts in place rather than building a new string, join allocates once rather than growing. Strip the optimization out of any of them and the bug cannot exist — the safe rewrites in the kata are a handful of lines each, and none of them can go wrong this way.

Every one of them broke on a fact that safe Rust never promised. That arithmetic does not wrap. That a closure returns. That a trait impl agrees with itself. Each is true of almost every program, which is why each survived review, and none of them is guaranteed by the type system, which is why each was a CVE.

Each fix is a check, not a redesign. A checked_mul, a Drop impl, a subtraction. unsafe did not go away in any of the three — it was still the whole point — but the obligation it carries got written down. That is what unsafe actually turns off: not the checks, the checking of one specific claim, which somebody then has to make true.

What is not here

The bugs that were merely wrong. "bananas".contains("nana") returning false, and a Greek word lowercasing to the wrong sigma for two years of stable releases — no CVE, no unsafe, no crash, just a wrong answer. Those are Wrong, but not unsafe.

The escaping one. CVE-2024-24576 ↗ is about text too, but nothing in it touches UTF-8: Command::arg documents that an argument reaches the child as-is, and on Windows a .bat or .cmd goes through cmd.exe, which re-parses it. std therefore has to escape, the escaping was incomplete, and an attacker who controlled an argument got arbitrary command execution. Fixed in 1.77.2 by refusing — InvalidInput when an argument cannot be escaped safely — and then fixed again ↗ for arguments ending in whitespace or periods. It is the data-versus-delimiter problem ↗, not the encoding problem, and it is only a std bug at all because std made a promise about somebody else's parser.

The other fifteen. These three are the only entries about str and String in RustSec's advisories for std ↗, which currently lists eighteen. The rest are iterators and collections — four of them are Zip on its own. Strings are not unusually dangerous; they are unusually optimized, which is a different thing and the reason this page exists.

If you are coming from another language

C. The invariant is the NUL terminator and the equivalent bug is the entire history of strcpy. The difference is not that Rust cannot have these — it plainly can — but where they live: three of them, in one library, each with a number, a date and a release everybody got at once. In C the same class of bug is in your program, and there are as many of them as there are programs.

Python. A str cannot be corrupted from Python, because the buffer is not reachable from Python; CPython's own equivalents are in C extension code and in the unicode object's internals. The nearest thing you can write yourself is the same shape as join here — a __len__ that disagrees with the iterable it describes — and it produces a wrong answer rather than a memory error, because CPython re-checks.

Java, C#. String is UTF-16 with no validity invariant at all: an unpaired surrogate is a perfectly legal char. There is nothing to break, so this class of bug does not exist — and the cost is paid later, at the encode step, as a ? in the output or an exception at a boundary rather than a CVE. See Four lengths for the other end of that trade.

ABAP. Text is a managed type in a managed runtime; there is no buffer to write past and no unsafe to reach for. The analogue is the conversion at the edge — a CONVERT TEXT or a codepage-mismatched RFC — where the failure is mojibake in a field rather than a byte outside an allocation.

Practice

Write the safe version of each of the three, then say what the unsafe one buys. Build safe_join, safe_retain and safe_repeat using nothing but push_str, collect and checked_mul. Drive all three with the same hostile inputs the lesson used — the Borrow that grows between calls, the predicate that panics, the n that wraps — and show that each safe version is boring: no panic to catch, no invariant to restore.

Then finish the sentence the exercise is really about. For each pair, name the operation the std version avoids that yours performs, and say what it must prove in order to skip it. If you cannot name the proof obligation, you have not found the unsafe block yet.

Solution

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

//! Kata: write the safe version of each of the three, and name what the
//! `unsafe` one has to prove in order to be faster.

use std::borrow::Borrow;
use std::cell::Cell;
use std::panic::{self, AssertUnwindSafe};

fn caught<T>(f: impl FnOnce() -> T) -> Result<T, String> {
    let hook = panic::take_hook();
    panic::set_hook(Box::new(|_| {}));
    let outcome = panic::catch_unwind(AssertUnwindSafe(f));
    panic::set_hook(hook);
    outcome.map_err(|e| match e.downcast_ref::<&str>() {
        Some(s) => (*s).to_string(),
        None => e.downcast_ref::<String>().cloned().unwrap_or_default(),
    })
}

struct Shifty {
    calls: Cell<usize>,
    at_length_time: &'static str,
    at_copy_time: &'static str,
}

impl Shifty {
    fn new(at_length_time: &'static str, at_copy_time: &'static str) -> Self {
        Shifty { calls: Cell::new(0), at_length_time, at_copy_time }
    }
}

impl Borrow<str> for Shifty {
    fn borrow(&self) -> &str {
        let n = self.calls.get();
        self.calls.set(n + 1);
        if n == 0 { self.at_length_time } else { self.at_copy_time }
    }
}

/// One borrow per element, no promised capacity, no `unsafe`.
fn safe_join<S: Borrow<str>>(parts: &[S], sep: &str) -> String {
    let mut out = String::new();
    for (i, part) in parts.iter().enumerate() {
        if i > 0 {
            out.push_str(sep);
        }
        out.push_str(part.borrow());
    }
    out
}

/// Builds a new `String` instead of shifting bytes inside the old one, so an
/// unwind out of `f` drops a half-built value nobody can observe.
fn safe_retain(s: &String, mut f: impl FnMut(char) -> bool) -> String {
    s.chars().filter(|c| f(*c)).collect()
}

/// The capacity question asked out loud, instead of assumed.
fn safe_repeat(s: &str, n: usize) -> Option<String> {
    let capacity = s.len().checked_mul(n)?;
    let mut out = String::with_capacity(capacity);
    for _ in 0..n {
        out.push_str(s);
    }
    Some(out)
}

fn main() {
    println!("join — a Borrow that grows between the two calls");
    let a = [Shifty::new("x", "x"), Shifty::new("a", "aaaaaaaaaaaa")];
    println!("  std::join   {:?}", caught(|| a.join("-")));
    let b = [Shifty::new("x", "x"), Shifty::new("a", "aaaaaaaaaaaa")];
    println!("  safe_join   {:?}", safe_join(&b, "-"));
    println!("  the difference: safe_join borrows once and believes the answer;");
    println!("  join borrows twice, so it must survive two different answers.");

    println!();
    println!("retain — a predicate that panics");
    let s = String::from("0\u{e8}0");
    let mut seen = 0;
    let out = caught(|| {
        safe_retain(&s, |_| {
            seen += 1;
            match seen {
                1 => false,
                2 => true,
                _ => panic!("the predicate gave up"),
            }
        })
    });
    println!("  safe_retain {:?}", out);
    println!("  original    {:?}  {:02X?}", s, s.as_bytes());
    println!("  the difference: nothing was written into `s`, so an unwind cannot");
    println!("  leave it holding half of a moved character.");

    println!();
    println!("repeat — a capacity that would wrap");
    let n = usize::MAX / 2 + 1;
    println!("  safe_repeat(\"ab\", 3)  {:?}", safe_repeat("ab", 3));
    println!("  safe_repeat(\"ab\", n)  {:?}", safe_repeat("ab", n));
    println!("  the difference: `?` on a `checked_mul` is the same guard std spells");
    println!("  `.expect(\"capacity overflow\")`; the bug was that neither was there.");
}

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

join — a Borrow that grows between the two calls
  std::join   Err("mid > len")
  safe_join   "x-a"
  the difference: safe_join borrows once and believes the answer;
  join borrows twice, so it must survive two different answers.

retain — a predicate that panics
  safe_retain Err("the predicate gave up")
  original    "0è0"  [30, C3, A8, 30]
  the difference: nothing was written into `s`, so an unwind cannot
  leave it holding half of a moved character.

repeat — a capacity that would wrap
  safe_repeat("ab", 3)  Some("ababab")
  safe_repeat("ab", n)  None
  the difference: `?` on a `checked_mul` is the same guard std spells
  `.expect("capacity overflow")`; the bug was that neither was there.

See also

Po polsku

Trzy błędy z tej strony łączy jedno: każdy był w optymalizacji, nie w zwykłej ścieżce. String w Ruscie to Vec<u8> plus obietnica, że bajty są poprawnym UTF-8 — i właśnie dlatego chars() niczego nie sprawdza, a &s[a..b] nie waliduje na nowo. Kod, który pisze do takiego bufora, może więc pominąć kontrolę i być szybszy; cena jest taka, że pominięta kontrola musi być prawdziwa z innego powodu. Trzy razy nie była, i za każdym razem wystarczył bezpieczny kod: mnożenie, które się przekręciło, panic! w domknięciu i implementacja Borrow, która za drugim razem odpowiada inaczej.

Praktyczny wniosek nie brzmi „nie ufaj std” — te błędy są znalezione, ponumerowane i naprawione, a łatkę dostali wszyscy naraz, czego w C nie ma. Brzmi tak: unsafe nie wyłącza sprawdzania, tylko przenosi je na człowieka, a obietnica, którą wtedy składasz, musi być prawdziwa także wtedy, gdy ktoś inny napisze złośliwą, ale całkowicie legalną implementację cechy. Jeśli piszesz unsafe, wypisz na głos założenie — dokładnie tak, jak zrobiło to alloc/src/str.rs, gdzie komentarz nad funkcją opisuje zagrożenie, zanim opisze rozwiązanie.

Szukaj po polsku: niezmiennik typu (invariant) · bezpieczeństwo pamięci a poprawność · panic safety a niezmienniki · przepełnienie mnożenia usize · dlaczego String gwarantuje UTF-8