Implement EET oracle - #1349

This PR implements the EET test oracle, based on:

Zu-Ming Jiang and Zhendong Su. Detecting Logic Bugs in Database Engines via Equivalent Expression Transformation.
18th USENIX Symposium on Operating Systems Design and Implementation (OSDI'24).

Transformation rules

The seven EET transformation rules are defined in the EETTransformer class (sqlancer/common/oracle/EETTransformer.java). The class' transformNode method may or may not (as per random choice) apply a transformation rule to an expression, unless the forceApply input of transformNode is set to true (in which case an applicable rule is definitely applied).

Which rules are applicable is determined by applyRandomRule's booleanContext input (which if true, enables rules 1-2) and CaseWhenApplicable(expr) method (which, if returning false, forces rule 7). If transformNode decides to apply a rule, then all applicable rules have an equal probability of being chosen. The exception is Rule 7, which is avoided if possible. I.e., rule 7 is only used if booleanContext is false and isCaseWhenApplicable(expr) is false. This is because Rule 7 is simple a "do nothing" rule, and the decision of whether to "do nothing" is already handled when deciding whether to apply a rule at all.

• boolean context = true in the following contexts: the WHERE predicate, the operands of AND/OR/XOR, NOT, and switch-less CASE WHEN conditions.
• boolean context = false in the following contexts: operands of comparisons, arithmetic, function arguments, CAST, BETWEEN, IN, and THEN/ELSE branches.

Architecture

The implementation follows the "common core + per-DBMS subclasses" pattern. As much as possible is DBMS-independent, while parts that must construct or walk a specific AST are DBMS-specific.

Common

EETOracle.check():

1. Generates a random query (SELECT <fetch cols> FROM <tables> [joins] WHERE <predicate>).
2. Runs it to get result set of original query.
3. Transforms the fetch-column expressions and the WHERE predicate via EETTransformer.transform(...).
4. Runs the transformed query to get result set of trasnformed query.
5. Compares the two result sets (first column, as a multiset with a cardinality check, via ComparatorHelper); a mismatch throws an AssertionError reported by SQLancer as a bug.

It also installs a Reproducer (EETReproducer) that re-runs both the original and the transformed query against the current (reduced) database and re-checks the mismatch, which SQLancer uses to reduce the finding, similarly to other oracles (e.g. TLP WHERE).

DBMS-specific

MySQL is used as an example.

Expression transformation

The paper transforms expressions by traversing the query AST. SQLancer's AST has no generic child-rewrite facility, so MySQLEETTransformer walks the MySQL AST explicitly. For each node it:

1. descends — transforms the pre-existing children and rebuilds the node (descend() / descendCase()), then
2. wraps — with some probability applies a random rule to the rebuilt node (transformNode()).

This is a single bottom-up pass over the original AST. Auxiliary sub-expressions introduced by a rule (the random p in true_expr/false_expr, the random CASE predicate) are generated fresh with the query generator and are not themselves passed back through the transformer — only pre-existing nodes are visited. At the root a rule is always applied (forceApply), guaranteeing the transformed query actually differs from the original (unless only rule 7 is applicable). The generator reuses the columns available at that point in the query.

copy_expr / rand_expr and type safety

The paper notes (§3.2.2, footnote to Table 2) that the type of the expression placed in the dead branch of rules No. 3–4 must equal type(expr): although the dead branch is never evaluated, its static type participates in the DBMS's CASE result-type resolution, so a mismatch can alter the live branch's rendering (e.g. CASE WHEN FALSE THEN 1.5 ELSE 1 END might print 1.0 instead of 1).

EETTransformer therefore realises rand_expr(type(expr)) through two DBMS-specific methods:

• inferType(expr) — returns the static type of expr in a DBMS-specific, possibly coarse type domain T, or
  null if it cannot be determined. The domain only needs to be precise enough that two expressions of the same T
  behave identically under CASE result-type resolution.
• generateExpressionOfType(type) — generates a random expression of that static type.

When inferType returns null, the dead branch falls back to expr itself, which trivially has the correct type (degenerating rules No. 3–4 to 5–6). This fallback makes inference incrementally extensible: every classified node adds dead-branch diversity, while unclassified nodes do not prevent soundness.

For MySQL, whose expression generator is untyped, the type domain is MySQL's CAST target types (MySQLCastOperation.CastType: SIGNED, UNSIGNED, CHAR, FLOAT, DOUBLE, DECIMAL), and generateExpressionOfType pins the type of an arbitrary random expression by wrapping it in a CAST. DBMSs with typed expression generators (e.g. PostgreSQL) can implement inferType from their existing type tracking and generateExpressionOfType by delegating to generateExpression(type) directly, without the CAST trick.

Because the AST nodes are immutable and only rendered to SQL text, sharing the reference is safe and copy_expr (as used in the EET paper) is not required.

Running the oracle

Taking MySQL as an example:

mvn package -DskipTests
java -jar target/sqlancer-*.jar mysql --oracle EET

Scope and possible extensions

• The common core (EETOracle, EETTransformer, EETGenerator) is DBMS-independent; new DBMSs can be added by providing their own EETTransformer subclass (implementing descend, the abstract factory methods, and inferType / generateExpressionOfType) and making their own expression generator implement EETGenerator.
• Transformation currently targets SELECT queries (fetch columns + WHERE predicate). The paper also transforms expressions in other clauses and in DML (UPDATE/DELETE); these will be followed up in future PRs.
• Reduction uses SQLancer's generic Reproducer, which reduces the database generation but leaves the transformed query unchanged. As the transformed query may become very complex with this oracle, automatic reduction of it may be a future PR.
• FLOAT/DOUBLE/DECIMAL columns are created without an (M, D) precision/scale specifier while EET is active (see MySQLTableGenerator.optionallyAddPrecisionAndScale). This is because MySQLEETTransformer.inferColumnType maps these columns to the plain CastType.FLOAT/DOUBLE/DECIMAL targets, which only match the column's type when no (M, D) is present. This exclusion is scoped to EET only, preserving the (M, D) search space for the other oracles. A follow-up will be to track (M, D) through the schema and emit the exact precision/scale in the type-pinning CAST, at which point the restriction can be removed.