Skip to content

Commit 6c8166b

Browse files
luliqwertluliqwert
committed
Introduce DQE for MySQL in SQLancer and add test to workflow
1 parent 31c01db commit 6c8166b

7 files changed

Lines changed: 781 additions & 7 deletions

File tree

‎.github/workflows/main.yml‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -467,6 +467,7 @@ jobs:
467467
MYSQL_AVAILABLE=true mvn test -Dtest=TestMySQLPQS
468468
MYSQL_AVAILABLE=true mvn test -Dtest=TestMySQLTLP
469469
MYSQL_AVAILABLE=true mvn test -Dtest=TestMySQLCERT
470+
MYSQL_AVAILABLE=true mvn test -Dtest=TestMySQLDQE
470471
471472
oceanbase:
472473
name: DBMS Tests (OceanBase)

‎src/sqlancer/common/oracle/DQEBase.java‎

Lines changed: 156 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,156 @@
1+
package sqlancer.common.oracle;
2+
3+
import java.sql.SQLException;
4+
import java.util.Collections;
5+
import java.util.List;
6+
import java.util.Map;
7+
import java.util.Set;
8+
9+
import sqlancer.Main;
10+
import sqlancer.MainOptions;
11+
import sqlancer.SQLConnection;
12+
import sqlancer.SQLGlobalState;
13+
import sqlancer.common.query.ExpectedErrors;
14+
import sqlancer.common.query.SQLQueryAdapter;
15+
import sqlancer.common.query.SQLQueryError;
16+
import sqlancer.common.schema.AbstractRelationalTable;
17+
import sqlancer.mysql.MySQLSchema.MySQLTables;
18+
19+
/*
20+
* In DBMSs, SELECT, UPDATE and DELETE queries utilize predicates (i.e., WHERE clauses) to specify which rows to retrieve, update or delete, respectively.
21+
* If they use the same predicate φ, they should access the same rows in a database.
22+
* Ideally, DBMSs can adopt the same implementations for predicate evaluation in SELECT, UPDATE and DELETE queries.
23+
* However, a DBMS usually adopts different implementations for predicate evaluation in SELECT, UPDATE and DELETE queries due to various optimization choices.
24+
* Inconsistent implementations for predicate evaluation among these queries can cause SELECT, UPDATE and DELETE queries with the same predicate φ to access different rows.
25+
*
26+
*
27+
* Inspired by this key observation, we propose Differential Query Execution(DQE), a novel and general approach to detect logic bugs in SELECT, UPDATE and DELETE queries.
28+
* DQE solves the test oracle problem by executing SELECT, UPDATE and DELETE queries with the same predicate φ, and observing inconsistencies among their execution results.
29+
* For example, if a row that is updated by an UPDATE query with a predicate φ does not appear in the query result of a SELECT query with the same predicate φ, a logic bug is detected in the target DBMS.
30+
* The key challenge of DQE is to automatically obtain the accessed rows for a given SELECT, UPDATE or DELETE query.
31+
* To address this challenge, we append two extra columns to each table in a database, to uniquely identify each row and track whether a row has been modified, respectively.
32+
* We further rewrite SELECT and UPDATE queries to identify their accessed rows.
33+
*
34+
* more information see [DQE paper](https://ieeexplore.ieee.org/document/10172736)
35+
*/
36+
37+
public abstract class DQEBase<S extends SQLGlobalState<?, ?>> {
38+
39+
public static final String COLUMN_ROWID = "rowId";
40+
public static final String COLUMN_UPDATED = "updated";
41+
42+
protected final S state;
43+
protected final ExpectedErrors selectExpectedErrors = new ExpectedErrors();
44+
protected final ExpectedErrors updateExpectedErrors = new ExpectedErrors();
45+
protected final ExpectedErrors deleteExpectedErrors = new ExpectedErrors();
46+
47+
protected final Main.StateLogger logger;
48+
protected final MainOptions options;
49+
protected final SQLConnection con;
50+
51+
public DQEBase(S state) {
52+
this.state = state;
53+
this.con = state.getConnection();
54+
this.logger = state.getLogger();
55+
this.options = state.getOptions();
56+
}
57+
58+
public abstract String generateSelectStatement(MySQLTables tables, String tableName, String whereClauseStr);
59+
60+
public abstract String generateUpdateStatement(MySQLTables tables, String tableName, String whereClauseStr);
61+
62+
public abstract String generateDeleteStatement(MySQLTables tables, String tableName, String whereClauseStr);
63+
64+
/**
65+
* Add auxiliary columns to the database A abstract method, subclasses need to implement it.
66+
*
67+
* @param table
68+
*
69+
* @throws SQLException
70+
*/
71+
public abstract void addAuxiliaryColumns(AbstractRelationalTable<?, ?, ?> table) throws SQLException;
72+
73+
public void dropAuxiliaryColumns(AbstractRelationalTable<?, ?, ?> table) throws SQLException {
74+
String tableName = table.getName();
75+
String dropColumnRowId = String.format("ALTER TABLE %s DROP COLUMN %s", tableName, COLUMN_ROWID);
76+
new SQLQueryAdapter(dropColumnRowId).execute(state);
77+
String dropColumnUpdated = String.format("ALTER TABLE %s DROP COLUMN %s", tableName, COLUMN_UPDATED);
78+
new SQLQueryAdapter(dropColumnUpdated).execute(state);
79+
}
80+
81+
// This interface is to record Error code
82+
public interface UpdateErrorCodes {
83+
84+
}
85+
86+
public interface ErrorCodeStrategy {
87+
Set<Integer> getUpdateSpecificErrorCodes();
88+
89+
Set<Integer> getDeleteSpecificErrorCodes();
90+
91+
}
92+
93+
/**
94+
* The core idea of DQE is that the SELECT, UPDATE and DELETE queries with the same predicate φ should access the
95+
* same rows. If these queries access different rows, DQE reveals a potential logic bug in the target DBMS.
96+
*/
97+
public static class SQLQueryResult {
98+
99+
private final Map<AbstractRelationalTable<?, ?, ?>, Set<String>> accessedRows; // Table name with respect rows
100+
private final List<SQLQueryError> queryErrors;
101+
102+
public SQLQueryResult(Map<AbstractRelationalTable<?, ?, ?>, Set<String>> accessedRows,
103+
List<SQLQueryError> queryErrors) {
104+
this.accessedRows = accessedRows;
105+
this.queryErrors = queryErrors;
106+
}
107+
108+
public Map<AbstractRelationalTable<?, ?, ?>, Set<String>> getAccessedRows() {
109+
return accessedRows;
110+
}
111+
112+
public List<SQLQueryError> getQueryErrors() {
113+
return queryErrors;
114+
}
115+
116+
public boolean hasEmptyErrors() {
117+
return queryErrors.isEmpty();
118+
}
119+
120+
public boolean hasErrors() {
121+
return !hasEmptyErrors();
122+
}
123+
124+
public boolean hasSameErrors(SQLQueryResult that) {
125+
if (queryErrors.size() != that.getQueryErrors().size()) {
126+
return false;
127+
} else {
128+
Collections.sort(queryErrors);
129+
Collections.sort(that.getQueryErrors());
130+
for (int i = 0; i < queryErrors.size(); i++) {
131+
if (!queryErrors.get(i).equals(that.getQueryErrors().get(i))) {
132+
return false;
133+
}
134+
}
135+
}
136+
return true;
137+
}
138+
139+
public boolean hasAccessedRows() {
140+
if (accessedRows.isEmpty()) {
141+
return false;
142+
}
143+
for (Set<String> accessedRow : accessedRows.values()) {
144+
if (!accessedRow.isEmpty()) {
145+
return true;
146+
}
147+
}
148+
return false;
149+
}
150+
151+
public boolean hasSameAccessedRows(SQLQueryResult that) {
152+
return accessedRows.equals(that.getAccessedRows());
153+
}
154+
155+
}
156+
}

