LLM-Based Test Case Generation in DBMS through Monte Carlo Tree Search
Organizations: Harbin Institute of Technology, Shenzhen, Shenzhen, China · The Chinese University of Hong Kong, Shenzhen, Shenzhen, China · Huawei Hong Kong Research Center, Hongkong, China
Abstract
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.
Figures & tables
| DuckDB | PostgreSQL | SQLite | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Model | Approach | Line | Function | Branch | Line | Function | Branch | Line | Function | Branch |
| Fuzz4All | 29.9% | 29.7% | 17.0% | 23.1% | 25.2% | 16.2% | 29.9% | 38.9% | 22.5% | |
| Qwen2.5-7B | MIST | 42.0% | 38.2% | 24.5% | 30.3% | 38.6% | 21.3% | 39.7% | 46.1% | 31.3% |
| Fuzz4All | 32.3% | 31.7% | 18.3% | 24.2% | 31.8% | 16.9% | 28.3% | 36.6% | 21.1% | |
| Llama3.1-8B | MIST | 43.2% | 39.3% | 25.4% | 29.3% | 37.7% | 20.5% | 39.9% | 45.2% | 32.1% |
| Fuzz4All | 26.4% | 26.8% | 14.6% | 23.6% | 31.3% | 16.4% | 21.6% | 30.3% | 15.6% | |
| Model | Approach | Parser | Optimizer | Executor | Storage |
|---|---|---|---|---|---|
| DuckDB | |||||
| Qwen2.5 7B | Fuzz4All | 26.6% | 51.6% | 31.0% | 20.0% |
| MIST | 43.2% | 68.4% | 42.2% | 31.3% | |
| Llama3.1 8B | Fuzz4All | 30.1% | 52.8% | 35.1% | 22.7% |
| MIST | 48.9% | 69.3% | 47.3% | 32.9% | |
| Qwen2.5 14B | Fuzz4All | 24.2% | 43.4% | 22.9% | 22.1% |
| Synthetization | Mutation | DuckDB | PostgreSQL | SQLite | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Line | Function | Branch | Line | Function | Branch | Line | Function | Branch | ||
| Simple Instruction | ✗ | 29.9% | 29.7% | 17.0% | 23.1% | 25.2% | 16.2% | 29.9% | 38.9% | 22.5% |
| Random Feature | ✗ | 32.3% | 31.7% | 18.7% | 25.2% | 30.1% | 16.9% | 32.8% | 41.7% | 24.6% |
| Hierarchical Feature (MIST) | ✗ | 36.2% | 34.7% | 20.6% | 27.4% | 32.1% | 17.8% | 35.5% | 43.2% | 26.3% |
| Hierarchical Feature (MIST) | Simple Instruction | 37.8% | 35.7% | 21.6% | 28.3% | 33.9% | 18.1% | 36.9% | 44.2% | 27.5% |
| Hierarchical Feature (MIST) | Random Rule | 38.7% | 36.7% | 22.4% | 28.8% | 35.4% | 19.5% | 37.5% | 44.8% | 29.2% |
Automated Test Generation
Automated test generation creates inputs, scenarios, and checks to expose software and system defects with less manual effort.
See all 132 papers