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;
18 
19 import dexfuzz.Log;
20 import dexfuzz.rawdex.Instruction;
21 import dexfuzz.rawdex.Opcode;
22 
23 import java.util.ArrayList;
24 import java.util.Collections;
25 import java.util.LinkedList;
26 import java.util.List;
27 
28 /**
29  * A class that represents a CodeItem in a way that is more amenable to mutation.
30  */
31 public class MutatableCode {
32   /**
33    * To ensure we update the correct CodeItem in the raw DEX file.
34    */
35   public int codeItemIdx;
36 
37   /**
38    * This is an index into the Program's list of MutatableCodes.
39    */
40   public int mutatableCodeIdx;
41 
42   /**
43    * Number of registers this code uses.
44    */
45   public short registersSize;
46 
47   /**
48    * Number of ins this code has.
49    */
50   public short insSize;
51 
52   /**
53    * Number of outs this code has.
54    */
55   public short outsSize;
56 
57   /**
58    * Number of tries this code has.
59    */
60   public short triesSize;
61 
62   /**
63    * CodeTranslator is responsible for creating this, and
64    * converting it back to a list of Instructions.
65    */
66   private List<MInsn> mutatableInsns;
67 
68   /**
69    * CodeTranslator is responsible for creating this, and
70    * converting it back to the correct form for CodeItems.
71    */
72   public List<MTryBlock> mutatableTries;
73 
74   /**
75    * The name of the method this code represents.
76    */
77   public String name;
78   public String shorty;
79   public boolean isStatic;
80 
81   /**
82    * The Program that owns this MutatableCode.
83    * Currently used to get the size of constant pools for
84    * PoolIndexChanger/RandomInstructionGenerator
85    */
86   public Program program;
87 
88   private short originalInVReg;
89   private short tempVRegsAllocated;
90   private short initialTempVReg;
91   private boolean vregsNeedCopying;
92   private int numMoveInsnsGenerated;
93 
MutatableCode(Program program)94   public MutatableCode(Program program) {
95     this.program = program;
96     this.mutatableInsns = new LinkedList<MInsn>();
97   }
98 
99   /**
100    * Call this to update all instructions after the provided mInsn, to have their
101    * locations adjusted by the provided offset. It will also mark that they have been updated.
102    */
updateInstructionLocationsAfter(MInsn mInsn, int offset)103   public void updateInstructionLocationsAfter(MInsn mInsn, int offset) {
104     boolean updating = false;
105     for (MInsn mInsnChecking : mutatableInsns) {
106       if (updating) {
107         mInsnChecking.locationUpdated = true;
108         mInsnChecking.location += offset;
109       } else {
110         if (mInsnChecking == mInsn) {
111           updating = true;
112         }
113       }
114 
115     }
116   }
117 
recalculateLocations()118   private void recalculateLocations() {
119     int loc = 0;
120     for (MInsn mInsn : mutatableInsns) {
121       mInsn.location = loc;
122       loc += mInsn.insn.getSize();
123     }
124   }
125 
getInstructions()126   public List<MInsn> getInstructions() {
127     return Collections.unmodifiableList(mutatableInsns);
128   }
129 
getInstructionCount()130   public int getInstructionCount() {
131     return mutatableInsns.size();
132   }
133 
getInstructionIndex(MInsn mInsn)134   public int getInstructionIndex(MInsn mInsn) {
135     return mutatableInsns.indexOf(mInsn);
136   }
137 
getInstructionAt(int idx)138   public MInsn getInstructionAt(int idx) {
139     return mutatableInsns.get(idx);
140   }
141 
addInstructionToEnd(MInsn mInsn)142   public void addInstructionToEnd(MInsn mInsn) {
143     mutatableInsns.add(mInsn);
144   }
145 
insertInstructionAfter(MInsn toBeInserted, int insertionIdx)146   public void insertInstructionAfter(MInsn toBeInserted, int insertionIdx) {
147     if ((insertionIdx + 1) < mutatableInsns.size()) {
148       insertInstructionAt(toBeInserted, insertionIdx + 1);
149     } else {
150       // Appending to end.
151       MInsn finalInsn = mutatableInsns.get(mutatableInsns.size() - 1);
152       toBeInserted.location = finalInsn.location + finalInsn.insn.getSize();
153       mutatableInsns.add(toBeInserted);
154     }
155   }
156 
157   /**
158    * Has same semantics as List.add()
159    */
insertInstructionAt(MInsn toBeInserted, int insertionIdx)160   public void insertInstructionAt(MInsn toBeInserted, int insertionIdx) {
161     MInsn currentInsn = mutatableInsns.get(insertionIdx);
162     toBeInserted.location = currentInsn.location;
163     mutatableInsns.add(insertionIdx , toBeInserted);
164     updateInstructionLocationsAfter(toBeInserted, toBeInserted.insn.getSize());
165   }
166 
167   /**
168    * Checks if any MTryBlock's instruction refs pointed at the 'before' MInsn,
169    * and points them to the 'after' MInsn, if so. 'twoWay' will check if 'after'
170    * was pointed to, and point refs to the 'before' insn.
171    * (one-way is used when deleting instructions,
172    * two-way is used when swapping instructions.)
173    */
updateTryBlocksWithReplacementInsn(MInsn before, MInsn after, boolean twoWay)174   private void updateTryBlocksWithReplacementInsn(MInsn before, MInsn after,
175       boolean twoWay) {
176     if (triesSize > 0) {
177       for (MTryBlock mTryBlock : mutatableTries) {
178         if (mTryBlock.startInsn == before) {
179           Log.debug("Try block's first instruction was updated");
180           mTryBlock.startInsn = after;
181         } else if (twoWay && mTryBlock.startInsn == after) {
182           Log.debug("Try block's first instruction was updated");
183           mTryBlock.startInsn = before;
184         }
185         if (mTryBlock.endInsn == before) {
186           Log.debug("Try block's last instruction was updated");
187           mTryBlock.endInsn = after;
188         } else if (twoWay && mTryBlock.endInsn == after) {
189           Log.debug("Try block's last instruction was updated");
190           mTryBlock.endInsn = before;
191         }
192         if (mTryBlock.catchAllHandler == before) {
193           Log.debug("Try block's catch-all instruction was updated");
194           mTryBlock.catchAllHandler = after;
195         } else if (twoWay && mTryBlock.catchAllHandler == after) {
196           Log.debug("Try block's catch-all instruction was updated");
197           mTryBlock.catchAllHandler = before;
198         }
199 
200         List<Integer> matchesIndicesToChange = new ArrayList<Integer>();
201         List<Integer> replacementIndicesToChange = null;
202         if (twoWay) {
203           replacementIndicesToChange = new ArrayList<Integer>();
204         }
205 
206         int idx = 0;
207         for (MInsn handler : mTryBlock.handlers) {
208           if (handler == before) {
209             matchesIndicesToChange.add(idx);
210             Log.debug("Try block's handler instruction was updated");
211           } else if (twoWay && handler == after) {
212             replacementIndicesToChange.add(idx);
213             Log.debug("Try block's handler instruction was updated");
214           }
215           idx++;
216         }
217 
218         for (int idxToChange : matchesIndicesToChange) {
219           mTryBlock.handlers.set(idxToChange, after);
220         }
221 
222         if (twoWay) {
223           for (int idxToChange : replacementIndicesToChange) {
224             mTryBlock.handlers.set(idxToChange, before);
225           }
226         }
227       }
228     }
229   }
230 
231   /**
232    * The actual implementation of deleteInstruction called by
233    * the single-argument deleteInstructions.
234    */
deleteInstructionFull(MInsn toBeDeleted, int toBeDeletedIdx)235   private void deleteInstructionFull(MInsn toBeDeleted, int toBeDeletedIdx) {
236     // Make sure we update all locations afterwards first.
237     updateInstructionLocationsAfter(toBeDeleted, -(toBeDeleted.insn.getSize()));
238 
239     // Remove it.
240     mutatableInsns.remove(toBeDeletedIdx);
241 
242     // Update any branch instructions that branched to the instruction we just deleted!
243 
244     // First, pick the replacement target.
245     int replacementTargetIdx = toBeDeletedIdx;
246     if (replacementTargetIdx == mutatableInsns.size()) {
247       replacementTargetIdx--;
248     }
249     MInsn replacementTarget = mutatableInsns.get(replacementTargetIdx);
250 
251     for (MInsn mInsn : mutatableInsns) {
252       if (mInsn instanceof MBranchInsn) {
253         // Check if this branch insn points at the insn we just deleted.
254         MBranchInsn branchInsn = (MBranchInsn) mInsn;
255         MInsn target = branchInsn.target;
256         if (target == toBeDeleted) {
257           Log.debug(branchInsn + " was pointing at the deleted instruction, updated.");
258           branchInsn.target = replacementTarget;
259         }
260       } else if (mInsn instanceof MSwitchInsn) {
261         // Check if any of this switch insn's targets points at the insn we just deleted.
262         MSwitchInsn switchInsn = (MSwitchInsn) mInsn;
263         List<Integer> indicesToChange = new ArrayList<Integer>();
264         int idx = 0;
265         for (MInsn target : switchInsn.targets) {
266           if (target == toBeDeleted) {
267             indicesToChange.add(idx);
268             Log.debug(switchInsn + "[" + idx
269                 + "] was pointing at the deleted instruction, updated.");
270           }
271           idx++;
272         }
273         for (int idxToChange : indicesToChange) {
274           switchInsn.targets.remove(idxToChange);
275           switchInsn.targets.add(idxToChange, replacementTarget);
276         }
277       }
278     }
279 
280     // Now update the try blocks.
281     updateTryBlocksWithReplacementInsn(toBeDeleted, replacementTarget, false);
282   }
283 
284   /**
285    * Delete the provided MInsn.
286    */
deleteInstruction(MInsn toBeDeleted)287   public void deleteInstruction(MInsn toBeDeleted) {
288     deleteInstructionFull(toBeDeleted, mutatableInsns.indexOf(toBeDeleted));
289   }
290 
291   /**
292    * Delete the MInsn at the provided index.
293    */
deleteInstruction(int toBeDeletedIdx)294   public void deleteInstruction(int toBeDeletedIdx) {
295     deleteInstructionFull(mutatableInsns.get(toBeDeletedIdx), toBeDeletedIdx);
296   }
297 
swapInstructionsByIndex(int aIdx, int bIdx)298   public void swapInstructionsByIndex(int aIdx, int bIdx) {
299     MInsn aInsn = mutatableInsns.get(aIdx);
300     MInsn bInsn = mutatableInsns.get(bIdx);
301 
302     mutatableInsns.set(aIdx, bInsn);
303     mutatableInsns.set(bIdx, aInsn);
304 
305     updateTryBlocksWithReplacementInsn(aInsn, bInsn, true);
306 
307     recalculateLocations();
308   }
309 
310   /**
311    * Some mutators may require the use of temporary registers. For instance,
312    * to easily add in printing of values without having to look for registers
313    * that aren't currently live.
314    * The idea is to allocate these registers at the top of the set of registers.
315    * Because this will then shift where the arguments to the method are, we then
316    * change the start of the method to copy the arguments to the method
317    * into the place where the rest of the method's code expects them to be.
318    * Call allocateTemporaryVRegs(n), then use getTemporaryVReg(n),
319    * and then make sure finishedUsingTemporaryVRegs() is called!
320    */
allocateTemporaryVRegs(int count)321   public void allocateTemporaryVRegs(int count) {
322     if (count > tempVRegsAllocated) {
323       if (tempVRegsAllocated == 0) {
324         Log.info("Allocating temporary vregs for method...");
325         initialTempVReg = registersSize;
326         originalInVReg = (short) (registersSize - insSize);
327       } else {
328         Log.info("Extending allocation of temporary vregs for method...");
329       }
330       registersSize = (short) (initialTempVReg + count);
331       if (outsSize < count) {
332         outsSize = (short) count;
333       }
334       vregsNeedCopying = true;
335       tempVRegsAllocated = (short) count;
336     }
337   }
338 
getTemporaryVReg(int number)339   public int getTemporaryVReg(int number) {
340     if (number >= tempVRegsAllocated) {
341       Log.errorAndQuit("Not allocated enough temporary vregs!");
342     }
343     return initialTempVReg + number;
344   }
345 
finishedUsingTemporaryVRegs()346   public void finishedUsingTemporaryVRegs() {
347     if (tempVRegsAllocated > 0 && vregsNeedCopying) {
348       // Just delete all the move instructions and generate again, if we already have some.
349       while (numMoveInsnsGenerated > 0) {
350         deleteInstruction(0);
351         numMoveInsnsGenerated--;
352       }
353 
354       Log.info("Moving 'in' vregs to correct locations after allocating temporary vregs");
355 
356       int shortyIdx = 0;
357       if (isStatic) {
358         shortyIdx = 1;
359       }
360 
361       int insertionCounter = 0;
362 
363       // Insert copy insns that move all the in VRs down.
364       for (int i = 0; i < insSize; i++) {
365         MInsn moveInsn = new MInsn();
366         moveInsn.insn = new Instruction();
367         moveInsn.insn.vregA = originalInVReg + i;
368         moveInsn.insn.vregB = originalInVReg + i + tempVRegsAllocated;
369 
370         char type = 'L';
371         if (shortyIdx > 0) {
372           type = shorty.charAt(shortyIdx);
373         }
374         shortyIdx++;
375 
376         if (type == 'L') {
377           moveInsn.insn.info = Instruction.getOpcodeInfo(Opcode.MOVE_OBJECT_16);
378         } else if (type == 'D' || type == 'J') {
379           moveInsn.insn.info = Instruction.getOpcodeInfo(Opcode.MOVE_WIDE_16);
380           i++;
381         } else {
382           moveInsn.insn.info = Instruction.getOpcodeInfo(Opcode.MOVE_16);
383         }
384 
385         insertInstructionAt(moveInsn, insertionCounter);
386         insertionCounter++;
387         Log.info("Temp vregs creation, Added instruction " + moveInsn);
388         numMoveInsnsGenerated++;
389       }
390 
391       vregsNeedCopying = false;
392     }
393   }
394 
395   /**
396    * When we insert new Field/Type/MethodIds into the DEX file, this may shunt some Ids
397    * into a new position in the table. If this happens, every reference to the Ids must
398    * be updated! Because CodeItems have their Instructions wrapped into a graph of MInsns
399    * during mutation, they don't have a view of all their instructions during mutation,
400    * and so if they are asked to update their instructions' indices into the tables, they
401    * must call this method to get the actual list of instructions they currently own.
402    */
requestLatestInstructions()403   public List<Instruction> requestLatestInstructions() {
404     List<Instruction> latestInsns = new ArrayList<Instruction>();
405     for (MInsn mInsn : mutatableInsns) {
406       latestInsns.add(mInsn.insn);
407     }
408     return latestInsns;
409   }
410 }
411