FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

Add per-site simplification to EET transformed query reduction by tlmorgan24 · Pull Request #1361 · sqlancer/sqlancer · GitHub

/ sqlancer Public

Add per-site simplification to EET transformed query reduction #1361

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
mrigger merged 1 commit into from
Aug 24, 2026
Conversation 1 Commits 1 Checks 25 Files changed
Merged

Add per-site simplification to EET transformed query reduction #1361

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension .java  (5) All 1 file type selected
Viewed files
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Unified
Split
Hide whitespace
Diff view
Unified
Split
Hide whitespace
115 changes: 93 additions & 22 deletions src/sqlancer/TransformationReducer.java
Show comments
View file
Open in desktop
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Show hidden characters
Original file line number Diff line number Diff line change
Expand Up @@ -5,16 +5,20 @@
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import sqlancer.common.query.Query;

/**
* Reduces the transformed query of a {@link TransformationReproducer} by disabling transformation sites, searching
* (with the same delta-debugging strategy as {@link StatementReducer}) for a minimal set of sites that still triggers
* the bug. Because each site is an individually equivalence-preserving rewrite, any subset of sites yields a
* transformed query that is still semantically equivalent to the original query, so the reduction is sound. This
* reducer runs after statement reduction, evaluating each candidate against the already-reduced database; for
* reproducers that do not implement {@link TransformationReproducer}, it does nothing.
* Reduces the transformed query of a {@link TransformationReproducer} in two phases. First, transformation sites are
* disabled with the same delta-debugging strategy as {@link StatementReducer}, searching for a minimal set of sites
* that still triggers the bug. Second, each surviving site is greedily simplified: its always-true (or always-false)
* condition is rendered as a literal constant, and its generated dead branch is replaced by a copy of the live
* expression, keeping each simplification only if the bug still triggers. Because each site is an individually
* equivalence-preserving rewrite and both simplifications preserve that property, every candidate transformed query
* remains semantically equivalent to the original query, so the reduction is sound. This reducer runs after statement
* reduction, evaluating each candidate against the already-reduced database; for reproducers that do not implement
* {@link TransformationReproducer}, it does nothing.
*
* @param <G>
* the DBMS-specific global state class
Expand All @@ -39,6 +43,9 @@ public class TransformationReducer<G extends GlobalState<O, ?, C>, O extends DBM

private Instant timeOfReductionBegins;

private Set<Integer> constantConditionSites;
private Set<Integer> copiedDeadBranchSites;

public TransformationReducer(DatabaseProvider<G, O, C> provider) {
this.provider = provider;
}
Expand All @@ -50,6 +57,18 @@ private boolean hasNotReachedLimit(long curr, long limit) {
return curr < limit;
}

private boolean withinLimits() {
return hasNotReachedLimit(currentReduceSteps, maxReduceSteps)
&& hasNotReachedLimit(currentReduceTime, maxReduceTime);
}

// Accounts one candidate evaluation against the step/time limits; returns whether reduction may continue.
private boolean registerStepAndCheckLimits() {
currentReduceSteps++;
currentReduceTime = Duration.between(timeOfReductionBegins, Instant.now()).getSeconds();
return withinLimits();
}

@SuppressWarnings("unchecked")
@Override
public void reduce(G state, Reproducer<G> reproducer, G newGlobalState) throws Exception {
Expand All @@ -73,19 +92,20 @@ public void reduce(G state, Reproducer<G> reproducer, G newGlobalState) throws E
for (int site = 0; site < transformationReproducer.getTransformationSiteCount(); site++) {
enabledSites.add(site);
}
// With every site disabled the transformed query renders as the original one, which cannot mismatch with
// itself, so a single remaining site cannot be reduced further.
if (enabledSites.size() < 2) {
if (enabledSites.isEmpty()) {
return;
}

timeOfReductionBegins = Instant.now();
currentReduceSteps = 0;
currentReduceTime = 0;
partitionNum = 2;
constantConditionSites = new HashSet<>();
copiedDeadBranchSites = new HashSet<>();

while (enabledSites.size() >= 2 && hasNotReachedLimit(currentReduceSteps, maxReduceSteps)
&& hasNotReachedLimit(currentReduceTime, maxReduceTime)) {
// Phase 1: delta-debug the enabled-site set. With every site disabled the transformed query renders as the
// original one, which cannot mismatch with itself, so a single remaining site is not removable further.
while (enabledSites.size() >= 2 && withinLimits()) {
observedChange = false;

enabledSites = tryReduction(transformationReproducer, newGlobalState, enabledSites);
Expand All @@ -99,9 +119,12 @@ && hasNotReachedLimit(currentReduceTime, maxReduceTime)) {
}
}

simplifySurvivingSites(transformationReproducer, newGlobalState, enabledSites);

// Leave the reproducer holding the reduced transformed query (the last candidate tried may have failed), so
// the final bug information reflects the reduction.
transformationReproducer.setEnabledTransformationSites(new HashSet<>(enabledSites));
transformationReproducer.applyTransformationSites(new HashSet<>(enabledSites), constantConditionSites,
copiedDeadBranchSites);
newGlobalState.getState().setStatements(new ArrayList<>(statements));
newGlobalState.getLogger().updateReducedBugInformation(transformationReproducer.getBugInformation());
newGlobalState.getLogger().logReduced(newGlobalState.getState(),
Expand All @@ -126,15 +149,11 @@ private List<Integer> tryReduction(TransformationReproducer<G> transformationRep
observedChange = true;
sites = candidateSites;
partitionNum = Math.max(partitionNum - 1, 2);
newGlobalState.getLogger().updateReducedBugInformation(transformationReproducer.getBugInformation());
newGlobalState.getLogger().logReduced(newGlobalState.getState());
logReductionStep(transformationReproducer, newGlobalState);
break;
}

currentReduceSteps++;
currentReduceTime = Duration.between(timeOfReductionBegins, Instant.now()).getSeconds();
if (!hasNotReachedLimit(currentReduceSteps, maxReduceSteps)
|| !hasNotReachedLimit(currentReduceTime, maxReduceTime)) {
if (!registerStepAndCheckLimits()) {
return sites;
}
start = start + subLength;
Expand All @@ -143,8 +162,59 @@ private List<Integer> tryReduction(TransformationReproducer<G> transformationRep
}

/**
* Whether the bug still triggers with only {@code candidateSites} applied to the transformed query, evaluated
* against a freshly recreated database populated with the (already reduced) generation statements.
* Phase 2: greedily simplifies each surviving site, keeping a simplification only if the bug still triggers. First
* the site's condition is rendered as a literal constant (the condition's embedded random predicate is often the
* bulk of the transformed query), then, for sites that have one, the generated dead branch is replaced by a copy of
* the live expression.
*
* @param transformationReproducer
* the reproducer whose transformed query is being reduced
* @param newGlobalState
* the state the candidates are evaluated against
* @param enabledSites
* the sites that survived phase 1
*/
private void simplifySurvivingSites(TransformationReproducer<G> transformationReproducer, G newGlobalState,
List<Integer> enabledSites) {
Set<Integer> deadBranchSites = transformationReproducer.getDeadBranchSites();
for (int site : enabledSites) {
if (!withinLimits()) {
return;
}
constantConditionSites.add(site);
if (bugStillTriggersWith(transformationReproducer, newGlobalState, enabledSites)) {
logReductionStep(transformationReproducer, newGlobalState);
} else {
constantConditionSites.remove(site);
}
if (!registerStepAndCheckLimits()) {
return;
}

if (deadBranchSites.contains(site)) {
copiedDeadBranchSites.add(site);
if (bugStillTriggersWith(transformationReproducer, newGlobalState, enabledSites)) {
logReductionStep(transformationReproducer, newGlobalState);
} else {
copiedDeadBranchSites.remove(site);
}
if (!registerStepAndCheckLimits()) {
return;
}
}
}
}

