Home | History | Annotate | Download | only in mutators 
      1 /*
      2  * Copyright (C) 2014 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 package dexfuzz.program.mutators;
     18 
     19 import dexfuzz.Log;
     20 import dexfuzz.MutationStats;
     21 import dexfuzz.program.MBranchInsn;
     22 import dexfuzz.program.MInsn;
     23 import dexfuzz.program.MutatableCode;
     24 import dexfuzz.program.Mutation;
     25 import dexfuzz.rawdex.Instruction;
     26 import dexfuzz.rawdex.Opcode;
     27 import dexfuzz.rawdex.OpcodeInfo;
     28 import dexfuzz.rawdex.formats.AbstractFormat;
     29 import dexfuzz.rawdex.formats.ContainsConst;
     30 import dexfuzz.rawdex.formats.ContainsPoolIndex;
     31 import dexfuzz.rawdex.formats.ContainsPoolIndex.PoolIndexKind;
     32 import dexfuzz.rawdex.formats.ContainsVRegs;
     33 
     34 import java.util.List;
     35 import java.util.Random;
     36 
     37 public class RandomInstructionGenerator extends CodeMutator {
     38   /**
     39    * Every CodeMutator has an AssociatedMutation, representing the
     40    * mutation that this CodeMutator can perform, to allow separate
     41    * generateMutation() and applyMutation() phases, allowing serialization.
     42    */
     43   public static class AssociatedMutation extends Mutation {
     44     public int insertionIdx;
     45     public int newOpcode;
     46     public boolean hasConst;
     47     public long constValue;
     48     public boolean hasPoolIndex;
     49     public int poolIndexValue;
     50     public boolean hasVregs;
     51     public int vregCount;
     52     public int vregA;
     53     public int vregB;
     54     public int vregC;
     55     public int branchTargetIdx;
     56 
     57     @Override
     58     public String getString() {
     59       String result = String.format("%d %d %s %d %s %d %s %d %d %d %d %d",
     60           insertionIdx,
     61           newOpcode,
     62           (hasConst ? "T" : "F"),
     63           constValue,
     64           (hasPoolIndex ? "T" : "F"),
     65           poolIndexValue,
     66           (hasVregs ? "T" : "F"),
     67           vregCount,
     68           vregA,
     69           vregB,
     70           vregC,
     71           branchTargetIdx
     72           );
     73       return result;
     74     }
     75 
     76     @Override
     77     public void parseString(String[] elements) {
     78       insertionIdx = Integer.parseInt(elements[2]);
     79       newOpcode = Integer.parseInt(elements[3]);
     80       hasConst = (elements[4].equals("T"));
     81       constValue = Long.parseLong(elements[5]);
     82       hasPoolIndex = (elements[6].equals("T"));
     83       poolIndexValue = Integer.parseInt(elements[7]);
     84       hasVregs = (elements[8].equals("T"));
     85       vregCount = Integer.parseInt(elements[9]);
     86       vregA = Integer.parseInt(elements[10]);
     87       vregB = Integer.parseInt(elements[11]);
     88       vregC = Integer.parseInt(elements[12]);
     89       branchTargetIdx = Integer.parseInt(elements[13]);
     90     }
     91   }
     92 
     93   // The following two methods are here for the benefit of MutationSerializer,
     94   // so it can create a CodeMutator and get the correct associated Mutation, as it
     95   // reads in mutations from a dump of mutations.
     96   @Override
     97   public Mutation getNewMutation() {
     98     return new AssociatedMutation();
     99   }
    100 
    101   public RandomInstructionGenerator() { }
    102 
    103   public RandomInstructionGenerator(Random rng, MutationStats stats, List<Mutation> mutations) {
    104     super(rng, stats, mutations);
    105     likelihood = 30;
    106   }
    107 
    108   @Override
    109   protected Mutation generateMutation(MutatableCode mutatableCode) {
    110     // Find the insertion point.
    111     int insertionIdx = 0;
    112     boolean foundInsn = false;
    113 
    114     while (!foundInsn) {
    115       insertionIdx = rng.nextInt(mutatableCode.getInstructionCount());
    116       MInsn insertionPoint =
    117           mutatableCode.getInstructionAt(insertionIdx);
    118       foundInsn = true;
    119 
    120       // Don't want to insert instructions where there are raw instructions for now.
    121       if (insertionPoint.insn.justRaw) {
    122         foundInsn = false;
    123       }
    124     }
    125 
    126     Opcode newOpcode = null;
    127     int opcodeCount = Opcode.values().length;
    128     boolean foundOpcode = false;
    129 
    130     while (!foundOpcode) {
    131       newOpcode = Opcode.values()[rng.nextInt(opcodeCount)];
    132       foundOpcode = true;
    133       if (Opcode.isBetween(newOpcode, Opcode.FILLED_NEW_ARRAY, Opcode.FILL_ARRAY_DATA)
    134           || Opcode.isBetween(newOpcode, Opcode.PACKED_SWITCH, Opcode.SPARSE_SWITCH)
    135           || Opcode.isBetween(newOpcode, Opcode.INVOKE_VIRTUAL, Opcode.INVOKE_INTERFACE)
    136           || Opcode.isBetween(newOpcode,
    137               Opcode.INVOKE_VIRTUAL_RANGE, Opcode.INVOKE_INTERFACE_RANGE)
    138               // Can never accept these instructions at compile time.
    139               || Opcode.isBetween(newOpcode, Opcode.IGET_QUICK, Opcode.IPUT_SHORT_QUICK)
    140               // Unused opcodes...
    141               || Opcode.isBetween(newOpcode, Opcode.UNUSED_3E, Opcode.UNUSED_43)
    142               || Opcode.isBetween(newOpcode, Opcode.UNUSED_79, Opcode.UNUSED_7A)
    143               || Opcode.isBetween(newOpcode, Opcode.UNUSED_EF, Opcode.UNUSED_FF)) {
    144         foundOpcode = false;
    145       }
    146     }
    147 
    148     OpcodeInfo newOpcodeInfo = Instruction.getOpcodeInfo(newOpcode);
    149 
    150     AssociatedMutation mutation = new AssociatedMutation();
    151     mutation.setup(this.getClass(), mutatableCode);
    152     mutation.insertionIdx = insertionIdx;
    153     mutation.newOpcode = newOpcodeInfo.value;
    154 
    155     AbstractFormat fmt = newOpcodeInfo.format;
    156 
    157     if (fmt instanceof ContainsConst) {
    158       mutation.hasConst = true;
    159       mutation.constValue = rng.nextLong() % ((ContainsConst)fmt).getConstRange();
    160     }
    161     if (fmt instanceof ContainsPoolIndex) {
    162       mutation.hasPoolIndex = true;
    163       ContainsPoolIndex containsPoolIndex = (ContainsPoolIndex) fmt;
    164       PoolIndexKind poolIndexKind = containsPoolIndex.getPoolIndexKind(newOpcodeInfo);
    165       int maxPoolIndex = mutatableCode.program.getTotalPoolIndicesByKind(poolIndexKind);
    166       if (maxPoolIndex > 0) {
    167         mutation.poolIndexValue = rng.nextInt(maxPoolIndex);
    168       } else {
    169         mutation.poolIndexValue = 0;
    170       }
    171     }
    172     if (mutatableCode.registersSize == 0) {
    173       mutatableCode.registersSize = 1;
    174     }
    175     if (fmt instanceof ContainsVRegs) {
    176       mutation.hasVregs = true;
    177       ContainsVRegs containsVregs = (ContainsVRegs) fmt;
    178       mutation.vregCount = containsVregs.getVRegCount();
    179       switch (mutation.vregCount) {
    180         case 3:
    181           mutation.vregC = rng.nextInt(mutatableCode.registersSize);
    182           // fallthrough
    183         case 2:
    184           mutation.vregB = rng.nextInt(mutatableCode.registersSize);
    185           // fallthrough
    186         case 1:
    187           mutation.vregA = rng.nextInt(mutatableCode.registersSize);
    188           break;
    189         default:
    190           Log.errorAndQuit("Invalid number of vregs specified.");
    191       }
    192     }
    193     // If we have some kind of branch, pick a random target.
    194     if (Opcode.isBetween(newOpcode, Opcode.IF_EQ, Opcode.IF_LEZ)
    195         || Opcode.isBetween(newOpcode, Opcode.GOTO, Opcode.GOTO_32)) {
    196       mutation.branchTargetIdx = rng.nextInt(mutatableCode.getInstructionCount());
    197     }
    198 
    199     return mutation;
    200   }
    201 
    202   @Override
    203   protected void applyMutation(Mutation uncastMutation) {
    204     // Cast the Mutation to our AssociatedMutation, so we can access its fields.
    205     AssociatedMutation mutation = (AssociatedMutation) uncastMutation;
    206     MutatableCode mutatableCode = mutation.mutatableCode;
    207 
    208     Opcode newOpcode = Instruction.getOpcodeInfo(mutation.newOpcode).opcode;
    209 
    210     boolean isBranch = false;
    211     if (Opcode.isBetween(newOpcode, Opcode.IF_EQ, Opcode.IF_LEZ)
    212         || Opcode.isBetween(newOpcode, Opcode.GOTO, Opcode.GOTO_32)) {
    213       isBranch = true;
    214     }
    215 
    216     MInsn newInsn = null;
    217     if (!isBranch) {
    218       newInsn = new MInsn();
    219     } else {
    220       newInsn = new MBranchInsn();
    221     }
    222     newInsn.insn = new Instruction();
    223     newInsn.insn.info = Instruction.getOpcodeInfo(mutation.newOpcode);
    224     AbstractFormat fmt = newInsn.insn.info.format;
    225 
    226     if (mutation.hasConst) {
    227       ContainsConst containsConst = (ContainsConst) fmt;
    228       containsConst.setConst(newInsn.insn, mutation.constValue);
    229     }
    230     if (mutation.hasPoolIndex) {
    231       ContainsPoolIndex containsPoolIndex = (ContainsPoolIndex) fmt;
    232       containsPoolIndex.setPoolIndex(newInsn.insn, mutation.poolIndexValue);
    233     }
    234     if (mutation.hasVregs) {
    235       switch (mutation.vregCount) {
    236         case 3:
    237           newInsn.insn.vregC = mutation.vregC;
    238           // fallthrough
    239         case 2:
    240           newInsn.insn.vregB = mutation.vregB;
    241           // fallthrough
    242         case 1:
    243           newInsn.insn.vregA = mutation.vregA;
    244           break;
    245         default:
    246           Log.errorAndQuit("Invalid number of vregs specified.");
    247       }
    248     }
    249 
    250     if (isBranch) {
    251       // We have a branch instruction, point it at its target.
    252       MBranchInsn newBranchInsn = (MBranchInsn) newInsn;
    253       newBranchInsn.target = mutatableCode.getInstructionAt(mutation.branchTargetIdx);
    254     }
    255 
    256     MInsn insertionPoint =
    257         mutatableCode.getInstructionAt(mutation.insertionIdx);
    258 
    259     Log.info("Generated random instruction: " + newInsn
    260         + ", inserting at " + insertionPoint);
    261 
    262     stats.incrementStat("Generated random instruction");
    263 
    264     mutatableCode.insertInstructionAt(newInsn, mutation.insertionIdx);
    265 
    266     // If we've generated a monitor insn, generate the matching opposing insn.
    267     if (newInsn.insn.info.opcode == Opcode.MONITOR_ENTER) {
    268       MInsn exitInsn = newInsn.clone();
    269       exitInsn.insn.info = Instruction.getOpcodeInfo(Opcode.MONITOR_EXIT);
    270       mutatableCode.insertInstructionAfter(exitInsn, mutation.insertionIdx);
    271       Log.info("Generated matching monitor-exit: " + exitInsn);
    272     } else if (newInsn.insn.info.opcode == Opcode.MONITOR_EXIT) {
    273       MInsn enterInsn = newInsn.clone();
    274       enterInsn.insn.info = Instruction.getOpcodeInfo(Opcode.MONITOR_ENTER);
    275       mutatableCode.insertInstructionAt(enterInsn, mutation.insertionIdx);
    276       Log.info("Generated matching monitor-enter: " + enterInsn);
    277     }
    278   }
    279 }
    280