Home | History | Annotate | Download | only in mutators 
      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.Opcode;
     25 import dexfuzz.rawdex.formats.ContainsPoolIndex;
     26 import dexfuzz.rawdex.formats.ContainsPoolIndex.PoolIndexKind;
     27 
     28 import java.util.ArrayList;
     29 import java.util.List;
     30 import java.util.Random;
     31 
     32 /**
     33  * Mutator NewInstanceChanger changes the new instance type in a method to
     34  * any random type from the pool.
     35  */
     36 public class NewInstanceChanger extends CodeMutator {
     37 
     38   /**
     39    * Every CodeMutator has an AssociatedMutation, representing the
     40    * mutation that this CodeMutator can perform, to allow separate
     41    * generateMutation() and applyMutation() phases, allowing serialization.
     42    */
     43   public static class AssociatedMutation extends Mutation {
     44     public int newInstanceToChangeIdx;
     45     public int newInstanceTypeIdx;
     46 
     47     @Override
     48     public String getString() {
     49       StringBuilder builder = new StringBuilder();
     50       builder.append(newInstanceToChangeIdx).append(" ");
     51       builder.append(newInstanceTypeIdx);
     52       return builder.toString();
     53     }
     54 
     55     @Override
     56     public void parseString(String[] elements) {
     57       newInstanceToChangeIdx = Integer.parseInt(elements[2]);
     58       newInstanceTypeIdx = Integer.parseInt(elements[3]);
     59     }
     60   }
     61 
     62   // The following two methods are here for the benefit of MutationSerializer,
     63   // so it can create a CodeMutator and get the correct associated Mutation, as it
     64   // reads in mutations from a dump of mutations.
     65   @Override
     66   public Mutation getNewMutation() {
     67     return new AssociatedMutation();
     68   }
     69 
     70   public NewInstanceChanger() {}
     71 
     72   public NewInstanceChanger(Random rng, MutationStats stats, List<Mutation> mutations) {
     73     super(rng, stats, mutations);
     74     likelihood = 10;
     75   }
     76 
     77   // A cache that should only exist between generateMutation() and applyMutation(),
     78   // or be created at the start of applyMutation(), if we're reading in mutations from
     79   // a file.
     80   private List<MInsn> newInstanceCachedInsns = null;
     81 
     82   private void generateCachedNewInstanceInsns(MutatableCode mutatableCode) {
     83     if (newInstanceCachedInsns != null) {
     84       return;
     85     }
     86 
     87     newInstanceCachedInsns = new ArrayList<MInsn>();
     88 
     89     for (MInsn mInsn : mutatableCode.getInstructions()) {
     90       if (mInsn.insn.info.opcode == Opcode.NEW_INSTANCE) {
     91         newInstanceCachedInsns.add(mInsn);
     92       }
     93     }
     94   }
     95 
     96   @Override
     97   protected boolean canMutate(MutatableCode mutatableCode) {
     98     // Cannot change the pool index with only one type.
     99     if (mutatableCode.program.getTotalPoolIndicesByKind(PoolIndexKind.Type) < 2) {
    100       Log.debug("Cannot mutate, only one type, skipping...");
    101       return false;
    102     }
    103 
    104     for (MInsn mInsn : mutatableCode.getInstructions()) {
    105       if (mInsn.insn.info.opcode == Opcode.NEW_INSTANCE) {
    106         return true;
    107       }
    108     }
    109     Log.debug("No New Instance in method, skipping...");
    110     return false;
    111   }
    112 
    113   @Override
    114   protected Mutation generateMutation(MutatableCode mutatableCode) {
    115     generateCachedNewInstanceInsns(mutatableCode);
    116 
    117     int newInstanceIdxInCache = rng.nextInt(newInstanceCachedInsns.size());
    118     MInsn newInstanceInsn = newInstanceCachedInsns.get(newInstanceIdxInCache);
    119     int oldTypeIdx = (int) newInstanceInsn.insn.vregB;
    120     int newTypeIdx = 0;
    121     int totalPoolIndices = mutatableCode.program.getTotalPoolIndicesByKind(PoolIndexKind.Type);
    122     if (totalPoolIndices < 2) {
    123       Log.errorAndQuit("Less than two types present, quitting...");
    124     }
    125 
    126     while (newTypeIdx == oldTypeIdx) {
    127       newTypeIdx = rng.nextInt(totalPoolIndices);
    128     }
    129 
    130     AssociatedMutation mutation = new AssociatedMutation();
    131     mutation.setup(this.getClass(), mutatableCode);
    132     mutation.newInstanceToChangeIdx = newInstanceIdxInCache;
    133     mutation.newInstanceTypeIdx = newTypeIdx;
    134     return mutation;
    135   }
    136 
    137   @Override
    138   protected void applyMutation(Mutation uncastMutation) {
    139     // Cast the Mutation to our AssociatedMutation, so we can access its fields.
    140     AssociatedMutation mutation = (AssociatedMutation) uncastMutation;
    141     MutatableCode mutatableCode = mutation.mutatableCode;
    142 
    143     generateCachedNewInstanceInsns(mutatableCode);
    144 
    145     MInsn newInstanceInsn = newInstanceCachedInsns.get(mutation.newInstanceToChangeIdx);
    146 
    147     ContainsPoolIndex poolIndex = ((ContainsPoolIndex)newInstanceInsn.insn.info.format);
    148 
    149     poolIndex.setPoolIndex(newInstanceInsn.insn, mutation.newInstanceTypeIdx);
    150 
    151     Log.info("Changed the type of " + newInstanceInsn.toString() +
    152         " to " + mutation.newInstanceTypeIdx);
    153 
    154     int foundNewInstanceInsnIdx =
    155         foundInsnIdx(mutatableCode, newInstanceCachedInsns.get(mutation.newInstanceToChangeIdx));
    156 
    157     changeInvokeDirect(foundNewInstanceInsnIdx, mutation);
    158 
    159     stats.incrementStat("Changed new instance.");
    160 
    161     // Clear cache.
    162     newInstanceCachedInsns = null;
    163   }
    164 
    165   /**
    166    * Try to find the invoke-direct/ invoke-direct-range instruction that follows
    167    * the new instance instruction and change the method ID of the instruction.
    168    * @param foundInsnIdx
    169    * @param uncastMutation
    170    */
    171   protected void changeInvokeDirect(int foundInsnIdx, Mutation uncastMutation) {
    172     AssociatedMutation mutation = (AssociatedMutation) uncastMutation;
    173     MutatableCode mutatableCode = mutation.mutatableCode;
    174     if (foundInsnIdx == -1 ||
    175         foundInsnIdx + 1 == mutatableCode.getInstructionCount()) {
    176       return;
    177     }
    178 
    179     MInsn insn = mutatableCode.getInstructionAt(foundInsnIdx + 1);
    180     if (isInvokeInst(insn)) {
    181       ContainsPoolIndex poolIndex =((ContainsPoolIndex)insn.insn.info.format);
    182       long oldMethodIdx = poolIndex.getPoolIndex(insn.insn);
    183       String className = mutatableCode.program.getTypeString(mutation.newInstanceTypeIdx);
    184       String methodName = mutatableCode.program.getMethodString((int) oldMethodIdx);
    185       String shorty = mutatableCode.program.getMethodProto((int) oldMethodIdx);
    186 
    187       // Matches the type of the invoke with the randomly changed type of the prior new-instance.
    188       // This might create a lot of verification failures but still works many times.
    189       // TODO: Work on generating a program which finds a valid type.
    190       int methodId = mutatableCode.program.getNewItemCreator().
    191           findOrCreateMethodId(className, methodName, shorty);
    192 
    193       poolIndex.setPoolIndex(insn.insn, mutation.newInstanceTypeIdx);
    194 
    195       insn.insn.vregB = methodId;
    196 
    197       Log.info("Changed " + oldMethodIdx + " to " + methodId);
    198     }
    199   }
    200 
    201   protected boolean isInvokeInst(MInsn mInsn) {
    202     return (mInsn.insn.info.opcode == Opcode.INVOKE_DIRECT ||
    203         mInsn.insn.info.opcode == Opcode.INVOKE_DIRECT_RANGE);
    204   }
    205 
    206   // Check if there is an new instance instruction, and if found, return the index.
    207   // If not, return -1.
    208   protected int foundInsnIdx(MutatableCode mutatableCode, MInsn newInstanceInsn) {
    209     int i = 0;
    210     for (MInsn mInsn : mutatableCode.getInstructions()) {
    211       if (mInsn == newInstanceInsn) {
    212         return i;
    213       }
    214       i++;
    215     }
    216     return -1;
    217   }
    218 }
    219