1959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle/* 2959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * Copyright (C) 2014 The Android Open Source Project 3959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * 4959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * Licensed under the Apache License, Version 2.0 (the "License"); 5959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * you may not use this file except in compliance with the License. 6959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * You may obtain a copy of the License at 7959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * 8959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * http://www.apache.org/licenses/LICENSE-2.0 9959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * 10959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * Unless required by applicable law or agreed to in writing, software 11959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * distributed under the License is distributed on an "AS IS" BASIS, 12959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * See the License for the specific language governing permissions and 14959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * limitations under the License. 15959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 16959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 17959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kylepackage dexfuzz.program; 18959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 19959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.Log; 20959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.MutationStats; 21959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.Options; 22959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.listeners.BaseListener; 23959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.mutators.ArithOpChanger; 24959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.mutators.BranchShifter; 25959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.mutators.CmpBiasChanger; 26959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.mutators.CodeMutator; 27959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.mutators.ConstantValueChanger; 28959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.mutators.ConversionRepeater; 29959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.mutators.FieldFlagChanger; 30959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.mutators.InstructionDeleter; 31959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.mutators.InstructionDuplicator; 32959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.mutators.InstructionSwapper; 33959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.mutators.NewMethodCaller; 34959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.mutators.NonsenseStringPrinter; 35959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.mutators.PoolIndexChanger; 36959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.mutators.RandomInstructionGenerator; 37959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.mutators.SwitchBranchShifter; 38959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.mutators.TryBlockShifter; 39959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.mutators.ValuePrinter; 40959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.mutators.VRegChanger; 41959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.rawdex.ClassDataItem; 42959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.rawdex.ClassDefItem; 43959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.rawdex.CodeItem; 44959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.rawdex.DexRandomAccessFile; 45959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.rawdex.EncodedField; 46959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.rawdex.EncodedMethod; 47959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.rawdex.FieldIdItem; 48959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.rawdex.MethodIdItem; 49959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.rawdex.ProtoIdItem; 50959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.rawdex.RawDexFile; 51959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.rawdex.TypeIdItem; 52959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.rawdex.formats.ContainsPoolIndex.PoolIndexKind; 53959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 54959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport java.io.BufferedReader; 55959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport java.io.BufferedWriter; 56959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport java.io.FileReader; 57959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport java.io.FileWriter; 58959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport java.io.IOException; 59959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport java.util.ArrayList; 60959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport java.util.HashMap; 61959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport java.util.List; 62959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport java.util.Map; 63959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport java.util.Random; 64959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 65959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle/** 66959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * After the raw DEX file has been parsed, it is passed into this class 67959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * that represents the program in a mutatable form. 68959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * The class uses a CodeTranslator to translate between the raw DEX form 69959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * for a method, and the mutatable form. It also controls all CodeMutators, 70959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * deciding which ones should be applied to each CodeItem. 71959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 72959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kylepublic class Program { 73959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 74959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * The RNG used during mutation. 75959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 76959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private Random rng; 77959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 78959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 79959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * The seed that was given to the RNG. 80959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 81959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle public long rngSeed; 82959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 83959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 84959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * The parsed raw DEX file. 85959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 86959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private RawDexFile rawDexFile; 87959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 88959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 89959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * The system responsible for translating from CodeItems to MutatableCode and vice-versa. 90959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 91959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private CodeTranslator translator; 92959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 93959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 94959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * Responsible for adding new class ID items, method ID items, etc. 95959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 96959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private IdCreator idCreator; 97959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 98959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 99959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * A list of all the MutatableCode that the CodeTranslator produced from 100959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * CodeItems that are acceptable to mutate. 101959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 102959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private List<MutatableCode> mutatableCodes; 103959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 104959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 105959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * A list of all MutatableCode items that were mutated when mutateTheProgram() 106959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * was called. updateRawDexFile() will update the relevant CodeItems when called, 107959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * and then clear this list. 108959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 109959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private List<MutatableCode> mutatedCodes; 110959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 111959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 112959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * A list of all registered CodeMutators that this Program can use to mutate methods. 113959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 114959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private List<CodeMutator> mutators; 115959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 116959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 117959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * Used if we're loading mutations from a file, so we can find the correct mutator. 118959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 119959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private Map<Class<? extends CodeMutator>, CodeMutator> mutatorsLookupByClass; 120959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 121959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 122959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * Tracks mutation stats. 123959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 124959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private MutationStats mutationStats; 125959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 126959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 127959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * A list of all mutations used for loading/dumping mutations from/to a file. 128959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 129959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private List<Mutation> mutations; 130959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 131959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 132959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * The listener who is interested in events. 133959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * May be a listener that is responsible for multiple listeners. 134959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 135959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private BaseListener listener; 136959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 137959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 138959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * Given a maximum number of mutations that can be performed on a method, n, 139959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * give up after attempting (n * this value) mutations for any method. 140959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 141959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private static final int MAXIMUM_MUTATION_ATTEMPT_FACTOR = 10; 142959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 143959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 144959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * Construct the mutatable Program based on the raw DEX file that was parsed initially. 145959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 146959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle public Program(RawDexFile rawDexFile, List<Mutation> previousMutations, 147959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle BaseListener listener) { 148959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle this.listener = listener; 149959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 150959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle idCreator = new IdCreator(rawDexFile); 151959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 152959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Set up the RNG. 153959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle rng = new Random(); 154959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (Options.usingProvidedSeed) { 155959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle rng.setSeed(Options.rngSeed); 156959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle rngSeed = Options.rngSeed; 157959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } else { 158959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle long seed = System.currentTimeMillis(); 159959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle listener.handleSeed(seed); 160959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle rng.setSeed(seed); 161959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle rngSeed = seed; 162959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 163959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 164959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (previousMutations != null) { 165959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutations = previousMutations; 166959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } else { 167959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Allocate the mutations list. 168959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutations = new ArrayList<Mutation>(); 169959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 170959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Read in the mutations if we need to. 171959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (Options.loadMutations) { 172959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Allocate the mutators lookup table. 173959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutatorsLookupByClass = new HashMap<Class<? extends CodeMutator>, CodeMutator>(); 174959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle loadMutationsFromDisk(Options.loadMutationsFile); 175959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 176959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 177959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 178959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Allocate the mutators list. 179959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutators = new ArrayList<CodeMutator>(); 180959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 181959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle this.rawDexFile = rawDexFile; 182959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 183959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutatableCodes = new ArrayList<MutatableCode>(); 184959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutatedCodes = new ArrayList<MutatableCode>(); 185959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 186959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle translator = new CodeTranslator(); 187959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 188959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutationStats = new MutationStats(); 189959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 190959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Register all the code mutators here. 191959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle registerMutator(new ArithOpChanger(rng, mutationStats, mutations)); 192959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle registerMutator(new BranchShifter(rng, mutationStats, mutations)); 193959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle registerMutator(new CmpBiasChanger(rng, mutationStats, mutations)); 194959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle registerMutator(new ConstantValueChanger(rng, mutationStats, mutations)); 195959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle registerMutator(new ConversionRepeater(rng, mutationStats, mutations)); 196959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle registerMutator(new FieldFlagChanger(rng, mutationStats, mutations)); 197959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle registerMutator(new InstructionDeleter(rng, mutationStats, mutations)); 198959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle registerMutator(new InstructionDuplicator(rng, mutationStats, mutations)); 199959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle registerMutator(new InstructionSwapper(rng, mutationStats, mutations)); 200959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle registerMutator(new NewMethodCaller(rng, mutationStats, mutations)); 201959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle registerMutator(new NonsenseStringPrinter(rng, mutationStats, mutations)); 202959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle registerMutator(new PoolIndexChanger(rng, mutationStats, mutations)); 203959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle registerMutator(new RandomInstructionGenerator(rng, mutationStats, mutations)); 204959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle registerMutator(new SwitchBranchShifter(rng, mutationStats, mutations)); 205959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle registerMutator(new TryBlockShifter(rng, mutationStats, mutations)); 206959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle registerMutator(new ValuePrinter(rng, mutationStats, mutations)); 207959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle registerMutator(new VRegChanger(rng, mutationStats, mutations)); 208959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 209959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle associateClassDefsAndClassData(); 210959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle associateCodeItemsWithMethodNames(); 211959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 212959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle int codeItemIdx = 0; 213959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle for (CodeItem codeItem : rawDexFile.codeItems) { 214959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (legalToMutate(codeItem)) { 215959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.debug("Legal to mutate code item " + codeItemIdx); 216959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle int mutatableCodeIdx = mutatableCodes.size(); 217959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutatableCodes.add(translator.codeItemToMutatableCode(this, codeItem, 218959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle codeItemIdx, mutatableCodeIdx)); 219959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } else { 220959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.debug("Not legal to mutate code item " + codeItemIdx); 221959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 222959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle codeItemIdx++; 223959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 224959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 225959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 226959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private void registerMutator(CodeMutator mutator) { 227959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (mutator.canBeTriggered()) { 228959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.debug("Registering mutator " + mutator.getClass().getSimpleName()); 229959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutators.add(mutator); 230959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 231959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (Options.loadMutations) { 232959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutatorsLookupByClass.put(mutator.getClass(), mutator); 233959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 234959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 235959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 236959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 237959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * Associate ClassDefItem to a ClassDataItem and vice-versa. 238959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * This is so when we're associating method names with code items, 239959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * we can find the name of the class the method belongs to. 240959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 241959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private void associateClassDefsAndClassData() { 242959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle for (ClassDefItem classDefItem : rawDexFile.classDefs) { 243959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (classDefItem.classDataOff.pointsToSomething()) { 244959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle ClassDataItem classDataItem = (ClassDataItem) 245959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle classDefItem.classDataOff.getPointedToItem(); 246959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle classDataItem.meta.classDefItem = classDefItem; 247959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle classDefItem.meta.classDataItem = classDataItem; 248959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 249959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 250959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 251959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 252959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 253959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * For each CodeItem, find the name of the method the item represents. 254959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * This is done to allow the filtering of mutating methods based on if 255959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * they have the name *_MUTATE, but also for debugging info. 256959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 257959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private void associateCodeItemsWithMethodNames() { 258959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Associate method names with codeItems. 259959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle for (ClassDataItem classDataItem : rawDexFile.classDatas) { 260959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 261959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle String className = ""; 262959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (classDataItem.meta.classDefItem != null) { 263959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle int typeIdx = classDataItem.meta.classDefItem.classIdx; 264959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle TypeIdItem typeIdItem = rawDexFile.typeIds.get(typeIdx); 265959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle className = rawDexFile.stringDatas.get(typeIdItem.descriptorIdx).getString() + "."; 266959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 267959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 268959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Do direct methods... 269959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Track the current method index with this value, since the encoding in 270959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // each EncodedMethod is the absolute index for the first EncodedMethod, 271959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // and then relative index for the rest... 272959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle int methodIdx = 0; 273959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle for (EncodedMethod method : classDataItem.directMethods) { 274959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle methodIdx = associateMethod(method, methodIdx, className); 275959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 276959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Reset methodIdx for virtual methods... 277959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle methodIdx = 0; 278959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle for (EncodedMethod method : classDataItem.virtualMethods) { 279959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle methodIdx = associateMethod(method, methodIdx, className); 280959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 281959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 282959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 283959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 284959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 285959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * Associate the name of the provided method with its CodeItem, if it 286959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * has one. 287959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * 288959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * @param methodIdx The method index of the last EncodedMethod that was handled in this class. 289959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * @return The method index of the EncodedMethod that has just been handled in this class. 290959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 291959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private int associateMethod(EncodedMethod method, int methodIdx, String className) { 292959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (!method.codeOff.pointsToSomething()) { 293959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // This method doesn't have a code item, so we won't encounter it later. 294959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return methodIdx; 295959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 296959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 297959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // First method index is an absolute index. 298959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // The rest are relative to the previous. 299959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // (so if methodIdx is initialised to 0, this single line works) 300959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle methodIdx = methodIdx + method.methodIdxDiff; 301959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 302959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Get the name. 303959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle MethodIdItem methodIdItem = rawDexFile.methodIds.get(methodIdx); 304959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle ProtoIdItem protoIdItem = rawDexFile.protoIds.get(methodIdItem.protoIdx); 305959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle String shorty = rawDexFile.stringDatas.get(protoIdItem.shortyIdx).getString(); 306959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle String methodName = className 307959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle + rawDexFile.stringDatas.get(methodIdItem.nameIdx).getString(); 308959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 309959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Get the codeItem. 310959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (method.codeOff.getPointedToItem() instanceof CodeItem) { 311959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle CodeItem codeItem = (CodeItem) method.codeOff.getPointedToItem(); 312959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle codeItem.meta.methodName = methodName; 313959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle codeItem.meta.shorty = shorty; 314959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle codeItem.meta.isStatic = method.isStatic(); 315959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } else { 316959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.errorAndQuit("You've got an EncodedMethod that points to an Offsettable" 317959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle + " that does not contain a CodeItem"); 318959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 319959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 320959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return methodIdx; 321959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 322959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 323959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 324959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * Determine, based on the current options supplied to dexfuzz, as well as 325959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * its capabilities, if the provided CodeItem can be mutated. 326959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * @param codeItem The CodeItem we may wish to mutate. 327959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * @return If the CodeItem can be mutated. 328959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 329959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private boolean legalToMutate(CodeItem codeItem) { 330959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (!Options.mutateLimit) { 331959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.debug("Mutating everything."); 332959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return true; 333959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 334959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (codeItem.meta.methodName.endsWith("_MUTATE")) { 335959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.debug("Code item marked with _MUTATE."); 336959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return true; 337959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 338959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.debug("Code item not marked with _MUTATE, but not mutating all code items."); 339959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return false; 340959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 341959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 342959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private int getNumberOfMutationsToPerform() { 343959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // We want n mutations to be twice as likely as n+1 mutations. 344959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // 345959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // So if we have max 3, 346959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // then 0 has 8 chances ("tickets"), 347959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // 1 has 4 chances 348959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // 2 has 2 chances 349959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // and 3 has 1 chance 350959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 351959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Allocate the tickets 352959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // n mutations need (2^(n+1) - 1) tickets 353959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // e.g. 354959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // 3 mutations => 15 tickets 355959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // 4 mutations => 31 tickets 356959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle int tickets = (2 << Options.methodMutations) - 1; 357959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 358959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Pick the lucky ticket 359959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle int luckyTicket = rng.nextInt(tickets); 360959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 361959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // The tickets are put into buckets with accordance with log-base-2. 362959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // have to make sure it's luckyTicket + 1, because log(0) is undefined 363959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // so: 364959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // log_2(1) => 0 365959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // log_2(2) => 1 366959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // log_2(3) => 1 367959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // log_2(4) => 2 368959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // log_2(5) => 2 369959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // log_2(6) => 2 370959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // log_2(7) => 2 371959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // log_2(8) => 3 372959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // ... 373959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // so to make the highest mutation value the rarest, 374959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // subtract log_2(luckyTicket+1) from the maximum number 375959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // log2(x) <=> 31 - Integer.numberOfLeadingZeros(x) 376959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle int luckyMutation = Options.methodMutations 377959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle - (31 - Integer.numberOfLeadingZeros(luckyTicket + 1)); 378959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 379959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return luckyMutation; 380959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 381959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 382959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 383959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * Returns true if we completely failed to mutate this method's mutatable code after 384959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * attempting to. 385959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 386959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private boolean mutateAMutatableCode(MutatableCode mutatableCode) { 387959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle int mutations = getNumberOfMutationsToPerform(); 388959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 389959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.info("Attempting " + mutations + " mutations for method " + mutatableCode.name); 390959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 391959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle int mutationsApplied = 0; 392959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 393959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle int maximumMutationAttempts = Options.methodMutations * MAXIMUM_MUTATION_ATTEMPT_FACTOR; 394959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle int mutationAttempts = 0; 395959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle boolean hadToBail = false; 396959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 397959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle while (mutationsApplied < mutations) { 398959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle int mutatorIdx = rng.nextInt(mutators.size()); 399959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle CodeMutator mutator = mutators.get(mutatorIdx); 400959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.info("Running mutator " + mutator.getClass().getSimpleName()); 401959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (mutator.attemptToMutate(mutatableCode)) { 402959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutationsApplied++; 403959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 404959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutationAttempts++; 405959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (mutationAttempts > maximumMutationAttempts) { 406959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.info("Bailing out on mutation for this method, tried too many times..."); 407959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle hadToBail = true; 408959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle break; 409959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 410959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 411959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 412959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // If any of them actually mutated it, excellent! 413959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (mutationsApplied > 0) { 414959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.info("Method was mutated."); 415959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutatedCodes.add(mutatableCode); 416959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } else { 417959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.info("Method was not mutated."); 418959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 419959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 420959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return ((mutationsApplied == 0) && hadToBail); 421959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 422959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 423959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 424959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * Go through each mutatable method in turn, and attempt to mutate it. 425959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * Afterwards, call updateRawDexFile() to apply the results of mutation to the 426959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * original code. 427959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 428959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle public void mutateTheProgram() { 429959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (Options.loadMutations) { 430959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle applyMutationsFromList(); 431959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return; 432959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 433959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 434959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Typically, this is 2 to 10... 435959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle int methodsToMutate = Options.minMethods 436959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle + rng.nextInt((Options.maxMethods - Options.minMethods) + 1); 437959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 438959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Check we aren't trying to mutate more methods than we have. 439959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (methodsToMutate > mutatableCodes.size()) { 440959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle methodsToMutate = mutatableCodes.size(); 441959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 442959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 443959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Check if we're going to end up mutating all the methods. 444959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (methodsToMutate == mutatableCodes.size()) { 445959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Just do them all in order. 446959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.info("Mutating all possible methods."); 447959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle for (MutatableCode mutatableCode : mutatableCodes) { 448959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (mutatableCode == null) { 449959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.errorAndQuit("Why do you have a null MutatableCode?"); 450959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 451959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutateAMutatableCode(mutatableCode); 452959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 453959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.info("Finished mutating all possible methods."); 454959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } else { 455959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Pick them at random. 456959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.info("Randomly selecting " + methodsToMutate + " methods to mutate."); 457959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle while (mutatedCodes.size() < methodsToMutate) { 458959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle int randomMethodIdx = rng.nextInt(mutatableCodes.size()); 459959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle MutatableCode mutatableCode = mutatableCodes.get(randomMethodIdx); 460959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (mutatableCode == null) { 461959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.errorAndQuit("Why do you have a null MutatableCode?"); 462959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 463959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (!mutatedCodes.contains(mutatableCode)) { 464959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle boolean completelyFailedToMutate = mutateAMutatableCode(mutatableCode); 465959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (completelyFailedToMutate) { 466959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle methodsToMutate--; 467959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 468959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 469959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 470959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.info("Finished mutating the methods."); 471959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 472959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 473959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle listener.handleMutationStats(mutationStats.getStatsString()); 474959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 475959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (Options.dumpMutations) { 476959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle writeMutationsToDisk(Options.dumpMutationsFile); 477959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 478959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 479959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 480959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private void writeMutationsToDisk(String fileName) { 481959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.debug("Writing mutations to disk."); 482959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle try { 483959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle BufferedWriter writer = new BufferedWriter(new FileWriter(fileName)); 484959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle for (Mutation mutation : mutations) { 485959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle MutationSerializer.writeMutation(writer, mutation); 486959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 487959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle writer.close(); 488959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } catch (IOException e) { 489959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.errorAndQuit("IOException while writing mutations to disk..."); 490959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 491959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 492959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 493959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private void loadMutationsFromDisk(String fileName) { 494959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.debug("Loading mutations from disk."); 495959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle try { 496959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle BufferedReader reader = new BufferedReader(new FileReader(fileName)); 497959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle while (reader.ready()) { 498959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Mutation mutation = MutationSerializer.readMutation(reader); 499959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutations.add(mutation); 500959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 501959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle reader.close(); 502959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } catch (IOException e) { 503959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.errorAndQuit("IOException while loading mutations from disk..."); 504959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 505959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 506959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 507959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private void applyMutationsFromList() { 508959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.info("Applying preloaded list of mutations..."); 509959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle for (Mutation mutation : mutations) { 510959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Repopulate the MutatableCode field from the recorded index into the Program's list. 511959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutation.mutatableCode = mutatableCodes.get(mutation.mutatableCodeIdx); 512959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 513959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Get the right mutator. 514959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle CodeMutator mutator = mutatorsLookupByClass.get(mutation.mutatorClass); 515959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 516959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Apply the mutation. 517959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutator.forceMutate(mutation); 518959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 519959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Add this mutatable code to the list of mutated codes, if we haven't already. 520959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (!mutatedCodes.contains(mutation.mutatableCode)) { 521959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutatedCodes.add(mutation.mutatableCode); 522959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 523959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 524959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.info("...finished applying preloaded list of mutations."); 525959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 526959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 527959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle public List<Mutation> getMutations() { 528959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return mutations; 529959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 530959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 531959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 532959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * Updates any CodeItems that need to be updated after mutation. 533959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 534959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle public boolean updateRawDexFile() { 535959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle boolean anythingMutated = !(mutatedCodes.isEmpty()); 536959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle for (MutatableCode mutatedCode : mutatedCodes) { 537959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle translator.mutatableCodeToCodeItem(rawDexFile.codeItems 538959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle .get(mutatedCode.codeItemIdx), mutatedCode); 539959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 540959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutatedCodes.clear(); 541959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return anythingMutated; 542959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 543959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 544959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle public void writeRawDexFile(DexRandomAccessFile file) throws IOException { 545959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle rawDexFile.write(file); 546959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 547959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 548959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle public void updateRawDexFileHeader(DexRandomAccessFile file) throws IOException { 549959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle rawDexFile.updateHeader(file); 550959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 551959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 552959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 553959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * Used by the CodeMutators to determine legal index values. 554959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 555959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle public int getTotalPoolIndicesByKind(PoolIndexKind poolIndexKind) { 556959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle switch (poolIndexKind) { 557959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle case Type: 558959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return rawDexFile.typeIds.size(); 559959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle case Field: 560959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return rawDexFile.fieldIds.size(); 561959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle case String: 562959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return rawDexFile.stringIds.size(); 563959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle case Method: 564959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return rawDexFile.methodIds.size(); 565959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle case Invalid: 566959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return 0; 567959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle default: 568959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 569959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return 0; 570959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 571959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 572959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 573959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * Used by the CodeMutators to lookup and/or create Ids. 574959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 575959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle public IdCreator getNewItemCreator() { 576959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return idCreator; 577959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 578959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 579959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 580959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * Used by FieldFlagChanger, to find an EncodedField for a specified field in an insn, 581959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * if that field is actually defined in this DEX file. If not, null is returned. 582959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 583959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle public EncodedField getEncodedField(int fieldIdx) { 584959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (fieldIdx >= rawDexFile.fieldIds.size()) { 585959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.debug(String.format("Field idx 0x%x specified is not defined in this DEX file.", 586959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle fieldIdx)); 587959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return null; 588959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 589959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle FieldIdItem fieldId = rawDexFile.fieldIds.get(fieldIdx); 590959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 591959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle for (ClassDefItem classDef : rawDexFile.classDefs) { 592959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (classDef.classIdx == fieldId.classIdx) { 593959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle ClassDataItem classData = classDef.meta.classDataItem; 594959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return classData.getEncodedFieldWithIndex(fieldIdx); 595959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 596959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 597959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 598959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.debug(String.format("Field idx 0x%x specified is not defined in this DEX file.", 599959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle fieldIdx)); 600959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return null; 601959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 602959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle} 603