Detecting Logical Bugs of DBMS with Coverage-based Guidance

Basic Information:

Title: Detecting Logical Bugs of DBMS with Coverage-based Guidance (使用基于覆盖率的引导检测DBMS的逻辑错误)
Authors: Yu Liang, Song Liu, Hong Hu
Affiliation: Pennsylvania State University (宾夕法尼亚州立大学)
Keywords: DBMS, logical bugs, coverage-based guidance, validity-oriented mutations, oracles (DBMS, 逻辑错误, 基于覆盖率的引导, 有效性导向的变异, 神谕)
URLs: Paper, GitHub Code

论文简要 :

结构脉络大概如下：

引言：介绍了数据库管理系统（DBMS）的重要性和逻辑错误的危害，回顾了现有的检测逻辑错误的技术，如Oracle和覆盖率引导的模糊测试，提出了将两者结合的动机和挑战，概述了本文的主要贡献和创新点。
背景与挑战：举例说明了一个SQLite的逻辑错误，介绍了Oracle的原理和种类，分析了覆盖率引导的模糊测试的优势和局限，指出了生成有效SQL查询和支持多种Oracle的难题。
设计：提出了两个解决方案，一是有效性导向的查询生成，包括协作突变、专用解析、基于上下文的IR实例化和非确定性消除等策略，以提高查询的语法和语义正确性；二是通用接口的Oracle开发，包括预处理、添加输出、转换和比较等API，以简化Oracle的实现和集成。
实现：介绍了SQLRight的原型系统，基于Squirrel和SQLancer，支持四种Oracle，分别是NoREC, TLP, Index和Rowid，并针对不同DBMS定制解析器。还介绍了一些实现细节，如内存高效突变、错误定位和查询最小化等。
评估：在SQLite, MySQL和PostgreSQL三个DBMS上评估了SQLRight的效果，回答了四个问题：SQLRight能否检测到真实世界的逻辑错误？SQLRight能否比现有工具找到更多错误？覆盖率引导如何指导测试？查询有效性如何帮助检测错误？结果显示SQLRight在60天内发现了18个逻辑错误，超过了SQLancer和Squirrel+oracle，并且覆盖率引导和查询有效性都对发现逻辑错误有积极作用。
相关工作：总结了相关领域的研究进展，包括DBMS测试、覆盖率引导的模糊测试、Oracle设计等，并分析了本文与它们的区别和联系。
结论与未来工作：总结了本文的主要贡献和创新点，展望了未来可能的改进方向，如支持更多DBMS、开发更多Oracle、提高查询多样性等。

摘要：

这篇论文的作者提出了一种新的方法来检测数据库管理系统（DBMS）的逻辑错误。他们结合了基于覆盖率的引导、面向有效性的突变和预言机来检测DBMS系统中的逻辑错误。他们首先设计了一套通用的API，以便开发人员可以轻松地将模糊测试工具移植到DBMS测试中，并为现有的模糊测试工具编写新的预言机。然后，他们提供了面向有效性的突变，以生成高质量的查询语句，以便发现更多的逻辑错误。他们的原型系统SQLRight在性能上超越了那些只依赖预言机或代码覆盖率的现有工具。总的来说，SQLRight在两个经过充分测试的DBMS（SQLite和MySQL）中检测到了18个逻辑错误。所有的错误都已经得到确认，其中14个已经被修复。

模糊测试，是一种自动化软件测试方法，通过向系统注入非法、畸形或非预期的输入，以揭示软件缺陷和漏洞。
覆盖引导（coverage-guided），“Coverage-guided” 是一种软件测试方法，它是为了帮助发现程序中的错误或漏洞而设计的。通俗来说，就好像你在地图上规划一条路线，然后用GPS 导航来引导你。在软件测试中，“Coverage-guided” 就像是一种导航系统，它帮助测试人员或工具找到程序中尚未测试到的部分，以确保尽可能多地覆盖代码。这个方法通过追踪程序执行时经过的代码路径来工作。如果测试覆盖率不够，就会有可能错过一些潜在的问题。“Coverage-guided” 测试会不断地尝试各种输入，以尽可能多地覆盖程序中的不同代码路径。当测试发现新的代码路径或分支时，它会将这些信息反馈给测试人员或工具，以便进一步测试这些路径，从而提高软件的质量和稳定性。
面向有效性的突变（Efficiency-oriented Mutation）这是一种方法，用于生成高质量的查询语句，以便更有效地测试DBMS系统。在面向有效性的突变中，测试人员或测试工具会对现有的测试输入进行变异，以生成新的测试用例。这些变异的目标是确保测试输入仍然具有有效性，即输入仍然是有效的输入。有效性在这里通常指的是输入是否符合程序的预期输入格式和约束条件。如果生成的测试输入无效，那么它们不太可能用于有效测试。
预言（Oracles），是一种用于检测数据库管理系统（DBMS）逻辑错误的技术。逻辑错误是指DBMS返回了不正确的结果，而不是崩溃或断言失败。Oracles的核心思想是构造一些功能等价的查询，也就是说，对于同一个数据库，这些查询应该返回相同的结果。如果DBMS对不同的查询返回了不一致的结果，那么就说明存在一个逻辑错误。文章中提到了四种Oracles，分别是NoREC, TLP, Index和Rowid，它们都有各自的转换和比较方法。Oracles可以与覆盖率引导的模糊测试相结合，提高检测逻辑错误的效率和效果。具体包括：
- NoREC：这种Oracle通过将WHERE子句中的条件移动到SELECT表达式中，来生成语义等价的查询。这样可以避免一些优化对原始查询的影响，比如索引和视图。如果两个查询的结果行数不同，就说明可能有逻辑错误。
- TLP：这种Oracle通过将WHERE子句中的一个条件x分解为三个子查询：x IS TRUE, x IS FALSE, 和 x IS NULL。然后将三个子查询的结果合并起来，与原始查询的结果进行比较。如果不一致，就说明可能有逻辑错误。
- Index：这种Oracle通过在数据库中插入或删除不同的索引来生成语义等价的查询。索引可以加速查询的执行，但不应该影响查询的结果。如果有索引和无索引的查询返回了不同的结果，就说明可能有逻辑错误。
- Rowid：建表的时候without rowid

INTRODUCTION:

背景:

DBMS在数据密集型程序中被广泛使用，任何DBMS中的缺陷都会影响大量的用户。
尽管已经付出了很多努力来测试DBMS系统，但大多数都专注于找出导致程序意外终止的崩溃和断言失败。
对于不使程序崩溃的逻辑错误，需要一个”oracle”来确定每次执行是否产生了正确的结果。
由于各种语言方言和特性，构建一个oracle既费时又容易出错。

