Fuzzing: Practical approaches in ClickHouse

Fuzzing

— is testing with random data or conditions..

First we start with a program, we give it a bunch of garbage as input

Or forced to work in garbage conditions.

What we check:

— the program does not crash;
— does not go into loop, and run for too long;
— does not eat up too much memory;
— internal invariants are not violated;
— sanitizers do not find errors.

Fuzzing

xkcd.com

— A «gold mine» for finding bugs
(where fuzzing is not yet used).

Do you have a parser, converter, compression algorithm?
And you don't use fuzzing yet???

Types of Fuzzing

There are so many ways to do Fuzzing.

The more, the better :)

Types of Fuzzing

Unstructured:
— testing with random bytes;

Structured:
— testing by a random
structurally correct input.

Types of Fuzzing

— random data without feedback (stupid);

— coverage guided (smart);

— with a logical solvers (very smart).

Types of Fuzzing

Black box:
— we test the finished binary or service without changes;

With instrumentation:
— rebuilding the program for testing purpose.

Types of Fuzzing

By input data:
— we give the program a bunch of garbage as input;

By settings and environment:
— turn on random feature flags;
— change the system time (libfaketime) and timezones;
— Chaos Monkey;

By the way the program is executed::
— check the random order of execution of threads;
— we cause hangups of servers in a distributed environment.

Types of Fuzzing

Logical:
— check that the behavior on random data is correct;
— comparisons with another implementation; comparisons with the standard; checking invariants.

Physical:
— the result of the program is not important;
— we check that the program does not crash, sanitizers do not throw error, etc.

Examples

Example of successful manual fuzzing:
— kids cracked lock screen in Linux Mint:
Linux Mint fixes screensaver bypass discovered by two kids.

Example: Linux kernel, Syzcaller tool:
— Found more than 3000 bugs, 1056 pending fixes:
https://syzkaller.appspot.com/upstream.

Example: Chromium, ClusterFuzz tool, over 20,000 bugs!

An example where fuzzing would help a lot:
— iPhone crash when displaying
a combination of characters from the Telugu language: జ్ఞ‌ా

Fuzzing in ClickHouse

The more fuzzing, the better!

Some of them are dumb and primitive (ad-hoc fuzzer).

«It doesn’t matter what the fuzzer looks like, the main thing is that it catches bugs»
— Deng Xiaoping.

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

SQL fuzzer by Oleg Alekseenkov

$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 fuzzer by Oleg Alekseenkov

Perl script that generates SQL queries
with random expressions.

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

What did it find?

— lack of checking for boundaries in the H3 library.

Stress Test by Oleg Alekseenkov

Runs all ClickHouse tests in parallel,
in random order, but does not check their result.

Tests interfere with each other:
they create and delete identical tables, etc.

We launch 5 options: with Debug, ASan, MSan, TSan, UBSan.

We check that:
— the server does not fall;
— no deadlocks (hanging requests);
— the server can successfully restart after the test is completed;

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

Stress Test by Oleg Alekseenkov

What does it find?

— bugs in RocksDB:
facebook/rocksdb#7711 — race condition;
facebook/rocksdb#7821 — use after free;
facebook/rocksdb#7778 — misc.

— race conditions in NuRaft, rdkafka, AMQP-CPP...

— incredible bug in simdjson: simdjson/simdjson#169.

— race condition in boost? ClickHouse-Extras/boost#8

— bug in LLVM libunwind https://bugs.llvm.org/show_bug.cgi?id=48186

And of course, there are many potential and real bugs in ClickHouse,
most of them before the release.

Libfuzzer

Added to ClickHouse by Eldar Zaitov.

libfuzzer — coverage guided fuzzer available from 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();
        ...

It is recommended to enclose a «corpus» of examples of valid data.

Libfuzzer

What does it find?

Buffer overrun in data decompression:
https://github.com/ClickHouse/ClickHouse/pull/8404

Exponential backtracking in the parser:

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 by Alexey Milovidov

Not to be confused with Thread Sanitizer.

Race conditions are reproduced in
a specific thread order.

How to test as many different random execution orders as possible?

— We need to switch streams as often as possible
at random times.

But how to do that?

Thread Fuzzer by Alexey Milovidov

1. Set the signal on the timer: setitimer.

2. Put hooks on pthread_mutex_lock, pthread_mutex_unlock functions.

In the handler, we toss a coin and do:

1. sched_yield.

2. sleep for a random time.

3. sched_setaffinity on a random CPU.

Thread Fuzzer by Alexey Milovidov

Works great with Thread Sanitizer and Stress Test!

And he also finds a bunch of flaky tests
(race not in the program but in tests).

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

AST Fuzzer by Alexander Kuzmenkov

In clickhouse-client we take requests from regression tests.
From parsed requests, we take pieces of AST (Abstract Syntax Tree).
We substitute them randomly in other queries.
Mutating string literals...

We execute... the result is not important, we check that the server has not crashed.

Five options to test with: 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 by Alexander Kuzmenkov

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

Discovery of the year! Over 200 issues:

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

Not only bugs: edge cases, UBSan triggers...

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

Errored in UBSan, ASan tests... Somewhere it turns out NaN -> checks for array boundaries -> buffer overflow.

AST Fuzzer by Alexander Kuzmenkov

Bonus: Aggressive phasing of new tests in pull requests.

Tests new code for edge cases,
even when the author didn't think about it.

SQLancer — logical SQL phaser

Developed by Manuel Rigger at ETH Zurich.

Added to ClickHouse by Ilya Yatsishin.

Generates random valid SQL queries and data.

Verifies that the result is the same as a reference unoptimized query engine written according to the SQL standard.

Example:

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;

Insufficient column type check in WHERE, result in segfault.

Fuzzers not in ClickHouse

zzuf — mutates data when working with files and the network.

fuzzgrind — dynamic translation + solver for finding data that passes conditions in machine code (project abandoned).

AFL — Instrumentation builds are recommended, similar to libfuzzer, but run outside of the process.

Hongfuzz — supports hardware counters for coverage.

Radamsa — is not a fuzzer, but a separate data mutator.

Service security scanners are also phasers, for example: sqlmap.

Conclusion

You have to use Fuzzing. Everywhere, as much as possible!

We use fuzzer in CI — for pull request and for commit.

Need more fuzzer.

Bugs shall not pass!

Fuzzing: Practical approaches in ClickHouse

What is this about?

Fuzzing

Fuzzing

Types of Fuzzing

Types of Fuzzing

Types of Fuzzing

Types of Fuzzing

Types of Fuzzing

Types of Fuzzing

Examples

Fuzzing in ClickHouse

SQL fuzzer by Oleg Alekseenkov

SQL fuzzer by Oleg Alekseenkov

Stress Test by Oleg Alekseenkov

Stress Test by Oleg Alekseenkov

Libfuzzer

Libfuzzer

Thread Fuzzer by Alexey Milovidov

Thread Fuzzer by Alexey Milovidov

Thread Fuzzer by Alexey Milovidov

AST Fuzzer by Alexander Kuzmenkov

AST Fuzzer by Alexander Kuzmenkov

AST Fuzzer by Alexander Kuzmenkov

SQLancer — logical SQL phaser

Fuzzers not in ClickHouse

Conclusion

.

Fuzzing: Practical approaches in
ClickHouse