libdex/DexSwapVerify.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  * Byte-swapping and verification of dex files.
  19  */
  20
  21 #include "DexFile.h"
  22 #include "DexClass.h"
  23 #include "DexDataMap.h"
  24 #include "DexProto.h"
  25 #include "Leb128.h"
  26
  27 #include <safe_iop.h>
  28 #include <zlib.h>
  29
  30 #include <stdlib.h>
  31 #include <string.h>
  32
  33 #ifndef __BYTE_ORDER
  34 # error "byte ordering not defined"
  35 #endif
  36
  37 #if __BYTE_ORDER == __LITTLE_ENDIAN
  38 # define SWAP2(_value)      (_value)
  39 # define SWAP4(_value)      (_value)
  40 # define SWAP8(_value)      (_value)
  41 #else
  42 # define SWAP2(_value)      endianSwapU2((_value))
  43 # define SWAP4(_value)      endianSwapU4((_value))
  44 # define SWAP8(_value)      endianSwapU8((_value))
  45 static u2 endianSwapU2(u2 value) {
  46     return (value >> 8) | (value << 8);
  47 }
  48 static u4 endianSwapU4(u4 value) {
  49     /* ABCD --> CDAB --> DCBA */
  50     value = (value >> 16) | (value << 16);
  51     return ((value & 0xff00ff00) >> 8) | ((value << 8) & 0xff00ff00);
  52 }
  53 static u8 endianSwapU8(u8 value) {
  54     /* ABCDEFGH --> EFGHABCD --> GHEFCDAB --> HGFEDCBA */
  55     value = (value >> 32) | (value << 32);
  56     value = ((value & 0xffff0000ffff0000ULL) >> 16) |
  57             ((value << 16) & 0xffff0000ffff0000ULL);
  58     return ((value & 0xff00ff00ff00ff00ULL) >> 8) |
  59            ((value << 8) & 0xff00ff00ff00ff00ULL);
  60 }
  61 #endif
  62
  63 #define SWAP_FIELD2(_field) (_field) = SWAP2(_field)
  64 #define SWAP_FIELD4(_field) (_field) = SWAP4(_field)
  65 #define SWAP_FIELD8(_field) (_field) = SWAP8(_field)
  66
  67 /*
  68  * Some information we pass around to help verify values.
  69  */
  70 typedef struct CheckState {
  71     const DexHeader*  pHeader;
  72     const u1*         fileStart;
  73     const u1*         fileEnd;      // points to fileStart + fileLen
  74     u4                fileLen;
  75     DexDataMap*       pDataMap;     // set after map verification
  76     const DexFile*    pDexFile;     // set after intraitem verification
  77
  78     /*
  79      * bitmap of type_id indices that have been used to define classes;
  80      * initialized immediately before class_def cross-verification, and
  81      * freed immediately after it
  82      */
  83     u4*               pDefinedClassBits;
  84
  85     const void*       previousItem; // set during section iteration
  86 } CheckState;
  87
  88 /*
  89  * Return the file offset of the given pointer.
  90  */
  91 static inline u4 fileOffset(const CheckState* state, const void* ptr) {
  92     return ((const u1*) ptr) - state->fileStart;
  93 }
  94
  95 /*
  96  * Return a pointer for the given file offset.
  97  */
  98 static inline void* filePointer(const CheckState* state, u4 offset) {
  99     return (void*) (state->fileStart + offset);
 100 }
 101
 102 /*
 103  * Verify that a pointer range, start inclusive to end exclusive, only
 104  * covers bytes in the file and doesn't point beyond the end of the
 105  * file. That is, the start must indicate a valid byte or may point at
 106  * the byte just past the end of the file (but no further), and the
 107  * end must be no less than the start and must also not point beyond
 108  * the byte just past the end of the file.
 109  */
 110 static inline bool checkPtrRange(const CheckState* state,
 111         const void* start, const void* end, const char* label) {
 112     const void* fileStart = state->fileStart;
 113     const void* fileEnd = state->fileEnd;
 114     if ((start < fileStart) || (start > fileEnd)
 115             || (end < start) || (end > fileEnd)) {
 116         LOGW("Bad offset range for %s: 0x%x..0x%x\n", label,
 117                 fileOffset(state, start), fileOffset(state, end));
 118         return false;
 119     }
 120     return true;
 121 }
 122
 123 /*
 124  * Verify that a range of offsets, start inclusive to end exclusive,
 125  * are all valid. That is, the start must indicate a valid byte or may
 126  * point at the byte just past the end of the file (but no further),
 127  * and the end must be no less than the start and must also not point
 128  * beyond the byte just past the end of the file.
 129  *
 130  * Assumes "const CheckState* state".
 131  */
 132 #define CHECK_OFFSET_RANGE(_start, _end) {                                  \
 133         const u1* _startPtr = filePointer(state, (_start));                 \
 134         const u1* _endPtr = filePointer(state, (_end));                     \
 135         if (!checkPtrRange(state, _startPtr, _endPtr,                       \
 136                         #_start ".." #_end)) {                              \
 137             return 0;                                                       \
 138         }                                                                   \
 139     }
 140
 141 /*
 142  * Verify that a pointer range, start inclusive to end exclusive, only
 143  * covers bytes in the file and doesn't point beyond the end of the
 144  * file. That is, the start must indicate a valid byte or may point at
 145  * the byte just past the end of the file (but no further), and the
 146  * end must be no less than the start and must also not point beyond
 147  * the byte just past the end of the file.
 148  *
 149  * Assumes "const CheckState* state".
 150  */
 151 #define CHECK_PTR_RANGE(_start, _end) {                                     \
 152         if (!checkPtrRange(state, (_start), (_end), #_start ".." #_end)) {  \
 153             return 0;                                                       \
 154         }                                                                   \
 155     }
 156
 157 /*
 158  * Make sure a list of items fits entirely within the file.
 159  *
 160  * Assumes "const CheckState* state" and "typeof(_count) == typeof(_elemSize)"
 161  * If the type sizes or signs are mismatched, this will return 0.
 162  */
 163 #define CHECK_LIST_SIZE(_ptr, _count, _elemSize) {                          \
 164         const u1* _start = (const u1*) (_ptr);                              \
 165         const u1* _end = _start + ((_count) * (_elemSize));                 \
 166         if (!safe_mul(NULL, (_count), (_elemSize)) ||                       \
 167             !checkPtrRange(state, _start, _end, #_ptr)) {                   \
 168             return 0;                                                       \
 169         }                                                                   \
 170     }
 171
 172 /*
 173  * Swap a field that is known to hold an absolute DEX file offset. Note:
 174  * This does not check to see that the swapped offset points within the
 175  * mapped file, since that should be handled (with even more rigor) by
 176  * the cross-verification phase.
 177  *
 178  * Assumes "const CheckState* state".
 179  */
 180 #define SWAP_OFFSET4(_field) {                                              \
 181         SWAP_FIELD4((_field));                                              \
 182     }
 183
 184 /*
 185  * Verify that an index falls in a valid range.
 186  */
 187 #define CHECK_INDEX(_field, _limit) {                                       \
 188         if ((_field) >= (_limit)) {                                         \
 189             LOGW("Bad index: %s(%u) > %s(%u)\n",                            \
 190                 #_field, (u4)(_field), #_limit, (u4)(_limit));              \
 191             return 0;                                                       \
 192         }                                                                   \
 193     }
 194
 195 /*
 196  * Swap an index, and verify that it falls in a valid range.
 197  */
 198 #define SWAP_INDEX2(_field, _limit) {                                       \
 199         SWAP_FIELD2((_field));                                              \
 200         CHECK_INDEX((_field), (_limit));                                    \
 201     }
 202
 203 /*
 204  * Verify that an index falls in a valid range or is kDexNoIndex.
 205  */
 206 #define CHECK_INDEX_OR_NOINDEX(_field, _limit) {                            \
 207         if ((_field) != kDexNoIndex && (_field) >= (_limit)) {              \
 208             LOGW("Bad index: %s(%u) > %s(%u)\n",                            \
 209                 #_field, (u4)(_field), #_limit, (u4)(_limit));              \
 210             return 0;                                                       \
 211         }                                                                   \
 212     }
 213
 214 /*
 215  * Swap an index, and verify that it falls in a valid range.
 216  */
 217 #define SWAP_INDEX4(_field, _limit) {                                       \
 218         SWAP_FIELD4((_field));                                              \
 219         CHECK_INDEX((_field), (_limit));                                    \
 220     }
 221
 222 /*
 223  * Swap an index, and verify that it falls in a valid range or is
 224  * kDexNoIndex.
 225  */
 226 #define SWAP_INDEX4_OR_NOINDEX(_field, _limit) {                            \
 227         SWAP_FIELD4((_field));                                              \
 228         CHECK_INDEX_OR_NOINDEX((_field), (_limit));                         \
 229     }
 230
 231 /* Verify the definer of a given field_idx. */
 232 static bool verifyFieldDefiner(const CheckState* state, u4 definingClass,
 233         u4 fieldIdx) {
 234     const DexFieldId* field = dexGetFieldId(state->pDexFile, fieldIdx);
 235     return field->classIdx == definingClass;
 236 }
 237
 238 /* Verify the definer of a given method_idx. */
 239 static bool verifyMethodDefiner(const CheckState* state, u4 definingClass,
 240         u4 methodIdx) {
 241     const DexMethodId* meth = dexGetMethodId(state->pDexFile, methodIdx);
 242     return meth->classIdx == definingClass;
 243 }
 244
 245 /*
 246  * Calculate the required size (in elements) of the array pointed at by
 247  * pDefinedClassBits.
 248  */
 249 static size_t calcDefinedClassBitsSize(const CheckState* state)
 250 {
 251     // Divide typeIdsSize by 32 (0x20), rounding up.
 252     return (state->pHeader->typeIdsSize + 0x1f) >> 5;
 253 }
 254
 255 /*
 256  * Set the given bit in pDefinedClassBits, returning its former value.
 257  */
 258 static bool setDefinedClassBit(const CheckState* state, u4 typeIdx) {
 259     u4 arrayIdx = typeIdx >> 5;
 260     u4 bit = 1 << (typeIdx & 0x1f);
 261     u4* element = &state->pDefinedClassBits[arrayIdx];
 262     bool result = (*element & bit) != 0;
 263
 264     *element |= bit;
 265
 266     return result;
 267 }
 268
 269 /*
 270  * Swap the header_item.
 271  */
 272 static bool swapDexHeader(const CheckState* state, DexHeader* pHeader)
 273 {
 274     CHECK_PTR_RANGE(pHeader, pHeader + 1);
 275
 276     // magic is ok
 277     SWAP_FIELD4(pHeader->checksum);
 278     // signature is ok
 279     SWAP_FIELD4(pHeader->fileSize);
 280     SWAP_FIELD4(pHeader->headerSize);
 281     SWAP_FIELD4(pHeader->endianTag);
 282     SWAP_FIELD4(pHeader->linkSize);
 283     SWAP_OFFSET4(pHeader->linkOff);
 284     SWAP_OFFSET4(pHeader->mapOff);
 285     SWAP_FIELD4(pHeader->stringIdsSize);
 286     SWAP_OFFSET4(pHeader->stringIdsOff);
 287     SWAP_FIELD4(pHeader->typeIdsSize);
 288     SWAP_OFFSET4(pHeader->typeIdsOff);
 289     SWAP_FIELD4(pHeader->fieldIdsSize);
 290     SWAP_OFFSET4(pHeader->fieldIdsOff);
 291     SWAP_FIELD4(pHeader->methodIdsSize);
 292     SWAP_OFFSET4(pHeader->methodIdsOff);
 293     SWAP_FIELD4(pHeader->protoIdsSize);
 294     SWAP_OFFSET4(pHeader->protoIdsOff);
 295     SWAP_FIELD4(pHeader->classDefsSize);
 296     SWAP_OFFSET4(pHeader->classDefsOff);
 297     SWAP_FIELD4(pHeader->dataSize);
 298     SWAP_OFFSET4(pHeader->dataOff);
 299
 300     if (pHeader->endianTag != kDexEndianConstant) {
 301         LOGE("Unexpected endian_tag: 0x%x\n", pHeader->endianTag);
 302         return false;
 303     }
 304
 305     // Assign variables so the diagnostic is prettier. (Hooray for macros.)
 306     u4 linkOff = pHeader->linkOff;
 307     u4 linkEnd = linkOff + pHeader->linkSize;
 308     u4 dataOff = pHeader->dataOff;
 309     u4 dataEnd = dataOff + pHeader->dataSize;
 310     CHECK_OFFSET_RANGE(linkOff, linkEnd);
 311     CHECK_OFFSET_RANGE(dataOff, dataEnd);
 312
 313     /*
 314      * Note: The offsets and ranges of the other header items end up getting
 315      * checked during the first iteration over the map.
 316      */
 317
 318     return true;
 319 }
 320
 321 /* Check the header section for sanity. */
 322 static bool checkHeaderSection(const CheckState* state, u4 sectionOffset,
 323         u4 sectionCount, u4* endOffset) {
 324     if (sectionCount != 1) {
 325         LOGE("Multiple header items\n");
 326         return false;
 327     }
 328
 329     if (sectionOffset != 0) {
 330         LOGE("Header at 0x%x; not at start of file\n", sectionOffset);
 331         return false;
 332     }
 333
 334     const DexHeader* pHeader = filePointer(state, 0);
 335     *endOffset = pHeader->headerSize;
 336     return true;
 337 }
 338
 339 /*
 340  * Helper for swapMap(), which turns a map type constant into a small
 341  * one-bit-on integer, suitable for use in an int-sized bit set.
 342  */
 343 static u4 mapTypeToBitMask(int mapType) {
 344     switch (mapType) {
 345         case kDexTypeHeaderItem:               return 1 << 0;
 346         case kDexTypeStringIdItem:             return 1 << 1;
 347         case kDexTypeTypeIdItem:               return 1 << 2;
 348         case kDexTypeProtoIdItem:              return 1 << 3;
 349         case kDexTypeFieldIdItem:              return 1 << 4;
 350         case kDexTypeMethodIdItem:             return 1 << 5;
 351         case kDexTypeClassDefItem:             return 1 << 6;
 352         case kDexTypeMapList:                  return 1 << 7;
 353         case kDexTypeTypeList:                 return 1 << 8;
 354         case kDexTypeAnnotationSetRefList:     return 1 << 9;
 355         case kDexTypeAnnotationSetItem:        return 1 << 10;
 356         case kDexTypeClassDataItem:            return 1 << 11;
 357         case kDexTypeCodeItem:                 return 1 << 12;
 358         case kDexTypeStringDataItem:           return 1 << 13;
 359         case kDexTypeDebugInfoItem:            return 1 << 14;
 360         case kDexTypeAnnotationItem:           return 1 << 15;
 361         case kDexTypeEncodedArrayItem:         return 1 << 16;
 362         case kDexTypeAnnotationsDirectoryItem: return 1 << 17;
 363         default: {
 364             LOGE("Unknown map item type %04x\n", mapType);
 365             return 0;
 366         }
 367     }
 368 }
 369
 370 /*
 371  * Helper for swapMap(), which indicates if an item type should appear
 372  * in the data section.
 373  */
 374 static bool isDataSectionType(int mapType) {
 375     switch (mapType) {
 376         case kDexTypeHeaderItem:
 377         case kDexTypeStringIdItem:
 378         case kDexTypeTypeIdItem:
 379         case kDexTypeProtoIdItem:
 380         case kDexTypeFieldIdItem:
 381         case kDexTypeMethodIdItem:
 382         case kDexTypeClassDefItem: {
 383             return false;
 384         }
 385     }
 386
 387     return true;
 388 }
 389
 390 /*
 391  * Swap the map_list and verify what we can about it. Also, if verification
 392  * passes, allocate the state's DexDataMap.
 393  */
 394 static bool swapMap(CheckState* state, DexMapList* pMap)
 395 {
 396     DexMapItem* item = pMap->list;
 397     u4 count;
 398     u4 dataItemCount = 0; // Total count of items in the data section.
 399     u4 dataItemsLeft = state->pHeader->dataSize; // See use below.
 400     u4 usedBits = 0;      // Bit set: one bit per section
 401     bool first = true;
 402     u4 lastOffset = 0;
 403
 404     SWAP_FIELD4(pMap->size);
 405     count = pMap->size;
 406
 407     CHECK_LIST_SIZE(item, count, sizeof(DexMapItem));
 408
 409     while (count--) {
 410         SWAP_FIELD2(item->type);
 411         SWAP_FIELD2(item->unused);
 412         SWAP_FIELD4(item->size);
 413         SWAP_OFFSET4(item->offset);
 414
 415         if (first) {
 416             first = false;
 417         } else if (lastOffset >= item->offset) {
 418             LOGE("Out-of-order map item: 0x%x then 0x%x\n",
 419                     lastOffset, item->offset);
 420             return false;
 421         }
 422
 423         if (item->offset >= state->pHeader->fileSize) {
 424             LOGE("Map item after end of file: %x, size 0x%x\n",
 425                     item->offset, state->pHeader->fileSize);
 426             return false;
 427         }
 428
 429         if (isDataSectionType(item->type)) {
 430             u4 icount = item->size;
 431
 432             /*
 433              * This sanity check on the data section items ensures that
 434              * there are no more items than the number of bytes in
 435              * the data section.
 436              */
 437             if (icount > dataItemsLeft) {
 438                 LOGE("Unrealistically many items in the data section: "
 439                         "at least %d\n", dataItemCount + icount);
 440                 return false;
 441             }
 442
 443             dataItemsLeft -= icount;
 444             dataItemCount += icount;
 445         }
 446
 447         u4 bit = mapTypeToBitMask(item->type);
 448
 449         if (bit == 0) {
 450             return false;
 451         }
 452
 453         if ((usedBits & bit) != 0) {
 454             LOGE("Duplicate map section of type 0x%x\n", item->type);
 455             return false;
 456         }
 457
 458         usedBits |= bit;
 459         lastOffset = item->offset;
 460         item++;
 461     }
 462
 463     if ((usedBits & mapTypeToBitMask(kDexTypeHeaderItem)) == 0) {
 464         LOGE("Map is missing header entry\n");
 465         return false;
 466     }
 467
 468     if ((usedBits & mapTypeToBitMask(kDexTypeMapList)) == 0) {
 469         LOGE("Map is missing map_list entry\n");
 470         return false;
 471     }
 472
 473     if (((usedBits & mapTypeToBitMask(kDexTypeStringIdItem)) == 0)
 474             && ((state->pHeader->stringIdsOff != 0)
 475                     || (state->pHeader->stringIdsSize != 0))) {
 476         LOGE("Map is missing string_ids entry\n");
 477         return false;
 478     }
 479
 480     if (((usedBits & mapTypeToBitMask(kDexTypeTypeIdItem)) == 0)
 481             && ((state->pHeader->typeIdsOff != 0)
 482                     || (state->pHeader->typeIdsSize != 0))) {
 483         LOGE("Map is missing type_ids entry\n");
 484         return false;
 485     }
 486
 487     if (((usedBits & mapTypeToBitMask(kDexTypeProtoIdItem)) == 0)
 488             && ((state->pHeader->protoIdsOff != 0)
 489                     || (state->pHeader->protoIdsSize != 0))) {
 490         LOGE("Map is missing proto_ids entry\n");
 491         return false;
 492     }
 493
 494     if (((usedBits & mapTypeToBitMask(kDexTypeFieldIdItem)) == 0)
 495             && ((state->pHeader->fieldIdsOff != 0)
 496                     || (state->pHeader->fieldIdsSize != 0))) {
 497         LOGE("Map is missing field_ids entry\n");
 498         return false;
 499     }
 500
 501     if (((usedBits & mapTypeToBitMask(kDexTypeMethodIdItem)) == 0)
 502             && ((state->pHeader->methodIdsOff != 0)
 503                     || (state->pHeader->methodIdsSize != 0))) {
 504         LOGE("Map is missing method_ids entry\n");
 505         return false;
 506     }
 507
 508     if (((usedBits & mapTypeToBitMask(kDexTypeClassDefItem)) == 0)
 509             && ((state->pHeader->classDefsOff != 0)
 510                     || (state->pHeader->classDefsSize != 0))) {
 511         LOGE("Map is missing class_defs entry\n");
 512         return false;
 513     }
 514
 515     state->pDataMap = dexDataMapAlloc(dataItemCount);
 516     if (state->pDataMap == NULL) {
 517         LOGE("Unable to allocate data map (size 0x%x)\n", dataItemCount);
 518         return false;
 519     }
 520
 521     return true;
 522 }
 523
 524 /* Check the map section for sanity. */
 525 static bool checkMapSection(const CheckState* state, u4 sectionOffset,
 526         u4 sectionCount, u4* endOffset) {
 527     if (sectionCount != 1) {
 528         LOGE("Multiple map list items");
 529         return false;
 530     }
 531
 532     if (sectionOffset != state->pHeader->mapOff) {
 533         LOGE("Map not at header-defined offset: 0x%x, expected 0x%x\n",
 534                 sectionOffset, state->pHeader->mapOff);
 535         return false;
 536     }
 537
 538     const DexMapList* pMap = filePointer(state, sectionOffset);
 539
 540     *endOffset =
 541         sectionOffset + sizeof(u4) + (pMap->size * sizeof(DexMapItem));
 542     return true;
 543 }
 544
 545 /* Perform byte-swapping and intra-item verification on string_id_item. */
 546 static void* swapStringIdItem(const CheckState* state, void* ptr) {
 547     DexStringId* item = ptr;
 548
 549     CHECK_PTR_RANGE(item, item + 1);
 550     SWAP_OFFSET4(item->stringDataOff);
 551
 552     return item + 1;
 553 }
 554
 555 /* Perform cross-item verification of string_id_item. */
 556 static void* crossVerifyStringIdItem(const CheckState* state, void* ptr) {
 557     const DexStringId* item = ptr;
 558
 559     if (!dexDataMapVerify(state->pDataMap,
 560                     item->stringDataOff, kDexTypeStringDataItem)) {
 561         return NULL;
 562     }
 563
 564     const DexStringId* item0 = state->previousItem;
 565     if (item0 != NULL) {
 566         // Check ordering.
 567         const char* s0 = dexGetStringData(state->pDexFile, item0);
 568         const char* s1 = dexGetStringData(state->pDexFile, item);
 569         if (dexUtf8Cmp(s0, s1) >= 0) {
 570             LOGE("Out-of-order string_ids: '%s' then '%s'\n", s0, s1);
 571             return NULL;
 572         }
 573     }
 574
 575     return (void*) (item + 1);
 576 }
 577
 578 /* Perform byte-swapping and intra-item verification on type_id_item. */
 579 static void* swapTypeIdItem(const CheckState* state, void* ptr) {
 580     DexTypeId* item = ptr;
 581
 582     CHECK_PTR_RANGE(item, item + 1);
 583     SWAP_INDEX4(item->descriptorIdx, state->pHeader->stringIdsSize);
 584
 585     return item + 1;
 586 }
 587
 588 /* Perform cross-item verification of type_id_item. */
 589 static void* crossVerifyTypeIdItem(const CheckState* state, void* ptr) {
 590     const DexTypeId* item = ptr;
 591     const char* descriptor =
 592         dexStringById(state->pDexFile, item->descriptorIdx);
 593
 594     if (!dexIsValidTypeDescriptor(descriptor)) {
 595         LOGE("Invalid type descriptor: '%s'\n", descriptor);
 596         return NULL;
 597     }
 598
 599     const DexTypeId* item0 = state->previousItem;
 600     if (item0 != NULL) {
 601         // Check ordering. This relies on string_ids being in order.
 602         if (item0->descriptorIdx >= item->descriptorIdx) {
 603             LOGE("Out-of-order type_ids: 0x%x then 0x%x\n",
 604                     item0->descriptorIdx, item->descriptorIdx);
 605             return NULL;
 606         }
 607     }
 608
 609     return (void*) (item + 1);
 610 }
 611
 612 /* Perform byte-swapping and intra-item verification on proto_id_item. */
 613 static void* swapProtoIdItem(const CheckState* state, void* ptr) {
 614     DexProtoId* item = ptr;
 615
 616     CHECK_PTR_RANGE(item, item + 1);
 617     SWAP_INDEX4(item->shortyIdx, state->pHeader->stringIdsSize);
 618     SWAP_INDEX4(item->returnTypeIdx, state->pHeader->typeIdsSize);
 619     SWAP_OFFSET4(item->parametersOff);
 620
 621     return item + 1;
 622 }
 623
 624 /* Helper for crossVerifyProtoIdItem(), which checks a shorty character
 625  * to see if it is compatible with a type descriptor. Returns true if
 626  * so, false if not. */
 627 static bool shortyDescMatch(char shorty, const char* descriptor, bool
 628         isReturnType) {
 629     switch (shorty) {
 630         case 'V': {
 631             if (!isReturnType) {
 632                 LOGE("Invalid use of void\n");
 633                 return false;
 634             }
 635             // Fall through.
 636         }
 637         case 'B':
 638         case 'C':
 639         case 'D':
 640         case 'F':
 641         case 'I':
 642         case 'J':
 643         case 'S':
 644         case 'Z': {
 645             if ((descriptor[0] != shorty) || (descriptor[1] != '\0')) {
 646                 LOGE("Shorty vs. primitive type mismatch: '%c', '%s'\n",
 647                         shorty, descriptor);
 648                 return false;
 649             }
 650             break;
 651         }
 652         case 'L': {
 653             if ((descriptor[0] != 'L') && (descriptor[0] != '[')) {
 654                 LOGE("Shorty vs. type mismatch: '%c', '%s'\n",
 655                         shorty, descriptor);
 656                 return false;
 657             }
 658             break;
 659         }
 660         default: {
 661             LOGE("Bogus shorty: '%c'\n", shorty);
 662             return false;
 663         }
 664     }
 665
 666     return true;
 667 }
 668
 669 /* Perform cross-item verification of proto_id_item. */
 670 static void* crossVerifyProtoIdItem(const CheckState* state, void* ptr) {
 671     const DexProtoId* item = ptr;
 672     const char* shorty =
 673         dexStringById(state->pDexFile, item->shortyIdx);
 674
 675     if (!dexDataMapVerify0Ok(state->pDataMap,
 676                     item->parametersOff, kDexTypeTypeList)) {
 677         return NULL;
 678     }
 679
 680     if (!shortyDescMatch(*shorty,
 681                     dexStringByTypeIdx(state->pDexFile, item->returnTypeIdx),
 682                     true)) {
 683         return NULL;
 684     }
 685
 686     u4 protoIdx = item - state->pDexFile->pProtoIds;
 687     DexProto proto = { state->pDexFile, protoIdx };
 688     DexParameterIterator iterator;
 689
 690     dexParameterIteratorInit(&iterator, &proto);
 691     shorty++; // Skip the return type.
 692
 693     for (;;) {
 694         const char *desc = dexParameterIteratorNextDescriptor(&iterator);
 695
 696         if (desc == NULL) {
 697             break;
 698         }
 699
 700         if (*shorty == '\0') {
 701             LOGE("Shorty is too short\n");
 702             return NULL;
 703         }
 704
 705         if (!shortyDescMatch(*shorty, desc, false)) {
 706             return NULL;
 707         }
 708
 709         shorty++;
 710     }
 711
 712     if (*shorty != '\0') {
 713         LOGE("Shorty is too long\n");
 714         return NULL;
 715     }
 716
 717     const DexProtoId* item0 = state->previousItem;
 718     if (item0 != NULL) {
 719         // Check ordering. This relies on type_ids being in order.
 720         if (item0->returnTypeIdx > item->returnTypeIdx) {
 721             LOGE("Out-of-order proto_id return types\n");
 722             return NULL;
 723         } else if (item0->returnTypeIdx == item->returnTypeIdx) {
 724             bool badOrder = false;
 725             DexProto proto0 = { state->pDexFile, protoIdx - 1 };
 726             DexParameterIterator iterator0;
 727
 728             dexParameterIteratorInit(&iterator, &proto);
 729             dexParameterIteratorInit(&iterator0, &proto0);
 730
 731             for (;;) {
 732                 u4 idx0 = dexParameterIteratorNextIndex(&iterator0);
 733                 u4 idx1 = dexParameterIteratorNextIndex(&iterator);
 734
 735                 if (idx1 == kDexNoIndex) {
 736                     badOrder = true;
 737                     break;
 738                 }
 739
 740                 if (idx0 == kDexNoIndex) {
 741                     break;
 742                 }
 743
 744                 if (idx0 < idx1) {
 745                     break;
 746                 } else if (idx0 > idx1) {
 747                     badOrder = true;
 748                     break;
 749                 }
 750             }
 751
 752             if (badOrder) {
 753                 LOGE("Out-of-order proto_id arguments\n");
 754                 return NULL;
 755             }
 756         }
 757     }
 758
 759     return (void*) (item + 1);
 760 }
 761
 762 /* Perform byte-swapping and intra-item verification on field_id_item. */
 763 static void* swapFieldIdItem(const CheckState* state, void* ptr) {
 764     DexFieldId* item = ptr;
 765
 766     CHECK_PTR_RANGE(item, item + 1);
 767     SWAP_INDEX2(item->classIdx, state->pHeader->typeIdsSize);
 768     SWAP_INDEX2(item->typeIdx, state->pHeader->typeIdsSize);
 769     SWAP_INDEX4(item->nameIdx, state->pHeader->stringIdsSize);
 770
 771     return item + 1;
 772 }
 773
 774 /* Perform cross-item verification of field_id_item. */
 775 static void* crossVerifyFieldIdItem(const CheckState* state, void* ptr) {
 776     const DexFieldId* item = ptr;
 777     const char* s;
 778
 779     s = dexStringByTypeIdx(state->pDexFile, item->classIdx);
 780     if (!dexIsClassDescriptor(s)) {
 781         LOGE("Invalid descriptor for class_idx: '%s'\n", s);
 782         return NULL;
 783     }
 784
 785     s = dexStringByTypeIdx(state->pDexFile, item->typeIdx);
 786     if (!dexIsFieldDescriptor(s)) {
 787         LOGE("Invalid descriptor for type_idx: '%s'\n", s);
 788         return NULL;
 789     }
 790
 791     s = dexStringById(state->pDexFile, item->nameIdx);
 792     if (!dexIsValidMemberName(s)) {
 793         LOGE("Invalid name: '%s'\n", s);
 794         return NULL;
 795     }
 796
 797     const DexFieldId* item0 = state->previousItem;
 798     if (item0 != NULL) {
 799         // Check ordering. This relies on the other sections being in order.
 800         bool done = false;
 801         bool bogus = false;
 802
 803         if (item0->classIdx > item->classIdx) {
 804             bogus = true;
 805             done = true;
 806         } else if (item0->classIdx < item->classIdx) {
 807             done = true;
 808         }
 809
 810         if (!done) {
 811             if (item0->nameIdx > item->nameIdx) {
 812                 bogus = true;
 813                 done = true;
 814             } else if (item0->nameIdx < item->nameIdx) {
 815                 done = true;
 816             }
 817         }
 818
 819         if (!done) {
 820             if (item0->typeIdx >= item->typeIdx) {
 821                 bogus = true;
 822             }
 823         }
 824
 825         if (bogus) {
 826             LOGE("Out-of-order field_ids\n");
 827             return NULL;
 828         }
 829     }
 830
 831     return (void*) (item + 1);
 832 }
 833
 834 /* Perform byte-swapping and intra-item verification on method_id_item. */
 835 static void* swapMethodIdItem(const CheckState* state, void* ptr) {
 836     DexMethodId* item = ptr;
 837
 838     CHECK_PTR_RANGE(item, item + 1);
 839     SWAP_INDEX2(item->classIdx, state->pHeader->typeIdsSize);
 840     SWAP_INDEX2(item->protoIdx, state->pHeader->protoIdsSize);
 841     SWAP_INDEX4(item->nameIdx, state->pHeader->stringIdsSize);
 842
 843     return item + 1;
 844 }
 845
 846 /* Perform cross-item verification of method_id_item. */
 847 static void* crossVerifyMethodIdItem(const CheckState* state, void* ptr) {
 848     const DexMethodId* item = ptr;
 849     const char* s;
 850
 851     s = dexStringByTypeIdx(state->pDexFile, item->classIdx);
 852     if (!dexIsReferenceDescriptor(s)) {
 853         LOGE("Invalid descriptor for class_idx: '%s'\n", s);
 854         return NULL;
 855     }
 856
 857     s = dexStringById(state->pDexFile, item->nameIdx);
 858     if (!dexIsValidMemberName(s)) {
 859         LOGE("Invalid name: '%s'\n", s);
 860         return NULL;
 861     }
 862
 863     const DexMethodId* item0 = state->previousItem;
 864     if (item0 != NULL) {
 865         // Check ordering. This relies on the other sections being in order.
 866         bool done = false;
 867         bool bogus = false;
 868
 869         if (item0->classIdx > item->classIdx) {
 870             bogus = true;
 871             done = true;
 872         } else if (item0->classIdx < item->classIdx) {
 873             done = true;
 874         }
 875
 876         if (!done) {
 877             if (item0->nameIdx > item->nameIdx) {
 878                 bogus = true;
 879                 done = true;
 880             } else if (item0->nameIdx < item->nameIdx) {
 881                 done = true;
 882             }
 883         }
 884
 885         if (!done) {
 886             if (item0->protoIdx >= item->protoIdx) {
 887                 bogus = true;
 888             }
 889         }
 890
 891         if (bogus) {
 892             LOGE("Out-of-order method_ids\n");
 893             return NULL;
 894         }
 895     }
 896
 897     return (void*) (item + 1);
 898 }
 899
 900 /* Perform byte-swapping and intra-item verification on class_def_item. */
 901 static void* swapClassDefItem(const CheckState* state, void* ptr) {
 902     DexClassDef* item = ptr;
 903
 904     CHECK_PTR_RANGE(item, item + 1);
 905     SWAP_INDEX4(item->classIdx, state->pHeader->typeIdsSize);
 906     SWAP_FIELD4(item->accessFlags);
 907     SWAP_INDEX4_OR_NOINDEX(item->superclassIdx, state->pHeader->typeIdsSize);
 908     SWAP_OFFSET4(item->interfacesOff);
 909     SWAP_INDEX4_OR_NOINDEX(item->sourceFileIdx, state->pHeader->stringIdsSize);
 910     SWAP_OFFSET4(item->annotationsOff);
 911     SWAP_OFFSET4(item->classDataOff);
 912
 913     return item + 1;
 914 }
 915
 916 /* defined below */
 917 static u4 findFirstClassDataDefiner(const CheckState* state,
 918         DexClassData* classData);
 919 static u4 findFirstAnnotationsDirectoryDefiner(const CheckState* state,
 920         const DexAnnotationsDirectoryItem* dir);
 921
 922 /* Helper for crossVerifyClassDefItem(), which checks a class_data_item to
 923  * make sure all its references are to a given class. */
 924 static bool verifyClassDataIsForDef(const CheckState* state, u4 offset,
 925         u4 definerIdx) {
 926     if (offset == 0) {
 927         return true;
 928     }
 929
 930     const u1* data = filePointer(state, offset);
 931     DexClassData* classData = dexReadAndVerifyClassData(&data, NULL);
 932
 933     if (classData == NULL) {
 934         // Shouldn't happen, but bail here just in case.
 935         return false;
 936     }
 937
 938     /*
 939      * The class_data_item verification ensures that
 940      * it consistently refers to the same definer, so all we need to
 941      * do is check the first one.
 942      */
 943     u4 dataDefiner = findFirstClassDataDefiner(state, classData);
 944     bool result = (dataDefiner == definerIdx) || (dataDefiner == kDexNoIndex);
 945
 946     free(classData);
 947     return result;
 948 }
 949
 950 /* Helper for crossVerifyClassDefItem(), which checks an
 951  * annotations_directory_item to make sure all its references are to a
 952  * given class. */
 953 static bool verifyAnnotationsDirectoryIsForDef(const CheckState* state,
 954         u4 offset, u4 definerIdx) {
 955     if (offset == 0) {
 956         return true;
 957     }
 958
 959     const DexAnnotationsDirectoryItem* dir = filePointer(state, offset);
 960     u4 annoDefiner = findFirstAnnotationsDirectoryDefiner(state, dir);
 961
 962     return (annoDefiner == definerIdx) || (annoDefiner == kDexNoIndex);
 963 }
 964
 965 /* Perform cross-item verification of class_def_item. */
 966 static void* crossVerifyClassDefItem(const CheckState* state, void* ptr) {
 967     const DexClassDef* item = ptr;
 968     u4 classIdx = item->classIdx;
 969     const char* descriptor = dexStringByTypeIdx(state->pDexFile, classIdx);
 970
 971     if (!dexIsClassDescriptor(descriptor)) {
 972         LOGE("Invalid class: '%s'\n", descriptor);
 973         return NULL;
 974     }
 975
 976     if (setDefinedClassBit(state, classIdx)) {
 977         LOGE("Duplicate class definition: '%s'\n", descriptor);
 978         return NULL;
 979     }
 980
 981     bool okay =
 982         dexDataMapVerify0Ok(state->pDataMap,
 983                 item->interfacesOff, kDexTypeTypeList)
 984         && dexDataMapVerify0Ok(state->pDataMap,
 985                 item->annotationsOff, kDexTypeAnnotationsDirectoryItem)
 986         && dexDataMapVerify0Ok(state->pDataMap,
 987                 item->classDataOff, kDexTypeClassDataItem)
 988         && dexDataMapVerify0Ok(state->pDataMap,
 989                 item->staticValuesOff, kDexTypeEncodedArrayItem);
 990
 991     if (!okay) {
 992         return NULL;
 993     }
 994
 995     if (item->superclassIdx != kDexNoIndex) {
 996         descriptor = dexStringByTypeIdx(state->pDexFile, item->superclassIdx);
 997         if (!dexIsClassDescriptor(descriptor)) {
 998             LOGE("Invalid superclass: '%s'\n", descriptor);
 999             return NULL;
1000         }
1001     }
1002
1003     const DexTypeList* interfaces =
1004         dexGetInterfacesList(state->pDexFile, item);
1005     if (interfaces != NULL) {
1006         u4 size = interfaces->size;
1007         u4 i;
1008
1009         /*
1010          * Ensure that all interfaces refer to classes (not arrays or
1011          * primitives).
1012          */
1013         for (i = 0; i < size; i++) {
1014             descriptor = dexStringByTypeIdx(state->pDexFile,
1015                     dexTypeListGetIdx(interfaces, i));
1016             if (!dexIsClassDescriptor(descriptor)) {
1017                 LOGE("Invalid interface: '%s'\n", descriptor);
1018                 return NULL;
1019             }
1020         }
1021
1022         /*
1023          * Ensure that there are no duplicates. This is an O(N^2) test,
1024          * but in practice the number of interfaces implemented by any
1025          * given class is low. I will buy a milkshake for the
1026          * first person to show me a realistic case for which this test
1027          * would be unacceptably slow.
1028          */
1029         for (i = 1; i < size; i++) {
1030             u4 idx1 = dexTypeListGetIdx(interfaces, i);
1031             u4 j;
1032             for (j = 0; j < i; j++) {
1033                 u4 idx2 = dexTypeListGetIdx(interfaces, j);
1034                 if (idx1 == idx2) {
1035                     LOGE("Duplicate interface: '%s'\n",
1036                             dexStringByTypeIdx(state->pDexFile, idx1));
1037                     return NULL;
1038                 }
1039             }
1040         }
1041     }
1042
1043     if (!verifyClassDataIsForDef(state, item->classDataOff, item->classIdx)) {
1044         LOGE("Invalid class_data_item\n");
1045         return NULL;
1046     }
1047
1048     if (!verifyAnnotationsDirectoryIsForDef(state, item->annotationsOff,
1049                     item->classIdx)) {
1050         LOGE("Invalid annotations_directory_item\n");
1051         return NULL;
1052     }
1053
1054     return (void*) (item + 1);
1055 }
1056
1057 /* Helper for swapAnnotationsDirectoryItem(), which performs
1058  * byte-swapping and intra-item verification on an
1059  * annotation_directory_item's field elements. */
1060 static u1* swapFieldAnnotations(const CheckState* state, u4 count, u1* addr) {
1061     DexFieldAnnotationsItem* item = (DexFieldAnnotationsItem*) addr;
1062     bool first = true;
1063     u4 lastIdx = 0;
1064
1065     CHECK_LIST_SIZE(item, count, sizeof(DexFieldAnnotationsItem));
1066
1067     while (count--) {
1068         SWAP_INDEX4(item->fieldIdx, state->pHeader->fieldIdsSize);
1069         SWAP_OFFSET4(item->annotationsOff);
1070
1071         if (first) {
1072             first = false;
1073         } else if (lastIdx >= item->fieldIdx) {
1074             LOGE("Out-of-order field_idx: 0x%x then 0x%x\n", lastIdx,
1075                  item->fieldIdx);
1076             return NULL;
1077         }
1078
1079         lastIdx = item->fieldIdx;
1080         item++;
1081     }
1082
1083     return (u1*) item;
1084 }
1085
1086 /* Helper for swapAnnotationsDirectoryItem(), which performs
1087  * byte-swapping and intra-item verification on an
1088  * annotation_directory_item's method elements. */
1089 static u1* swapMethodAnnotations(const CheckState* state, u4 count, u1* addr) {
1090     DexMethodAnnotationsItem* item = (DexMethodAnnotationsItem*) addr;
1091     bool first = true;
1092     u4 lastIdx = 0;
1093
1094     CHECK_LIST_SIZE(item, count, sizeof(DexMethodAnnotationsItem));
1095
1096     while (count--) {
1097         SWAP_INDEX4(item->methodIdx, state->pHeader->methodIdsSize);
1098         SWAP_OFFSET4(item->annotationsOff);
1099
1100         if (first) {
1101             first = false;
1102         } else if (lastIdx >= item->methodIdx) {
1103             LOGE("Out-of-order method_idx: 0x%x then 0x%x\n", lastIdx,
1104                  item->methodIdx);
1105             return NULL;
1106         }
1107
1108         lastIdx = item->methodIdx;
1109         item++;
1110     }
1111
1112     return (u1*) item;
1113 }
1114
1115 /* Helper for swapAnnotationsDirectoryItem(), which performs
1116  * byte-swapping and intra-item verification on an
1117  * annotation_directory_item's parameter elements. */
1118 static u1* swapParameterAnnotations(const CheckState* state, u4 count,
1119         u1* addr) {
1120     DexParameterAnnotationsItem* item = (DexParameterAnnotationsItem*) addr;
1121     bool first = true;
1122     u4 lastIdx = 0;
1123
1124     CHECK_LIST_SIZE(item, count, sizeof(DexParameterAnnotationsItem));
1125
1126     while (count--) {
1127         SWAP_INDEX4(item->methodIdx, state->pHeader->methodIdsSize);
1128         SWAP_OFFSET4(item->annotationsOff);
1129
1130         if (first) {
1131             first = false;
1132         } else if (lastIdx >= item->methodIdx) {
1133             LOGE("Out-of-order method_idx: 0x%x then 0x%x\n", lastIdx,
1134                  item->methodIdx);
1135             return NULL;
1136         }
1137
1138         lastIdx = item->methodIdx;
1139         item++;
1140     }
1141
1142     return (u1*) item;
1143 }
1144
1145 /* Perform byte-swapping and intra-item verification on
1146  * annotations_directory_item. */
1147 static void* swapAnnotationsDirectoryItem(const CheckState* state, void* ptr) {
1148     DexAnnotationsDirectoryItem* item = ptr;
1149
1150     CHECK_PTR_RANGE(item, item + 1);
1151     SWAP_OFFSET4(item->classAnnotationsOff);
1152     SWAP_FIELD4(item->fieldsSize);
1153     SWAP_FIELD4(item->methodsSize);
1154     SWAP_FIELD4(item->parametersSize);
1155
1156     u1* addr = (u1*) (item + 1);
1157
1158     if (item->fieldsSize != 0) {
1159         addr = swapFieldAnnotations(state, item->fieldsSize, addr);
1160         if (addr == NULL) {
1161             return NULL;
1162         }
1163     }
1164
1165     if (item->methodsSize != 0) {
1166         addr = swapMethodAnnotations(state, item->methodsSize, addr);
1167         if (addr == NULL) {
1168             return NULL;
1169         }
1170     }
1171
1172     if (item->parametersSize != 0) {
1173         addr = swapParameterAnnotations(state, item->parametersSize, addr);
1174         if (addr == NULL) {
1175             return NULL;
1176         }
1177     }
1178
1179     return addr;
1180 }
1181
1182 /* Helper for crossVerifyAnnotationsDirectoryItem(), which checks the
1183  * field elements. */
1184 static const u1* crossVerifyFieldAnnotations(const CheckState* state, u4 count,
1185         const u1* addr, u4 definingClass) {
1186     const DexFieldAnnotationsItem* item = (DexFieldAnnotationsItem*) addr;
1187
1188     while (count--) {
1189         if (!verifyFieldDefiner(state, definingClass, item->fieldIdx)) {
1190             return NULL;
1191         }
1192         if (!dexDataMapVerify(state->pDataMap, item->annotationsOff,
1193                         kDexTypeAnnotationSetItem)) {
1194             return NULL;
1195         }
1196         item++;
1197     }
1198
1199     return (const u1*) item;
1200 }
1201
1202 /* Helper for crossVerifyAnnotationsDirectoryItem(), which checks the
1203  * method elements. */
1204 static const u1* crossVerifyMethodAnnotations(const CheckState* state,
1205         u4 count, const u1* addr, u4 definingClass) {
1206     const DexMethodAnnotationsItem* item = (DexMethodAnnotationsItem*) addr;
1207
1208     while (count--) {
1209         if (!verifyMethodDefiner(state, definingClass, item->methodIdx)) {
1210             return NULL;
1211         }
1212         if (!dexDataMapVerify(state->pDataMap, item->annotationsOff,
1213                         kDexTypeAnnotationSetItem)) {
1214             return NULL;
1215         }
1216         item++;
1217     }
1218
1219     return (const u1*) item;
1220 }
1221
1222 /* Helper for crossVerifyAnnotationsDirectoryItem(), which checks the
1223  * parameter elements. */
1224 static const u1* crossVerifyParameterAnnotations(const CheckState* state,
1225         u4 count, const u1* addr, u4 definingClass) {
1226     const DexParameterAnnotationsItem* item =
1227         (DexParameterAnnotationsItem*) addr;
1228
1229     while (count--) {
1230         if (!verifyMethodDefiner(state, definingClass, item->methodIdx)) {
1231             return NULL;
1232         }
1233         if (!dexDataMapVerify(state->pDataMap, item->annotationsOff,
1234                         kDexTypeAnnotationSetRefList)) {
1235             return NULL;
1236         }
1237         item++;
1238     }
1239
1240     return (const u1*) item;
1241 }
1242
1243 /* Helper for crossVerifyClassDefItem() and
1244  * crossVerifyAnnotationsDirectoryItem(), which finds the type_idx of
1245  * the definer of the first item in the data. */
1246 static u4 findFirstAnnotationsDirectoryDefiner(const CheckState* state,
1247         const DexAnnotationsDirectoryItem* dir) {
1248     if (dir->fieldsSize != 0) {
1249         const DexFieldAnnotationsItem* fields =
1250             dexGetFieldAnnotations(state->pDexFile, dir);
1251         const DexFieldId* field =
1252             dexGetFieldId(state->pDexFile, fields[0].fieldIdx);
1253         return field->classIdx;
1254     }
1255
1256     if (dir->methodsSize != 0) {
1257         const DexMethodAnnotationsItem* methods =
1258             dexGetMethodAnnotations(state->pDexFile, dir);
1259         const DexMethodId* method =
1260             dexGetMethodId(state->pDexFile, methods[0].methodIdx);
1261         return method->classIdx;
1262     }
1263
1264     if (dir->parametersSize != 0) {
1265         const DexParameterAnnotationsItem* parameters =
1266             dexGetParameterAnnotations(state->pDexFile, dir);
1267         const DexMethodId* method =
1268             dexGetMethodId(state->pDexFile, parameters[0].methodIdx);
1269         return method->classIdx;
1270     }
1271
1272     return kDexNoIndex;
1273 }
1274
1275 /* Perform cross-item verification of annotations_directory_item. */
1276 static void* crossVerifyAnnotationsDirectoryItem(const CheckState* state,
1277         void* ptr) {
1278     const DexAnnotationsDirectoryItem* item = ptr;
1279     u4 definingClass = findFirstAnnotationsDirectoryDefiner(state, item);
1280
1281     if (!dexDataMapVerify0Ok(state->pDataMap,
1282                     item->classAnnotationsOff, kDexTypeAnnotationSetItem)) {
1283         return NULL;
1284     }
1285
1286     const u1* addr = (const u1*) (item + 1);
1287
1288     if (item->fieldsSize != 0) {
1289         addr = crossVerifyFieldAnnotations(state, item->fieldsSize, addr,
1290                 definingClass);
1291         if (addr == NULL) {
1292             return NULL;
1293         }
1294     }
1295
1296     if (item->methodsSize != 0) {
1297         addr = crossVerifyMethodAnnotations(state, item->methodsSize, addr,
1298                 definingClass);
1299         if (addr == NULL) {
1300             return NULL;
1301         }
1302     }
1303
1304     if (item->parametersSize != 0) {
1305         addr = crossVerifyParameterAnnotations(state, item->parametersSize,
1306                 addr, definingClass);
1307         if (addr == NULL) {
1308             return NULL;
1309         }
1310     }
1311
1312     return (void*) addr;
1313 }
1314
1315 /* Perform byte-swapping and intra-item verification on type_list. */
1316 static void* swapTypeList(const CheckState* state, void* ptr)
1317 {
1318     DexTypeList* pTypeList = ptr;
1319     DexTypeItem* pType;
1320     u4 count;
1321
1322     CHECK_PTR_RANGE(pTypeList, pTypeList + 1);
1323     SWAP_FIELD4(pTypeList->size);
1324     count = pTypeList->size;
1325     pType = pTypeList->list;
1326     CHECK_LIST_SIZE(pType, count, sizeof(DexTypeItem));
1327
1328     while (count--) {
1329         SWAP_INDEX2(pType->typeIdx, state->pHeader->typeIdsSize);
1330         pType++;
1331     }
1332
1333     return pType;
1334 }
1335
1336 /* Perform byte-swapping and intra-item verification on
1337  * annotation_set_ref_list. */
1338 static void* swapAnnotationSetRefList(const CheckState* state, void* ptr) {
1339     DexAnnotationSetRefList* list = ptr;
1340     DexAnnotationSetRefItem* item;
1341     u4 count;
1342
1343     CHECK_PTR_RANGE(list, list + 1);
1344     SWAP_FIELD4(list->size);
1345     count = list->size;
1346     item = list->list;
1347     CHECK_LIST_SIZE(item, count, sizeof(DexAnnotationSetRefItem));
1348
1349     while (count--) {
1350         SWAP_OFFSET4(item->annotationsOff);
1351         item++;
1352     }
1353
1354     return item;
1355 }
1356
1357 /* Perform cross-item verification of annotation_set_ref_list. */
1358 static void* crossVerifyAnnotationSetRefList(const CheckState* state,
1359         void* ptr) {
1360     const DexAnnotationSetRefList* list = ptr;
1361     const DexAnnotationSetRefItem* item = list->list;
1362     int count = list->size;
1363
1364     while (count--) {
1365         if (!dexDataMapVerify0Ok(state->pDataMap,
1366                         item->annotationsOff, kDexTypeAnnotationSetItem)) {
1367             return NULL;
1368         }
1369         item++;
1370     }
1371
1372     return (void*) item;
1373 }
1374
1375 /* Perform byte-swapping and intra-item verification on
1376  * annotation_set_item. */
1377 static void* swapAnnotationSetItem(const CheckState* state, void* ptr) {
1378     DexAnnotationSetItem* set = ptr;
1379     u4* item;
1380     u4 count;
1381
1382     CHECK_PTR_RANGE(set, set + 1);
1383     SWAP_FIELD4(set->size);
1384     count = set->size;
1385     item = set->entries;
1386     CHECK_LIST_SIZE(item, count, sizeof(u4));
1387
1388     while (count--) {
1389         SWAP_OFFSET4(*item);
1390         item++;
1391     }
1392
1393     return item;
1394 }
1395
1396 /* Helper for crossVerifyAnnotationSetItem(), which extracts the type_idx
1397  * out of an annotation_item. */
1398 static u4 annotationItemTypeIdx(const DexAnnotationItem* item) {
1399     const u1* data = item->annotation;
1400     return readUnsignedLeb128(&data);
1401 }
1402
1403 /* Perform cross-item verification of annotation_set_item. */
1404 static void* crossVerifyAnnotationSetItem(const CheckState* state, void* ptr) {
1405     const DexAnnotationSetItem* set = ptr;
1406     int count = set->size;
1407     u4 lastIdx = 0;
1408     bool first = true;
1409     int i;
1410
1411     for (i = 0; i < count; i++) {
1412         if (!dexDataMapVerify0Ok(state->pDataMap,
1413                         dexGetAnnotationOff(set, i), kDexTypeAnnotationItem)) {
1414             return NULL;
1415         }
1416
1417         const DexAnnotationItem* annotation =
1418             dexGetAnnotationItem(state->pDexFile, set, i);
1419         u4 idx = annotationItemTypeIdx(annotation);
1420
1421         if (first) {
1422             first = false;
1423         } else if (lastIdx >= idx) {
1424             LOGE("Out-of-order entry types: 0x%x then 0x%x\n",
1425                     lastIdx, idx);
1426             return NULL;
1427         }
1428
1429         lastIdx = idx;
1430     }
1431
1432     return (void*) (set->entries + count);
1433 }
1434
1435 /* Helper for verifyClassDataItem(), which checks a list of fields. */
1436 static bool verifyFields(const CheckState* state, u4 size,
1437         DexField* fields, bool expectStatic) {
1438     u4 i;
1439
1440     for (i = 0; i < size; i++) {
1441         DexField* field = &fields[i];
1442         u4 accessFlags = field->accessFlags;
1443         bool isStatic = (accessFlags & ACC_STATIC) != 0;
1444
1445         CHECK_INDEX(field->fieldIdx, state->pHeader->fieldIdsSize);
1446
1447         if (isStatic != expectStatic) {
1448             LOGE("Field in wrong list @ %d\n", i);
1449             return false;
1450         }
1451
1452         if ((accessFlags & ~ACC_FIELD_MASK) != 0) {
1453             LOGE("Bogus field access flags %x @ %d\n", accessFlags, i);
1454             return false;
1455         }
1456     }
1457
1458     return true;
1459 }
1460
1461 /* Helper for verifyClassDataItem(), which checks a list of methods. */
1462 static bool verifyMethods(const CheckState* state, u4 size,
1463         DexMethod* methods, bool expectDirect) {
1464     u4 i;
1465
1466     for (i = 0; i < size; i++) {
1467         DexMethod* method = &methods[i];
1468
1469         CHECK_INDEX(method->methodIdx, state->pHeader->methodIdsSize);
1470
1471         u4 accessFlags = method->accessFlags;
1472         bool isDirect =
1473             (accessFlags & (ACC_STATIC | ACC_PRIVATE | ACC_CONSTRUCTOR)) != 0;
1474         bool expectCode = (accessFlags & (ACC_NATIVE | ACC_ABSTRACT)) == 0;
1475         bool isSynchronized = (accessFlags & ACC_SYNCHRONIZED) != 0;
1476         bool allowSynchronized = (accessFlags & ACC_NATIVE) != 0;
1477
1478         if (isDirect != expectDirect) {
1479             LOGE("Method in wrong list @ %d\n", i);
1480             return false;
1481         }
1482
1483         if (((accessFlags & ~ACC_METHOD_MASK) != 0)
1484                 || (isSynchronized && !allowSynchronized)) {
1485             LOGE("Bogus method access flags %x @ %d\n", accessFlags, i);
1486             return false;
1487         }
1488
1489         if (expectCode) {
1490             if (method->codeOff == 0) {
1491                 LOGE("Unexpected zero code_off for access_flags %x\n",
1492                         accessFlags);
1493                 return false;
1494             }
1495         } else if (method->codeOff != 0) {
1496             LOGE("Unexpected non-zero code_off 0x%x for access_flags %x\n",
1497                     method->codeOff, accessFlags);
1498             return false;
1499         }
1500     }
1501
1502     return true;
1503 }
1504
1505 /* Helper for verifyClassDataItem(), which does most of the work. */
1506 static bool verifyClassDataItem0(const CheckState* state,
1507         DexClassData* classData) {
1508     bool okay;
1509
1510     okay = verifyFields(state, classData->header.staticFieldsSize,
1511             classData->staticFields, true);
1512
1513     if (!okay) {
1514         LOGE("Trouble with static fields\n");
1515         return false;
1516     }
1517
1518     verifyFields(state, classData->header.instanceFieldsSize,
1519             classData->instanceFields, false);
1520
1521     if (!okay) {
1522         LOGE("Trouble with instance fields\n");
1523         return false;
1524     }
1525
1526     okay = verifyMethods(state, classData->header.directMethodsSize,
1527             classData->directMethods, true);
1528
1529     if (!okay) {
1530         LOGE("Trouble with direct methods\n");
1531         return false;
1532     }
1533
1534     okay = verifyMethods(state, classData->header.virtualMethodsSize,
1535             classData->virtualMethods, false);
1536
1537     if (!okay) {
1538         LOGE("Trouble with virtual methods\n");
1539         return false;
1540     }
1541
1542     return true;
1543 }
1544
1545 /* Perform intra-item verification on class_data_item. */
1546 static void* intraVerifyClassDataItem(const CheckState* state, void* ptr) {
1547     const u1* data = ptr;
1548     DexClassData* classData = dexReadAndVerifyClassData(&data, state->fileEnd);
1549
1550     if (classData == NULL) {
1551         LOGE("Unable to parse class_data_item\n");
1552         return NULL;
1553     }
1554
1555     bool okay = verifyClassDataItem0(state, classData);
1556
1557     free(classData);
1558
1559     if (!okay) {
1560         return NULL;
1561     }
1562
1563     return (void*) data;
1564 }
1565
1566 /* Helper for crossVerifyClassDefItem() and
1567  * crossVerifyClassDataItem(), which finds the type_idx of the definer
1568  * of the first item in the data. */
1569 static u4 findFirstClassDataDefiner(const CheckState* state,
1570         DexClassData* classData) {
1571     if (classData->header.staticFieldsSize != 0) {
1572         u4 fieldIdx = classData->staticFields[0].fieldIdx;
1573         const DexFieldId* field = dexGetFieldId(state->pDexFile, fieldIdx);
1574         return field->classIdx;
1575     }
1576
1577     if (classData->header.instanceFieldsSize != 0) {
1578         u4 fieldIdx = classData->instanceFields[0].fieldIdx;
1579         const DexFieldId* field = dexGetFieldId(state->pDexFile, fieldIdx);
1580         return field->classIdx;
1581     }
1582
1583     if (classData->header.directMethodsSize != 0) {
1584         u4 methodIdx = classData->directMethods[0].methodIdx;
1585         const DexMethodId* meth = dexGetMethodId(state->pDexFile, methodIdx);
1586         return meth->classIdx;
1587     }
1588
1589     if (classData->header.virtualMethodsSize != 0) {
1590         u4 methodIdx = classData->virtualMethods[0].methodIdx;
1591         const DexMethodId* meth = dexGetMethodId(state->pDexFile, methodIdx);
1592         return meth->classIdx;
1593     }
1594
1595     return kDexNoIndex;
1596 }
1597
1598 /* Perform cross-item verification of class_data_item. */
1599 static void* crossVerifyClassDataItem(const CheckState* state, void* ptr) {
1600     const u1* data = ptr;
1601     DexClassData* classData = dexReadAndVerifyClassData(&data, state->fileEnd);
1602     u4 definingClass = findFirstClassDataDefiner(state, classData);
1603     bool okay = true;
1604     u4 i;
1605
1606     for (i = classData->header.staticFieldsSize; okay && (i > 0); /*i*/) {
1607         i--;
1608         const DexField* field = &classData->staticFields[i];
1609         okay = verifyFieldDefiner(state, definingClass, field->fieldIdx);
1610     }
1611
1612     for (i = classData->header.instanceFieldsSize; okay && (i > 0); /*i*/) {
1613         i--;
1614         const DexField* field = &classData->instanceFields[i];
1615         okay = verifyFieldDefiner(state, definingClass, field->fieldIdx);
1616     }
1617
1618     for (i = classData->header.directMethodsSize; okay && (i > 0); /*i*/) {
1619         i--;
1620         const DexMethod* meth = &classData->directMethods[i];
1621         okay = dexDataMapVerify0Ok(state->pDataMap, meth->codeOff,
1622                 kDexTypeCodeItem)
1623             && verifyMethodDefiner(state, definingClass, meth->methodIdx);
1624     }
1625
1626     for (i = classData->header.virtualMethodsSize; okay && (i > 0); /*i*/) {
1627         i--;
1628         const DexMethod* meth = &classData->virtualMethods[i];
1629         okay = dexDataMapVerify0Ok(state->pDataMap, meth->codeOff,
1630                 kDexTypeCodeItem)
1631             && verifyMethodDefiner(state, definingClass, meth->methodIdx);
1632     }
1633
1634     free(classData);
1635
1636     if (!okay) {
1637         return NULL;
1638     }
1639
1640     return (void*) data;
1641 }
1642
1643 /* Helper for swapCodeItem(), which fills an array with all the valid
1644  * handlerOff values for catch handlers and also verifies the handler
1645  * contents. */
1646 static u4 setHandlerOffsAndVerify(const CheckState* state,
1647         DexCode* code, u4 firstOffset, u4 handlersSize, u4* handlerOffs) {
1648     const u1* fileEnd = state->fileEnd;
1649     const u1* handlersBase = dexGetCatchHandlerData(code);
1650     u4 offset = firstOffset;
1651     bool okay = true;
1652     u4 i;
1653
1654     for (i = 0; i < handlersSize; i++) {
1655         const u1* ptr = handlersBase + offset;
1656         int size = readAndVerifySignedLeb128(&ptr, fileEnd, &okay);
1657         bool catchAll;
1658
1659         if (!okay) {
1660             LOGE("Bogus size\n");
1661             return 0;
1662         }
1663
1664         if ((size < -65536) || (size > 65536)) {
1665             LOGE("Invalid size: %d\n", size);
1666             return 0;
1667         }
1668
1669         if (size <= 0) {
1670             catchAll = true;
1671             size = -size;
1672         } else {
1673             catchAll = false;
1674         }
1675
1676         handlerOffs[i] = offset;
1677
1678         while (size-- > 0) {
1679             u4 typeIdx =
1680                 readAndVerifyUnsignedLeb128(&ptr, fileEnd, &okay);
1681
1682             if (!okay) {
1683                 LOGE("Bogus type_idx");
1684                 return 0;
1685             }
1686
1687             CHECK_INDEX(typeIdx, state->pHeader->typeIdsSize);
1688
1689             u4 addr = readAndVerifyUnsignedLeb128(&ptr, fileEnd, &okay);
1690
1691             if (!okay) {
1692                 LOGE("Bogus addr");
1693                 return 0;
1694             }
1695
1696             if (addr >= code->insnsSize) {
1697                 LOGE("Invalid addr: 0x%x", addr);
1698                 return 0;
1699             }
1700         }
1701
1702         if (catchAll) {
1703             u4 addr = readAndVerifyUnsignedLeb128(&ptr, fileEnd, &okay);
1704
1705             if (!okay) {
1706                 LOGE("Bogus catch_all_addr");
1707                 return 0;
1708             }
1709
1710             if (addr >= code->insnsSize) {
1711                 LOGE("Invalid catch_all_addr: 0x%x", addr);
1712                 return 0;
1713             }
1714         }
1715
1716         offset = ptr - handlersBase;
1717     }
1718
1719     return offset;
1720 }
1721
1722 /* Helper for swapCodeItem(), which does all the try-catch related
1723  * swapping and verification. */
1724 static void* swapTriesAndCatches(const CheckState* state, DexCode* code) {
1725     const u1* encodedHandlers = dexGetCatchHandlerData(code);
1726     const u1* encodedPtr = encodedHandlers;
1727     bool okay = true;
1728     u4 handlersSize =
1729         readAndVerifyUnsignedLeb128(&encodedPtr, state->fileEnd, &okay);
1730
1731     if (!okay) {
1732         LOGE("Bogus handlers_size\n");
1733         return NULL;
1734     }
1735
1736     if ((handlersSize == 0) || (handlersSize >= 65536)) {
1737         LOGE("Invalid handlers_size: %d\n", handlersSize);
1738         return NULL;
1739     }
1740
1741     u4 handlerOffs[handlersSize]; // list of valid handlerOff values
1742     u4 endOffset = setHandlerOffsAndVerify(state, code,
1743             encodedPtr - encodedHandlers,
1744             handlersSize, handlerOffs);
1745
1746     if (endOffset == 0) {
1747         return NULL;
1748     }
1749
1750     DexTry* tries = (DexTry*) dexGetTries(code);
1751     u4 count = code->triesSize;
1752     u4 lastEnd = 0;
1753
1754     CHECK_LIST_SIZE(tries, count, sizeof(DexTry));
1755
1756     while (count--) {
1757         u4 i;
1758
1759         SWAP_FIELD4(tries->startAddr);
1760         SWAP_FIELD2(tries->insnCount);
1761         SWAP_FIELD2(tries->handlerOff);
1762
1763         if (tries->startAddr < lastEnd) {
1764             LOGE("Out-of-order try\n");
1765             return NULL;
1766         }
1767
1768         if (tries->startAddr >= code->insnsSize) {
1769             LOGE("Invalid start_addr: 0x%x\n", tries->startAddr);
1770             return NULL;
1771         }
1772
1773         for (i = 0; i < handlersSize; i++) {
1774             if (tries->handlerOff == handlerOffs[i]) {
1775                 break;
1776             }
1777         }
1778
1779         if (i == handlersSize) {
1780             LOGE("Bogus handler offset: 0x%x\n", tries->handlerOff);
1781             return NULL;
1782         }
1783
1784         lastEnd = tries->startAddr + tries->insnCount;
1785
1786         if (lastEnd > code->insnsSize) {
1787             LOGE("Invalid insn_count: 0x%x (end addr 0x%x)\n",
1788                     tries->insnCount, lastEnd);
1789             return NULL;
1790         }
1791
1792         tries++;
1793     }
1794
1795     return (u1*) encodedHandlers + endOffset;
1796 }
1797
1798 /* Perform byte-swapping and intra-item verification on code_item. */
1799 static void* swapCodeItem(const CheckState* state, void* ptr) {
1800     DexCode* item = ptr;
1801     u2* insns;
1802     u4 count;
1803
1804     CHECK_PTR_RANGE(item, item + 1);
1805     SWAP_FIELD2(item->registersSize);
1806     SWAP_FIELD2(item->insSize);
1807     SWAP_FIELD2(item->outsSize);
1808     SWAP_FIELD2(item->triesSize);
1809     SWAP_OFFSET4(item->debugInfoOff);
1810     SWAP_FIELD4(item->insnsSize);
1811
1812     if (item->insSize > item->registersSize) {
1813         LOGE("insSize (%u) > registersSize (%u)\n", item->insSize,
1814                 item->registersSize);
1815         return NULL;
1816     }
1817
1818     if ((item->outsSize > 5) && (item->outsSize > item->registersSize)) {
1819         /*
1820          * It's okay for outsSize to be up to five, even if registersSize
1821          * is smaller, since the short forms of method invocation allow
1822          * repetition of a register multiple times within a single parameter
1823          * list. Longer parameter lists, though, need to be represented
1824          * in-order in the register file.
1825          */
1826         LOGE("outsSize (%u) > registersSize (%u)\n", item->outsSize,
1827                 item->registersSize);
1828         return NULL;
1829     }
1830
1831     count = item->insnsSize;
1832     insns = item->insns;
1833     CHECK_LIST_SIZE(insns, count, sizeof(u2));
1834
1835     while (count--) {
1836         *insns = SWAP2(*insns);
1837         insns++;
1838     }
1839
1840     if (item->triesSize == 0) {
1841         ptr = insns;
1842     } else {
1843         if ((((u4) insns) & 3) != 0) {
1844             // Four-byte alignment for the tries. Verify the spacer is a 0.
1845             if (*insns != 0) {
1846                 LOGE("Non-zero padding: 0x%x\n", (u4) *insns);
1847                 return NULL;
1848             }
1849         }
1850
1851         ptr = swapTriesAndCatches(state, item);
1852     }
1853
1854     return ptr;
1855 }
1856
1857 /* Perform intra-item verification on string_data_item. */
1858 static void* intraVerifyStringDataItem(const CheckState* state, void* ptr) {
1859     const u1* fileEnd = state->fileEnd;
1860     const u1* data = ptr;
1861     bool okay = true;
1862     u4 utf16Size = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
1863     u4 i;
1864
1865     if (!okay) {
1866         LOGE("Bogus utf16_size\n");
1867         return NULL;
1868     }
1869
1870     for (i = 0; i < utf16Size; i++) {
1871         if (data >= fileEnd) {
1872             LOGE("String data would go beyond end-of-file\n");
1873             return NULL;
1874         }
1875
1876         u1 byte1 = *(data++);
1877
1878         // Switch on the high four bits.
1879         switch (byte1 >> 4) {
1880             case 0x00: {
1881                 // Special case of bit pattern 0xxx.
1882                 if (byte1 == 0) {
1883                     LOGE("String shorter than indicated utf16_size 0x%x\n",
1884                             utf16Size);
1885                     return NULL;
1886                 }
1887                 break;
1888             }
1889             case 0x01:
1890             case 0x02:
1891             case 0x03:
1892             case 0x04:
1893             case 0x05:
1894             case 0x06:
1895             case 0x07: {
1896                 // Bit pattern 0xxx. No need for any extra bytes or checks.
1897                 break;
1898             }
1899             case 0x08:
1900             case 0x09:
1901             case 0x0a:
1902             case 0x0b:
1903             case 0x0f: {
1904                 /*
1905                  * Bit pattern 10xx or 1111, which are illegal start bytes.
1906                  * Note: 1111 is valid for normal UTF-8, but not the
1907                  * modified UTF-8 used here.
1908                  */
1909                 LOGE("Illegal start byte 0x%x\n", byte1);
1910                 return NULL;
1911             }
1912             case 0x0e: {
1913                 // Bit pattern 1110, so there are two additional bytes.
1914                 u1 byte2 = *(data++);
1915                 if ((byte2 & 0xc0) != 0x80) {
1916                     LOGE("Illegal continuation byte 0x%x\n", byte2);
1917                     return NULL;
1918                 }
1919                 u1 byte3 = *(data++);
1920                 if ((byte3 & 0xc0) != 0x80) {
1921                     LOGE("Illegal continuation byte 0x%x\n", byte3);
1922                     return NULL;
1923                 }
1924                 u2 value = ((byte1 & 0x0f) << 12) | ((byte2 & 0x3f) << 6)
1925                     | (byte3 & 0x3f);
1926                 if (value < 0x800) {
1927                     LOGE("Illegal representation for value %x\n", value);
1928                     return NULL;
1929                 }
1930                 break;
1931             }
1932             case 0x0c:
1933             case 0x0d: {
1934                 // Bit pattern 110x, so there is one additional byte.
1935                 u1 byte2 = *(data++);
1936                 if ((byte2 & 0xc0) != 0x80) {
1937                     LOGE("Illegal continuation byte 0x%x\n", byte2);
1938                     return NULL;
1939                 }
1940                 u2 value = ((byte1 & 0x1f) << 6) | (byte2 & 0x3f);
1941                 if ((value != 0) && (value < 0x80)) {
1942                     LOGE("Illegal representation for value %x\n", value);
1943                     return NULL;
1944                 }
1945                 break;
1946             }
1947         }
1948     }
1949
1950     if (*(data++) != '\0') {
1951         LOGE("String longer than indicated utf16_size 0x%x\n", utf16Size);
1952         return NULL;
1953     }
1954
1955     return (void*) data;
1956 }
1957
1958 /* Perform intra-item verification on debug_info_item. */
1959 static void* intraVerifyDebugInfoItem(const CheckState* state, void* ptr) {
1960     const u1* fileEnd = state->fileEnd;
1961     const u1* data = ptr;
1962     bool okay = true;
1963     u4 i;
1964
1965     readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
1966
1967     if (!okay) {
1968         LOGE("Bogus line_start\n");
1969         return NULL;
1970     }
1971
1972     u4 parametersSize =
1973         readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
1974
1975     if (!okay) {
1976         LOGE("Bogus parameters_size\n");
1977         return NULL;
1978     }
1979
1980     if (parametersSize > 65536) {
1981         LOGE("Invalid parameters_size: 0x%x\n", parametersSize);
1982         return NULL;
1983     }
1984
1985     for (i = 0; i < parametersSize; i++) {
1986         u4 parameterName =
1987             readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
1988
1989         if (!okay) {
1990             LOGE("Bogus parameter_name\n");
1991             return NULL;
1992         }
1993
1994         if (parameterName != 0) {
1995             parameterName--;
1996             CHECK_INDEX(parameterName, state->pHeader->stringIdsSize);
1997         }
1998     }
1999
2000     bool done = false;
2001     while (!done) {
2002         u1 opcode = *(data++);
2003
2004         switch (opcode) {
2005             case DBG_END_SEQUENCE: {
2006                 done = true;
2007                 break;
2008             }
2009             case DBG_ADVANCE_PC: {
2010                 readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
2011                 break;
2012             }
2013             case DBG_ADVANCE_LINE: {
2014                 readAndVerifySignedLeb128(&data, fileEnd, &okay);
2015                 break;
2016             }
2017             case DBG_START_LOCAL: {
2018                 u4 idx;
2019                 u4 regNum = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
2020                 if (!okay) break;
2021                 if (regNum >= 65536) {
2022                     okay = false;
2023                     break;
2024                 }
2025                 idx = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
2026                 if (!okay) break;
2027                 if (idx != 0) {
2028                     idx--;
2029                     CHECK_INDEX(idx, state->pHeader->stringIdsSize);
2030                 }
2031                 idx = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
2032                 if (!okay) break;
2033                 if (idx != 0) {
2034                     idx--;
2035                     CHECK_INDEX(idx, state->pHeader->stringIdsSize);
2036                 }
2037                 break;
2038             }
2039             case DBG_END_LOCAL:
2040             case DBG_RESTART_LOCAL: {
2041                 u4 regNum = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
2042                 if (!okay) break;
2043                 if (regNum >= 65536) {
2044                     okay = false;
2045                     break;
2046                 }
2047                 break;
2048             }
2049             case DBG_START_LOCAL_EXTENDED: {
2050                 u4 idx;
2051                 u4 regNum = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
2052                 if (!okay) break;
2053                 if (regNum >= 65536) {
2054                     okay = false;
2055                     break;
2056                 }
2057                 idx = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
2058                 if (!okay) break;
2059                 if (idx != 0) {
2060                     idx--;
2061                     CHECK_INDEX(idx, state->pHeader->stringIdsSize);
2062                 }
2063                 idx = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
2064                 if (!okay) break;
2065                 if (idx != 0) {
2066                     idx--;
2067                     CHECK_INDEX(idx, state->pHeader->stringIdsSize);
2068                 }
2069                 idx = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
2070                 if (!okay) break;
2071                 if (idx != 0) {
2072                     idx--;
2073                     CHECK_INDEX(idx, state->pHeader->stringIdsSize);
2074                 }
2075                 break;
2076             }
2077             case DBG_SET_FILE: {
2078                 u4 idx = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
2079                 if (!okay) break;
2080                 if (idx != 0) {
2081                     idx--;
2082                     CHECK_INDEX(idx, state->pHeader->stringIdsSize);
2083                 }
2084                 break;
2085             }
2086             default: {
2087                 // No arguments to parse for anything else.
2088             }
2089         }
2090
2091         if (!okay) {
2092             LOGE("Bogus syntax for opcode %02x\n", opcode);
2093             return NULL;
2094         }
2095     }
2096
2097     return (void*) data;
2098 }
2099
2100 /* defined below */
2101 static const u1* verifyEncodedValue(const CheckState* state, const u1* data,
2102         bool crossVerify);
2103 static const u1* verifyEncodedAnnotation(const CheckState* state,
2104         const u1* data, bool crossVerify);
2105
2106 /* Helper for verifyEncodedValue(), which reads a 1- to 4- byte unsigned
2107  * little endian value. */
2108 static u4 readUnsignedLittleEndian(const CheckState* state, const u1** pData,
2109         u4 size) {
2110     const u1* data = *pData;
2111     u4 result = 0;
2112     u4 i;
2113
2114     CHECK_PTR_RANGE(data, data + size);
2115
2116     for (i = 0; i < size; i++) {
2117         result |= ((u4) *(data++)) << (i * 8);
2118     }
2119
2120     *pData = data;
2121     return result;
2122 }
2123
2124 /* Helper for *VerifyAnnotationItem() and *VerifyEncodedArrayItem(), which
2125  * verifies an encoded_array. */
2126 static const u1* verifyEncodedArray(const CheckState* state,
2127         const u1* data, bool crossVerify) {
2128     bool okay = true;
2129     u4 size = readAndVerifyUnsignedLeb128(&data, state->fileEnd, &okay);
2130
2131     if (!okay) {
2132         LOGE("Bogus encoded_array size\n");
2133         return NULL;
2134     }
2135
2136     while (size--) {
2137         data = verifyEncodedValue(state, data, crossVerify);
2138         if (data == NULL) {
2139             LOGE("Bogus encoded_array value\n");
2140             return NULL;
2141         }
2142     }
2143
2144     return data;
2145 }
2146
2147 /* Helper for *VerifyAnnotationItem() and *VerifyEncodedArrayItem(), which
2148  * verifies an encoded_value. */
2149 static const u1* verifyEncodedValue(const CheckState* state,
2150         const u1* data, bool crossVerify) {
2151     CHECK_PTR_RANGE(data, data + 1);
2152
2153     u1 headerByte = *(data++);
2154     u4 valueType = headerByte & kDexAnnotationValueTypeMask;
2155     u4 valueArg = headerByte >> kDexAnnotationValueArgShift;
2156
2157     switch (valueType) {
2158         case kDexAnnotationByte: {
2159             if (valueArg != 0) {
2160                 LOGE("Bogus byte size 0x%x\n", valueArg);
2161                 return NULL;
2162             }
2163             data++;
2164             break;
2165         }
2166         case kDexAnnotationShort:
2167         case kDexAnnotationChar: {
2168             if (valueArg > 1) {
2169                 LOGE("Bogus char/short size 0x%x\n", valueArg);
2170                 return NULL;
2171             }
2172             data += valueArg + 1;
2173             break;
2174         }
2175         case kDexAnnotationInt:
2176         case kDexAnnotationFloat: {
2177             if (valueArg > 3) {
2178                 LOGE("Bogus int/float size 0x%x\n", valueArg);
2179                 return NULL;
2180             }
2181             data += valueArg + 1;
2182             break;
2183         }
2184         case kDexAnnotationLong:
2185         case kDexAnnotationDouble: {
2186             data += valueArg + 1;
2187             break;
2188         }
2189         case kDexAnnotationString: {
2190             if (valueArg > 3) {
2191                 LOGE("Bogus string size 0x%x\n", valueArg);
2192                 return NULL;
2193             }
2194             u4 idx = readUnsignedLittleEndian(state, &data, valueArg + 1);
2195             CHECK_INDEX(idx, state->pHeader->stringIdsSize);
2196             break;
2197         }
2198         case kDexAnnotationType: {
2199             if (valueArg > 3) {
2200                 LOGE("Bogus type size 0x%x\n", valueArg);
2201                 return NULL;
2202             }
2203             u4 idx = readUnsignedLittleEndian(state, &data, valueArg + 1);
2204             CHECK_INDEX(idx, state->pHeader->typeIdsSize);
2205             break;
2206         }
2207         case kDexAnnotationField:
2208         case kDexAnnotationEnum: {
2209             if (valueArg > 3) {
2210                 LOGE("Bogus field/enum size 0x%x\n", valueArg);
2211                 return NULL;
2212             }
2213             u4 idx = readUnsignedLittleEndian(state, &data, valueArg + 1);
2214             CHECK_INDEX(idx, state->pHeader->fieldIdsSize);
2215             break;
2216         }
2217         case kDexAnnotationMethod: {
2218             if (valueArg > 3) {
2219                 LOGE("Bogus method size 0x%x\n", valueArg);
2220                 return NULL;
2221             }
2222             u4 idx = readUnsignedLittleEndian(state, &data, valueArg + 1);
2223             CHECK_INDEX(idx, state->pHeader->methodIdsSize);
2224             break;
2225         }
2226         case kDexAnnotationArray: {
2227             if (valueArg != 0) {
2228                 LOGE("Bogus array value_arg 0x%x\n", valueArg);
2229                 return NULL;
2230             }
2231             data = verifyEncodedArray(state, data, crossVerify);
2232             break;
2233         }
2234         case kDexAnnotationAnnotation: {
2235             if (valueArg != 0) {
2236                 LOGE("Bogus annotation value_arg 0x%x\n", valueArg);
2237                 return NULL;
2238             }
2239             data = verifyEncodedAnnotation(state, data, crossVerify);
2240             break;
2241         }
2242         case kDexAnnotationNull: {
2243             if (valueArg != 0) {
2244                 LOGE("Bogus null value_arg 0x%x\n", valueArg);
2245                 return NULL;
2246             }
2247             // Nothing else to do for this type.
2248             break;
2249         }
2250         case kDexAnnotationBoolean: {
2251             if (valueArg > 1) {
2252                 LOGE("Bogus boolean value_arg 0x%x\n", valueArg);
2253                 return NULL;
2254             }
2255             // Nothing else to do for this type.
2256             break;
2257         }
2258         default: {
2259             LOGE("Bogus value_type 0x%x\n", valueType);
2260             return NULL;
2261         }
2262     }
2263
2264     return data;
2265 }
2266
2267 /* Helper for *VerifyAnnotationItem() and *VerifyEncodedArrayItem(), which
2268  * verifies an encoded_annotation. */
2269 static const u1* verifyEncodedAnnotation(const CheckState* state,
2270         const u1* data, bool crossVerify) {
2271     const u1* fileEnd = state->fileEnd;
2272     bool okay = true;
2273     u4 idx = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
2274
2275     if (!okay) {
2276         LOGE("Bogus encoded_annotation type_idx\n");
2277         return NULL;
2278     }
2279
2280     CHECK_INDEX(idx, state->pHeader->typeIdsSize);
2281
2282     if (crossVerify) {
2283         const char* descriptor = dexStringByTypeIdx(state->pDexFile, idx);
2284         if (!dexIsClassDescriptor(descriptor)) {
2285             LOGE("Bogus annotation type: '%s'\n", descriptor);
2286             return NULL;
2287         }
2288     }
2289
2290     u4 size = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
2291     u4 lastIdx = 0;
2292     bool first = true;
2293
2294     if (!okay) {
2295         LOGE("Bogus encoded_annotation size\n");
2296         return NULL;
2297     }
2298
2299     while (size--) {
2300         idx = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
2301
2302         if (!okay) {
2303             LOGE("Bogus encoded_annotation name_idx\n");
2304             return NULL;
2305         }
2306
2307         CHECK_INDEX(idx, state->pHeader->stringIdsSize);
2308
2309         if (crossVerify) {
2310             const char* name = dexStringById(state->pDexFile, idx);
2311             if (!dexIsValidMemberName(name)) {
2312                 LOGE("Bogus annotation member name: '%s'\n", name);
2313                 return NULL;
2314             }
2315         }
2316
2317         if (first) {
2318             first = false;
2319         } else if (lastIdx >= idx) {
2320             LOGE("Out-of-order encoded_annotation name_idx: 0x%x then 0x%x\n",
2321                     lastIdx, idx);
2322             return NULL;
2323         }
2324
2325         data = verifyEncodedValue(state, data, crossVerify);
2326         lastIdx = idx;
2327
2328         if (data == NULL) {
2329             return NULL;
2330         }
2331     }
2332
2333     return data;
2334 }
2335
2336 /* Perform intra-item verification on encoded_array_item. */
2337 static void* intraVerifyEncodedArrayItem(const CheckState* state, void* ptr) {
2338     return (void*) verifyEncodedArray(state, (const u1*) ptr, false);
2339 }
2340
2341 /* Perform intra-item verification on annotation_item. */
2342 static void* intraVerifyAnnotationItem(const CheckState* state, void* ptr) {
2343     const u1* data = ptr;
2344
2345     CHECK_PTR_RANGE(data, data + 1);
2346
2347     switch (*(data++)) {
2348         case kDexVisibilityBuild:
2349         case kDexVisibilityRuntime:
2350         case kDexVisibilitySystem: {
2351             break;
2352         }
2353         default: {
2354             LOGE("Bogus annotation visibility: 0x%x\n", *data);
2355             return NULL;
2356         }
2357     }
2358
2359     return (void*) verifyEncodedAnnotation(state, data, false);
2360 }
2361
2362 /* Perform cross-item verification on annotation_item. */
2363 static void* crossVerifyAnnotationItem(const CheckState* state, void* ptr) {
2364     const u1* data = ptr;
2365
2366     // Skip the visibility byte.
2367     data++;
2368
2369     return (void*) verifyEncodedAnnotation(state, data, true);
2370 }
2371
2372
2373
2374
2375 /*
2376  * Function to visit an individual top-level item type.
2377  */
2378 typedef void* ItemVisitorFunction(const CheckState* state, void* ptr);
2379
2380 /*
2381  * Iterate over all the items in a section, optionally updating the
2382  * data map (done if mapType is passed as non-negative). The section
2383  * must consist of concatenated items of the same type.
2384  */
2385 static bool iterateSectionWithOptionalUpdate(CheckState* state,
2386         u4 offset, u4 count, ItemVisitorFunction* func, u4 alignment,
2387         u4* nextOffset, int mapType) {
2388     u4 alignmentMask = alignment - 1;
2389     u4 i;
2390
2391     state->previousItem = NULL;
2392
2393     for (i = 0; i < count; i++) {
2394         u4 newOffset = (offset + alignmentMask) & ~alignmentMask;
2395         u1* ptr = filePointer(state, newOffset);
2396
2397         if (offset < newOffset) {
2398             ptr = filePointer(state, offset);
2399             if (offset < newOffset) {
2400                 CHECK_OFFSET_RANGE(offset, newOffset);
2401                 while (offset < newOffset) {
2402                     if (*ptr != '\0') {
2403                         LOGE("Non-zero padding 0x%02x @ %x\n", *ptr, offset);
2404                         return false;
2405                     }
2406                     ptr++;
2407                     offset++;
2408                 }
2409             }
2410         }
2411
2412         u1* newPtr = (u1*) func(state, ptr);
2413         newOffset = fileOffset(state, newPtr);
2414
2415         if (newPtr == NULL) {
2416             LOGE("Trouble with item %d @ offset 0x%x\n", i, offset);
2417             return false;
2418         }
2419
2420         if (newOffset > state->fileLen) {
2421             LOGE("Item %d @ offset 0x%x ends out of bounds\n", i, offset);
2422             return false;
2423         }
2424
2425         if (mapType >= 0) {
2426             dexDataMapAdd(state->pDataMap, offset, mapType);
2427         }
2428
2429         state->previousItem = ptr;
2430         offset = newOffset;
2431     }
2432
2433     if (nextOffset != NULL) {
2434         *nextOffset = offset;
2435     }
2436
2437     return true;
2438 }
2439
2440 /*
2441  * Iterate over all the items in a section. The section must consist of
2442  * concatenated items of the same type. This variant will not update the data
2443  * map.
2444  */
2445 static bool iterateSection(CheckState* state, u4 offset, u4 count,
2446         ItemVisitorFunction* func, u4 alignment, u4* nextOffset) {
2447     return iterateSectionWithOptionalUpdate(state, offset, count, func,
2448             alignment, nextOffset, -1);
2449 }
2450
2451 /*
2452  * Like iterateSection(), but also check that the offset and count match
2453  * a given pair of expected values.
2454  */
2455 static bool checkBoundsAndIterateSection(CheckState* state,
2456         u4 offset, u4 count, u4 expectedOffset, u4 expectedCount,
2457         ItemVisitorFunction* func, u4 alignment, u4* nextOffset) {
2458     if (offset != expectedOffset) {
2459         LOGE("Bogus offset for section: got 0x%x; expected 0x%x\n",
2460                 offset, expectedOffset);
2461         return false;
2462     }
2463
2464     if (count != expectedCount) {
2465         LOGE("Bogus size for section: got 0x%x; expected 0x%x\n",
2466                 count, expectedCount);
2467         return false;
2468     }
2469
2470     return iterateSection(state, offset, count, func, alignment, nextOffset);
2471 }
2472
2473 /*
2474  * Like iterateSection(), but also update the data section map and
2475  * check that all the items fall within the data section.
2476  */
2477 static bool iterateDataSection(CheckState* state, u4 offset, u4 count,
2478         ItemVisitorFunction* func, u4 alignment, u4* nextOffset, int mapType) {
2479     u4 dataStart = state->pHeader->dataOff;
2480     u4 dataEnd = dataStart + state->pHeader->dataSize;
2481
2482     assert(nextOffset != NULL);
2483
2484     if ((offset < dataStart) || (offset >= dataEnd)) {
2485         LOGE("Bogus offset for data subsection: 0x%x\n", offset);
2486         return false;
2487     }
2488
2489     if (!iterateSectionWithOptionalUpdate(state, offset, count, func,
2490                     alignment, nextOffset, mapType)) {
2491         return false;
2492     }
2493
2494     if (*nextOffset > dataEnd) {
2495         LOGE("Out-of-bounds end of data subsection: 0x%x\n", *nextOffset);
2496         return false;
2497     }
2498
2499     return true;
2500 }
2501
2502 /*
2503  * Byte-swap all items in the given map except the header and the map
2504  * itself, both of which should have already gotten swapped. This also
2505  * does all possible intra-item verification, that is, verification
2506  * that doesn't need to assume the sanctity of the contents of *other*
2507  * items. The intra-item limitation is because at the time an item is
2508  * asked to verify itself, it can't assume that the items it refers to
2509  * have been byte-swapped and verified.
2510  */
2511 static bool swapEverythingButHeaderAndMap(CheckState* state,
2512         DexMapList* pMap) {
2513     const DexMapItem* item = pMap->list;
2514     u4 lastOffset = 0;
2515     u4 count = pMap->size;
2516     bool okay = true;
2517
2518     while (okay && count--) {
2519         u4 sectionOffset = item->offset;
2520         u4 sectionCount = item->size;
2521         u2 type = item->type;
2522
2523         if (lastOffset < sectionOffset) {
2524             CHECK_OFFSET_RANGE(lastOffset, sectionOffset);
2525             const u1* ptr = filePointer(state, lastOffset);
2526             while (lastOffset < sectionOffset) {
2527                 if (*ptr != '\0') {
2528                     LOGE("Non-zero padding 0x%02x before section start @ %x\n",
2529                             *ptr, lastOffset);
2530                     okay = false;
2531                     break;
2532                 }
2533                 ptr++;
2534                 lastOffset++;
2535             }
2536         } else if (lastOffset > sectionOffset) {
2537             LOGE("Section overlap or out-of-order map: %x, %x\n",
2538                     lastOffset, sectionOffset);
2539             okay = false;
2540         }
2541
2542         if (!okay) {
2543             break;
2544         }
2545
2546         switch (type) {
2547             case kDexTypeHeaderItem: {
2548                 /*
2549                  * The header got swapped very early on, but do some
2550                  * additional sanity checking here.
2551                  */
2552                 okay = checkHeaderSection(state, sectionOffset, sectionCount,
2553                         &lastOffset);
2554                 break;
2555             }
2556             case kDexTypeStringIdItem: {
2557                 okay = checkBoundsAndIterateSection(state, sectionOffset,
2558                         sectionCount, state->pHeader->stringIdsOff,
2559                         state->pHeader->stringIdsSize, swapStringIdItem,
2560                         sizeof(u4), &lastOffset);
2561                 break;
2562             }
2563             case kDexTypeTypeIdItem: {
2564                 okay = checkBoundsAndIterateSection(state, sectionOffset,
2565                         sectionCount, state->pHeader->typeIdsOff,
2566                         state->pHeader->typeIdsSize, swapTypeIdItem,
2567                         sizeof(u4), &lastOffset);
2568                 break;
2569             }
2570             case kDexTypeProtoIdItem: {
2571                 okay = checkBoundsAndIterateSection(state, sectionOffset,
2572                         sectionCount, state->pHeader->protoIdsOff,
2573                         state->pHeader->protoIdsSize, swapProtoIdItem,
2574                         sizeof(u4), &lastOffset);
2575                 break;
2576             }
2577             case kDexTypeFieldIdItem: {
2578                 okay = checkBoundsAndIterateSection(state, sectionOffset,
2579                         sectionCount, state->pHeader->fieldIdsOff,
2580                         state->pHeader->fieldIdsSize, swapFieldIdItem,
2581                         sizeof(u4), &lastOffset);
2582                 break;
2583             }
2584             case kDexTypeMethodIdItem: {
2585                 okay = checkBoundsAndIterateSection(state, sectionOffset,
2586                         sectionCount, state->pHeader->methodIdsOff,
2587                         state->pHeader->methodIdsSize, swapMethodIdItem,
2588                         sizeof(u4), &lastOffset);
2589                 break;
2590             }
2591             case kDexTypeClassDefItem: {
2592                 okay = checkBoundsAndIterateSection(state, sectionOffset,
2593                         sectionCount, state->pHeader->classDefsOff,
2594                         state->pHeader->classDefsSize, swapClassDefItem,
2595                         sizeof(u4), &lastOffset);
2596                 break;
2597             }
2598             case kDexTypeMapList: {
2599                 /*
2600                  * The map section was swapped early on, but do some
2601                  * additional sanity checking here.
2602                  */
2603                 okay = checkMapSection(state, sectionOffset, sectionCount,
2604                         &lastOffset);
2605                 break;
2606             }
2607             case kDexTypeTypeList: {
2608                 okay = iterateDataSection(state, sectionOffset, sectionCount,
2609                         swapTypeList, sizeof(u4), &lastOffset, type);
2610                 break;
2611             }
2612             case kDexTypeAnnotationSetRefList: {
2613                 okay = iterateDataSection(state, sectionOffset, sectionCount,
2614                         swapAnnotationSetRefList, sizeof(u4), &lastOffset,
2615                         type);
2616                 break;
2617             }
2618             case kDexTypeAnnotationSetItem: {
2619                 okay = iterateDataSection(state, sectionOffset, sectionCount,
2620                         swapAnnotationSetItem, sizeof(u4), &lastOffset, type);
2621                 break;
2622             }
2623             case kDexTypeClassDataItem: {
2624                 okay = iterateDataSection(state, sectionOffset, sectionCount,
2625                         intraVerifyClassDataItem, sizeof(u1), &lastOffset,
2626                         type);
2627                 break;
2628             }
2629             case kDexTypeCodeItem: {
2630                 okay = iterateDataSection(state, sectionOffset, sectionCount,
2631                         swapCodeItem, sizeof(u4), &lastOffset, type);
2632                 break;
2633             }
2634             case kDexTypeStringDataItem: {
2635                 okay = iterateDataSection(state, sectionOffset, sectionCount,
2636                         intraVerifyStringDataItem, sizeof(u1), &lastOffset,
2637                         type);
2638                 break;
2639             }
2640             case kDexTypeDebugInfoItem: {
2641                 okay = iterateDataSection(state, sectionOffset, sectionCount,
2642                         intraVerifyDebugInfoItem, sizeof(u1), &lastOffset,
2643                         type);
2644                 break;
2645             }
2646             case kDexTypeAnnotationItem: {
2647                 okay = iterateDataSection(state, sectionOffset, sectionCount,
2648                         intraVerifyAnnotationItem, sizeof(u1), &lastOffset,
2649                         type);
2650                 break;
2651             }
2652             case kDexTypeEncodedArrayItem: {
2653                 okay = iterateDataSection(state, sectionOffset, sectionCount,
2654                         intraVerifyEncodedArrayItem, sizeof(u1), &lastOffset,
2655                         type);
2656                 break;
2657             }
2658             case kDexTypeAnnotationsDirectoryItem: {
2659                 okay = iterateDataSection(state, sectionOffset, sectionCount,
2660                         swapAnnotationsDirectoryItem, sizeof(u4), &lastOffset,
2661                         type);
2662                 break;
2663             }
2664             default: {
2665                 LOGE("Unknown map item type %04x\n", type);
2666                 return false;
2667             }
2668         }
2669
2670         if (!okay) {
2671             LOGE("Swap of section type %04x failed\n", type);
2672         }
2673
2674         item++;
2675     }
2676
2677     return okay;
2678 }
2679
2680 /*
2681  * Perform cross-item verification on everything that needs it. This
2682  * pass is only called after all items are byte-swapped and
2683  * intra-verified (checked for internal consistency).
2684  */
2685 static bool crossVerifyEverything(CheckState* state, DexMapList* pMap)
2686 {
2687     const DexMapItem* item = pMap->list;
2688     u4 count = pMap->size;
2689     bool okay = true;
2690
2691     while (okay && count--) {
2692         u4 sectionOffset = item->offset;
2693         u4 sectionCount = item->size;
2694
2695         switch (item->type) {
2696             case kDexTypeHeaderItem:
2697             case kDexTypeMapList:
2698             case kDexTypeTypeList:
2699             case kDexTypeCodeItem:
2700             case kDexTypeStringDataItem:
2701             case kDexTypeDebugInfoItem:
2702             case kDexTypeAnnotationItem:
2703             case kDexTypeEncodedArrayItem: {
2704                 // There is no need for cross-item verification for these.
2705                 break;
2706             }
2707             case kDexTypeStringIdItem: {
2708                 okay = iterateSection(state, sectionOffset, sectionCount,
2709                         crossVerifyStringIdItem, sizeof(u4), NULL);
2710                 break;
2711             }
2712             case kDexTypeTypeIdItem: {
2713                 okay = iterateSection(state, sectionOffset, sectionCount,
2714                         crossVerifyTypeIdItem, sizeof(u4), NULL);
2715                 break;
2716             }
2717             case kDexTypeProtoIdItem: {
2718                 okay = iterateSection(state, sectionOffset, sectionCount,
2719                         crossVerifyProtoIdItem, sizeof(u4), NULL);
2720                 break;
2721             }
2722             case kDexTypeFieldIdItem: {
2723                 okay = iterateSection(state, sectionOffset, sectionCount,
2724                         crossVerifyFieldIdItem, sizeof(u4), NULL);
2725                 break;
2726             }
2727             case kDexTypeMethodIdItem: {
2728                 okay = iterateSection(state, sectionOffset, sectionCount,
2729                         crossVerifyMethodIdItem, sizeof(u4), NULL);
2730                 break;
2731             }
2732             case kDexTypeClassDefItem: {
2733                 // Allocate (on the stack) the "observed class_def" bits.
2734                 size_t arraySize = calcDefinedClassBitsSize(state);
2735                 u4 definedClassBits[arraySize];
2736                 memset(definedClassBits, 0, arraySize * sizeof(u4));
2737                 state->pDefinedClassBits = definedClassBits;
2738
2739                 okay = iterateSection(state, sectionOffset, sectionCount,
2740                         crossVerifyClassDefItem, sizeof(u4), NULL);
2741
2742                 state->pDefinedClassBits = NULL;
2743                 break;
2744             }
2745             case kDexTypeAnnotationSetRefList: {
2746                 okay = iterateSection(state, sectionOffset, sectionCount,
2747                         crossVerifyAnnotationSetRefList, sizeof(u4), NULL);
2748                 break;
2749             }
2750             case kDexTypeAnnotationSetItem: {
2751                 okay = iterateSection(state, sectionOffset, sectionCount,
2752                         crossVerifyAnnotationSetItem, sizeof(u4), NULL);
2753                 break;
2754             }
2755             case kDexTypeClassDataItem: {
2756                 okay = iterateSection(state, sectionOffset, sectionCount,
2757                         crossVerifyClassDataItem, sizeof(u1), NULL);
2758                 break;
2759             }
2760             case kDexTypeAnnotationsDirectoryItem: {
2761                 okay = iterateSection(state, sectionOffset, sectionCount,
2762                         crossVerifyAnnotationsDirectoryItem, sizeof(u4), NULL);
2763                 break;
2764             }
2765             default: {
2766                 LOGE("Unknown map item type %04x\n", item->type);
2767                 return false;
2768             }
2769         }
2770
2771         if (!okay) {
2772             LOGE("Cross-item verify of section type %04x failed\n",
2773                     item->type);
2774         }
2775
2776         item++;
2777     }
2778
2779     return okay;
2780 }
2781
2782 /*
2783  * Fix the byte ordering of all fields in the DEX file, and do
2784  * structural verification. This is only required for code that opens
2785  * "raw" DEX files, such as the DEX optimizer.
2786  *
2787  * Returns 0 on success, nonzero on failure.
2788  */
2789 int dexSwapAndVerify(u1* addr, int len)
2790 {
2791     DexHeader* pHeader;
2792     CheckState state;
2793     bool okay = true;
2794
2795     memset(&state, 0, sizeof(state));
2796     LOGV("+++ swapping and verifying\n");
2797
2798     /*
2799      * Start by verifying the magic number.  The caller verified that "len"
2800      * says we have at least a header's worth of data.
2801      */
2802     pHeader = (DexHeader*) addr;
2803     if (memcmp(pHeader->magic, DEX_MAGIC, 4) != 0) {
2804         /* really shouldn't be here -- this is weird */
2805         LOGE("ERROR: Can't byte swap: bad magic number "
2806                 "(0x%02x %02x %02x %02x)\n",
2807              pHeader->magic[0], pHeader->magic[1],
2808              pHeader->magic[2], pHeader->magic[3]);
2809         okay = false;
2810     }
2811
2812     if (okay && memcmp(pHeader->magic+4, DEX_MAGIC_VERS, 4) != 0) {
2813         /* older or newer version we don't know how to read */
2814         LOGE("ERROR: Can't byte swap: bad dex version "
2815                 "(0x%02x %02x %02x %02x)\n",
2816              pHeader->magic[4], pHeader->magic[5],
2817              pHeader->magic[6], pHeader->magic[7]);
2818         okay = false;
2819     }
2820
2821     if (okay) {
2822         int expectedLen = (int) SWAP4(pHeader->fileSize);
2823         if (len < expectedLen) {
2824             LOGE("ERROR: Bad length: expected %d, got %d\n", expectedLen, len);
2825             okay = false;
2826         } else if (len != expectedLen) {
2827             LOGW("WARNING: Odd length: expected %d, got %d\n", expectedLen,
2828                     len);
2829             // keep going
2830         }
2831     }
2832
2833     if (okay) {
2834         /*
2835          * Compute the adler32 checksum and compare it to what's stored in
2836          * the file.  This isn't free, but chances are good that we just
2837          * unpacked this from a jar file and have all of the pages sitting
2838          * in memory, so it's pretty quick.
2839          *
2840          * This might be a big-endian system, so we need to do this before
2841          * we byte-swap the header.
2842          */
2843         uLong adler = adler32(0L, Z_NULL, 0);
2844         const int nonSum = sizeof(pHeader->magic) + sizeof(pHeader->checksum);
2845         u4 storedFileSize = SWAP4(pHeader->fileSize);
2846         u4 expectedChecksum = SWAP4(pHeader->checksum);
2847
2848         adler = adler32(adler, ((const u1*) pHeader) + nonSum,
2849                     storedFileSize - nonSum);
2850
2851         if (adler != expectedChecksum) {
2852             LOGE("ERROR: bad checksum (%08lx, expected %08x)\n",
2853                 adler, expectedChecksum);
2854             okay = false;
2855         }
2856     }
2857
2858     if (okay) {
2859         state.fileStart = addr;
2860         state.fileEnd = addr + len;
2861         state.fileLen = len;
2862         state.pDexFile = NULL;
2863         state.pDataMap = NULL;
2864         state.pDefinedClassBits = NULL;
2865         state.previousItem = NULL;
2866
2867         /*
2868          * Swap the header and check the contents.
2869          */
2870         okay = swapDexHeader(&state, pHeader);
2871     }
2872
2873     if (okay) {
2874         state.pHeader = pHeader;
2875
2876         if (pHeader->headerSize < sizeof(DexHeader)) {
2877             LOGE("ERROR: Small header size %d, struct %d\n",
2878                     pHeader->headerSize, (int) sizeof(DexHeader));
2879             okay = false;
2880         } else if (pHeader->headerSize > sizeof(DexHeader)) {
2881             LOGW("WARNING: Large header size %d, struct %d\n",
2882                     pHeader->headerSize, (int) sizeof(DexHeader));
2883             // keep going?
2884         }
2885     }
2886
2887     if (okay) {
2888         /*
2889          * Look for the map. Swap it and then use it to find and swap
2890          * everything else.
2891          */
2892         if (pHeader->mapOff != 0) {
2893             DexFile dexFile;
2894             DexMapList* pDexMap = (DexMapList*) (addr + pHeader->mapOff);
2895
2896             okay = okay && swapMap(&state, pDexMap);
2897             okay = okay && swapEverythingButHeaderAndMap(&state, pDexMap);
2898
2899             dexFileSetupBasicPointers(&dexFile, addr);
2900             state.pDexFile = &dexFile;
2901
2902             okay = okay && crossVerifyEverything(&state, pDexMap);
2903         } else {
2904             LOGE("ERROR: No map found; impossible to byte-swap and verify");
2905             okay = false;
2906         }
2907     }
2908
2909     if (!okay) {
2910         LOGE("ERROR: Byte swap + verify failed\n");
2911     }
2912
2913     if (state.pDataMap != NULL) {
2914         dexDataMapFree(state.pDataMap);
2915     }
2916
2917     return !okay;       // 0 == success
2918 }
2919
2920 /*
2921  * Detect the file type of the given memory buffer via magic number.
2922  * Call dexSwapAndVerify() on an unoptimized DEX file, do nothing
2923  * but return successfully on an optimized DEX file, and report an
2924  * error for all other cases.
2925  *
2926  * Returns 0 on success, nonzero on failure.
2927  */
2928 int dexSwapAndVerifyIfNecessary(u1* addr, int len)
2929 {
2930     if (memcmp(addr, DEX_OPT_MAGIC, 4) == 0) {
2931         // It is an optimized dex file.
2932         return 0;
2933     }
2934
2935     if (memcmp(addr, DEX_MAGIC, 4) == 0) {
2936         // It is an unoptimized dex file.
2937         return dexSwapAndVerify(addr, len);
2938     }
2939
2940     LOGE("ERROR: Bad magic number (0x%02x %02x %02x %02x)\n",
2941              addr[0], addr[1], addr[2], addr[3]);
2942
2943     return 1;
2944 }