数据库管理系统(dbms)广泛用于数据密集型程序，帮助数十亿设备托管数万亿数据库[23,51,54 - 57]。dbms中的任何错误都会影响大量用户。尽管在测试DBMS系统上花费了很多努力[10,58,70,71]，但大多数都集中在寻找最终导致执行意外终止的崩溃和断言失败上。它们无法检测导致DBMS返回意外结果的逻辑错误，比如泄漏额外的行。由于逻辑错误通常不会使程序崩溃，因此我们需要一个oracle来确定每次执行是否产生正确的结果。然而，由于各种语言方言和特点，构建oracle非常耗时且容易出错[49]。

相关工作:

模糊测试：

基于生成（model-based generation）的方法 SQLSmith

SQLSmith [2] 是目前使用较广的基于生成的 DBMS 模糊测试工具。它基于抽象语法树（Abstract Syntax Tree）来生成语法正确的查询语句。与其他的黑盒模糊测试工具一样，因为没有反馈信息，SQLSmith 会依次遍历 SQL 语句的输入空间。由于许多的 SQL 语句在 DBMS 中是由一套代码流程来处理，因此在探索程序状态空间上，这种方法是十分低效的。此外，这种方法也较难产生符合语义正确的输入。

基于变异(random mutation)的方法 AFL

而基于变异的方法在近年来飞速发展，以 AFL 为代表的工具以代码覆盖率作为反馈，可以有效的探索程序的状态空间。但是 AFL 的变异策略对于结构化的输入效果并不好，很难变异出合法的 SQL 语句。文章中的实验显示，AFL 在 24 小时变异生成的两千万条 SQL 查询语句中，只有 30% 通过了语法检查，并且最终只有 4% 是语义正确的。

Squirrel 的工作就是将上述的两种方法的优势进行结合，即将基于 AST 的变异方法引入到具有反馈驱动的 AFL 中，并且提出了基于依赖图的查询实例化（instantiation）方法，尽可能的使变异出来的语句通过语义检查。总的来看，Squirrel 的每次执行都从一个空的数据库开始，一次输入一组 SQL 语句（通常会包含创建表、插入数据、查询等语句）。在变异前，Squirrel 会剥离这些 SQL 语句中语义信息（例如列名、表名、整型数值）。变异后，Squirrel 会经过一个被称为 “实例化” 的阶段，再来填充这些新的 SQL 语句中的语义信息。最后，输入到 DBMS 中执行，并监控执行结果，执行完毕后会清空数据库。

对于每组输入的 SQL 语句，Squirrel 会首先将其转换为 AST，然后将 AST 转换为文中所谓的中间表示（Intermediate Representation）。但本质上来说，这个 IR 就是二叉树形式的 AST。其中每个 IR 是这个二叉树上的一个节点，保存着这个节点的左子节点和右子节点，以及该节点的类型。由于 AST 中的节点可能有超过两个子节点，因此转化为二叉树后，需要创建一些 “虚空节点” 来进行连接，这些虚空节点的类型即为 Unknown。

Squirrel的IR图：

SQLancer（基于Oracle的逻辑错误检测的工作）：

例如，Rigger等人通过将SQL查询转换为语义等价的形式来构造几个通用的oracle。一个DBMS可以用不同的代码路径处理这些查询，但最终结果应该是相同的。任何不一致都表明存在潜在的逻辑错误。SQLancer是实现这些oracle的工具，它已经成功地发现了许多逻辑错误[30,42]。然而，SQLancer依赖于基于规则的生成器来合成原始查询，这可能会限制其探索程序状态的能力。具体来说，它基于特定DBMS的语法和底层数据库的模式为WHERE和JOIN子句创建表达式。考虑到巨大的查询空间，它可能会在类似的查询上投入大量的时间和精力，而这些查询无法检查不同的程序代码。

局限性:

SQLancer依赖于基于规则的生成器来合成初始查询，可能限制了其探索程序状态的能力。
虽然模糊测试成功发现了与内存相关的错误，但没有研究尝试将覆盖率导向应用于逻辑错误检测。

大多数的测试都在寻找最终导致执行意外终止的崩溃和断言失败上，对于逻辑错误关注较少

将SQL查询转换为语义等价的形式来构造几个通用的oracle，能够成功的发现逻辑错误，但是普适性、鲁棒性很差

覆盖率引导的程序测试或模糊测试已被用于测试广泛的程序，但并没有应用于逻辑错误检测

主要的问题来源于生成有效的SQL查询。由于我们需要比较DBMS执行的结果，所生成的查询应该通过语法和语义检查，并成功产生有意义的输出。现有的模糊器可以合成一些能够触发断言失败和崩溃的查询，但其中许多并不完全有效，因此不能用于查找逻辑错误。为了解决这个问题，作者提出了“针对有效性的变异”策略，其定义了一套策略以提高生成查询的有效性。首先，他们设计了一种自动的方法来转换每个DBMS的SQL解析器，以达到模糊的目的。由于许多DBMS使用自己的SQL方言，统一的解析器可能会生成很多不兼容的查询。因此，他们为每个DBMS提供了一个查询解析器。他们的第二个努力是构建一个基于上下文的实例化算法，该算法强制确保SQL元素之间的准确依赖关系。此外，他们还考虑了oracle的需求来产生更有用的查询，并消除了查询中的非确定性行为。

另一个问题是模糊器和DBMS预言机（oracle）之间缺乏统一的接口。大多数模糊器仅依赖操作系统或各种清理器来检测错误，而检测逻辑错误需要生成适当的SQL语句并检查执行结果。为了填补这一空白，作者设计了一套表达性强的API来简化DBMS预言机的实现。这些API将模糊逻辑和预言机逻辑分离，开发人员可以专注于模糊或预言机的一个领域，从而更容易地应用现有的方法来检测逻辑错误。

克服局限性的方法:

将覆盖率反馈机制引入到检测逻辑错误之中

本文旨在了解基于覆盖率的指导在逻辑缺陷检测方面的好处，特别是在DBMS系统中。该研究揭示了采用当前基于突变的模糊测试器来发现逻辑错误面临的若干挑战。主要的问题来自生成有效的SQL查询。因为我们需要比较DBMS执行的结果，所以生成的查询应该通过语法和语义检查，并成功地产生有意义的输出。现有的模糊器可以合成触发断言失败和崩溃的查询，但其中许多都不是完全有效的，因此不能用于查找逻辑错误。

