몬테 카를로 트리 탐색을 이용한 LLM 기반 DBMS 테스트 케이스 생성

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

데이터베이스 관리 시스템(DBMS)은 현대의 데이터 기반 애플리케이션의 핵심 인프라이며, 시스템의 안정성을 보장하기 위해서는 고품질의 SQL 테스트 케이스를 활용한 철저한 테스트가 필수적입니다. 퍼징과 같은 기존 방법은 특정 DBMS에 효과적일 수 있지만, 다양한 독점적인 SQL 방언에 적용하려면 상당한 수동 노력이 필요합니다. 대규모 언어 모델(LLM)은 자동화된 SQL 테스트 생성에 유망한 기회를 제공하지만, 산업 환경에서는 중요한 과제에 직면합니다. 첫째, 보안 및 개인 정보 보호 제약으로 인해 조직에서 경량 모델이 널리 사용되지만, 이러한 모델은 독점적인 SQL 방언에 대한 구문적으로 유효한 쿼리를 생성하는 데 어려움을 겪습니다. 둘째, LLM이 생성한 쿼리는 종종 의미적으로 유사하며, 얕은 실행 경로만 실행하여 빠르게 커버리지 수준이 정체되는 경향이 있습니다. 이러한 과제에 대응하기 위해, 우리는 몬테 카를로 트리 탐색을 이용한 LLM 기반 DBMS 테스트 케이스 생성 프레임워크인 MIST를 제안합니다. MIST는 두 가지 단계로 구성됩니다. 첫째, 특징 기반 오류 주도 테스트 케이스 합성 단계는 계층적 특징 트리를 구성하고 오류 피드백을 활용하여 LLM 생성을 안내하여 다양한 DBMS 방언에 대한 구문적으로 유효하고 의미적으로 다양한 쿼리를 생성하는 것을 목표로 합니다. 둘째, 몬테 카를로 트리 탐색 기반 테스트 케이스 변환 단계는 시드 쿼리 선택 및 변환 규칙 적용을 공동으로 최적화하며, 커버리지 피드백을 통해 더 깊은 실행 경로를 탐색하여 코드 커버리지를 향상시키는 것을 목표로 합니다. 널리 사용되는 세 가지 DBMS와 네 가지 경량 LLM을 사용한 실험 결과, MIST는 기준 접근 방식에 비해 평균적으로 43.3%의 라인 커버리지 향상, 32.3%의 함수 커버리지 향상, 46.4%의 분기 커버리지 향상을 달성했으며, 최상의 라인 커버리지는 옵티마이저 모듈에서 69.3%를 기록했습니다.

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.