‎src/sqlancer/common/query/SQLQueryAdapter.java‎

Lines changed: 59 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -81,17 +81,55 @@ public String getUnterminatedQueryString() {
8181
return result;
8282
}
8383

84+
/**
85+
* This method is used to mostly oracles, which need to report exceptions. We set the reportException parameter to
86+
* true by default meaning that exceptions are reported.
87+
*
88+
* @param globalState
89+
* @param fills
90+
*
91+
* @return whether the query was executed successfully
92+
*
93+
* @param <G>
94+
*
95+
* @throws SQLException
96+
*/
8497
@Override
8598
public <G extends GlobalState<?, ?, SQLConnection>> boolean execute(G globalState, String... fills)
8699
throws SQLException {
100+
return execute(globalState, true, fills);
101+
}
102+
103+
/**
104+
* This method is used to DQE oracles, DQE does not check exception separately, while other testing methods may
105+
* need. We use reportException to control this behavior. For a specific DBMS used DQE oracle, we call this method
106+
* and pass a boolean value of false as an argument.
107+
*
108+
* @param globalState
109+
* @param reportException
110+
* @param fills
111+
*
112+
* @return whether the query was executed successfully
113+
*
114+
* @param <G>
115+
*
116+
* @throws SQLException
117+
*/
118+
public <G extends GlobalState<?, ?, SQLConnection>> boolean execute(G globalState, boolean reportException,
119+
String... fills) throws SQLException {
120+
return internalExecute(globalState.getConnection(), reportException, fills);
121+
}
122+
123+
protected <G extends GlobalState<?, ?, SQLConnection>> boolean internalExecute(SQLConnection connection,
124+
boolean reportException, String... fills) throws SQLException {
87125
Statement s;
88126
if (fills.length > 0) {
89-
s = globalState.getConnection().prepareStatement(fills[0]);
127+
s = connection.prepareStatement(fills[0]);
90128
for (int i = 1; i < fills.length; i++) {
91129
((PreparedStatement) s).setString(i, fills[i]);
92130
}
93131
} else {
94-
s = globalState.getConnection().createStatement();
132+
s = connection.createStatement();
95133
}
96134
try {
97135
if (fills.length > 0) {
@@ -103,7 +141,9 @@ public String getUnterminatedQueryString() {
103141
return true;
104142
} catch (Exception e) {
105143
Main.nrUnsuccessfulActions.addAndGet(1);
106-
checkException(e);
144+
if (reportException) {
145+
checkException(e);
146+
}
107147
return false;
108148
} finally {
109149
s.close();
@@ -127,14 +167,24 @@ public void checkException(Exception e) throws AssertionError {
127167
@Override
128168
public <G extends GlobalState<?, ?, SQLConnection>> SQLancerResultSet executeAndGet(G globalState, String... fills)
129169
throws SQLException {
170+
return executeAndGet(globalState, true, fills);
171+
}
172+
173+
public <G extends GlobalState<?, ?, SQLConnection>> SQLancerResultSet executeAndGet(G globalState,
174+
boolean reportException, String... fills) throws SQLException {
175+
return internalExecuteAndGet(globalState.getConnection(), reportException, fills);
176+
}
177+
178+
protected <G extends GlobalState<?, ?, SQLConnection>> SQLancerResultSet internalExecuteAndGet(
179+
SQLConnection connection, boolean reportException, String... fills) throws SQLException {
130180
Statement s;
131181
if (fills.length > 0) {
132-
s = globalState.getConnection().prepareStatement(fills[0]);
182+
s = connection.prepareStatement(fills[0]);
133183
for (int i = 1; i < fills.length; i++) {
134184
((PreparedStatement) s).setString(i, fills[i]);
135185
}
136186
} else {
137-
s = globalState.getConnection().createStatement();
187+
s = connection.createStatement();
138188
}
139189
ResultSet result;
140190
try {
@@ -151,9 +201,11 @@ public void checkException(Exception e) throws AssertionError {
151201
} catch (Exception e) {
152202
s.close();
153203
Main.nrUnsuccessfulActions.addAndGet(1);
154-
checkException(e);
204+
if (reportException) {
205+
checkException(e);
206+
}
207+
return null;
155208
}
156-
return null;
157209
}
158210

159211
@Override

‎src/sqlancer/common/query/SQLancerResultSet.java‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,8 @@
44
import java.sql.ResultSet;
55
import java.sql.SQLException;
66

7+
import sqlancer.common.query.SQLQueryError.ErrorLevel;
8+
79
public class SQLancerResultSet implements Closeable {
810

911
ResultSet rs;
@@ -42,6 +44,23 @@ public String getString(int i) throws SQLException {
4244
}
4345
}
4446

47+
// This method is to fetch the result of SQL: "SHOW WARNINGS;"
48+
public ErrorLevel getErrorLevel(String colName) throws SQLException {
49+
String res = rs.getString(colName);
50+
if (res == null) {
51+
return ErrorLevel.WARNING;
52+
}
53+
return "ERROR".equalsIgnoreCase(res.trim()) ? ErrorLevel.ERROR : ErrorLevel.WARNING;
54+
}
55+
56+
public String getString(String colName) throws SQLException {
57+
return rs.getString(colName);
58+
}
59+
60+
public int getInt(String colName) throws SQLException {
61+
return rs.getInt(colName);
62+
}
63+
4564
public boolean isClosed() throws SQLException {
4665
return rs.isClosed();
4766
}

‎src/sqlancer/mysql/MySQLOracleFactory.java‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,7 @@
1010
import sqlancer.common.query.ExpectedErrors;
1111
import sqlancer.common.query.SQLancerResultSet;
1212
import sqlancer.mysql.gen.MySQLExpressionGenerator;
13+
import sqlancer.mysql.oracle.MySQLDQEOracle;
1314
import sqlancer.mysql.oracle.MySQLDQPOracle;
1415
import sqlancer.mysql.oracle.MySQLFuzzer;
1516
import sqlancer.mysql.oracle.MySQLPivotedQuerySynthesisOracle;
@@ -75,5 +76,11 @@ public TestOracle<MySQLGlobalState> create(MySQLGlobalState globalState) throws
7576
public TestOracle<MySQLGlobalState> create(MySQLGlobalState globalState) throws SQLException {
7677
return new MySQLDQPOracle(globalState);
7778
}
79+
},
80+
DQE {
81+
@Override
82+
public TestOracle<MySQLGlobalState> create(MySQLGlobalState globalState) throws SQLException {
83+
return new MySQLDQEOracle(globalState);
84+
}
7885
};
7986
}

0 commit comments

Comments
 (0)