为了解决这个问题，我们提出了面向有效性的变异，定义了一组策略来提高生成的查询的有效性。首先，我们设计了一种自动转换各个DBMS的SQL解析器以实现模糊测试的方法。目前，大多数模糊测试器使用一个解析器来处理不同的DBMS系统[10,71]。由于许多dbms使用自己的SQL语言来支持独特的[49]特性，统一的解析器可能会产生许多不兼容的查询。更糟糕的是，错误的查询可能会触发错误处理代码，并根据覆盖率指导进行优先级排序。因此，我们为每个DBMS提供一个查询解析器，以减少无效查询。我们的第二个努力是构建一个基于上下文的实例化算法，该算法强制执行SQL元素之间的准确依赖关系。例如，DROP TABLE X从当前数据库中删除表X。我们的方法将遵循语义，并从上下文中删除相应的表，以便它不会用于以下语句。我们还考虑了oracle产生更有用查询的需求。具体来说，我们允许oracle将必要的元素标记为不可变的。我们的协作式变异引擎将避免改变这些元素，同时随机更新其他元素。最后，消除查询中的不确定性行为，以避免不必要的误报。通过这些方法，有效地提高了查询的有效性。

这部分我感觉属于凑字数部分，看了源码，一个数据库一个接口，扩展也不易

另一个阻碍fuzzing检测逻辑错误的问题是fuzzer与DBMS oracle之间缺乏统一的接口。大多数模糊测试器只是简单地依赖于操作系统或各种清理程序来检测bug[28, 46, 47]，而检测逻辑错误需要生成适当的SQL语句并检查执行结果。为了弥补这一不足，我们设计了一套富有表现力的api来简化DBMS oracle的实现。我们的api解耦了模糊测试逻辑和oracle逻辑。开发人员可以专注于一个领域，无论是模糊测试还是oracle，从而轻松地应用现有的方法来检测逻辑缺陷。我们实现了一个SQLRight系统，它结合了基于覆盖率的指导、面向有效性的突变和oracle来检测DBMS系统的逻辑错误。SQLRight首先以协作方式修改现有查询。它插入一组oracle必需的语句，并应用面向有效性的变更来提高有效性。然后，它将查询发送给oracle，以创建功能等效的查询对应项。SQLRight将所有生成的查询提供给DBMS，并收集执行结果和覆盖率信息。然后，SQLRight调用oracle来比较不同查询的结果，以识别逻辑错误。最后，将提高覆盖率的查询插入到队列中，以备将来发生变化时使用。我们实现了四个oracle，包括之前工作[43,44]中提出的两个和本文提出的两个。

贡献:

研究了基于覆盖指导的模糊测试在DBMS系统中检测逻辑错误的有效性，确定了两个有用的因素:查询有效性和代码覆盖率。
实现了SQLRight，这是一个基于覆盖率的模糊测试器，用于检测dbms的逻辑错误。SQLRight提供通用api以简化oracle开发，并嵌入面向有效性的变更以提高查询质量。
在实际的DBMS系统上评估SQLRight，发现18个逻辑错误。单元测试展示了工具不同组件的贡献。我们在https: //github.com/psu-security-universe/sqlright上发布了SQLRight的源代码，以帮助增强DBMS系统的安全性和健壮性。

BACKGROUND:

An Example Logical Bug

这个错误首先是通过SQLRight工具检测出来的，并已被SQLite的开发者修复。
示例中，首先创建了一个只有一个INT类型的pid列的person表。接着插入了三行数据：一个1和两个10。接下来，创建了一个名为idx的唯一部分索引，只维护pid值为1的行的记录。因此，只有第一行会连接到idx。最后一个SELECT语句请求pid值为10的行，并使用DISTINCT关键字来去除重复的结果。根据表中的内容，结果应该是一行10。但是，SQLite产生了两行10 10，违反了DISTINCT的要求。
这个问题是由于SELECT的错误优化引起的。当WHERE中的所有列都连接到某些唯一索引时，SQLite会将DISTINCT关键字视为不必要的，并在查询处理过程中简单地忽略它。但是，它忘记了部分索引的情况，只有部分行是连接的。为了修复这个bug，SQLite检查索引类型，并只将优化应用于完整索引的情况。
安全影响：这个逻辑错误将重复的数据行视为唯一的。根据具体的使用情况，它可能导致各种安全后果。例如，如果查询故意使用DISTINCT来隐藏匹配行的数量以保护隐私，那么这个bug会泄露数量信息。如果查询用于向用户分发随机密码，它可能会将同一个密码发送给多个不同的用户。由于SQLite在公众中被广泛使用，例如在35亿部智能手机上，因此这个重复删除bug可能会带来严重的功能和安全后果。

Oracles for Logical Bug Detection

预言（Oracles），是一种用于检测数据库管理系统（DBMS）逻辑错误的技术。逻辑错误是指DBMS返回了不正确的结果，而不是崩溃或断言失败。Oracles的核心思想是构造一些功能等价的查询，也就是说，对于同一个数据库，这些查询应该返回相同的结果。如果DBMS对不同的查询返回了不一致的结果，那么就说明存在一个逻辑错误。文章中提到了四种Oracles，分别是NoREC, TLP, Index和Rowid，它们都有各自的转换和比较方法。Oracles可以与覆盖率引导的模糊测试相结合，提高检测逻辑错误的效率和效果。具体包括：

NoREC：这种Oracle通过将WHERE子句中的条件移动到SELECT表达式中，来生成语义等价的查询。这样可以避免一些优化对原始查询的影响，比如索引和视图。如果两个查询的结果行数不同，就说明可能有逻辑错误。
TLP：这种Oracle通过将WHERE子句中的一个条件x分解为三个子查询：x IS TRUE, x IS FALSE, 和 x IS NULL。然后将三个子查询的结果合并起来，与原始查询的结果进行比较。如果不一致，就说明可能有逻辑错误。
Index：这种Oracle通过在数据库中插入或删除不同的索引来生成语义等价的查询。索引可以加速查询的执行，但不应该影响查询的结果。如果有索引和无索引的查询返回了不同的结果，就说明可能有逻辑错误。
Rowid：建表的时候without rowid

用于检查上面sql的逻辑错误

Coverage-guided Testing

基于覆盖率的测试（也称为模糊测试或fuzzing）及其在DBMS系统中的应用。

