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 122 Frame<V>[] frames = getFrames(); 123 Frame<V> currentFrame = frames[0]; 124 expandFrames(owner, method, currentFrame); 125 for (int insnIndex = 0; insnIndex < insnList.size(); ++insnIndex) { 126 Frame<V> oldFrame = frames[insnIndex]; 127 128 // Simulate the execution of this instruction. 129 AbstractInsnNode insnNode = null; 130 try { 131 insnNode = method.instructions.get(insnIndex); 132 int insnOpcode = insnNode.getOpcode(); 133 int insnType = insnNode.getType(); 134 135 if (insnType == AbstractInsnNode.LABEL 136 || insnType == AbstractInsnNode.LINE 137 || insnType == AbstractInsnNode.FRAME) { 138 checkFrame(insnIndex + 1, oldFrame, /* requireFrame = */ false); 139 } else { 140 currentFrame.init(oldFrame).execute(insnNode, interpreter); 141 142 if (insnNode instanceof JumpInsnNode) { 143 if (insnOpcode == JSR) { 144 throw new AnalyzerException(insnNode, "JSR instructions are unsupported"); 145 } 146 JumpInsnNode jumpInsn = (JumpInsnNode) insnNode; 147 int targetInsnIndex = insnList.indexOf(jumpInsn.label); 148 checkFrame(targetInsnIndex, currentFrame, /* requireFrame = */ true); 149 if (insnOpcode == GOTO) { 150 endControlFlow(insnIndex); 151 } else { 152 checkFrame(insnIndex + 1, currentFrame, /* requireFrame = */ false); 153 } 154 } else if (insnNode instanceof LookupSwitchInsnNode) { 155 LookupSwitchInsnNode lookupSwitchInsn = (LookupSwitchInsnNode) insnNode; 156 int targetInsnIndex = insnList.indexOf(lookupSwitchInsn.dflt); 157 checkFrame(targetInsnIndex, currentFrame, /* requireFrame = */ true); 158 for (int i = 0; i < lookupSwitchInsn.labels.size(); ++i) { 159 LabelNode label = lookupSwitchInsn.labels.get(i); 160 targetInsnIndex = insnList.indexOf(label); 161 currentFrame.initJumpTarget(insnOpcode, label); 162 checkFrame(targetInsnIndex, currentFrame, /* requireFrame = */ true); 163 } 164 endControlFlow(insnIndex); 165 } else if (insnNode instanceof TableSwitchInsnNode) { 166 TableSwitchInsnNode tableSwitchInsn = (TableSwitchInsnNode) insnNode; 167 int targetInsnIndex = insnList.indexOf(tableSwitchInsn.dflt); 168 currentFrame.initJumpTarget(insnOpcode, tableSwitchInsn.dflt); 169 checkFrame(targetInsnIndex, currentFrame, /* requireFrame = */ true); 170 newControlFlowEdge(insnIndex, targetInsnIndex); 171 for (int i = 0; i < tableSwitchInsn.labels.size(); ++i) { 172 LabelNode label = tableSwitchInsn.labels.get(i); 173 currentFrame.initJumpTarget(insnOpcode, label); 174 targetInsnIndex = insnList.indexOf(label); 175 checkFrame(targetInsnIndex, currentFrame, /* requireFrame = */ true); 176 } 177 endControlFlow(insnIndex); 178 } else if (insnOpcode == RET) { 179 throw new AnalyzerException(insnNode, "RET instructions are unsupported"); 180 } else if (insnOpcode != ATHROW && (insnOpcode < IRETURN || insnOpcode > RETURN)) { 181 checkFrame(insnIndex + 1, currentFrame, /* requireFrame = */ false); 182 } else { 183 endControlFlow(insnIndex); 184 } 185 } 186 187 List<TryCatchBlockNode> insnHandlers = getHandlers(insnIndex); 188 if (insnHandlers != null) { 189 for (TryCatchBlockNode tryCatchBlock : insnHandlers) { 190 Type catchType; 191 if (tryCatchBlock.type == null) { 192 catchType = Type.getObjectType("java/lang/Throwable"); 193 } else { 194 catchType = Type.getObjectType(tryCatchBlock.type); 195 } 196 Frame<V> handler = newFrame(oldFrame); 197 handler.clearStack(); 198 handler.push(interpreter.newExceptionValue(tryCatchBlock, handler, catchType)); 199 checkFrame(insnList.indexOf(tryCatchBlock.handler), handler, /* requireFrame = */ true); 200 } 201 } 202 203 if (!hasNextJvmInsnOrFrame(insnIndex)) { 204 break; 205 } 206 } catch (AnalyzerException e) { 207 throw new AnalyzerException( 208 e.node, "Error at instruction " + insnIndex + ": " + e.getMessage(), e); 209 } catch (RuntimeException e) { 210 // DontCheck(IllegalCatch): can't be fixed, for backward compatibility. 211 throw new AnalyzerException( 212 insnNode, "Error at instruction " + insnIndex + ": " + e.getMessage(), e); 213 } 214 } 215 } 216 217 /** 218 * Expands the {@link FrameNode} "instructions" of the given method into {@link Frame} objects and 219 * stores them at the corresponding indices of the {@link #frames} array. The expanded frames are 220 * also associated with the label and line number nodes immediately preceding each frame node. 221 * 222 * @param owner the internal name of the class to which 'method' belongs. 223 * @param method the method whose frames must be expanded. 224 * @param initialFrame the implicit initial frame of 'method'. 225 * @throws AnalyzerException if the stack map frames of 'method', i.e. its FrameNode 226 * "instructions", are invalid. 227 */ expandFrames( final String owner, final MethodNode method, final Frame<V> initialFrame)228 private void expandFrames( 229 final String owner, final MethodNode method, final Frame<V> initialFrame) 230 throws AnalyzerException { 231 int lastJvmOrFrameInsnIndex = -1; 232 Frame<V> currentFrame = initialFrame; 233 int currentInsnIndex = 0; 234 for (AbstractInsnNode insnNode : method.instructions) { 235 if (insnNode instanceof FrameNode) { 236 try { 237 currentFrame = expandFrame(owner, currentFrame, (FrameNode) insnNode); 238 } catch (AnalyzerException e) { 239 throw new AnalyzerException( 240 e.node, "Error at instruction " + currentInsnIndex + ": " + e.getMessage(), e); 241 } 242 for (int index = lastJvmOrFrameInsnIndex + 1; index <= currentInsnIndex; ++index) { 243 getFrames()[index] = currentFrame; 244 } 245 } 246 if (isJvmInsnNode(insnNode) || insnNode instanceof FrameNode) { 247 lastJvmOrFrameInsnIndex = currentInsnIndex; 248 } 249 currentInsnIndex += 1; 250 } 251 } 252 253 /** 254 * Returns the expanded representation of the given {@link FrameNode}. 255 * 256 * @param owner the internal name of the class to which 'frameNode' belongs. 257 * @param previousFrame the frame before 'frameNode', in expanded form. 258 * @param frameNode a possibly compressed stack map frame. 259 * @return the expanded version of 'frameNode'. 260 * @throws AnalyzerException if 'frameNode' is invalid. 261 */ expandFrame( final String owner, final Frame<V> previousFrame, final FrameNode frameNode)262 private Frame<V> expandFrame( 263 final String owner, final Frame<V> previousFrame, final FrameNode frameNode) 264 throws AnalyzerException { 265 Frame<V> frame = newFrame(previousFrame); 266 List<Object> locals = frameNode.local == null ? Collections.emptyList() : frameNode.local; 267 int currentLocal = currentLocals; 268 switch (frameNode.type) { 269 case Opcodes.F_NEW: 270 case Opcodes.F_FULL: 271 currentLocal = 0; 272 // fall through 273 case Opcodes.F_APPEND: 274 for (Object type : locals) { 275 V value = newFrameValue(owner, frameNode, type); 276 if (currentLocal + value.getSize() > frame.getLocals()) { 277 throw new AnalyzerException(frameNode, "Cannot append more locals than maxLocals"); 278 } 279 frame.setLocal(currentLocal++, value); 280 if (value.getSize() == 2) { 281 frame.setLocal(currentLocal++, interpreter.newValue(null)); 282 } 283 } 284 break; 285 case Opcodes.F_CHOP: 286 for (Object unusedType : locals) { 287 if (currentLocal <= 0) { 288 throw new AnalyzerException(frameNode, "Cannot chop more locals than defined"); 289 } 290 if (currentLocal > 1 && frame.getLocal(currentLocal - 2).getSize() == 2) { 291 currentLocal -= 2; 292 } else { 293 currentLocal -= 1; 294 } 295 } 296 break; 297 case Opcodes.F_SAME: 298 case Opcodes.F_SAME1: 299 break; 300 default: 301 throw new AnalyzerException(frameNode, "Illegal frame type " + frameNode.type); 302 } 303 currentLocals = currentLocal; 304 while (currentLocal < frame.getLocals()) { 305 frame.setLocal(currentLocal++, interpreter.newValue(null)); 306 } 307 308 List<Object> stack = frameNode.stack == null ? Collections.emptyList() : frameNode.stack; 309 frame.clearStack(); 310 for (Object type : stack) { 311 frame.push(newFrameValue(owner, frameNode, type)); 312 } 313 return frame; 314 } 315 316 /** 317 * Creates a new {@link Value} that represents the given stack map frame type. 318 * 319 * @param owner the internal name of the class to which 'frameNode' belongs. 320 * @param frameNode the stack map frame to which 'type' belongs. 321 * @param type an Integer, String or LabelNode object representing a primitive, reference or 322 * uninitialized a stack map frame type, respectively. See {@link FrameNode}. 323 * @return a value that represents the given type. 324 * @throws AnalyzerException if 'type' is an invalid stack map frame type. 325 */ newFrameValue(final String owner, final FrameNode frameNode, final Object type)326 private V newFrameValue(final String owner, final FrameNode frameNode, final Object type) 327 throws AnalyzerException { 328 if (type == Opcodes.TOP) { 329 return interpreter.newValue(null); 330 } else if (type == Opcodes.INTEGER) { 331 return interpreter.newValue(Type.INT_TYPE); 332 } else if (type == Opcodes.FLOAT) { 333 return interpreter.newValue(Type.FLOAT_TYPE); 334 } else if (type == Opcodes.LONG) { 335 return interpreter.newValue(Type.LONG_TYPE); 336 } else if (type == Opcodes.DOUBLE) { 337 return interpreter.newValue(Type.DOUBLE_TYPE); 338 } else if (type == Opcodes.NULL) { 339 return interpreter.newOperation(new InsnNode(Opcodes.ACONST_NULL)); 340 } else if (type == Opcodes.UNINITIALIZED_THIS) { 341 return interpreter.newValue(Type.getObjectType(owner)); 342 } else if (type instanceof String) { 343 return interpreter.newValue(Type.getObjectType((String) type)); 344 } else if (type instanceof LabelNode) { 345 AbstractInsnNode referencedNode = (LabelNode) type; 346 while (referencedNode != null && !isJvmInsnNode(referencedNode)) { 347 referencedNode = referencedNode.getNext(); 348 } 349 if (referencedNode == null || referencedNode.getOpcode() != Opcodes.NEW) { 350 throw new AnalyzerException(frameNode, "LabelNode does not designate a NEW instruction"); 351 } 352 return interpreter.newValue(Type.getObjectType(((TypeInsnNode) referencedNode).desc)); 353 } 354 throw new AnalyzerException(frameNode, "Illegal stack map frame value " + type); 355 } 356 357 /** 358 * Checks that the given frame is compatible with the frame at the given instruction index, if 359 * any. If there is no frame at this instruction index and none is required, the frame at 360 * 'insnIndex' is set to the given frame. Otherwise, if the merge of the two frames is not equal 361 * to the current frame at 'insnIndex', an exception is thrown. 362 * 363 * @param insnIndex an instruction index. 364 * @param frame a frame. This frame is left unchanged by this method. 365 * @param requireFrame whether a frame must already exist or not in {@link #frames} at 366 * 'insnIndex'. 367 * @throws AnalyzerException if the frames have incompatible sizes or if the frame at 'insnIndex' 368 * is missing (if required) or not compatible with 'frame'. 369 */ checkFrame(final int insnIndex, final Frame<V> frame, final boolean requireFrame)370 private void checkFrame(final int insnIndex, final Frame<V> frame, final boolean requireFrame) 371 throws AnalyzerException { 372 Frame<V> oldFrame = getFrames()[insnIndex]; 373 if (oldFrame == null) { 374 if (requireFrame) { 375 throw new AnalyzerException(null, "Expected stack map frame at instruction " + insnIndex); 376 } 377 getFrames()[insnIndex] = newFrame(frame); 378 } else { 379 String error = checkMerge(frame, oldFrame); 380 if (error != null) { 381 throw new AnalyzerException( 382 null, 383 "Stack map frame incompatible with frame at instruction " 384 + insnIndex 385 + " (" 386 + error 387 + ")"); 388 } 389 } 390 } 391 392 /** 393 * Checks that merging the two given frames would not produce any change, i.e. that the types in 394 * the source frame are sub types of the corresponding types in the destination frame. 395 * 396 * @param srcFrame a source frame. This frame is left unchanged by this method. 397 * @param dstFrame a destination frame. This frame is left unchanged by this method. 398 * @return an error message if the frames have incompatible sizes, or if a type in the source 399 * frame is not a sub type of the corresponding type in the destination frame. Returns 400 * {@literal null} otherwise. 401 */ checkMerge(final Frame<V> srcFrame, final Frame<V> dstFrame)402 private String checkMerge(final Frame<V> srcFrame, final Frame<V> dstFrame) { 403 int numLocals = srcFrame.getLocals(); 404 if (numLocals != dstFrame.getLocals()) { 405 throw new AssertionError(); 406 } 407 for (int i = 0; i < numLocals; ++i) { 408 V v = interpreter.merge(srcFrame.getLocal(i), dstFrame.getLocal(i)); 409 if (!v.equals(dstFrame.getLocal(i))) { 410 return "incompatible types at local " 411 + i 412 + ": " 413 + srcFrame.getLocal(i) 414 + " and " 415 + dstFrame.getLocal(i); 416 } 417 } 418 int numStack = srcFrame.getStackSize(); 419 if (numStack != dstFrame.getStackSize()) { 420 return "incompatible stack heights"; 421 } 422 for (int i = 0; i < numStack; ++i) { 423 V v = interpreter.merge(srcFrame.getStack(i), dstFrame.getStack(i)); 424 if (!v.equals(dstFrame.getStack(i))) { 425 return "incompatible types at stack item " 426 + i 427 + ": " 428 + srcFrame.getStack(i) 429 + " and " 430 + dstFrame.getStack(i); 431 } 432 } 433 return null; 434 } 435 436 /** 437 * Ends the control flow graph at the given instruction. This method checks that there is an 438 * existing frame for the next instruction, if any. 439 * 440 * @param insnIndex an instruction index. 441 * @throws AnalyzerException if 'insnIndex' is not the last instruction and there is no frame at 442 * 'insnIndex' + 1 in {@link #getFrames}. 443 */ endControlFlow(final int insnIndex)444 private void endControlFlow(final int insnIndex) throws AnalyzerException { 445 if (hasNextJvmInsnOrFrame(insnIndex) && getFrames()[insnIndex + 1] == null) { 446 throw new AnalyzerException( 447 null, "Expected stack map frame at instruction " + (insnIndex + 1)); 448 } 449 } 450 451 /** 452 * Returns true if the given instruction is followed by a JVM instruction or a by stack map frame. 453 * 454 * @param insnIndex an instruction index. 455 * @return true if 'insnIndex' is followed by a JVM instruction or a by stack map frame. 456 */ hasNextJvmInsnOrFrame(final int insnIndex)457 private boolean hasNextJvmInsnOrFrame(final int insnIndex) { 458 AbstractInsnNode insn = insnList.get(insnIndex).getNext(); 459 while (insn != null) { 460 if (isJvmInsnNode(insn) || insn instanceof FrameNode) { 461 return true; 462 } 463 insn = insn.getNext(); 464 } 465 return false; 466 } 467 468 /** 469 * Returns true if the given instruction node corresponds to a real JVM instruction. 470 * 471 * @param insnNode an instruction node. 472 * @return true except for label, line number and stack map frame nodes. 473 */ isJvmInsnNode(final AbstractInsnNode insnNode)474 private static boolean isJvmInsnNode(final AbstractInsnNode insnNode) { 475 return insnNode.getOpcode() >= 0; 476 } 477 } 478