LinLi's Blog

Mallet: SQL Dialect Translation with LLM Rule GenerationABSTRACT在不同系统的SQL方言之间进行翻译对于迁移和联合查询处理非常重要。现有的方法依赖于手工制定的翻译规则，这些规则往往不完整且难以维护，尤其是在需要翻译的方言数量增加的情况下。因此，方言翻译仍然是一个未解决的问题。 为了解决这个问题，我们引入了Mallet系统，该系统利用大型语言模型（LLMs）来自动生成SQL-to-SQL翻译规则，即模式转换、自动UDF生成、扩展选择和表达式组合。一旦生成这些规则，它们在新的工作负载上可以无限次重复使用，而无需将LLM置于查询执行的关键路径上。Mallet通过以下方式提高LLM的准确性：（1）在系统文档和人工专业知识的基础上执行检索增强生成（RAG），（2）使用实际SQL系统进行经验验证，以检测幻觉，（3）自动创建准确的少量学习实例。贡献者在不了解系统代码的情况下，通过提供自然语言专业知识来改进Mallet的RAG。 INTRODUCTIONBackground 数据库管理领域在过去几十年里变得越来越复杂。这种复杂性不仅源于大量 ...

Keep It Simple: Testing Databases via DifferentialQuery PlansABSTRACT查询优化器执行各种优化，其中许多已被提出用于优化连接。确保这些优化的正确性至关重要，这意味着它们应经过广泛测试。除了手工编写的测试之外，自动化测试方法也得到了广泛采用。这些方法半随机地生成数据库和查询。更重要的是，它们提供了一种所谓的测试预言机，能够推断系统的结果是否正确。最近，研究人员提出了一种名为“转换查询合成”（Transformed Query Synthesis，TQS）的新测试方法，专门用于发现连接优化中的逻辑错误。TQS是一种复杂的方法，它将给定的输入表拆分成多个子表，并通过检索给定表来验证连接这些子表的查询结果。 我们研究了TQS的错误报告，发现15个独特错误中有14个是通过执行相同查询但使用不同查询计划时显示出差异来报告的。因此，在本研究中，我们提出了一种简单的替代TQS的方法。我们的方法强制为同一查询采用不同的查询计划，并验证结果的一致性。我们将这种方法称为“差异查询计划”（Differential Query Plan，DQP） ...

WINGFUZZ: Implementing Continuous Fuzzing for DBMSsAbstract数据库管理系统（DBMS）是软件生态系统中的关键组件，其安全性和稳定性至关重要。近年来，模糊测试已成为一种重要的自动化测试技术，有效地识别了各种DBMS中的漏洞。然而，许多模糊测试工具需要针对特定版本的DBMS进行特殊适配。在企业级DBMS上持续进行测试面临挑战，因为这些DBMS具有多样化的规格且版本更新迅速。 在本文中，我们介绍了在企业级DBMS（如ClickHouse）上实施持续模糊测试的行业实践。我们总结了实现这一过程中的三个主要障碍，分别是测试用例生成中的多样化SQL语法、持续测试中代码库的不断演化以及异常分析期间的噪声干扰。我们提出了WINGFUZZ，通过使用基于规范的变异生成、基于语料库的代码演化模糊测试以及抗噪异常评估来解决这些问题。通过与工程师合作进行持续DBMS模糊测试，我们在12种广泛使用的企业级DBMS（包括ClickHouse、DamengDB和TenDB）中发现了总计236个之前未发现的漏洞。由于其显著的测试效果，我们的努力得到了部分DBMS厂 ...

