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;
25
26import java.util.ArrayList;
27import java.util.List;
28import java.util.Random;
29
30public class BranchShifter extends CodeMutator {
31  /**
32   * Every CodeMutator has an AssociatedMutation, representing the
33   * mutation that this CodeMutator can perform, to allow separate
34   * generateMutation() and applyMutation() phases, allowing serialization.
35   */
36  public static class AssociatedMutation extends Mutation {
37    public int branchInsnIdx;
38    public int newTargetIdx;
39
40    @Override
41    public String getString() {
42      StringBuilder builder = new StringBuilder();
43      builder.append(branchInsnIdx).append(" ");
44      builder.append(newTargetIdx);
45      return builder.toString();
46    }
47
48    @Override
49    public void parseString(String[] elements) {
50      branchInsnIdx = Integer.parseInt(elements[2]);
51      newTargetIdx = Integer.parseInt(elements[3]);
52    }
53  }
54
55  // The following two methods are here for the benefit of MutationSerializer,
56  // so it can create a CodeMutator and get the correct associated Mutation, as it
57  // reads in mutations from a dump of mutations.
58  @Override
59  public Mutation getNewMutation() {
60    return new AssociatedMutation();
61  }
62
63  public BranchShifter() { }
64
65  public BranchShifter(Random rng, MutationStats stats, List<Mutation> mutations) {
66    super(rng, stats, mutations);
67    likelihood = 30;
68  }
69
70  // A cache that should only exist between generateMutation() and applyMutation(),
71  // or be created at the start of applyMutation(), if we're reading in mutations from
72  // a file.
73  private List<MBranchInsn> branchInsns;
74
75  private void generateCachedBranchInsns(MutatableCode mutatableCode) {
76    if (branchInsns != null) {
77      return;
78    }
79
80    branchInsns = new ArrayList<MBranchInsn>();
81
82    for (MInsn mInsn : mutatableCode.getInstructions()) {
83      if (mInsn instanceof MBranchInsn) {
84        branchInsns.add((MBranchInsn) mInsn);
85      }
86    }
87  }
88
89  @Override
90  protected boolean canMutate(MutatableCode mutatableCode) {
91    // Can't shift a branch if there's only one instruction in the method.
92    if (mutatableCode.getInstructionCount() == 1) {
93      Log.debug("Method contains only one instruction, skipping.");
94      return false;
95    }
96    for (MInsn mInsn : mutatableCode.getInstructions()) {
97      if (mInsn instanceof MBranchInsn) {
98        return true;
99      }
100    }
101
102    Log.debug("Method contains no branch instructions.");
103    return false;
104  }
105
106  @Override
107  protected Mutation generateMutation(MutatableCode mutatableCode) {
108    generateCachedBranchInsns(mutatableCode);
109
110    // Pick a random branching instruction.
111    int branchInsnIdx = rng.nextInt(branchInsns.size());
112    MBranchInsn branchInsn = branchInsns.get(branchInsnIdx);
113
114    // Get its original target, find its index.
115    MInsn oldTargetInsn = branchInsn.target;
116    int oldTargetInsnIdx = mutatableCode.getInstructionIndex(oldTargetInsn);
117
118    int newTargetIdx = oldTargetInsnIdx;
119
120    int delta = 0;
121
122    // Keep searching for a new index.
123    while (newTargetIdx == oldTargetInsnIdx) {
124      // Vary by +/- 2 instructions.
125      delta = 0;
126      while (delta == 0) {
127        delta = (rng.nextInt(5) - 2);
128      }
129
130      newTargetIdx = oldTargetInsnIdx + delta;
131
132      // Check the new index is legal.
133      if (newTargetIdx < 0) {
134        newTargetIdx = 0;
135      } else if (newTargetIdx >= mutatableCode.getInstructionCount()) {
136        newTargetIdx = mutatableCode.getInstructionCount() - 1;
137      }
138    }
139
140    AssociatedMutation mutation = new AssociatedMutation();
141    mutation.setup(this.getClass(), mutatableCode);
142    mutation.branchInsnIdx = branchInsnIdx;
143    mutation.newTargetIdx = newTargetIdx;
144    return mutation;
145  }
146
147  @Override
148  protected void applyMutation(Mutation uncastMutation) {
149    // Cast the Mutation to our AssociatedMutation, so we can access its fields.
150    AssociatedMutation mutation = (AssociatedMutation) uncastMutation;
151    MutatableCode mutatableCode = mutation.mutatableCode;
152
153    generateCachedBranchInsns(mutatableCode);
154
155    MBranchInsn branchInsn = branchInsns.get(mutation.branchInsnIdx);
156
157    // Get the new target.
158    MInsn newTargetInsn = mutatableCode.getInstructionAt(mutation.newTargetIdx);
159
160    // Set the new target.
161    branchInsn.target = newTargetInsn;
162
163    Log.info("Shifted the target of " + branchInsn + " to point to " + newTargetInsn);
164
165    stats.incrementStat("Shifted branch target");
166
167    // Clear cache.
168    branchInsns = null;
169  }
170}
171