Skip to content

Commit 061a337

Browse files
mriggermrigger
authored
Merge pull request #1251 from luliqwerty/main
Feat: Integrating DQE Testing Approaches into SQLancer first in MySQL
2 parents 31c01db + 131febb commit 061a337

File tree

8 files changed

+741
-7
lines changed

8 files changed

+741
-7
lines changed

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

‎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: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -42,6 +42,14 @@ public String getString(int i) throws SQLException {
4242
}
4343
}
4444

45+
public String getString(String colName) throws SQLException {
46+
return rs.getString(colName);
47+
}
48+
49+
public int getInt(String colName) throws SQLException {
50+
return rs.getInt(colName);
51+
}
52+
4553
public boolean isClosed() throws SQLException {
4654
return rs.isClosed();
4755
}

‎src/sqlancer/mysql/MySQLErrors.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -53,6 +53,7 @@ public static List<String> getInsertUpdateErrors() {
5353
errors.add("Data truncated for functional index");
5454
errors.add("cannot be null");
5555
errors.add("Incorrect decimal value");
56+
errors.add("The value specified for generated column");
5657

5758
return errors;
5859
}

‎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)