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 getString()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 parseString(String[] elements)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 getNewMutation()97 public Mutation getNewMutation() { 98 return new AssociatedMutation(); 99 } 100 RandomInstructionGenerator()101 public RandomInstructionGenerator() { } 102 RandomInstructionGenerator(Random rng, MutationStats stats, List<Mutation> mutations)103 public RandomInstructionGenerator(Random rng, MutationStats stats, List<Mutation> mutations) { 104 super(rng, stats, mutations); 105 likelihood = 30; 106 } 107 108 @Override generateMutation(MutatableCode mutatableCode)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 applyMutation(Mutation uncastMutation)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