dexfuzz/fuzzers/Fuzzer.java

/*
 * Copyright (C) 2014 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.fuzzers;

import dexfuzz.Log;
import dexfuzz.Options;
import dexfuzz.Timer;
import dexfuzz.executors.Architecture;
import dexfuzz.executors.Arm64InterpreterExecutor;
import dexfuzz.executors.Arm64OptimizingBackendExecutor;
import dexfuzz.executors.Arm64QuickBackendExecutor;
import dexfuzz.executors.ArmInterpreterExecutor;
import dexfuzz.executors.ArmOptimizingBackendExecutor;
import dexfuzz.executors.ArmQuickBackendExecutor;
import dexfuzz.executors.Device;
import dexfuzz.executors.Executor;
import dexfuzz.executors.Mips64InterpreterExecutor;
import dexfuzz.executors.Mips64OptimizingBackendExecutor;
import dexfuzz.executors.Mips64QuickBackendExecutor;
import dexfuzz.executors.MipsInterpreterExecutor;
import dexfuzz.executors.MipsOptimizingBackendExecutor;
import dexfuzz.executors.MipsQuickBackendExecutor;
import dexfuzz.executors.X86InterpreterExecutor;
import dexfuzz.executors.X86OptimizingBackendExecutor;
import dexfuzz.executors.X86QuickBackendExecutor;
import dexfuzz.executors.X86_64InterpreterExecutor;
import dexfuzz.executors.X86_64OptimizingBackendExecutor;
import dexfuzz.executors.X86_64QuickBackendExecutor;
import dexfuzz.listeners.BaseListener;
import dexfuzz.program.Mutation;
import dexfuzz.program.Program;
import dexfuzz.rawdex.DexRandomAccessFile;
import dexfuzz.rawdex.OffsetTracker;
import dexfuzz.rawdex.RawDexFile;

import java.io.FileNotFoundException;
import java.io.IOException;
import java.lang.reflect.Constructor;
import java.lang.reflect.InvocationTargetException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * A particular fuzzing strategy, this class provides the common methods
 * most fuzzing will involve, and subclasses override the run() method, to
 * employ a particular strategy.
 */
public abstract class Fuzzer {
  private List<Executor> executors;
  private OffsetTracker offsetTracker;

  /**
   * This is the executor that we use to test for self-divergent programs.
   */
  private Executor goldenExecutor;

  /*
   * These two flags are set during fuzz(), and then cleared at the end of execute().
   */
  private boolean mutatedSuccessfully;
  private boolean savedSuccessfully;

  private Timer totalTimer = new Timer("Total Time");
  private Timer timerDexInput = new Timer("DEX Input");
  private Timer timerProgGen = new Timer("Program Generation");
  private Timer timerMutation = new Timer("Mutation Time");
  private Timer timerDexOutput = new Timer("DEX Output");
  private Timer timerChecksumCalc = new Timer("Checksum Calculation");

  protected BaseListener listener;

  protected Fuzzer(BaseListener listener) {
    totalTimer.start();
    executors = new ArrayList<Executor>();
    this.listener = listener;
  }

  public abstract void run();

  protected abstract String getNextInputFilename();

  protected abstract String getNextOutputFilename();

  /**
   * Call this after fuzzer execution to print out timing results.
   */
  public void printTimingInfo() {
    totalTimer.stop();
    timerDexInput.printTime(listener);
    timerProgGen.printTime(listener);
    timerMutation.printTime(listener);
    timerDexOutput.printTime(listener);
    timerChecksumCalc.printTime(listener);
    totalTimer.printTime(listener);
  }

  /**
   * Make sure this is called to correctly shutdown each Executor's StreamConsumers.
   */
  public void shutdown() {
    if (executors != null) {
      for (Executor executor : executors) {
        executor.shutdown();
      }
    }
  }

  private void addExecutorsForArchitecture(Device device, Class<? extends Executor> quick,
      Class<? extends Executor> optimizing, Class<? extends Executor> interpreter) {
    // NB: Currently QuickBackend MUST come immediately before same arch's Interpreter.
    // This is because intepreter execution relies on there being an OAT file already
    // created to produce correct debug information. Otherwise we will see
    // false-positive divergences.
    try {
      if (Options.useQuick) {
        Constructor<? extends Executor> constructor =
            quick.getConstructor(BaseListener.class, Device.class);
        executors.add(constructor.newInstance(listener, device));
      }
      if (Options.useOptimizing) {
        Constructor<? extends Executor> constructor =
            optimizing.getConstructor(BaseListener.class, Device.class);
        executors.add(constructor.newInstance(listener, device));
      }
      if (Options.useInterpreter) {
        Constructor<? extends Executor> constructor =
            interpreter.getConstructor(BaseListener.class, Device.class);
        executors.add(constructor.newInstance(listener, device));
      }
    } catch (NoSuchMethodException e) {
      Log.errorAndQuit("Executor doesn't have correct constructor.");
    } catch (InstantiationException e) {
      Log.errorAndQuit("Executor couldn't be instantiated.");
    } catch (IllegalAccessException e) {
      Log.errorAndQuit("Executor couldn't be accessed.");
    } catch (IllegalArgumentException e) {
      Log.errorAndQuit("Invalid arguments to instantiation of Executor.");
    } catch (InvocationTargetException e) {
      Log.errorAndQuit("Instantiation of Executor threw an Exception!");
    }
  }

