Detecting Logic Bugs in Database Engines via Equivalent Expression Transformation
Talkat 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI '24) · 2024-07-10..07-12·
summary
Proposes equivalent expression transformation that rewrites expressions (using CASE-based rewrites and boolean identities) so semantics stay the same while avoiding dependence on SQL dialects or query patterns. Implements the approach against MySQL, PostgreSQL, SQLite, ClickHouse and TiDB and finds 66 unique bugs, 35 producing incorrect results, many in subqueries and joins and some present for years (longest 20). Provides an open source tool and CI-ready tests that generate semantically equivalent queries and compare outputs.
AI-written summary · about
chapters (10)
- 0:00Database engine reliability
- 1:47Reliability issues and goals
- 2:53SQL testing challenges
- 4:00SQL result validation
- 5:49Semantic-preserving transformation
- 7:17Expression analysis for transformation
- 9:29Case expressions and logic
- 10:14Expression transformation examples
- 11:47Bug detection results
- 13:10Bug types and issues
related talks
11mDetecting Transactional Bugs in Database Engines via Graph-Based Oracle Construction
18mValScope: Value-Semantics-Aware Metamorphic Testing for Detecting Logical Bugs in DBMSs
20mVeriEQL: Bounded Equivalence Verification for Complex SQL Queries with Integrity(…)
19mPinolo: Detecting Logical Bugs in Database Management Systems with Approximate...
15mFinding Bugs in Database Systems via Query Partitioning
20mGraphiti: Bridging Graph and Relational Database Queries
17mFinding Cross-rule Optimization Bugs in Datalog Engines
10mHow to test software without writing tests