Detecting Logical Bugs of DBMS with Coverage-based Guidance

Yu Liang, Song Liu, Hong Hu. 2022. USENIX Security Symposium.

What this paper does with SQLancer

SQLRight is built on SQLancer and Squirrel, and two of its four oracles -- NoREC and TLP -- are ported from SQLancer directly. It then measures itself against SQLancer as the state-of-the-art oracle-based tool, reporting more bugs but acknowledging SQLancer's much higher query validity. SQLRight adds coverage-based guidance to logic-bug detection in DBMSs, arguing that oracle-driven tools generate queries from fixed rules and so explore a limited set of program states, while coverage-guided fuzzers find crashes but have no oracle for wrong results. It combines a coverage-guided mutation engine with validity-preserving mutation that keeps the clauses an oracle needs, and adds non-determinism mitigation. Over 72 hours it reported 12 unique logic bugs where the tools it compares against found one and none respectively. Written by claude-opus-5 from the 83 places this paper refers to SQLancer. The quotations below are the paper's own words, stored verbatim when the text was extracted.

How it was classified

uses infrastructure — yes (implementation)

M28 states the implementation is based on Squirrel and SQLancer, and M29 that two of its four oracles, NoREC and TLP, are ported from SQLancer. The artifact carries SQLancer source content, which agrees.

Our implementation is based on Squirrel [71] and SQLancer [30]. M28 · 3.1.4 Non-determinism Mitigation · page 8

Currently, SQLRight supports four oracles, including NoREC and TLPported from SQLancer [43, 44], and Index and Rowid we propose in this paper. M29 · 3.1.4 Non-determinism Mitigation · page 8

extends technique — yes

Porting NoREC and TLP is reuse; what makes it extension is that the mutation engine is adapted to preserve the clauses those oracles require (M18, M20), so the oracles run under coverage guidance rather than rule-based generation. The paper proposes two further oracles of its own alongside them.

Non-optimizing Reference Engine Construction (NoREC)Ternary Logic Partitioning (TLP)

To support the NoREC oracle, we fix SELECT_statement ,FROM and WHERE of the statement and leave others for the mutation engine to change. M18 · 3.1.1 Cooperative Mutation · page 6

As a result, the crucial components for oracle NoREC are preserved. M20 · 3.1.1 Cooperative Mutation · page 6

Currently, SQLRight supports four oracles, including NoREC and TLPported from SQLancer [43, 44], and Index and Rowid we propose in this paper. M29 · 3.1.4 Non-determinism Mitigation · page 8

compares with — yes

SQLancer is one of two tools SQLRight is measured against over 72 hours, using NoREC and TLP as the shared oracles, with bug counts and coverage reported for each.

Non-optimizing Reference Engine Construction (NoREC)Ternary Logic Partitioning (TLP)

We also compare our system with the stateof-the-art tools, including SQLancer (using oracles to detect logical bugs) and Squirrel (using code coverage to detect crashes and assertion failures). M8 · 1 Introduction · page 3

After testing for 72 hours, SQLRight reports 12 unique logical bugs, Squirrel detects one bug, and SQLancer does not find any bug. M9 · 1 Introduction · page 3

Therefore, we use NoREC and TLPto compare SQLRight ,SQLancer, and Squirrel +oracle. M44 · 5.1 DBMS Logical Bugs · page 10

Squirrel +oracle merely found 1 bug, which is from SQLite using NoREC; SQLancer did not find any logical bug. M48 · 5.1 DBMS Logical Bugs · page 10

Overall, SQLRight can find more logical bugs than SQLancer andSquirrel +oracle. M58 · 5.1 DBMS Logical Bugs · page 11

describes as state of the art — yes

Both call SQLancer one of the state-of-the-art bug-finding tools for DBMSs.

For Q2, we compare SQLRight with SQLancer and Squirrel, the state-of-the-art bug-finding tools for DBMSs. M33 · 3.1.4 Non-determinism Mitigation · page 9

What could not be determined

Whether the ported oracles were modified beyond what the mutation engine required is not stated in the mentions.

Its artifact

PSU-Security-Universe/sqlright-artifact carries sqlancer source content match.

Repository names this paper.
Artifact Evaluation code for USENIX 2022 paper: Detecting Logical Bugs of DBMS with Coverage-based Guidance # sqlright-artifact: The code, analysis scripts and results for USENIX 2022 Artifact Evaluation
source

