ClickHouse 模糊测试

测试是软件开发中的一大难题：永远不会有足够的测试。对于数据库管理系统来说，情况尤其如此，它的任务是解释一种在分布式方式下对系统管理的持久状态起作用的查询语言。这三个功能中的每一个都难以单独测试，当您将它们组合在一起时，情况会变得更糟。作为 ClickHouse 开发人员，我们从经验中了解这一点。尽管我们在持续集成系统中例行公事地执行大量各种自动测试，但新错误和回归正在不断出现。我们一直在寻找改进测试覆盖率的方法，本文将介绍我们最近在这方面的开发成果——基于 AST 的查询模糊器。

针对 SQL DBMS 的一种自然测试形式是创建一个描述测试用例的 SQL 脚本，并记录其参考结果。要进行测试，我们运行脚本并检查结果是否与参考结果匹配。这在许多 SQL DBMS 中都有使用，也是您在为任何 ClickHouse 功能或修复编写测试时所期望的默认类型。目前，我们仅有 73k 行 SQL 测试，达到了 76% 的代码覆盖率。

这种测试形式，即开发人员编写一些简化的功能使用示例，有时被称为“基于示例的测试”。不幸的是，错误通常出现在各种边缘情况和功能交集处，而手动枚举所有这些情况并不实际。有一种技术可以自动化此过程，称为“属性测试”。它允许您编写更通用的测试，其形式为“对于所有符合这些规范的值，对它们执行某些操作的结果应符合此其他规范”。例如，这样的测试可以检查，如果您添加两个正数，则结果大于这两个数。但您并没有指定具体是哪些数字，只是这些属性。然后，属性测试系统会随机生成一些符合规范的特定数字示例，并检查结果是否也符合其规范。

据说属性测试非常有效，但需要开发人员投入一些精力和专业知识才能以特殊的方式编写测试。还有一种众所周知的测试技术，从某种意义上来说是属性测试的一种边缘情况，并且不需要开发人员花费太多时间。它被称为模糊测试。当您对程序进行模糊测试时，您会向它提供根据某种语法生成的随机输入，而您要检查的属性是您的程序是否正确终止（没有段错误、断言或其他类型的程序错误）。大多数情况下，用于模糊测试的输入语法很简单——例如，位翻转和加法，或者可能是一些字典。可能的输入空间非常大，因此为了在其中找到有趣的路径，模糊测试软件会记录被测程序在特定输入下采用的代码路径，并关注导致之前未见过的新的代码路径的输入。它还会采用一些技术来查找有趣的常数值，等等。总的来说，模糊测试允许您自动地在程序中查找许多有趣的边缘情况，而无需开发人员过多地参与。

使用位翻转来生成有效的 SQL 查询需要很长时间，因此有一些系统可以根据 SQL 语法生成查询，例如 SQLSmith。它们已成功用于查找数据库中的错误。对 ClickHouse 使用这样的系统将会很有趣，但需要一些前期工作来支持 ClickHouse SQL 语法和函数，这些语法和函数可能与标准不同。此外，这些系统不使用任何反馈，因此尽管它们比具有原始语法的系统要好得多，但它们仍然可能难以找到有趣的示例。但是我们已经有了一个大型的人工编写的有趣 SQL 查询语料库——它就在我们的回归测试中。也许我们可以将它们作为模糊测试的基础？我们尝试过这样做，结果发现这非常简单而且高效。

考虑回归测试中的某个 SQL 查询。解析后，很容易在执行之前对生成的 AST（抽象语法树，解析查询的内部表示）进行变异，以便在查询中引入随机更改。对于字符串和数组，我们进行随机修改，例如插入随机字符或将字符串加倍。对于数字，有一些众所周知的错误数字，例如 0、1、2 的幂和附近、整数限制、NaN。NaN 在查找错误方面特别有效，因为您通常可以在数字代码中有一些替代分支，但是对于 NaN，这两个分支同时成立（或不成立），因此会导致不良影响。

我们还可以做的另一件有趣的事情是更改函数的参数，或者更改 SELECT、ORDER BY 等中的表达式列表。当然，所有有趣的参数都可以从其他测试查询中获取。更改查询中使用的表也是如此。当模糊器在 CI 中运行时，它会以随机顺序运行来自所有 SQL 测试的查询，将它之前见过的某些查询部分混合到其中。此过程最终可以涵盖我们所有功能的所有可能排列。

