博客 / 工程

ClickHouse 模糊测试

Alexander Kuzmenkov

2021 年 3 月 11 日 - 分钟阅读

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

SQL DBMS 的自然测试形式是创建描述测试用例的 SQL 脚本，并记录其参考结果。为了进行测试，我们运行脚本并检查结果是否与参考结果匹配。这在许多 SQL DBMS 中使用，并且是您期望为任何 ClickHouse 功能或修复编写的默认测试类型。目前，我们仅 SQL 测试就有 7.3 万行代码，达到了 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 测试，并且我们在进行模糊测试时会格外注意新测试，为它们生成更多排列。即使测试的覆盖率不足，模糊测试器也有很大机会找到缺少的极端情况。因此，当我们看到特定拉取请求的所有不同配置中的模糊测试器运行都失败时，这几乎总是意味着它引入了一个新错误。在开发需要新语法的特性时，为其添加模糊测试支持也很有帮助。我在开发的早期阶段为窗口函数做了这件事，它帮助我找到了几个错误。

使模糊测试对我们真正有效的一个主要因素是，我们的代码中有很多断言和其他程序逻辑检查。对于仅用于调试的检查，我们使用来自 <cassert> 的普通 assert 宏。对于即使在发布模式下也需要的检查，我们使用带有特殊代码 LOGICAL_ERROR 的异常，该代码表示内部程序错误。我们做了一些工作来确保这些错误与错误的用户操作引起的错误区分开来。为随机生成的查询报告的用户错误是正常的（例如，它引用了一些不存在的列），但是当我们看到内部程序错误时，我们知道这绝对是一个错误，与断言相同。当然，即使没有断言，您也可以获得操作系统提供的一些内存错误检查（段错误）。向程序添加运行时检查的另一种方法是使用某种消毒器。我们已经在 clang 的 Address、Memory、UndefinedBehavior 和 Thread 消毒器下运行了我们的大部分测试。将它们与此模糊测试器结合使用也被证明非常有效。

要亲眼看看模糊测试器是如何工作的，您只需要普通的 ClickHouse 客户端。启动 clickhouse-client --query-fuzzer-runs=100，输入任何查询，然后享受客户端发疯并运行一百个随机查询。当前会话中的所有查询都将成为模糊测试的表达式来源，因此请尝试输入几个不同的查询以获得更有趣的结果。注意不要在生产环境中执行此操作！当您进行此实验时，您很快就会注意到模糊测试器倾向于生成运行时间很长的查询。这就是为什么对于 CI 模糊测试器运行，我们必须配置服务器以使用相应的服务器设置限制查询执行时间、内存使用量等。在那之后，我们遇到了一个搞笑的情况：模糊测试器通过生成 SET max_execution_time = 0 查询，然后生成一个永无止境的查询并失败，从而弄清楚了如何删除限制。值得庆幸的是，我们能够通过使用设置约束来击败它的聪明才智。

我们讨论的基于 AST 的模糊测试器只是我们在 ClickHouse 中拥有的众多模糊测试器之一。Alexey Milovidov 做了一个演讲（俄语，幻灯片在此处），探讨了我们拥有的所有模糊测试器。另一个有趣的最新发展是将透视查询合成技术应用于 ClickHouse，该技术在 SQLancer 中实现。作者将很快就此发表演讲，敬请期待。

2021-03-11 Alexander Kuzmenkov

分享这篇文章