1    :  // Copyright 2013 Google Inc. All Rights Reserved.
   2    :  //
   3    :  // Licensed under the Apache License, Version 2.0 (the "License");
   4    :  // you may not use this file except in compliance with the License.
   5    :  // You may obtain a copy of the License at
   6    :  //
   7    :  //     http://www.apache.org/licenses/LICENSE-2.0
   8    :  //
   9    :  // Unless required by applicable law or agreed to in writing, software
  10    :  // distributed under the License is distributed on an "AS IS" BASIS,
  11    :  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12    :  // See the License for the specific language governing permissions and
  13    :  // limitations under the License.
  14    :  
  15    :  #include "syzygy/block_graph/transforms/fuzzing_transform.h"
  16    :  
  17    :  #include "base/logging.h"
  18    :  #include "base/strings/string_util.h"
  19    :  #include "base/strings/stringprintf.h"
  20    :  #include "syzygy/block_graph/basic_block_assembler.h"
  21    :  #include "syzygy/block_graph/block_builder.h"
  22    :  #include "syzygy/block_graph/block_util.h"
  23    :  #include "syzygy/block_graph/analysis/liveness_analysis.h"
  24    :  #include "syzygy/common/defs.h"
  25    :  
  26    :  namespace block_graph {
  27    :  namespace transforms {
  28    :  namespace {
  29    :  
  30    :  using block_graph::BasicBlock;
  31    :  using block_graph::BasicBlockAssembler;
  32    :  using block_graph::BasicCodeBlock;
  33    :  using block_graph::Instruction;
  34    :  using block_graph::Immediate;
  35    :  
  36    :  }  // namespace
  37    :  
  38    :  const char LivenessFuzzingBasicBlockTransform::kTransformName[]
  39    :      = "LivenessFuzzingBasicBlockTransform";
  40    :  const char FuzzingTransform::kTransformName[] = "FuzzingTransform";
  41    :  
  42    :  bool LivenessFuzzingBasicBlockTransform::TransformBasicBlockSubGraph(
  43    :      const TransformPolicyInterface* policy,
  44    :      BlockGraph* block_graph,
  45  E :      BasicBlockSubGraph* subgraph) {
  46  E :    DCHECK(policy != NULL);
  47  E :    DCHECK(block_graph != NULL);
  48  E :    DCHECK(subgraph != NULL);
  49    :  
  50    :    // Perform the global liveness analysis.
  51  E :    block_graph::analysis::LivenessAnalysis liveness;
  52  E :    liveness.Analyze(subgraph);
  53    :  
  54    :    // Iterate through each basic block and instrument it.
  55    :    BasicBlockSubGraph::BBCollection::iterator bb_iter =
  56  E :        subgraph->basic_blocks().begin();
  57  E :    for (; bb_iter != subgraph->basic_blocks().end(); ++bb_iter) {
  58  E :      BasicCodeBlock* bb = BasicCodeBlock::Cast(*bb_iter);
  59  E :      if (bb == NULL)
  60  E :        continue;
  61    :  
  62  E :      block_graph::analysis::LivenessAnalysis::State state;
  63  E :      liveness.GetStateAtExitOf(bb, &state);
  64    :  
  65  E :      BasicBlock::Instructions& instructions = bb->instructions();
  66    :  
  67  E :      if (instructions.empty())
  68  E :        continue;
  69    :  
  70  E :      BasicBlock::Instructions::iterator instr_iter = instructions.end();
  71  E :      --instr_iter;
  72    :  
  73  E :      while (true) {
  74    :        // Propagate liveness through the current instruction.
  75  E :        Instruction instr = *instr_iter;
  76  E :        liveness.PropagateBackward(instr, &state);
  77    :  
  78    :        // Rewrite dead registers.
  79  E :        for (size_t i = 0; i < assm::kRegister32Count; ++i) {
  80  E :          const assm::Register32& reg = assm::kRegisters32[i];
  81  E :          if (state.IsLive(reg))
  82  E :            continue;
  83    :  
  84  E :          BasicBlockAssembler assembly(instr_iter, &instructions);
  85    :  
  86    :          // Write some garbage in the dead register.
  87  E :          assembly.mov(reg, Immediate(0xCCCCCCCC));
  88  E :          --instr_iter;
  89  E :        }
  90    :  
  91  E :        if (!state.AreArithmeticFlagsLive()) {
  92    :          // Write some garbage to the flags register when they are not alive.
  93  E :          BasicBlockAssembler assembly(instr_iter, &instructions);
  94  E :          assembly.add(assm::ebp, Immediate(0, assm::kSize32Bit));
  95  E :          --instr_iter;
  96    :        }
  97    :  
  98    :        // Move to the previous instruction.
  99  E :        if (instr_iter == instructions.begin())
 100  E :          break;
 101  E :        --instr_iter;
 102  E :      }
 103  E :    }
 104    :  
 105  E :    return true;
 106  E :  }
 107    :  
 108  E :  FuzzingTransform::FuzzingTransform() {
 109  E :  }
 110    :  
 111    :  bool FuzzingTransform::OnBlock(
 112    :      const TransformPolicyInterface* policy,
 113    :      BlockGraph* block_graph,
 114  E :      BlockGraph::Block* block) {
 115  E :    DCHECK(policy != NULL);
 116  E :    DCHECK(block_graph != NULL);
 117  E :    DCHECK(block != NULL);
 118    :  
 119    :    // Use the policy to skip blocks that aren't eligible for basic block
 120    :    // decomposition.
 121  E :    if (!policy->BlockIsSafeToBasicBlockDecompose(block))
 122  E :      return true;
 123    :  
 124    :    // Apply a basic block transform.
 125  E :    LivenessFuzzingBasicBlockTransform liveness_transform;
 126    :    if (!ApplyBasicBlockSubGraphTransform(
 127  E :            &liveness_transform, policy, block_graph, block, NULL)) {
 128  i :      return false;
 129    :    }
 130    :  
 131  E :    return true;
 132  E :  }
 133    :  
 134    :  }  // namespace transforms
 135    :  }  // namespace block_graph