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
17package dexfuzz.program.mutators;
18
19import dexfuzz.Log;
20import dexfuzz.MutationStats;
21import dexfuzz.program.MBranchInsn;
22import dexfuzz.program.MInsn;
23import dexfuzz.program.MutatableCode;
24import dexfuzz.program.Mutation;
25import dexfuzz.rawdex.Instruction;
26import dexfuzz.rawdex.Opcode;
27import dexfuzz.rawdex.OpcodeInfo;
28import dexfuzz.rawdex.formats.AbstractFormat;
29import dexfuzz.rawdex.formats.ContainsConst;
30import dexfuzz.rawdex.formats.ContainsPoolIndex;
31import dexfuzz.rawdex.formats.ContainsPoolIndex.PoolIndexKind;
32import dexfuzz.rawdex.formats.ContainsVRegs;
33
34import java.util.List;
35import java.util.Random;
36
37public 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