DexVerify.cpp revision c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2ef 
1/*
2 * Copyright (C) 2008 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17/*
18 * Dalvik classfile verification.  This file contains the verifier entry
19 * points and the static constraint checks.
20 */
21#include "Dalvik.h"
22#include "analysis/CodeVerify.h"
23#include "libdex/DexCatch.h"
24
25
26/* fwd */
27static bool verifyMethod(Method* meth);
28static bool verifyInstructions(VerifierData* vdata);
29
30
31/*
32 * Verify a class.
33 *
34 * By the time we get here, the value of gDvm.classVerifyMode should already
35 * have been factored in.  If you want to call into the verifier even
36 * though verification is disabled, that's your business.
37 *
38 * Returns "true" on success.
39 */
40bool dvmVerifyClass(ClassObject* clazz)
41{
42    int i;
43
44    if (dvmIsClassVerified(clazz)) {
45        ALOGD("Ignoring duplicate verify attempt on %s", clazz->descriptor);
46        return true;
47    }
48
49    for (i = 0; i < clazz->directMethodCount; i++) {
50        if (!verifyMethod(&clazz->directMethods[i])) {
51            LOG_VFY("Verifier rejected class %s", clazz->descriptor);
52            return false;
53        }
54    }
55    for (i = 0; i < clazz->virtualMethodCount; i++) {
56        if (!verifyMethod(&clazz->virtualMethods[i])) {
57            LOG_VFY("Verifier rejected class %s", clazz->descriptor);
58            return false;
59        }
60    }
61
62    return true;
63}
64
65
66/*
67 * Compute the width of the instruction at each address in the instruction
68 * stream, and store it in vdata->insnFlags.  Addresses that are in the
69 * middle of an instruction, or that are part of switch table data, are not
70 * touched (so the caller should probably initialize "insnFlags" to zero).
71 *
72 * The "newInstanceCount" and "monitorEnterCount" fields in vdata are
73 * also set.
74 *
75 * Performs some static checks, notably:
76 * - opcode of first instruction begins at index 0
77 * - only documented instructions may appear
78 * - each instruction follows the last
79 * - last byte of last instruction is at (code_length-1)
80 *
81 * Logs an error and returns "false" on failure.
82 */
83static bool computeWidthsAndCountOps(VerifierData* vdata)
84{
85    const Method* meth = vdata->method;
86    InsnFlags* insnFlags = vdata->insnFlags;
87    size_t insnCount = vdata->insnsSize;
88    const u2* insns = meth->insns;
89    bool result = false;
90    int newInstanceCount = 0;
91    int monitorEnterCount = 0;
92    int i;
93
94    for (i = 0; i < (int) insnCount; /**/) {
95        size_t width = dexGetWidthFromInstruction(insns);
96        if (width == 0) {
97            LOG_VFY_METH(meth, "VFY: invalid instruction (0x%04x)", *insns);
98            goto bail;
99        } else if (width > 65535) {
100            LOG_VFY_METH(meth,
101                "VFY: warning: unusually large instr width (%d)", width);
102        }
103
104        Opcode opcode = dexOpcodeFromCodeUnit(*insns);
105        if (opcode == OP_NEW_INSTANCE)
106            newInstanceCount++;
107        if (opcode == OP_MONITOR_ENTER)
108            monitorEnterCount++;
109
110        insnFlags[i] |= width;
111        i += width;
112        insns += width;
113    }
114    if (i != (int) vdata->insnsSize) {
115        LOG_VFY_METH(meth, "VFY: code did not end where expected (%d vs. %d)",
116            i, dvmGetMethodInsnsSize(meth));
117        goto bail;
118    }
119
120    result = true;
121    vdata->newInstanceCount = newInstanceCount;
122    vdata->monitorEnterCount = monitorEnterCount;
123
124bail:
125    return result;
126}
127
128/*
129 * Set the "in try" flags for all instructions protected by "try" statements.
130 * Also sets the "branch target" flags for exception handlers.
131 *
132 * Call this after widths have been set in "insnFlags".
133 *
134 * Returns "false" if something in the exception table looks fishy, but
135 * we're expecting the exception table to be somewhat sane.
136 */
137static bool scanTryCatchBlocks(const Method* meth, InsnFlags* insnFlags)
138{
139    u4 insnsSize = dvmGetMethodInsnsSize(meth);
140    const DexCode* pCode = dvmGetMethodCode(meth);
141    u4 triesSize = pCode->triesSize;
142    const DexTry* pTries;
143    u4 idx;
144
145    if (triesSize == 0) {
146        return true;
147    }
148
149    pTries = dexGetTries(pCode);
150
151    for (idx = 0; idx < triesSize; idx++) {
152        const DexTry* pTry = &pTries[idx];
153        u4 start = pTry->startAddr;
154        u4 end = start + pTry->insnCount;
155        u4 addr;
156
157        if ((start >= end) || (start >= insnsSize) || (end > insnsSize)) {
158            LOG_VFY_METH(meth,
159                "VFY: bad exception entry: startAddr=%d endAddr=%d (size=%d)",
160                start, end, insnsSize);
161            return false;
162        }
163
164        if (dvmInsnGetWidth(insnFlags, start) == 0) {
165            LOG_VFY_METH(meth,
166                "VFY: 'try' block starts inside an instruction (%d)",
167                start);
168            return false;
169        }
170
171        for (addr = start; addr < end;
172            addr += dvmInsnGetWidth(insnFlags, addr))
173        {
174            assert(dvmInsnGetWidth(insnFlags, addr) != 0);
175            dvmInsnSetInTry(insnFlags, addr, true);
176        }
177    }
178
179    /* Iterate over each of the handlers to verify target addresses. */
180    u4 handlersSize = dexGetHandlersSize(pCode);
181    u4 offset = dexGetFirstHandlerOffset(pCode);
182    for (idx = 0; idx < handlersSize; idx++) {
183        DexCatchIterator iterator;
184        dexCatchIteratorInit(&iterator, pCode, offset);
185
186        for (;;) {
187            DexCatchHandler* handler = dexCatchIteratorNext(&iterator);
188            u4 addr;
189
190            if (handler == NULL) {
191                break;
192            }
193
194            addr = handler->address;
195            if (dvmInsnGetWidth(insnFlags, addr) == 0) {
196                LOG_VFY_METH(meth,
197                    "VFY: exception handler starts at bad address (%d)",
198                    addr);
199                return false;
200            }
201
202            dvmInsnSetBranchTarget(insnFlags, addr, true);
203        }
204
205        offset = dexCatchIteratorGetEndOffset(&iterator, pCode);
206    }
207
208    return true;
209}
210
211/*
212 * Perform verification on a single method.
213 *
214 * We do this in three passes:
215 *  (1) Walk through all code units, determining instruction locations,
216 *      widths, and other characteristics.
217 *  (2) Walk through all code units, performing static checks on
218 *      operands.
219 *  (3) Iterate through the method, checking type safety and looking
220 *      for code flow problems.
221 *
222 * Some checks may be bypassed depending on the verification mode.  We can't
223 * turn this stuff off completely if we want to do "exact" GC.
224 *
225 * TODO: cite source?
226 * Confirmed here:
227 * - code array must not be empty
228 * - (N/A) code_length must be less than 65536
229 * Confirmed by computeWidthsAndCountOps():
230 * - opcode of first instruction begins at index 0
231 * - only documented instructions may appear
232 * - each instruction follows the last
233 * - last byte of last instruction is at (code_length-1)
234 */
235static bool verifyMethod(Method* meth)
236{
237    bool result = false;
238
239    /*
240     * Verifier state blob.  Various values will be cached here so we
241     * can avoid expensive lookups and pass fewer arguments around.
242     */
243    VerifierData vdata;
244#if 1   // ndef NDEBUG
245    memset(&vdata, 0x99, sizeof(vdata));
246#endif
247
248    vdata.method = meth;
249    vdata.insnsSize = dvmGetMethodInsnsSize(meth);
250    vdata.insnRegCount = meth->registersSize;
251    vdata.insnFlags = NULL;
252    vdata.uninitMap = NULL;
253    vdata.basicBlocks = NULL;
254
255    /*
256     * If there aren't any instructions, make sure that's expected, then
257     * exit successfully.  Note: for native methods, meth->insns gets set
258     * to a native function pointer on first call, so don't use that as
259     * an indicator.
260     */
261    if (vdata.insnsSize == 0) {
262        if (!dvmIsNativeMethod(meth) && !dvmIsAbstractMethod(meth)) {
263            LOG_VFY_METH(meth,
264                "VFY: zero-length code in concrete non-native method");
265            goto bail;
266        }
267
268        goto success;
269    }
270
271    /*
272     * Sanity-check the register counts.  ins + locals = registers, so make
273     * sure that ins <= registers.
274     */
275    if (meth->insSize > meth->registersSize) {
276        LOG_VFY_METH(meth, "VFY: bad register counts (ins=%d regs=%d)",
277            meth->insSize, meth->registersSize);
278        goto bail;
279    }
280
281    /*
282     * Allocate and populate an array to hold instruction data.
283     *
284     * TODO: Consider keeping a reusable pre-allocated array sitting
285     * around for smaller methods.
286     */
287    vdata.insnFlags = (InsnFlags*) calloc(vdata.insnsSize, sizeof(InsnFlags));
288    if (vdata.insnFlags == NULL)
289        goto bail;
290
291    /*
292     * Compute the width of each instruction and store the result in insnFlags.
293     * Count up the #of occurrences of certain opcodes while we're at it.
294     */
295    if (!computeWidthsAndCountOps(&vdata))
296        goto bail;
297
298    /*
299     * Allocate a map to hold the classes of uninitialized instances.
300     */
301    vdata.uninitMap = dvmCreateUninitInstanceMap(meth, vdata.insnFlags,
302        vdata.newInstanceCount);
303    if (vdata.uninitMap == NULL)
304        goto bail;
305
306    /*
307     * Set the "in try" flags for all instructions guarded by a "try" block.
308     * Also sets the "branch target" flag on exception handlers.
309     */
310    if (!scanTryCatchBlocks(meth, vdata.insnFlags))
311        goto bail;
312
313    /*
314     * Perform static instruction verification.  Also sets the "branch
315     * target" flags.
316     */
317    if (!verifyInstructions(&vdata))
318        goto bail;
319
320    /*
321     * Do code-flow analysis.
322     *
323     * We could probably skip this for a method with no registers, but
324     * that's so rare that there's little point in checking.
325     */
326    if (!dvmVerifyCodeFlow(&vdata)) {
327        //ALOGD("+++ %s failed code flow", meth->name);
328        goto bail;
329    }
330
331success:
332    result = true;
333
334bail:
335    dvmFreeVfyBasicBlocks(&vdata);
336    dvmFreeUninitInstanceMap(vdata.uninitMap);
337    free(vdata.insnFlags);
338    return result;
339}
340
341
342/*
343 * Verify an array data table.  "curOffset" is the offset of the
344 * fill-array-data instruction.
345 */
346static bool checkArrayData(const Method* meth, u4 curOffset)
347{
348    const u4 insnCount = dvmGetMethodInsnsSize(meth);
349    const u2* insns = meth->insns + curOffset;
350    const u2* arrayData;
351    u4 valueCount, valueWidth, tableSize;
352    s4 offsetToArrayData;
353
354    assert(curOffset < insnCount);
355
356    /* make sure the start of the array data table is in range */
357    offsetToArrayData = insns[1] | (((s4)insns[2]) << 16);
358    if ((s4)curOffset + offsetToArrayData < 0 ||
359        curOffset + offsetToArrayData + 2 >= insnCount)
360    {
361        LOG_VFY("VFY: invalid array data start: at %d, data offset %d, "
362                "count %d",
363            curOffset, offsetToArrayData, insnCount);
364        return false;
365    }
366
367    /* offset to array data table is a relative branch-style offset */
368    arrayData = insns + offsetToArrayData;
369
370    /* make sure the table is 32-bit aligned */
371    if ((((u4) arrayData) & 0x03) != 0) {
372        LOG_VFY("VFY: unaligned array data table: at %d, data offset %d",
373            curOffset, offsetToArrayData);
374        return false;
375    }
376
377    valueWidth = arrayData[1];
378    valueCount = *(u4*)(&arrayData[2]);
379
380    tableSize = 4 + (valueWidth * valueCount + 1) / 2;
381
382    /* make sure the end of the switch is in range */
383    if (curOffset + offsetToArrayData + tableSize > insnCount) {
384        LOG_VFY("VFY: invalid array data end: at %d, data offset %d, end %d, "
385                "count %d",
386            curOffset, offsetToArrayData,
387            curOffset + offsetToArrayData + tableSize, insnCount);
388        return false;
389    }
390
391    return true;
392}
393
394/*
395 * Perform static checks on a "new-instance" instruction.  Specifically,
396 * make sure the class reference isn't for an array class.
397 *
398 * We don't need the actual class, just a pointer to the class name.
399 */
400static bool checkNewInstance(const DvmDex* pDvmDex, u4 idx)
401{
402    const char* classDescriptor;
403
404    if (idx >= pDvmDex->pHeader->typeIdsSize) {
405        LOG_VFY("VFY: bad type index %d (max %d)",
406            idx, pDvmDex->pHeader->typeIdsSize);
407        return false;
408    }
409
410    classDescriptor = dexStringByTypeIdx(pDvmDex->pDexFile, idx);
411    if (classDescriptor[0] != 'L') {
412        LOG_VFY("VFY: can't call new-instance on type '%s'",
413            classDescriptor);
414        return false;
415    }
416
417    return true;
418}
419
420/*
421 * Perform static checks on a "new-array" instruction.  Specifically, make
422 * sure they aren't creating an array of arrays that causes the number of
423 * dimensions to exceed 255.
424 */
425static bool checkNewArray(const DvmDex* pDvmDex, u4 idx)
426{
427    const char* classDescriptor;
428
429    if (idx >= pDvmDex->pHeader->typeIdsSize) {
430        LOG_VFY("VFY: bad type index %d (max %d)",
431            idx, pDvmDex->pHeader->typeIdsSize);
432        return false;
433    }
434
435    classDescriptor = dexStringByTypeIdx(pDvmDex->pDexFile, idx);
436
437    int bracketCount = 0;
438    const char* cp = classDescriptor;
439    while (*cp++ == '[')
440        bracketCount++;
441
442    if (bracketCount == 0) {
443        /* The given class must be an array type. */
444        LOG_VFY("VFY: can't new-array class '%s' (not an array)",
445            classDescriptor);
446        return false;
447    } else if (bracketCount > 255) {
448        /* It is illegal to create an array of more than 255 dimensions. */
449        LOG_VFY("VFY: can't new-array class '%s' (exceeds limit)",
450            classDescriptor);
451        return false;
452    }
453
454    return true;
455}
456
457/*
458 * Perform static checks on an instruction that takes a class constant.
459 * Ensure that the class index is in the valid range.
460 */
461static bool checkTypeIndex(const DvmDex* pDvmDex, u4 idx)
462{
463    if (idx >= pDvmDex->pHeader->typeIdsSize) {
464        LOG_VFY("VFY: bad type index %d (max %d)",
465            idx, pDvmDex->pHeader->typeIdsSize);
466        return false;
467    }
468    return true;
469}
470
471/*
472 * Perform static checks on a field get or set instruction.  All we do
473 * here is ensure that the field index is in the valid range.
474 */
475static bool checkFieldIndex(const DvmDex* pDvmDex, u4 idx)
476{
477    if (idx >= pDvmDex->pHeader->fieldIdsSize) {
478        LOG_VFY("VFY: bad field index %d (max %d)",
479            idx, pDvmDex->pHeader->fieldIdsSize);
480        return false;
481    }
482    return true;
483}
484
485/*
486 * Perform static checks on a method invocation instruction.  All we do
487 * here is ensure that the method index is in the valid range.
488 */
489static bool checkMethodIndex(const DvmDex* pDvmDex, u4 idx)
490{
491    if (idx >= pDvmDex->pHeader->methodIdsSize) {
492        LOG_VFY("VFY: bad method index %d (max %d)",
493            idx, pDvmDex->pHeader->methodIdsSize);
494        return false;
495    }
496    return true;
497}
498
499/*
500 * Ensure that the string index is in the valid range.
501 */
502static bool checkStringIndex(const DvmDex* pDvmDex, u4 idx)
503{
504    if (idx >= pDvmDex->pHeader->stringIdsSize) {
505        LOG_VFY("VFY: bad string index %d (max %d)",
506            idx, pDvmDex->pHeader->stringIdsSize);
507        return false;
508    }
509    return true;
510}
511
512/*
513 * Ensure that the register index is valid for this method.
514 */
515static bool checkRegisterIndex(const Method* meth, u4 idx)
516{
517    if (idx >= meth->registersSize) {
518        LOG_VFY("VFY: register index out of range (%d >= %d)",
519            idx, meth->registersSize);
520        return false;
521    }
522    return true;
523}
524
525/*
526 * Ensure that the wide register index is valid for this method.
527 */
528static bool checkWideRegisterIndex(const Method* meth, u4 idx)
529{
530    if (idx+1 >= meth->registersSize) {
531        LOG_VFY("VFY: wide register index out of range (%d+1 >= %d)",
532            idx, meth->registersSize);
533        return false;
534    }
535    return true;
536}
537
538/*
539 * Check the register indices used in a "vararg" instruction, such as
540 * invoke-virtual or filled-new-array.
541 *
542 * vA holds word count (0-5), args[] have values.
543 *
544 * There are some tests we don't do here, e.g. we don't try to verify
545 * that invoking a method that takes a double is done with consecutive
546 * registers.  This requires parsing the target method signature, which
547 * we will be doing later on during the code flow analysis.
548 */
549static bool checkVarargRegs(const Method* meth,
550    const DecodedInstruction* pDecInsn)
551{
552    u2 registersSize = meth->registersSize;
553    unsigned int idx;
554
555    if (pDecInsn->vA > 5) {
556        LOG_VFY("VFY: invalid arg count (%d) in non-range invoke)",
557            pDecInsn->vA);
558        return false;
559    }
560
561    for (idx = 0; idx < pDecInsn->vA; idx++) {
562        if (pDecInsn->arg[idx] > registersSize) {
563            LOG_VFY("VFY: invalid reg index (%d) in non-range invoke (> %d)",
564                pDecInsn->arg[idx], registersSize);
565            return false;
566        }
567    }
568
569    return true;
570}
571
572/*
573 * Check the register indices used in a "vararg/range" instruction, such as
574 * invoke-virtual/range or filled-new-array/range.
575 *
576 * vA holds word count, vC holds index of first reg.
577 */
578static bool checkVarargRangeRegs(const Method* meth,
579    const DecodedInstruction* pDecInsn)
580{
581    u2 registersSize = meth->registersSize;
582
583    /*
584     * vA/vC are unsigned 8-bit/16-bit quantities for /range instructions,
585     * so there's no risk of integer overflow when adding them here.
586     */
587    if (pDecInsn->vA + pDecInsn->vC > registersSize) {
588        LOG_VFY("VFY: invalid reg index %d+%d in range invoke (> %d)",
589            pDecInsn->vA, pDecInsn->vC, registersSize);
590        return false;
591    }
592
593    return true;
594}
595
596/*
597 * Verify a switch table.  "curOffset" is the offset of the switch
598 * instruction.
599 *
600 * Updates "insnFlags", setting the "branch target" flag.
601 */
602static bool checkSwitchTargets(const Method* meth, InsnFlags* insnFlags,
603    u4 curOffset)
604{
605    const u4 insnCount = dvmGetMethodInsnsSize(meth);
606    const u2* insns = meth->insns + curOffset;
607    const u2* switchInsns;
608    u2 expectedSignature;
609    u4 switchCount, tableSize;
610    s4 offsetToSwitch, offsetToKeys, offsetToTargets;
611    s4 offset, absOffset;
612    u4 targ;
613
614    assert(curOffset < insnCount);
615
616    /* make sure the start of the switch is in range */
617    offsetToSwitch = insns[1] | ((s4) insns[2]) << 16;
618    if ((s4) curOffset + offsetToSwitch < 0 ||
619        curOffset + offsetToSwitch + 2 >= insnCount)
620    {
621        LOG_VFY("VFY: invalid switch start: at %d, switch offset %d, "
622                "count %d",
623            curOffset, offsetToSwitch, insnCount);
624        return false;
625    }
626
627    /* offset to switch table is a relative branch-style offset */
628    switchInsns = insns + offsetToSwitch;
629
630    /* make sure the table is 32-bit aligned */
631    if ((((u4) switchInsns) & 0x03) != 0) {
632        LOG_VFY("VFY: unaligned switch table: at %d, switch offset %d",
633            curOffset, offsetToSwitch);
634        return false;
635    }
636
637    switchCount = switchInsns[1];
638
639    if ((*insns & 0xff) == OP_PACKED_SWITCH) {
640        /* 0=sig, 1=count, 2/3=firstKey */
641        offsetToTargets = 4;
642        offsetToKeys = -1;
643        expectedSignature = kPackedSwitchSignature;
644    } else {
645        /* 0=sig, 1=count, 2..count*2 = keys */
646        offsetToKeys = 2;
647        offsetToTargets = 2 + 2*switchCount;
648        expectedSignature = kSparseSwitchSignature;
649    }
650    tableSize = offsetToTargets + switchCount*2;
651
652    if (switchInsns[0] != expectedSignature) {
653        LOG_VFY("VFY: wrong signature for switch table (0x%04x, wanted 0x%04x)",
654            switchInsns[0], expectedSignature);
655        return false;
656    }
657
658    /* make sure the end of the switch is in range */
659    if (curOffset + offsetToSwitch + tableSize > (u4) insnCount) {
660        LOG_VFY("VFY: invalid switch end: at %d, switch offset %d, end %d, "
661                "count %d",
662            curOffset, offsetToSwitch, curOffset + offsetToSwitch + tableSize,
663            insnCount);
664        return false;
665    }
666
667    /* for a sparse switch, verify the keys are in ascending order */
668    if (offsetToKeys > 0 && switchCount > 1) {
669        s4 lastKey;
670
671        lastKey = switchInsns[offsetToKeys] |
672                  (switchInsns[offsetToKeys+1] << 16);
673        for (targ = 1; targ < switchCount; targ++) {
674            s4 key = (s4) switchInsns[offsetToKeys + targ*2] |
675                    (s4) (switchInsns[offsetToKeys + targ*2 +1] << 16);
676            if (key <= lastKey) {
677                LOG_VFY("VFY: invalid packed switch: last key=%d, this=%d",
678                    lastKey, key);
679                return false;
680            }
681
682            lastKey = key;
683        }
684    }
685
686    /* verify each switch target */
687    for (targ = 0; targ < switchCount; targ++) {
688        offset = (s4) switchInsns[offsetToTargets + targ*2] |
689                (s4) (switchInsns[offsetToTargets + targ*2 +1] << 16);
690        absOffset = curOffset + offset;
691
692        if (absOffset < 0 || absOffset >= (s4)insnCount ||
693            !dvmInsnIsOpcode(insnFlags, absOffset))
694        {
695            LOG_VFY("VFY: invalid switch target %d (-> %#x) at %#x[%d]",
696                offset, absOffset, curOffset, targ);
697            return false;
698        }
699        dvmInsnSetBranchTarget(insnFlags, absOffset, true);
700    }
701
702    return true;
703}
704
705/*
706 * Verify that the target of a branch instruction is valid.
707 *
708 * We don't expect code to jump directly into an exception handler, but
709 * it's valid to do so as long as the target isn't a "move-exception"
710 * instruction.  We verify that in a later stage.
711 *
712 * The VM spec doesn't forbid an instruction from branching to itself,
713 * but the Dalvik spec declares that only certain instructions can do so.
714 *
715 * Updates "insnFlags", setting the "branch target" flag.
716 */
717static bool checkBranchTarget(const Method* meth, InsnFlags* insnFlags,
718    int curOffset, bool selfOkay)
719{
720    const int insnCount = dvmGetMethodInsnsSize(meth);
721    s4 offset, absOffset;
722    bool isConditional;
723
724    if (!dvmGetBranchOffset(meth, insnFlags, curOffset, &offset,
725            &isConditional))
726        return false;
727
728    if (!selfOkay && offset == 0) {
729        LOG_VFY_METH(meth, "VFY: branch offset of zero not allowed at %#x",
730            curOffset);
731        return false;
732    }
733
734    /*
735     * Check for 32-bit overflow.  This isn't strictly necessary if we can
736     * depend on the VM to have identical "wrap-around" behavior, but
737     * it's unwise to depend on that.
738     */
739    if (((s8) curOffset + (s8) offset) != (s8)(curOffset + offset)) {
740        LOG_VFY_METH(meth, "VFY: branch target overflow %#x +%d",
741            curOffset, offset);
742        return false;
743    }
744    absOffset = curOffset + offset;
745    if (absOffset < 0 || absOffset >= insnCount ||
746        !dvmInsnIsOpcode(insnFlags, absOffset))
747    {
748        LOG_VFY_METH(meth,
749            "VFY: invalid branch target %d (-> %#x) at %#x",
750            offset, absOffset, curOffset);
751        return false;
752    }
753    dvmInsnSetBranchTarget(insnFlags, absOffset, true);
754
755    return true;
756}
757
758
759/*
760 * Perform static verification on instructions.
761 *
762 * As a side effect, this sets the "branch target" flags in InsnFlags.
763 *
764 * "(CF)" items are handled during code-flow analysis.
765 *
766 * v3 4.10.1
767 * - target of each jump and branch instruction must be valid
768 * - targets of switch statements must be valid
769 * - operands referencing constant pool entries must be valid
770 * - (CF) operands of getfield, putfield, getstatic, putstatic must be valid
771 * - (new) verify operands of "quick" field ops
772 * - (CF) operands of method invocation instructions must be valid
773 * - (new) verify operands of "quick" method invoke ops
774 * - (CF) only invoke-direct can call a method starting with '<'
775 * - (CF) <clinit> must never be called explicitly
776 * - operands of instanceof, checkcast, new (and variants) must be valid
777 * - new-array[-type] limited to 255 dimensions
778 * - can't use "new" on an array class
779 * - (?) limit dimensions in multi-array creation
780 * - local variable load/store register values must be in valid range
781 *
782 * v3 4.11.1.2
783 * - branches must be within the bounds of the code array
784 * - targets of all control-flow instructions are the start of an instruction
785 * - register accesses fall within range of allocated registers
786 * - (N/A) access to constant pool must be of appropriate type
787 * - code does not end in the middle of an instruction
788 * - execution cannot fall off the end of the code
789 * - (earlier) for each exception handler, the "try" area must begin and
790 *   end at the start of an instruction (end can be at the end of the code)
791 * - (earlier) for each exception handler, the handler must start at a valid
792 *   instruction
793 */
794static bool verifyInstructions(VerifierData* vdata)
795{
796    const Method* meth = vdata->method;
797    const DvmDex* pDvmDex = meth->clazz->pDvmDex;
798    InsnFlags* insnFlags = vdata->insnFlags;
799    const u2* insns = meth->insns;
800    unsigned int codeOffset;
801
802    /* the start of the method is a "branch target" */
803    dvmInsnSetBranchTarget(insnFlags, 0, true);
804
805    for (codeOffset = 0; codeOffset < vdata->insnsSize; /**/) {
806        /*
807         * Pull the instruction apart.
808         */
809        int width = dvmInsnGetWidth(insnFlags, codeOffset);
810        DecodedInstruction decInsn;
811        bool okay = true;
812
813        dexDecodeInstruction(meth->insns + codeOffset, &decInsn);
814
815        /*
816         * Check register, type, class, field, method, and string indices
817         * for out-of-range values.  Do additional checks on branch targets
818         * and some special cases like new-instance and new-array.
819         */
820        switch (decInsn.opcode) {
821        case OP_NOP:
822        case OP_RETURN_VOID:
823            /* nothing to check */
824            break;
825        case OP_MOVE_RESULT:
826        case OP_MOVE_RESULT_OBJECT:
827        case OP_MOVE_EXCEPTION:
828        case OP_RETURN:
829        case OP_RETURN_OBJECT:
830        case OP_CONST_4:
831        case OP_CONST_16:
832        case OP_CONST:
833        case OP_CONST_HIGH16:
834        case OP_MONITOR_ENTER:
835        case OP_MONITOR_EXIT:
836        case OP_THROW:
837            okay &= checkRegisterIndex(meth, decInsn.vA);
838            break;
839        case OP_MOVE_RESULT_WIDE:
840        case OP_RETURN_WIDE:
841        case OP_CONST_WIDE_16:
842        case OP_CONST_WIDE_32:
843        case OP_CONST_WIDE:
844        case OP_CONST_WIDE_HIGH16:
845            okay &= checkWideRegisterIndex(meth, decInsn.vA);
846            break;
847        case OP_GOTO:
848        case OP_GOTO_16:
849            okay &= checkBranchTarget(meth, insnFlags, codeOffset, false);
850            break;
851        case OP_GOTO_32:
852            okay &= checkBranchTarget(meth, insnFlags, codeOffset, true);
853            break;
854        case OP_MOVE:
855        case OP_MOVE_FROM16:
856        case OP_MOVE_16:
857        case OP_MOVE_OBJECT:
858        case OP_MOVE_OBJECT_FROM16:
859        case OP_MOVE_OBJECT_16:
860        case OP_ARRAY_LENGTH:
861        case OP_NEG_INT:
862        case OP_NOT_INT:
863        case OP_NEG_FLOAT:
864        case OP_INT_TO_FLOAT:
865        case OP_FLOAT_TO_INT:
866        case OP_INT_TO_BYTE:
867        case OP_INT_TO_CHAR:
868        case OP_INT_TO_SHORT:
869        case OP_ADD_INT_2ADDR:
870        case OP_SUB_INT_2ADDR:
871        case OP_MUL_INT_2ADDR:
872        case OP_DIV_INT_2ADDR:
873        case OP_REM_INT_2ADDR:
874        case OP_AND_INT_2ADDR:
875        case OP_OR_INT_2ADDR:
876        case OP_XOR_INT_2ADDR:
877        case OP_SHL_INT_2ADDR:
878        case OP_SHR_INT_2ADDR:
879        case OP_USHR_INT_2ADDR:
880        case OP_ADD_FLOAT_2ADDR:
881        case OP_SUB_FLOAT_2ADDR:
882        case OP_MUL_FLOAT_2ADDR:
883        case OP_DIV_FLOAT_2ADDR:
884        case OP_REM_FLOAT_2ADDR:
885        case OP_ADD_INT_LIT16:
886        case OP_RSUB_INT:
887        case OP_MUL_INT_LIT16:
888        case OP_DIV_INT_LIT16:
889        case OP_REM_INT_LIT16:
890        case OP_AND_INT_LIT16:
891        case OP_OR_INT_LIT16:
892        case OP_XOR_INT_LIT16:
893        case OP_ADD_INT_LIT8:
894        case OP_RSUB_INT_LIT8:
895        case OP_MUL_INT_LIT8:
896        case OP_DIV_INT_LIT8:
897        case OP_REM_INT_LIT8:
898        case OP_AND_INT_LIT8:
899        case OP_OR_INT_LIT8:
900        case OP_XOR_INT_LIT8:
901        case OP_SHL_INT_LIT8:
902        case OP_SHR_INT_LIT8:
903        case OP_USHR_INT_LIT8:
904            okay &= checkRegisterIndex(meth, decInsn.vA);
905            okay &= checkRegisterIndex(meth, decInsn.vB);
906            break;
907        case OP_INT_TO_LONG:
908        case OP_INT_TO_DOUBLE:
909        case OP_FLOAT_TO_LONG:
910        case OP_FLOAT_TO_DOUBLE:
911        case OP_SHL_LONG_2ADDR:
912        case OP_SHR_LONG_2ADDR:
913        case OP_USHR_LONG_2ADDR:
914            okay &= checkWideRegisterIndex(meth, decInsn.vA);
915            okay &= checkRegisterIndex(meth, decInsn.vB);
916            break;
917        case OP_LONG_TO_INT:
918        case OP_LONG_TO_FLOAT:
919        case OP_DOUBLE_TO_INT:
920        case OP_DOUBLE_TO_FLOAT:
921            okay &= checkRegisterIndex(meth, decInsn.vA);
922            okay &= checkWideRegisterIndex(meth, decInsn.vB);
923            break;
924        case OP_MOVE_WIDE:
925        case OP_MOVE_WIDE_FROM16:
926        case OP_MOVE_WIDE_16:
927        case OP_DOUBLE_TO_LONG:
928        case OP_LONG_TO_DOUBLE:
929        case OP_NEG_DOUBLE:
930        case OP_NEG_LONG:
931        case OP_NOT_LONG:
932        case OP_ADD_LONG_2ADDR:
933        case OP_SUB_LONG_2ADDR:
934        case OP_MUL_LONG_2ADDR:
935        case OP_DIV_LONG_2ADDR:
936        case OP_REM_LONG_2ADDR:
937        case OP_AND_LONG_2ADDR:
938        case OP_OR_LONG_2ADDR:
939        case OP_XOR_LONG_2ADDR:
940        case OP_ADD_DOUBLE_2ADDR:
941        case OP_SUB_DOUBLE_2ADDR:
942        case OP_MUL_DOUBLE_2ADDR:
943        case OP_DIV_DOUBLE_2ADDR:
944        case OP_REM_DOUBLE_2ADDR:
945            okay &= checkWideRegisterIndex(meth, decInsn.vA);
946            okay &= checkWideRegisterIndex(meth, decInsn.vB);
947            break;
948        case OP_CONST_STRING:
949        case OP_CONST_STRING_JUMBO:
950            okay &= checkRegisterIndex(meth, decInsn.vA);
951            okay &= checkStringIndex(pDvmDex, decInsn.vB);
952            break;
953        case OP_CONST_CLASS:
954        case OP_CHECK_CAST:
955            okay &= checkRegisterIndex(meth, decInsn.vA);
956            okay &= checkTypeIndex(pDvmDex, decInsn.vB);
957            break;
958        case OP_INSTANCE_OF:
959            okay &= checkRegisterIndex(meth, decInsn.vA);
960            okay &= checkRegisterIndex(meth, decInsn.vB);
961            okay &= checkTypeIndex(pDvmDex, decInsn.vC);
962            break;
963        case OP_NEW_INSTANCE:
964            okay &= checkRegisterIndex(meth, decInsn.vA);
965            okay &= checkNewInstance(pDvmDex, decInsn.vB);
966            break;
967        case OP_NEW_ARRAY:
968            okay &= checkRegisterIndex(meth, decInsn.vA);
969            okay &= checkRegisterIndex(meth, decInsn.vB);
970            okay &= checkNewArray(pDvmDex, decInsn.vC);
971            break;
972        case OP_FILL_ARRAY_DATA:
973            okay &= checkRegisterIndex(meth, decInsn.vA);
974            okay &= checkArrayData(meth, codeOffset);
975            break;
976        case OP_PACKED_SWITCH:
977            okay &= checkRegisterIndex(meth, decInsn.vA);
978            okay &= checkSwitchTargets(meth, insnFlags, codeOffset);
979            break;
980        case OP_SPARSE_SWITCH:
981            okay &= checkRegisterIndex(meth, decInsn.vA);
982            okay &= checkSwitchTargets(meth, insnFlags, codeOffset);
983            break;
984        case OP_CMPL_FLOAT:
985        case OP_CMPG_FLOAT:
986        case OP_AGET:
987        case OP_AGET_OBJECT:
988        case OP_AGET_BOOLEAN:
989        case OP_AGET_BYTE:
990        case OP_AGET_CHAR:
991        case OP_AGET_SHORT:
992        case OP_APUT:
993        case OP_APUT_OBJECT:
994        case OP_APUT_BOOLEAN:
995        case OP_APUT_BYTE:
996        case OP_APUT_CHAR:
997        case OP_APUT_SHORT:
998        case OP_ADD_INT:
999        case OP_SUB_INT:
1000        case OP_MUL_INT:
1001        case OP_DIV_INT:
1002        case OP_REM_INT:
1003        case OP_AND_INT:
1004        case OP_OR_INT:
1005        case OP_XOR_INT:
1006        case OP_SHL_INT:
1007        case OP_SHR_INT:
1008        case OP_USHR_INT:
1009        case OP_ADD_FLOAT:
1010        case OP_SUB_FLOAT:
1011        case OP_MUL_FLOAT:
1012        case OP_DIV_FLOAT:
1013        case OP_REM_FLOAT:
1014            okay &= checkRegisterIndex(meth, decInsn.vA);
1015            okay &= checkRegisterIndex(meth, decInsn.vB);
1016            okay &= checkRegisterIndex(meth, decInsn.vC);
1017            break;
1018        case OP_AGET_WIDE:
1019        case OP_APUT_WIDE:
1020            okay &= checkWideRegisterIndex(meth, decInsn.vA);
1021            okay &= checkRegisterIndex(meth, decInsn.vB);
1022            okay &= checkRegisterIndex(meth, decInsn.vC);
1023            break;
1024        case OP_CMPL_DOUBLE:
1025        case OP_CMPG_DOUBLE:
1026        case OP_CMP_LONG:
1027            okay &= checkRegisterIndex(meth, decInsn.vA);
1028            okay &= checkWideRegisterIndex(meth, decInsn.vB);
1029            okay &= checkWideRegisterIndex(meth, decInsn.vC);
1030            break;
1031        case OP_ADD_DOUBLE:
1032        case OP_SUB_DOUBLE:
1033        case OP_MUL_DOUBLE:
1034        case OP_DIV_DOUBLE:
1035        case OP_REM_DOUBLE:
1036        case OP_ADD_LONG:
1037        case OP_SUB_LONG:
1038        case OP_MUL_LONG:
1039        case OP_DIV_LONG:
1040        case OP_REM_LONG:
1041        case OP_AND_LONG:
1042        case OP_OR_LONG:
1043        case OP_XOR_LONG:
1044            okay &= checkWideRegisterIndex(meth, decInsn.vA);
1045            okay &= checkWideRegisterIndex(meth, decInsn.vB);
1046            okay &= checkWideRegisterIndex(meth, decInsn.vC);
1047            break;
1048        case OP_SHL_LONG:
1049        case OP_SHR_LONG:
1050        case OP_USHR_LONG:
1051            okay &= checkWideRegisterIndex(meth, decInsn.vA);
1052            okay &= checkWideRegisterIndex(meth, decInsn.vB);
1053            okay &= checkRegisterIndex(meth, decInsn.vC);
1054            break;
1055        case OP_IF_EQ:
1056        case OP_IF_NE:
1057        case OP_IF_LT:
1058        case OP_IF_GE:
1059        case OP_IF_GT:
1060        case OP_IF_LE:
1061            okay &= checkRegisterIndex(meth, decInsn.vA);
1062            okay &= checkRegisterIndex(meth, decInsn.vB);
1063            okay &= checkBranchTarget(meth, insnFlags, codeOffset, false);
1064            break;
1065        case OP_IF_EQZ:
1066        case OP_IF_NEZ:
1067        case OP_IF_LTZ:
1068        case OP_IF_GEZ:
1069        case OP_IF_GTZ:
1070        case OP_IF_LEZ:
1071            okay &= checkRegisterIndex(meth, decInsn.vA);
1072            okay &= checkBranchTarget(meth, insnFlags, codeOffset, false);
1073            break;
1074        case OP_IGET:
1075        case OP_IGET_OBJECT:
1076        case OP_IGET_BOOLEAN:
1077        case OP_IGET_BYTE:
1078        case OP_IGET_CHAR:
1079        case OP_IGET_SHORT:
1080        case OP_IPUT:
1081        case OP_IPUT_OBJECT:
1082        case OP_IPUT_BOOLEAN:
1083        case OP_IPUT_BYTE:
1084        case OP_IPUT_CHAR:
1085        case OP_IPUT_SHORT:
1086            okay &= checkRegisterIndex(meth, decInsn.vA);
1087            okay &= checkRegisterIndex(meth, decInsn.vB);
1088            okay &= checkFieldIndex(pDvmDex, decInsn.vC);
1089            break;
1090        case OP_IGET_WIDE:
1091        case OP_IPUT_WIDE:
1092            okay &= checkWideRegisterIndex(meth, decInsn.vA);
1093            okay &= checkRegisterIndex(meth, decInsn.vB);
1094            okay &= checkFieldIndex(pDvmDex, decInsn.vC);
1095            break;
1096        case OP_SGET:
1097        case OP_SGET_OBJECT:
1098        case OP_SGET_BOOLEAN:
1099        case OP_SGET_BYTE:
1100        case OP_SGET_CHAR:
1101        case OP_SGET_SHORT:
1102        case OP_SPUT:
1103        case OP_SPUT_OBJECT:
1104        case OP_SPUT_BOOLEAN:
1105        case OP_SPUT_BYTE:
1106        case OP_SPUT_CHAR:
1107        case OP_SPUT_SHORT:
1108            okay &= checkRegisterIndex(meth, decInsn.vA);
1109            okay &= checkFieldIndex(pDvmDex, decInsn.vB);
1110            break;
1111        case OP_SGET_WIDE:
1112        case OP_SPUT_WIDE:
1113            okay &= checkWideRegisterIndex(meth, decInsn.vA);
1114            okay &= checkFieldIndex(pDvmDex, decInsn.vB);
1115            break;
1116        case OP_FILLED_NEW_ARRAY:
1117            /* decoder uses B, not C, for type ref */
1118            okay &= checkTypeIndex(pDvmDex, decInsn.vB);
1119            okay &= checkVarargRegs(meth, &decInsn);
1120            break;
1121        case OP_FILLED_NEW_ARRAY_RANGE:
1122            okay &= checkTypeIndex(pDvmDex, decInsn.vB);
1123            okay &= checkVarargRangeRegs(meth, &decInsn);
1124            break;
1125        case OP_INVOKE_VIRTUAL:
1126        case OP_INVOKE_SUPER:
1127        case OP_INVOKE_DIRECT:
1128        case OP_INVOKE_STATIC:
1129        case OP_INVOKE_INTERFACE:
1130            /* decoder uses B, not C, for type ref */
1131            okay &= checkMethodIndex(pDvmDex, decInsn.vB);
1132            okay &= checkVarargRegs(meth, &decInsn);
1133            break;
1134        case OP_INVOKE_VIRTUAL_RANGE:
1135        case OP_INVOKE_SUPER_RANGE:
1136        case OP_INVOKE_DIRECT_RANGE:
1137        case OP_INVOKE_STATIC_RANGE:
1138        case OP_INVOKE_INTERFACE_RANGE:
1139            okay &= checkMethodIndex(pDvmDex, decInsn.vB);
1140            okay &= checkVarargRangeRegs(meth, &decInsn);
1141            break;
1142
1143        /* verifier/optimizer output; we should never see these */
1144        case OP_IGET_VOLATILE:
1145        case OP_IPUT_VOLATILE:
1146        case OP_SGET_VOLATILE:
1147        case OP_SPUT_VOLATILE:
1148        case OP_IGET_OBJECT_VOLATILE:
1149        case OP_IPUT_OBJECT_VOLATILE:
1150        case OP_SGET_OBJECT_VOLATILE:
1151        case OP_SPUT_OBJECT_VOLATILE:
1152        case OP_IGET_WIDE_VOLATILE:
1153        case OP_IPUT_WIDE_VOLATILE:
1154        case OP_SGET_WIDE_VOLATILE:
1155        case OP_SPUT_WIDE_VOLATILE:
1156        case OP_BREAKPOINT:
1157        case OP_THROW_VERIFICATION_ERROR:
1158        case OP_EXECUTE_INLINE:
1159        case OP_EXECUTE_INLINE_RANGE:
1160        case OP_INVOKE_OBJECT_INIT_RANGE:
1161        case OP_RETURN_VOID_BARRIER:
1162        case OP_IGET_QUICK:
1163        case OP_IGET_WIDE_QUICK:
1164        case OP_IGET_OBJECT_QUICK:
1165        case OP_IPUT_QUICK:
1166        case OP_IPUT_WIDE_QUICK:
1167        case OP_IPUT_OBJECT_QUICK:
1168        case OP_INVOKE_VIRTUAL_QUICK:
1169        case OP_INVOKE_VIRTUAL_QUICK_RANGE:
1170        case OP_INVOKE_SUPER_QUICK:
1171        case OP_INVOKE_SUPER_QUICK_RANGE:
1172        case OP_UNUSED_3E:
1173        case OP_UNUSED_3F:
1174        case OP_UNUSED_40:
1175        case OP_UNUSED_41:
1176        case OP_UNUSED_42:
1177        case OP_UNUSED_43:
1178        case OP_UNUSED_73:
1179        case OP_UNUSED_79:
1180        case OP_UNUSED_7A:
1181        case OP_UNUSED_FF:
1182            ALOGE("VFY: unexpected opcode %04x", decInsn.opcode);
1183            okay = false;
1184            break;
1185
1186        /*
1187         * DO NOT add a "default" clause here.  Without it the compiler will
1188         * complain if an instruction is missing (which is desirable).
1189         */
1190        }
1191
1192        if (!okay) {
1193            LOG_VFY_METH(meth, "VFY:  rejecting opcode 0x%02x at 0x%04x",
1194                decInsn.opcode, codeOffset);
1195            return false;
1196        }
1197
1198        OpcodeFlags opFlags = dexGetFlagsFromOpcode(decInsn.opcode);
1199        if ((opFlags & VERIFY_GC_INST_MASK) != 0) {
1200            /*
1201             * This instruction is a GC point.  If space is a concern,
1202             * the set of GC points could be reduced by eliminating
1203             * foward branches.
1204             *
1205             * TODO: we could also scan the targets of a "switch" statement,
1206             * and if none of them branch backward we could ignore that
1207             * instruction as well.
1208             */
1209            dvmInsnSetGcPoint(insnFlags, codeOffset, true);
1210        }
1211
1212        assert(width > 0);
1213        codeOffset += width;
1214        insns += width;
1215    }
1216
1217    /* make sure the last instruction ends at the end of the insn area */
1218    if (codeOffset != vdata->insnsSize) {
1219        LOG_VFY_METH(meth,
1220            "VFY: code did not end when expected (end at %d, count %d)",
1221            codeOffset, vdata->insnsSize);
1222        return false;
1223    }
1224
1225    return true;
1226}
1227