| /* |
| * Copyright (C) 2008 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| /* |
| * Dalvik classfile verification. This file contains the verifier entry |
| * points and the static constraint checks. |
| */ |
| #include "Dalvik.h" |
| #include "analysis/CodeVerify.h" |
| |
| |
| /* fwd */ |
| static bool verifyMethod(Method* meth); |
| static bool verifyInstructions(VerifierData* vdata); |
| |
| |
| /* |
| * Initialize some things we need for verification. |
| */ |
| bool dvmVerificationStartup(void) |
| { |
| gDvm.instrWidth = dexCreateInstrWidthTable(); |
| gDvm.instrFormat = dexCreateInstrFormatTable(); |
| gDvm.instrFlags = dexCreateInstrFlagsTable(); |
| if (gDvm.instrWidth == NULL || gDvm.instrFormat == NULL || |
| gDvm.instrFlags == NULL) |
| { |
| LOGE("Unable to create instruction tables\n"); |
| return false; |
| } |
| |
| return true; |
| } |
| |
| /* |
| * Free up some things we needed for verification. |
| */ |
| void dvmVerificationShutdown(void) |
| { |
| free(gDvm.instrWidth); |
| free(gDvm.instrFormat); |
| free(gDvm.instrFlags); |
| } |
| |
| |
| /* |
| * Verify a class. |
| * |
| * By the time we get here, the value of gDvm.classVerifyMode should already |
| * have been factored in. If you want to call into the verifier even |
| * though verification is disabled, that's your business. |
| * |
| * Returns "true" on success. |
| */ |
| bool dvmVerifyClass(ClassObject* clazz) |
| { |
| int i; |
| |
| if (dvmIsClassVerified(clazz)) { |
| LOGD("Ignoring duplicate verify attempt on %s\n", clazz->descriptor); |
| return true; |
| } |
| |
| for (i = 0; i < clazz->directMethodCount; i++) { |
| if (!verifyMethod(&clazz->directMethods[i])) { |
| LOG_VFY("Verifier rejected class %s\n", clazz->descriptor); |
| return false; |
| } |
| } |
| for (i = 0; i < clazz->virtualMethodCount; i++) { |
| if (!verifyMethod(&clazz->virtualMethods[i])) { |
| LOG_VFY("Verifier rejected class %s\n", clazz->descriptor); |
| return false; |
| } |
| } |
| |
| return true; |
| } |
| |
| |
| /* |
| * Perform verification on a single method. |
| * |
| * We do this in three passes: |
| * (1) Walk through all code units, determining instruction locations, |
| * widths, and other characteristics. |
| * (2) Walk through all code units, performing static checks on |
| * operands. |
| * (3) Iterate through the method, checking type safety and looking |
| * for code flow problems. |
| * |
| * Some checks may be bypassed depending on the verification mode. We can't |
| * turn this stuff off completely if we want to do "exact" GC. |
| * |
| * TODO: cite source? |
| * Confirmed here: |
| * - code array must not be empty |
| * - (N/A) code_length must be less than 65536 |
| * Confirmed by dvmComputeCodeWidths(): |
| * - opcode of first instruction begins at index 0 |
| * - only documented instructions may appear |
| * - each instruction follows the last |
| * - last byte of last instruction is at (code_length-1) |
| */ |
| static bool verifyMethod(Method* meth) |
| { |
| bool result = false; |
| int newInstanceCount; |
| |
| /* |
| * Verifier state blob. Various values will be cached here so we |
| * can avoid expensive lookups and pass fewer arguments around. |
| */ |
| VerifierData vdata; |
| #if 1 // ndef NDEBUG |
| memset(&vdata, 0x99, sizeof(vdata)); |
| #endif |
| |
| vdata.method = meth; |
| vdata.insnsSize = dvmGetMethodInsnsSize(meth); |
| vdata.insnRegCount = meth->registersSize; |
| vdata.insnFlags = NULL; |
| vdata.uninitMap = NULL; |
| |
| /* |
| * If there aren't any instructions, make sure that's expected, then |
| * exit successfully. Note: for native methods, meth->insns gets set |
| * to a native function pointer on first call, so don't use that as |
| * an indicator. |
| */ |
| if (vdata.insnsSize == 0) { |
| if (!dvmIsNativeMethod(meth) && !dvmIsAbstractMethod(meth)) { |
| LOG_VFY_METH(meth, |
| "VFY: zero-length code in concrete non-native method\n"); |
| goto bail; |
| } |
| |
| goto success; |
| } |
| |
| /* |
| * Sanity-check the register counts. ins + locals = registers, so make |
| * sure that ins <= registers. |
| */ |
| if (meth->insSize > meth->registersSize) { |
| LOG_VFY_METH(meth, "VFY: bad register counts (ins=%d regs=%d)\n", |
| meth->insSize, meth->registersSize); |
| goto bail; |
| } |
| |
| /* |
| * Allocate and populate an array to hold instruction data. |
| * |
| * TODO: Consider keeping a reusable pre-allocated array sitting |
| * around for smaller methods. |
| */ |
| vdata.insnFlags = (InsnFlags*) |
| calloc(dvmGetMethodInsnsSize(meth), sizeof(InsnFlags)); |
| if (vdata.insnFlags == NULL) |
| goto bail; |
| |
| /* |
| * Compute the width of each instruction and store the result in insnFlags. |
| * Count up the #of occurrences of new-instance instructions while we're |
| * at it. |
| */ |
| if (!dvmComputeCodeWidths(meth, vdata.insnFlags, &newInstanceCount)) |
| goto bail; |
| |
| /* |
| * Allocate a map to hold the classes of uninitialized instances. |
| */ |
| vdata.uninitMap = dvmCreateUninitInstanceMap(meth, vdata.insnFlags, |
| newInstanceCount); |
| if (vdata.uninitMap == NULL) |
| goto bail; |
| |
| /* |
| * Set the "in try" flags for all instructions guarded by a "try" block. |
| */ |
| if (!dvmSetTryFlags(meth, vdata.insnFlags)) |
| goto bail; |
| |
| /* |
| * Perform static instruction verification. |
| */ |
| if (!verifyInstructions(&vdata)) |
| goto bail; |
| |
| /* |
| * Do code-flow analysis. Do this after verifying the branch targets |
| * so we don't need to worry about it here. |
| * |
| * If there are no registers, we don't need to do much in the way of |
| * analysis, but we still need to verify that nothing actually tries |
| * to use a register. |
| */ |
| if (!dvmVerifyCodeFlow(&vdata)) { |
| //LOGD("+++ %s failed code flow\n", meth->name); |
| goto bail; |
| } |
| |
| success: |
| result = true; |
| |
| bail: |
| dvmFreeUninitInstanceMap(vdata.uninitMap); |
| free(vdata.insnFlags); |
| return result; |
| } |
| |
| |
| /* |
| * Verify an array data table. "curOffset" is the offset of the fill-array-data |
| * instruction. |
| */ |
| static bool checkArrayData(const Method* meth, int curOffset) |
| { |
| const int insnCount = dvmGetMethodInsnsSize(meth); |
| const u2* insns = meth->insns + curOffset; |
| const u2* arrayData; |
| int valueCount, valueWidth, tableSize; |
| int offsetToArrayData; |
| |
| assert(curOffset >= 0 && curOffset < insnCount); |
| |
| /* make sure the start of the array data table is in range */ |
| offsetToArrayData = insns[1] | (((s4)insns[2]) << 16); |
| if (curOffset + offsetToArrayData < 0 || |
| curOffset + offsetToArrayData + 2 >= insnCount) |
| { |
| LOG_VFY_METH(meth, |
| "VFY: invalid array data start: at %d, data offset %d, count %d\n", |
| curOffset, offsetToArrayData, insnCount); |
| return false; |
| } |
| |
| /* offset to array data table is a relative branch-style offset */ |
| arrayData = insns + offsetToArrayData; |
| |
| /* make sure the table is 32-bit aligned */ |
| if ((((u4) arrayData) & 0x03) != 0) { |
| LOG_VFY_METH(meth, |
| "VFY: unaligned array data table: at %d, data offset %d\n", |
| curOffset, offsetToArrayData); |
| return false; |
| } |
| |
| valueWidth = arrayData[1]; |
| valueCount = *(u4*)(&arrayData[2]); |
| |
| tableSize = 4 + (valueWidth * valueCount + 1) / 2; |
| |
| /* make sure the end of the switch is in range */ |
| if (curOffset + offsetToArrayData + tableSize > insnCount) { |
| LOG_VFY_METH(meth, |
| "VFY: invalid array data end: at %d, data offset %d, end %d, " |
| "count %d\n", |
| curOffset, offsetToArrayData, |
| curOffset + offsetToArrayData + tableSize, |
| insnCount); |
| return false; |
| } |
| |
| return true; |
| } |
| |
| |
| /* |
| * Decode the current instruction. |
| */ |
| static void decodeInstruction(const Method* meth, int insnIdx, |
| DecodedInstruction* pDecInsn) |
| { |
| dexDecodeInstruction(gDvm.instrFormat, meth->insns + insnIdx, pDecInsn); |
| } |
| |
| |
| /* |
| * Perform static checks on a "new-instance" instruction. Specifically, |
| * make sure the class reference isn't for an array class. |
| * |
| * We don't need the actual class, just a pointer to the class name. |
| */ |
| static bool checkNewInstance(const Method* meth, int insnIdx) |
| { |
| DvmDex* pDvmDex = meth->clazz->pDvmDex; |
| DecodedInstruction decInsn; |
| const char* classDescriptor; |
| u4 idx; |
| |
| decodeInstruction(meth, insnIdx, &decInsn); |
| idx = decInsn.vB; // 2nd item |
| if (idx >= pDvmDex->pHeader->typeIdsSize) { |
| LOG_VFY_METH(meth, "VFY: bad type index %d (max %d)\n", |
| idx, pDvmDex->pHeader->typeIdsSize); |
| return false; |
| } |
| |
| classDescriptor = dexStringByTypeIdx(pDvmDex->pDexFile, idx); |
| if (classDescriptor[0] != 'L') { |
| LOG_VFY_METH(meth, "VFY: can't call new-instance on type '%s'\n", |
| classDescriptor); |
| return false; |
| } |
| |
| return true; |
| } |
| |
| /* |
| * Perform static checks on a "new-array" instruction. Specifically, make |
| * sure they aren't creating an array of arrays that causes the number of |
| * dimensions to exceed 255. |
| */ |
| static bool checkNewArray(const Method* meth, int insnIdx) |
| { |
| DvmDex* pDvmDex = meth->clazz->pDvmDex; |
| DecodedInstruction decInsn; |
| const char* classDescriptor; |
| u4 idx; |
| |
| decodeInstruction(meth, insnIdx, &decInsn); |
| idx = decInsn.vC; // 3rd item |
| if (idx >= pDvmDex->pHeader->typeIdsSize) { |
| LOG_VFY_METH(meth, "VFY: bad type index %d (max %d)\n", |
| idx, pDvmDex->pHeader->typeIdsSize); |
| return false; |
| } |
| |
| classDescriptor = dexStringByTypeIdx(pDvmDex->pDexFile, idx); |
| |
| int bracketCount = 0; |
| const char* cp = classDescriptor; |
| while (*cp++ == '[') |
| bracketCount++; |
| |
| if (bracketCount == 0) { |
| /* The given class must be an array type. */ |
| LOG_VFY_METH(meth, "VFY: can't new-array class '%s' (not an array)\n", |
| classDescriptor); |
| return false; |
| } else if (bracketCount > 255) { |
| /* It is illegal to create an array of more than 255 dimensions. */ |
| LOG_VFY_METH(meth, "VFY: can't new-array class '%s' (exceeds limit)\n", |
| classDescriptor); |
| return false; |
| } |
| |
| return true; |
| } |
| |
| /* |
| * Perform static checks on an instruction that takes a class constant. |
| * Ensure that the class index is in the valid range. |
| */ |
| static bool checkTypeIndex(const Method* meth, int insnIdx, bool useB) |
| { |
| DvmDex* pDvmDex = meth->clazz->pDvmDex; |
| DecodedInstruction decInsn; |
| u4 idx; |
| |
| decodeInstruction(meth, insnIdx, &decInsn); |
| if (useB) |
| idx = decInsn.vB; |
| else |
| idx = decInsn.vC; |
| if (idx >= pDvmDex->pHeader->typeIdsSize) { |
| LOG_VFY_METH(meth, "VFY: bad type index %d (max %d)\n", |
| idx, pDvmDex->pHeader->typeIdsSize); |
| return false; |
| } |
| |
| return true; |
| } |
| |
| /* |
| * Perform static checks on a field get or set instruction. All we do |
| * here is ensure that the field index is in the valid range. |
| */ |
| static bool checkFieldIndex(const Method* meth, int insnIdx, bool useB) |
| { |
| DvmDex* pDvmDex = meth->clazz->pDvmDex; |
| DecodedInstruction decInsn; |
| u4 idx; |
| |
| decodeInstruction(meth, insnIdx, &decInsn); |
| if (useB) |
| idx = decInsn.vB; |
| else |
| idx = decInsn.vC; |
| if (idx >= pDvmDex->pHeader->fieldIdsSize) { |
| LOG_VFY_METH(meth, |
| "VFY: bad field index %d (max %d) at offset 0x%04x\n", |
| idx, pDvmDex->pHeader->fieldIdsSize, insnIdx); |
| return false; |
| } |
| |
| return true; |
| } |
| |
| /* |
| * Perform static checks on a method invocation instruction. All we do |
| * here is ensure that the method index is in the valid range. |
| */ |
| static bool checkMethodIndex(const Method* meth, int insnIdx) |
| { |
| DvmDex* pDvmDex = meth->clazz->pDvmDex; |
| DecodedInstruction decInsn; |
| |
| decodeInstruction(meth, insnIdx, &decInsn); |
| if (decInsn.vB >= pDvmDex->pHeader->methodIdsSize) { |
| LOG_VFY_METH(meth, "VFY: bad method index %d (max %d)\n", |
| decInsn.vB, pDvmDex->pHeader->methodIdsSize); |
| return false; |
| } |
| |
| return true; |
| } |
| |
| /* |
| * Perform static checks on a string constant instruction. All we do |
| * here is ensure that the string index is in the valid range. |
| */ |
| static bool checkStringIndex(const Method* meth, int insnIdx) |
| { |
| DvmDex* pDvmDex = meth->clazz->pDvmDex; |
| DecodedInstruction decInsn; |
| |
| decodeInstruction(meth, insnIdx, &decInsn); |
| if (decInsn.vB >= pDvmDex->pHeader->stringIdsSize) { |
| LOG_VFY_METH(meth, "VFY: bad string index %d (max %d)\n", |
| decInsn.vB, pDvmDex->pHeader->stringIdsSize); |
| return false; |
| } |
| |
| return true; |
| } |
| |
| /* |
| * Perform static verification on instructions. |
| * |
| * As a side effect, this sets the "branch target" flags in InsnFlags. |
| * |
| * "(CF)" items are handled during code-flow analysis. |
| * |
| * v3 4.10.1 |
| * - target of each jump and branch instruction must be valid |
| * - targets of switch statements must be valid |
| * - (CF) operands referencing constant pool entries must be valid |
| * - (CF) operands of getfield, putfield, getstatic, putstatic must be valid |
| * - (new) verify operands of "quick" field ops |
| * - (CF) operands of method invocation instructions must be valid |
| * - (new) verify operands of "quick" method invoke ops |
| * - (CF) only invoke-direct can call a method starting with '<' |
| * - (CF) <clinit> must never be called explicitly |
| * - (CF) operands of instanceof, checkcast, new (and variants) must be valid |
| * - new-array[-type] limited to 255 dimensions |
| * - can't use "new" on an array class |
| * - (?) limit dimensions in multi-array creation |
| * - (CF) local variable load/store register values must be in valid range |
| * |
| * v3 4.11.1.2 |
| * - branches must be within the bounds of the code array |
| * - targets of all control-flow instructions are the start of an instruction |
| * - (CF) register accesses fall within range of allocated registers |
| * - (N/A) access to constant pool must be of appropriate type |
| * - (CF) code does not end in the middle of an instruction |
| * - (CF) execution cannot fall off the end of the code |
| * - (earlier) for each exception handler, the "try" area must begin and |
| * end at the start of an instruction (end can be at the end of the code) |
| * - (earlier) for each exception handler, the handler must start at a valid |
| * instruction |
| * |
| * TODO: move some of the "CF" items in here for better performance (the |
| * code-flow analysis sometimes has to process the same instruction several |
| * times). |
| */ |
| static bool verifyInstructions(VerifierData* vdata) |
| { |
| const Method* meth = vdata->method; |
| InsnFlags* insnFlags = vdata->insnFlags; |
| const size_t insnCount = vdata->insnsSize; |
| const u2* insns = meth->insns; |
| int i; |
| |
| /* the start of the method is a "branch target" */ |
| dvmInsnSetBranchTarget(insnFlags, 0, true); |
| |
| for (i = 0; i < (int) insnCount; /**/) { |
| /* |
| * These types of instructions can be GC points. To support precise |
| * GC, all such instructions must export the PC in the interpreter, |
| * or the GC won't be able to identify the current PC for the thread. |
| */ |
| static const int gcMask = kInstrCanBranch | kInstrCanSwitch | |
| kInstrCanThrow | kInstrCanReturn; |
| |
| int width = dvmInsnGetWidth(insnFlags, i); |
| OpCode opcode = *insns & 0xff; |
| InstructionFlags opFlags = dexGetInstrFlags(gDvm.instrFlags, opcode); |
| |
| if ((opFlags & gcMask) != 0) { |
| /* |
| * This instruction is probably a GC point. Branch instructions |
| * only qualify if they go backward, so we need to check the |
| * offset. |
| */ |
| int offset = -1; |
| bool unused; |
| if (dvmGetBranchTarget(meth, insnFlags, i, &offset, &unused)) { |
| if (offset <= 0) { |
| dvmInsnSetGcPoint(insnFlags, i, true); |
| } |
| } else { |
| /* not a branch target */ |
| dvmInsnSetGcPoint(insnFlags, i, true); |
| } |
| } |
| |
| switch (opcode) { |
| case OP_NOP: |
| /* plain no-op or switch table data; nothing to do here */ |
| break; |
| |
| case OP_CONST_STRING: |
| case OP_CONST_STRING_JUMBO: |
| if (!checkStringIndex(meth, i)) |
| return false; |
| break; |
| |
| case OP_CONST_CLASS: |
| case OP_CHECK_CAST: |
| if (!checkTypeIndex(meth, i, true)) |
| return false; |
| break; |
| case OP_INSTANCE_OF: |
| if (!checkTypeIndex(meth, i, false)) |
| return false; |
| break; |
| |
| case OP_PACKED_SWITCH: |
| case OP_SPARSE_SWITCH: |
| /* verify the associated table */ |
| if (!dvmCheckSwitchTargets(meth, insnFlags, i)) |
| return false; |
| break; |
| |
| case OP_FILL_ARRAY_DATA: |
| /* verify the associated table */ |
| if (!checkArrayData(meth, i)) |
| return false; |
| break; |
| |
| case OP_GOTO: |
| case OP_GOTO_16: |
| case OP_IF_EQ: |
| case OP_IF_NE: |
| case OP_IF_LT: |
| case OP_IF_GE: |
| case OP_IF_GT: |
| case OP_IF_LE: |
| case OP_IF_EQZ: |
| case OP_IF_NEZ: |
| case OP_IF_LTZ: |
| case OP_IF_GEZ: |
| case OP_IF_GTZ: |
| case OP_IF_LEZ: |
| /* check the destination */ |
| if (!dvmCheckBranchTarget(meth, insnFlags, i, false)) |
| return false; |
| break; |
| case OP_GOTO_32: |
| /* check the destination; self-branch is okay */ |
| if (!dvmCheckBranchTarget(meth, insnFlags, i, true)) |
| return false; |
| break; |
| |
| case OP_NEW_INSTANCE: |
| if (!checkNewInstance(meth, i)) |
| return false; |
| break; |
| |
| case OP_NEW_ARRAY: |
| if (!checkNewArray(meth, i)) |
| return false; |
| break; |
| |
| case OP_FILLED_NEW_ARRAY: |
| if (!checkTypeIndex(meth, i, true)) |
| return false; |
| break; |
| case OP_FILLED_NEW_ARRAY_RANGE: |
| if (!checkTypeIndex(meth, i, true)) |
| return false; |
| break; |
| |
| case OP_IGET: |
| case OP_IGET_WIDE: |
| case OP_IGET_OBJECT: |
| case OP_IGET_BOOLEAN: |
| case OP_IGET_BYTE: |
| case OP_IGET_CHAR: |
| case OP_IGET_SHORT: |
| case OP_IPUT: |
| case OP_IPUT_WIDE: |
| case OP_IPUT_OBJECT: |
| case OP_IPUT_BOOLEAN: |
| case OP_IPUT_BYTE: |
| case OP_IPUT_CHAR: |
| case OP_IPUT_SHORT: |
| /* check the field index */ |
| if (!checkFieldIndex(meth, i, false)) |
| return false; |
| break; |
| case OP_SGET: |
| case OP_SGET_WIDE: |
| case OP_SGET_OBJECT: |
| case OP_SGET_BOOLEAN: |
| case OP_SGET_BYTE: |
| case OP_SGET_CHAR: |
| case OP_SGET_SHORT: |
| case OP_SPUT: |
| case OP_SPUT_WIDE: |
| case OP_SPUT_OBJECT: |
| case OP_SPUT_BOOLEAN: |
| case OP_SPUT_BYTE: |
| case OP_SPUT_CHAR: |
| case OP_SPUT_SHORT: |
| /* check the field index */ |
| if (!checkFieldIndex(meth, i, true)) |
| return false; |
| break; |
| |
| case OP_INVOKE_VIRTUAL: |
| case OP_INVOKE_SUPER: |
| case OP_INVOKE_DIRECT: |
| case OP_INVOKE_STATIC: |
| case OP_INVOKE_INTERFACE: |
| case OP_INVOKE_VIRTUAL_RANGE: |
| case OP_INVOKE_SUPER_RANGE: |
| case OP_INVOKE_DIRECT_RANGE: |
| case OP_INVOKE_STATIC_RANGE: |
| case OP_INVOKE_INTERFACE_RANGE: |
| /* check the method index */ |
| if (!checkMethodIndex(meth, i)) |
| return false; |
| break; |
| |
| case OP_EXECUTE_INLINE: |
| case OP_INVOKE_DIRECT_EMPTY: |
| case OP_IGET_QUICK: |
| case OP_IGET_WIDE_QUICK: |
| case OP_IGET_OBJECT_QUICK: |
| case OP_IPUT_QUICK: |
| case OP_IPUT_WIDE_QUICK: |
| case OP_IPUT_OBJECT_QUICK: |
| case OP_INVOKE_VIRTUAL_QUICK: |
| case OP_INVOKE_VIRTUAL_QUICK_RANGE: |
| case OP_INVOKE_SUPER_QUICK: |
| case OP_INVOKE_SUPER_QUICK_RANGE: |
| LOG_VFY("VFY: not expecting optimized instructions\n"); |
| return false; |
| break; |
| |
| default: |
| /* nothing to do */ |
| break; |
| } |
| |
| assert(width > 0); |
| i += width; |
| insns += width; |
| } |
| |
| /* make sure the last instruction ends at the end of the insn area */ |
| if (i != (int) insnCount) { |
| LOG_VFY_METH(meth, |
| "VFY: code did not end when expected (end at %d, count %d)\n", |
| i, insnCount); |
| return false; |
| } |
| |
| return true; |
| } |