  protected void addExecutors() {
    Device device = null;
    if (Options.executeOnHost) {
      device = new Device();
    } else {
      device = new Device(Options.deviceName, Options.noBootImage);
    }

    if (Options.useArchArm64) {
      addExecutorsForArchitecture(device, Arm64QuickBackendExecutor.class,
          Arm64OptimizingBackendExecutor.class, Arm64InterpreterExecutor.class);
    }

    if (Options.useArchArm) {
      addExecutorsForArchitecture(device, ArmQuickBackendExecutor.class,
          ArmOptimizingBackendExecutor.class, ArmInterpreterExecutor.class);
    }

    if (Options.useArchX86_64) {
      addExecutorsForArchitecture(device, X86_64QuickBackendExecutor.class,
          X86_64OptimizingBackendExecutor.class, X86_64InterpreterExecutor.class);
    }

    if (Options.useArchX86) {
      addExecutorsForArchitecture(device, X86QuickBackendExecutor.class,
          X86OptimizingBackendExecutor.class, X86InterpreterExecutor.class);
    }

    if (Options.useArchMips64) {
      addExecutorsForArchitecture(device, Mips64QuickBackendExecutor.class,
          Mips64OptimizingBackendExecutor.class, Mips64InterpreterExecutor.class);
    }

    if (Options.useArchMips) {
      addExecutorsForArchitecture(device, MipsQuickBackendExecutor.class,
          MipsOptimizingBackendExecutor.class, MipsInterpreterExecutor.class);
    }

    // Add the first backend as the golden executor for self-divergence tests.
    goldenExecutor = executors.get(0);
  }

  /**
   * Called from each Fuzzer subclass that we can instantiate. Parses the program, fuzzes it,
   * and then saves it, if mutation was successful. We can use --skip-mutation to bypass
   * the mutation phase, if we wanted to verify that a test program itself works.
   */
  protected Program fuzz() {
    String inputFile = getNextInputFilename();
    Program program = loadProgram(inputFile, null);
    if (program == null) {
      Log.errorAndQuit("Problem loading seed file.");
    }
    // Mutate the program.
    if (!Options.skipMutation) {
      timerMutation.start();
      program.mutateTheProgram();

      mutatedSuccessfully = program.updateRawDexFile();
      timerMutation.stop();
      if (!mutatedSuccessfully) {
        listener.handleMutationFail();
      }
    } else {
      Log.info("Skipping mutation stage as requested.");
      mutatedSuccessfully = true;
    }
    if (mutatedSuccessfully) {
      savedSuccessfully = saveProgram(program, getNextOutputFilename());
    }
    return program;
  }

  protected boolean safeToExecute() {
    return mutatedSuccessfully && savedSuccessfully;
  }

  protected void execute(Program program) {
    if (!safeToExecute()) {
      Log.errorAndQuit("Your Fuzzer subclass called execute() "
          + "without checking safeToExecute()!");
    }

    String programName = getNextOutputFilename();
    boolean verified = true;

    if (!Options.skipHostVerify && !Options.executeOnHost) {
      verified = goldenExecutor.verifyOnHost(programName);
      if (verified) {
        listener.handleSuccessfulHostVerification();
      }
    }

    if (verified) {
      boolean skipAnalysis = false;

      for (Executor executor : executors) {
        executor.reset();
        executor.prepareProgramForExecution(programName);
        executor.execute(programName);
        if (!executor.didTargetVerify()) {
          listener.handleFailedTargetVerification();
          skipAnalysis = true;
          break;
        }
        // Results are saved in the executors until they reset, usually at the
        // next iteration.
      }

      if (!skipAnalysis) {
        listener.handleSuccessfullyFuzzedFile(programName);
        analyseResults(program, programName);
      }
    }

    goldenExecutor.finishedWithProgramOnDevice();
    mutatedSuccessfully = false;
    savedSuccessfully = false;
  }

  /**
   * Checks if the different outputs we observed align with different architectures.
   */
  private boolean checkForArchitectureSplit(Map<String, List<Executor>> outputMap) {
    if (outputMap.size() != 2) {
      // Cannot have a two-way split if we don't have 2 kinds of output.
      return false;
    }

    Architecture[] architectures = new Architecture[2];
    int archIdx = 0;

    // For each kind of output we saw, make sure they all
    // came from the same architecture.
    for (List<Executor> executorList : outputMap.values()) {
      architectures[archIdx] = executorList.get(0).getArchitecture();
      for (int execIdx = 1; execIdx < executorList.size(); execIdx++) {
        if (executorList.get(execIdx).getArchitecture() != architectures[archIdx]) {
          // Not every executor with this output shared the same architecture.
          return false;
        }
      }
      archIdx++;
    }

    // Now make sure that the two outputs we saw were different architectures.
    if (architectures[0] == architectures[1]) {
      return false;
    }
    return true;
  }

