Wrong, but not unsafe

Level: 201 → 301 · deep dive

One line: Two string bugs with no CVE, no unsafe and no crash — "bananas".contains("nana") was false, and for two years of stable releases a Greek word ending in Σ lowercased to the wrong sigma — and both were in a fast path, which is the only kind of code that can be wrong in a way the naive version cannot.

Memory safety is not correctness. The borrow checker will not tell you that a substring search missed, and Miri will not tell you that a letter came out in the wrong shape; both bugs below are perfectly well-behaved programs returning the wrong value. They are also both in an optimization, and that is not a coincidence: an optimization is a second implementation of the same function, and every input that takes it is untested by the tests written for the first one.

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

#16589  "bananas".contains(..)  — every substring, 2014 and now
  substrings tested          28
  reported missing           []
  contains("nana")           true
  find("nana")               Some(2)

#124714  to_lowercase and the final sigma
                    ΣΣ  ->  σς
                  ΟΔΟΣ  ->  οδος
                    aΣ  ->  aς
     abcdefghijklmnopΣ  ->  abcdefghijklmnopς
        'Σ' on its own  ->  σ

  k letters, then Σ — does the word end in ς?
    k in 1..=32, ending in σ   []
    k = 0, no word at all      "σ"

"bananas".contains("nana") — the periodic needle

Filed 2014-08-18 ↗, one sentence and a double loop:

Currently, "bananas".contains("nana") returns false. It is the only substring of "bananas" for which this is true.

str::find and str::contains do not scan. They use Two-Way — Crochemore and Perrin, 1991 — which splits the needle at a critical factorization and, on a mismatch, jumps forward by a distance computed from the needle rather than by one byte. That jump is what makes the search linear in the worst case with no extra memory, and it is only sound if the needle is aperiodic. A word has period p when x[i] == x[i+p] for every i in range: nana has period 2, because it is na twice. Jump by the whole needle length over a periodic needle and you step straight over a match.

So Two-Way carries a periodicity check and takes a shorter jump when it fires. From the fix ↗, merged five days later:

The reason "bananas".contains("nana") (and similar searches) were returning false was because the periodicity check was wrong.

What is worth taking from this is not the algorithm, it is the shape of the input. The bug needed a repeating needle, and a hand-written test for contains almost never has one — you write contains("world"), it passes, you move on. The report did not do that. It swept every substring of one word, all 28 of them, and let the machine say which was odd. That is the same test the program above still runs, and the miss list is now empty.

The final sigma, broken twice

Greek is the one place where lowercasing depends on where the letter is. Σ becomes σ in general and ς at the end of a word, and Final_Sigma is the only conditional but language-independent mapping ↗ in Unicode's SpecialCasing.txt. str::to_lowercase promises the full Unicode rules, so it owes you the right one.

2015 — it was not implemented. Issue #26035 ↗ reported the missing case; PR #26039 ↗ added it, hard-coded rather than built on a general condition mechanism, with a comment saying exactly that. It still reads that way today.

2022 — a fast path arrived. PR #97046 ↗, "improve case conversion happy path", landed in 1.63.0. Most strings are ASCII, so to_lowercase now converts the leading ASCII run in fixed-size chunks — vectorisable, and much faster — and hands the remainder to the Unicode loop.

2024 — the sigma was wrong again. Issue #124714 ↗:

"aΣ".to_lowercase()                 ->  aς      correct
"abcdefghijklmnopΣ".to_lowercase()  ->  abcdefghijklmnopσ

Sixteen ASCII letters, then a sigma at the end of a word, and it came out non-final. The reporter pinned the shape precisely: it happened whenever the Σ followed a multiple of 2 * size_of::<usize>() characters. That number is the fast path's chunk, and it is right there in alloc/src/str.rs as of 1.79.0 — the last release with the bug in it:

const USIZE_SIZE: usize = mem::size_of::<usize>();
const MAGIC_UNROLL: usize = 2;
const N: usize = USIZE_SIZE * MAGIC_UNROLL;

