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 import dexfuzz.rawdex.formats.ContainsPoolIndex;
25 import dexfuzz.rawdex.formats.ContainsPoolIndex.PoolIndexKind;
26 
27 import java.util.ArrayList;
28 import java.util.List;
29 import java.util.Random;
30 
31 public class PoolIndexChanger extends CodeMutator {
32   /**
33    * Every CodeMutator has an AssociatedMutation, representing the
34    * mutation that this CodeMutator can perform, to allow separate
35    * generateMutation() and applyMutation() phases, allowing serialization.
36    */
37   public static class AssociatedMutation extends Mutation {
38     public int poolIndexInsnIdx;
39     public int newPoolIndex;
40 
41     @Override
getString()42     public String getString() {
43       StringBuilder builder = new StringBuilder();
44       builder.append(poolIndexInsnIdx).append(" ");
45       builder.append(newPoolIndex);
46       return builder.toString();
47     }
48 
49     @Override
parseString(String[] elements)50     public void parseString(String[] elements) {
51       poolIndexInsnIdx = Integer.parseInt(elements[2]);
52       newPoolIndex = Integer.parseInt(elements[3]);
53     }
54   }
55 
56   // The following two methods are here for the benefit of MutationSerializer,
57   // so it can create a CodeMutator and get the correct associated Mutation, as it
58   // reads in mutations from a dump of mutations.
59   @Override
getNewMutation()60   public Mutation getNewMutation() {
61     return new AssociatedMutation();
62   }
63 
PoolIndexChanger()64   public PoolIndexChanger() { }
65 
PoolIndexChanger(Random rng, MutationStats stats, List<Mutation> mutations)66   public PoolIndexChanger(Random rng, MutationStats stats, List<Mutation> mutations) {
67     super(rng, stats, mutations);
68     likelihood = 30;
69   }
70 
71   // A cache that should only exist between generateMutation() and applyMutation(),
72   // or be created at the start of applyMutation(), if we're reading in mutations from
73   // a file.
74   private List<MInsn> poolIndexInsns = null;
75 
generateCachedPoolIndexInsns(MutatableCode mutatableCode)76   private void generateCachedPoolIndexInsns(MutatableCode mutatableCode) {
77     if (poolIndexInsns != null) {
78       return;
79     }
80 
81     poolIndexInsns = new ArrayList<MInsn>();
82     for (MInsn mInsn : mutatableCode.getInstructions()) {
83       if (mInsn.insn.info.format instanceof ContainsPoolIndex) {
84         poolIndexInsns.add(mInsn);
85       }
86     }
87   }
88 
89   @Override
canMutate(MutatableCode mutatableCode)90   protected boolean canMutate(MutatableCode mutatableCode) {
91     // Remember what kinds of pool indices we see.
92     List<PoolIndexKind> seenKinds = new ArrayList<PoolIndexKind>();
93 
94     for (MInsn mInsn : mutatableCode.getInstructions()) {
95       if (mInsn.insn.info.format instanceof ContainsPoolIndex) {
96 
97         ContainsPoolIndex containsPoolIndex =
98             (ContainsPoolIndex)mInsn.insn.info.format;
99 
100         PoolIndexKind newPoolIndexKind =
101             containsPoolIndex.getPoolIndexKind(mInsn.insn.info);
102 
103         seenKinds.add(newPoolIndexKind);
104       }
105     }
106 
107     // Now check that there exists a kind such that the max pool index for
108     // the kind is greater than 1 (i.e., something can be changed)
109     if (!seenKinds.isEmpty()) {
110 
111       for (PoolIndexKind kind : seenKinds) {
112         int numPoolIndices = mutatableCode.program.getTotalPoolIndicesByKind(kind);
113         if (numPoolIndices > 1) {
114           return true;
115         }
116       }
117 
118       Log.debug("Method does not contain any insns that index into a const pool size > 1");
119       return false;
120     }
121 
122     Log.debug("Method contains no instructions that index into the constant pool.");
123     return false;
124   }
125 
126   @Override
generateMutation(MutatableCode mutatableCode)127   protected Mutation generateMutation(MutatableCode mutatableCode) {
128     generateCachedPoolIndexInsns(mutatableCode);
129 
130     int poolIndexInsnIdx = 0;
131     boolean found = false;
132 
133     int oldPoolIndex = 0;
134     int newPoolIndex = 0;
135     int maxPoolIndex = 0;
136 
137     // Pick a random instruction.
138     while (!found) {
139       poolIndexInsnIdx = rng.nextInt(poolIndexInsns.size());
140       MInsn poolIndexInsn = poolIndexInsns.get(poolIndexInsnIdx);
141 
142       found = true;
143 
144       ContainsPoolIndex containsPoolIndex =
145           (ContainsPoolIndex)poolIndexInsn.insn.info.format;
146 
147       // Get the pool index.
148       oldPoolIndex = containsPoolIndex.getPoolIndex(poolIndexInsn.insn);
149       newPoolIndex = oldPoolIndex;
150 
151       // Get the largest pool index available for the provided kind of pool index.
152       PoolIndexKind poolIndexKind =
153           containsPoolIndex.getPoolIndexKind(poolIndexInsn.insn.info);
154       maxPoolIndex = mutatableCode.program.getTotalPoolIndicesByKind(poolIndexKind);
155 
156       if (maxPoolIndex <= 1) {
157         found = false;
158       }
159     }
160 
161     // Get a new pool index.
162     while (newPoolIndex == oldPoolIndex) {
163       newPoolIndex = rng.nextInt(maxPoolIndex);
164     }
165 
166     AssociatedMutation mutation = new AssociatedMutation();
167     mutation.setup(this.getClass(), mutatableCode);
168     mutation.poolIndexInsnIdx = poolIndexInsnIdx;
169     mutation.newPoolIndex = newPoolIndex;
170     return mutation;
171   }
172 
173   @Override
applyMutation(Mutation uncastMutation)174   protected void applyMutation(Mutation uncastMutation) {
175     // Cast the Mutation to our AssociatedMutation, so we can access its fields.
176     AssociatedMutation mutation = (AssociatedMutation) uncastMutation;
177     MutatableCode mutatableCode = mutation.mutatableCode;
178 
179     generateCachedPoolIndexInsns(mutatableCode);
180 
181     MInsn poolIndexInsn = poolIndexInsns.get(mutation.poolIndexInsnIdx);
182 
183     ContainsPoolIndex containsPoolIndex =
184         (ContainsPoolIndex) poolIndexInsn.insn.info.format;
185 
186     int oldPoolIndex = containsPoolIndex.getPoolIndex(poolIndexInsn.insn);
187 
188     Log.info("Changed pool index " + oldPoolIndex + " to " + mutation.newPoolIndex
189         + " in " + poolIndexInsn);
190 
191     stats.incrementStat("Changed constant pool index");
192 
193     // Set the new pool index.
194     containsPoolIndex.setPoolIndex(poolIndexInsn.insn, mutation.newPoolIndex);
195 
196     // Clear cache.
197     poolIndexInsns = null;
198   }
199 }
200