diff options
Diffstat (limited to 'tools/dexfuzz/src/dexfuzz/rawdex/OffsetTracker.java')
| -rw-r--r-- | tools/dexfuzz/src/dexfuzz/rawdex/OffsetTracker.java | 513 |
1 files changed, 513 insertions, 0 deletions
diff --git a/tools/dexfuzz/src/dexfuzz/rawdex/OffsetTracker.java b/tools/dexfuzz/src/dexfuzz/rawdex/OffsetTracker.java new file mode 100644 index 0000000..34d609a --- /dev/null +++ b/tools/dexfuzz/src/dexfuzz/rawdex/OffsetTracker.java @@ -0,0 +1,513 @@ +/* + * 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.rawdex; + +import dexfuzz.Log; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +/** + * This class allows the recording of both Offsettable items (that is, items that can be + * referred to by an offset somewhere else in the file - RawDexObjects) and Offsets. + * The idea in a nutshell is that for every Offsettable item we read, we remember + * its original position in the file using a map, and the order in which the Offsettables were + * written out. We also remember every Offset we read in, and its value. Then, after reading + * the whole file, we use the map to find the Offsettable it pointed at. + * Then, as we write out the file, for every Offsettable we write out, we record its new position, + * using the order we collected earlier. For every Offset we write out, we look at its Offsettable + * to see where it was written. If it hasn't been written yet, then we write out a blank value + * for the time being, remember where that blank value was written, and put the Offset into a + * table for patching once everything has been written out. + * There are some variables (index_after_map_list, restore_point) used for remembering certain + * points to jump forward and back to, because we cannot read and write the file out in exactly + * the same order. + * TODO: Perhaps it makes more sense to just reorder the offsettable_table once it's been read, + * in preparation for the order in which the file is written out? + * Finally, we provide methods for adding new Offsettable items into the right place in the order + * table. + */ +public class OffsetTracker { + /** + * A map from the original offset in the input DEX file to + * the Offsettable it points to. (That Offsettable will contain + * the actual item, and later on the new offset for the item when + * the item is written out. + */ + private Map<Integer, Offsettable> offsettableMap; + + /** + * A table of all Offsettables. We need to ensure we write out + * all items in the same order we read them in, to make sure we update + * the Offsettable.new_position field with the correct value wrt to + * the original_position field. + */ + private List<Offsettable> offsettableTable; + + /** + * A table of all offsets that is populated as we read in the DEX file. + * As the end, we find the correct Offsettable for the Offset in the above + * map, and associate them. + */ + private List<Offset> needsAssociationTable; + + /** + * A table of all offsets that we could not write out an updated offset for + * as we write out a DEX file. Will be checked after writing is complete, + * to allow specific patching of each offset's location as at that point + * all Offsettables will have been updated with their new position. + */ + private List<Offset> needsUpdateTable; + + /** + * Tracks how far we are through the offsettable_table as we write out the file. + */ + private int offsettableTableIdx; + + /** + * Because we write in a slightly different order to how we read + * (why? to read, we read the header, then the map list, and then use the map + * list to read everything else. + * when we write, we write the header, and then we cannot write the map list + * because we don't know where it will go yet, so we write everything else first) + * so: we remember the position in the offsettable_table after we read the map list, + * so we can skip there after we write out the header. + */ + private int indexAfterMapList; + + /** + * Related to index_after_map_list, this is the index we save when we're jumping back to + * write the map list. + */ + private int restorePoint; + + /** + * Create a new OffsetTracker. Should persist between parsing a DEX file, and outputting + * the mutated DEX file. + */ + public OffsetTracker() { + offsettableMap = new HashMap<Integer,Offsettable>(); + offsettableTable = new ArrayList<Offsettable>(); + needsAssociationTable = new ArrayList<Offset>(); + needsUpdateTable = new ArrayList<Offset>(); + } + + /** + * Lookup an Item by the offset it had in the input DEX file. + * @param offset The offset in the input DEX file. + * @return The corresponding Item. + */ + public RawDexObject getItemByOffset(int offset) { + return offsettableMap.get(offset).getItem(); + } + + /** + * As Items are read in, they call this function once they have word-aligned the file pointer, + * to record their position and themselves into an Offsettable object, that will be tracked. + * @param file Used for recording position into the new Offsettable. + * @param item Used for recording the relevant Item into the new Offsettable. + */ + public void getNewOffsettable(DexRandomAccessFile file, RawDexObject item) throws IOException { + Offsettable offsettable = new Offsettable(item, false); + offsettable.setOriginalPosition((int) file.getFilePointer()); + offsettableMap.put(offsettable.getOriginalPosition(), offsettable); + offsettableTable.add(offsettable); + } + + /** + * As Items read in Offsets, they call this function with the offset they originally + * read from the file, to allow later association with an Offsettable. + * @param originalOffset The original offset read from the input DEX file. + * @return An Offset that will later be associated with an Offsettable. + */ + public Offset getNewOffset(int originalOffset) throws IOException { + Offset offset = new Offset(false); + offset.setOriginalOffset(originalOffset); + needsAssociationTable.add(offset); + return offset; + } + + /** + * Only MapItem should call this method, when the MapItem that points to the header + * is read. + */ + public Offset getNewHeaderOffset(int originalOffset) throws IOException { + Offset offset = new Offset(true); + offset.setOriginalOffset(originalOffset); + needsAssociationTable.add(offset); + return offset; + } + + /** + * Call this after reading, to associate Offsets with Offsettables. + */ + public void associateOffsets() { + for (Offset offset : needsAssociationTable) { + if (offset.getOriginalOffset() == 0 && !(offset.pointsAtHeader())) { + offset.setPointsAtNull(); + } else { + offset.pointTo(offsettableMap.get(offset.getOriginalOffset())); + if (!offset.pointsToSomething()) { + Log.error(String.format("Couldn't find original offset 0x%x!", + offset.getOriginalOffset())); + } + } + } + needsAssociationTable.clear(); + } + + /** + * As Items are written out into the output DEX file, this function is called + * to update the next Offsettable with the file pointer's current position. + * This should allow the tracking of new offset locations. + * This also requires that reading and writing of all items happens in the same order + * (with the exception of the map list, see above) + * @param file Used for recording the new position. + */ + public void updatePositionOfNextOffsettable(DexRandomAccessFile file) throws IOException { + if (offsettableTableIdx == offsettableTable.size()) { + Log.errorAndQuit("Not all created Offsettable items have been added to the " + + "Offsettable Table!"); + } + Offsettable offsettable = offsettableTable.get(offsettableTableIdx); + offsettable.setNewPosition((int) file.getFilePointer()); + offsettableTableIdx++; + } + + /** + * As Items are written out, any writing out of an offset must call this function, passing + * in the relevant offset. This function will write out the offset, if the associated + * Offsettable has been updated with its new position, or else will write out a null value, and + * the Offset will be stored for writing after all Items have been written, and all + * Offsettables MUST have been updated. + * @param offset The offset received from getNewOffset(). + * @param file Used for writing out to the file. + * @param useUleb128 Whether or not the offset should be written in UINT or ULEB128 form. + */ + public void tryToWriteOffset(Offset offset, DexRandomAccessFile file, boolean useUleb128) + throws IOException { + if (!offset.isNewOffset() && (!offset.pointsToSomething())) { + if (useUleb128) { + file.writeUleb128(0); + } else { + file.writeUInt(0); + } + return; + } + + if (offset.readyForWriting()) { + if (useUleb128) { + file.writeUleb128(offset.getNewPositionOfItem()); + } else { + file.writeUInt(offset.getNewPositionOfItem()); + } + } else { + offset.setOutputLocation((int) file.getFilePointer()); + if (useUleb128) { + file.writeLargestUleb128(offset.getOriginalOffset()); + offset.setUsesUleb128(); + } else { + file.writeUInt(offset.getOriginalOffset()); + } + needsUpdateTable.add(offset); + } + } + + /** + * This is called after all writing has finished, to write out any Offsets + * that could not be written out during the original writing phase, because their + * associated Offsettables hadn't had their new positions calculated yet. + * @param file Used for writing out to the file. + */ + public void updateOffsets(DexRandomAccessFile file) throws IOException { + if (offsettableTableIdx != offsettableTable.size()) { + Log.errorAndQuit("Being asked to update dangling offsets but the " + + "correct number of offsettables has not been written out!"); + } + for (Offset offset : needsUpdateTable) { + file.seek(offset.getOutputLocation()); + if (offset.usesUleb128()) { + file.writeLargestUleb128(offset.getNewPositionOfItem()); + } else { + file.writeUInt(offset.getNewPositionOfItem()); + } + } + needsUpdateTable.clear(); + } + + /** + * Called after writing out the header, to skip to after the map list. + */ + public void skipToAfterMapList() { + offsettableTableIdx = indexAfterMapList; + } + + /** + * Called once the map list needs to be written out, to set the + * offsettable table index back to the right place. + */ + public void goBackToMapList() { + restorePoint = offsettableTableIdx; + offsettableTableIdx = (indexAfterMapList - 1); + } + + /** + * Called once the map list has been written out, to set the + * offsettable table index back to where it was before. + */ + public void goBackToPreviousPoint() { + if (offsettableTableIdx != indexAfterMapList) { + Log.errorAndQuit("Being asked to go to the point before the MapList was written out," + + " but we're not in the right place."); + } + offsettableTableIdx = restorePoint; + } + + /** + * Called after reading in the map list, to remember the point to be skipped + * to later. + */ + public void rememberPointAfterMapList() { + indexAfterMapList = offsettableTable.size(); + } + + private void updateHeaderOffsetIfValid(Offset offset, Offsettable previousFirst, + Offsettable newFirst, String offsetName) { + if (offset.pointsToThisOffsettable(previousFirst)) { + offset.pointToNew(newFirst); + } else { + Log.errorAndQuit("Header " + offsetName + " offset not pointing at first element?"); + } + } + + private void addTypeListsToMapFile(RawDexFile rawDexFile, Offsettable typeListOffsettable) { + // Create a MapItem for the TypeLists + MapItem typeListMapItem = new MapItem(); + typeListMapItem.offset = new Offset(false); + typeListMapItem.offset.pointToNew(typeListOffsettable); + typeListMapItem.type = MapItem.TYPE_TYPE_LIST; + typeListMapItem.size = 1; + + // Insert into the MapList. + // (first, find the MapItem that points to StringDataItems...) + int idx = 0; + for (MapItem mapItem : rawDexFile.mapList.mapItems) { + if (mapItem.type == MapItem.TYPE_STRING_DATA_ITEM) { + break; + } + idx++; + } + // (now insert the TypeList MapItem just before the StringDataItem one...) + rawDexFile.mapList.mapItems.add(idx, typeListMapItem); + } + + private void addFieldIdsToHeaderAndMapFile(RawDexFile rawDexFile, + Offsettable fieldOffsettable) { + // Add the field IDs to the header. + rawDexFile.header.fieldIdsOff.unsetNullAndPointTo(fieldOffsettable); + rawDexFile.header.fieldIdsSize = 1; + + // Create a MapItem for the field IDs. + MapItem fieldMapItem = new MapItem(); + fieldMapItem.offset = new Offset(false); + fieldMapItem.offset.pointToNew(fieldOffsettable); + fieldMapItem.type = MapItem.TYPE_FIELD_ID_ITEM; + fieldMapItem.size = 1; + + // Insert into the MapList. + // (first, find the MapItem that points to MethodIdItems...) + int idx = 0; + for (MapItem mapItem : rawDexFile.mapList.mapItems) { + if (mapItem.type == MapItem.TYPE_METHOD_ID_ITEM) { + break; + } + idx++; + } + // (now insert the FieldIdItem MapItem just before the MethodIdItem one...) + rawDexFile.mapList.mapItems.add(idx, fieldMapItem); + } + + + private void updateOffsetsInHeaderAndMapFile(RawDexFile rawDexFile, + Offsettable newFirstOffsettable) { + Offsettable prevFirstOffsettable = null; + for (int i = 0; i < offsettableTable.size(); i++) { + if (offsettableTable.get(i) == newFirstOffsettable) { + prevFirstOffsettable = offsettableTable.get(i + 1); + break; + } + } + if (prevFirstOffsettable == null) { + Log.errorAndQuit("When calling updateMapListOffsets, could not find new " + + "first offsettable?"); + } + + // Based on the type of the item we just added, check the relevant Offset in the header + // and if it pointed at the prev_first_offsettable, make it point at the new one. + // NB: if it isn't pointing at the prev one, something is wrong. + HeaderItem header = rawDexFile.header; + if (newFirstOffsettable.getItem() instanceof StringIdItem) { + updateHeaderOffsetIfValid(header.stringIdsOff, prevFirstOffsettable, + newFirstOffsettable, "StringID"); + } else if (newFirstOffsettable.getItem() instanceof TypeIdItem) { + updateHeaderOffsetIfValid(header.typeIdsOff, prevFirstOffsettable, + newFirstOffsettable, "TypeID"); + } else if (newFirstOffsettable.getItem() instanceof ProtoIdItem) { + updateHeaderOffsetIfValid(header.protoIdsOff, prevFirstOffsettable, + newFirstOffsettable, "ProtoID"); + } else if (newFirstOffsettable.getItem() instanceof FieldIdItem) { + updateHeaderOffsetIfValid(header.fieldIdsOff, prevFirstOffsettable, + newFirstOffsettable, "FieldID"); + } else if (newFirstOffsettable.getItem() instanceof MethodIdItem) { + updateHeaderOffsetIfValid(header.methodIdsOff, prevFirstOffsettable, + newFirstOffsettable, "MethodID"); + } else if (newFirstOffsettable.getItem() instanceof ClassDefItem) { + updateHeaderOffsetIfValid(header.classDefsOff, prevFirstOffsettable, + newFirstOffsettable, "ClassDef"); + } + + // Now iterate through the MapList's MapItems, and see if their Offsets pointed at the + // prev_first_offsettable, and if so, make them now point at the new_first_offsettable. + for (MapItem mapItem : rawDexFile.mapList.mapItems) { + if (mapItem.offset.pointsToThisOffsettable(prevFirstOffsettable)) { + Log.info("Updating offset in MapItem (type: " + mapItem.type + ") after " + + "we called insertNewOffsettableAsFirstOfType()"); + mapItem.offset.pointToNew(newFirstOffsettable); + } + } + } + + private void insertOffsettableAt(int idx, Offsettable offsettable) { + offsettableTable.add(idx, offsettable); + if (indexAfterMapList > idx) { + indexAfterMapList++; + } + if (restorePoint > idx) { + restorePoint++; + } + } + + /** + * If we're creating our first TypeList, then IdCreator has to call this method to + * ensure it gets put into the correct place in the offsettable table. + * This assumes TypeLists always come before StringDatas. + */ + public Offsettable insertNewOffsettableAsFirstEverTypeList(RawDexObject item, + RawDexFile rawDexFile) { + // We find the first StringDataItem, the type lists will come before this. + Log.info("Calling insertNewOffsettableAsFirstEverTypeList()"); + for (int i = 0; i < offsettableTable.size(); i++) { + if (offsettableTable.get(i).getItem() instanceof StringDataItem) { + Offsettable offsettable = new Offsettable(item, true); + insertOffsettableAt(i, offsettable); + addTypeListsToMapFile(rawDexFile, offsettable); + return offsettable; + } + } + Log.errorAndQuit("Could not find any StringDataItems to insert the type list before."); + return null; + } + + /** + * If we're creating our first FieldId, then IdCreator has to call this method to + * ensure it gets put into the correct place in the offsettable table. + * This assumes FieldIds always come before MethodIds. + */ + public Offsettable insertNewOffsettableAsFirstEverField(RawDexObject item, + RawDexFile rawDexFile) { + // We find the first MethodIdItem, the fields will come before this. + Log.info("Calling insertNewOffsettableAsFirstEverField()"); + for (int i = 0; i < offsettableTable.size(); i++) { + if (offsettableTable.get(i).getItem() instanceof MethodIdItem) { + Offsettable offsettable = new Offsettable(item, true); + insertOffsettableAt(i, offsettable); + addFieldIdsToHeaderAndMapFile(rawDexFile, offsettable); + return offsettable; + } + } + Log.errorAndQuit("Could not find any MethodIdItems to insert the field before."); + return null; + } + + /** + * If we're creating a new Item (such as FieldId, MethodId) that is placed into the + * first position of the relevant ID table, then IdCreator has to call this method to + * ensure it gets put into the correct place in the offsettable table. + */ + public Offsettable insertNewOffsettableAsFirstOfType(RawDexObject item, + RawDexFile rawDexFile) { + Log.debug("Calling insertNewOffsettableAsFirstOfType()"); + int index = getOffsettableIndexForFirstItemType(item); + if (index == -1) { + Log.errorAndQuit("Could not find any object of class: " + item.getClass()); + } + Offsettable offsettable = new Offsettable(item, true); + insertOffsettableAt(index, offsettable); + updateOffsetsInHeaderAndMapFile(rawDexFile, offsettable); + return offsettable; + } + + /** + * IdCreator has to call this method when it creates a new IdItem, to make sure it + * gets put into the correct place in the offsettable table. IdCreator should + * provide the IdItem that should come before this new IdItem. + */ + public Offsettable insertNewOffsettableAfter(RawDexObject item, RawDexObject itemBefore) { + Log.debug("Calling insertNewOffsettableAfter()"); + int index = getOffsettableIndexForItem(itemBefore); + if (index == -1) { + Log.errorAndQuit("Did not find specified 'after' object in offsettable table."); + } + Offsettable offsettable = new Offsettable(item, true); + insertOffsettableAt(index + 1, offsettable); + return offsettable; + } + + private int getOffsettableIndexForFirstItemType(RawDexObject item) { + Class<?> itemClass = item.getClass(); + for (int i = 0; i < offsettableTable.size(); i++) { + if (offsettableTable.get(i).getItem().getClass().equals(itemClass)) { + return i; + } + } + return -1; + } + + private int getOffsettableIndexForItem(RawDexObject item) { + for (int i = 0; i < offsettableTable.size(); i++) { + if (offsettableTable.get(i).getItem() == item) { + return i; + } + } + return -1; + } + + /** + * Given a RawDexObject, get the Offsettable that contains it. + */ + public Offsettable getOffsettableForItem(RawDexObject item) { + for (int i = 0; i < offsettableTable.size(); i++) { + if (offsettableTable.get(i).getItem() == item) { + return offsettableTable.get(i); + } + } + return null; + } +} |