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.MutatableCode;
23import dexfuzz.program.Mutation;
24import dexfuzz.rawdex.formats.ContainsPoolIndex;
25import dexfuzz.rawdex.formats.ContainsPoolIndex.PoolIndexKind;
26
27import java.util.ArrayList;
28import java.util.List;
29import java.util.Random;
30
31public 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
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
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
60  public Mutation getNewMutation() {
61    return new AssociatedMutation();
62  }
63
64  public PoolIndexChanger() { }
65
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
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
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
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
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