Merge "Integrate dexfuzz with bisection search"

24 files changed, 255 insertions, 58 deletions

diff --git a/tools/dexfuzz/src/dexfuzz/DexFuzz.java b/tools/dexfuzz/src/dexfuzz/DexFuzz.java
index 04bbbf8b62..7337ffc2b6 100644
--- a/tools/dexfuzz/src/dexfuzz/DexFuzz.java
+++ b/tools/dexfuzz/src/dexfuzz/DexFuzz.java
@@ -22,6 +22,7 @@ import dexfuzz.fuzzers.FuzzerMultipleNoExecute;
 import dexfuzz.fuzzers.FuzzerSingleExecute;
 import dexfuzz.fuzzers.FuzzerSingleNoExecute;
 import dexfuzz.listeners.BaseListener;
+import dexfuzz.listeners.BisectionSearchListener;
 import dexfuzz.listeners.ConsoleLoggerListener;
 import dexfuzz.listeners.LogFileListener;
 import dexfuzz.listeners.MultiplexerListener;
@@ -66,6 +67,10 @@ public class DexFuzz {
       }
       // Add the file logging listener.
       multipleListener.addListener(new LogFileListener(Options.reportLogFile));
+      if (Options.runBisectionSearch) {
+        // Add the bisection search listener.
+        multipleListener.addListener(new BisectionSearchListener());
+      }
       // Add the unique program tracker.
       multipleListener.addListener(new UniqueProgramTrackerListener(Options.uniqueDatabaseFile));
       listener = multipleListener;
diff --git a/tools/dexfuzz/src/dexfuzz/ExecutionResult.java b/tools/dexfuzz/src/dexfuzz/ExecutionResult.java
index 3a8c6cb9a5..f85af1ab0d 100644
--- a/tools/dexfuzz/src/dexfuzz/ExecutionResult.java
+++ b/tools/dexfuzz/src/dexfuzz/ExecutionResult.java
@@ -31,6 +31,7 @@ public class ExecutionResult {
   private String flattenedError;
   private String flattenedErrorWithNewlines;
   private String flattenedAll;
+  private String flattenedAllWithNewlines;
 
   private static final int TIMEOUT_RETURN_VALUE = 124;
   private static final int SIGABORT_RETURN_VALUE = 134;
@@ -101,6 +102,16 @@ public class ExecutionResult {
     return flattenedAll;
   }
 
+  /**
+   * Get both the output and error, concatenated together, including newline characters.
+   */
+  public String getFlattenedAllWithNewlines() {
+    if (flattenedAllWithNewlines == null) {
+      flattenedAllWithNewlines = getFlattenedOutputWithNewlines() + getFlattenedErrorWithNewlines();
+    }
+    return flattenedAllWithNewlines;
+  }
+
   public boolean isTimeout() {
     return (returnValue == TIMEOUT_RETURN_VALUE);
   }
diff --git a/tools/dexfuzz/src/dexfuzz/Options.java b/tools/dexfuzz/src/dexfuzz/Options.java
index 2e929c80e3..b442b221fa 100644
--- a/tools/dexfuzz/src/dexfuzz/Options.java
+++ b/tools/dexfuzz/src/dexfuzz/Options.java
@@ -78,6 +78,7 @@ public class Options {
   public static boolean skipMutation;
   public static boolean dumpMutations;
   public static boolean loadMutations;
+  public static boolean runBisectionSearch;
 
   /**
    * Print out usage information about dexfuzz, and then exit.
@@ -138,6 +139,7 @@ public class Options {
     Log.always("  --report-unique        : Print out information about unique programs generated");
     Log.always("  --unique-db=<file>     : Use <file> store results about unique programs");
     Log.always("                           (Default: unique_progs.db)");
+    Log.always("  --bisection-search     : Run bisection search for divergences");
     Log.always("");
     System.exit(0);
   }
@@ -197,6 +199,8 @@ public class Options {
       methodMutations = 1;
       minMethods = 1;
       maxMethods = 1;
+    } else if (flag.equals("bisection-search")) {
+      runBisectionSearch = true;
     } else if (flag.equals("help")) {
       usage();
     } else {
diff --git a/tools/dexfuzz/src/dexfuzz/executors/Arm64InterpreterExecutor.java b/tools/dexfuzz/src/dexfuzz/executors/Arm64InterpreterExecutor.java
index 227c698fce..55462072f0 100644
--- a/tools/dexfuzz/src/dexfuzz/executors/Arm64InterpreterExecutor.java
+++ b/tools/dexfuzz/src/dexfuzz/executors/Arm64InterpreterExecutor.java
@@ -21,11 +21,12 @@ import dexfuzz.listeners.BaseListener;
 public class Arm64InterpreterExecutor extends Executor {
 
   public Arm64InterpreterExecutor(BaseListener listener, Device device) {
-    super("ARM64 Interpreter", 30, listener, Architecture.ARM64, device, false);
+    super("ARM64 Interpreter", 30, listener, Architecture.ARM64, device,
+        /*needsCleanCodeCache*/ false, /*isBisectable*/ false);
   }
 
   @Override
