Skip to content

Commit 0f9eef7

Browse files
ColinYoungTarooraluben
ColinYoungTaro
and
oraluben
authored
feat: Add virtual db for statement reduction testing (sqlancer#815)
* feat: Add virtual db for statement reduction testing + Implement a prototype of `VirtualDB` so that statement reduction can be tested. + Write some test cases for statement reduction. + Simplify the code of StatementReducer + Add parameter for timeout and max steps of reducer * Correct code of VirtualDB. * Add an extra empty line for StatementReducer.java * Add GitHub Action for reducer tests * format * format 2 * Fix name issues * Do not run reducer test in "general" --------- Co-authored-by: Yichen Yan <[email protected]> Co-authored-by: Yichen Yan <[email protected]>
1 parent eb0a65d commit 0f9eef7

12 files changed

Lines changed: 522 additions & 16 deletions

‎.github/workflows/main.yml‎

Lines changed: 19 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -30,7 +30,7 @@ jobs:
3030
- name: Verify
3131
run: mvn -B verify -DskipTests=true
3232
- name: Misc Tests
33-
run: mvn -B '-Dtest=!sqlancer.dbms.**,!sqlancer.qpg.**' test
33+
run: mvn -B '-Dtest=!sqlancer.dbms.**,!sqlancer.qpg.**,!sqlancer.reducer.**' test
3434
- name: Set up Python
3535
uses: actions/setup-python@v4
3636
with:
@@ -533,3 +533,21 @@ jobs:
533533
run: mvn -B package -DskipTests=true
534534
- name: Shortly run DuckDB
535535
run: cd target && java -jar $(ls | grep -P 'sqlancer-[0-9.]*.jar') --num-threads 4 --timeout-seconds 30 --num-queries 0 duckdb
536+
537+
reducer:
538+
name: Reducer Tests
539+
runs-on: ubuntu-latest
540+
541+
steps:
542+
- uses: actions/checkout@v3
543+
with:
544+
fetch-depth: 0
545+
- name: Set up JDK 11
546+
uses: actions/[email protected]
547+
with:
548+
java-version: 11
549+
- name: Build
550+
run: mvn -B package -DskipTests=true
551+
- name: Run Tests
552+
run: |
553+
mvn -Dtest=TestStatementReducer test

‎src/sqlancer/MainOptions.java‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,7 @@
1010
@Parameters(separators = "=", commandDescription = "Options applicable to all DBMS")
1111
public class MainOptions {
1212
public static final int NO_SET_PORT = -1;
13+
public static final int NO_REDUCE_LIMIT = -1;
1314
public static final MainOptions DEFAULT_OPTIONS = new MainOptions();
1415

1516
@Parameter(names = { "--help", "-h" }, description = "Lists all supported options and commands", help = true)
@@ -125,6 +126,12 @@ public class MainOptions {
125126
@Parameter(names = "--use-reducer", description = "EXPERIMENTAL Attempt to reduce queries using a simple reducer")
126127
private boolean useReducer = false; // NOPMD
127128

129+
@Parameter(names = "--statement-reducer-max-steps", description = "EXPERIMENTAL Maximum steps the statement reducer will do")
130+
private long maxStatementReduceSteps = NO_REDUCE_LIMIT; // NOPMD
131+
132+
@Parameter(names = "--statement-reducer-max-time", description = "EXPERIMENTAL Maximum time duration (secs) the statement reducer will do")
133+
private long maxStatementReduceTime = NO_REDUCE_LIMIT; // NOPMD
134+
128135
public int getMaxExpressionDepth() {
129136
return maxExpressionDepth;
130137
}
@@ -285,4 +292,12 @@ public boolean performConnectionTest() {
285292
public boolean useReducer() {
286293
return useReducer;
287294
}
295+
296+
public long getMaxStatementReduceSteps() {
297+
return maxStatementReduceSteps;
298+
}
299+
300+
public long getMaxStatementReduceTime() {
301+
return maxStatementReduceTime;
302+
}
288303
}

‎src/sqlancer/StatementReducer.java‎

Lines changed: 54 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -1,59 +1,95 @@
11
package sqlancer;
22

3+
import java.time.Duration;
4+
import java.time.Instant;
35
import java.util.ArrayList;
46
import java.util.List;
5-
import java.util.function.BiFunction;
6-
import java.util.stream.Collectors;
77

88
import sqlancer.common.query.Query;
99

1010
public class StatementReducer<G extends GlobalState<O, ?, C>, O extends DBMSSpecificOptions<?>, C extends SQLancerDBConnection>
1111
implements Reducer<G> {
1212
private final DatabaseProvider<G, O, C> provider;
1313
private boolean observedChange;
14+
private int partitionNum;
1415

1516
public StatementReducer(DatabaseProvider<G, O, C> provider) {
1617
this.provider = provider;
1718
}
1819

20+
private boolean hasNotReachedLimit(long curr, long limit) {
21+
if (limit == MainOptions.NO_REDUCE_LIMIT) {
22+
return true;
23+
}
24+
return curr < limit;
25+
}
26+
1927
@SuppressWarnings("unchecked")
2028
@Override
2129
public void reduce(G state, Reproducer<G> reproducer, G newGlobalState) throws Exception {
2230

31+
long maxReduceTime = state.getOptions().getMaxStatementReduceTime();
32+
long maxReduceSteps = state.getOptions().getMaxStatementReduceSteps();
33+
2334
List<Query<C>> knownToReproduceBugStatements = new ArrayList<>();
2435
for (Query<?> stat : state.getState().getStatements()) {
2536
knownToReproduceBugStatements.add((Query<C>) stat);
2637
}
38+
2739
System.out.println("Starting query:");
2840
printQueries(knownToReproduceBugStatements);
2941
System.out.println();
3042

31-
do {
43+
if (knownToReproduceBugStatements.size() <= 1) {
44+
return;
45+
}
46+
47+
Instant timeOfReductionBegins = Instant.now();
48+
long currentReduceSteps = 0;
49+
long currentReduceTime = 0;
50+
partitionNum = 2;
51+
52+
while (knownToReproduceBugStatements.size() >= 2 && hasNotReachedLimit(currentReduceSteps, maxReduceSteps)
53+
&& hasNotReachedLimit(currentReduceTime, maxReduceTime)) {
3254
observedChange = false;
55+
3356
knownToReproduceBugStatements = tryReduction(state, reproducer, newGlobalState,
34-
knownToReproduceBugStatements, (candidateStatements, i) -> {
35-
candidateStatements.remove((int) i);
36-
return true;
37-
});
38-
} while (observedChange);
57+
knownToReproduceBugStatements);
58+
if (!observedChange) {
59+
if (partitionNum == knownToReproduceBugStatements.size()) {
60+
break;
61+
}
62+
// increase the search granularity
63+
partitionNum = Math.min(partitionNum * 2, knownToReproduceBugStatements.size());
64+
65+
currentReduceSteps++;
66+
Instant currentInstant = Instant.now();
67+
currentReduceTime = Duration.between(currentInstant, timeOfReductionBegins).getSeconds();
68+
}
69+
70+
}
3971

4072
System.out.println("Reduced query:");
4173
printQueries(knownToReproduceBugStatements);
74+
newGlobalState.getState().setStatements(new ArrayList<>(knownToReproduceBugStatements));
4275
}
4376

4477
private List<Query<C>> tryReduction(G state, // NOPMD
45-
Reproducer<G> reproducer, G newGlobalState, List<Query<C>> knownToReproduceBugStatements,
46-
BiFunction<List<Query<C>>, Integer, Boolean> reductionOperation) throws Exception {
78+
Reproducer<G> reproducer, G newGlobalState, List<Query<C>> knownToReproduceBugStatements) throws Exception {
4779

4880
List<Query<C>> statements = knownToReproduceBugStatements;
49-
for (int i = 0; i < statements.size(); i++) {
81+
82+
int start = 0;
83+
int subLength = statements.size() / partitionNum;
84+
while (start < statements.size()) {
85+
// newStatements = candidate[:start] + candidate[start+subLength:]
86+
// in other word, remove [start, start+subLength) from candidates
5087
try (C con2 = provider.createDatabase(newGlobalState)) {
5188
newGlobalState.setConnection(con2);
5289
List<Query<C>> candidateStatements = new ArrayList<>(statements);
53-
if (!reductionOperation.apply(candidateStatements, i)) {
54-
continue;
55-
}
56-
newGlobalState.getState().setStatements(candidateStatements.stream().collect(Collectors.toList()));
90+
candidateStatements.subList(start, start + subLength).clear();
91+
newGlobalState.getState().setStatements(new ArrayList<>(candidateStatements));
92+
5793
for (Query<C> s : candidateStatements) {
5894
try {
5995
s.execute(newGlobalState);
@@ -65,13 +101,16 @@ private List<Query<C>> tryReduction(G state, // NOPMD
65101
if (reproducer.bugStillTriggers(newGlobalState)) {
66102
observedChange = true;
67103
statements = candidateStatements;
104+
partitionNum = Math.max(partitionNum - 1, 2);
105+
break;
68106
// reproducer.outputHook((SQLite3GlobalState) newGlobalState);
69107
// state.getLogger().logReduced(newGlobalState.getState());
70108
}
71109
} catch (Throwable ignoredException) {
72110

73111
}
74112
}
113+
start = start + subLength;
75114
}
76115
return statements;
77116
}

‎test/sqlancer/reducer/TestEnvironment.java‎

Lines changed: 114 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,114 @@
1+
package sqlancer.reducer;
2+
3+
import sqlancer.*;
4+
import sqlancer.common.query.Query;
5+
import sqlancer.reducer.VirtualDB.VirtualDBGlobalState;
6+
import sqlancer.reducer.VirtualDB.VirtualDBProvider;
7+
import sqlancer.reducer.VirtualDB.VirtualDBQuery;
8+
9+
import java.util.ArrayList;
10+
import java.util.List;
11+
import java.util.ServiceLoader;
12+
import java.util.function.Function;
13+
import java.util.stream.Collectors;
14+
15+
/**
16+
* TODO: Make Connection a generic type OR Fake a conn QUERY AND CONNECTION BOTH ARE FAKE. FAKE QUERY sub class
17+
*/
18+
public class TestEnvironment {
19+
private final String databaseName = "virtual_db";
20+
private final MainOptions options = new MainOptions();
21+
private VirtualDBProvider provider = null;
22+
private VirtualDBGlobalState state, newGlobalState;
23+
24+
public TestEnvironment() throws Exception {
25+
setUpTestingEnvironment();
26+
}
27+
28+
/**
29+
* @param queries:
30+
* List of Query<?>
31+
*
32+
* @return String of queries that appended together with '\n' separated (no '\n' at the last line)
33+
*/
34+
public static String getQueriesString(List<Query<?>> queries) {
35+
return queries.stream().map(Query::getQueryString).collect(Collectors.joining("\n"));
36+
}
37+
38+
private VirtualDBGlobalState createGlobalState() {
39+
try {
40+
return provider.getGlobalStateClass().getDeclaredConstructor().newInstance();
41+
} catch (Exception e) {
42+
throw new AssertionError(e);
43+
}
44+
}
45+
46+
@SuppressWarnings("rawtypes")
47+
private void initVirtualDBProvider() {
48+
try {
49+
ServiceLoader<DatabaseProvider> loader = ServiceLoader.load(DatabaseProvider.class);
50+
for (DatabaseProvider<?, ?, ?> provider : loader) {
51+
if (provider.getDBMSName().equals(databaseName)) {
52+
this.provider = (VirtualDBProvider) provider;
53+
break;
54+
}
55+
}
56+
if (provider == null) {
57+
throw new AssertionError("testing provider not registered");
58+
}
59+
} catch (Exception e) {
60+
throw new AssertionError(e);
61+
}
62+
63+
}
64+
65+
private void setUpTestingEnvironment() throws Exception {
66+
initVirtualDBProvider();
67+
state = createGlobalState();
68+
StateToReproduce stateToReproduce = provider.getStateToReproduce(databaseName);
69+
70+
state.setState(stateToReproduce);
71+
state.setDatabaseName(databaseName);
72+
state.setMainOptions(options);
73+
74+
// Main.StateLogger logger = new Main.StateLogger(databaseName, provider, options);
75+
// state.setStateLogger(logger);
76+
77+
try (SQLConnection con = provider.createDatabase(state)) {
78+
state.setConnection(con);
79+
newGlobalState = createGlobalState();
80+
// Main.StateLogger newLogger = new Main.StateLogger(databaseName, provider, options);
81+
// newGlobalState.setStateLogger(newLogger);
82+
newGlobalState.setState(stateToReproduce);
83+
newGlobalState.setDatabaseName(databaseName);
84+
newGlobalState.setMainOptions(options);
85+
}
86+
}
87+
88+
public void setInitialStatementsFromStrings(List<String> statements) {
89+
List<Query<?>> queries = new ArrayList<>();
90+
for (String s : statements) {
91+
queries.add(new VirtualDBQuery(s));
92+
}
93+
state.getState().setStatements(queries);
94+
}
95+
96+
public void setBugInducingCondition(Function<List<Query<?>>, Boolean> bugInducingCondition) {
97+
state.setBugInducingCondition(bugInducingCondition);
98+
newGlobalState.setBugInducingCondition(bugInducingCondition);
99+
}
100+
101+
public void runReduce() throws Exception {
102+
Reducer<VirtualDBGlobalState> reducer = new StatementReducer<>(provider);
103+
Reproducer<VirtualDBGlobalState> reproducer = provider.generateAndTestDatabase(newGlobalState);
104+
reducer.reduce(state, reproducer, newGlobalState);
105+
}
106+
107+
public List<Query<?>> getReducedStatements() {
108+
return newGlobalState.getState().getStatements();
109+
}
110+
111+
public List<Query<?>> getInitialStatements() {
112+
return state.getState().getStatements();
113+
}
114+
}

‎test/sqlancer/reducer/TestStatementReducer.java‎

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
package sqlancer.reducer;
2+
3+
import org.junit.jupiter.api.Test;
4+
import sqlancer.common.query.Query;
5+
6+
import java.util.ArrayList;
7+
import java.util.List;
8+
import java.util.regex.Pattern;
9+
10+
import static org.junit.jupiter.api.Assertions.assertEquals;
11+
12+
public class TestStatementReducer {
13+
14+
@Test
15+
void testSimple() throws Exception {
16+
TestEnvironment env = new TestEnvironment();
17+
18+
String[] queriesStr = { "CREATE TABLE FAKE_TABLE;", "SELECT * FROM FAKE_TABLE;", "EXIT", };
19+
env.setInitialStatementsFromStrings(List.of(queriesStr));
20+
env.setBugInducingCondition(statements -> {
21+
String queriesString = TestEnvironment.getQueriesString(statements);
22+
return queriesString.contains("SELECT");
23+
});
24+
env.runReduce();
25+
List<Query<?>> reducedResult = env.getReducedStatements();
26+
assertEquals(1, reducedResult.size());
27+
assertEquals("SELECT * FROM FAKE_TABLE;", reducedResult.get(0).toString());
28+
29+
}
30+
31+
@Test
32+
void testDeltaDebugging() throws Exception {
33+
TestEnvironment env = new TestEnvironment();
34+
List<String> fakeStatements = new ArrayList<>();
35+
for (int i = 0; i < 10000; i++) {
36+
String statement = "Statement_" + i + ";";
37+
fakeStatements.add(statement);
38+
}
39+
40+
env.setInitialStatementsFromStrings(fakeStatements);
41+
env.setBugInducingCondition(statements -> {
42+
String queries = TestEnvironment.getQueriesString(statements);
43+
return queries.contains("Statement_29;");
44+
});
45+
46+
env.runReduce();
47+
List<Query<?>> reducedQueries = env.getReducedStatements();
48+
String queriesString = TestEnvironment.getQueriesString(reducedQueries);
49+
assertEquals(queriesString, "Statement_29;");
50+
}
51+
52+
@Test
53+
void testDeltaDebuggingWithStatementsCombination() throws Exception {
54+
TestEnvironment env = new TestEnvironment();
55+
List<String> fakeStatements = new ArrayList<>();
56+
57+
String pattern = "(.*\\n)*(Statement_2;)\\n(.*\\n)*(Statement_318);\\n(.*\\n)*(Statement_990;)(.*\\n)*.*";
58+
for (int i = 0; i < 1000; i++) {
59+
String statement = "Statement_" + i + ";";
60+
fakeStatements.add(statement);
61+
}
62+
63+
env.setInitialStatementsFromStrings(fakeStatements);
64+
env.setBugInducingCondition(queryList -> {
65+
String queries = TestEnvironment.getQueriesString(queryList);
66+
return Pattern.matches(pattern, queries);
67+
});
68+
69+
env.runReduce();
70+
List<Query<?>> reducedQueries = env.getReducedStatements();
71+
String queriesString = TestEnvironment.getQueriesString(reducedQueries);
72+
assertEquals(queriesString, "Statement_2;\nStatement_318;\nStatement_990;");
73+
}
74+
75+
}

0 commit comments

Comments
 (0)