模糊测试概述：模糊测试已被广泛应用于测试大量程序，成功地发现了数千个错误。现代的模糊测试工具（fuzzers）利用代码覆盖率来指导输入的选择和变异。
模糊测试的工作流：
- 给定一个程序输入，模糊测试工具首先随机更新其内容以生成一组新的输入。
- 新输入被输入到程序并监控执行。
- 如果程序崩溃或报告断言失败，工具将此输入视为潜在错误的证明概念（PoC）。
- 对于没有触发崩溃的输入，工具会检查执行是否达到了新的代码路径。如果是，它会将输入加入队列。否则，它将丢弃输入并从队列中选择下一个输入进行另一轮的模糊测试。
模糊测试的应用范围：模糊测试已被用于测试各种程序，包括操作系统、编译器、网络浏览器、文档阅读器和智能合约。
模糊测试在DBMS中的应用：最近的工作也将基于覆盖率的模糊测试转移到DBMS系统上。文中特别提到了名为“Squirrel”的研究工作，其目的是检测DBMS系统中的崩溃和断言失败。
Squirrel的工作机制：
- Squirrel以一组SQL查询作为模糊测试的种子。
- 它首先将查询转化为中间表示（IR），这包含了很多结构信息。
- Squirrel采用三种变异方法（节点插入、删除和替换）来修改查询的IR。
- 对于每一个新生成的IR，Squirrel构建不同操作数（如表和列）之间的数据依赖图并使用随机生成的字符串填充操作数。
- 最后，它将新的IR转回为查询，并将其输入到DBMS。
- Squirrel最后报告崩溃并为下一轮的模糊测试优先选择揭示代码的查询。
Squirrel的成功：Squirrel成功地从常用的DBMS系统（如SQLite）中发现了一系列的崩溃和断言失败。

Challenges of Fuzzing Logical Bugs

将覆盖率指导的模糊测试应用于数据库管理系统(DBMS)以查找逻辑错误的挑战：

之前的努力：尽我们所知，之前没有尝试将覆盖率指导的模糊测试应用于查找DBMS的逻辑错误。
主要挑战：
- 生成高质量的SQL查询：目前的模糊测试工具还不能生成高质量的SQL查询。即使使用了如语法保留变异和语义引导实例化的先进技术，例如在最近的Squirrel工作中，其对SQLite的有效性只有大约30%。对于其他DBMS系统，有效性甚至更低。虽然在测试DBMS崩溃和断言错误时可以容忍这样的低有效性，因为无效的查询仍然可能触发一些错误，但是用于寻找逻辑错误的工具不能使用任何无效的查询。这是因为DBMS不会产生任何有意义的结果，因此无法使用预期输出(oracle)。
- 现有模糊测试工具的限制：当前的模糊测试工具主要依赖于操作系统和清理工具来检测错误（例如断言失败）。它们不能与DBMS预期输出(oracle)协作来检测逻辑错误。因此，我们需要重新设计模糊测试工具的架构，以支持各种DBMS预期输出。

Design of SQLRight

Overview

SQLRight的设计主要为了解决在数据库管理系统(DBMS)中测试逻辑错误的覆盖率指导的挑战。以下是其关键特点和工作流程：

解决方案：
- 有效性导向的生成：这提供了一套策略来生成有效、确定性的SQL查询。生成的查询在语法和语义上都具有高度的有效性，并且排除了可能导致误报的随机行为。
- 通用、全面的API：设计了一套API来支持开发新的DBMS预期输出(oracle)。这些API将预期输出(oracle)和模糊测试工具解耦，使用户更容易测试DBMS系统。它们还帮助DBMS开发者采用覆盖率指导来找到逻辑错误。
系统概览：
- SQLRight是第一个结合覆盖率指导、有效性导向的变异和预期输出(oracle)来查找DBMS系统逻辑错误的测试平台。
- 它接受目标程序（即DBMS）和一套样本查询（即SQL语句）作为输入，并产生逻辑错误报告。
- 首先，SQLRight将所有样本查询加入队列。在模糊测试的每一轮，它从队列中选择一个查询并应用变异来生成新查询。然后，它更新查询操作数，如表名和列名。
- SQLRight将新查询发送到DBMS并检查执行结果以识别意外的行为。如果新查询触发新代码，SQLRight将查询添加到队列中以供将来测试。
- 与传统的内存错误模糊测试工具（如Squirrel）不同，SQLRight与DBMS预期输出(oracle)合作，产生高质量的查询以识别逻辑错误。具体来说，对于查询变异，它调用预期输出API来更新特定于预期输出的SQL语句，为结果检查做准备。对于查询验证，它再次调用预期输出API将查询转换为语义上等价的变体。执行后，它依赖于预期输出(oracle)来决定查询是否触发逻辑错误。

简而言之，SQLRight通过结合特定的查询生成策略和与DBMS预期输出(oracle)的交互，为DBMS提供了一个逻辑错误检测平台。

图2展示了我们的工具SQLRight的概述，这是第一个结合了基于覆盖率的指导、面向有效性的突变和oracle来为DBMS系统查找逻辑错误的测试平台。它接受目标程序(即DBMS)和一组示例查询(即SQL语句)作为输入，并将生成逻辑错误报告。首先，SQLRight将所有示例查询添加到队列中。对于每一轮的模糊测试，它从队列中提取一个查询，并应用变异来生成新查询。然后，更新查询操作数，如表名和列名。之后，SQLRight将新查询发送给DBMS，并检查执行结果以识别意外行为。如果新查询触发新代码，SQLRight将查询添加到队列中以供将来测试。与传统的memorybug模糊器(如图1中的Squirrel)不同，SQLRight与DBMS oracle合作产生高质量的查询来识别逻辑bug。具体来说，对于mutation查询，它调用oracle api来更新oracle特定的SQL语句，为结果检查做准备。为了验证查询，它再次调用oracle api将查询转换为语义等价的变体。执行之后，它依赖于oracle来决定查询是否会触发逻辑错误。

和Squirrel的区别就在于下面的Oracle APIs,其他没区别

Validity-oriented Query Generation

SQLRight 需要高质量的 SQL 查询来压测不同的 DBMS 的各个方面。任何导致语法或语义错误的查询都不适用于寻找逻辑错误。遗憾的是，生成语义上正确的查询已被证明是 NP-hard 难题。近期的模糊测试工具利用基于类型的变异和语义引导的实例化来生成有效的查询，但其有效率只有约30%，这仍然不足以有效地测试 DBMS 系统。更糟糕的是，生成的大部分查询并不适用于检测逻辑错误。因此，我们提出了几种实用技术来提高查询的有效性。

3.1.1 Cooperative Mutation

SQLRight并行采用两种独立的变异策略来生成查询集的不同组件。如图3所示，它维护两个队列:select队列只包含select语句，用于生成产生输出的适当的select查询;普通队列承载其他语句，用于为测试准备数据库，如创建表和插入值。在模糊测试初始化期间，SQLRight扫描所有种子输入，将所有SELECT语句保存到SELECT队列，并将其他语句保存在普通队列中。对于每一轮模糊测试，SQLRight从普通队列中收集一组语句，并依赖普通变异引擎生成新查询。

