Home | History | Annotate | Download | only in analysis 
      1 /*
      2  * Copyright (C) 2008 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 /*
     18  * Dalvik verification subroutines.
     19  */
     20 #include "Dalvik.h"
     21 #include "analysis/CodeVerify.h"
     22 #include "libdex/DexCatch.h"
     23 #include "libdex/InstrUtils.h"
     24 
     25 
     26 /*
     27  * Compute the width of the instruction at each address in the instruction
     28  * stream.  Addresses that are in the middle of an instruction, or that
     29  * are part of switch table data, are not set (so the caller should probably
     30  * initialize "insnFlags" to zero).
     31  *
     32  * If "pNewInstanceCount" is not NULL, it will be set to the number of
     33  * new-instance instructions in the method.
     34  *
     35  * Logs an error and returns "false" on failure.
     36  */
     37 bool dvmComputeCodeWidths(const Method* meth, InsnFlags* insnFlags,
     38     int* pNewInstanceCount)
     39 {
     40     const int insnCount = dvmGetMethodInsnsSize(meth);
     41     const u2* insns = meth->insns;
     42     bool result = false;
     43     int newInstanceCount = 0;
     44     int i;
     45 
     46 
     47     for (i = 0; i < insnCount; /**/) {
     48         int width;
     49 
     50         /*
     51          * Switch tables and array data tables are identified with
     52          * "extended NOP" opcodes.  They contain no executable code,
     53          * so we can just skip past them.
     54          */
     55         if (*insns == kPackedSwitchSignature) {
     56             width = 4 + insns[1] * 2;
     57         } else if (*insns == kSparseSwitchSignature) {
     58             width = 2 + insns[1] * 4;
     59         } else if (*insns == kArrayDataSignature) {
     60             u4 size = insns[2] | (((u4)insns[3]) << 16);
     61             width = 4 + (insns[1] * size + 1) / 2;
     62         } else {
     63             int instr = *insns & 0xff;
     64             width = dexGetInstrWidthAbs(gDvm.instrWidth, instr);
     65             if (width == 0) {
     66                 LOG_VFY_METH(meth,
     67                     "VFY: invalid post-opt instruction (0x%x)\n", instr);
     68                 LOGI("### instr=%d width=%d table=%d\n",
     69                     instr, width, dexGetInstrWidthAbs(gDvm.instrWidth, instr));
     70                 goto bail;
     71             }
     72             if (width < 0 || width > 5) {
     73                 LOGE("VFY: bizarre width value %d\n", width);
     74                 dvmAbort();
     75             }
     76 
     77             if (instr == OP_NEW_INSTANCE)
     78                 newInstanceCount++;
     79         }
     80 
     81         if (width > 65535) {
     82             LOG_VFY_METH(meth, "VFY: insane width %d\n", width);
     83             goto bail;
     84         }
     85 
     86         insnFlags[i] |= width;
     87         i += width;
     88         insns += width;
     89     }
     90     if (i != (int) dvmGetMethodInsnsSize(meth)) {
     91         LOG_VFY_METH(meth, "VFY: code did not end where expected (%d vs. %d)\n",
     92             i, dvmGetMethodInsnsSize(meth));
     93         goto bail;
     94     }
     95 
     96     result = true;
     97     if (pNewInstanceCount != NULL)
     98         *pNewInstanceCount = newInstanceCount;
     99 
    100 bail:
    101     return result;
    102 }
    103 
    104 /*
    105  * Set the "in try" flags for all instructions protected by "try" statements.
    106  * Also sets the "branch target" flags for exception handlers.
    107  *
    108  * Call this after widths have been set in "insnFlags".
    109  *
    110  * Returns "false" if something in the exception table looks fishy, but
    111  * we're expecting the exception table to be somewhat sane.
    112  */
    113 bool dvmSetTryFlags(const Method* meth, InsnFlags* insnFlags)
    114 {
    115     u4 insnsSize = dvmGetMethodInsnsSize(meth);
    116     DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile;
    117     const DexCode* pCode = dvmGetMethodCode(meth);
    118     u4 triesSize = pCode->triesSize;
    119     const DexTry* pTries;
    120     u4 handlersSize;
    121     u4 offset;
    122     u4 i;
    123 
    124     if (triesSize == 0) {
    125         return true;
    126     }
    127 
    128     pTries = dexGetTries(pCode);
    129     handlersSize = dexGetHandlersSize(pCode);
    130 
    131     for (i = 0; i < triesSize; i++) {
    132         const DexTry* pTry = &pTries[i];
    133         u4 start = pTry->startAddr;
    134         u4 end = start + pTry->insnCount;
    135         u4 addr;
    136 
    137         if ((start >= end) || (start >= insnsSize) || (end > insnsSize)) {
    138             LOG_VFY_METH(meth,
    139                 "VFY: bad exception entry: startAddr=%d endAddr=%d (size=%d)\n",
    140                 start, end, insnsSize);
    141             return false;
    142         }
    143 
    144         if (dvmInsnGetWidth(insnFlags, start) == 0) {
    145             LOG_VFY_METH(meth,
    146                 "VFY: 'try' block starts inside an instruction (%d)\n",
    147                 start);
    148             return false;
    149         }
    150 
    151         for (addr = start; addr < end;
    152             addr += dvmInsnGetWidth(insnFlags, addr))
    153         {
    154             assert(dvmInsnGetWidth(insnFlags, addr) != 0);
    155             dvmInsnSetInTry(insnFlags, addr, true);
    156         }
    157     }
    158 
    159     /* Iterate over each of the handlers to verify target addresses. */
    160     offset = dexGetFirstHandlerOffset(pCode);
    161     for (i = 0; i < handlersSize; i++) {
    162         DexCatchIterator iterator;
    163         dexCatchIteratorInit(&iterator, pCode, offset);
    164 
    165         for (;;) {
    166             DexCatchHandler* handler = dexCatchIteratorNext(&iterator);
    167             u4 addr;
    168 
    169             if (handler == NULL) {
    170                 break;
    171             }
    172 
    173             addr = handler->address;
    174             if (dvmInsnGetWidth(insnFlags, addr) == 0) {
    175                 LOG_VFY_METH(meth,
    176                     "VFY: exception handler starts at bad address (%d)\n",
    177                     addr);
    178                 return false;
    179             }
    180 
    181             dvmInsnSetBranchTarget(insnFlags, addr, true);
    182         }
    183 
    184         offset = dexCatchIteratorGetEndOffset(&iterator, pCode);
    185     }
    186 
    187     return true;
    188 }
    189 
    190 /*
    191  * Verify a switch table.  "curOffset" is the offset of the switch
    192  * instruction.
    193  */
    194 bool dvmCheckSwitchTargets(const Method* meth, InsnFlags* insnFlags,
    195     int curOffset)
    196 {
    197     const int insnCount = dvmGetMethodInsnsSize(meth);
    198     const u2* insns = meth->insns + curOffset;
    199     const u2* switchInsns;
    200     u2 expectedSignature;
    201     int switchCount, tableSize;
    202     int offsetToSwitch, offsetToKeys, offsetToTargets, targ;
    203     int offset, absOffset;
    204 
    205     assert(curOffset >= 0 && curOffset < insnCount);
    206 
    207     /* make sure the start of the switch is in range */
    208     offsetToSwitch = (s2) insns[1];
    209     if (curOffset + offsetToSwitch < 0 ||
    210         curOffset + offsetToSwitch + 2 >= insnCount)
    211     {
    212         LOG_VFY_METH(meth,
    213             "VFY: invalid switch start: at %d, switch offset %d, count %d\n",
    214             curOffset, offsetToSwitch, insnCount);
    215         return false;
    216     }
    217 
    218     /* offset to switch table is a relative branch-style offset */
    219     switchInsns = insns + offsetToSwitch;
    220 
    221     /* make sure the table is 32-bit aligned */
    222     if ((((u4) switchInsns) & 0x03) != 0) {
    223         LOG_VFY_METH(meth,
    224             "VFY: unaligned switch table: at %d, switch offset %d\n",
    225             curOffset, offsetToSwitch);
    226         return false;
    227     }
    228 
    229     switchCount = switchInsns[1];
    230 
    231     if ((*insns & 0xff) == OP_PACKED_SWITCH) {
    232         /* 0=sig, 1=count, 2/3=firstKey */
    233         offsetToTargets = 4;
    234         offsetToKeys = -1;
    235         expectedSignature = kPackedSwitchSignature;
    236     } else {
    237         /* 0=sig, 1=count, 2..count*2 = keys */
    238         offsetToKeys = 2;
    239         offsetToTargets = 2 + 2*switchCount;
    240         expectedSignature = kSparseSwitchSignature;
    241     }
    242     tableSize = offsetToTargets + switchCount*2;
    243 
    244     if (switchInsns[0] != expectedSignature) {
    245         LOG_VFY_METH(meth,
    246             "VFY: wrong signature for switch table (0x%04x, wanted 0x%04x)\n",
    247             switchInsns[0], expectedSignature);
    248         return false;
    249     }
    250 
    251     /* make sure the end of the switch is in range */
    252     if (curOffset + offsetToSwitch + tableSize > insnCount) {
    253         LOG_VFY_METH(meth,
    254             "VFY: invalid switch end: at %d, switch offset %d, end %d, count %d\n",
    255             curOffset, offsetToSwitch, curOffset + offsetToSwitch + tableSize,
    256             insnCount);
    257         return false;
    258     }
    259 
    260     /* for a sparse switch, verify the keys are in ascending order */
    261     if (offsetToKeys > 0 && switchCount > 1) {
    262         s4 lastKey;
    263 
    264         lastKey = switchInsns[offsetToKeys] |
    265                   (switchInsns[offsetToKeys+1] << 16);
    266         for (targ = 1; targ < switchCount; targ++) {
    267             s4 key = (s4) switchInsns[offsetToKeys + targ*2] |
    268                     (s4) (switchInsns[offsetToKeys + targ*2 +1] << 16);
    269             if (key <= lastKey) {
    270                 LOG_VFY_METH(meth,
    271                     "VFY: invalid packed switch: last key=%d, this=%d\n",
    272                     lastKey, key);
    273                 return false;
    274             }
    275 
    276             lastKey = key;
    277         }
    278     }
    279 
    280     /* verify each switch target */
    281     for (targ = 0; targ < switchCount; targ++) {
    282         offset = (s4) switchInsns[offsetToTargets + targ*2] |
    283                 (s4) (switchInsns[offsetToTargets + targ*2 +1] << 16);
    284         absOffset = curOffset + offset;
    285 
    286         if (absOffset < 0 || absOffset >= insnCount ||
    287             !dvmInsnIsOpcode(insnFlags, absOffset))
    288         {
    289             LOG_VFY_METH(meth,
    290                 "VFY: invalid switch target %d (-> 0x%x) at 0x%x[%d]\n",
    291                 offset, absOffset, curOffset, targ);
    292             return false;
    293         }
    294         dvmInsnSetBranchTarget(insnFlags, absOffset, true);
    295     }
    296 
    297     return true;
    298 }
    299 
    300 /*
    301  * Verify that the target of a branch instruction is valid.
    302  *
    303  * We don't expect code to jump directly into an exception handler, but
    304  * it's valid to do so as long as the target isn't a "move-exception"
    305  * instruction.  We verify that in a later stage.
    306  *
    307  * The VM spec doesn't forbid an instruction from branching to itself,
    308  * but the Dalvik spec declares that only certain instructions can do so.
    309  */
    310 bool dvmCheckBranchTarget(const Method* meth, InsnFlags* insnFlags,
    311     int curOffset, bool selfOkay)
    312 {
    313     const int insnCount = dvmGetMethodInsnsSize(meth);
    314     const u2* insns = meth->insns + curOffset;
    315     int offset, absOffset;
    316     bool isConditional;
    317 
    318     if (!dvmGetBranchTarget(meth, insnFlags, curOffset, &offset,
    319             &isConditional))
    320         return false;
    321 
    322     if (!selfOkay && offset == 0) {
    323         LOG_VFY_METH(meth, "VFY: branch offset of zero not allowed at 0x%x\n",
    324             curOffset);
    325         return false;
    326     }
    327 
    328     /*
    329      * Check for 32-bit overflow.  This isn't strictly necessary if we can
    330      * depend on the VM to have identical "wrap-around" behavior, but
    331      * it's unwise to depend on that.
    332      */
    333     if (((s8) curOffset + (s8) offset) != (s8)(curOffset + offset)) {
    334         LOG_VFY_METH(meth, "VFY: branch target overflow 0x%x +%d\n",
    335             curOffset, offset);
    336         return false;
    337     }
    338     absOffset = curOffset + offset;
    339     if (absOffset < 0 || absOffset >= insnCount ||
    340         !dvmInsnIsOpcode(insnFlags, absOffset))
    341     {
    342         LOG_VFY_METH(meth,
    343             "VFY: invalid branch target %d (-> 0x%x) at 0x%x\n",
    344             offset, absOffset, curOffset);
    345         return false;
    346     }
    347     dvmInsnSetBranchTarget(insnFlags, absOffset, true);
    348 
    349     return true;
    350 }
    351 
    352 
    353 /*
    354  * Output a code verifier warning message.  For the pre-verifier it's not
    355  * a big deal if something fails (and it may even be expected), but if
    356  * we're doing just-in-time verification it's significant.
    357  */
    358 void dvmLogVerifyFailure(const Method* meth, const char* format, ...)
    359 {
    360     va_list ap;
    361     int logLevel;
    362 
    363     if (gDvm.optimizing) {
    364         return;
    365         //logLevel = ANDROID_LOG_DEBUG;
    366     } else {
    367         logLevel = ANDROID_LOG_WARN;
    368     }
    369 
    370     va_start(ap, format);
    371     LOG_PRI_VA(logLevel, LOG_TAG, format, ap);
    372     if (meth != NULL) {
    373         char* desc = dexProtoCopyMethodDescriptor(&meth->prototype);
    374         LOG_PRI(logLevel, LOG_TAG, "VFY:  rejected %s.%s %s\n",
    375             meth->clazz->descriptor, meth->name, desc);
    376         free(desc);
    377     }
    378 }
    379 
    380 /*
    381  * Show a relatively human-readable message describing the failure to
    382  * resolve a class.
    383  *
    384  * TODO: this is somewhat misleading when resolution fails because of
    385  * illegal access rather than nonexistent class.
    386  */
    387 void dvmLogUnableToResolveClass(const char* missingClassDescr,
    388     const Method* meth)
    389 {
    390     if (gDvm.optimizing)
    391         return;
    392 
    393     char* dotMissingClass = dvmDescriptorToDot(missingClassDescr);
    394     char* dotFromClass = dvmDescriptorToDot(meth->clazz->descriptor);
    395     //char* methodDescr = dexProtoCopyMethodDescriptor(&meth->prototype);
    396 
    397     LOGE("Could not find class '%s', referenced from method %s.%s\n",
    398         dotMissingClass, dotFromClass, meth->name/*, methodDescr*/);
    399 
    400     free(dotMissingClass);
    401     free(dotFromClass);
    402     //free(methodDescr);
    403 }
    404 
    405 /*
    406  * Extract the relative offset from a branch instruction.
    407  *
    408  * Returns "false" on failure (e.g. this isn't a branch instruction).
    409  */
    410 bool dvmGetBranchTarget(const Method* meth, InsnFlags* insnFlags,
    411     int curOffset, int* pOffset, bool* pConditional)
    412 {
    413     const u2* insns = meth->insns + curOffset;
    414     int tmp;
    415 
    416     switch (*insns & 0xff) {
    417     case OP_GOTO:
    418         *pOffset = ((s2) *insns) >> 8;
    419         *pConditional = false;
    420         break;
    421     case OP_GOTO_32:
    422         *pOffset = insns[1] | (((u4) insns[2]) << 16);
    423         *pConditional = false;
    424         break;
    425     case OP_GOTO_16:
    426         *pOffset = (s2) insns[1];
    427         *pConditional = false;
    428         break;
    429     case OP_IF_EQ:
    430     case OP_IF_NE:
    431     case OP_IF_LT:
    432     case OP_IF_GE:
    433     case OP_IF_GT:
    434     case OP_IF_LE:
    435     case OP_IF_EQZ:
    436     case OP_IF_NEZ:
    437     case OP_IF_LTZ:
    438     case OP_IF_GEZ:
    439     case OP_IF_GTZ:
    440     case OP_IF_LEZ:
    441         *pOffset = (s2) insns[1];
    442         *pConditional = true;
    443         break;
    444     default:
    445         return false;
    446         break;
    447     }
    448 
    449     return true;
    450 }
    451 
    452 /*
    453  * Given a 32-bit constant, return the most-restricted RegType enum entry
    454  * that can hold the value.
    455  */
    456 char dvmDetermineCat1Const(s4 value)
    457 {
    458     if (value < -32768)
    459         return kRegTypeInteger;
    460     else if (value < -128)
    461         return kRegTypeShort;
    462     else if (value < 0)
    463         return kRegTypeByte;
    464     else if (value == 0)
    465         return kRegTypeZero;
    466     else if (value == 1)
    467         return kRegTypeOne;
    468     else if (value < 128)
    469         return kRegTypePosByte;
    470     else if (value < 32768)
    471         return kRegTypePosShort;
    472     else if (value < 65536)
    473         return kRegTypeChar;
    474     else
    475         return kRegTypeInteger;
    476 }
    477 
    478