1 /*
2  * Copyright (C) 2017 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.Instruction;
25 import dexfuzz.rawdex.Opcode;
26 
27 import java.util.ArrayList;
28 import java.util.List;
29 import java.util.Random;
30 
31 public class NewArrayLengthChanger 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 newArrayToChangeIdx;
39 
40     @Override
getString()41     public String getString() {
42       return Integer.toString(newArrayToChangeIdx);
43     }
44 
45     @Override
parseString(String[] elements)46     public void parseString(String[] elements) {
47       newArrayToChangeIdx = Integer.parseInt(elements[2]);
48     }
49   }
50 
51   // The following two methods are here for the benefit of MutationSerializer,
52   // so it can create a CodeMutator and get the correct associated Mutation, as it
53   // reads in mutations from a dump of mutations.
54   @Override
getNewMutation()55   public Mutation getNewMutation() {
56     return new AssociatedMutation();
57   }
58 
NewArrayLengthChanger()59   public NewArrayLengthChanger() { }
60 
NewArrayLengthChanger(Random rng, MutationStats stats, List<Mutation> mutations)61   public NewArrayLengthChanger(Random rng, MutationStats stats, List<Mutation> mutations) {
62     super(rng, stats, mutations);
63     likelihood = 50;
64   }
65 
66   // A cache that should only exist between generateMutation() and applyMutation(),
67   // or be created at the start of applyMutation(), if we're reading in mutations from
68   // a file.
69   private List<MInsn> newArrayLengthInsns = null;
70 
generateCachedArrayLengthInsns(MutatableCode mutatableCode)71   private void generateCachedArrayLengthInsns(MutatableCode mutatableCode) {
72     if (newArrayLengthInsns != null) {
73       return;
74     }
75 
76     newArrayLengthInsns = new ArrayList<MInsn>();
77 
78     for (MInsn mInsn : mutatableCode.getInstructions()) {
79       if (isNewArray(mInsn)) {
80         newArrayLengthInsns.add(mInsn);
81       }
82     }
83   }
84 
85   @Override
canMutate(MutatableCode mutatableCode)86   protected boolean canMutate(MutatableCode mutatableCode) {
87     for (MInsn mInsn : mutatableCode.getInstructions()) {
88       // TODO: Add filled-new-array and filled-new-array/range with their respective
89       // positions of registers and also proper encoding.
90       if (isNewArray(mInsn)) {
91         return true;
92       }
93     }
94     Log.debug("No New Array instruction in method, skipping...");
95     return false;
96   }
97 
98   @Override
generateMutation(MutatableCode mutatableCode)99   protected Mutation generateMutation(MutatableCode mutatableCode) {
100     generateCachedArrayLengthInsns(mutatableCode);
101 
102     int newArrayIdx = rng.nextInt(newArrayLengthInsns.size());
103 
104     AssociatedMutation mutation = new AssociatedMutation();
105     mutation.setup(this.getClass(), mutatableCode);
106     mutation.newArrayToChangeIdx = newArrayIdx;
107     return mutation;
108   }
109 
110   @Override
applyMutation(Mutation uncastMutation)111   protected void applyMutation(Mutation uncastMutation) {
112     // Cast the Mutation to our AssociatedMutation, so we can access its fields.
113     AssociatedMutation mutation = (AssociatedMutation) uncastMutation;
114     MutatableCode mutatableCode = mutation.mutatableCode;
115     MInsn newArrayInsn = newArrayLengthInsns.get(mutation.newArrayToChangeIdx);
116     int newArrayInsnIdx = mutatableCode.getInstructionIndex(newArrayInsn);
117     // If the original new-array instruction is no longer present
118     // in the code (as indicated by a negative index), we make a
119     // best effort to find any other new-array instruction to
120     // apply the mutation to. If that effort fails, we simply
121     // bail by doing nothing.
122     if (newArrayInsnIdx < 0) {
123       newArrayInsnIdx = scanNewArray(mutatableCode);
124       if (newArrayInsnIdx == -1) {
125         return;
126       }
127     }
128 
129     MInsn newInsn = new MInsn();
130     newInsn.insn = new Instruction();
131     newInsn.insn.info = Instruction.getOpcodeInfo(Opcode.CONST_16);
132     mutatableCode.allocateTemporaryVRegs(1);
133     newArrayInsn.insn.vregB = mutatableCode.getTemporaryVReg(0);
134     newInsn.insn.vregA = (int) newArrayInsn.insn.vregB;
135     // New length chosen randomly between 1 to 100.
136     newInsn.insn.vregB = rng.nextInt(100);
137     mutatableCode.insertInstructionAt(newInsn, newArrayInsnIdx);
138     Log.info("Changed the length of the array to " + newInsn.insn.vregB);
139     stats.incrementStat("Changed length of new array");
140     mutatableCode.finishedUsingTemporaryVRegs();
141   }
142 
isNewArray(MInsn mInsn)143   private boolean isNewArray(MInsn mInsn) {
144     Opcode opcode = mInsn.insn.info.opcode;
145     return opcode == Opcode.NEW_ARRAY;
146   }
147 
148   // Return the index of first new-array in the method, -1 otherwise.
scanNewArray(MutatableCode mutatableCode)149   private int scanNewArray(MutatableCode mutatableCode) {
150     int idx = 0;
151     for (MInsn mInsn : mutatableCode.getInstructions()) {
152       if (isNewArray(mInsn)) {
153         return idx;
154       }
155       idx++;
156     }
157     return -1;
158   }
159 }