MySQL/docker/sqlancer/sqlancer/src/sqlancer/Randomly.java is SQLancer's Randomly.java (8 of 8 identifiers match: StringGenerationStrategy, SOPHISTICATED, cachedLongs, cachedStrings, cachedDoubles).
private static StringGenerationStrategy stringGenerationStrategy = StringGenerationStrategy.SOPHISTICATED;
source

SQLancer publications it cites (6)

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
30	Manuel Rigger. SQLancer. https://github.com/sqlancer/ sqlancer. (visited in June 2021).	sqlancer publication
42	Manuel Rigger. Bugs Found in Database Management Systems. https: //www.manuelrigger.at/dbms-bugs/. (visited in June 2021).	project authored
43	Manuel Rigger and Zhendong 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...	sqlancer publication · NOREC
44	Manuel Rigger and Zhendong Su. Finding Bugs in Database Systems via Query Partitioning. Proceedings of the ACM on Programming Languages, 4(OOPSLA):1–30, 2020.	sqlancer publication · TLP
45	Manuel Rigger and Zhendong Su. Testing Database Engines via Pivoted Query Synthesis. In Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI), Virtual, 2020.	sqlancer publication · PQS
71	Rui Zhong, Yongheng Chen, Hong Hu, Hangfan Zhang, Wenke Lee, and Dinghao Wu. SQUIRREL: Testing Database Management Systems with Language Validity and Coverage Feedback. In Proceedings of the 27th ACM Conference on Com...	sqlancer publication

Every place it refers to SQLancer (83)

