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