LLM-Based Test Case Generation in DBMS through Monte Carlo Tree Search

📄 arXiv: 2603.21530v1 📥 PDF

作者: Yujia Chen, Yingli Zhou, Fangyuan Zhang, Cuiyun Gao

分类: cs.SE, cs.AI

发布日期: 2026-03-23

备注: Accepted to ICSE 2026 Industry Challenge Track

💡 一句话要点

MIST：基于蒙特卡洛树搜索的LLM驱动DBMS测试用例生成框架

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 数据库测试 自动化测试 大型语言模型 蒙特卡洛树搜索 代码覆盖率

📋 核心要点

  1. 现有DBMS测试方法难以适应不同专有SQL方言，且LLM生成测试用例存在语法错误和语义相似性问题，导致覆盖率提升受限。
  2. MIST框架通过特征引导的错误驱动合成和蒙特卡洛树搜索变异，生成语法有效、语义多样且能探索深层执行路径的测试用例。
  3. 实验结果表明，MIST在行覆盖率、函数覆盖率和分支覆盖率方面显著优于基线方法，平均提升分别达到43.3%、32.3%和46.4%。

📝 摘要（中文）

数据库管理系统(DBMS)是现代数据驱动应用的基础设施，高质量的SQL测试用例对于确保系统可靠性至关重要。传统的模糊测试方法对于特定DBMS有效，但将其适配到不同的专有方言需要大量的人工工作。大型语言模型(LLM)为自动化SQL测试生成提供了有希望的机会，但在工业环境中面临严峻挑战。首先，由于安全和隐私限制，组织广泛使用轻量级模型，但它们难以生成符合专有SQL方言的语法有效的查询。其次，LLM生成的查询通常语义相似，仅能执行浅层的执行路径，从而迅速达到覆盖率平台期。为了解决这些挑战，我们提出了MIST，一个基于蒙特卡洛树搜索的LLM驱动的DBMS测试用例生成框架。MIST包括两个阶段：特征引导的错误驱动测试用例合成，它构建一个分层特征树，并使用错误反馈来指导LLM生成，旨在为不同的DBMS方言生成语法有效且语义多样的查询；以及基于蒙特卡洛树搜索的测试用例变异，它联合优化种子查询选择和变异规则应用，并由覆盖率反馈指导，旨在通过探索更深层的执行路径来提高代码覆盖率。在三个广泛使用的DBMS上使用四个轻量级LLM进行的实验表明，与在Optimizer模块中具有最高69.3%行覆盖率的基线方法相比，MIST在行覆盖率、函数覆盖率和分支覆盖率方面分别平均提高了43.3%、32.3%和46.4%。

🔬 方法详解

问题定义：论文旨在解决DBMS测试中，现有方法难以适应不同专有SQL方言，以及LLM生成测试用例时存在的语法错误、语义相似性问题，导致代码覆盖率提升受限的问题。现有方法，如模糊测试，需要大量人工适配工作，而直接使用LLM生成测试用例，容易产生无效或重复的测试用例，无法有效探索深层代码路径。

核心思路：论文的核心思路是结合LLM的生成能力和蒙特卡洛树搜索(MCTS)的探索能力，设计一个两阶段的测试用例生成框架。首先，利用特征引导和错误驱动的方法，提高LLM生成测试用例的语法正确性和语义多样性。然后，利用MCTS，根据代码覆盖率反馈，选择合适的种子查询和变异规则，引导测试用例向更深层的代码路径探索。

技术框架：MIST框架包含两个主要阶段：1) 特征引导的错误驱动测试用例合成：构建分层特征树，指导LLM生成SQL查询，并根据DBMS的错误反馈进行调整，提高语法正确性。2) 基于蒙特卡洛树搜索的测试用例变异：利用MCTS选择种子查询和变异规则，根据代码覆盖率反馈进行优化，探索更深层的执行路径。

关键创新：MIST的关键创新在于：1) 结合了LLM和MCTS，充分利用了LLM的生成能力和MCTS的探索能力。2) 提出了特征引导的错误驱动合成方法，有效提高了LLM生成SQL查询的语法正确性和语义多样性。3) 利用代码覆盖率反馈，指导MCTS选择种子查询和变异规则，实现了对深层代码路径的有效探索。与现有方法相比，MIST能够更有效地生成高质量的测试用例，提高代码覆盖率。

关键设计：在特征引导的错误驱动合成阶段，特征树的构建需要根据目标DBMS的SQL方言进行定制。错误反馈的处理需要设计合适的策略，例如，根据错误类型调整LLM的生成策略。在基于蒙特卡洛树搜索的测试用例变异阶段，需要定义合适的变异规则，例如，增加、删除或修改SQL查询的子句。MCTS的奖励函数需要根据代码覆盖率进行设计，例如，可以使用行覆盖率、函数覆盖率或分支覆盖率作为奖励。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，MIST在三个广泛使用的DBMS上，使用四个轻量级LLM进行测试，与基线方法相比，在行覆盖率、函数覆盖率和分支覆盖率方面分别平均提高了43.3%、32.3%和46.4%。基线方法在Optimizer模块中具有最高的69.3%行覆盖率，MIST在此基础上仍有显著提升。

🎯 应用场景

MIST框架可应用于各种数据库管理系统的自动化测试，尤其适用于需要适配多种专有SQL方言的场景。该研究成果有助于提高DBMS的可靠性和安全性，降低软件开发和维护成本，并可推广到其他软件系统的自动化测试领域。

📄 摘要（原文）

Database Management Systems (DBMSs) are fundamental infrastructure for modern data-driven applications, where thorough testing with high-quality SQL test cases is essential for ensuring system reliability. Traditional approaches such as fuzzing can be effective for specific DBMSs, but adapting them to different proprietary dialects requires substantial manual effort. Large Language Models (LLMs) present promising opportunities for automated SQL test generation, but face critical challenges in industrial environments. First, lightweight models are widely used in organizations due to security and privacy constraints, but they struggle to generate syntactically valid queries for proprietary SQL dialects. Second, LLM-generated queries are often semantically similar and exercise only shallow execution paths, thereby quickly reaching a coverage plateau. To address these challenges, we propose MIST, an LLM-based test case generatIon framework for DBMS through Monte Carlo Tree search. MIST consists of two stages: Feature-Guided Error-Driven Test Case Synthetization, which constructs a hierarchical feature tree and uses error feedback to guide LLM generation, aiming to produce syntactically valid and semantically diverse queries for different DBMS dialects, and Monte Carlo Tree Search-Based Test Case Mutation, which jointly optimizes seed query selection and mutation rule application guided by coverage feedback, aiming at boosting code coverage by exploring deeper execution paths. Experiments on three widely-used DBMSs with four lightweight LLMs show that MIST achieves average improvements of 43.3% in line coverage, 32.3% in function coverage, and 46.4% in branch coverage compared to the baseline approach with the highest line coverage of 69.3% in the Optimizer module.