Sembug: Detecting Logic Bugs in Dbms Through Generating Semantic-Aware Non-Optimizing Query

← Research building on SQLancer

Shiyang Ye, Chao Ni, Jue Wang, Qianqian Pang, Xinrui Li, Xiaodan Xu. 2025. IEEE International Conference on Program Comprehension.

Read the paper · doi:10.1109/icpc66645.2025.00021

What this paper does with SQLancer

SemBug is a direct descendant of NoREC: it says it transforms the optimized query into a less optimized one 'inspired by NoREC', and its evaluation treats NoREC, TLP and Pinolo as the state-of-the-art techniques to beat. It also runs on SQLancer's own machinery, using it as the query generator, and its artifact carries SQLancer's source under a renamed package. SemBug detects logic bugs in DBMSs by transforming a query the optimizer can work on heavily into an equivalent but less optimized form and comparing the results. The authors divide prior work in two: approaches that target optimization bugs but check only the cardinality of the result, and approaches that check content as well but handle optimization bugs poorly. SemBug aims to cover both by adding semantic analysis to non-optimizing query construction, which also lets it test features such as aggregates and ORDER BY. It was evaluated on five widely used DBMSs against three baselines. Written by claude-opus-5 from the 84 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 (generator)

The paper states it uses SQLancer as its query generator, and notes that SemBug could be integrated with any generation technique -- so SQLancer supplies a component rather than the whole framework. The artifact carries SQLancer's source under a renamed package, which agrees.

We use SQLancer [29], a rule-based method for query generation. M23 · B Database and Query Generation · page 4

It is noted that although we only use SQLancer to generate queries, SemBug can be integrated with any generation technique. M25 · B Database and Query Generation · page 4

Specifically, NoREC, TLP, and SemBug employ SQLancer [29] as the query generator, while Pinolo uses Go-Randgen [30]. M31 · A Experimental Setup · page 6

extends technique — yes

M26 states the transformation is inspired by NoREC and describes the same WHERE-to-SELECT rewrite, extended to preserve semantic information rather than only cardinality. That extension is the paper's contribution, not a baseline.

Non-optimizing Reference Engine Construction (NoREC)

Inspired by NoREC, we transform the optimized query to the less optimized one of the form SELECT 𝛼, P is true AS flag FROM t through moving WHERE clause after the SELECT clause. M26 · C Transform the Query and Retrieve Semantic Information · page 4

compares with — yes

NoREC and TLP are two of the three baselines SemBug is measured against, run on the same query generator.

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

3)Baselines: We compare SemBug against the state-ofthe-art logic bug detection techniques, namely NoREC [18], TLP [10], and Pinolo [19], respectively. M30 · A Experimental Setup · page 6

Specifically, NoREC, TLP, and SemBug employ SQLancer [29] as the query generator, while Pinolo uses Go-Randgen [30]. M31 · A Experimental Setup · page 6

describes as state of the art — yes

M30 calls NoREC, TLP and Pinolo 'the state-of-the-art logic bug detection techniques'.

3)Baselines: We compare SemBug against the state-ofthe-art logic bug detection techniques, namely NoREC [18], TLP [10], and Pinolo [19], respectively. M30 · A Experimental Setup · page 6

Where this differs from the pattern checks

The regular expressions that scan for these relationships are advisory. Where the reading above contradicts one, the reason is recorded.

Its artifact

Syang111/SemBug carries renamed sqlancer package, sqlancer source content match.

Repository is named after Sembug, the tool this paper says it built, and is about database testing.
# SemBug
source

src/Sonar/Randomly.java is SQLancer's Randomly.java, with the package renamed to Sonar (8 of 8 identifiers match: StringGenerationStrategy, SOPHISTICATED, cachedLongs, cachedStrings, cachedDoubles).
private static StringGenerationStrategy stringGenerationStrategy = StringGenerationStrategy.SOPHISTICATED;
source

