blob: c56b1bcca739fabe80b56cd87b80771a4f830c4c [file] [log] [blame]
/*
* Copyright (C) 2014 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package dexfuzz.program;
import dexfuzz.Log;
import dexfuzz.rawdex.Instruction;
import dexfuzz.rawdex.Opcode;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
/**
* A class that represents a CodeItem in a way that is more amenable to mutation.
*/
public class MutatableCode {
/**
* To ensure we update the correct CodeItem in the raw DEX file.
*/
public int codeItemIdx;
/**
* This is an index into the Program's list of MutatableCodes.
*/
public int mutatableCodeIdx;
/**
* Number of registers this code uses.
*/
public short registersSize;
/**
* Number of ins this code has.
*/
public short insSize;
/**
* Number of outs this code has.
*/
public short outsSize;
/**
* Number of tries this code has.
*/
public short triesSize;
/**
* CodeTranslator is responsible for creating this, and
* converting it back to a list of Instructions.
*/
private List<MInsn> mutatableInsns;
/**
* CodeTranslator is responsible for creating this, and
* converting it back to the correct form for CodeItems.
*/
public List<MTryBlock> mutatableTries;
/**
* The name of the method this code represents.
*/
public String name;
public String shorty;
public boolean isStatic;
/**
* The Program that owns this MutatableCode.
* Currently used to get the size of constant pools for
* PoolIndexChanger/RandomInstructionGenerator
*/
public Program program;
private short originalInVReg;
private short tempVRegsAllocated;
private short initialTempVReg;
private boolean vregsNeedCopying;
private int numMoveInsnsGenerated;
public MutatableCode(Program program) {
this.program = program;
this.mutatableInsns = new LinkedList<MInsn>();
}
/**
* Call this to update all instructions after the provided mInsn, to have their
* locations adjusted by the provided offset. It will also mark that they have been updated.
*/
public void updateInstructionLocationsAfter(MInsn mInsn, int offset) {
boolean updating = false;
for (MInsn mInsnChecking : mutatableInsns) {
if (updating) {
mInsnChecking.locationUpdated = true;
mInsnChecking.location += offset;
} else {
if (mInsnChecking == mInsn) {
updating = true;
}
}
}
}
private void recalculateLocations() {
int loc = 0;
for (MInsn mInsn : mutatableInsns) {
mInsn.location = loc;
loc += mInsn.insn.getSize();
}
}
public List<MInsn> getInstructions() {
return Collections.unmodifiableList(mutatableInsns);
}
public int getInstructionCount() {
return mutatableInsns.size();
}
public int getInstructionIndex(MInsn mInsn) {
return mutatableInsns.indexOf(mInsn);
}
public MInsn getInstructionAt(int idx) {
return mutatableInsns.get(idx);
}
public void addInstructionToEnd(MInsn mInsn) {
mutatableInsns.add(mInsn);
}
public void insertInstructionAfter(MInsn toBeInserted, int insertionIdx) {
if ((insertionIdx + 1) < mutatableInsns.size()) {
insertInstructionAt(toBeInserted, insertionIdx + 1);
} else {
// Appending to end.
MInsn finalInsn = mutatableInsns.get(mutatableInsns.size() - 1);
toBeInserted.location = finalInsn.location + finalInsn.insn.getSize();
mutatableInsns.add(toBeInserted);
}
}
/**
* Has same semantics as List.add()
*/
public void insertInstructionAt(MInsn toBeInserted, int insertionIdx) {
MInsn currentInsn = mutatableInsns.get(insertionIdx);
toBeInserted.location = currentInsn.location;
mutatableInsns.add(insertionIdx , toBeInserted);
updateInstructionLocationsAfter(toBeInserted, toBeInserted.insn.getSize());
}
/**
* Checks if any MTryBlock's instruction refs pointed at the 'before' MInsn,
* and points them to the 'after' MInsn, if so. 'twoWay' will check if 'after'
* was pointed to, and point refs to the 'before' insn.
* (one-way is used when deleting instructions,
* two-way is used when swapping instructions.)
*/
private void updateTryBlocksWithReplacementInsn(MInsn before, MInsn after,
boolean twoWay) {
if (triesSize > 0) {
for (MTryBlock mTryBlock : mutatableTries) {
if (mTryBlock.startInsn == before) {
Log.debug("Try block's first instruction was updated");
mTryBlock.startInsn = after;
} else if (twoWay && mTryBlock.startInsn == after) {
Log.debug("Try block's first instruction was updated");
mTryBlock.startInsn = before;
}
if (mTryBlock.endInsn == before) {
Log.debug("Try block's last instruction was updated");
mTryBlock.endInsn = after;
} else if (twoWay && mTryBlock.endInsn == after) {
Log.debug("Try block's last instruction was updated");
mTryBlock.endInsn = before;
}
if (mTryBlock.catchAllHandler == before) {
Log.debug("Try block's catch-all instruction was updated");
mTryBlock.catchAllHandler = after;
} else if (twoWay && mTryBlock.catchAllHandler == after) {
Log.debug("Try block's catch-all instruction was updated");
mTryBlock.catchAllHandler = before;
}
List<Integer> matchesIndicesToChange = new ArrayList<Integer>();
List<Integer> replacementIndicesToChange = null;
if (twoWay) {
replacementIndicesToChange = new ArrayList<Integer>();
}
int idx = 0;
for (MInsn handler : mTryBlock.handlers) {
if (handler == before) {
matchesIndicesToChange.add(idx);
Log.debug("Try block's handler instruction was updated");
} else if (twoWay && handler == after) {
replacementIndicesToChange.add(idx);
Log.debug("Try block's handler instruction was updated");
}
idx++;
}
for (int idxToChange : matchesIndicesToChange) {
mTryBlock.handlers.set(idxToChange, after);
}
if (twoWay) {
for (int idxToChange : replacementIndicesToChange) {
mTryBlock.handlers.set(idxToChange, before);
}
}
}
}
}
/**
* The actual implementation of deleteInstruction called by
* the single-argument deleteInstructions.
*/
private void deleteInstructionFull(MInsn toBeDeleted, int toBeDeletedIdx) {
// Make sure we update all locations afterwards first.
updateInstructionLocationsAfter(toBeDeleted, -(toBeDeleted.insn.getSize()));
// Remove it.
mutatableInsns.remove(toBeDeletedIdx);
// Update any branch instructions that branched to the instruction we just deleted!
// First, pick the replacement target.
int replacementTargetIdx = toBeDeletedIdx;
if (replacementTargetIdx == mutatableInsns.size()) {
replacementTargetIdx--;
}
MInsn replacementTarget = mutatableInsns.get(replacementTargetIdx);
for (MInsn mInsn : mutatableInsns) {
if (mInsn instanceof MBranchInsn) {
// Check if this branch insn points at the insn we just deleted.
MBranchInsn branchInsn = (MBranchInsn) mInsn;
MInsn target = branchInsn.target;
if (target == toBeDeleted) {
Log.debug(branchInsn + " was pointing at the deleted instruction, updated.");
branchInsn.target = replacementTarget;
}
} else if (mInsn instanceof MSwitchInsn) {
// Check if any of this switch insn's targets points at the insn we just deleted.
MSwitchInsn switchInsn = (MSwitchInsn) mInsn;
List<Integer> indicesToChange = new ArrayList<Integer>();
int idx = 0;
for (MInsn target : switchInsn.targets) {
if (target == toBeDeleted) {
indicesToChange.add(idx);
Log.debug(switchInsn + "[" + idx
+ "] was pointing at the deleted instruction, updated.");
}
idx++;
}
for (int idxToChange : indicesToChange) {
switchInsn.targets.remove(idxToChange);
switchInsn.targets.add(idxToChange, replacementTarget);
}
}
}
// Now update the try blocks.
updateTryBlocksWithReplacementInsn(toBeDeleted, replacementTarget, false);
}
/**
* Delete the provided MInsn.
*/
public void deleteInstruction(MInsn toBeDeleted) {
deleteInstructionFull(toBeDeleted, mutatableInsns.indexOf(toBeDeleted));
}
/**
* Delete the MInsn at the provided index.
*/
public void deleteInstruction(int toBeDeletedIdx) {
deleteInstructionFull(mutatableInsns.get(toBeDeletedIdx), toBeDeletedIdx);
}
public void swapInstructionsByIndex(int aIdx, int bIdx) {
MInsn aInsn = mutatableInsns.get(aIdx);
MInsn bInsn = mutatableInsns.get(bIdx);
mutatableInsns.set(aIdx, bInsn);
mutatableInsns.set(bIdx, aInsn);
updateTryBlocksWithReplacementInsn(aInsn, bInsn, true);
recalculateLocations();
}
/**
* Some mutators may require the use of temporary registers. For instance,
* to easily add in printing of values without having to look for registers
* that aren't currently live.
* The idea is to allocate these registers at the top of the set of registers.
* Because this will then shift where the arguments to the method are, we then
* change the start of the method to copy the arguments to the method
* into the place where the rest of the method's code expects them to be.
* Call allocateTemporaryVRegs(n), then use getTemporaryVReg(n),
* and then make sure finishedUsingTemporaryVRegs() is called!
*/
public void allocateTemporaryVRegs(int count) {
if (count > tempVRegsAllocated) {
if (tempVRegsAllocated == 0) {
Log.info("Allocating temporary vregs for method...");
initialTempVReg = registersSize;
originalInVReg = (short) (registersSize - insSize);
} else {
Log.info("Extending allocation of temporary vregs for method...");
}
registersSize = (short) (initialTempVReg + count);
if (outsSize < count) {
outsSize = (short) count;
}
vregsNeedCopying = true;
tempVRegsAllocated = (short) count;
}
}
public int getTemporaryVReg(int number) {
if (number >= tempVRegsAllocated) {
Log.errorAndQuit("Not allocated enough temporary vregs!");
}
return initialTempVReg + number;
}
public void finishedUsingTemporaryVRegs() {
if (tempVRegsAllocated > 0 && vregsNeedCopying) {
// Just delete all the move instructions and generate again, if we already have some.
while (numMoveInsnsGenerated > 0) {
deleteInstruction(0);
numMoveInsnsGenerated--;
}
Log.info("Moving 'in' vregs to correct locations after allocating temporary vregs");
int shortyIdx = 0;
if (isStatic) {
shortyIdx = 1;
}
int insertionCounter = 0;
// Insert copy insns that move all the in VRs down.
for (int i = 0; i < insSize; i++) {
MInsn moveInsn = new MInsn();
moveInsn.insn = new Instruction();
moveInsn.insn.vregA = originalInVReg + i;
moveInsn.insn.vregB = originalInVReg + i + tempVRegsAllocated;
char type = 'L';
if (shortyIdx > 0) {
type = shorty.charAt(shortyIdx);
}
shortyIdx++;
if (type == 'L') {
moveInsn.insn.info = Instruction.getOpcodeInfo(Opcode.MOVE_OBJECT_16);
} else if (type == 'D' || type == 'J') {
moveInsn.insn.info = Instruction.getOpcodeInfo(Opcode.MOVE_WIDE_16);
i++;
} else {
moveInsn.insn.info = Instruction.getOpcodeInfo(Opcode.MOVE_16);
}
insertInstructionAt(moveInsn, insertionCounter);
insertionCounter++;
Log.info("Temp vregs creation, Added instruction " + moveInsn);
numMoveInsnsGenerated++;
}
vregsNeedCopying = false;
}
}
/**
* When we insert new Field/Type/MethodIds into the DEX file, this may shunt some Ids
* into a new position in the table. If this happens, every reference to the Ids must
* be updated! Because CodeItems have their Instructions wrapped into a graph of MInsns
* during mutation, they don't have a view of all their instructions during mutation,
* and so if they are asked to update their instructions' indices into the tables, they
* must call this method to get the actual list of instructions they currently own.
*/
public List<Instruction> requestLatestInstructions() {
List<Instruction> latestInsns = new ArrayList<Instruction>();
for (MInsn mInsn : mutatableInsns) {
latestInsns.add(mInsn.insn);
}
return latestInsns;
}
}