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.MSwitchInsn;
23 import dexfuzz.program.MutatableCode;
24 import dexfuzz.program.Mutation;
25 
26 import java.util.ArrayList;
27 import java.util.List;
28 import java.util.Random;
29 
30 public 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
getString()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
parseString(String[] elements)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
getNewMutation()62   public Mutation getNewMutation() {
63     return new AssociatedMutation();
64   }
65 
SwitchBranchShifter()66   public SwitchBranchShifter() { }
67 
SwitchBranchShifter(Random rng, MutationStats stats, List<Mutation> mutations)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 
generateCachedSwitchInsns(MutatableCode mutatableCode)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
canMutate(MutatableCode mutatableCode)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
generateMutation(MutatableCode mutatableCode)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
applyMutation(Mutation uncastMutation)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