Sedar: Obtaining High-Quality Seeds for DBMS Fuzzing via Cross-DBMS SQL TransferABSTRACT有效的数据库管理系统（DBMS）模糊测试依赖于高质量的初始种子，这些种子作为变异的起点。这些初始种子应该包含各种DBMS功能，以全面探索状态空间。尽管内置的测试用例通常用作初始种子，但许多DBMS缺乏全面的测试用例，这使得难以直接应用最先进的模糊测试技术。 为了解决这个问题，我们提出了Sedar，Sedar通过从其他DBMS转移测试用例，为目标DBMS生成初始种子。其基本原理是，许多DBMS共享类似的功能特性，允许覆盖一个DBMS中深度执行路径的种子可以适用于其他DBMS。挑战在于将这些种子转换为目标数据库所支持的语法格式。Sedar生成种子的过程分为三个步骤。首先，它在种子最初设计的DBMS中执行现有的SQL测试用例，并在执行期间捕获架构信息。其次，它利用大语言模型（LLM）以及捕获的架构信息，基于LLM的响应指导新测试用例的生成。最后，为了确保测试用例能够被模糊测试器正确解析和变异，Sedar暂时注释掉模糊测 ...

Testing Database Engines via Query Plan GuidanceABSTRACT摘要——数据库系统被广泛用于存储和查询数据。测试预言机（test oracles）已被提议用于发现这些系统中的逻辑错误，即导致数据库系统计算出错误结果的错误。为了实现完全自动化的测试方法，这些测试预言机与测试用例生成技术相结合；测试用例指的是数据库状态和可应用测试预言机的查询。在这项工作中，我们提出了查询计划引导（QPG）的概念，用于引导自动化测试朝向“有趣”的测试用例。SQL和其他查询语言是声明式的。因此，为了执行查询，数据库系统将源语言中的每个操作符翻译为一个或多个可以执行的所谓物理操作符；物理操作符的树被称为查询计划。我们的直觉是，通过引导测试去探索各种独特的查询计划，我们也会探索更多有趣的行为——其中一些可能是错误的。为此，我们提出了一种变异技术，逐步将有希望的变异应用于数据库状态，从而导致数据库管理系统（DBMS）为后续查询创建潜在的未见过的查询计划。我们将我们的方法应用于三个成熟的、广泛使用且经过广泛测试的数据库系统——SQLite、TiDB和CockroachD ...

Detecting Metadata-Related Logical Bugs in Database Systems via Raw Database ConstructionABSTRACT:数据库管理系统（DBMSs）被广泛用于高效地存储和检索数据。DBMSs通常支持各种元数据，例如用于确保数据完整性的完整性约束和用于定位数据的索引。DBMSs还可以利用这些元数据来优化查询评估。然而，不正确的元数据相关优化可能会引入元数据相关的逻辑错误，这可能导致DBMS对给定查询返回不正确的查询结果。在本文中，我们提出了一种通用且有效的测试方法，原始数据库构建（Radar），以检测DBMS中的元数据相关逻辑错误。给定一个包含一些元数据的数据库DB，Radar首先构建一个原始数据库DB_raw，它清除DB中的元数据并包含与DB相同的数据。由于DB和DB_raw具有相同的数据，它们对给定查询应返回相同的查询结果。任何查询结果的不一致都表明存在元数据相关的逻辑错误。为了有效地检测元数据相关的逻辑错误，我们进一步提出了一种元数据导向的测试优化策略，重点测试以前未见过的元数据，从而快速检测更多的元数据相 ...

Fuzz4All: Universal Fuzzing with Large Language ModelsAbstractFuzzing技术在发现各种软件系统中的漏洞和缺陷方面取得了巨大的成功。作为软件开发的基础构件，接受编程语言或形式语言输入的测试系统（SUTs），如编译器、运行时引擎、约束求解器和具有可访问API的软件库，尤为重要。然而，现有的针对这些系统的fuzzers通常针对特定语言，因此无法轻易应用于其他语言甚至同一语言的不同版本。此外，现有fuzzers生成的输入通常局限于输入语言的特定特性，难以发现与其他或新特性相关的漏洞。本文提出了Fuzz4All，这是首个在多个不同输入语言和这些语言的多个特性方面通用的fuzzer。Fuzz4All的核心思想是利用大型语言模型（LLMs）作为输入生成和变异引擎，从而使该方法能够为任何实际相关的语言生成多样且逼真的输入。为了实现这一潜力，我们提出了一种新颖的自动提示技术，该技术创建了适合fuzzing的LLM提示，并提出了一种新颖的LLM驱动的fuzzing循环，该循环迭代更新提示以创建新的fuzzing输入。我们在九个接受六种不同语 ...

