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.mutators; 18959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 19959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.Log; 20959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.MutationStats; 21959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.MBranchInsn; 22959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.MInsn; 23959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.MutatableCode; 24959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport dexfuzz.program.Mutation; 25959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 26959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport java.util.ArrayList; 27959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport java.util.List; 28959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyleimport java.util.Random; 29959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 30959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kylepublic class BranchShifter extends CodeMutator { 31959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle /** 32959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * Every CodeMutator has an AssociatedMutation, representing the 33959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * mutation that this CodeMutator can perform, to allow separate 34959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle * generateMutation() and applyMutation() phases, allowing serialization. 35959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle */ 36959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle public static class AssociatedMutation extends Mutation { 37959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle public int branchInsnIdx; 38959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle public int newTargetIdx; 39959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 40959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle @Override 41959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle public String getString() { 42959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle StringBuilder builder = new StringBuilder(); 43959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle builder.append(branchInsnIdx).append(" "); 44959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle builder.append(newTargetIdx); 45959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return builder.toString(); 46959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 47959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 48959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle @Override 49959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle public void parseString(String[] elements) { 50959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle branchInsnIdx = Integer.parseInt(elements[2]); 51959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle newTargetIdx = Integer.parseInt(elements[3]); 52959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 53959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 54959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 55959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // The following two methods are here for the benefit of MutationSerializer, 56959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // so it can create a CodeMutator and get the correct associated Mutation, as it 57959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // reads in mutations from a dump of mutations. 58959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle @Override 59959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle public Mutation getNewMutation() { 60959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return new AssociatedMutation(); 61959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 62959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 63959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle public BranchShifter() { } 64959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 65959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle public BranchShifter(Random rng, MutationStats stats, List<Mutation> mutations) { 66959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle super(rng, stats, mutations); 67959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle likelihood = 30; 68959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 69959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 70959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // A cache that should only exist between generateMutation() and applyMutation(), 71959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // or be created at the start of applyMutation(), if we're reading in mutations from 72959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // a file. 73959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private List<MBranchInsn> branchInsns; 74959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 75959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle private void generateCachedBranchInsns(MutatableCode mutatableCode) { 76959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (branchInsns != null) { 77959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return; 78959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 79959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 80959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle branchInsns = new ArrayList<MBranchInsn>(); 81959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 82959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle for (MInsn mInsn : mutatableCode.getInstructions()) { 83959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (mInsn instanceof MBranchInsn) { 84959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle branchInsns.add((MBranchInsn) mInsn); 85959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 86959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 87959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 88959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 89959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle @Override 90959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle protected boolean canMutate(MutatableCode mutatableCode) { 91959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Can't shift a branch if there's only one instruction in the method. 92959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (mutatableCode.getInstructionCount() == 1) { 93959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.debug("Method contains only one instruction, skipping."); 94959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return false; 95959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 96959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle for (MInsn mInsn : mutatableCode.getInstructions()) { 97959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (mInsn instanceof MBranchInsn) { 98959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return true; 99959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 100959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 101959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 102959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.debug("Method contains no branch instructions."); 103959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return false; 104959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 105959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 106959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle @Override 107959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle protected Mutation generateMutation(MutatableCode mutatableCode) { 108959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle generateCachedBranchInsns(mutatableCode); 109959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 110959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Pick a random branching instruction. 111959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle int branchInsnIdx = rng.nextInt(branchInsns.size()); 112959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle MBranchInsn branchInsn = branchInsns.get(branchInsnIdx); 113959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 114959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Get its original target, find its index. 115959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle MInsn oldTargetInsn = branchInsn.target; 116959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle int oldTargetInsnIdx = mutatableCode.getInstructionIndex(oldTargetInsn); 117959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 118959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle int newTargetIdx = oldTargetInsnIdx; 119959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 120959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle int delta = 0; 121959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 122959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Keep searching for a new index. 123959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle while (newTargetIdx == oldTargetInsnIdx) { 124959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Vary by +/- 2 instructions. 125959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle delta = 0; 126959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle while (delta == 0) { 127959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle delta = (rng.nextInt(5) - 2); 128959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 129959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 130959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle newTargetIdx = oldTargetInsnIdx + delta; 131959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 132959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Check the new index is legal. 133959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle if (newTargetIdx < 0) { 134959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle newTargetIdx = 0; 135959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } else if (newTargetIdx >= mutatableCode.getInstructionCount()) { 136959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle newTargetIdx = mutatableCode.getInstructionCount() - 1; 137959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 138959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 139959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 140959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle AssociatedMutation mutation = new AssociatedMutation(); 141959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutation.setup(this.getClass(), mutatableCode); 142959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutation.branchInsnIdx = branchInsnIdx; 143959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle mutation.newTargetIdx = newTargetIdx; 144959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle return mutation; 145959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 146959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 147959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle @Override 148959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle protected void applyMutation(Mutation uncastMutation) { 149959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Cast the Mutation to our AssociatedMutation, so we can access its fields. 150959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle AssociatedMutation mutation = (AssociatedMutation) uncastMutation; 151959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle MutatableCode mutatableCode = mutation.mutatableCode; 152959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 153959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle generateCachedBranchInsns(mutatableCode); 154959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 155959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle MBranchInsn branchInsn = branchInsns.get(mutation.branchInsnIdx); 156959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 157959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Get the new target. 158959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle MInsn newTargetInsn = mutatableCode.getInstructionAt(mutation.newTargetIdx); 159959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 160959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Set the new target. 161959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle branchInsn.target = newTargetInsn; 162959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 163959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle Log.info("Shifted the target of " + branchInsn + " to point to " + newTargetInsn); 164959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 165959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle stats.incrementStat("Shifted branch target"); 166959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle 167959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle // Clear cache. 168959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle branchInsns = null; 169959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle } 170959ffdf65f280ee90b7944a8dd610564e7f99e69Stephen Kyle} 171