Фазинг: практические кейсы в ClickHouse

Фазинг: практические кейсы
в ClickHouse

Про что доклад?

Не только про C++.

По большей части не про C++.

Фазинг

— это тестирование случайными данными или условиями.

Есть программа, подаём ей на вход кучу мусора.

Или заставляем работать в мусорных условиях.

Проверяем:

— программа не падает;
— не зацикливается, не выполняется слишком долго;
— не съедает слишком много памяти;
— внутренние инварианты не нарушаются;
— санитайзеры не находят ошибки.

Фазинг


xkcd.com

«золотая жила» для поиска багов
(там, где фазинг ещё не используют).

У вас парсер, конвертер, алгоритм сжатия?
И вы ещё не используете фазинг???

Какой бывает фазинг?

Есть очень много способов делать фазинг.

Чем больше, тем лучше :)

Какой бывает фазинг?

Неструктурированный:
— тестирование случайными байтами;

Структурированный:
— тестирование случайным
  структурно-корректным входом.

Какой бывает фазинг?

— случайные данные без обратной связи (тупой);

— coverage guided (умный);

— с логическим выводом (совсем умный).

Какой бывает фазинг?

Black box:
— тестируем готовый бинарник или сервис без изменений;

С инструментированием:
— пересобираем программу для тестирования.

Какой бывает фазинг?

По входным данным:
— подаём программе на вход кучу мусора;

По настройкам и окружению:
— включаем случайные фиче-флаги;
— меняем системное время (libfaketime) и таймзоны;
— Chaos Monkey;

По способу выполнения программы:
— проверяем случайный порядок выполнения потоков;
— вызываем зависания серверов в распределённой среде.

Какой бывает фазинг?

Логический:
— проверяем, что поведение на случайных данных корректно;
— путём сравнения с другой реализацией; сравнения с эталоном; проверки инвариантов.

Физический:
— результат работы программы не важен;
— проверяем, что программа не падает, санитайзеры не ругаются и т. п.

Примеры

Пример успешного фазинга вручную:
— дети взломали lock screen в Linux Mint:
Linux Mint fixes screensaver bypass discovered by two kids.

Пример: ядро Linux, инструмент Syzcaller:
— нашёл больше 3000 багов, 1056 ждут исправления:
https://syzkaller.appspot.com/upstream.

Пример: Chromium, инструмент ClusterFuzz, больше 20 000 багов!

Пример где фазинг очень помог бы:
— креш iPhone при отображении
комбинации символов из письменности Телугу: జ్ఞ‌ా

Фазеры в ClickHouse

Чем больше фазеров, тем лучше!

Некоторые из них тупые и примитивные (ad-hoc fuzzer).

«Не важно, как выглядит фазер, главное чтобы он ловил баги»
— Deng Xiaoping.

http://en.naipo.com/Portals/0/web_en/Knowledge_Center/Feature/IPNE_170224_0701.htm

SQL фазер Олега Алексеенкова

