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