1 // ASM: a very small and fast Java bytecode manipulation framework 2 // Copyright (c) 2000-2011 INRIA, France Telecom 3 // All rights reserved. 4 // 5 // Redistribution and use in source and binary forms, with or without 6 // modification, are permitted provided that the following conditions 7 // are met: 8 // 1. Redistributions of source code must retain the above copyright 9 // notice, this list of conditions and the following disclaimer. 10 // 2. Redistributions in binary form must reproduce the above copyright 11 // notice, this list of conditions and the following disclaimer in the 12 // documentation and/or other materials provided with the distribution. 13 // 3. Neither the name of the copyright holders nor the names of its 14 // contributors may be used to endorse or promote products derived from 15 // this software without specific prior written permission. 16 // 17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 18 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 21 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 22 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 23 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 24 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 25 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 26 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 27 // THE POSSIBILITY OF SUCH DAMAGE. 28 package org.objectweb.asm.util; 29 30 import java.util.Collections; 31 import java.util.List; 32 import org.objectweb.asm.Opcodes; 33 import org.objectweb.asm.Type; 34 import org.objectweb.asm.tree.AbstractInsnNode; 35 import org.objectweb.asm.tree.FrameNode; 36 import org.objectweb.asm.tree.InsnList; 37 import org.objectweb.asm.tree.InsnNode; 38 import org.objectweb.asm.tree.JumpInsnNode; 39 import org.objectweb.asm.tree.LabelNode; 40 import org.objectweb.asm.tree.LookupSwitchInsnNode; 41 import org.objectweb.asm.tree.MethodNode; 42 import org.objectweb.asm.tree.TableSwitchInsnNode; 43 import org.objectweb.asm.tree.TryCatchBlockNode; 44 import org.objectweb.asm.tree.TypeInsnNode; 45 import org.objectweb.asm.tree.analysis.Analyzer; 46 import org.objectweb.asm.tree.analysis.AnalyzerException; 47 import org.objectweb.asm.tree.analysis.Frame; 48 import org.objectweb.asm.tree.analysis.Interpreter; 49 import org.objectweb.asm.tree.analysis.Value; 50 51 /** 52 * An {@link Analyzer} subclass which checks that methods provide stack map frames where expected 53 * (i.e. at jump target and after instructions without immediate successor), and that these stack 54 * map frames are valid (for the provided interpreter; they may still be invalid for the JVM, if the 55 * {@link Interpreter} uses a simplified type system compared to the JVM verifier). This is done in 56 * two steps: 57 * 58 * <ul> 59 * <li>First, the stack map frames in {@link FrameNode}s are expanded, and stored at their 60 * respective instruction offsets. The expansion process uncompresses the APPEND, CHOP and 61 * SAME frames to FULL frames. It also converts the stack map frame verification types to 62 * {@link Value}s, via the provided {@link Interpreter}. The expansion is done in {@link 63 * #expandFrames}, by looking at each {@link FrameNode} in sequence (compressed frames are 64 * defined relatively to the previous {@link FrameNode}, or the implicit first frame). The 65 * actual decompression is done in {@link #expandFrame}, and the type conversion in {@link 66 * #newFrameValue}. 67 * <li>Next, the method instructions are checked in sequence. Starting from the implicit initial 68 * frame, the execution of each instruction <em>i</em> is simulated on the current stack map 69 * frame, with the {@link Frame#execute} method. This gives a new stack map frame <em>f</em>, 70 * representing the stack map frame state after the execution of <em>i</em>. Then: 71 * <ul> 72 * <li>If there is a next instruction and if the control flow cannot continue to it (e.g. if 73 * <em>i</em> is a RETURN or an ATHROW, for instance): an existing stack map frame 74 * <em>f0</em> (coming from the first step) is expected after <em>i</em>. 75 * <li>If there is a next instruction and if the control flow can continue to it (e.g. if 76 * <em>i</em> is a ALOAD, for instance): either there an existing stack map frame 77 * <em>f0</em> (coming from the first step) after <em>i</em>, or there is none. In the 78 * first case <em>f</em> and <em>f0</em> must be <em>compatible</em>: the types in 79 * <em>f</em> must be sub types of the corresponding types in the existing frame 80 * <em>f0</em> (otherwise an exception is thrown). In the second case, <em>f0</em> is 81 * simply set to the value of <em>f</em>. 82 * <li>If the control flow can continue to some instruction <em>j</em> (e.g. if <em>i</em> 83 * is an IF_EQ, for instance): an existing stack map frame <em>f0</em> (coming from the 84 * first step) is expected at <em>j</em>, which must be compatible with <em>f</em> (as 85 * defined previously). 86 * </ul> 87 * The sequential loop over the instructions is done in {@link #init}, which is called from 88 * the {@link Analyzer#analyze} method. Cases where the control flow cannot continue to the 89 * next instruction are handled in {@link #endControlFlow}. Cases where the control flow can 90 * continue to the next instruction, or jump to another instruction, are handled in {@link 91 * #checkFrame}. This method checks that an existing stack map frame is present when required, 92 * and checks the stack map frames compatibility with {@link #checkMerge}. 93 * </ul> 94 * 95 * @author Eric Bruneton 96 * @param <V> type of the {@link Value} used for the analysis. 97 */ 98 class CheckFrameAnalyzer<V extends Value> extends Analyzer<V> { 99 100 /** The interpreter to use to symbolically interpret the bytecode instructions. */ 101 private final Interpreter<V> interpreter; 102 103 /** The instructions of the currently analyzed method. */ 104 private InsnList insnList; 105 106 /** 107 * The number of locals in the last stack map frame processed by {@link expandFrame}. Long and 108 * double values are represented with two elements. 109 */ 110 private int currentLocals; 111 CheckFrameAnalyzer(final Interpreter<V> interpreter)112 CheckFrameAnalyzer(final Interpreter<V> interpreter) { 113 super(interpreter); 114 this.interpreter = interpreter; 115 } 116 117 @Override init(final String owner, final MethodNode method)118 protected void init(final String owner, final MethodNode method) throws AnalyzerException { 119 insnList = method.instructions; 120 currentLocals = Type.getArgumentsAndReturnSizes(method.desc) >> 2; 121 if ((method.access & Opcodes.ACC_STATIC) != 0) { 122 currentLocals -= 1; 123 } 124 125 Frame<V>[] frames = getFrames(); 126 Frame<V> currentFrame = frames[0]; 127 expandFrames(owner, method, currentFrame); 128 for (int insnIndex = 0; insnIndex < insnList.size(); ++insnIndex) { 129 Frame<V> oldFrame = frames[insnIndex]; 130 131 // Simulate the execution of this instruction. 132 AbstractInsnNode insnNode = null; 133 try { 134 insnNode = method.instructions.get(insnIndex); 135 int insnOpcode = insnNode.getOpcode(); 136 int insnType = insnNode.getType(); 137 138 if (insnType == AbstractInsnNode.LABEL 139 || insnType == AbstractInsnNode.LINE 140 || insnType == AbstractInsnNode.FRAME) { 141 checkFrame(insnIndex + 1, oldFrame, /* requireFrame = */ false); 142 } else { 143 currentFrame.init(oldFrame).execute(insnNode, interpreter); 144 145 if (insnNode instanceof JumpInsnNode) { 146 if (insnOpcode == JSR) { 147 throw new AnalyzerException(insnNode, "JSR instructions are unsupported"); 148 } 149 JumpInsnNode jumpInsn = (JumpInsnNode) insnNode; 150 int targetInsnIndex = insnList.indexOf(jumpInsn.label); 151 checkFrame(targetInsnIndex, currentFrame, /* requireFrame = */ true); 152 if (insnOpcode == GOTO) { 153 endControlFlow(insnIndex); 154 } else { 155 checkFrame(insnIndex + 1, currentFrame, /* requireFrame = */ false); 156 } 157 } else if (insnNode instanceof LookupSwitchInsnNode) { 158 LookupSwitchInsnNode lookupSwitchInsn = (LookupSwitchInsnNode) insnNode; 159 int targetInsnIndex = insnList.indexOf(lookupSwitchInsn.dflt); 160 checkFrame(targetInsnIndex, currentFrame, /* requireFrame = */ true); 161 for (int i = 0; i < lookupSwitchInsn.labels.size(); ++i) { 162 LabelNode label = lookupSwitchInsn.labels.get(i); 163 targetInsnIndex = insnList.indexOf(label); 164 currentFrame.initJumpTarget(insnOpcode, label); 165 checkFrame(targetInsnIndex, currentFrame, /* requireFrame = */ true); 166 } 167 endControlFlow(insnIndex); 168 } else if (insnNode instanceof TableSwitchInsnNode) { 169 TableSwitchInsnNode tableSwitchInsn = (TableSwitchInsnNode) insnNode; 170 int targetInsnIndex = insnList.indexOf(tableSwitchInsn.dflt); 171 currentFrame.initJumpTarget(insnOpcode, tableSwitchInsn.dflt); 172 checkFrame(targetInsnIndex, currentFrame, /* requireFrame = */ true); 173 newControlFlowEdge(insnIndex, targetInsnIndex); 174 for (int i = 0; i < tableSwitchInsn.labels.size(); ++i) { 175 LabelNode label = tableSwitchInsn.labels.get(i); 176 currentFrame.initJumpTarget(insnOpcode, label); 177 targetInsnIndex = insnList.indexOf(label); 178 checkFrame(targetInsnIndex, currentFrame, /* requireFrame = */ true); 179 } 180 endControlFlow(insnIndex); 181 } else if (insnOpcode == RET) { 182 throw new AnalyzerException(insnNode, "RET instructions are unsupported"); 183 } else if (insnOpcode != ATHROW && (insnOpcode < IRETURN || insnOpcode > RETURN)) { 184 checkFrame(insnIndex + 1, currentFrame, /* requireFrame = */ false); 185 } else { 186 endControlFlow(insnIndex); 187 } 188 } 189 190 List<TryCatchBlockNode> insnHandlers = getHandlers(insnIndex); 191 if (insnHandlers != null) { 192 for (TryCatchBlockNode tryCatchBlock : insnHandlers) { 193 Type catchType; 194 if (tryCatchBlock.type == null) { 195 catchType = Type.getObjectType("java/lang/Throwable"); 196 } else { 197 catchType = Type.getObjectType(tryCatchBlock.type); 198 } 199 Frame<V> handler = newFrame(oldFrame); 200 handler.clearStack(); 201 handler.push(interpreter.newExceptionValue(tryCatchBlock, handler, catchType)); 202 checkFrame(insnList.indexOf(tryCatchBlock.handler), handler, /* requireFrame = */ true); 203 } 204 } 205 206 if (!hasNextJvmInsnOrFrame(insnIndex)) { 207 break; 208 } 209 } catch (AnalyzerException e) { 210 throw new AnalyzerException( 211 e.node, "Error at instruction " + insnIndex + ": " + e.getMessage(), e); 212 } catch (RuntimeException e) { 213 // DontCheck(IllegalCatch): can't be fixed, for backward compatibility. 214 throw new AnalyzerException( 215 insnNode, "Error at instruction " + insnIndex + ": " + e.getMessage(), e); 216 } 217 } 218 } 219 220 /** 221 * Expands the {@link FrameNode} "instructions" of the given method into {@link Frame} objects and 222 * stores them at the corresponding indices of the {@link #frames} array. The expanded frames are 223 * also associated with the label and line number nodes immediately preceding each frame node. 224 * 225 * @param owner the internal name of the class to which 'method' belongs. 226 * @param method the method whose frames must be expanded. 227 * @param initialFrame the implicit initial frame of 'method'. 228 * @throws AnalyzerException if the stack map frames of 'method', i.e. its FrameNode 229 * "instructions", are invalid. 230 */ expandFrames( final String owner, final MethodNode method, final Frame<V> initialFrame)231 private void expandFrames( 232 final String owner, final MethodNode method, final Frame<V> initialFrame) 233 throws AnalyzerException { 234 int lastJvmOrFrameInsnIndex = -1; 235 Frame<V> currentFrame = initialFrame; 236 int currentInsnIndex = 0; 237 for (AbstractInsnNode insnNode : method.instructions) { 238 if (insnNode instanceof FrameNode) { 239 try { 240 currentFrame = expandFrame(owner, currentFrame, (FrameNode) insnNode); 241 } catch (AnalyzerException e) { 242 throw new AnalyzerException( 243 e.node, "Error at instruction " + currentInsnIndex + ": " + e.getMessage(), e); 244 } 245 for (int index = lastJvmOrFrameInsnIndex + 1; index <= currentInsnIndex; ++index) { 246 getFrames()[index] = currentFrame; 247 } 248 } 249 if (isJvmInsnNode(insnNode) || insnNode instanceof FrameNode) { 250 lastJvmOrFrameInsnIndex = currentInsnIndex; 251 } 252 currentInsnIndex += 1; 253 } 254 } 255 256 /** 257 * Returns the expanded representation of the given {@link FrameNode}. 258 * 259 * @param owner the internal name of the class to which 'frameNode' belongs. 260 * @param previousFrame the frame before 'frameNode', in expanded form. 261 * @param frameNode a possibly compressed stack map frame. 262 * @return the expanded version of 'frameNode'. 263 * @throws AnalyzerException if 'frameNode' is invalid. 264 */ expandFrame( final String owner, final Frame<V> previousFrame, final FrameNode frameNode)265 private Frame<V> expandFrame( 266 final String owner, final Frame<V> previousFrame, final FrameNode frameNode) 267 throws AnalyzerException { 268 Frame<V> frame = newFrame(previousFrame); 269 List<Object> locals = frameNode.local == null ? Collections.emptyList() : frameNode.local; 270 int currentLocal = currentLocals; 271 switch (frameNode.type) { 272 case Opcodes.F_NEW: 273 case Opcodes.F_FULL: 274 currentLocal = 0; 275 // fall through 276 case Opcodes.F_APPEND: 277 for (Object type : locals) { 278 V value = newFrameValue(owner, frameNode, type); 279 if (currentLocal + value.getSize() > frame.getLocals()) { 280 throw new AnalyzerException(frameNode, "Cannot append more locals than maxLocals"); 281 } 282 frame.setLocal(currentLocal++, value); 283 if (value.getSize() == 2) { 284 frame.setLocal(currentLocal++, interpreter.newValue(null)); 285 } 286 } 287 break; 288 case Opcodes.F_CHOP: 289 for (Object unusedType : locals) { 290 if (currentLocal <= 0) { 291 throw new AnalyzerException(frameNode, "Cannot chop more locals than defined"); 292 } 293 if (currentLocal > 1 && frame.getLocal(currentLocal - 2).getSize() == 2) { 294 currentLocal -= 2; 295 } else { 296 currentLocal -= 1; 297 } 298 } 299 break; 300 case Opcodes.F_SAME: 301 case Opcodes.F_SAME1: 302 break; 303 default: 304 throw new AnalyzerException(frameNode, "Illegal frame type " + frameNode.type); 305 } 306 currentLocals = currentLocal; 307 while (currentLocal < frame.getLocals()) { 308 frame.setLocal(currentLocal++, interpreter.newValue(null)); 309 } 310 311 List<Object> stack = frameNode.stack == null ? Collections.emptyList() : frameNode.stack; 312 frame.clearStack(); 313 for (Object type : stack) { 314 frame.push(newFrameValue(owner, frameNode, type)); 315 } 316 return frame; 317 } 318 319 /** 320 * Creates a new {@link Value} that represents the given stack map frame type. 321 * 322 * @param owner the internal name of the class to which 'frameNode' belongs. 323 * @param frameNode the stack map frame to which 'type' belongs. 324 * @param type an Integer, String or LabelNode object representing a primitive, reference or 325 * uninitialized a stack map frame type, respectively. See {@link FrameNode}. 326 * @return a value that represents the given type. 327 * @throws AnalyzerException if 'type' is an invalid stack map frame type. 328 */ newFrameValue(final String owner, final FrameNode frameNode, final Object type)329 private V newFrameValue(final String owner, final FrameNode frameNode, final Object type) 330 throws AnalyzerException { 331 if (type == Opcodes.TOP) { 332 return interpreter.newValue(null); 333 } else if (type == Opcodes.INTEGER) { 334 return interpreter.newValue(Type.INT_TYPE); 335 } else if (type == Opcodes.FLOAT) { 336 return interpreter.newValue(Type.FLOAT_TYPE); 337 } else if (type == Opcodes.LONG) { 338 return interpreter.newValue(Type.LONG_TYPE); 339 } else if (type == Opcodes.DOUBLE) { 340 return interpreter.newValue(Type.DOUBLE_TYPE); 341 } else if (type == Opcodes.NULL) { 342 return interpreter.newOperation(new InsnNode(Opcodes.ACONST_NULL)); 343 } else if (type == Opcodes.UNINITIALIZED_THIS) { 344 return interpreter.newValue(Type.getObjectType(owner)); 345 } else if (type instanceof String) { 346 return interpreter.newValue(Type.getObjectType((String) type)); 347 } else if (type instanceof LabelNode) { 348 AbstractInsnNode referencedNode = (LabelNode) type; 349 while (referencedNode != null && !isJvmInsnNode(referencedNode)) { 350 referencedNode = referencedNode.getNext(); 351 } 352 if (referencedNode == null || referencedNode.getOpcode() != Opcodes.NEW) { 353 throw new AnalyzerException(frameNode, "LabelNode does not designate a NEW instruction"); 354 } 355 return interpreter.newValue(Type.getObjectType(((TypeInsnNode) referencedNode).desc)); 356 } 357 throw new AnalyzerException(frameNode, "Illegal stack map frame value " + type); 358 } 359 360 /** 361 * Checks that the given frame is compatible with the frame at the given instruction index, if 362 * any. If there is no frame at this instruction index and none is required, the frame at 363 * 'insnIndex' is set to the given frame. Otherwise, if the merge of the two frames is not equal 364 * to the current frame at 'insnIndex', an exception is thrown. 365 * 366 * @param insnIndex an instruction index. 367 * @param frame a frame. This frame is left unchanged by this method. 368 * @param requireFrame whether a frame must already exist or not in {@link #frames} at 369 * 'insnIndex'. 370 * @throws AnalyzerException if the frames have incompatible sizes or if the frame at 'insnIndex' 371 * is missing (if required) or not compatible with 'frame'. 372 */ checkFrame(final int insnIndex, final Frame<V> frame, final boolean requireFrame)373 private void checkFrame(final int insnIndex, final Frame<V> frame, final boolean requireFrame) 374 throws AnalyzerException { 375 Frame<V> oldFrame = getFrames()[insnIndex]; 376 if (oldFrame == null) { 377 if (requireFrame) { 378 throw new AnalyzerException(null, "Expected stack map frame at instruction " + insnIndex); 379 } 380 getFrames()[insnIndex] = newFrame(frame); 381 } else { 382 String error = checkMerge(frame, oldFrame); 383 if (error != null) { 384 throw new AnalyzerException( 385 null, 386 "Stack map frame incompatible with frame at instruction " 387 + insnIndex 388 + " (" 389 + error 390 + ")"); 391 } 392 } 393 } 394 395 /** 396 * Checks that merging the two given frames would not produce any change, i.e. that the types in 397 * the source frame are sub types of the corresponding types in the destination frame. 398 * 399 * @param srcFrame a source frame. This frame is left unchanged by this method. 400 * @param dstFrame a destination frame. This frame is left unchanged by this method. 401 * @return an error message if the frames have incompatible sizes, or if a type in the source 402 * frame is not a sub type of the corresponding type in the destination frame. Returns 403 * {@literal null} otherwise. 404 */ checkMerge(final Frame<V> srcFrame, final Frame<V> dstFrame)405 private String checkMerge(final Frame<V> srcFrame, final Frame<V> dstFrame) { 406 int numLocals = srcFrame.getLocals(); 407 if (numLocals != dstFrame.getLocals()) { 408 throw new AssertionError(); 409 } 410 for (int i = 0; i < numLocals; ++i) { 411 V v = interpreter.merge(srcFrame.getLocal(i), dstFrame.getLocal(i)); 412 if (!v.equals(dstFrame.getLocal(i))) { 413 return "incompatible types at local " 414 + i 415 + ": " 416 + srcFrame.getLocal(i) 417 + " and " 418 + dstFrame.getLocal(i); 419 } 420 } 421 int numStack = srcFrame.getStackSize(); 422 if (numStack != dstFrame.getStackSize()) { 423 return "incompatible stack heights"; 424 } 425 for (int i = 0; i < numStack; ++i) { 426 V v = interpreter.merge(srcFrame.getStack(i), dstFrame.getStack(i)); 427 if (!v.equals(dstFrame.getStack(i))) { 428 return "incompatible types at stack item " 429 + i 430 + ": " 431 + srcFrame.getStack(i) 432 + " and " 433 + dstFrame.getStack(i); 434 } 435 } 436 return null; 437 } 438 439 /** 440 * Ends the control flow graph at the given instruction. This method checks that there is an 441 * existing frame for the next instruction, if any. 442 * 443 * @param insnIndex an instruction index. 444 * @throws AnalyzerException if 'insnIndex' is not the last instruction and there is no frame at 445 * 'insnIndex' + 1 in {@link #getFrames}. 446 */ endControlFlow(final int insnIndex)447 private void endControlFlow(final int insnIndex) throws AnalyzerException { 448 if (hasNextJvmInsnOrFrame(insnIndex) && getFrames()[insnIndex + 1] == null) { 449 throw new AnalyzerException( 450 null, "Expected stack map frame at instruction " + (insnIndex + 1)); 451 } 452 } 453 454 /** 455 * Returns true if the given instruction is followed by a JVM instruction or a by stack map frame. 456 * 457 * @param insnIndex an instruction index. 458 * @return true if 'insnIndex' is followed by a JVM instruction or a by stack map frame. 459 */ hasNextJvmInsnOrFrame(final int insnIndex)460 private boolean hasNextJvmInsnOrFrame(final int insnIndex) { 461 AbstractInsnNode insn = insnList.get(insnIndex).getNext(); 462 while (insn != null) { 463 if (isJvmInsnNode(insn) || insn instanceof FrameNode) { 464 return true; 465 } 466 insn = insn.getNext(); 467 } 468 return false; 469 } 470 471 /** 472 * Returns true if the given instruction node corresponds to a real JVM instruction. 473 * 474 * @param insnNode an instruction node. 475 * @return true except for label, line number and stack map frame nodes. 476 */ isJvmInsnNode(final AbstractInsnNode insnNode)477 private static boolean isJvmInsnNode(final AbstractInsnNode insnNode) { 478 return insnNode.getOpcode() >= 0; 479 } 480 } 481