-  public void execute(String programName) {
+  protected String constructCommand(String programName) {
     StringBuilder commandBuilder = new StringBuilder();
     commandBuilder.append("dalvikvm64 -Xint ");
     if (device.noBootImageAvailable()) {
@@ -33,6 +34,6 @@ public class Arm64InterpreterExecutor extends Executor {
     }
     commandBuilder.append("-cp ").append(testLocation).append("/").append(programName).append(" ");
     commandBuilder.append(executeClass);
-    executionResult = executeCommandWithTimeout(commandBuilder.toString(), true);
+    return commandBuilder.toString();
   }
 }
diff --git a/tools/dexfuzz/src/dexfuzz/executors/Arm64OptimizingBackendExecutor.java b/tools/dexfuzz/src/dexfuzz/executors/Arm64OptimizingBackendExecutor.java
index bfa87b7349..72e36e86ea 100644
--- a/tools/dexfuzz/src/dexfuzz/executors/Arm64OptimizingBackendExecutor.java
+++ b/tools/dexfuzz/src/dexfuzz/executors/Arm64OptimizingBackendExecutor.java
@@ -21,11 +21,12 @@ import dexfuzz.listeners.BaseListener;
 public class Arm64OptimizingBackendExecutor extends Executor {
 
   public Arm64OptimizingBackendExecutor(BaseListener listener, Device device) {
-    super("ARM64 Optimizing Backend", 5, listener, Architecture.ARM64, device, true);
+    super("ARM64 Optimizing Backend", 5, listener, Architecture.ARM64, device,
+        /*needsCleanCodeCache*/ true, /*isBisectable*/ true);
   }
 
   @Override
-  public void execute(String programName) {
+  protected String constructCommand(String programName) {
     StringBuilder commandBuilder = new StringBuilder();
     commandBuilder.append("dalvikvm64 -Xcompiler-option --compiler-backend=Optimizing ");
     if (device.noBootImageAvailable()) {
@@ -33,6 +34,6 @@ public class Arm64OptimizingBackendExecutor extends Executor {
     }
     commandBuilder.append("-cp ").append(testLocation).append("/").append(programName).append(" ");
     commandBuilder.append(executeClass);
-    executionResult = executeCommandWithTimeout(commandBuilder.toString(), true);
+    return commandBuilder.toString();
   }
 }
diff --git a/tools/dexfuzz/src/dexfuzz/executors/Arm64QuickBackendExecutor.java b/tools/dexfuzz/src/dexfuzz/executors/Arm64QuickBackendExecutor.java
index 7251ec5535..d9228ed08f 100644
--- a/tools/dexfuzz/src/dexfuzz/executors/Arm64QuickBackendExecutor.java
+++ b/tools/dexfuzz/src/dexfuzz/executors/Arm64QuickBackendExecutor.java
@@ -21,11 +21,12 @@ import dexfuzz.listeners.BaseListener;
 public class Arm64QuickBackendExecutor extends Executor {
 
   public Arm64QuickBackendExecutor(BaseListener listener, Device device) {
-    super("ARM64 Quick Backend", 5, listener, Architecture.ARM64, device, true);
+    super("ARM64 Quick Backend", 5, listener, Architecture.ARM64, device,
+        /*needsCleanCodeCache*/ true, /*isBisectable*/ false);
   }
 
   @Override
-  public void execute(String programName) {
+  protected String constructCommand(String programName) {
     StringBuilder commandBuilder = new StringBuilder();
     commandBuilder.append("dalvikvm64 -Xcompiler-option --compiler-backend=Quick ");
     if (device.noBootImageAvailable()) {
@@ -33,6 +34,6 @@ public class Arm64QuickBackendExecutor extends Executor {
     }
     commandBuilder.append("-cp ").append(testLocation).append("/").append(programName).append(" ");
     commandBuilder.append(executeClass);
-    executionResult = executeCommandWithTimeout(commandBuilder.toString(), true);
+    return commandBuilder.toString();
   }
 }
diff --git a/tools/dexfuzz/src/dexfuzz/executors/ArmInterpreterExecutor.java b/tools/dexfuzz/src/dexfuzz/executors/ArmInterpreterExecutor.java
index d17ea87785..bdfad3d868 100644
--- a/tools/dexfuzz/src/dexfuzz/executors/ArmInterpreterExecutor.java
+++ b/tools/dexfuzz/src/dexfuzz/executors/ArmInterpreterExecutor.java
@@ -21,11 +21,12 @@ import dexfuzz.listeners.BaseListener;
 public class ArmInterpreterExecutor extends Executor {
 
   public ArmInterpreterExecutor(BaseListener listener, Device device) {
-    super("ARM Interpreter", 30, listener, Architecture.ARM, device, false);
+    super("ARM Interpreter", 30, listener, Architecture.ARM, device,
+        /*needsCleanCodeCache*/ false, /*isBisectable*/ false);
   }
 
   @Override
-  public void execute(String programName) {
+  protected String constructCommand(String programName) {
     StringBuilder commandBuilder = new StringBuilder();
     commandBuilder.append("dalvikvm32 -Xint ");
     if (device.noBootImageAvailable()) {
@@ -33,6 +34,6 @@ public class ArmInterpreterExecutor extends Executor {
     }
     commandBuilder.append("-cp ").append(testLocation).append("/").append(programName).append(" ");
     commandBuilder.append(executeClass);
-    executionResult = executeCommandWithTimeout(commandBuilder.toString(), true);
+    return commandBuilder.toString();
   }
 }
diff --git a/tools/dexfuzz/src/dexfuzz/executors/ArmOptimizingBackendExecutor.java b/tools/dexfuzz/src/dexfuzz/executors/ArmOptimizingBackendExecutor.java
index 947bb2fa35..ded8cf9914 100644
--- a/tools/dexfuzz/src/dexfuzz/executors/ArmOptimizingBackendExecutor.java
+++ b/tools/dexfuzz/src/dexfuzz/executors/ArmOptimizingBackendExecutor.java
@@ -21,11 +21,12 @@ import dexfuzz.listeners.BaseListener;
 public class ArmOptimizingBackendExecutor extends Executor {
 
   public ArmOptimizingBackendExecutor(BaseListener listener, Device device) {
-    super("ARM Optimizing Backend", 5, listener, Architecture.ARM, device, true);
+    super("ARM Optimizing Backend", 5, listener, Architecture.ARM, device,
+        /*needsCleanCodeCache*/ true, /*isBisectable*/ true);
   }
 
   @Override
-  public void execute(String programName) {
+  protected String constructCommand(String programName) {
     StringBuilder commandBuilder = new StringBuilder();
     commandBuilder.append("dalvikvm32 -Xcompiler-option --compiler-backend=Optimizing ");
     if (device.noBootImageAvailable()) {
@@ -33,6 +34,6 @@ public class ArmOptimizingBackendExecutor extends Executor {
     }
     commandBuilder.append("-cp ").append(testLocation).append("/").append(programName).append(" ");
     commandBuilder.append(executeClass);
-    executionResult = executeCommandWithTimeout(commandBuilder.toString(), true);
+    return commandBuilder.toString();
   }
 }
diff --git a/tools/dexfuzz/src/dexfuzz/executors/ArmQuickBackendExecutor.java b/tools/dexfuzz/src/dexfuzz/executors/ArmQuickBackendExecutor.java
index 7d226e89a3..0eb35f78c9 100644
--- a/tools/dexfuzz/src/dexfuzz/executors/ArmQuickBackendExecutor.java
+++ b/tools/dexfuzz/src/dexfuzz/executors/ArmQuickBackendExecutor.java
@@ -21,11 +21,12 @@ import dexfuzz.listeners.BaseListener;
 public class ArmQuickBackendExecutor extends Executor {
 
   public ArmQuickBackendExecutor(BaseListener listener, Device device) {
-    super("ARM Quick Backend", 5, listener, Architecture.ARM, device, true);
+    super("ARM Quick Backend", 5, listener, Architecture.ARM, device,
+        /*needsCleanCodeCache*/ true, /*isBisectable*/ false);
   }
 
   @Override
-  public void execute(String programName) {
+  protected String constructCommand(String programName) {
     StringBuilder commandBuilder = new StringBuilder();
     commandBuilder.append("dalvikvm32 -Xcompiler-option --compiler-backend=Quick ");
     if (device.noBootImageAvailable()) {
@@ -33,6 +34,6 @@ public class ArmQuickBackendExecutor extends Executor {
     }
     commandBuilder.append("-cp ").append(testLocation).append("/").append(programName).append(" ");
     commandBuilder.append(executeClass);
-    executionResult = executeCommandWithTimeout(commandBuilder.toString(), true);
+    return commandBuilder.toString();
   }
 }
diff --git a/tools/dexfuzz/src/dexfuzz/executors/Device.java b/tools/dexfuzz/src/dexfuzz/executors/Device.java
index 45538fe7de..72f73b88f5 100644
--- a/tools/dexfuzz/src/dexfuzz/executors/Device.java
+++ b/tools/dexfuzz/src/dexfuzz/executors/Device.java
@@ -18,7 +18,11 @@ package dexfuzz.executors;
 
 import java.io.IOException;
 import java.io.File;
+import java.util.ArrayList;
+import java.util.List;
 import java.util.Map;
+import java.util.regex.Matcher;
+import java.util.regex.Pattern;
 
 import dexfuzz.ExecutionResult;
 import dexfuzz.Log;
@@ -139,6 +143,10 @@ public class Device {
     return isHost;
   }
 
+  public boolean isUsingSpecificDevice() {
+    return usingSpecificDevice;
+  }
+
   /**
    * Certain AOSP builds of Android may not have a full boot.art built. This will be set if
    * we use --no-boot-image, and is used by Executors when deciding the arguments for dalvikvm
@@ -186,7 +194,7 @@ public class Device {
     Log.info("Executing: " + command);
 
     try {
-      ProcessBuilder processBuilder = new ProcessBuilder(command.split(" "));
+      ProcessBuilder processBuilder = new ProcessBuilder(splitCommand(command));
       processBuilder.environment().put("ANDROID_ROOT", androidHostOut);
       if (Options.executeOnHost) {
         processBuilder.environment().put("ANDROID_DATA", androidData);
@@ -229,6 +237,17 @@ public class Device {
     return result;
   }
 
+  /**
+   * Splits command respecting single quotes.
+   */
+  private List<String> splitCommand(String command) {
+    List<String> ret = new ArrayList<String>();
+    Matcher m = Pattern.compile("(\'[^\']+\'| *[^ ]+ *)").matcher(command);
+    while (m.find())
+      ret.add(m.group(1).trim().replace("\'", ""));
+    return ret;
+  }
+
   private String getExecutionPrefixWithAdb(String command) {
     if (usingSpecificDevice) {
       return String.format("adb -s %s %s ", deviceName, command);
diff --git a/tools/dexfuzz/src/dexfuzz/executors/Executor.java b/tools/dexfuzz/src/dexfuzz/executors/Executor.java
index 1e5d4be1a2..c62a3ad322 100644
--- a/tools/dexfuzz/src/dexfuzz/executors/Executor.java
+++ b/tools/dexfuzz/src/dexfuzz/executors/Executor.java
@@ -39,9 +39,10 @@ public abstract class Executor {
   protected Architecture architecture;
   protected Device device;
   private boolean needsCleanCodeCache;
+  private boolean isBisectable;
 
   protected Executor(String name, int timeout, BaseListener listener, Architecture architecture,
-      Device device, boolean needsCleanCodeCache) {
+      Device device, boolean needsCleanCodeCache, boolean isBisectable) {
     executeClass = Options.executeClass;
 
     if (Options.shortTimeouts) {
@@ -55,6 +56,7 @@ public abstract class Executor {
     this.architecture = architecture;
     this.device = device;
     this.needsCleanCodeCache = needsCleanCodeCache;
+    this.isBisectable = isBisectable;
 
     if (Options.executeOnHost) {
       this.testLocation = System.getProperty("user.dir");
@@ -169,7 +171,33 @@ public abstract class Executor {
    * Executor subclasses need to override this, to construct their arguments for dalvikvm
    * invocation correctly.
    */
-  public abstract void execute(String programName);
+  protected abstract String constructCommand(String programName);
+
+  /**
+   * Executes runtime.
+   */
+  public void execute(String programName) {
+    executionResult = executeCommandWithTimeout(constructCommand(programName), true);
+  }
+
+  /**
+   * Runs bisection bug search.
+   */
+  public ExecutionResult runBisectionSearch(String programName, String expectedOutputFile, String logFile) {
+    assert(isBisectable);
+    String runtimeCommand = constructCommand(programName);
+    StringBuilder commandBuilder = new StringBuilder();
+    commandBuilder.append("bisection_search.py --raw-cmd '").append(runtimeCommand);
+    commandBuilder.append("' --expected-output=").append(expectedOutputFile);
+    commandBuilder.append(" --logfile=").append(logFile);
+    if (!device.isHost()) {
+      commandBuilder.append(" --device");
+      if (device.isUsingSpecificDevice()) {
+        commandBuilder.append(" --specific-device=").append(device.getName());
+      }
+    }
+    return device.executeCommand(commandBuilder.toString(), true, outputConsumer, errorConsumer);
+  }
 
   /**
    * Fuzzer.checkForArchitectureSplit() will use this determine the architecture of the Executor.
@@ -207,4 +235,8 @@ public abstract class Executor {
   public void finishedWithProgramOnDevice() {
     device.resetProgramPushed();
   }
+
+  public boolean isBisectable() {
+    return isBisectable;
+  }
 }
diff --git a/tools/dexfuzz/src/dexfuzz/executors/Mips64InterpreterExecutor.java b/tools/dexfuzz/src/dexfuzz/executors/Mips64InterpreterExecutor.java
index f31920103b..eee6111140 100644
--- a/tools/dexfuzz/src/dexfuzz/executors/Mips64InterpreterExecutor.java
+++ b/tools/dexfuzz/src/dexfuzz/executors/Mips64InterpreterExecutor.java
@@ -21,16 +21,17 @@ import dexfuzz.listeners.BaseListener;
 public class Mips64InterpreterExecutor extends Executor {
 
   public Mips64InterpreterExecutor(BaseListener listener, Device device) {
-    super("MIPS64 Interpreter", 30, listener, Architecture.MIPS64, device, false);
+    super("MIPS64 Interpreter", 30, listener, Architecture.MIPS64, device,
+        /*needsCleanCodeCache*/ false, /*isBisectable*/ false);
   }
 
   @Override
-  public void execute(String programName) {
+  protected String constructCommand(String programName) {
     StringBuilder commandBuilder = new StringBuilder();
     commandBuilder.append("dalvikvm64 -Xint ");
     commandBuilder.append("-cp ").append(testLocation).append("/").append(programName).append(" ");
     commandBuilder.append(executeClass);
-    executionResult = executeCommandWithTimeout(commandBuilder.toString(), true);
+    return commandBuilder.toString();
 
   }
-}
\ No newline at end of file
+}
diff --git a/tools/dexfuzz/src/dexfuzz/executors/Mips64OptimizingBackendExecutor.java b/tools/dexfuzz/src/dexfuzz/executors/Mips64OptimizingBackendExecutor.java
index a6784e67a8..72d43e732c 100644
--- a/tools/dexfuzz/src/dexfuzz/executors/Mips64OptimizingBackendExecutor.java
+++ b/tools/dexfuzz/src/dexfuzz/executors/Mips64OptimizingBackendExecutor.java
@@ -21,15 +21,16 @@ import dexfuzz.listeners.BaseListener;
 public class Mips64OptimizingBackendExecutor extends Executor {
 
   public Mips64OptimizingBackendExecutor(BaseListener listener, Device device) {
-    super("MIPS64 Optimizing Backend", 5, listener, Architecture.MIPS64, device, true);
+    super("MIPS64 Optimizing Backend", 5, listener, Architecture.MIPS64, device,
+        /*needsCleanCodeCache*/ true, /*isBisectable*/ true);
   }
 
   @Override
-  public void execute(String programName) {
+  protected String constructCommand(String programName) {
     StringBuilder commandBuilder = new StringBuilder();
     commandBuilder.append("dalvikvm64 -Xcompiler-option --compiler-backend=Optimizing ");
     commandBuilder.append("-cp ").append(testLocation).append("/").append(programName).append(" ");
     commandBuilder.append(executeClass);
-    executionResult = executeCommandWithTimeout(commandBuilder.toString(), true);
+    return commandBuilder.toString();
   }
 }
diff --git a/tools/dexfuzz/src/dexfuzz/executors/Mips64QuickBackendExecutor.java b/tools/dexfuzz/src/dexfuzz/executors/Mips64QuickBackendExecutor.java
index 36e39c27e1..e7e5ff68e8 100644
--- a/tools/dexfuzz/src/dexfuzz/executors/Mips64QuickBackendExecutor.java
+++ b/tools/dexfuzz/src/dexfuzz/executors/Mips64QuickBackendExecutor.java
@@ -21,15 +21,16 @@ import dexfuzz.listeners.BaseListener;
 public class Mips64QuickBackendExecutor extends Executor {
 
   public Mips64QuickBackendExecutor(BaseListener listener, Device device) {
-    super("MIPS64 Quick Backend", 5, listener, Architecture.MIPS64, device, true);
+    super("MIPS64 Quick Backend", 5, listener, Architecture.MIPS64, device,
+        /*needsCleanCodeCache*/ true, /*isBisectable*/ false);
   }
 
   @Override
-  public void execute(String programName) {
+  protected String constructCommand(String programName) {
     StringBuilder commandBuilder = new StringBuilder();
     commandBuilder.append("dalvikvm64 -Xcompiler-option --compiler-backend=Quick ");
     commandBuilder.append("-cp ").append(testLocation).append("/").append(programName).append(" ");
     commandBuilder.append(executeClass);
-    executionResult = executeCommandWithTimeout(commandBuilder.toString(), true);
+    return commandBuilder.toString();
   }
 }
diff --git a/tools/dexfuzz/src/dexfuzz/executors/MipsInterpreterExecutor.java b/tools/dexfuzz/src/dexfuzz/executors/MipsInterpreterExecutor.java
index 4268c76a95..4a403dbf85 100644
--- a/tools/dexfuzz/src/dexfuzz/executors/MipsInterpreterExecutor.java
+++ b/tools/dexfuzz/src/dexfuzz/executors/MipsInterpreterExecutor.java
@@ -21,15 +21,16 @@ import dexfuzz.listeners.BaseListener;
 public class MipsInterpreterExecutor extends Executor {
 
   public MipsInterpreterExecutor(BaseListener listener, Device device) {
-    super("MIPS Interpreter", 30, listener, Architecture.MIPS, device, false);
+    super("MIPS Interpreter", 30, listener, Architecture.MIPS, device,
+        /*needsCleanCodeCache*/ false, /*isBisectable*/ false);
   }
 
   @Override
-  public void execute(String programName) {
+  protected String constructCommand(String programName) {
     StringBuilder commandBuilder = new StringBuilder();
     commandBuilder.append("dalvikvm32 -Xint ");
     commandBuilder.append("-cp ").append(testLocation).append("/").append(programName).append(" ");
     commandBuilder.append(executeClass);
-    executionResult = executeCommandWithTimeout(commandBuilder.toString(), true);
+    return commandBuilder.toString();
   }
 }
diff --git a/tools/dexfuzz/src/dexfuzz/executors/MipsOptimizingBackendExecutor.java b/tools/dexfuzz/src/dexfuzz/executors/MipsOptimizingBackendExecutor.java
index d64b1cea23..63f6858cf5 100644
--- a/tools/dexfuzz/src/dexfuzz/executors/MipsOptimizingBackendExecutor.java
+++ b/tools/dexfuzz/src/dexfuzz/executors/MipsOptimizingBackendExecutor.java
@@ -21,15 +21,16 @@ import dexfuzz.listeners.BaseListener;
 public class MipsOptimizingBackendExecutor extends Executor {
 
   public MipsOptimizingBackendExecutor(BaseListener listener, Device device) {
-    super("MIPS Optimizing Backend", 5, listener, Architecture.MIPS, device, true);
+    super("MIPS Optimizing Backend", 5, listener, Architecture.MIPS, device,
+        /*needsCleanCodeCache*/ true, /*isBisectable*/ true);
   }
 
   @Override
-  public void execute(String programName) {
+  protected String constructCommand(String programName) {
     StringBuilder commandBuilder = new StringBuilder();
     commandBuilder.append("dalvikvm32 -Xcompiler-option --compiler-backend=Optimizing ");
     commandBuilder.append("-cp ").append(testLocation).append("/").append(programName).append(" ");
     commandBuilder.append(executeClass);
-    executionResult = executeCommandWithTimeout(commandBuilder.toString(), true);
+    return commandBuilder.toString();
   }
 }
diff --git a/tools/dexfuzz/src/dexfuzz/executors/MipsQuickBackendExecutor.java b/tools/dexfuzz/src/dexfuzz/executors/MipsQuickBackendExecutor.java
index 0ea166ba68..b262090333 100644
--- a/tools/dexfuzz/src/dexfuzz/executors/MipsQuickBackendExecutor.java
+++ b/tools/dexfuzz/src/dexfuzz/executors/MipsQuickBackendExecutor.java
@@ -21,15 +21,16 @@ import dexfuzz.listeners.BaseListener;
 public class MipsQuickBackendExecutor extends Executor {
 
   public MipsQuickBackendExecutor(BaseListener listener, Device device) {
-    super("MIPS Quick Backend", 5, listener, Architecture.MIPS, device, true);
+    super("MIPS Quick Backend", 5, listener, Architecture.MIPS, device,
+        /*needsCleanCodeCache*/ true, /*isBisectable*/ false);
   }
 
   @Override
-  public void execute(String programName) {
+  protected String constructCommand(String programName) {
     StringBuilder commandBuilder = new StringBuilder();
     commandBuilder.append("dalvikvm32 -Xcompiler-option --compiler-backend=Quick ");
     commandBuilder.append("-cp ").append(testLocation).append("/").append(programName).append(" ");
     commandBuilder.append(executeClass);
-    executionResult = executeCommandWithTimeout(commandBuilder.toString(), true);
+    return commandBuilder.toString();
   }
 }
diff --git a/tools/dexfuzz/src/dexfuzz/executors/X86InterpreterExecutor.java b/tools/dexfuzz/src/dexfuzz/executors/X86InterpreterExecutor.java
index 510f0d0ddd..a8e68a7e44 100644
--- a/tools/dexfuzz/src/dexfuzz/executors/X86InterpreterExecutor.java
+++ b/tools/dexfuzz/src/dexfuzz/executors/X86InterpreterExecutor.java
@@ -22,11 +22,12 @@ import dexfuzz.listeners.BaseListener;
 public class X86InterpreterExecutor extends Executor {
 
   public X86InterpreterExecutor(BaseListener listener, Device device) {
-    super("x86 Interpreter", 30, listener, Architecture.X86, device, false);
+    super("x86 Interpreter", 30, listener, Architecture.X86, device,
+        /*needsCleanCodeCache*/ false, /*isBisectable*/ false);
   }
 
   @Override
-  public void execute(String programName) {
+  protected String constructCommand(String programName) {
     StringBuilder commandBuilder = new StringBuilder();
     commandBuilder.append("dalvikvm32 -Xint ");
     if (Options.executeOnHost) {
@@ -34,6 +35,6 @@ public class X86InterpreterExecutor extends Executor {
     }
     commandBuilder.append("-cp ").append(testLocation).append("/").append(programName).append(" ");
     commandBuilder.append(executeClass);
-    executionResult = executeCommandWithTimeout(commandBuilder.toString(), true);
+    return commandBuilder.toString();
   }
 }
diff --git a/tools/dexfuzz/src/dexfuzz/executors/X86OptimizingBackendExecutor.java b/tools/dexfuzz/src/dexfuzz/executors/X86OptimizingBackendExecutor.java
index 81d728535c..5908a8b961 100644
--- a/tools/dexfuzz/src/dexfuzz/executors/X86OptimizingBackendExecutor.java
+++ b/tools/dexfuzz/src/dexfuzz/executors/X86OptimizingBackendExecutor.java
@@ -22,11 +22,12 @@ import dexfuzz.listeners.BaseListener;
 public class X86OptimizingBackendExecutor extends Executor {
 
   public X86OptimizingBackendExecutor(BaseListener listener, Device device) {
-    super("x86 Optimizing Backend", 5, listener, Architecture.X86, device, true);
+    super("x86 Optimizing Backend", 5, listener, Architecture.X86, device,
+        /*needsCleanCodeCache*/ true, /*isBisectable*/ true);
   }
 
   @Override
-  public void execute(String programName) {
+  protected String constructCommand(String programName) {
     StringBuilder commandBuilder = new StringBuilder();
     commandBuilder.append("dalvikvm32 -Xcompiler-option --compiler-backend=Optimizing ");
     if (Options.executeOnHost) {
@@ -34,6 +35,6 @@ public class X86OptimizingBackendExecutor extends Executor {
     }
     commandBuilder.append("-cp ").append(testLocation).append("/").append(programName).append(" ");
     commandBuilder.append(executeClass);
-    executionResult = executeCommandWithTimeout(commandBuilder.toString(), true);
+    return commandBuilder.toString();
   }
 }
diff --git a/tools/dexfuzz/src/dexfuzz/executors/X86QuickBackendExecutor.java b/tools/dexfuzz/src/dexfuzz/executors/X86QuickBackendExecutor.java
index 7e4a2f6976..9e8039d67a 100644
--- a/tools/dexfuzz/src/dexfuzz/executors/X86QuickBackendExecutor.java
+++ b/tools/dexfuzz/src/dexfuzz/executors/X86QuickBackendExecutor.java
@@ -22,11 +22,12 @@ import dexfuzz.listeners.BaseListener;
 public class X86QuickBackendExecutor extends Executor {
 
   public X86QuickBackendExecutor(BaseListener listener, Device device) {
-    super("x86 Quick Backend", 5, listener, Architecture.X86, device, true);
+    super("x86 Quick Backend", 5, listener, Architecture.X86, device,
+        /*needsCleanCodeCache*/ true, /*isBisectable*/ false);
   }
 
   @Override
-  public void execute(String programName) {
+  protected String constructCommand(String programName) {
     StringBuilder commandBuilder = new StringBuilder();
     commandBuilder.append("dalvikvm32 -Xcompiler-option --compiler-backend=Quick ");
     if (Options.executeOnHost) {
@@ -34,6 +35,6 @@ public class X86QuickBackendExecutor extends Executor {
     }
     commandBuilder.append("-cp ").append(testLocation).append("/").append(programName).append(" ");
     commandBuilder.append(executeClass);
-    executionResult = executeCommandWithTimeout(commandBuilder.toString(), true);
+    return commandBuilder.toString();
   }
 }
diff --git a/tools/dexfuzz/src/dexfuzz/executors/X86_64InterpreterExecutor.java b/tools/dexfuzz/src/dexfuzz/executors/X86_64InterpreterExecutor.java
index dc55a41576..af00760dc1 100644
--- a/tools/dexfuzz/src/dexfuzz/executors/X86_64InterpreterExecutor.java
+++ b/tools/dexfuzz/src/dexfuzz/executors/X86_64InterpreterExecutor.java
@@ -21,15 +21,16 @@ import dexfuzz.listeners.BaseListener;
 public class X86_64InterpreterExecutor extends Executor {
 
   public X86_64InterpreterExecutor(BaseListener listener, Device device) {
-    super("x86_64 Interpreter", 30, listener, Architecture.X86_64, device, false);
+    super("x86_64 Interpreter", 30, listener, Architecture.X86_64, device,
+        /*needsCleanCodeCache*/ false, /*isBisectable*/ false);
   }
 
   @Override
-  public void execute(String programName) {
+  protected String constructCommand(String programName) {
     StringBuilder commandBuilder = new StringBuilder();
     commandBuilder.append("dalvikvm64 -Xint ");
     commandBuilder.append("-cp ").append(testLocation).append("/").append(programName).append(" ");
     commandBuilder.append(executeClass);
-    executionResult = executeCommandWithTimeout(commandBuilder.toString(), true);
+    return commandBuilder.toString();
   }
 }
diff --git a/tools/dexfuzz/src/dexfuzz/executors/X86_64OptimizingBackendExecutor.java b/tools/dexfuzz/src/dexfuzz/executors/X86_64OptimizingBackendExecutor.java
index 2a01c6c1b1..28ff1a506f 100644
--- a/tools/dexfuzz/src/dexfuzz/executors/X86_64OptimizingBackendExecutor.java
+++ b/tools/dexfuzz/src/dexfuzz/executors/X86_64OptimizingBackendExecutor.java
@@ -21,15 +21,16 @@ import dexfuzz.listeners.BaseListener;
 public class X86_64OptimizingBackendExecutor extends Executor {
 
   public X86_64OptimizingBackendExecutor(BaseListener listener, Device device) {
-    super("x86_64 Optimizing Backend", 5, listener, Architecture.X86_64, device, true);
+    super("x86_64 Optimizing Backend", 5, listener, Architecture.X86_64, device,
+        /*needsCleanCodeCache*/ true, /*isBisectable*/ true);
   }
 
   @Override
-  public void execute(String programName) {
+  protected String constructCommand(String programName) {
     StringBuilder commandBuilder = new StringBuilder();
     commandBuilder.append("dalvikvm64 -Xcompiler-option --compiler-backend=Optimizing ");
     commandBuilder.append("-cp ").append(testLocation).append("/").append(programName).append(" ");
     commandBuilder.append(executeClass);
-    executionResult = executeCommandWithTimeout(commandBuilder.toString(), true);
+    return commandBuilder.toString();
   }
 }
diff --git a/tools/dexfuzz/src/dexfuzz/executors/X86_64QuickBackendExecutor.java b/tools/dexfuzz/src/dexfuzz/executors/X86_64QuickBackendExecutor.java
index 995cba2ac8..22cafe2045 100644
--- a/tools/dexfuzz/src/dexfuzz/executors/X86_64QuickBackendExecutor.java
+++ b/tools/dexfuzz/src/dexfuzz/executors/X86_64QuickBackendExecutor.java
@@ -21,15 +21,16 @@ import dexfuzz.listeners.BaseListener;
 public class X86_64QuickBackendExecutor extends Executor {
 
   public X86_64QuickBackendExecutor(BaseListener listener, Device device) {
-    super("x86_64 Quick Backend", 5, listener, Architecture.X86_64, device, true);
+    super("x86_64 Quick Backend", 5, listener, Architecture.X86_64, device,
+        /*needsCleanCodeCache*/ true, /*isBisectable*/ false);
   }
 
   @Override
-  public void execute(String programName) {
+  protected String constructCommand(String programName) {
     StringBuilder commandBuilder = new StringBuilder();
     commandBuilder.append("dalvikvm64 -Xcompiler-option --compiler-backend=Quick ");
     commandBuilder.append("-cp ").append(testLocation).append("/").append(programName).append(" ");
     commandBuilder.append(executeClass);
-    executionResult = executeCommandWithTimeout(commandBuilder.toString(), true);
+    return commandBuilder.toString();
   }
 }
diff --git a/tools/dexfuzz/src/dexfuzz/listeners/BisectionSearchListener.java b/tools/dexfuzz/src/dexfuzz/listeners/BisectionSearchListener.java
new file mode 100644
index 0000000000..dfd9637519
--- /dev/null
+++ b/tools/dexfuzz/src/dexfuzz/listeners/BisectionSearchListener.java
@@ -0,0 +1,108 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package dexfuzz.listeners;
+
+import dexfuzz.ExecutionResult;
+import dexfuzz.executors.Executor;
+import dexfuzz.Log;
+
+import java.io.File;
+import java.io.IOException;
+import java.io.PrintWriter;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * Runs bisection search for divergent programs.
+ */
+public class BisectionSearchListener extends BaseListener {
+
+  /**
+   * Used to remember the seed used to fuzz the fuzzed file, so we can save it with this
+   * seed as a name, if we find a divergence.
+   */
+  private long currentSeed;
+
+  /**
+   * Used to remember the name of the file we've fuzzed, so we can save it if we
+   * find a divergence.
+   */
+  private String fuzzedFile;
+
+  @Override
+  public void handleSeed(long seed) {
+    currentSeed = seed;
+  }
+
+  @Override
+  public void handleSuccessfullyFuzzedFile(String programName) {
+    fuzzedFile = programName;
+  }
+
+  private void writeToFile(String file, String toWrite) throws IOException {
+    PrintWriter writer = new PrintWriter(file);
+    writer.write(toWrite);
+    writer.close();
+  }
+
+  private String extractExpectedOutput(ExecutionResult result) {
+    StringBuilder builder = new StringBuilder();
+    // Skip last, artificial output line with return code.
+    for (int i = 0; i < result.output.size() - 1; i++) {
+      builder.append(result.output.get(i)).append("\n");
+    }
+    return builder.toString();
+  }
+
+  @Override
+  public void handleDivergences(Map<String, List<Executor>> outputMap) {
+    if (outputMap.size() != 2) {
+      // It's unclear which output should be considered reference output.
+      return;
+    }
+    try {
+      File expected_output_file = File.createTempFile("expected_output", ".txt");
+      String outputFile = String.format("bisection_outputs/%d_out.txt", currentSeed);
+      String logFile = String.format("bisection_outputs/%d_log.txt", currentSeed);
+      List<List<Executor>> executorsGroupedByOutput =
+          new ArrayList<List<Executor>>(outputMap.values());
+      List<String> outputs = new ArrayList<String>();
+      for (List<Executor> executors : executorsGroupedByOutput) {
+        outputs.add(extractExpectedOutput(executors.get(0).getResult()));
+      }
+      for (int i = 0; i < 2; i++) {
+        String output = outputs.get(i);
+        String otherOutput = outputs.get(1 - i);
+        List<Executor> executors = executorsGroupedByOutput.get(i);
+        for (Executor executor : executors) {
+          if (executor.isBisectable()) {
+            writeToFile(expected_output_file.getAbsolutePath(), otherOutput);
+            ExecutionResult result = executor.runBisectionSearch(fuzzedFile,
+                expected_output_file.getAbsolutePath(), logFile);
+            writeToFile(outputFile, result.getFlattenedAllWithNewlines());
+          }
+        }
+      }
+      expected_output_file.delete();
+    } catch (IOException e) {
+      Log.error(
+          "BisectionSearchListener.handleDivergences() caught an IOException " + e.toString());
+    }
+  }
+
+}