$expression_cast = { 'CAST' => sub { my ($state) = @_; '(CAST((' . one_of($state, $expression_cast) . ') AS ' . one_of($state, $type_cast) . '))' }, 'SELECT' => sub { my ($state) = @_; list_of( $state, {max => 2}, [sub { '( ' . one_of($state, $query_select) . ' ) AS ' . rand_word() }, sub { '( ' . one_of($state, $query_select) . ' ) ' }] ); }, 'number' => sub { my ($state) = @_; return rand_pick(['', '-']) . rand_word(8, 0 .. 9) . rand_pick(['', '.' . rand_word(6, 0 .. 9)]) }, 'string' => sub { my ($state) = @_; return q{'} . rand_word(8, map { $_ ~~ q{'} ? '\\' . $_ : $_ } map {chr} 32 .. 127) . q{'}; }, '[]' => '[]', '[x]' => sub { my ($state) = @_; return '[' . one_of($state, $expression) . ']' }, 'function()' => sub { my ($state) = @_; return one_of($state, $functions) . '(' . list_of($state, {min => 0, max => 3}, $expression) . ')' }, "'\\0'" => "'\\0'", "''" => "''", 'NULL' => 'NULL', };

https://github.com/ClickHouse/ClickHouse/pull/3442

SQL фазер Олега Алексеенкова

Скрипт на Perl, генерирующий SQL запросы
со случайными выражениями.

https://github.com/ClickHouse/ClickHouse/pull/3442

Что находит?

— отсутствие проверки на границы в библиотеке H3.

Stress Test Олега Алексеенкова

Запускает все тесты ClickHouse параллельно,
в случайном порядке, но не проверяет их результат.

Тесты мешают друг-другу:
создают и удаляют одинаковые таблицы и т. п.

Запускаем 5 вариантов: с Debug, ASan, MSan, TSan, UBSan.

Проверяем, что:
— сервер не падает;
— нет дедлоков (зависших запросов);
— сервер может успешно перезапуститься после завершения теста;

https://github.com/ClickHouse/ClickHouse/pull/3057
https://github.com/ClickHouse/ClickHouse/pull/3438

Stress Test Олега Алексеенкова

Что находит?

— баги в RocksDB:
facebook/rocksdb#7711 — race condition;
facebook/rocksdb#7821 — use after free;
facebook/rocksdb#7778 — misc.

— рейсы в NuRaft, rdkafka, AMQP-CPP...

— невероятный баг в simdjson: simdjson/simdjson#169.

— рейс в boost? ClickHouse-Extras/boost#8

— баг в LLVM libunwind! https://bugs.llvm.org/show_bug.cgi?id=48186

И конечно много потенциальных и настоящих багов в ClickHouse,
большинство ещё до релиза.

Libfuzzer

Добавил в ClickHouse Эльдар Заитов.

libfuzzer — coverage guided fuzzer, доступный в LLVM/clang.

-fsanitize=fuzzer,...
-fprofile-instr-generate -fcoverage-mapping
extern "C" int LLVMFuzzerTestOneInput(const uint8_t * data, size_t size) { DB::Lexer lexer(data, data + size); while (true) { DB::Token token = lexer.nextToken(); ...


Рекомендуется подложить «корпус» примеров валидных данных.

Libfuzzer

Что находит?

Buffer overrun в разжатии данных:
https://github.com/ClickHouse/ClickHouse/pull/8404

Экспоненциальный бэктрекинг в парсере:

SELECT fo,22222?LUTAY(SELECT(NOT CAUTAY(SELECT(NOT CAST(NOTT(NOT CAST(NOT NOT LEfT(NOT coARRAYlumnsFLuTAY(SELECT(NO0?LUTAY(SELECT(NOT CAUTAY(SELECT(NOT CAST(NOTT(NOT CAST(NOT NOT LEfT(NOT coARRAYlumnsFLuTAY(SELECT(NOTAYTAY(SELECT(NOTAYEFAULT(fo,22222?LUTAY(%SELECT(NOT CAST(NOT NOTAYTAY(SELECT(NOTAYEFAULT(fo,22222?LUTAY(SELECT(NOT CAST(NOT NOT (NOe)))))))))))))))))))))))))))))))))


https://github.com/ClickHouse/ClickHouse/issues/20158

Thread Fuzzer Алексея Миловидова

Не путать с Thread Sanitizer.

Race conditions воспроизводятся при
специфическом порядке работы потоков.

Как проверить как можно больше
разных случайных порядков выполнения?

— Надо переключать потоки как можно чаще
в случайные моменты времени.

Но как это сделать?

Thread Fuzzer

1. Ставим сигнал по таймеру: setitimer.

2. Ставим хуки на функции pthread_mutex_lock, pthread_mutex_unlock.

В обработчике подкидываем монетку и делаем:

1. sched_yield.

2. sleep на случайное время.

3. sched_setaffinity на случайный CPU.

Thread Fuzzer

Прекрасно сочетается с Thread Sanitizer и Stress Test!

А ещё находит кучу флапающих тестов
(рейс кондишены не в программе, а в тестах).

https://github.com/ClickHouse/ClickHouse/blob/master/
src/Common/ThreadFuzzer.h, cpp

AST Fuzzer Александра Кузьменкова

В clickhouse-client берём запросы из тестов.
Из разобранных запросов берём кусочки AST.
Подставляем их случайным образом в другие запросы.
Мутируем строковые литералы...

Выполняем... результат не важен, проверяем что сервер не упал.

Пять вариантов: Debug, ASan, MSan, TSan, UBSan.

SELECT 0.00009999999747378752 * NULL, 1 * -2, 1024, sum(toUInt64(255, 1048576 * 65537, NULL * 100.0000991821289)) FROM (SELECT 1 * 1025, intDiv(number, 1.) AS k, toUInt64('0.0000065536', 255, toUInt64(7 * NULL), NULL * 0.) FROM numbers(2 * 9223372036854775807, toUInt64(10 * 255)) GROUP BY k)

AST Fuzzer Александра Кузьменкова

https://github.com/ClickHouse/ClickHouse/pull/12111

Открытие года! Больше 200 issues:

https://github.com/ClickHouse/ClickHouse/issues?q=is%3Aissue+label%3Afuzz

Не только баги: краевые случаи, срабатывания UBSan...

SELECT bar((greatCircleAngle(100, -1, number, number) - number) * 2, -9223372036854775808, 1023, 100) FROM numbers(1048575);


Ругается UBSan, ASan. Где-то получается NaN -> проходят проверки на границы массива -> buffer overflow.

AST Fuzzer Александра Кузьменкова

Бонус: агрессивный фазинг новых тестов в pull requests.

Тестирует новый код на краевые случаи,
даже когда автор об этом не подумал.

SQLancer — логический SQL фазер

Разработан Manuel Rigger в ETH Zurich.

Добавил в ClickHouse Илья Яцишин.

Генерирует случайные корректные SQL запросы и данные.

Проверяет, что результат совпадает с эталонным не оптимизированным движком запросов, написанным в соответствии со стандартом SQL.

Пример:

SELECT t0.c2, t0.c1, t0.c0 FROM t0 WHERE t0.c0 ORDER BY ((t0.c2)>=(t0.c1)), (((- (((t0.c0)>(t0.c0))))) IS NULL) FORMAT TabSeparatedWithNamesAndTypes;


Недостаточная проверка типа столбца в WHERE, segfault.

Фазеры не в ClickHouse

zzuf — мутирует данные при работе с файлами и сетью.

fuzzgrind — динамическая трансляция + solver для поиска данных, проходящих условия в машинном коде (проект заброшен).

AFL — рекомендуется сборка с инструментированием аналогично libfuzzer, но работает снаружи процесса.

Hongfuzz — поддерживает hardware counters для coverage.

Radamsa — не фазер, а отдельный мутатор данных.

Сканеры безопасности сервисов — тоже фазеры, пример: sqlmap.

Выводы

Надо использовать фазинг. Какой угодно и побольше.

Мы используем фазеры в CI — для pull requests и для коммитов.

Нужно больше фазеров.

Баги не пройдут!

.