Detecting Logic Bugs in Database Engines via Equivalent Expression TransformationABSTRACT数据库管理系统（DBMS）对于存储和获取数据至关重要。为了提高这些系统的可靠性，已提出了各种方法来检测导致DBMS处理数据错误的逻辑错误。这些方法通过操作查询并检查DBMS生成的查询结果是否符合预期来发现错误。然而，这种查询级别的操作无法处理复杂的查询语义，因此需要限制生成的查询模式，这降低了测试的有效性。 在本文中，我们采用了一种细粒度的方法——表达式级别的操作，这种方法使得所提出的方法能够适用于任意查询。为了在DBMS中找到逻辑错误，我们设计了一种新颖且通用的方法，即等价表达式转换（EET）。我们的核心思想是，以保持语义的方式操作查询的表达式，也可以保持整个查询的语义，并且与查询模式无关。EET通过检查转换后的查询是否仍然产生与原始查询相同的结果来验证DBMS。我们实现了这种方法，并在五种广泛使用且经过广泛测试的DBMS上进行了评估：MySQL、PostgreSQL、SQLite、ClickHouse 和 ...

Mozi: Discovering DBMS Bugs via Configuration-Based Equivalent TransformationABSTRACT测试数据库管理系统（DBMS）是一项复杂的任务。传统方法，如变异测试，需要深入理解SQL规范以生成具有等效语义的多样化输入。SQL规范的模糊性和复杂性使得准确建模查询语义变得困难，从而在测试DBMS的正确性和性能时遇到挑战。为了解决这一问题，我们提出了Mozi，一个通过基于配置的等效转换来发现DBMS错误的框架。Mozi的核心思想是比较同一DBMS在不同配置下的结果，而不是比较语义上等效的查询。该框架包括分析查询计划，更改配置以将DBMS转换为等效状态，以及重新执行查询，使用各种测试神谕来比较结果。例如，查询结果的差异表明正确性错误，而在优化后的DBMS上观察到更快的执行时间则表明性能错误。 我们通过在四个广泛使用的DBMS上测试Mozi来证明其有效性，即MySQL、MariaDB、Clickhouse和PostgreSQL。在持续测试中，Mozi共发现了101个以前未知的错误，包括四个DBMS中的49个正确性错误和5 ...

Testing Graph Database Systems via Equivalent Query RewritingABSTRACT图数据库管理系统（GDBMS）利用图模型进行数据存储，并通过图遍历执行查询，在推荐系统、知识图谱和社交网络等实际场景中被广泛使用。与关系数据库管理系统（RDBMS）类似，GDBMS也不免于出现错误。这些错误通常表现为逻辑错误导致的结果不正确（例如，漏掉应包含的节点）、性能错误（例如，由冗余图扫描导致的长执行时间）和异常问题（例如，意外或缺失的异常）。 本文将等价查询重写（EQR）技术应用于GDBMS测试。EQR将GDBMS查询重写为触发不同查询计划的等价查询，并检查它们是否在系统行为上存在差异。为了实现EQR，我们提出了一个称为抽象语法图（ASG）的通用概念。其核心思想是将基本查询的语义嵌入到图的路径中，这些路径可以用于生成具有自定义属性（例如等价性）的新查询。给定一个基本查询，构建一个ASG，然后通过找到集体携带基本查询完整语义的路径生成等价查询。为此，我们进一步设计了随机游走覆盖（RWC）算法，这是一个简单而有效的路径覆盖算法。作为这些想法的实际 ...