Blog Website

AST-based Query Fuzzer in ClickHouse

ClickHouse

在软件开发中，测试是保证系统/程序能够正确、可靠、稳定运行的重要途径，并且是一项永无止境的工作。

对于数据库来说，其需要对输入的 SQL 查询语言进行解释执行，从而对持久化存储的数据进行计算和处理，并且执行过程通常是分布式的。对于上述每一项功能的正确性测试，都非常困难，而当三者结合到一块时，情况则更加复杂。

ClickHouse 如何进行测试

在 ClickHouse 的 ci 中，有许多种不同类型的测试，简要介绍其中包含的几种主要测试：

  • Unit tests：单元测试在 ClickHouse 中实际上并不常见，也不常用，只有在实现内部的一些核心模块时，会编写一些单元测试，大多数时候来说，都不需要写单元测试。
  • 回归测试：回归测试，在 ci 中叫做 functional test，这一类测试是 ClickHouse 保证功能正确的最主要的测试，也是日常在开发新特性，或者进行 BugFix 时通常需要编写的测试。这一类测试的编写非常简单，只需要编写 SQL 脚本来描述测试 case，然后记录脚本对应的 reference 输出，在进行测试时，会运行脚本检查输出是否和 reference 一致，这种测试方法在许多数据库中都有使用到。目前，在 ClickHouse 中，这一测试对应的 SQL 行数已经超过十万行，达到了很高的代码覆盖率。
  • Stress tests：压测，如名字所示。
  • Integration tests：集成测试，当需要测试的功能依赖于一些外部组件时，如 Kafka Engine 或者 S3/HDFS 相关功能，则需要编写 Integration test 来测试正确性。
  • Performance tests：性能测试，如名字所示。在快速迭代开发过程中，需要持续关注性能变化，防止性能回退。在提交性能优化相关的 PR 时，需要通过性能测试来验证优化的有效性。
  • AST fuzzer：模糊测试，在下文中会进行介绍。

Fuzzing Test

Fuzzing test，模糊测试，是一种自动化的软件测试方法，其通过生成一些未确定的、随机的数据，注入到程序中，进而监测程序的运行状态，比如是否发生 crash，或者触发 断言(assertion)失败、内存泄漏或 data race 等行为，从而找出程序中存在的 bug。

为什么需要 fuzzing test？在上文中提到，在开发一个新的特性时，需要编写对应的回归测试，这一类型的测试通常只是通过一些简单的示例来描述了该特性支持什么，不支持什么，即 example-based tests。然而，在实际情况中，bug 经常发生在的是一些开发过程中没有考虑到的 corner cases，或者是由于几个不同的特性结合产生的，我们无法枚举出所有可能的情况，即输入空间是巨大的。而在 fuzzing test 中，通过将一些按照特定语法规则随机生成的查询注入数据库中，就能够自动帮助我们找到许多有趣的 corner cases。

AST-based Query Fuzzer

当前，业内已有一些工具能够按照 SQL 语法来生成有效的查询，如 sqlsmith，已经在许多数据库中被运用。然而，ClickHouse 实现了一个基于递归下降的纯手写 Parser，同时不是标准的 SQL 语法，并且包含了大量丰富的函数，因此很难直接将此类工具运用到 ClickHouse 中。

在 ClickHouse 中，包含了大量人工编写的回归测试 SQL，当前已经超过 10 万行，是否能够基于这些 SQL 来进行 fuzzing 呢？对于这些回归测试中的任意一个 SQL，当其被解析之后，我们很容易在进行执行前，对其 AST（抽象语法树）表示进行一些随机的变换，从而生成一个新的查询，AST-based Query Fuzzer 正是基于这种方式实现的。

对 AST 的变换非常简单。例如，对于一个 String，可以随机将其置为空，或复制一遍，或者随机在某个位置插入一个 \0；对于整数或浮点数，可以随机变换为 0、INT_MAX 或 NaN 之类的 bad values，这类 bad values 通常是最容易导致出现 bug 的参数。

对于 SELECT 查询，可以随机添加或者删除一些 SELECT 表达式、ORDER BY 表达式，随机添加或删除过滤条件等，同时递归对 AST 的 children 节点进行 fuzzing，于是便生成了一个新的查询；对于 CREATE 建表语句，可以对 COLUMN 声明进行 fuzzing，例如将数据类型从非 Nullable 变成 Nullable，非低基数类型变成低基数类型，从而创建不同的表，用于后续查询的 fuzzing。