83 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	Although many efforts have been spent on testing DBMS systems [10, 58, 70, 71], most of them focus on finding crashes and assertion failures that finally make the execution terminate accidentally.	citation marker	1 Introduction page 2
M2	Recent progress on DBMS oracles shed light on logical bug detection [43 –45].	citation marker	1 Introduction page 2
M3	SQLancer, the tool that implements these oracles, has successfully found many logical bugs [30, 42].	name background	1 Introduction page 2
M4	However, SQLancer relies on a rule-based generator to synthesize original queries, which may limit its capability to explore program states.	name motivation	1 Introduction page 2
M5	Previous works applied coverage-guided fuzzing to test DBMSs and demonstrated the benefits of detecting memory-related bugs [10, 60, 71].	citation marker	1 Introduction page 2
M6	Currently, most fuzzers use one parser to handle different DBMS systems [10, 71].	citation marker	1 Introduction page 3
M7	We implemented four oracles, including two proposed in previous works [43, 44] and two proposed in this paper.	citation marker	1 Introduction page 3
M8	We also compare our system with the stateof-the-art tools, including SQLancer (using oracles to detect logical bugs) and Squirrel (using code coverage to detect crashes and assertion failures).	name baseline	1 Introduction page 3
M9	After testing for 72 hours, SQLRight reports 12 unique logical bugs, Squirrel detects one bug, and SQLancer does not find any bug.	name result comparison	1 Introduction page 3
M10	Recent works construct functionally equivalent queries and check whether the DBMS produces the same result for all queries [43 –45].	citation marker	2.1 An Example Logical Bug page 4
M11	For example, for a given query, oracle NoREC shifts all conditions from WHERE clauses to SELECT expressions, which effectively disables most optimizations applied to the original query [43].	technique definition	2.1 An Example Logical Bug page 4
M12	It combines the results from three subqueries and checks the equivalence with the original one [44].	citation marker	2.1 An Example Logical Bug page 4
M13	As oracles are built on high-level semantics instead of low-level implementations, we can use them to test multiple DBMS systems [30].	citation marker	2.1 An Example Logical Bug page 4
M14	We can implement oracle Index Mutation EngineValidation EngineResult AnalyzerSquirrelcode coverageSeed InputsCrash BugsDatabase Management SystemFigure 1: Overview of Squirrel [71].	citation marker	2.1 An Example Logical Bug page 4
M15	Recent works also ported coverage-guided fuzzing to test DBMS systems [21, 26, 60, 71].	citation marker	2.3 Coverage-guided Testing page 4
M16	Figure 1 shows an overview ofSquirrel [71], a recent work that aims to detect crashes and assertion failures from DBMS systems.	citation marker	2.3 Coverage-guided Testing page 4
M17	Recent fuzzers utilize typebased mutation and semantic-guided instantiation in order to produce valid queries [71].	citation marker	3.1 Validity-oriented Query Generation page 5
M18	To support the NoREC oracle, we fix SELECT_statement ,FROM and WHERE of the statement and leave others for the mutation engine to change.	technique reuse component	3.1.1 Cooperative Mutation page 6
M19	For example, oracle NoREC requires the SELECT statement to have both FROM clause and WHERE clause.	technique definition	3.1.1 Cooperative Mutation page 6
M20	As a result, the crucial components for oracle NoREC are preserved.	technique reuse component	3.1.1 Cooperative Mutation page 6
M21	The IR-based mutation engine supports various patterns and different conditions in the from_clause andwhere_clause, and thus provides rich capability comparable to the unconstrained mutator [71].	citation marker	3.1.1 Cooperative Mutation page 6
M22	3 Context-based IR Instantiation The previous work Squirrel [71] identifies data dependency among all SQL statements to help instantiate query operands, like table names and column names.	citation marker	3.1.3 Context-based IR Instantiation page 6
M23	For example, because oracle NoREC shifts conditions from WHERE to SELECT, it only appends SELECT statements that have a FROM clause and a WHERE clause (both clauses are optional for SELECT ).	technique definition	3.1.4 Non-determinism Mitigation page 7
M24	For example, oracle NoREC returns only one variant where the WHERE conditions in the original query are moved to the SELECT expressions.	technique	3.1.4 Non-determinism Mitigation page 7
M25	4314 31st USENIX Security Symposium USENIX Association API Basic NoREC TLP Index Rowid preprocess() check applicability basic basic remove UNIQUE INDEX basic attach_output() append random SELECT SELECT COUNT(*) FROM x WHERE x; basic basic basic transform() - expr: WHERE→SELECT /0→T∪F∪NULL insert CREATE INDEX add WIT...	technique	3.1.4 Non-determinism Mitigation page 7
M26	Our system currently supports four oracles: NoREC ,TLP,Index andRowid .	technique	3.1.4 Non-determinism Mitigation page 8
M27	We take special actions to handle oracle NoREC, as the new query form always generates one row for each record ( TRUE or FALSE based on the condition).	technique	3.1.4 Non-determinism Mitigation page 8
M28	Our implementation is based on Squirrel [71] and SQLancer [30].	name reuse implementation	3.1.4 Non-determinism Mitigation page 8
M29	Currently, SQLRight supports four oracles, including NoREC and TLPported from SQLancer [43, 44], and Index and Rowid we propose in this paper.	name reuse implementation	3.1.4 Non-determinism Mitigation page 8
M30	1) USENIX Association 31st USENIX Security Symposium 4315 ID DBMS Description Oracle D Status Fix Logical Bugs 1SQLite UNIQUE PARTIAL INDEX ,DISTINCT INDEX 5 fixed c2f940b 2SQLite JOIN and LIKELY/UNLIKELY NoREC 3 fixed 2363a14 3SQLite IN-early-out optimization TLP 2 fixed eb40248 4SQLite EXISTS (SELECT.	technique	3.1.4 Non-determinism Mitigation page 8
M31	) to IN NoREC 2 fixed 16252d7 5SQLite Misuse aggregate in ORDER BY NoREC 2 fixed 0d11d77 6SQLite Aggregate in ORDER BY NoREC 1 confirmed 7SQLite WITHOUT ROWID with DESC NoREC 7 fixed f65c929 8SQLite unordered WITHOUT ROWID table ROWID 2 fixed c21bc5a 9SQLite mixed table name and CTE NoREC 2 fixed 0f0959c 10SQLite in...	technique	3.1.4 Non-determinism Mitigation page 9
M32	To answer Q1, we use SQLRight to test three popular DBMS systems, SQLite ,MySQL andPostgreSQL, which are commonly used in previous works to evaluate bugfinding tools for DBMSs [21,43 –45,71].	citation marker	3.1.4 Non-determinism Mitigation page 9
M33	For Q2, we compare SQLRight with SQLancer and Squirrel, the state-of-the-art bug-finding tools for DBMSs.	name state of the art	3.1.4 Non-determinism Mitigation page 9
M34	Since SQLancer requires the particular SQLite version 3.	name baseline	3.1.4 Non-determinism Mitigation page 9
M35	SQLancer is a generation-based tool and does not require any seed input.	name background	3.1.4 Non-determinism Mitigation page 9
M36	Despite the different testing durations, we can find the similar pattern of bug numbers from previous works [43 –45, 71], where most bugs are from SQLite, and very few are from PostgreSQL.	citation marker	5.1 DBMS Logical Bugs page 9
M37	Most bugs are detected by NoREC, and other oracles detect one or two bugs.	technique	5.1 DBMS Logical Bugs page 9
M38	0 12 24 36 48 60 720123456Unique Bug (a)SQLite logical bugs 0 12 24 36 48 60 7201234Unique Bug (b)MySQL logcial bugs 0 12 24 36 48 60 722025303540Coverage (k) SQLRight Squirrel+ oracle SQLancer 0 12 24 36 48 60 722025303540Coverage (k) (c)SQLite code coverage 0 12 24 36 48 60 72100120140160180200Coverage (k) (d)MySQ...	name result comparison	5.1 DBMS Logical Bugs page 10
M39	SQLancer does not implement NoREC forMySQL, so we skip the evaluation.	name baseline	5.1 DBMS Logical Bugs page 10
M40	With validity-improvement techniques, SQLRight can detect bugs that Squirrel +oracle and SQLancer will miss.	name result comparison	5.1 DBMS Logical Bugs page 10
M41	SQLancer cannot detect this bug since it does not use aliases when generating SELECT statements.	name result comparison	5.1 DBMS Logical Bugs page 10
M42	2 Comparison with Existing Tools SQLancer contains three oracles, NoREC ,TLP, and PQS.	name definition	5.1 DBMS Logical Bugs page 10
M43	Both NoREC and TLPjust modify query statements to detect bugs, and SQLRight can easily support them using our general APIs.	technique	5.1 DBMS Logical Bugs page 10
M44	Therefore, we use NoREC and TLPto compare SQLRight ,SQLancer, and Squirrel +oracle.	name baseline	5.1 DBMS Logical Bugs page 10
M45	Since SQLancer does not support NoREC forMySQL, we skip this setting.	name baseline	5.1 DBMS Logical Bugs page 10
M46	Figure 5 ( NoREC ) and Figure 8 (TLP) in Appendix show the evaluation results.	technique	5.1 DBMS Logical Bugs page 10
M47	Based on Figure 5a b and Figure 8a b,SQLRight reports the most 12 bugs across all settings, including 6 SQLite bugs and 3 MySQL bugs using NoREC, and 2SQLite bugs and 1 MySQL bug using TLP.	technique	5.1 DBMS Logical Bugs page 10
M48	Squirrel +oracle merely found 1 bug, which is from SQLite using NoREC; SQLancer did not find any logical bug.	name result comparison	5.1 DBMS Logical Bugs page 10
M49	The empty outcome from SQLancer could be due to its extensive use in testing these DBMS systems [43 –45].	name result comparison	5.1 DBMS Logical Bugs page 10
M50	USENIX Association 31st USENIX Security Symposium 4317 0 4 8 12 16 20 240123456Unique Bug (a)bugs of SQLite (NoREC ) 0 4 8 12 16 20 240123Unique Bug (b)bugs of SQLite (TLP) 0 4 8 12 16 20 242025303540Coverage (k) (c)coverage of SQLite (NoREC ) 0 4 8 12 16 20 242025303540Coverage (k) (d)coverage of SQLite (TLP) SQLRi...	technique	5.1 DBMS Logical Bugs page 10
M51	a and b show the number of unique SQLite bugs found by NoREC and TLP; c and d show the average number of SQLite edges using NoREC and TLP.	technique	5.1 DBMS Logical Bugs page 11
M52	All tools fail to find any bug in PostgreSQL, indicating its good code quality observed by previous works [43–45, 71].	citation marker	5.1 DBMS Logical Bugs page 11
M53	Considering that SQLancer is a generation-based tester and has a high validity rate, the extra coverage of SQLRight over SQLancer mainly comes from the coverage-based guidance and full-featured per-DBMS parsers.	name result comparison	5.1 DBMS Logical Bugs page 11
M54	From Figure 5f g h and Figure 8f g h we can find that SQLancer achieves the highest query validity, where over 80% of all queries are valid for SQLite, 99% for MySQL, and over 28% for PostgreSQL.	name result comparison	5.1 DBMS Logical Bugs page 11
M55	This result is reasonable since SQLancer follows well-defined rules to generate SQL statements, leading to more valid queries.	name background	5.1 DBMS Logical Bugs page 11
M56	Another observation is that SQLancer can keep a consistent high validity rate for 72 hours.	name result comparison	5.1 DBMS Logical Bugs page 11
M57	SQLancer can generate more valid queries than others, but its efficiency varies over time.	name result comparison	5.1 DBMS Logical Bugs page 11
M58	Overall, SQLRight can find more logical bugs than SQLancer andSquirrel +oracle.	name result comparison	5.1 DBMS Logical Bugs page 11
M59	Although SQLancer produces high-quality queries, its lack of query diversity makes it less effective in finding new logical bugs.	name result comparison	5.1 DBMS Logical Bugs page 11
M60	We perform the unit tests using SQLite with NoREC and TLP.	technique	5.1 DBMS Logical Bugs page 11
M61	For both NoREC and TLP,SQLRight reports the most bugs, including 4 bugs using NoREC and 2 bugs using TLP.	technique	5.1 DBMS Logical Bugs page 11
M62	Using NoREC ,SQLRight dropand SQLRight savereport 2 bugs, and SQLRight randonly detects 1.	technique	5.1 DBMS Logical Bugs page 11
M63	Without code coverage, SQLRight did not find any logical bug using TLP.	technique	5.1 DBMS Logical Bugs page 11
M64	1K branches with NoREC and 39.	technique	5.1 DBMS Logical Bugs page 11
M65	2K branches with TLP.	technique	5.1 DBMS Logical Bugs page 11
M66	2K branches using NoREC and 35.	technique	5.1 DBMS Logical Bugs page 11
M67	0K branches using TLP, which are 13.	technique	5.1 DBMS Logical Bugs page 11
M68	In NoREC, besides the seed-triggered code (depth 0), 14.	technique	5.1 DBMS Logical Bugs page 11
M69	0% is triggered by queries with 8 or more mutations; in TLP, the contributions of high-depth queries are 18.	technique	5.1 DBMS Logical Bugs page 11
M70	5Coverage (k) (c)SQLite code coverage 0 4 8 12 16 20 24100120140160180200220Coverage (k) (d)MySQL code coverage 0 4 8 12 16 20 24020406080100120Coverage (k) (e)PostgreSQL code coverage 0 4 8 12 16 20 24203040506070Query Validity (%) (f)SQLite query validity 0 4 8 12 16 20 24010203040Query Validity (%) (g)MySQL query...	technique	5.1 DBMS Logical Bugs page 12
M71	Figure 7 ( NoREC ) and Figure 9 ( TLP) in Appendix show the results.	technique	5.4 Contribution of Validity page 12
M72	SQLRight triggers the most bugs,shown in Figure 7a b and Figure 9a b, including 4 bugs in SQLite using NoREC, 2 bugs in SQLite using TLP, 2 bugs in MySQL using NoREC, and 1 bug in MySQL using TLP.	technique	5.4 Contribution of Validity page 12
M73	SQLRight -db-par&ctx-valid andSquirrel +oracle merely find 1 bug using NoREC.	technique	5.4 Contribution of Validity page 12
M74	First, Squirrel parsers do not support custom functions in SELECT, including function COUNT, which is necessary to generate NoREC -compatible queries.	technique	5.4 Contribution of Validity page 12
M75	Second, these parsers do not support UNION ALL, which is the key component to implement compatible queries for TLP.	technique	5.4 Contribution of Validity page 12
M76	Since USENIX Association 31st USENIX Security Symposium 4319 DBMS Oracle FPs Main Reason SQLite NoREC SQLRight: 19 VIEW affinity, subquery ordering SQLRight -deter :42 randomblob andjulianday() func SQLite TLP SQLRight: 8 subquery ordering SQLRight -deter: 53 randomblob func MySQL NoREC SQLRight: 0SQLRight -deter :1...	technique	5.4 Contribution of Validity page 12
M77	PostgreSQL enforces the most rigorous syntax and semantic rules, it is hard to generate valid SQL queries [43 –45, 71].	citation marker	5.4 Contribution of Validity page 13
M78	We find that the affinity issue is commonly reported by third-party tools as “bugs”, including SQLancer [30].	name incidental	5.4 Contribution of Validity page 13
M79	Differential testing [29] is commonly used to detect logical bugs from DBMS systems [43 –45, 49, 61, 68].	citation marker	5.4 Contribution of Validity page 14
M80	SQLancer proposes the third direction, which constructs functionally equivalent queries to test one DBMS [43 –45].	name background	5.4 Contribution of Validity page 14
M81	This method requires a deep understanding of SQL and DBMS [30].	citation marker	5.4 Contribution of Validity page 14
M82	SQLsmith [58] is highly customized and effective for PostgreSQL [71].	citation marker	5.4 Contribution of Validity page 14
M83	The most recent work Squirrel translates SQL strings to an IR-based representation, and relies on the IR type to increase the validity of query generation [71].	citation marker	5.4 Contribution of Validity page 14

This page is rendered from _data/papers/paper_s2_77faa12e3aa52f3cb41009e9e8f65c79c9ef9f42.json, extracted from supplied pdf. 19 pages, 71 references parsed.