Semantic Conformance Testing of Relational DBMS
Read the paper · doi:10.14778/3712221.3712247 · arXiv:2406.09469
What this paper does with SQLancer
SEMCONT is built on SQLancer, whose syntax-guided generation it enhances with coverage guidance and uses as the seed pool for its own query generation. TLP and NoREC are then its baselines, described as state-of-the-art metamorphic testing methods and run in both their SQLancer and SQLRight implementations.
This paper introduces semantic conformance testing for relational DBMSs -- checking a system against the semantics of SQL rather than against another system. Two obstacles are identified: the standard is written in ambiguous natural language and is not executable, and it is hard to generate queries covering all its keywords and parameters. The authors formally define SQL's denotational semantics and implement them in Prolog as an executable reference, then add coverage criteria over those semantics and a coverage-guided generation algorithm. Across six widely used RDBMSs it uncovered 19 bugs and 13 inconsistencies, all confirmed.
How it was classified
uses infrastructure — yes (implementation)
M3 says the approach enhances SQLancer's syntax-guided generation with coverage guidance, and M7 that SQLancer is adopted to generate the seed pool the query generation works from.
Here, we 10 enhance the syntax-guided generation method, SQLancer [14], with coverage-guided test case generation.
We adopt SQLancer to randomly generatea large number of SQL statements (line 2), which serves as the seed pool of our query generation algorithm.
Both NoREC and TLP are implemented in SQLancer [14] and SQLRight [34].
extends technique — uncertain
M18 describes adding keywords and generation rules SQLancer did not support, which extends the tool's generator rather than one of the named oracles. Nothing shown claims to extend PQS, NoREC or TLP.
compares with — yes
TLP and NoREC are the baselines, run in both their SQLancer and SQLRight implementations.
Ternary Logic Partitioning (TLP)Non-optimizing Reference Engine Construction (NoREC)
We compared SEMCONT with TLP [41] and NoREC [40], which are state-of-the-art metamorphic testing methods for testing RDBMS.
Both NoREC and TLP are implemented in SQLancer [14] and SQLRight [34].
, NoREC (SQLancer), NoREC (SQLRight), TLP (SQLancer) and TLP (SQLRight).
describes as state of the art — yes
M9 calls TLP and NoREC state-of-the-art metamorphic testing methods for RDBMSs, and M4 describes syntax-guided random generation as the state-of-the-art practice.
Coverage guided test case generation The state-of-the-art practice in test case generation involves randomly generating SQL queries guided by the syntax of SQL, among which SQLancer [14] stands out as one of the most effective tools of this kind.
We compared SEMCONT with TLP [41] and NoREC [40], which are state-of-the-art metamorphic testing methods for testing RDBMS.
SQLancer publications it cites (4)
Bibliography entries that resolved to a SQLancer publication, or to a paper by one of the project's authors. A sentence citing one of these numbers is a reference to SQLancer even when it never writes the name.
| # | Entry | Matched as |
|---|---|---|
| 14 | “Sqlancer,” https://github.com/sqlancer/sqlancer, 2019, accessed on November 10, 2023. | sqlancer publication |
| 40 | M. Rigger and Z. Su, “Detecting optimization bugs in database engines via non-optimizing reference engine construction,” in Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Sym... | sqlancer publication · NOREC |
| 41 | M. Rigger and Z. Su, “Finding bugs in database systems via query partitioning,” Proceedings of the ACM on Programming Languages, vol. 4, no. OOPSLA, pp. 1–30, 2020. | sqlancer publication · TLP |
| 42 | M. Rigger and Z. Su, “Testing database engines via pivoted query synthesis,” in 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), 2020, pp. 667–682. | sqlancer publication · PQS |
Every place it refers to SQLancer (42)
42 sentences, each stored verbatim from the extracted text with where it was found and how. “Citation marker” means the sentence names no tool at all and was reached through a reference number that resolved to a SQLancer publication.
| Id | Sentence | Found by | Where |
|---|---|---|---|
| M1 | The serious impacts of bugs in RDBMS have been discussed by various existing studies [14], [34], [40], [41], and thus it is critical to detect those bugs. | citation marker | I INTRODUCTION page 2 |
| M2 | However, existing approaches on testing RDBMSs either use different RDBMSs as the test oracle [47] or propose metamorphic relations [34], [40]–[42]. | citation marker | I INTRODUCTION page 2 |
| M3 | Here, we 10 enhance the syntax-guided generation method, SQLancer [14], with coverage-guided test case generation. |
name |
A Overview of our approach page 9 |
| M4 | Coverage guided test case generation The state-of-the-art practice in test case generation involves randomly generating SQL queries guided by the syntax of SQL, among which SQLancer [14] stands out as one of the most effective tools of this kind. |
name |
B Coverage guided test case generation page 10 |
| M5 | SQLancer considers database objects, such as tables, views, and indexes, as well as keywords and functionalities within query statements. |
name |
B Coverage guided test case generation page 10 |
| M6 | Throughout the generation process, SQLancer maintains a set of keywords and functionalities, from which it randomly selects keywords to incorporate into the test cases, subject to syntactic rules of SQL (so that they remain syntactically valid). |
name |
B Coverage guided test case generation page 10 |
| M7 | We adopt SQLancer to randomly generatea large number of SQL statements (line 2), which serves as the seed pool of our query generation algorithm. |
name |
B Coverage guided test case generation page 11 |
| M8 | It is important to note that we used the latest release of each RDBMS, which has been extensively tested by existing approaches [40], [41]. | citation marker | A Experiment setup page 13 |
| M9 | We compared SEMCONT with TLP [41] and NoREC [40], which are state-of-the-art metamorphic testing methods for testing RDBMS. |
technique |
A Experiment setup page 14 |
| M10 | NoREC constructs two semantically equivalent queries, one triggers the optimization and the other does not, executes the queries and compare the results. |
technique |
A Experiment setup page 14 |
| M11 | TLP, on the other hand, partitions the conditional expression of the original query into three segments, corresponding to the three possible results, i. |
technique |
A Experiment setup page 14 |
| M12 | Both NoREC and TLP are implemented in SQLancer [14] and SQLRight [34]. |
name |
A Experiment setup page 14 |
| M13 | SQLancer adopts a generative approach for query generation and SQLRight adopts a mutation-based approach for generating queries. |
name |
A Experiment setup page 14 |
| M14 | , NoREC (SQLancer), NoREC (SQLRight), TLP (SQLancer) and TLP (SQLRight). |
name |
A Experiment setup page 14 |
| M15 | They are also under-specified in the SQL standard and insufficiently tested by existing approaches [34], [40]– [42]. | citation marker | B Experiment results page 14 |
| M16 | Moreover, they have been extensively tested by prior research [34], [40]–[42], making it more challenging to uncover new inconsistencies. | citation marker | B Experiment results page 14 |
| M17 | It is noteworthy that all four databases have been extensively tested by existing methods [40]–[42], yet SEMCONTis still able to detect bugs that were not detected by those approaches. | citation marker | B Experiment results page 14 |
| M18 | In Figure 9, SQLancer+ keyword syntax represents the setting of adding keywords and the corresponding generation rules which were not supported by SQLancer. |
name |
B Experiment results page 15 |
| M19 | SQLancer+ keyword syntax greatly improved the keyword coverage for all four databases. |
name |
B Experiment results page 15 |
| M20 | Keyword coverage guided query generation (SQLancer+ keyword coverage) further improves the keyword coverage, and achieved 100% keyword coverage within the first 200 generate queries for all databases, demonstrating the effectiveness of our keyword-guided query generation method. |
name |
B Experiment results page 15 |
| M21 | , data types, by SQLancer, especially for DBMS such as DuckDB and TiDB, relying only on SQLancer achieves low rule coverage, as shown in Figure 10. | name | B Experiment results page 15 |
| M22 | Therefore, we add those missing features in SQLancer for the corresponding DBMS query generation and refer this as SQLancer + rule syntax. | name | B Experiment results page 15 |
| M23 | Rule coverage-guided query generation (SQLancer+ rule coverage) achieves the highest rule coverage with the fewest number of queries. | name | B Experiment results page 15 |
| M24 | With SQLancer, which conducts random query generation, we observed that the increase in composite rule coverage tends to plateau after generating 60 million data points. | name | B Experiment results page 15 |
| M25 | Note that to conduct fair comparisons, we improved SQLancer by incorporating all keywords supported by our semantics and related generation rules in SEMCONT. | name | B Experiment results page 15 |
| M26 | We compare SEMCONT with two state-of-the-art approaches TLP [40] and NoREC [41], which are metamorphic testing approaches for relational DBMS. | technique | B Experiment results page 16 |
| M27 | For both approaches, we adopt SQLancer [14] and SQLRight [34] for query generation. | name | B Experiment results page 16 |
| M28 | Notably, SQLancer does not support the NoREC oracle for MySQL and TiDB, while SQLRight does not support TiDB, DuckDB and OceanBase. | name | B Experiment results page 16 |
| M29 | The experimental results show that both SQLancer and SQLRight using the NoREC as the oracle were unable to detect new bugs or inconsistencies. | name | B Experiment results page 16 |
| M30 | The TLP oracle with SQLancer for query generation detected 4 bugs in three databases, and with SQLRight for query generation detectd 1 bug in MySQL. | name | B Experiment results page 16 |
| M31 | Both TLP and NoREC failed to detect this bug, even after successfully generated the bug triggering query. | technique | B Experiment results page 16 |
| M32 | 3 million test cases for SQLancer, and 30 hours and 8. | name | B Experiment results page 16 |
| M33 | Our approach finds more bugs/inconsistencies 17 TABLE VI: The bugs and inconsistencies detected by SQLancer, SQLRight and SEMCONT in 6h DBMSTLP (SQLancer) NoREC (SQLancer) TLP (SQLRight) NoREC (SQLRight) SEMCONT Bugs Inconsistencies Bugs Inconsistencies Bugs Inconsistencies Bugs Inconsistencies Bugs Inconsistencies ... | name | B Experiment results page 16 |
| M34 | 12: The memory consumption of SEMCONT with SQLancer. | name | B Experiment results page 17 |
| M35 | Figure 12 and Figure 13 shows the memory usage of SEMCONT and SQLancer during a 6-hour test on six databases. | name | B Experiment results page 17 |
| M36 | The paper sets this passage with letter-spacing, which extraction cannot undo — the sentence is there, but no readable form of it is. | name | B Experiment results page 17 |
| M37 | Numerous testing methods involve constructing a test oracle by proposing a variety of metamorphic relations [21], [28], [40]–[42]. | citation marker | VI RELATED WORK page 19 |
| M38 | In recent years, SQLancer [14] has emerged as the most effective black-box fuzz testing tool, distinguished by its adoption of three complementary oracles [40]–[42]. | name | VI RELATED WORK page 19 |
| M39 | PQS [42] operates by first selecting a row of data, and then synthesizing a query based on this selected data. | technique | VI RELATED WORK page 19 |
| M40 | NoREC [40] transforms an optimized SQL query into an equivalent non-optimized version and then compares the execution results of both. | technique | VI RELATED WORK page 19 |
| M41 | TLP [41] divides a SQL query into three separate SQL statements that collectively retain the same semantics as the original query. | technique | VI RELATED WORK page 19 |
| M42 | SQLRight [34] focuses on enhancing the semantic correctness of generated SQL queries and adopts the oracles proposed by PQS [42], NoREC [40], and TLP [41]. | technique | VI RELATED WORK page 19 |