然后，调用oracle的协作mutation来创建和添加多条SELECT语句。在组合之后，我们利用实例化来构建一个具体的查询集。

在合作变异期间，oracle 保留了对正确性测试有用的查询元素。例如，oracle NoREC 要求 SELECT 语句既有 FROM 子句又有 WHERE 子句。我们为 oracle 提供了接口，通知变异引擎不删除这些必要的节点，或者如果原始语句没有其中之一，则添加新的节点。图 4 说明了如何控制语句 SELECT COUNT(*) FROM v0 WHERE v1=0 的变异。给定查询的 IR，我们为三个节点（具体为 SELECT_statment、FROM 和 WHERE）添加属性，将它们标记为不可变。结果，对于 oracle NoREC 而言至关重要的组件得以保留。变异引擎仍然具有完全的灵活性，可以更新 from_clause 节点和 where_clause 节点来生成新的 SELECT 语句。基于 IR 的变异引擎支持在 from_clause 和 where_clause 中的各种模式和不同条件，从而提供与无约束的变异器 [71] 相当的丰富功能。

相当于做了约定，限制部分（阴影部分）不变，只改变其他部分。

3.1.2 Dedicated Parsing

为了提高语法正确性，SQLRight 针对每个 DBMS 定制了其变异引擎。大多数受欢迎的 DBMS 系统都有自己的定制 SQL 方言，这些方言之间只分享有限的功能。因此，针对公共功能的统一 SQL 语法只涵盖了 DBMS 代码的一小部分，并且无法找到 DBMS 唯一特性中的错误。相反，旨在支持所有功能的全包括性语法可能会导致许多无效的查询。

为了解决这个问题，SQLRight 设计了一个工具，可以自动将每个 DBMS 的解析器移植到 SQLRight 中。观察发现，大多数流行的 DBMS 系统使用 GNU Bison 来编译它们的解析器前端。因此，SQLRight 按照 Bison 定义的语法规则，将 DBMS 解析器前端转换为 SQLRight 的 IR。由于 Bison 格式有很好的文档记录，所以该工具可以轻松地为 SQLRight 移植不同的解析器。通过原始的 DBMS 解析器前端，SQLRight 可以支持每个 DBMS 的完整方言语法，并确保高度的语法正确性，以提高查询有效性。

Squirrel论文中在实现部分提到了用Bison解析AST，并将其转化成IR，篇幅较少，这一部分它拿出来大写特写。专用解析器就是将不同的Bison语法规则的Parser统一成IR。

Squirrel论文中的IR （看了代码，Select结构都是固定写死的，语义上的部分是有限的，无法扩展）：

3.1.3 Context-based IR Instantiation

该段落对比了先前的工作Squirrel和新工作SQLRight在处理SQL语句的数据依赖性时的不同方法。

Squirrel的限制：
- Squirrel识别所有SQL语句之间的数据依赖性，以帮助实例化查询操作数，如表名和列名。
- 它构建的依赖性图将多个SQL语句紧密地结合成一个静态图。
- 对于复杂的查询，它不能更新数据依赖性以反映动态的SQL上下文。它维持整个查询序列的静态数据依赖性，并不能自我调整以适应不同SQL语句之间不断变化的关系。
SQLRight的改进：
- 设计了一个基于上下文的IR实例化算法，该算法根据SQL上下文动态地更新数据依赖性，并为查询框架填入准确的具体值。
- 不是将多个SQL语句分组到一个依赖图中，SQLRight每次解决一个SQL语句。在处理多个SQL语句时，它只将必要的依赖信息保存到库中。
实例：
- 描述了SQLRight是如何利用上下文来实例化SQL IR的。
- 通过创建、插入、更改列名等语句的例子，展示了SQLRight如何动态更新上下文，从而准确地处理和生成SQL语句。
- 与此相反，Squirrel的原始方法无法捕获ALTER带来的动态变化，并可能在SELECT中错误地使用了已更改的列名。

总之，与Squirrel相比，SQLRight提供了一种更加动态和灵活的方法来处理SQL语句的数据依赖性，特别是在处理复杂的查询时。

Squirrel的原始方法是如何捕获依赖关系的?

Squirrel识别所有SQL语句之间的数据依赖性以帮助实例化查询操作数，如表名和列名。Squirrel构建的依赖性图将多个SQL语句紧密地结合成一个静态图。这意味着它将所有语句的数据依赖性视为固定的，并且在整个查询序列中不会改变。这种静态的方法在处理复杂查询时会遇到问题，因为它不能更新数据依赖性以反映动态的SQL上下文。

之前的工作Squirrel[71]确定了所有SQL语句之间的数据依赖关系，以帮助实例化查询操作数，如表名和列名。然而，Squirrel构建的依赖图将多条SQL语句紧密耦合为一个静态图。在处理复杂查询时，无法通过更新数据依赖关系来反映SQL上下文的动态变化。具体来说，它在整个查询序列中保持静态数据依赖关系不变，无法进行自我调整以适应不同SQL语句之间不断变化的关系。为了解决这一限制，设计了一种基于上下文的IR实例化算法。它根据SQL上下文动态更新数据依赖关系，并将准确的具体值填充到查询骨架中。SQLRight不是将多个SQL语句组合到一个依赖关系图中，而是一次解决一条SQL语句。当解决多条SQL语句时，它只将必要的依赖信息保存到库中。

这也算贡献：Squirrel在他的论文里实现了数据库初始化的依赖关系，然后他在新生成的SQL语句中增加了识别ALTER的关系，然后就说是动态更新dependency graph。

Squirrel的Dependency graph:

3.1.4 Non-determinism Mitigation

数据库管理系统(DBMS)的某些功能包含非确定性行为，这使得即使没有触发逻辑错误，两次执行也会产生不同的结果。这样的查询会混淆DBMS的预测模型并导致误报。专注于内存相关错误的之前的模糊测试工具不关心查询结果，所以它们忽略了这个问题。因此，我们不能直接使用它们生成的查询来查找逻辑错误。

为了避免此类误报，我们确定并删除具有非确定性行为的语句或关键字。目前，SQLRight将非确定性行为分为三类：

