Pinolo: Detecting Logical Bugs in Database Management Systems with Approximate Query Synthesis
What this paper does with SQLancer
Pinolo positions itself directly against SQLancer's oracles: PQS is the oracle-guided synthesis it says considers only one row at a time, NoREC and TLP are the metamorphic approaches it says preserve too much of the query, and it states that metamorphic testing of that kind is recognised as the state of the art in DBMS logical bug detection.
Pinolo detects logical bugs in DBMSs by approximate query synthesis: rather than constructing an exactly equivalent query, it mutates a query into one whose result set must be a superset or subset of the original, and reports a violation of that containment as a bug. The authors survey three existing categories -- differential testing, oracle-guided synthesis, and metamorphic testing -- and argue each is limited, the last because its transformations preserve all operators and so miss certain bugs. Pinolo covers more SQL features than those techniques, including set operators, arithmetic expressions and sub-queries.
How it was classified
uses infrastructure — no
Nothing shown says Pinolo is built on SQLancer's codebase.
extends technique — no
Approximate query synthesis relaxes equivalence to containment, which the paper presents as an alternative to the metamorphic approaches rather than a generalisation of one.
compares with — yes
M13 shows a bug NoREC and TLP cannot reveal and M14 states Pinolo covers more SQL features than those techniques, so they are the approaches it measures itself against.
Pivoted Query Synthesis (PQS)Non-optimizing Reference Engine Construction (NoREC)Ternary Logic Partitioning (TLP)
For example, the logical bug shown in Figure 1 can not be revealed by NOREC [34] and TLP [35], as the transformations preserve all the operators and the functions, still triggering the buggy evaluation process.
Compared with the existing techniques [ 34–36],PINOLO considers more SQL features, such as set operators, arithmetic expressions, sub-queries, etc.
describes as state of the art — yes
M10 states the metamorphic testing based approach, citing TLP, has been recognised as state-of-the-art in DBMS testing for logical bug detection.
Notably, the metamorphic testing based approach has been recognized to be state-of-the-art in DBMS testing for logical bug detection [ 35,37].
SQLancer publications it cites (5)
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 |
|---|---|---|
| 33 | Manuel Rigger. sqlancer. https://github.com/ sqlancer/sqlancer, 2022. [Online; accessed Jan2023]. | sqlancer publication |
| 34 | Manuel Rigger and Zhendong Su. Detecting optimization bugs in database engines via non-optimizing reference engine construction. In 28th ACM Joint European Software Engineering Conference and Symposium on the Foundati... | sqlancer publication · NOREC |
| 35 | Manuel Rigger and Zhendong Su. Finding bugs in database systems via query partitioning. Proc. ACM Program. Lang., 4(OOPSLA):211:1–211:30, 2020. USENIX Association 2023 USENIX Annual Technical Conference 357 | sqlancer publication · TLP |
| 36 | Manuel Rigger and Zhendong Su. Testing database engines via pivoted query synthesis. In 14th USENIX Symposium on Operating Systems Design and Implementation, pages 667–682. USENIX Association, 2020. | sqlancer publication · PQS |
| 37 | Manuel Rigger and Zhendong Su. Intramorphic testing: A new approach to the test oracle problem. In Proceedings of the 2022 ACMSIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming... | project authored |
Every place it refers to SQLancer (35)
35 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 | Therefore, DBMS testing has attracted considerable attention in the industry [ 14,23,38,41] and academia [ 10,34–36]. |
citation marker |
1 Introduction page 2 |
| M2 | However, as pointed out by the existing studies [ 34,36,39], differential testing cannot be applied when a generated SQL query cannot comply with the grammar of all selected DBMSs or contains operations that have different semantics between different DBMSs. |
citation marker |
1 Introduction page 2 |
| M3 | The second category is the oracle-guided synthesis approach [ 36], which does not rely on multiple DBMSs and thus mitigates the limitation of differential testing. |
citation marker |
1 Introduction page 2 |
| M4 | However, since such an approach considers only one row each time and the synthesis merely focuses on the where clause generation, it would miss logical bugs in various scenarios [ 34,35]. |
citation marker |
1 Introduction page 2 |
| M5 | Moreover, as pointed out by some recent studies [34,35], the synthesis requires domain knowledge of the database dialect’s supported operators and functions, and thus the implementation effort is high. |
citation marker |
1 Introduction page 2 |
| M6 | USENIX Association 2023 USENIX Annual Technical Conference 345 The third category is the metamorphic testing based approach [ 34,35]. |
citation marker |
1 Introduction page 2 |
| M7 | For example, TLP [35] decomposes a query qinto three partitioning sub-queries, each of which computes the result sets for a boolean predicate to be evaluated as TRUE ,FALSE, and NULL, respectively, and then constructs an equivalent query q′ by performing the union operation on these three sub-queries. |
technique |
1 Introduction page 3 |
| M8 | NOREC [34] transforms an optimized version of a query into a non-optimized one by the customized rule, e. |
technique |
1 Introduction page 3 |
| M9 | ” Compared with the aforementioned two categories of approaches, metamorphic testing based approaches are much more lightweight to implement and have been proven to be more effective in detecting logical bugs [ 34,35]. |
citation marker |
1 Introduction page 3 |
| M10 | Notably, the metamorphic testing based approach has been recognized to be state-of-the-art in DBMS testing for logical bug detection [ 35,37]. |
citation marker |
2.2 Logical Bugs in DBMSs page 4 |
| M11 | For example, NOREC [34] transforms a query into a form in which the DBMS does not apply optimizations, which yields the test oracle that the two queries should make the tested DBMS return the same result. |
technique |
2.2 Logical Bugs in DBMSs page 4 |
| M12 | Besides, TLP [35] gets the equivalent query result by splitting the input query into several sub-queries and merging the results of sub-queries into one. |
technique |
2.2 Logical Bugs in DBMSs page 4 |
| M13 | For example, the logical bug shown in Figure 1 can not be revealed by NOREC [34] and TLP [35], as the transformations preserve all the operators and the functions, still triggering the buggy evaluation process. |
technique |
2.2 Logical Bugs in DBMSs page 4 |
| M14 | Compared with the existing techniques [ 34–36],PINOLO considers more SQL features, such as set operators, arithmetic expressions, sub-queries, etc. |
citation marker |
3.5 Summary page 8 |
| M15 | Following the best practice summarized in the prior study [ 36], we restrict the number of table records to be no more than 30. | citation marker | 4 Implementation page 8 |
| M16 | They are also commonly used in the evaluation of previous studies [ 34–36]. | citation marker | 5.1 Experiment Setup page 9 |
| M17 | We compared PINOLO with the three state-ofthe-art logical bug detection techniques, namely PQS [ 36], NOREC [34], and TLP [35], respectively, which correspond to three kinds of test oracles. | technique | 5.1 Experiment Setup page 9 |
| M18 | 352 2023 USENIX Annual Technical Conference USENIX Association 024681012141618202224 Testing Time(h)0246810121416Unique Bug (a) MySQLPINOLO TLP 024681012141618202224 Testing Time(h)0246810121416Unique Bug (b) MariaDBPINOLO NoREC 024681012141618202224 Testing Time(h)024681012Unique Bug (c) TiDBPINOLO TLP 024681012141... | technique | 5.1 Experiment Setup page 9 |
| M19 | 1K 2,722,881 2021 Table 3: Applicability of existing logical detection techniques and PINOLO for the selected DBMSs DBMSPQS NOREC TLP PINOLO MySQL ✓ × ✓ ✓ MariaDB × ✓ × ✓ TiDB × × ✓ ✓ OceanBase ✓ ✓ ✓ ✓ 5. | technique | 5.1 Experiment Setup page 10 |
| M20 | , PQS, NOREC, and TLP. | technique | 5.3 Comparisons on Detecting Logical Bugs page 10 |
| M21 | For MySQL, PINOLO detected 14 logical bugs, while TLP only discovered 2 bugs. | technique | 5.3 Comparisons on Detecting Logical Bugs page 10 |
| M22 | For MariaDB, PINOLO detected 14 bugs, while NOREC discovered 10 bugs. | technique | 5.3 Comparisons on Detecting Logical Bugs page 10 |
| M23 | For TiDB, PINOLO detected 11 bugs, while TLP only discovered 2 bugs. | technique | 5.3 Comparisons on Detecting Logical Bugs page 10 |
| M24 | For MariaDB, 4 out of 10 bugs detected by NOREC can also be found by PINOLO. | technique | 5.3 Comparisons on Detecting Logical Bugs page 10 |
| M25 | For TiDB, 1 out of 2 bugs detected by TLP can also be found by PINOLO. | technique | 5.3 Comparisons on Detecting Logical Bugs page 10 |
| M26 | There are no bugs detected by PQS. | technique | 5.3 Comparisons on Detecting Logical Bugs page 10 |
| M27 | For MySQL, the improvement of PINOLO over PQS and TLP is 2. | technique | 5.3 Comparisons on Detecting Logical Bugs page 11 |
| M28 | For MariaDB, the improvement of PINOLO over NOREC is 12. | technique | 5.3 Comparisons on Detecting Logical Bugs page 11 |
| M29 | This result indicates that the logical bugs are typically difficult and slow to be found, which is also consistent with the findings of the prior study [35]. | citation marker | 5.5 Discussion page 12 |
| M30 | However, we believe that it is non-trivial to detect new bugs in these selected DBMSs, as they have been thoroughly tested by SQLancer [ 33]. | name | 6 Threats to Validity page 12 |
| M31 | Most of them target discovering logical bugs in the relational DBMS [ 34–36]. | citation marker | 7 Related Work page 13 |
| M32 | It has been used in testing many software systems, such as compilers [ 16,50], SMT solvers [ 48,54], DBMSs [ 35,36], and AI systems [ 2,47,55]. | citation marker | 7 Related Work page 13 |
| M33 | Therefore, it is able to detect insightful logical bugs that existing approaches, such as NOREC [34] and TLP [35], fail to discover. | technique | 7 Related Work page 13 |
| M34 | It has been widely used in testing many real-world software systems, such as browsers [ 45], compilers [ 51], and DBMSs [ 36,57]. | citation marker | 7 Related Work page 13 |
| M35 | We do think it is also promising to utilize existing grammar fuzzing techniques to enumerate initial seed queries automatically [ 36,57], which can provide more opportunities for improving the coverage in the DBMS testing. | citation marker | 7 Related Work page 13 |