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  * 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