模糊器的核心实现相对较小，由大约 700 行 C++ 代码组成。原型在几天内就制作出来了，但自然地，完善它并开始在 CI 中例行使用它需要更长的时间。它非常有效，已经让我们找到了 200 多个错误（请参阅 GitHub 上的标签 fuzz），其中一些是严重的逻辑错误甚至内存错误。当我们刚开始时，我们使用最简单的只读查询（例如 SELECT arrayReverseFill(x -> (x < 10), []) 或 SELECT geoDistance(0., 0., -inf, 1.)）就可以让服务器出现段错误或使其进入无限循环。当然，我忍不住用其中一些查询来让我们的 公共游乐场 崩溃，并很满意地看到服务器很快正确地重新启动。这些查询实际上是手动缩减的，通常模糊器会生成一些几乎无法理解的内容，例如

SELECT
    (val + 257,
      (((tuple(NULL), 10.000100135803223), tuple(-inf)), '-1', (NULL, '0.10', NULL), NULL),
      (val + 9223372036854775807) = (rval * 100),
      tuple(65535), tuple(NULL), NULL, NULL),
    *
FROM 
(
    SELECT dummy AS val
    FROM system.one
) AS s1
ANY LEFT JOIN 
(
    SELECT toLowCardinality(toNullable(dummy)) AS rval
    FROM system.one
) AS s2 ON (val + 100) = (rval * 7)

原则上，我们可以通过修改 AST 来添加自动测试用例缩减功能，与模糊测试类似。但这有点复杂，因为服务器在每次（恕我直言）成功失败的查询后都会崩溃，所以我们还没有实现它。

模糊测试发现的错误并非都重要，其中一些很无聊且无害，例如对越界参数的错误代码。我们仍然尝试修复所有错误，因为这让我们可以确保在正常操作下，模糊测试不会发现任何错误。这类似于通常对编译器警告和其他可选诊断所采取的方法——最好修复或禁用每一个案例，这样你就可以确定，如果一切正常，就不会有任何诊断，并且很容易发现新的问题。

在修复了大多数预先存在的错误后，这个模糊测试器在寻找新功能中的错误方面变得高效。引入新功能的拉取请求通常会添加一个 SQL 测试，我们在模糊测试时会格外注意新的测试，为它们生成更多排列组合。即使测试覆盖率不足，模糊测试器也有很大的机会找到遗漏的边缘案例。因此，当我们看到所有不同配置下的模糊测试运行对于某个特定的拉取请求都失败时，这几乎总是意味着它引入了新的错误。在开发需要新语法的功能时，为它添加模糊测试支持也很有帮助。我在窗口函数开发的早期阶段就做了这件事，它帮助我发现了一些错误。

使模糊测试对我们非常有效的一个主要因素是，我们在代码中有很多断言和其他程序逻辑检查。对于仅用于调试的检查，我们使用来自``的普通`assert`宏。对于即使在发布模式下也需要的检查，我们使用带有特殊代码`LOGICAL_ERROR`的异常，表示内部程序错误。我们做了一些工作来确保这些错误与由错误的用户操作引起的错误不同。为随机生成的查询报告的用户错误是正常的（例如，它引用了某些不存在的列），但是当我们看到内部程序错误时，我们就知道它肯定是一个错误，与断言一样。当然，即使没有断言，你也会从操作系统获得一些针对内存错误的检查（段错误）。另一种为程序添加运行时检查的方法是使用某种类型的消毒剂。我们已经在大多数测试中使用 clang 的地址、内存、未定义行为和线程消毒剂。将它们与这个模糊测试器结合使用也被证明非常有效。

要亲眼看看模糊测试器是如何工作的，你只需要普通的 ClickHouse 客户端。启动`clickhouse-client --query-fuzzer-runs=100`，输入任何查询，然后享受客户端疯狂地运行一百个随机查询。当前会话的所有查询都成为模糊测试表达式来源，所以尝试输入几个不同的查询以获得更有趣的结果。小心不要在生产环境中这样做！当你做这个实验时，你会很快发现模糊测试器倾向于生成运行时间很长的查询。这就是为什么对于 CI 模糊测试运行，我们必须配置服务器使用相应的服务器设置来限制查询执行时间、内存使用量等。之后我们遇到过一个滑稽的情况：模糊测试器找到了通过生成`SET max_execution_time = 0`查询来移除限制的方法，然后生成了一个永不结束的查询并失败了。谢天谢地，我们能够通过使用设置约束来战胜它的聪明才智。

我们讨论的基于 AST 的模糊测试器只是 ClickHouse 中众多模糊测试器中的一种。有演讲（俄语，幻灯片在这里）由 Alexey Milovidov 探索我们所有的模糊测试器。另一个有趣的最新发展是将枢轴查询合成技术应用到 ClickHouse，它在SQLancer中实现。作者将很快发表关于此的演讲，敬请关注。

2021-03-11 Alexander Kuzmenkov