一类包含设计上返回随机结果的函数。例如，SQLite中的random()会产生一个伪随机整数。
另一类包含查询结果取决于不断变化的环境变量的查询，如日期和时间（例如，SQLite中的julianday()和PostgreSQL中的current_timestamp）。
非确定性的第三个来源来自未定义的行为。特别地，结果未在DBMS标准中指定，完全取决于每次动态执行如何生成结果。例如，LIMIT子句将SELECT的结果截断为最多N行。它的设计目的是防止大量输出。但是，LIMIT子句导致语义上等价的查询之间的结果不一致，因为它取决于DBMS决定返回哪N行。我们从所有生成的SQL查询中删除LIMIT子句。

感觉和宗寅那篇Stabled bug很像，就是排除一下那些不确定的函数，工作量也很少

General Interfaces for DBMS Oracles

Oracle是检测逻辑错误的关键，但没有任何oracle可以从所有DBMS系统中检测到所有错误。考虑到各种SQL方言和扩展，我们需要多个不同的oracle来覆盖不同的逻辑错误。使我们的模糊测试平台支持多种不同的oracle是至关重要的。在这项工作中，我们提出了一组通用的API，允许开发者采用现有的oracle并开发新的oracle。

SQLRight为模糊器与DBMS oracle通信提供了四个通用的API，分别是preprocess()、append_output()、transform()和compare()。我们使用表1来解释每个API的目的，该表显示了当前支持的oracle和它们API的功能。

预处理：preprocess()以查询集为输入，执行必要的操作为未来的步骤做好准备。例如，oracle Rowid试图从查询中找到CREATE TABLE语句。如果没有创建表，它会通知模糊器跳过当前查询，继续下一个查询。
附加输出语句：SQLRight为每个oracle提供append_output() API，以插入适当的输出生成语句。
转换：oracle的核心任务是将一个查询转换为不同的等价变体。transform()接受查询集作为输入，返回一个或多个等价的查询集。
结果比较：SQLRight允许oracle定义自己的比较方法来识别意外的结果。我们提供了一个宽松的比较函数，仅检查结果中的行数。但是，如果在SELECT中使用了聚合函数(如MIN和SUM)，比较应该期望相同的输出。

在附录B中详细介绍了SQLRight使用oracle Index查找Listing 1中的错误的步骤。

Implementation

SQLRight 是一个用于寻找逻辑错误的覆盖引导型数据库管理系统(DBMS)模糊测试工具。它的设计基于 Squirrel 和 SQLancer，结合了 Squirrel 的查询变异模块，并实现了通用的oracle API以及有效性导向的变异。SQLRight 目前支持四种oracle，包括从SQLancer移植的 NoREC 和 TLP，以及在本文中提出的 Index 和 Rowid。为了有效测试这些DBMS，开发者将SQLite、MySQL和PostgreSQL的解析器移植到了SQLRight。

关键实施细节包括：

内存高效变异：为减少存储SQL查询时的内存使用，SQLRight 不再像 Squirrel 那样存储IR节点，而是直接存储查询字符串。这种方法减少了内存使用，但每次变异查询时，都需要重新将字符串解析为IR，这增加了处理时间。
错误切分：采用了二分查找方法来识别重复的错误报告。对于每个错误报告，它会使用二分搜索算法从所有的代码提交中定位首次引入该错误的提交。此方法有助于避免重复报告相同的问题。
查询最小化工具：为了帮助开发人员更容易地诊断问题，该工具可以自动简化触发错误的查询。通过删除IR节点并检查是否仍然可以触发错误，这一工具可以逐步简化查询，直到得到一个最小版本。

综上所述，SQLRight 是一个先进的模糊测试工具，设计用来识别DBMS的逻辑错误。它具有内存高效的变异策略、错误切分技术以及查询最小化工具，这些特点使其在覆盖率上优于Squirrel，尽管它在同一时间段内生成的查询数量可能较少。

Evaluation

评估问题：

Q1. SQLRight 是否能够检测到真实世界中的逻辑错误？
Q2. SQLRight 是否能找到比现有工具更多的错误？
Q3. 代码覆盖率如何指导测试？
Q4. 查询的有效性如何帮助检测错误？

评价指标：

真实世界中的逻辑错误的检测率（针对Q1）
与现有工具比较的错误发现数量（针对Q2）
代码覆盖率的变化和反馈（针对Q3）
代码覆盖率、查询有效性和错误检测的影响，在禁用SQLRight的每个查询有效性组件后（针对Q4）

实验设置：

测试的DBMS：（针对RQ1）

SQLite
MySQL
PostgreSQL

测试的Oracle:

TLP
NoRec
rowid
index

这三个DBMS是之前用来评估DBMS错误查找工具的常见选择。

为了回答Q1，我们使用SQLRight测试了三个流行的DBMS系统，即SQLite、MySQL和PostgreSQL，这些系统在之前的工作中常用于评估DBMS的错误查找工具[21,43-45,71]。为了回答Q2，我们将SQLRight与SQLancer和Squirrel进行比较，这两者是DBMS的最先进的错误查找工具。由于Squirrel不能检测逻辑错误，我们将我们的oracles移植到Squirrel上，称为Squirrel+oracle。为了回答Q3，我们比较了处理新查询的三种方法的覆盖率反馈：全部丢弃、全部保存和随机保存一些。为了回答Q4，我们禁用了SQLRight的每个查询有效性组件，以找出其对代码覆盖率、查询有效性和错误检测的影响。

DBMS Logical Bugs

由于资源的有限性，作者对每个DBMS进行了不同持续时间的错误查找实验。具体来说，他们花了60天测试SQLite，14天测试PostgreSQL，7天测试MySQL。总共，SQLRight检测到了27个错误，包括18个逻辑错误，5次崩溃和4次断言失败。除了来自MySQL的3个逻辑错误外，所有其他错误都来自SQLite；他们没有在PostgreSQL中找到任何错误。尽管测试持续时间不同，但他们发现了与之前的研究[43-45, 71]中的错误数量相似的模式，其中大部分错误来自SQLite，很少有错误来自PostgreSQL。所有的发现都已报告给开发人员，所有错误都已确认，并且其中23个已经被修复。

与崩溃和断言失败相比，SQLRight检测到更多的逻辑错误。由于我们设计了一套解决方案来提高查询的有效性，所以SQLRight生成的异常语句导致DBMS崩溃的次数减少了。表2提供了更多的错误详情。

文章描述了两个逻辑错误的细节，以帮助说明反馈和有效性对于错误查找的必要性。其中一个错误是由于SQLite的不正确的索引查找引起的。另一个错误只能通过使用每个DBMS的解析器和基于上下文的实例化来检测。

Necessity of Coverage-based Feedback.

Listing 6 展示了一个由于不正确的索引查找导致的SQLite逻辑错误。

