一句话：提出 DBStorm，以冲突图为核心黑盒生成多样有效负载测试数据库隔离级别，发现 33 个真实缺陷。
隔离级别是应用与数据库之间的正确性契约，实现有误会导致错误的事务执行结果与数据库状态。现有工作难以高效生成多样且有效的工作负载来测试隔离级别，核心挑战包括：(a) 黑盒测试，需触发闭源 DBMS 的隔离级别代码；(b) 有效测试，需规避冗余无效测试；(c) 异常敏感测试，需以可区分方式测试各隔离级别。作者调研 15 个流行 DBMS 的隔离级别实现，发现它们遵循通用框架：用冲突图管理负载中的所有冲突，并执行验证策略预防不可串行化异常。据此提出轻量的数据状态镜像方法，生成精确访问预期记录并参与特定冲突图形成的 SQL 操作；提出与历史无关的高效冲突图生成方法，保证图生成开销与历史图规模无关；并提出基于植入的方法，按异常定义编排冲突记录访问并注入不同事务。实验表明该方法在测试有效性、效率与覆盖率上优于已有方法，并在流行 DBMS 中成功发现 33 个缺陷。
Isolation level (IL) acts as a correctness contract between applications and DBMSs. Problematic IL implementations would cause incorrect transaction execution results and erroneous database states. However, existing studies could not efficiently generate various effective workloads for IL test. The core challenges come from the requirements of (a) black-box testing (trigger the IL code of a closed source DBMS), (b) effective testing (evade redundant and ineffective testing), and (c) anomaly-sensitive testing (test various ILs in a distinguishable way). For black-box testing, we investigate the IL implementations of 15 popular DBMSs and discover that they follow a generic framework that utilizes conflict graphs to manage all conflicts of a workload, and performs a verification policy to prevent non-serializable anomalies. For effective testing, we propose a lightweight data state mirroring method, which helps generate SQL operations that precisely access its expected records and participate the formation of specific conflict graphs. We also propose an efficient history-independent approach to generate dissimilar conflict graphs. It guarantees the graph generation overhead is irrelevant to the scale of historical graphs. For anomaly-sensitive testing, we propose an implantation-based approach to orchestrate conflict record accesses and inject them into different transactions according to the anomaly definition. Our approach outperforms existing approaches in testing effectiveness, efficiency, and coverage. Practically, we have successfully found 33 bugs in popular DBMSs.
@inproceedings{paperbot8611,
title = {DBStorm: Generating Various Effective Workloads for Testing Isolation Levels},
author = {Keqiang Li and Siyang Weng and Lyu Ni and Chengcheng Yang and Rong Zhang and Xuan Zhou and Aoying Zhou},
booktitle = {ISSTA},
year = {2024},
doi = {10.1145/3650212.3680318}
}