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.MInsn; 22 import dexfuzz.program.MutatableCode; 23 import dexfuzz.program.Mutation; 24 25 import java.util.List; 26 import java.util.Random; 27 28 public class InstructionSwapper extends CodeMutator { 29 /** 30 * Every CodeMutator has an AssociatedMutation, representing the 31 * mutation that this CodeMutator can perform, to allow separate 32 * generateMutation() and applyMutation() phases, allowing serialization. 33 */ 34 public static class AssociatedMutation extends Mutation { 35 public int swapInsnIdx; 36 public int swapWithInsnIdx; 37 38 @Override getString()39 public String getString() { 40 StringBuilder builder = new StringBuilder(); 41 builder.append(swapInsnIdx).append(" "); 42 builder.append(swapWithInsnIdx); 43 return builder.toString(); 44 } 45 46 @Override parseString(String[] elements)47 public void parseString(String[] elements) { 48 swapInsnIdx = Integer.parseInt(elements[2]); 49 swapWithInsnIdx = Integer.parseInt(elements[3]); 50 } 51 } 52 53 // The following two methods are here for the benefit of MutationSerializer, 54 // so it can create a CodeMutator and get the correct associated Mutation, as it 55 // reads in mutations from a dump of mutations. 56 @Override getNewMutation()57 public Mutation getNewMutation() { 58 return new AssociatedMutation(); 59 } 60 InstructionSwapper()61 public InstructionSwapper() { } 62 InstructionSwapper(Random rng, MutationStats stats, List<Mutation> mutations)63 public InstructionSwapper(Random rng, MutationStats stats, List<Mutation> mutations) { 64 super(rng, stats, mutations); 65 likelihood = 80; 66 } 67 68 @Override canMutate(MutatableCode mutatableCode)69 protected boolean canMutate(MutatableCode mutatableCode) { 70 if (mutatableCode.getInstructionCount() == 1) { 71 // Cannot swap one instruction. 72 Log.debug("Cannot swap insns in a method with only one."); 73 return false; 74 } 75 return true; 76 } 77 78 @Override generateMutation(MutatableCode mutatableCode)79 protected Mutation generateMutation(MutatableCode mutatableCode) { 80 int swapInsnIdx = 0; 81 int swapWithInsnIdx = 0; 82 83 boolean foundFirstInsn = false; 84 boolean foundSecondInsn = false; 85 86 while (!foundFirstInsn || !foundSecondInsn) { 87 // Look for the first insn. 88 while (!foundFirstInsn) { 89 swapInsnIdx = rng.nextInt(mutatableCode.getInstructionCount()); 90 MInsn toBeSwapped = mutatableCode.getInstructionAt(swapInsnIdx); 91 foundFirstInsn = true; 92 if (toBeSwapped.insn.justRaw) { 93 foundFirstInsn = false; 94 } 95 } 96 97 // Look for the second insn. 98 int secondInsnAttempts = 0; 99 while (!foundSecondInsn) { 100 int delta = rng.nextInt(5) - 1; 101 102 if (delta == 0) { 103 continue; 104 } 105 106 swapWithInsnIdx = swapInsnIdx + delta; 107 foundSecondInsn = true; 108 109 // Check insn is in valid range. 110 if (swapWithInsnIdx < 0) { 111 foundSecondInsn = false; 112 } else if (swapWithInsnIdx >= mutatableCode.getInstructionCount()) { 113 foundSecondInsn = false; 114 } 115 116 // Finally, check if we're swapping with a raw insn. 117 if (foundSecondInsn) { 118 if (mutatableCode.getInstructionAt(swapWithInsnIdx).insn.justRaw) { 119 foundSecondInsn = false; 120 } 121 } 122 123 // If we've checked 10 times for an insn to swap with, 124 // and still found nothing, then try a new first insn. 125 if (!foundSecondInsn) { 126 secondInsnAttempts++; 127 if (secondInsnAttempts == 10) { 128 foundFirstInsn = false; 129 break; 130 } 131 } 132 } 133 } 134 135 AssociatedMutation mutation = new AssociatedMutation(); 136 mutation.setup(this.getClass(), mutatableCode); 137 mutation.swapInsnIdx = swapInsnIdx; 138 mutation.swapWithInsnIdx = swapWithInsnIdx; 139 return mutation; 140 } 141 142 @Override applyMutation(Mutation uncastMutation)143 protected void applyMutation(Mutation uncastMutation) { 144 // Cast the Mutation to our AssociatedMutation, so we can access its fields. 145 AssociatedMutation mutation = (AssociatedMutation) uncastMutation; 146 MutatableCode mutatableCode = mutation.mutatableCode; 147 148 MInsn toBeSwapped = mutatableCode.getInstructionAt(mutation.swapInsnIdx); 149 MInsn swappedWith = mutatableCode.getInstructionAt(mutation.swapWithInsnIdx); 150 151 Log.info("Swapping " + toBeSwapped + " with " + swappedWith); 152 153 stats.incrementStat("Swapped two instructions"); 154 155 mutatableCode.swapInstructionsByIndex(mutation.swapInsnIdx, mutation.swapWithInsnIdx); 156 157 Log.info("Now " + swappedWith + " is swapped with " + toBeSwapped); 158 } 159 } 160