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

Фазинг

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

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

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

Проверяем:

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

Фазинг

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 и для коммитов.

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

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

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

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

Фазинг

Фазинг

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

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

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

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

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

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

Примеры

Фазеры в ClickHouse

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

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

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

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

Libfuzzer

Libfuzzer

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

Thread Fuzzer

Thread Fuzzer

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

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

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

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

Фазеры не в ClickHouse

Выводы

.

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