首先，创建了一个没有ROWID的表，该表有两列。v1是表的主键，并按降序排列。接下来，向v0插入了一行数据，并为列v2创建了索引v3。SELECT语句试图查找满足v2=10和v1<11条件的行。理论上，行(10,10)应满足这些条件并被返回。但是，由于不正确的索引搜索混淆了DESC PRIMARY KEY和索引v3，SQLite没有返回任何结果。

在Listing 6的结尾部分，我们看到了引发这个错误的相关种子输入。从原始输入中，我们可以看到缺少大部分触发这个错误所需的组件，比如WITHOUT ROWID、DESC、INDEX和SELECT。为了生成这个触发错误的查询，SQLRight必须累积七个连续的变异。每个变异都触发新的代码覆盖率并被保存到队列中。如果没有代码覆盖率的指导，SQLRight很难维持如此深的变异链，也难以检测到这个错误。

Necessity of SQL Validity.

Listing 7 揭示了与列别名相关的SQLite逻辑错误。当使用特定的SQL有效性技巧时，SQLRight能够检测到其他工具如Squirrel+oracle和SQLancer可能会错过的错误。

在这个示例中，首先创建了一个有两列的表v0，并为这两列创建了一个索引。接着，插入了一行数据到这个表。接下来的两个SELECT语句试图查找满足条件v1=v2和v1=’x’的行。但是，由于v1和v2的值是不同的，这些条件实际上并不满足。然而，当使用别名引用表v0时，SQLite会错误地优化查询，忽略第一个条件并返回这行。而SQLancer不能检测到这个错误，因为它在生成SELECT语句时不使用别名。尽管Squirrel+oracle在解析时允许使用别名，但在实例化时不使用它。因此，如果表有别名，Squirrel+oracle会解析条件为v1=v2，导致“模糊的列名”错误。与此不同，SQLRight采用了基于上下文的实例化，成功地避免了这种冲突问题并触发了这个错误。

Comparison with Existing Tools

本节比较了SQLancer与SQLRight和Squirrel+oracle三种工具。

SQLancer有三种oracle：NoREC、TLP和PQS。NoREC和TLP修改查询语句来检测错误，而SQLRight可以通过其通用API轻松支持它们。但PQS依赖于数据库内容来构建语句，SQLRight考虑在将来支持它。
实验设置：他们在每个设置中启动五个实例，并运行72小时。因为SQLancer不支持MySQL的NoREC，所以跳过了这个设置。附录中的图5（NoREC）和图8（TLP）展示了评估结果。
逻辑错误：SQLRight在所有设置中报告了最多的12个错误，包括使用NoREC的6个SQLite错误和3个MySQL错误，以及使用TLP的2个SQLite错误和1个MySQL错误。Squirrel+oracle仅找到1个错误，这是使用NoREC从SQLite中找到的；SQLancer没有找到任何逻辑错误。SQLancer的空结果可能是因为它在测试这些DBMS系统时被广泛使用。这证明了引入更多种多样的机制来检测逻辑错误的必要性。
代码覆盖率：SQLRight在三个DBMS系统上触发的代码覆盖率明显高于其他工具。与Squirrel+oracle相比，精确的解析器和基于上下文的实例化帮助SQLRight超越这个先进的基于覆盖率的DBMS测试器。
查询有效性：SQLancer达到了最高的查询有效性，对于SQLite超过80%，MySQL为99%，PostgreSQL超过28%。SQLRight对于三个测试的DBMS分别达到了大约30%、25%和10%的有效性。尽管如此，与Squirrel+oracle相比，SQLRight达到了显著更高的有效性。另一个观察是，SQLancer可以保持一致的高有效率达到72小时。基于突变的模糊器随着时间的推移有效率会降低。

总之，SQLRight与其他工具相比，在代码覆盖率、逻辑错误检测和查询有效性方面都有其优势和特点。

局限性：只比较了NOREC这一种Oracle，因为他的工具在这种Oracle上表现得最好

Overall:总的来说，SQLLight比SQLancer和松鼠+版本可以找到更多的逻辑错误。它在触发更多的程序代码方面也优于现有的工具。尽管SQLancer可以产生高质量的查询，但它缺乏查询多样性，这使得它在查找新的逻辑bug方面效率较低。

squirrel查询0%的有效性是怎么回事？Squirrel在 SQLite、MySQL 和 MariaDB 中分别找到了 51 个、7 个和 5 个漏洞，可能是Squirrel在MySQL文法上支持不好的原因

Contribution of Coverage Feedback

该部分探讨了SQLRight在使用三种不同反馈方法时的效果：SQLRightdrop、SQLRightsave和SQLRightrand。

不同反馈策略：
- SQLRightdrop：丢弃所有生成的查询，仅变异种子输入。
- SQLRightsave：保存所有生成的查询到队列中，并轮流变异每个查询。（无论它们是否触发新的覆盖率）
- SQLRightrand：随机将10%的所有生成的查询保存到队列中。
实验设置：使用SQLite对NoREC和TLP进行单元测试，每个设置并行运行五个实例，持续24小时。图6显示了代码覆盖率和逻辑错误的平均结果。他们还测量了不同深度的查询对覆盖率的贡献。
逻辑错误：对于NoREC和TLP，SQLRight报告的错误最多，包括使用NoREC的4个错误和使用TLP的2个错误。SQLRightdrop和SQLRightsave在使用NoREC时报告2个错误，而SQLRightrand只检测到1个。没有代码覆盖时，使用TLP的SQLRight没有找到任何逻辑错误。
代码覆盖率：SQLRight达到了最高的代码覆盖率，与SQLRightdrop相比，它更高。SQLRightrand和SQLRightsave引发的分支更少。结果显示了基于覆盖率指导生成更多样化查询的好处。
突变深度：SQLRight维护了更深的变异链，高深度的查询帮助SQLRight触发更多的代码覆盖率。高深度查询对于发现错误和保持高覆盖率是非常有益的。SQLRightdrop、SQLRightrand和SQLRightsave在没有基于覆盖的指导的情况下积累变异较慢，落后于SQLRight。
结论：基于覆盖的指导帮助生成更多样化的查询，并积累有用的突变，这帮助比没有反馈的基线发现更多的错误。

总之，通过对SQLRight的不同反馈策略的比较，研究表明基于覆盖的反馈在生成更多样化的查询、触发更高的代码覆盖率和发现更多的逻辑错误方面都具有优势。

Overall:基于覆盖的指导有助于生成更多样化的查询和积累有用的突变，这有助于发现比无反馈基线更多的bug。

控制变量对比试验，说明覆盖率导向是有用的，这点可以学习一下

Contribution of Validity

这一部分评估了在§3.1中引入的提高有效性的技术，包括合作突变、DBMS特定的解析器、基于上下文的实例化以及非确定性缓解。

