Conformance Testing of Relational DBMS Against SQL Specifications
Read the paper · arXiv:2406.09469
What this paper does with SQLancer
SQLancer is SEMCONT's generator, extended. The paper states it enhances the syntax-guided generation method, SQLancer, with coverage-guided test case generation, and uses it to produce the seed pool its algorithm works from. It then adds what SQLancer does not emit -- keywords and generation rules the tool lacked for particular systems -- reporting the results as SQLancer+ keyword syntax and SQLancer+ rule syntax, each measurably improving coverage. SQLancer is also the reference point for the comparison: TLP and NoREC are the state-of-the-art metamorphic methods it is measured against, run in both their SQLancer and SQLRight implementations.
SEMCONT tests whether a relational DBMS conforms to the SQL specification, rather than whether two systems or two queries agree. It derives expected behaviour from the standard and reports where an implementation departs from it, which reaches under-specified corners that differential and metamorphic oracles pass over because both sides of their comparison are equally wrong.
How it was classified
uses infrastructure — yes (generator)
M3 states the approach enhances SQLancer with coverage-guided generation, M7 that SQLancer is adopted to generate the seed pool, and M22 that missing features were added to SQLancer for particular systems. The generation is SQLancer's; the conformance oracle is the paper's own.
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.
Therefore, we add those missing features in SQLancer for the corresponding DBMS query generation and refer this as SQLancer + rule syntax.
extends technique — no
What is extended is SQLancer's generation -- keywords, rules, and coverage guidance -- not any of its oracles. The oracle here is conformance to the SQL specification.
compares with — yes
M9 states SEMCONT is compared with TLP and NoREC, M14 records both being run in their SQLancer and SQLRight implementations, and M17 reports SEMCONT finding bugs those approaches did not.
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.
, NoREC (SQLancer), NoREC (SQLRight), TLP (SQLancer) and TLP (SQLRight).
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.
describes as state of the art — yes
M4 calls SQLancer one of the most effective tools of its kind and the state-of-the-art practice in test case generation; M9 calls TLP and NoREC state-of-the-art metamorphic testing methods.
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 |