// Logs an accepted reduction step, refreshing the logged bug information with the re-rendered transformed query.
private void logReductionStep(TransformationReproducer<G> transformationReproducer, G newGlobalState) {
newGlobalState.getLogger().updateReducedBugInformation(transformationReproducer.getBugInformation());
newGlobalState.getLogger().logReduced(newGlobalState.getState());
}

/**
* Whether the bug still triggers with the given sites applied to the transformed query (further simplified per the
* current constant-condition and copied-dead-branch sets), evaluated against a freshly recreated database populated
* with the (already reduced) generation statements.
*
* @param transformationReproducer
* the reproducer whose transformed query is being reduced
Expand All @@ -153,11 +223,12 @@ private List<Integer> tryReduction(TransformationReproducer<G> transformationRep
* @param candidateSites
* the transformation sites to keep applied
*
* @return {@code true} if the bug still triggers with the candidate sites
* @return {@code true} if the bug still triggers with the candidate configuration
*/
private boolean bugStillTriggersWith(TransformationReproducer<G> transformationReproducer, G newGlobalState,
List<Integer> candidateSites) {
transformationReproducer.setEnabledTransformationSites(new HashSet<>(candidateSites));
transformationReproducer.applyTransformationSites(new HashSet<>(candidateSites), constantConditionSites,
copiedDeadBranchSites);
try (C con2 = provider.createDatabase(newGlobalState)) {
newGlobalState.setConnection(con2);
// discard the setup statements createDatabase just logged into the state
Expand Down
23 changes: 20 additions & 3 deletions src/sqlancer/TransformationReproducer.java
Show comments
View file
Open in desktop
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Show hidden characters
Original file line number Diff line number Diff line change
Expand Up @@ -23,11 +23,28 @@ public interface TransformationReproducer<G extends GlobalState<?, ?, ?>> extend
int getTransformationSiteCount();

/**
* Re-renders the transformed query with only the given transformation sites applied. Later
* {@link #bugStillTriggers} calls and {@link #getBugInformation} use the re-rendered query.
* The transformation sites whose rule application embeds a generated dead-branch expression, which
* {@link #applyTransformationSites} may replace with a copy of the live expression.
*
* @return the indices of the sites with a generated dead branch
*/
Set<Integer> getDeadBranchSites();

/**
* Re-renders the transformed query with only the given transformation sites applied, further simplified per site: a
* site in {@code constantConditionSites} renders its always-true (or always-false) condition as the literal
* constant of the same truth value, and a site in {@code copiedDeadBranchSites} replaces its generated dead branch
* with a copy of the live expression. Both simplifications preserve the equivalence of the transformed query, like
* disabling a site does. Later {@link #bugStillTriggers} calls and {@link #getBugInformation} use the re-rendered
* query.
*
* @param enabledSites
* the indices ({@code 0} to {@code getTransformationSiteCount() - 1}) of the sites to keep applied
* @param constantConditionSites
* the indices of the enabled sites whose condition is rendered as a literal constant
* @param copiedDeadBranchSites
* the indices of the enabled sites whose dead branch is replaced by a copy of the live expression
*/
void setEnabledTransformationSites(Set<Integer> enabledSites);
void applyTransformationSites(Set<Integer> enabledSites, Set<Integer> constantConditionSites,
Set<Integer> copiedDeadBranchSites);
}
60 changes: 50 additions & 10 deletions src/sqlancer/common/oracle/EETOracle.java
Show comments
View file
Open in desktop
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Show hidden characters
Original file line number Diff line number Diff line change
Expand Up @@ -2,6 +2,7 @@

import java.sql.SQLException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

Expand Down Expand Up @@ -94,36 +95,75 @@ public int getTransformationSiteCount() {
}

@Override
public void setEnabledTransformationSites(Set<Integer> enabledSites) {
if (enabledSites.size() == getTransformationSiteCount()) {
// With every site enabled, the transformed query is the unreduced one; keep the exact string that
// originally detected the bug rather than re-rendering it (rendering an AST draws random textual
public Set<Integer> getDeadBranchSites() {
// Global site indices are assigned over the fetch columns' records first (in column order), then the
// WHERE clause's record.
Set<Integer> deadBranchSites = new HashSet<>();
int offset = 0;
for (EETTransformer.TransformationRecord record : fetchColumnRecords) {
for (int site : record.getDeadBranchSites()) {
deadBranchSites.add(offset + site);
}
offset += record.getSiteCount();
}
for (int site : whereClauseRecord.getDeadBranchSites()) {
deadBranchSites.add(offset + site);
}
return deadBranchSites;
}

@Override
public void applyTransformationSites(Set<Integer> enabledSites, Set<Integer> constantConditionSites,
Set<Integer> copiedDeadBranchSites) {
if (enabledSites.size() == getTransformationSiteCount() && constantConditionSites.isEmpty()
&& copiedDeadBranchSites.isEmpty()) {
// With every site fully enabled, the transformed query is the unreduced one; keep the exact string
// that originally detected the bug rather than re-rendering it (rendering an AST draws random textual
// variants, so a re-render would produce a semantically equal but untested string).
transformedQueryString = initialTransformedQueryString;
return;
}
// Pin the RNG while re-rendering so the same enabled sites always yield the same query string; the string
// tested during reduction is then exactly the string the reduced test case reports.
// Pin the RNG while re-rendering so the same site configuration always yields the same query string; the
// string tested during reduction is then exactly the string the reduced test case reports.
transformedQueryString = Randomly.withFixedSeedRandom(() -> {
// Global site indices are assigned over the fetch columns' records first (in column order), then the
// WHERE clause's record.
List<E> replayedFetchColumns = new ArrayList<>();
int offset = 0;
for (int i = 0; i < fetchColumns.size(); i++) {
int base = offset;
replayedFetchColumns.add(transformer.replay(fetchColumns.get(i), false, fetchColumnRecords.get(i),
site -> enabledSites.contains(base + site)));
directives(enabledSites, constantConditionSites, copiedDeadBranchSites, offset)));
offset += fetchColumnRecords.get(i).getSiteCount();
}
int whereBase = offset;
E replayedWhereClause = transformer.replay(whereClause, true, whereClauseRecord,
site -> enabledSites.contains(whereBase + site));
directives(enabledSites, constantConditionSites, copiedDeadBranchSites, offset));
select.setFetchColumns(replayedFetchColumns);
select.setWhereClause(replayedWhereClause);
return select.asString();
});
}

// Translates the global-index site sets into a record-local directives view starting at the given offset.
private EETTransformer.SiteDirectives directives(Set<Integer> enabledSites, Set<Integer> constantConditionSites,
Set<Integer> copiedDeadBranchSites, int offset) {
return new EETTransformer.SiteDirectives() {
@Override
public boolean isEnabled(int site) {
return enabledSites.contains(offset + site);
}

@Override
public boolean useConstantCondition(int site) {
return constantConditionSites.contains(offset + site);
}

@Override
public boolean useCopiedDeadBranch(int site) {
return copiedDeadBranchSites.contains(offset + site);
}
};
}

@Override
protected List<String> evaluateOriginal(G globalState) throws SQLException {
// Re-execute against the current (reduced) database instead of comparing against a cached result set,
Expand Down
Loading
Loading
Back | FazBrowse Home | New Git URL