  private boolean checkGoldenExecutorForSelfDivergence(String programName) {
    // Run golden executor 5 times, make sure it always produces
    // the same output, otherwise report that it is self-divergent.

    // TODO: Instead, produce a list of acceptable outputs, and see if the divergent
    // outputs of the backends fall within this set of outputs.
    String seenOutput = null;
    for (int i = 0; i < 5; i++) {
      goldenExecutor.reset();
      goldenExecutor.execute(programName);
      String output = goldenExecutor.getResult().getFlattenedOutput();
      if (seenOutput == null) {
        seenOutput = output;
      } else if (!seenOutput.equals(output)) {
        return true;
      }
    }
    return false;
  }

  private void analyseResults(Program program, String programName) {
    // Check timeouts.
    // Construct two lists of executors, those who timed out, and those who did not.
    // Report if we had some timeouts.
    List<Executor> timedOut = new ArrayList<Executor>();
    List<Executor> didNotTimeOut = new ArrayList<Executor>();
    for (Executor executor : executors) {
      if (executor.getResult().isTimeout()) {
        timedOut.add(executor);
      } else {
        didNotTimeOut.add(executor);
      }
    }
    if (!timedOut.isEmpty()) {
      listener.handleTimeouts(timedOut, didNotTimeOut);
      // Do not bother reporting divergence information.
      return;
    }

    // Check divergences.
    // Construct a map {output1: [executor that produced output1, ...], output2: [...]}
    // If the map has more than one output, we had divergence, report it.
    Map<String, List<Executor>> outputMap = new HashMap<String, List<Executor>>();
    for (Executor executor : executors) {
      String output = executor.getResult().getFlattenedOutput();
      if (Options.dumpOutput) {
        listener.handleDumpOutput(
            executor.getResult().getFlattenedOutputWithNewlines(), executor);
      }
      if (outputMap.containsKey(output)) {
        outputMap.get(output).add(executor);
      } else {
        List<Executor> newList = new ArrayList<Executor>();
        newList.add(executor);
        outputMap.put(output, newList);
      }
    }

    if (outputMap.size() > 1) {
      // Report that we had divergence.
      listener.handleDivergences(outputMap);
      listener.handleMutations(program.getMutations());
      // If we found divergences, try running the "golden executor"
      // a few times in succession, to see if the output it produces is different
      // from run to run. If so, then we're probably executing something with either:
      //  a) randomness
      //  b) timing-dependent code
      //  c) threads
      // So we will not consider it a "true" divergence, but still useful?
      if (checkGoldenExecutorForSelfDivergence(programName)) {
        listener.handleSelfDivergence();
        return;
      }
      // If we found divergences, try checking if the differences
      // in outputs align with differences in architectures.
      // For example, if we have: {Output1: [ARM, ARM], Output2: [ARM64, ARM64]}
      if (checkForArchitectureSplit(outputMap)) {
        listener.handleArchitectureSplit();
      }
    } else {
      // No problems with execution.
      listener.handleSuccess(outputMap);
    }
  }

  private Program loadProgram(String inputName, List<Mutation> mutations) {
    Program program = null;
    try {
      DexRandomAccessFile input = new DexRandomAccessFile(inputName, "r");
      offsetTracker = new OffsetTracker();
      input.setOffsetTracker(offsetTracker);
      // Read the raw DexFile
      RawDexFile rawDexFile = new RawDexFile();
      timerDexInput.start();
      rawDexFile.read(input);
      timerDexInput.stop();
      input.close();
      // Create the program view.
      timerProgGen.start();
      program = new Program(rawDexFile, mutations, listener);
      timerProgGen.stop();
    } catch (FileNotFoundException e) {
      Log.errorAndQuit("Couldn't open a file called " + inputName);
    } catch (IOException e) {
      Log.errorAndQuit("IOException when trying to load a DEX test file!");
    }
    return program;
  }

  private boolean saveProgram(Program program, String outputName) {
    boolean success = false;

    try {
      // Write out the results of mutation.
      DexRandomAccessFile output = new DexRandomAccessFile(outputName, "rw");
      output.setOffsetTracker(offsetTracker);
      // Delete the contents of the file, in case it already existed.
      output.setLength(0);
      // Write out the file.
      timerDexOutput.start();
      program.writeRawDexFile(output);
      timerDexOutput.stop();
      // Recalculate the header info.
      timerChecksumCalc.start();
      program.updateRawDexFileHeader(output);
      timerChecksumCalc.stop();
      output.close();
      success = true;
    } catch (FileNotFoundException e) {
      Log.errorAndQuit("Couldn't open a file called " + outputName);
    } catch (IOException e) {
      Log.errorAndQuit("IOException when trying to save a DEX test file!");
    }
    return success;
  }
}