SQLancer publications it cites (8)

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
5	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
10	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
15	J. Ba and M. Rigger, “Keep it simple: Testing databases via differential query plans,” 2, no. 3, may 2024. [Online]. Available: https://doi.org/10.1145/3654991	sqlancer publication · DQP
18	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
29	M. Rigger, “Sqlancer,” https://github.com/sqlancer/sqlancer, 2024, accessed: 2024-03-30.	sqlancer publication
33	J. Ba and M. Rigger, “Testing database engines via query plan guidance,” in (ICSE), 2023, pp. 2060–2071.	sqlancer publication · QPG
35	Z.-M. Jiang, S. Liu, M. Rigger, and Z. Su, “Detecting transactional bugs in database engines via Graph-Based oracle construction,” in 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23). Bos...	project authored
40	J. Ba and M. Rigger, “Cert: Finding performance issues in database systems through the lens of cardinality estimation,” 2024.	sqlancer publication · CERT

Every place it refers to SQLancer (84)

84 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	, Pinolo, TLP, and NoREC).	technique	page 1
M2	Consequently, DBMS testing has become an area of considerable interest for researchers [4]–[10].	citation marker	I Introduction page 1
M3	The majority of logic bugs originate from issues within the query optimizer [15], which is acknowledged as one of the most complex components of a DBMS.	citation marker	I Introduction page 1
M4	To tackle this challenge, researchers have proposed several DBMS oracles [5], [10], [17]–[19] for the automatic detection of logic bugs, including differential testing-based methods, oracle-guided methods, and metamorphic testing-based methods.	citation marker	I Introduction page 1
M5	introduced PQS [5], a technique that begins by randomly selecting a specific row from a table.	technique definition	I Introduction page 1
M6	Although PQS has been successful in detecting logic bugs in widely-used DBMSs, its most significant drawback is the considerable implementation effort required, involving the re-implementation of each function and operator for each tested DBMS.	technique motivation	I Introduction page 1
M7	, such as NoREC [18]), while the second one addresses both cardinality-incorrect logic bugs and semantic logic bugs, where the cardinality remains consistent, but the content of the results is not as expected.	technique background	I Introduction page 2
M8	, Pinolo [19] and TLP [10]).	technique background	I Introduction page 2
M9	, TLP and Pinolo) in the second group are optimization-related bugs, which indicates that we should pay more attention to these types of logic bugs.	technique motivation	I Introduction page 2
M10	, NoREC), though it is designed to specifically address the logic bugs within optimization scenarios, it takes no consideration of semantical logic bugs and has no support for testing advanced DBMS features (e.	technique motivation	I Introduction page 2
M11	Among these issues, logic bugs, which cause a query to return unexpected outcomes [5], stand out as particularly elusive, often hidden deep within the core functionalities of a DBMS [19].	citation marker	A Logic Bugs in DBMS page 2
M12	Logic bugs that originate from the query optimizer are commonly referred to as optimization bugs [18].	citation marker	B Optimization Bugs Detection in DBMS page 2
M13	[18] proposed NoREC, which restructures SQL statements to inhibit query 125 SELECT t0.	technique definition	B Optimization Bugs Detection in DBMS page 2
M14	This particular bug cannot be detected by NoREC, as it only identifies bugs resulting from inconsistent cardinality.	technique motivation	B Optimization Bugs Detection in DBMS page 3
M15	TLP and Pinolo cannot detect this optimization bug either.	technique motivation	B Optimization Bugs Detection in DBMS page 3
M16	Though NoREC performs effectively in detecting bugs, it ignores checking the results content, leading to missing semantic unmatched logic bugs and consequently limiting supporting advanced DBMS features (e.	technique motivation	B Optimization Bugs Detection in DBMS page 3
M17	, TLP [10] and Pinolo [19]) can detect optimization logic bugs even though they are not specifically designed for them.	technique background	B Optimization Bugs Detection in DBMS page 3
M18	In particular, TLP [10] decomposes a query into three sub-queries, and each sub-query has a predicate evaluated as TRUE, FALSE, or NULL.	technique definition	B Optimization Bugs Detection in DBMS page 3
M19	Nevertheless, the practical utility of both TLP and Pinolo in identifying optimization bugs remains limited.	technique motivation	B Optimization Bugs Detection in DBMS page 3
M20	This issue shows a significant limitation of NoREC, which concentrates only on the cardinality of results, thereby missing such semantic discrepancies.	technique motivation	C Motivating Example page 3
M21	Similarly, TLP and Pinolo do not thoroughly investigate optimization bugs, which can lead to overlooked logic bugs.	technique motivation	C Motivating Example page 3
M22	Common methods for generating databases and queries include mutation-based [6], [9] and rule-based approaches [11], [29], [30].	citation marker	B Database and Query Generation page 4
M23	We use SQLancer [29], a rule-based method for query generation.	name reuse component	B Database and Query Generation page 4
M24	This is because most optimization techniques are applied to data filtering, typically expressed in the query’s WHERE clause [18].	citation marker	B Database and Query Generation page 4
M25	It is noted that although we only use SQLancer to generate queries, SemBug can be integrated with any generation technique.	name reuse component	B Database and Query Generation page 4
M26	Inspired by NoREC, we transform the optimized query to the less optimized one of the form SELECT 𝛼, P is true AS flag FROM t through moving WHERE clause after the SELECT clause.	technique extension	C Transform the Query and Retrieve Semantic Information page 4
M27	NoREC cannot directly test the aggregate function because it relies on the principle that the number of records returned by two queries should match the number of records satisfying the WHERE condition.	technique motivation	E Supporting Features page 5
M28	NoREC does not support the verification of semantic information, it is incapable of testing the sorting order specified by ORDER BY.	technique motivation	E Supporting Features page 5
M29	They have also been thoroughly tested in previous work [10], [18], [19], [31].	citation marker	A Experimental Setup page 6
M30	3)Baselines: We compare SemBug against the state-ofthe-art logic bug detection techniques, namely NoREC [18], TLP [10], and Pinolo [19], respectively.	technique baseline	A Experimental Setup page 6
M31	Specifically, NoREC, TLP, and SemBug employ SQLancer [29] as the query generator, while Pinolo uses Go-Randgen [30].	name reuse component	A Experimental Setup page 6
M32	, NoREC, TLP, and Pinolo.	technique	C RQ2: Comparison on Other Techniques page 7
M33	It is noted that we implement NoREC on TiDB and MySQL to enhance the generalizability of the results.	technique	C RQ2: Comparison on Other Techniques page 7
M34	Compared to Pinolo, NoREC, and TLP, the number of detected bugs by SemBug increased by 13, 15, and 19, respectively.	technique	C RQ2: Comparison on Other Techniques page 7
M35	DBMS # SemBug # Pinolo # NoREC # TLP MySQL 13 8 8 7 TiDB 9 6 4 6 MariaDB 9 7 6 SQLite 3 - 2 2 PostgreSQL 0 - 0 0 Total 34 21 20 15 Improvement-13 ↑ 14↑ 19↑ Overlap of bugs.	technique	C RQ2: Comparison on Other Techniques page 7
M36	We observe that, except NoREC, SemBug shares partial overlap with other methods in bug detection, indicating that SemBug has its unique strengths.	technique	C RQ2: Comparison on Other Techniques page 7
M37	Regarding NoREC, SemBug is capable of detecting all the bugs that NoREC finds.	technique	C RQ2: Comparison on Other Techniques page 7
M38	For Pinolo, SemBug detects 7 out of 21 logic bugs, and for TLP, SemBug finds 13 out of 15 logic bugs.	technique	C RQ2: Comparison on Other Techniques page 7
M39	Since SemBug encompasses the functionalities of NoREC, it can detect all the bugs that NoREC discovers.	technique	C RQ2: Comparison on Other Techniques page 7
M40	SemBug and TLP both heavily rely on the WHERE clause for logic bug detection, SemBugTLP MySQL:13 TiDB:9 MariaDB:9 SQLite:3MySQL:7 TiDB:3 SQLite:1MySQL:7 TiDB:6 SQLite:2Pinolo MySQL:8 TiDB:6 MariaDB :7SemBug MySQL:13 TiDB:9 MariaDB:9 SQLite:3MySQL:4 TiDB:1 MariaDB :2SemBug MySQL:5 TiDB:5 MariaDB:3 SQLite:2NoREC MySQL...	technique	C RQ2: Comparison on Other Techniques page 7
M41	which is why SemBug can detect the majority of bugs found by TLP.	technique	C RQ2: Comparison on Other Techniques page 7
M42	Compared to Pinolo, NoREC, and TLP, the number of detected bugs by SemBug increased by 13, 14, and 19, respectively.	technique	C RQ2: Comparison on Other Techniques page 7
M43	In contrast, enhanced with semantic analysis technology, our approach is capable of supporting the most features, achieving a comparable level of support as the TLP.	technique	D RQ3: The Advantages of Expanded Feature Support page 7
M44	SemBug and TLP support the most features.	technique	D RQ3: The Advantages of Expanded Feature Support page 8
M45	Advanced Features NoREC Pinolo TLP SemBug Join clause ✓ ✓ ✓ ✓ Having clause ✓ ✓ ✓ ✓ Group by clause ✓ ✓ ✓ ✓ Order by clause ✗ ✗ ✓ ✓ Distinct ✗ ✓ ✓ ✓ NULL value ✓ ✗ ✓ ✓ Aggregate function ✗ ✗ ✓ ✓ Window function ✗ ✗ ✓ ✓ Nondeterministic function ✗ ✗ ✗ ✗ of the Kahan-Babushka-Neumaier (KBN) algorithm to improve the pr...	technique	D RQ3: The Advantages of Expanded Feature Support page 8
M46	6: The incorrect query result is caused by the window function, and the bug can be detected by SemBug but not by TLP.	technique	D RQ3: The Advantages of Expanded Feature Support page 8
M47	As illustrated in Figure 4, SemBug is capable of detecting all bugs present in NoREC, an expected outcome given SemBug’s integration of semantic analysis techniques and support for a broader range of features.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 8
M48	However, the figure also indicates that SemBug does not catch all logic bugs found by TLP and Pinolo.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 8
M49	Understanding the advantages and limitations of SemBug, Pinolo, and TLP is crucial for detecting logic bugs in DBMS.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 8
M50	The quality of seed queries significantly impacts bug detection [6], [33].	citation marker	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 8
M51	Specifically, we consider the scenario where SemBug, TLP, and Pinolo generate mutated queries based on their respective mutation principles.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 8
M52	Employing this principle, if SemBug identifies a logic bug, we can manually construct a mutated version of the original query from the case, using the principles of TLP and Pinolo as our guide.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 8
M53	If the results of the mutated and original queries violate the mutation relationship, it suggests that TLP or Pinolo can detect logic bugs that SemBug uncovers.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 8
M54	Comparison of SemBug and TLP.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 8
M55	The TLP method, on the other hand, decomposes a query without WHERE clause into three sub-queries, each with a predicate after WHERE clause that evaluates to TRUE, FALSE, or NULL, ensuring the union of the sub-query results aligns with the original query’s outcome.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 8
M56	Both SemBug and TLP excel at detecting WHERE clause-related optimization bugs, as they heavily rely on the WHERE clause for logic bug detection.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 8
M57	SemBug’s primary advantage over TLP lies in its superior detection of optimization logic bugs, an area where TLP often falls short.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 8
M58	For instance, TLP may incorrectly assess records that should be TRUE as FALSE or NULL, missing the bug because the union of sub-query results inadvertently matches the original query’s outcome.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 8
M59	However, TLP fails to identify the logic bug because the union of the sub-query results aligns coincidentally with the ’2024-01-01’ result from the original query, which does not include a WHERE clause.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 8
M60	This reason accounts for the majority of logic bugs that TLP overlooks but SemBug catches, making it the leading cause of TLP’s deficiency in optimization logic bug detection.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 8
M61	Besides, some test cases show that TLP’s oversight of certain logic bugs also stems from the UNION operator’s potential to alter the erroneous query plan, thereby omitting some bugs.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 8
M62	TLP identifies two logic bugs in MySQL that SemBug overlooks, specifically in cases where the negation operator!	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 8
M63	This discovery is unexpected as TLP is not initially designed to handle such scenarios.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 8
M64	However, the example demonstrates that TLP has the 131 CREATE VIRTUAL TABLE rt1USING rtree_i32(c0, c1, c2, +c3 INT ); INSERT INTO rt1(c0, c2, c3) VALUES ('9223372036854775807’, 1, 1); CREATE VIEW v0(c4) AS SELECT CAST (COALESCE (c0, c0) ASBLOB ) FROM rt1; SELECT (c0== CAST (c4 ASREAL ))AS f1FROM rt1, v0; --{0} SELEC...	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 8
M65	Similarly, TLP might also detect operator UNION related bugs, but our experiments do not yield such cases.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 9
M66	Overall, SemBug exhibits enhanced capabilities in identifying optimization logic bugs, a domain where TLP might be theoretically inadequate.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 9
M67	Its nested query design enables SemBug to uncover bugs that TLP usually cannot.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 9
M68	Nevertheless, in some specific situations, TLP might identify logic bugs that SemBug fails to detect.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 9
M69	Unlike SemBug and TLP, Pinolo requires an approximate relationship between the original query and the mutated query.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 9
M70	In summary, SemBug outperforms Pinolo in detecting logic bugs in query optimizations, similar to its advantage over TLP.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 9
M71	Beyond the strengths already discussed in comparison with TLP, SemBug is also capable of detecting a wider range of features within DBMS than Pinolo.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 9
M72	Answer to RQ4: SemBug is superior at finding optimization bugs, theoretically catching all that NoREC and TLP can.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 9
M73	While TLP occasionally spots bugs SemBug doesn’t, such cases are rare.	technique	E RQ4: Discrepancies in Logic Bug Detection Across Methods page 9
M74	The bugs in transactions are even more complex, but there are some dedicated works [34], [35] specifically addressing transaction issues.	citation marker project authored	B Limitations page 9
M75	In recent years, metamorphic testing has been widely applied to various software systems [36]–[38], 132 and has become popular to detect logic [6], [10], [18], [19], [31] and performance bugs [39], [40] in DBMSs.	citation marker	A Metamorphic Testing of DBMS page 9
M76	Given the seed query, CERT [40] derives a more restrictive query.	technique	A Metamorphic Testing of DBMS page 10
M77	NoREC [18] detects optimization bugs in DBMSs by converting optimized queries to unoptimized ones.	technique	A Metamorphic Testing of DBMS page 10
M78	TLP [10] decomposes the original query into three partition sub-queries and then constructs an equivalent query by applying the union operator on these three sub-queries.	technique	A Metamorphic Testing of DBMS page 10
M79	Distinct from NoREC and TLP, Pinolo [19] employs metamorphic testing based on approximate relationships to mutate the seed query.	technique	A Metamorphic Testing of DBMS page 10
M80	Although these methods have their strengths, NoREC excels in detecting optimization bugs and identifying issues that other methods may miss.	technique	A Metamorphic Testing of DBMS page 10
M81	Inspired by NoREC, SemBug retains semantic information to support a broader range of features and detect deeper semantic optimization logic bugs.	technique	A Metamorphic Testing of DBMS page 10
M82	Many approaches [6], [11], [29], [30], [33], [48] have been proposed for database and query generation.	citation marker	D Query Generation of DBMS page 10
M83	SQLancer [29] can generate random queries for more than 10 DBMSs.	name	D Query Generation of DBMS page 10
M84	QPG [33] utilizes query plan as guidance to produce statements that have diverse query plans.	technique	D Query Generation of DBMS page 10

This page is rendered from _data/papers/paper_doi_10_1109_icpc66645_2025_00021.json, extracted from supplied pdf. 12 pages, 49 references parsed.