不同设置：
- SQLRight-deter：禁用非确定性缓解技术。
- SQLRight-ctx-valid：禁用基于上下文的实例化，并使用Squirrel的依赖关系图验证。
- SQLRight-db-par&ctx-valid：在SQLRight-ctx-valid的基础上重用Squirrel的SQL解析器。
- Squirrel+oracle：不采用任何有效性改进技术。
实验设置：在三个DBMS上进行单元测试，并使用两个oracle评估每个设置，每个设置运行五个实例，持续24小时。
逻辑错误：在各种设置中，SQLRight触发的错误最多，尤其是在SQLite和MySQL中。其他设置发现的错误较少。
代码覆盖率：SQLRight在所有单元测试中都占据了代码覆盖率的领导地位。有效性技术有助于生成更多样化的查询并探索更多代码。每个DBMS的解析器对代码覆盖率的贡献最大，因为解析器理解不同的SQL方言，可以探索每个DBMS特定的自定义功能。
查询有效性：每个DBMS的解析器在查询有效性中起着最重要的作用。Squirrel的解析器在测试PostgreSQL和MySQL时无法生成任何有用的查询。SQLRight在三个DBMS中对PostgreSQL的有效性最低，因为它有着最严格的语法和语义规则。
由非确定性导致的假阳性：表4显示了二分法后的假阳性数字。SQLRight-deter与SQLRight在代码覆盖率和有效性上相似，但它在SQLite和MySQL中产生了大量的假阳性。禁用所有非确定性行为后，SQLRight仍然引入了少量的假阳性，主要是由于每个DBMS中的特殊语义。

总结，通过评估不同的提高有效性的技术，研究表明这些技术有助于提高代码覆盖率、生成更多样化的查询和减少假阳性。SQLRight在所有测试设置中都表现出色，尤其是在代码覆盖率和查询有效性方面。

Discussion

在本节中，我们首先讨论SQLRight的误报（FP）和无效查询的常见原因。然后，我们介绍了种子输入对于查找逻辑错误的重要性。

FP1：在SQLite中查看相关性。我们在View of SQLite中发现了一些与数据相关性问题有关的误报。清单8给出了一个触发错误警报的示例。我们预计第5行返回的行数与第6行的结果相同（可能为4）。但是，第一个SELECT返回四行，而第二个返回2行。SQLite开发人员明确表示，这种不一致性是由于未定义的亲和性造成的。
在这里插入图片描述

具体来说，SQLite为每列分配一个关联（类似于数据类型），并为每个关联使用不同的比较算法。在本例中，v2.v3的亲和性是独立的，因为来自两个来源的亲和性不同：SELECT v1 from v0返回一个具有亲和性TEXT的列，而SELECT v1=10 from v1返回一个带有亲和性NONE的列。因此，在最后两个SELECT中，SQLite可以自由选择任何亲和性来比较v3。在第5行中，SQLite使用亲和性TEXT并重新转换四行，而在第6行中，SQLite选择亲和性BLOB并只找到两行匹配的行。我们发现，亲和性问题通常被第三方工具报告为“错误”，包括SQLancer[30]。尽管SQLite文档已经清楚地解释了这个问题[50]，但我们怀疑DBMS管理员可能仍然会错过它并创建不明确的查询。

FP2：SQLite子查询中的排序。清单9显示了一个由于子查询中未定义排序而导致的误报。
该查询首先创建具有列c1和c2的表v0，并插入行（NULL，10）和（NULL，NULL）。然后，它创建视图v3以访问v0中的特定行。如果v0中的一行满足条件c1为NULL，则最小c1将分配给c4，c2将分配给c5。两个SELECT语句的计数都是c5，但它们返回的结果不同。这个问题是由于SQLite子查询中未定义的顺序造成的。VIEW创建语句在子查询中使用聚合函数MIN。为了保持行号的一致性，SQLite将返回一行c2并将其分配给c5。然而，c2的哪一行没有定义，也就是说，它可以是10或NULL，因为v0中的两行都满足条件c1为NULL。如果返回NULL，则计数结果为0；如果使用10，则结果为1。

在这里插入图片描述

FP3:MySQL中的GROUP BY NULL。清单10显示了MySQL中常见的误报。当我们从sql_mode关闭ONLY_FULL_GROUP_BY时，这个假阳性是可重复的。示例查询首先创建表v0并插入行（1）、（1）和（3）。然后，它使用oracleTLP来检查v0的行。两个SELECT返回的结果不同，触发TLP报告潜在错误。区别在于GROUP BY NULL，它强制SELECT返回一行，而不管真正匹配的行是什么。第一个SELECT有一个SELECT子句，因此返回一行，而第二个SELECT有三个SELECT子句并返回两行。如果GROUP BY子句中的SQL表达式返回NULL，也可能触发此问题。因此，除非我们手动从GROUP BY中排除表达式，否则很容易触发这种误报。幸运的是，由于误报数量较少，我们可以很容易地识别和忽略此类误报。

在这里插入图片描述

无效查询的示例。尽管SQLRight使用了几种技术来提高有效性，但它不能保证100%的正确性。清单11显示了SQLRight为PostgreSQL生成的一组无效查询。查询首先创建一个具有自定义类型circle的表，插入一个circle值，然后在对其行进行重新排序后尝试打印出该表。由于PostgreSQL没有圆的比较方法，因此重新排序操作将失败。要修复此程序，SQLRight必须了解PostgreSQL几何类型及其相关函数。它应该生成查询来比较圆的半径、直径、面积或其他几何特征。最后一个SELECT显示一个正确的查询。由于大量的自定义数据类型及其相关功能，我们考虑在未来支持它们。

在这里插入图片描述

种子语料库的重要性。在评估过程中，我们没有注意到种子输入对于SQLRight查找逻辑错误很重要。SQLRight依赖于随机突变来生成新的查询，而种子输入提供了突变的所有元素。如果种子输入涵盖了广泛的功能，SQLRight可以生成更多样的测试查询，从而可以测试DBMS的更多方面。为了保证种子输入的质量，我们从每个测试的DBMS。例如，我们从TCL测试脚本中为SQLite收集了160多个种子输入，涵盖了各种SQLite函数，如WHERE、ROWID和IN。TCL测试是SQLite的内置测试工具。它的代码可在SQLite GitHub存储库中获得，它包含1272个测试文件和46000多个独特的测试用例。这些TCL测试脚本不仅包含以前发现的错误，还涵盖了许多SQLite特定的功能，如ROWID。我们计划在未来的工作中向SQLRight引入更多高质量和多样化的种子输入.