在运行 ci 时，所有 tests 中的全部查询会以任意的顺序运行，在 fuzzing 过程中会不断收集前面已经执行完的 SQL 的参数，因此在对后续的 SQL 进行 fuzzing 时能够与已经运行过的查询中出现的参数结合到一块，从而能够进一步对不同特性的随机结合进行测试。此外，对于 PR 中的新特性，ci 在 fuzzing 的过程中会对新添加的测试产生更多的输入，因此即使手工编写的回归测试不够完备，也有很大可能在 fuzzing 过程中找到回归测试中没有覆盖到的 corner cases。

那么，如何在 fuzzing 过程中检查出现的错误和 bug 呢？主要依赖于以下几种方式：

  • 当程序因为内存问题导致 crash 退出(由操作系统控制)，则说明出现了相应的 bug，这是最直接的方式；
  • ci 会分别在 Debug 和 Release 模式下运行。在 Debug 模式下，通过 assert 来进行判断；而在 Release 模式下，如果抛出了 ErrorCode 为 LOGICAL_ERROR 的异常，表示程序内部出现了逻辑错误，在 ClickHouse 中，将这类异常和其他比如由于用户输出了错误的 SQL 导致的异常区分开来，出现 LOGICAL_ERROR 的异常则表明程序中存在 bug；
  • 此外，ClickHouse 也使用了多种 clang 的 sanitizer 在运行时对程序进行检查，包括 AddressSanitizer、MemorySanitizer、UndefinedBehaviorSanitizer 和 ThreadSanitizer。这些 sanitizer 和 fuzzer 结合到一块，找到了许多相应的 bug。

AST Fuzzer 的实现位于 ClickHouse 代码库 src/Client/QueryFuzzer.h 和 src/Client/QueryFuzzer.cpp， 总共仅有 1000 多行代码，可以说是“短小精悍”。自从 2021 年推出 AST Fuzzer 以来，已经发现并修复了大量的 bug。

示例

如果想通过 clickhouse-client 对 SQL 进行 fuzzing，只需要在运行时添加参数 query-fuzzer-runs，该参数表示对输入的 SQL 进行多少次 fuzzing，例如，以如下参数运行时，

1
clickhouse-client --query-fuzzer-runs = 300

对于输入的每一个SQL，会进行 300 次 fuzzing 并执行。

我们以 ClickHouse Star Schema Benchmark 中的 Q1.1 为例进行 fuzzing，看看会生成什么样的 SQL，原始 SQL 如下：

1
2
3
SELECT sum(LO_EXTENDEDPRICE * LO_DISCOUNT) AS revenue
FROM lineorder_flat
WHERE toYear(LO_ORDERDATE) = 1993 AND LO_DISCOUNT BETWEEN 1 AND 3 AND LO_QUANTITY < 25;

在进行 fuzzing 后，SQL 变成了如下形式：

1
2
3
4
5
6
7
8
9
SELECT sum(LO_EXTENDEDPRICE * LO_DISCOUNT) AS revenue
FROM lineorder_flat
PREWHERE (LO_DISCOUNT >= 2147483647) AND NULL AND (LO_DISCOUNT <= 1.1754943508222875e-38)
WHERE LO_QUANTITY < 7
GROUP BY
    GROUPING SETS (
        (toYear(LO_ORDERDATE) = '9223372036854775806'),
        ((LO_DISCOUNT >= NULL) AND (LO_QUANTITY < 10)),
        ((LO_DISCOUNT >= 7) AND (toYear(LO_ORDERDATE) = 3.4028234663852886e38) AND (LO_QUANTITY < 0)))

可以看到，在 fuzzing 之后，生成了更加复杂的随机的 SQL。事实上，上文提到，fuzzing 过程中会不断收集前面已经运行过的 SQL 的参数，所以，在对后续的 SQL 进行 fuzzing 过程中，能够使用到前面运行过的 SQL 的参数，因此能够将不同 SQL、不同特性结合到一块进行 fuzzing。

后记

前一阵子，在修复一个 EXPLAIN PIPELINE 相关的 bug 时，Alexey 提醒我顺便检查一下目前 AST Fuzzer 是否会对 EXPLAIN 查询进行 fuzzing，如果没有，需要添加一下，否则后续类似的 bug 还会不断出现。

之后，我去查看 QueryFuzzer 的代码，发现确实没有针对 EXPLAIN 查询的 fuzzing，于是分别添加了对 EXPLAIN 查询的fuzzing 和随机将 SELECT 查询 fuzzing 成 EXPLAIN 查询两个特性。

在这两个 PRs 合并进 master 分支之后，Fuzzer 开始工作了：

过去几天里，得益于新加入的功能，已经发现了多个相关的 bug，
其中一些与新的 Analyzer 相关：

这一方面证明了 Fuzzer 的有效性，同时也验证了文章开头的话：测试是一项永无止境的工作。

Recents

Archives

Categories

Tags