[Перевод] Самодельный фаззер против Rust-крейта regex: искал один баг, нашёл два
Находят ли генеративные (рандомизированные) тесты баги заметно лучше, чем юнит-тесты на примерах? На lobste.rs по этому поводу идёт интересное обсуждение. Один из доводов в пользу юнит-тестов, если пересказать своими словами, звучит так:
Мой универсальный фаззер не смог найти вот этот хитрый баг в Rust-крейте
regex.
Мне показалось, что генеративное тестирование как раз должно вытряхивать таких зверей, поэтому я написал небольшой фаззер сам. И он действительно нашёл в той версии regex другой баг, а потом и тот, за которым я охотился. В последней версии ничего не нашлось. Хочу описать процесс: это хороший учебный пример того, как подступаться к такой задаче.
Сразу оговорюсь: как аргумент это очень слабо. Я точно знаю, какой баг ищу, и даже знаю, что фаззеры способны его найти. Главная цель здесь — научить приёмам, а насколько они эффективны, судите сами. И всё же, по-моему, второй найденный баг подход отчасти подтверждает.
Ещё хочу подчеркнуть, что писать фаззеры под уже известные баги — вовсе не праздная забава. Я считаю, что генеративное тестирование очень мощное относительно своей цены, но всегда остаётся вопрос, достаточно ли тщателен конкретный тест. А он никогда не бывает достаточно тщательным: в другом месте вы обязательно найдёте ещё баги (поэтому так важны эшелонированная защита и защитные механизмы во время выполнения). И если какой-то вредитель проскочил мимо ваших фаззеров, первым делом считайте это багом в фаззере и меняйте его так, чтобы он находил и этот баг, и родственные. Только после этого разрешается добавить исправление и юнит-тест!
Баг
Для регулярного выражения ".abb|b" и входа "zabb" старая версия крейта regex возвращала первым совпадением b. Это неверно: совпадает вся строка zabb.
use regex;
fn main() {
let r = regex::Regex::new(".abb|b").unwrap();
let m = r.find("zabb").unwrap();
// Fails with regex-automata=0.4.15:
assert_eq!(m.as_str(), "zabb")
}
Как найти этот баг или что-то похожее на него?
Движки регулярных выражений — одна из самых удобных целей для генеративного тестирования: это чистые алгоритмы. Большие системы редко состоят только из алгоритма, но внутри компонентов интересных систем алгоритмы повсюду, так что это знание прикладное.
Самый важный приём тестирования алгоритмов, с большим отрывом, — сверка с заведомо правильным ответом, с оракулом. Реализуйте алгоритм и за O(N log N), и за O(N^2), и сравнивайте ответы.
Справедливости ради, в исходном комментарии говорилось, что фаззер автора не нашёл проблему именно потому, что у него не было оракула. Но если вы проектируете надёжную систему, обеспечить ей оракул — часть вашей работы! Одним из первых шагов в нашем Jepsen-тестировании TigerBeetle было вынести внутренние временные метки в API, чтобы Jepsen было проще находить баги (TigerBeetle проектируется вместе со своим внутренним симулятором VOPR, у которого естественным образом есть доступ к временным меткам и ко всему остальному). А для движка регулярных выражений придумать оракул должно быть несложно: обычно за единым фасадом в них и так живут несколько специализированных реализаций, и их можно сверять друг с другом.
Но случай с regex ещё проще, и поэтому он отлично подходит как учебный пример: есть крейт regex_lite с тем же API.
Отсюда план: сгенерировать регулярное выражение и входной текст и проверить, что regex и regex_lite дают одинаковые ответы.
Генерируем строку
Начну с кода, который генерирует случайную строку: он проще, но в нём уже есть пара нетривиальных идей. Для начала нужен генератор случайных чисел:
use fastrand::Rng;
Есть техники и поизощрённее, которые дают минимизацию тест-кейсов, исчерпывающий перебор или исследование по покрытию, но суть в том, что даже скромный ГПСЧ (генератор псевдослучайных чисел) бьёт беспощадно, если правильно им распорядиться.
Когда только начинаешь заниматься рандомизированным тестированием, тянет сгенерировать что-нибудь большое, нет, ОГРОМНОЕ! Уж на 5 ГиБ входных данных regex точно подавится? Обычно это неверный ход. Баги, как правило, сидят в маленьких, но хитрых примерах, которые сталкивают между собой несколько возможностей. Строка, где все символы одинаковые, скорее вызовет баг, чем совершенно случайная строка, где каждый символ уникален.
Поэтому по умолчанию я генерирую строки так. Сначала фиксирую алфавит допустимых символов. Удобный способ его получить — прогнать все юнит-тесты через sort | unique. Затем для каждой конкретной строки выбираю подмножество этого алфавита. Мне нужны строки, в которых встречаются все символы, но нужны и длинные строки только из a и b! Потом генерирую строку из выбранного подмножества, причём длину тоже выбираю случайно.
Чтобы фаззинг был эффективным, каждая итерация должна быть как можно быстрее, поэтому память я переиспользую между итерациями — это статическое выделение памяти в миниатюре:
use fastrand::Rng;
fn main() {
let mut rng = Rng::new();
// Re-use the same memory for all tests.
let mut text_alphabet: Vec<u8> = vec![];
let mut text: Vec<u8> = vec![];
for _ in 0..1_000_000 {
// It's unlikely that a counter example with
// 7 different letters exists, while there
// isn't one with just 6.
alphabet_swarm(&mut rng, b"abcdef", &mut text_alphabet);
let text =
gen_string(&mut rng, &text_alphabet, &mut text);
}
}
fn alphabet_swarm<'a>(
rng: &mut Rng,
all: &[u8],
pick: &'a mut Vec<u8>,
) {
pick.clear();
pick.extend(all);
rng.shuffle(pick);
let count = rng.usize(1..=pick.len());
pick.truncate(count);
}
fn gen_string<'a>(
rng: &mut Rng,
alphabet: &[u8],
result: &'a mut Vec<u8>,
) -> &'a str {
result.clear();
// Again, this is a short string.
// Longer failures are not likely.
let count = rng.usize(0..8);
for _ in 0..count {
result.push(alphabet[rng.usize(0..alphabet.len())]);
}
str::from_utf8(result).unwrap()
}
У этого двухшагового процесса (сначала алфавит, потом строка) есть удобная интерпретация. Чтобы сгенерировать строку, нужно распределение символов. Можно брать одно и то же распределение на все миллион итераций. Но есть простой способ всё оживить — сделать случайным само распределение. Идею «рандомизировать сами распределения» я отношу к swarm-тестированию.
Генерируем распределение для регулярных выражений
Применим те же трюки к генерации регулярного выражения:
выбираем подмножество задействованных возможностей regex;
случайно выбираем размер;
переиспользуем память.
Начнём с первого:
#[derive(Default, Debug)]
struct ReOptions {
alt: u16, // |
rep: u16, // *
any: u16, // .
lit: u16, // 'a'
sum: u16,
alphabet: Vec<u8>,
}
У регулярных выражений есть альтернатива r1|r2, повторение r*, любой символ . и литералы a. Вместо того чтобы просто включать или выключать каждую возможность, я назначаю ей вес от 0 до 100 — это чуть более общий подход. sum — сумма всех весов. Чтобы выбрать возможность случайно, генерируем число в диапазоне 0..sum и смотрим, в какой отрезок оно попало.
В чём-то посерьёзнее я бы завёл явные типы для вероятностей и распределений, но для небольшой задачи вполне хватает просто двузначного числа.
Вот как я генерирую ReOptions, следя, чтобы у литералов вес всегда был ненулевым, и заодно выбирая для них алфавит:
impl ReOptions {
fn swarm(&mut self, rng: &mut Rng, alphabet_full: &[u8]) {
// We _still_ want to enable a few features at a time.
self.alt = if rng.bool() { 0 } else { rng.u16(0..100) };
self.rep = if rng.bool() { 0 } else { rng.u16(0..100) };
self.any = if rng.bool() { 0 } else { rng.u16(0..100) };
self.lit = rng.u16(1..100);
self.sum = self.alt + self.rep + self.any + self.lit;
assert!(self.sum > 0);
alphabet_swarm(rng, alphabet_full, &mut self.alphabet);
}
}
Генерируем регулярное выражение
Теперь можно генерировать само регулярное выражение. Удобнее всего делать это рекурсивно. Чтобы обойтись без выделений памяти, через все вызовы передаётся выходной буфер. Чтобы управлять длиной выражения, туда же передаётся параметр size, и рекурсивные вызовы, которые ветвятся, делят size между потомками:
fn gen_re(
rng: &mut Rng,
options: &ReOptions,
result: &mut Vec<u8>,
) {
result.clear();
let size = rng.u8(0..8);
gen_re_rec(rng, options, result, size);
}
fn gen_re_rec(
rng: &mut Rng,
options: &ReOptions,
result: &mut Vec<u8>,
size: u8,
) {
if size == 0 {
return; // Base case, empty regex.
}
// Pick one of the features, according to weights.
let mut p = rng.u16(0..options.sum);
if p < options.alt {
// Alternation distributes the size
// among the two children.
let size_left = rng.u8(0..=size - 1);
let size_right = size - size_left - 1;
assert!(size == size_left + 1 + size_right);
result.push(b'(');
gen_re_rec(rng, options, result, size_left);
result.extend(b")|(");
gen_re_rec(rng, options, result, size_right);
result.push(b')');
return;
}
p -= options.alt;
if p < options.rep {
result.push(b'(');
gen_re_rec(rng, options, result, size - 1);
result.extend(b")*");
return;
}
p -= options.rep;
if p < options.any {
gen_re_rec(rng, options, result, size - 1);
result.push(b'.');
return;
}
p -= options.any;
if p < options.lit {
gen_re_rec(rng, options, result, size - 1);
let index = rng.usize(0..options.alphabet.len());
let lit = options.alphabet[index];
result.push(lit);
return;
}
unreachable!();
}
Цикл поиска
Компиляция регулярных выражений довольно медленная, поэтому разумно прогонять много строк на одной паре скомпилированных выражений. Получается такой код:
fn main() {
let mut rng = Rng::new();
let mut options = ReOptions::default();
let mut text_alphabet: Vec<u8> = vec![];
let mut text: Vec<u8> = vec![];
let mut re: Vec<u8> = vec![];
let mut test_count: u32 = 0;
for _ in 0..1_000_000 {
options.swarm(&mut rng, b"abcdef");
alphabet_swarm(&mut rng, b"abcdefx", &mut text_alphabet);
gen_re(&mut rng, &options, &mut re);
let re = str::from_utf8(&re).unwrap();
let r1 = regex::Regex::new(re).unwrap();
let r2 = regex_lite::Regex::new(re).unwrap();
for _ in 0..1000 {
test_count += 1;
let text =
gen_string(&mut rng, &text_alphabet, &mut text);
let m1 = r1.find(text)
.map_or("not found", |it| it.as_str());
let m2 = r2.find(text)
.map_or("not found", |it| it.as_str());
if m1 != m2 {
eprintln!("err re={re} text={text} m1={m1} m2={m2}");
return;
}
if test_count % 500_000 == 0 {
eprintln!("ok re={re} text={text}");
}
}
}
}
Он находит примеры, похожие на пример из issue, — с общим суффиксом:
err re=(e)|(fee) text=xxfee
но и примеры несколько иного рода, без общего суффикса:
err re=(f..)*.d text=xfcbdd
Всё вместе:
use fastrand::Rng;
fn main() {
let mut rng = Rng::new();
let mut options = ReOptions::default();
let mut text_alphabet: Vec<u8> = vec![];
let mut text: Vec<u8> = vec![];
let mut re: Vec<u8> = vec![];
let mut test_count: u32 = 0;
for _ in 0..1_000_000 {
options.swarm(&mut rng, b"abcdef");
alphabet_swarm(&mut rng, b"abcdefx", &mut text_alphabet);
gen_re(&mut rng, &options, &mut re);
let re = str::from_utf8(&re).unwrap();
let r1 = regex::Regex::new(re).unwrap();
let r2 = regex_lite::Regex::new(re).unwrap();
for _ in 0..1000 {
test_count += 1;
let text =
gen_string(&mut rng, &text_alphabet, &mut text);
let m1 = r1.find(text)
.map_or("not found", |it| it.as_str());
let m2 = r2.find(text)
.map_or("not found", |it| it.as_str());
if m1 != m2 {
eprintln!("err re={re} text={text} m1={m1} m2={m2}");
return;
}
if test_count % 500_000 == 0 {
eprintln!("ok re={re} text={text}");
}
}
}
}
fn alphabet_swarm<'a>(
rng: &mut Rng,
all: &[u8],
pick: &'a mut Vec<u8>,
) {
pick.clear();
pick.extend(all);
rng.shuffle(pick);
let count = rng.usize(1..=pick.len());
pick.truncate(count);
}
fn gen_string<'a>(
rng: &mut Rng,
alphabet: &[u8],
result: &'a mut Vec<u8>,
) -> &'a str {
result.clear();
let count = rng.usize(0..8);
for _ in 0..count {
result.push(alphabet[rng.usize(0..alphabet.len())]);
}
str::from_utf8(result).unwrap()
}
#[derive(Default, Debug)]
struct ReOptions {
alt: u16, // |
rep: u16, // *
any: u16, // .
lit: u16, // 'a'
sum: u16,
alphabet: Vec<u8>,
}
impl ReOptions {
fn swarm(&mut self, rng: &mut Rng, alphabet_full: &[u8]) {
self.alt = if rng.bool() { 0 } else { rng.u16(0..100) };
self.rep = if rng.bool() { 0 } else { rng.u16(0..100) };
self.any = if rng.bool() { 0 } else { rng.u16(0..100) };
self.lit = rng.u16(1..100);
self.sum = self.alt + self.rep + self.any + self.lit;
assert!(self.sum > 0);
alphabet_swarm(rng, alphabet_full, &mut self.alphabet);
}
}
fn gen_re(
rng: &mut Rng,
options: &ReOptions,
result: &mut Vec<u8>,
) {
result.clear();
let size = rng.u8(0..8);
gen_re_rec(rng, options, result, size);
}
fn gen_re_rec(
rng: &mut Rng,
options: &ReOptions,
result: &mut Vec<u8>,
size: u8,
) {
if size == 0 {
return; // Base case, empty regex.
}
// Pick one of the features, according to weights.
let mut p = rng.u16(0..options.sum);
if p < options.alt {
// Alternation distributes the size
// among the two children.
let size_left = rng.u8(0..=size - 1);
let size_right = size - size_left - 1;
assert!(size == size_left + 1 + size_right);
result.push(b'(');
gen_re_rec(rng, options, result, size_left);
result.extend(b")|(");
gen_re_rec(rng, options, result, size_right);
result.push(b')');
return;
}
p -= options.alt;
if p < options.rep {
result.push(b'(');
gen_re_rec(rng, options, result, size - 1);
result.extend(b")*");
return;
}
p -= options.rep;
if p < options.any {
gen_re_rec(rng, options, result, size - 1);
result.push(b'.');
return;
}
p -= options.any;
if p < options.lit {
gen_re_rec(rng, options, result, size - 1);
let index = rng.usize(0..options.alphabet.len());
let lit = options.alphabet[index];
result.push(lit);
return;
}
unreachable!();
}
Код целиком: https://github.com/matklad/regex-fuzz
Что из этого вынести
Фаззинг со сверкой по оракулу работает, и это сильный довод в пользу того, чтобы оракул завести!
Ищите маленькие хитрые примеры, а не большие однородные.
Настоящие фаззеры — это здорово, но если вы кое-что понимаете в задаче, даже xoroshiro может натворить дел.
Тестировать чёрный ящик — хорошо, но проектировать систему вместе с её тестовой обвязкой — точка опоры (заведите оракул!).
Это не rocket science: чтобы применять эти идеи, не нужна степень PhD по Haskell.
KioskNews shows a cleaned-up reading view extracted from the publisher’s page — the original always lives on their site, not ours.