Sixteen bytes on a 64-bit machine, eight on a 32-bit one — so the same program was wrong at different word lengths depending on the target. (Today's std pins it at a fixed N = 16, with a comment saying it used to depend on usize.)

The fix ↗ is two lines:

-                map_uppercase_sigma(rest, i, &mut s)
+                let out_len = self.len() - rest.len();
+                let sigma_lowercase = map_uppercase_sigma(&self, i + out_len);
+                s.push(sigma_lowercase);

rest is what is left after the ASCII prefix. Asking map_uppercase_sigma about rest asks it to look for a preceding cased letter inside a slice the preceding letters are no longer in — so when the fast path had swallowed the whole word up to the Σ, the answer was "nothing before this", and nothing before it means not word-final. The fix passes the whole string and an index into it. Here is the function the index feeds, from the source on your disk:

fn map_uppercase_sigma(from: &str, i: usize) -> char {
    fn case_ignorable_then_cased<I: Iterator<Item = char>>(iter: I) -> bool {
        match iter.skip_while(|&c| c.is_case_ignorable()).next() {
            Some(c) => c.is_cased(),
            None => false,
        }
    }

    let is_word_final = case_ignorable_then_cased(from[..i].chars().rev())
        && !case_ignorable_then_cased(from[i + const { 'Σ'.len_utf8() }..].chars());
    if is_word_final { 'ς' } else { 'σ' }
}

from[..i] is the whole point. It is a backwards look at everything before the letter, which is exactly the information a chunked fast path throws away.

It shipped in 1.80.0 (tagged 2024-07-25), so the wrong answer was in stable Rust from 1.63.0 (2022-08-11) through 1.79.x — seventeen releases, just under two years.

Why two years of tests did not see it

to_lowercase had sigma tests from the day the rule was added in 2015. They are still there, and the fix added one more line to them:

assert_eq!("ΑΣ".to_lowercase(), "ας");     // one of about twenty already there
assert_eq!("ΑΣ'Α".to_lowercase(), "ασ'α");
// https://github.com/rust-lang/rust/issues/124714
assert_eq!("abcdefghijklmnopΣ".to_lowercase(), "abcdefghijklmnopς");   // added by the fix

Look at what the old ones have in common — the kata below measures it. A test for a Greek rule is naturally written in Greek, so the longest ASCII prefix in the entire set is two characters, and those two are the apostrophes in "''Σ". The fast path needs sixteen bytes before it converts anything at all, so it stopped at byte 0 or 1 or 2 in every one of those tests and handed the Unicode loop a string that still had the letters in it. The tests could not reach the code that broke.

This library's own reference page has the same hole: str::to_lowercase demonstrates the rule with "ΣΣ" and "ΟΔΟΣ", and both would have passed happily on Rust 1.70.

The general form is worth carrying around. A fast path is a second implementation, and it is selected by a property of the input that has nothing to do with the property under test. Here the selector is "how much leading ASCII", the subject is "Greek casing", and no amount of thinking about Greek gets you to the crossing. What gets you there is sweeping the selector: the kata does 1..=64 leading letters and reports which lengths are wrong.

What both have in common

• Neither is unsafe, and neither would be caught by anything that looks for undefined behaviour. Miri, ASan, the borrow checker and cargo audit are all silent on a function that returns a wrong bool or a wrong char.
• Both were found by sweeping, not by testing. All 28 substrings of one word; every ASCII prefix length in a range. In both cases the reporter's script is the regression test, and in both cases it is four lines long.
• Both are in the optimization. A linear scan cannot have the periodic-needle bug. An unchunked to_lowercase cannot have the sigma bug. The naive versions are slower and neither of them was ever wrong.

What is not here

The soundness bugs. Three CVEs where safe code could break the UTF-8 invariant — and, as it happens, all three of those are also fast paths. See When the UTF-8 invariant broke.

The Turkish dotted I. "I".to_lowercase() is "i", which is wrong in Turkish, where it should be ı. That is not a bug: str::to_lowercase implements the language-independent mappings on purpose and says so, because it has no locale to consult and guessing one would be worse. Final sigma is in this page precisely because it is the one contextual rule that needs no locale — so std owes you it, and for two years it did not deliver.

If you are coming from another language

Python. "ΑΣ".lower() is 'ας' — CPython implements Final_Sigma too, in unicodeobject.c, with the same backwards look at the preceding cased character. It also has an ASCII fast path, and the same crossing exists there; it is one of the reasons the CPython test suite tests casing with a leading ASCII run. str.find uses a mix of Crochemore–Perrin two-way and Boyer–Moore–Horspool, so the periodicity question is live there as well.

JavaScript. 'ΑΣ'.toLowerCase() is 'ας' here too — checked on the Node on this machine, alongside the Python above. String.prototype.includes is specified by its result rather than by an algorithm, so a substring bug in JavaScript is an engine bug and never a specification one. The difference that does bite: JS strings are UTF-16, so "the end of a word" is asked over code units and a needle can be half a character.

ABAP. Worth measuring on your own system rather than taking from a page: lowercase a Greek word ending in Σ with to_lower( ) and see which sigma comes back. Whichever it is, it is a property of the runtime and not something you can ask for per call — so find out before you compare that string against one Rust or Python produced, because ς and σ are different characters and a WHERE clause will not forgive the difference.

Practice

Write the test that would have caught each of them. Not a case — a property, swept over the input dimension the optimization keys on.

1. Every substring of a word is findable in that word. Run it over a list stacked with periodic words: banana, aaaa, abcabcabc, mississippi. Report the substrings that fail rather than asserting, so a failure tells you which one.
2. A Σ at the end of a word lowercases to ς, however long the word is. Sweep the ASCII prefix from 1 to 64. Then explain the one length that legitimately gives σ and must not be in your sweep.
3. Pick a third fast path and break it the same way. to_uppercase on ß is a good one, because the output is longer than the input — try it after a leading ASCII run and say what a chunked converter would have to get right that a naive one does not.

Finish by computing the ASCII prefix length of each of std's pre-2024 sigma tests, and writing one sentence about what that number explains.

Solution

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

//! Kata: write the test that would have caught each bug, then run it against
//! the compiler you have.

/// Every substring of a word must be findable in it. Periodic words are the
/// ones that broke the 2014 searcher, so the list is stacked with them.
fn unfindable_substrings(word: &str) -> Vec<&str> {
    let mut missing = Vec::new();
    for i in 0..word.len() {
        for j in i + 1..=word.len() {
            if word.is_char_boundary(i) && word.is_char_boundary(j) {
                let part = &word[i..j];
                if !word.contains(part) || word.find(part).is_none() {
                    missing.push(part);
                }
            }
        }
    }
    missing
}

/// A sigma at the end of a word lowercases to ς however long the word is.
fn ascii_runs_ending_in_plain_sigma(max: usize) -> Vec<usize> {
    (1..=max)
        .filter(|k| !("a".repeat(*k) + "\u{3a3}").to_lowercase().ends_with('\u{3c2}'))
        .collect()
}

/// The other thing a "convert the ASCII prefix in chunks" path can get wrong:
/// a character whose case mapping is longer than the character.
fn ascii_runs_losing_the_sharp_s(max: usize) -> Vec<usize> {
    (0..=max)
        .filter(|k| {
            let word = "a".repeat(*k) + "\u{df}";
            word.to_uppercase() != "A".repeat(*k) + "SS"
        })
        .collect()
}

fn main() {
    println!("property 1 — every substring of a word is found in it");
    for word in ["bananas", "aaaa", "abcabcabc", "mississippi", "zażółć"] {
        println!("  {word:>12}  unfindable {:?}", unfindable_substrings(word));
    }

    println!();
    println!("property 2 — Σ at the end of a word lowercases to ς");
    println!("  k in 1..=64, wrong  {:?}", ascii_runs_ending_in_plain_sigma(64));

    println!();
    println!("property 3 — ß uppercases to SS whatever precedes it");
    println!("  k in 0..=64, wrong  {:?}", ascii_runs_losing_the_sharp_s(64));

    println!();
    println!("what std's own sigma tests looked like before 2024:");
    let mut longest = 0;
    for word in ["\u{391}\u{3a3}", "\u{391}'\u{3a3}", "\u{391}\u{3a3}'\u{391}", "'\u{3a3}", "''\u{3a3}", "\u{3a3}"] {
        let ascii_prefix = word.bytes().take_while(u8::is_ascii).count();
        longest = longest.max(ascii_prefix);
        println!("  {word:>6}  ->  {:<8}  ascii prefix {ascii_prefix}", word.to_lowercase());
    }
    println!("  longest ASCII prefix in the whole set  {longest}");
}

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

property 1 — every substring of a word is found in it
       bananas  unfindable []
          aaaa  unfindable []
     abcabcabc  unfindable []
   mississippi  unfindable []
        zażółć  unfindable []

property 2 — Σ at the end of a word lowercases to ς
  k in 1..=64, wrong  []

property 3 — ß uppercases to SS whatever precedes it
  k in 0..=64, wrong  []

what std's own sigma tests looked like before 2024:
      ΑΣ  ->  ας        ascii prefix 0
     Α'Σ  ->  α'ς       ascii prefix 0
    ΑΣ'Α  ->  ασ'α      ascii prefix 0
      'Σ  ->  'σ        ascii prefix 1
     ''Σ  ->  ''σ       ascii prefix 2
       Σ  ->  σ         ascii prefix 0
  longest ASCII prefix in the whole set  2

See also

• STRINGS.md — the map: every string lesson, in reading order
• When the UTF-8 invariant broke — the other half: three CVEs, same fast-path shape, memory instead of meaning
• str::to_lowercase — the method's own reference page, sigma rule included
• Searching without splitting — contains, find and the Pattern trait they share
• Comparing and sorting text — the other place where "the same string" is a question, not a fact
• Meet the char — why a char method cannot answer a contextual question at all
• Confusables and scripts ↗ — Greek letters as an attack rather than a casing problem

Po polsku

Obie pomyłki z tej strony to złe odpowiedzi, a nie awarie: program działał, nic się nie wywróciło, tylko wynik był nieprawdziwy. Żaden borrow checker, żaden unsafe, żaden Miri tego nie widzi — i to jest cała różnica między bezpieczeństwem pamięci a poprawnością, o którą w Ruście łatwo się potknąć, bo kompilator przyzwyczaja do tego, że pilnuje wszystkiego.

Wspólny mianownik jest jeszcze ciekawszy: oba błędy siedziały w optymalizacji. Szybka ścieżka to druga implementacja tej samej funkcji, wybierana przez cechę wejścia, która z testowaną własnością nie ma nic wspólnego — tutaj „ile znaków ASCII na początku” wobec „grecka reguła wielkości liter”. Testy std na sigmę istniały od 2015 roku i wszystkie były napisane po grecku, czyli miały zerowy przedrostek ASCII, więc do zepsutego kodu nie sięgały. Polski akcent jest ten sam co zwykle: "ŻÓŁW".to_lowercase() działa, ale "ŻÓŁW" też nie ma przedrostka ASCII — a "cd-ŻÓŁW" już ma, i to właśnie taki wariant trzeba zmieść (sweep), żeby cokolwiek udowodnić.

Szukaj po polsku: poprawność a bezpieczeństwo pamięci · testy własnościowe (property-based testing) · sigma końcowa w grece · algorytm Two-Way wyszukiwania wzorca · szybka ścieżka ASCII