dalvik/vm/analysis/VerifySubs.c

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