Home | History | Annotate | Download | only in analysis
      1 /*
      2  * Copyright 2013, Google Inc.
      3  * All rights reserved.
      4  *
      5  * Redistribution and use in source and binary forms, with or without
      6  * modification, are permitted provided that the following conditions are
      7  * met:
      8  *
      9  *     * Redistributions of source code must retain the above copyright
     10  * notice, this list of conditions and the following disclaimer.
     11  *     * Redistributions in binary form must reproduce the above
     12  * copyright notice, this list of conditions and the following disclaimer
     13  * in the documentation and/or other materials provided with the
     14  * distribution.
     15  *     * Neither the name of Google Inc. nor the names of its
     16  * contributors may be used to endorse or promote products derived from
     17  * this software without specific prior written permission.
     18  *
     19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     20  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     21  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     22  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     23  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     26  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     27  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     28  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     29  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     30  */
     31 
     32 package org.jf.dexlib2.analysis;
     33 
     34 import com.google.common.base.Objects;
     35 import com.google.common.collect.Maps;
     36 import org.jf.dexlib2.iface.instruction.*;
     37 import org.jf.dexlib2.iface.reference.MethodReference;
     38 import org.jf.dexlib2.iface.reference.Reference;
     39 import org.jf.util.ExceptionWithContext;
     40 
     41 import javax.annotation.Nonnull;
     42 import javax.annotation.Nullable;
     43 import java.util.*;
     44 
     45 public class AnalyzedInstruction implements Comparable<AnalyzedInstruction> {
     46     /**
     47      * The actual instruction
     48      */
     49     protected Instruction instruction;
     50 
     51     /**
     52      * The index of the instruction, where the first instruction in the method is at index 0, and so on
     53      */
     54     protected final int instructionIndex;
     55 
     56     /**
     57      * Instructions that can pass on execution to this one during normal execution
     58      */
     59     protected final TreeSet<AnalyzedInstruction> predecessors = new TreeSet<AnalyzedInstruction>();
     60 
     61     /**
     62      * Instructions that can execution could pass on to next during normal execution
     63      */
     64     protected final LinkedList<AnalyzedInstruction> successors = new LinkedList<AnalyzedInstruction>();
     65 
     66     /**
     67      * This contains the register types *before* the instruction has executed
     68      */
     69     protected final RegisterType[] preRegisterMap;
     70 
     71     /**
     72      * This contains the register types *after* the instruction has executed
     73      */
     74     protected final RegisterType[] postRegisterMap;
     75 
     76     /**
     77      * This contains optional register type overrides for register types from predecessors
     78      */
     79     @Nullable
     80     protected Map<PredecessorOverrideKey, RegisterType> predecessorRegisterOverrides = null;
     81 
     82     /**
     83      * When deodexing, we might need to deodex this instruction multiple times, when we merge in new register
     84      * information. When this happens, we need to restore the original (odexed) instruction, so we can deodex it again
     85      */
     86     protected final Instruction originalInstruction;
     87 
     88     public AnalyzedInstruction(Instruction instruction, int instructionIndex, int registerCount) {
     89         this.instruction = instruction;
     90         this.originalInstruction = instruction;
     91         this.instructionIndex = instructionIndex;
     92         this.postRegisterMap = new RegisterType[registerCount];
     93         this.preRegisterMap = new RegisterType[registerCount];
     94         RegisterType unknown = RegisterType.getRegisterType(RegisterType.UNKNOWN, null);
     95         for (int i=0; i<registerCount; i++) {
     96             preRegisterMap[i] = unknown;
     97             postRegisterMap[i] = unknown;
     98         }
     99     }
    100 
    101     public int getInstructionIndex() {
    102         return instructionIndex;
    103     }
    104 
    105     public int getPredecessorCount() {
    106         return predecessors.size();
    107     }
    108 
    109     public SortedSet<AnalyzedInstruction> getPredecessors() {
    110         return Collections.unmodifiableSortedSet(predecessors);
    111     }
    112 
    113     public RegisterType getPredecessorRegisterType(@Nonnull AnalyzedInstruction predecessor, int registerNumber) {
    114         if (predecessorRegisterOverrides != null) {
    115             RegisterType override = predecessorRegisterOverrides.get(
    116                     new PredecessorOverrideKey(predecessor, registerNumber));
    117             if (override != null) {
    118                 return override;
    119             }
    120         }
    121         return predecessor.postRegisterMap[registerNumber];
    122     }
    123 
    124     protected boolean addPredecessor(AnalyzedInstruction predecessor) {
    125         return predecessors.add(predecessor);
    126     }
    127 
    128     protected void addSuccessor(AnalyzedInstruction successor) {
    129         successors.add(successor);
    130     }
    131 
    132     protected void setDeodexedInstruction(Instruction instruction) {
    133         assert originalInstruction.getOpcode().odexOnly();
    134         this.instruction = instruction;
    135     }
    136 
    137     protected void restoreOdexedInstruction() {
    138         assert originalInstruction.getOpcode().odexOnly();
    139         instruction = originalInstruction;
    140     }
    141 
    142     public int getSuccessorCount() {
    143         return successors.size();
    144     }
    145 
    146     public List<AnalyzedInstruction> getSuccesors() {
    147         return Collections.unmodifiableList(successors);
    148     }
    149 
    150     public Instruction getInstruction() {
    151         return instruction;
    152     }
    153 
    154     public Instruction getOriginalInstruction() {
    155         return originalInstruction;
    156     }
    157 
    158     /**
    159      * Is this instruction a "beginning instruction". A beginning instruction is defined to be an instruction
    160      * that can be the first successfully executed instruction in the method. The first instruction is always a
    161      * beginning instruction. If the first instruction can throw an exception, and is covered by a try block, then
    162      * the first instruction of any exception handler for that try block is also a beginning instruction. And likewise,
    163      * if any of those instructions can throw an exception and are covered by try blocks, the first instruction of the
    164      * corresponding exception handler is a beginning instruction, etc.
    165      *
    166      * To determine this, we simply check if the first predecessor is the fake "StartOfMethod" instruction, which has
    167      * an instruction index of -1.
    168      * @return a boolean value indicating whether this instruction is a beginning instruction
    169      */
    170     public boolean isBeginningInstruction() {
    171         //if this instruction has no predecessors, it is either the fake "StartOfMethod" instruction or it is an
    172         //unreachable instruction.
    173         if (predecessors.size() == 0) {
    174             return false;
    175         }
    176 
    177         if (predecessors.first().instructionIndex == -1) {
    178             return true;
    179         }
    180         return false;
    181     }
    182 
    183     /*
    184      * Merges the given register type into the specified pre-instruction register, and also sets the post-instruction
    185      * register type accordingly if it isn't a destination register for this instruction
    186      * @param registerNumber Which register to set
    187      * @param registerType The register type
    188      * @returns true If the post-instruction register type was changed. This might be false if either the specified
    189      * register is a destination register for this instruction, or if the pre-instruction register type didn't change
    190      * after merging in the given register type
    191      */
    192     protected boolean mergeRegister(int registerNumber, RegisterType registerType, BitSet verifiedInstructions,
    193                                     boolean override) {
    194         assert registerNumber >= 0 && registerNumber < postRegisterMap.length;
    195         assert registerType != null;
    196 
    197         RegisterType oldRegisterType = preRegisterMap[registerNumber];
    198 
    199         RegisterType mergedRegisterType;
    200         if (override) {
    201             mergedRegisterType = getMergedPreRegisterTypeFromPredecessors(registerNumber);
    202         } else {
    203             mergedRegisterType = oldRegisterType.merge(registerType);
    204         }
    205 
    206         if (mergedRegisterType.equals(oldRegisterType)) {
    207             return false;
    208         }
    209 
    210         preRegisterMap[registerNumber] = mergedRegisterType;
    211         verifiedInstructions.clear(instructionIndex);
    212 
    213         if (!setsRegister(registerNumber)) {
    214             postRegisterMap[registerNumber] = mergedRegisterType;
    215             return true;
    216         }
    217 
    218         return false;
    219     }
    220 
    221     /**
    222      * Iterates over the predecessors of this instruction, and merges all the post-instruction register types for the
    223      * given register. Any dead, unreachable, or odexed predecessor is ignored. This takes into account any overridden
    224      * predecessor register types
    225      *
    226      * @param registerNumber the register number
    227      * @return The register type resulting from merging the post-instruction register types from all predecessors
    228      */
    229     protected RegisterType getMergedPreRegisterTypeFromPredecessors(int registerNumber) {
    230         RegisterType mergedRegisterType = null;
    231         for (AnalyzedInstruction predecessor: predecessors) {
    232             RegisterType predecessorRegisterType = getPredecessorRegisterType(predecessor, registerNumber);
    233             if (predecessorRegisterType != null) {
    234                 if (mergedRegisterType == null) {
    235                     mergedRegisterType = predecessorRegisterType;
    236                 } else {
    237                     mergedRegisterType = predecessorRegisterType.merge(mergedRegisterType);
    238                 }
    239             }
    240         }
    241         return mergedRegisterType;
    242     }
    243     /**
    244      * Sets the "post-instruction" register type as indicated.
    245      * @param registerNumber Which register to set
    246      * @param registerType The "post-instruction" register type
    247      * @return true if the given register type is different than the existing post-instruction register type
    248      */
    249     protected boolean setPostRegisterType(int registerNumber, RegisterType registerType) {
    250         assert registerNumber >= 0 && registerNumber < postRegisterMap.length;
    251         assert registerType != null;
    252 
    253         RegisterType oldRegisterType = postRegisterMap[registerNumber];
    254         if (oldRegisterType.equals(registerType)) {
    255             return false;
    256         }
    257 
    258         postRegisterMap[registerNumber] = registerType;
    259         return true;
    260     }
    261 
    262     /**
    263      * Adds an override for a register type from a predecessor.
    264      *
    265      * This is used to set the register type for only one branch from a conditional jump.
    266      *
    267      * @param predecessor Which predecessor is being overriden
    268      * @param registerNumber The register number of the register being overriden
    269      * @param registerType The overridden register type
    270      * @param verifiedInstructions
    271      *
    272      * @return true if the post-instruction register type for this instruction changed as a result of this override
    273      */
    274     protected boolean overridePredecessorRegisterType(@Nonnull AnalyzedInstruction predecessor, int registerNumber,
    275                                                       @Nonnull RegisterType registerType, BitSet verifiedInstructions) {
    276         if (predecessorRegisterOverrides == null) {
    277             predecessorRegisterOverrides = Maps.newHashMap();
    278         }
    279         predecessorRegisterOverrides.put(new PredecessorOverrideKey(predecessor, registerNumber), registerType);
    280 
    281         RegisterType mergedType = getMergedPreRegisterTypeFromPredecessors(registerNumber);
    282 
    283         if (preRegisterMap[registerNumber].equals(mergedType)) {
    284             return false;
    285         }
    286 
    287         preRegisterMap[registerNumber] = mergedType;
    288         verifiedInstructions.clear(instructionIndex);
    289 
    290         if (!setsRegister(registerNumber)) {
    291             if (!postRegisterMap[registerNumber].equals(mergedType)) {
    292                 postRegisterMap[registerNumber] = mergedType;
    293                 return true;
    294             }
    295         }
    296 
    297         return false;
    298     }
    299 
    300     protected boolean isInvokeInit() {
    301         if (instruction == null || !instruction.getOpcode().canInitializeReference()) {
    302             return false;
    303         }
    304 
    305         ReferenceInstruction instruction = (ReferenceInstruction)this.instruction;
    306 
    307         Reference reference = instruction.getReference();
    308         if (reference instanceof MethodReference) {
    309             return ((MethodReference)reference).getName().equals("<init>");
    310         }
    311 
    312         return false;
    313     }
    314 
    315     public boolean setsRegister() {
    316         return instruction.getOpcode().setsRegister();
    317     }
    318 
    319     public boolean setsWideRegister() {
    320         return instruction.getOpcode().setsWideRegister();
    321     }
    322 
    323     public boolean setsRegister(int registerNumber) {
    324         //When constructing a new object, the register type will be an uninitialized reference after the new-instance
    325         //instruction, but becomes an initialized reference once the <init> method is called. So even though invoke
    326         //instructions don't normally change any registers, calling an <init> method will change the type of its
    327         //object register. If the uninitialized reference has been copied to other registers, they will be initialized
    328         //as well, so we need to check for that too
    329         if (isInvokeInit()) {
    330             int destinationRegister;
    331             if (instruction instanceof FiveRegisterInstruction) {
    332                 destinationRegister = ((FiveRegisterInstruction)instruction).getRegisterC();
    333             } else {
    334                 assert instruction instanceof RegisterRangeInstruction;
    335                 RegisterRangeInstruction rangeInstruction = (RegisterRangeInstruction)instruction;
    336                 assert rangeInstruction.getRegisterCount() > 0;
    337                 destinationRegister = rangeInstruction.getStartRegister();
    338             }
    339 
    340             if (registerNumber == destinationRegister) {
    341                 return true;
    342             }
    343             RegisterType preInstructionDestRegisterType = getPreInstructionRegisterType(registerNumber);
    344             if (preInstructionDestRegisterType.category != RegisterType.UNINIT_REF &&
    345                 preInstructionDestRegisterType.category != RegisterType.UNINIT_THIS) {
    346 
    347                 return false;
    348             }
    349             //check if the uninit ref has been copied to another register
    350             if (getPreInstructionRegisterType(registerNumber).equals(preInstructionDestRegisterType)) {
    351                 return true;
    352             }
    353             return false;
    354         }
    355 
    356         if (!setsRegister()) {
    357             return false;
    358         }
    359         int destinationRegister = getDestinationRegister();
    360 
    361         if (registerNumber == destinationRegister) {
    362             return true;
    363         }
    364         if (setsWideRegister() && registerNumber == (destinationRegister + 1)) {
    365             return true;
    366         }
    367         return false;
    368     }
    369 
    370     public int getDestinationRegister() {
    371         if (!this.instruction.getOpcode().setsRegister()) {
    372             throw new ExceptionWithContext("Cannot call getDestinationRegister() for an instruction that doesn't " +
    373                     "store a value");
    374         }
    375         return ((OneRegisterInstruction)instruction).getRegisterA();
    376     }
    377 
    378     public int getRegisterCount() {
    379         return postRegisterMap.length;
    380     }
    381 
    382     @Nonnull
    383     public RegisterType getPostInstructionRegisterType(int registerNumber) {
    384         return postRegisterMap[registerNumber];
    385     }
    386 
    387     @Nonnull
    388     public RegisterType getPreInstructionRegisterType(int registerNumber) {
    389         return preRegisterMap[registerNumber];
    390     }
    391 
    392     public int compareTo(AnalyzedInstruction analyzedInstruction) {
    393         if (instructionIndex < analyzedInstruction.instructionIndex) {
    394             return -1;
    395         } else if (instructionIndex == analyzedInstruction.instructionIndex) {
    396             return 0;
    397         } else {
    398             return 1;
    399         }
    400     }
    401 
    402     private static class PredecessorOverrideKey {
    403         public final AnalyzedInstruction analyzedInstruction;
    404         public final int registerNumber;
    405 
    406         public PredecessorOverrideKey(AnalyzedInstruction analyzedInstruction, int registerNumber) {
    407             this.analyzedInstruction = analyzedInstruction;
    408             this.registerNumber = registerNumber;
    409         }
    410 
    411         @Override public boolean equals(Object o) {
    412             if (this == o) return true;
    413             if (o == null || getClass() != o.getClass()) return false;
    414             PredecessorOverrideKey that = (PredecessorOverrideKey)o;
    415             return com.google.common.base.Objects.equal(registerNumber, that.registerNumber) &&
    416                     Objects.equal(analyzedInstruction, that.analyzedInstruction);
    417         }
    418 
    419         @Override public int hashCode() {
    420             return Objects.hashCode(analyzedInstruction, registerNumber);
    421         }
    422     }
    423 }
    424 
    425