001/* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * https://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 */ 019package org.apache.bcel.verifier.structurals; 020 021import java.io.PrintWriter; 022import java.io.StringWriter; 023import java.util.ArrayList; 024import java.util.List; 025import java.util.Random; 026import java.util.Vector; 027 028import org.apache.bcel.Const; 029import org.apache.bcel.Repository; 030import org.apache.bcel.classfile.JavaClass; 031import org.apache.bcel.classfile.Method; 032import org.apache.bcel.generic.ConstantPoolGen; 033import org.apache.bcel.generic.InstructionHandle; 034import org.apache.bcel.generic.JsrInstruction; 035import org.apache.bcel.generic.MethodGen; 036import org.apache.bcel.generic.ObjectType; 037import org.apache.bcel.generic.RET; 038import org.apache.bcel.generic.ReferenceType; 039import org.apache.bcel.generic.ReturnInstruction; 040import org.apache.bcel.generic.ReturnaddressType; 041import org.apache.bcel.generic.Type; 042import org.apache.bcel.verifier.PassVerifier; 043import org.apache.bcel.verifier.VerificationResult; 044import org.apache.bcel.verifier.Verifier; 045import org.apache.bcel.verifier.exc.AssertionViolatedException; 046import org.apache.bcel.verifier.exc.StructuralCodeConstraintException; 047import org.apache.bcel.verifier.exc.VerifierConstraintViolatedException; 048 049/** 050 * This PassVerifier verifies a method of class file according to pass 3, so-called structural verification as described 051 * in The Java Virtual Machine Specification, 2nd edition. More detailed information is to be found at the do_verify() 052 * method's documentation. 053 * 054 * @see #do_verify() 055 */ 056 057public final class Pass3bVerifier extends PassVerifier { 058 /* 059 * TODO: Throughout pass 3b, upper halves of LONG and DOUBLE are represented by Type.UNKNOWN. This should be changed in 060 * favor of LONG_Upper and DOUBLE_Upper as in pass 2. 061 */ 062 063 /** 064 * An InstructionContextQueue is a utility class that holds (InstructionContext, ArrayList) pairs in a Queue data 065 * structure. This is used to hold information about InstructionContext objects externally --- i.e. that information is 066 * not saved inside the InstructionContext object itself. This is useful to save the execution path of the symbolic 067 * execution of the Pass3bVerifier - this is not information that belongs into the InstructionContext object itself. 068 * Only at "execute()"ing time, an InstructionContext object will get the current information we have about its symbolic 069 * execution predecessors. 070 */ 071 private static final class InstructionContextQueue { 072 // The following two fields together represent the queue. 073 /** The first elements from pairs in the queue. */ 074 private final List<InstructionContext> ics = new Vector<>(); 075 /** The second elements from pairs in the queue. */ 076 private final List<ArrayList<InstructionContext>> ecs = new Vector<>(); 077 078 /** 079 * Adds an (InstructionContext, ExecutionChain) pair to this queue. 080 * 081 * @param ic the InstructionContext 082 * @param executionChain the ExecutionChain 083 */ 084 public void add(final InstructionContext ic, final ArrayList<InstructionContext> executionChain) { 085 ics.add(ic); 086 ecs.add(executionChain); 087 } 088 089 /** 090 * Gets a specific ExecutionChain from the queue. 091 * 092 * @param i the index of the item to be fetched 093 * @return the indicated ExecutionChain 094 */ 095 public ArrayList<InstructionContext> getEC(final int i) { 096 return ecs.get(i); 097 } 098 099 /** 100 * Gets a specific InstructionContext from the queue. 101 * 102 * @param i the index of the item to be fetched 103 * @return the indicated InstructionContext 104 */ 105 public InstructionContext getIC(final int i) { 106 return ics.get(i); 107 } 108 109 /** 110 * Tests if InstructionContext queue is empty. 111 * 112 * @return true if the InstructionContext queue is empty. 113 */ 114 public boolean isEmpty() { 115 return ics.isEmpty(); 116 } 117 118 /** 119 * Removes a specific (InstructionContext, ExecutionChain) pair from their respective queues. 120 * 121 * @param i the index of the items to be removed 122 */ 123 public void remove(final int i) { 124 ics.remove(i); 125 ecs.remove(i); 126 } 127 128 /** 129 * Gets the size of the InstructionContext queue. 130 * 131 * @return the size of the InstructionQueue 132 */ 133 public int size() { 134 return ics.size(); 135 } 136 } // end Inner Class InstructionContextQueue 137 138 /** In DEBUG mode, the verification algorithm is not randomized. */ 139 private static final boolean DEBUG = true; 140 141 /** The Verifier that created this. */ 142 private final Verifier myOwner; 143 144 /** The method number to verify. */ 145 private final int methodNo; 146 147 /** 148 * This class should only be instantiated by a Verifier. 149 * 150 * @see org.apache.bcel.verifier.Verifier 151 */ 152 public Pass3bVerifier(final Verifier myOwner, final int methodNo) { 153 this.myOwner = myOwner; 154 this.methodNo = methodNo; 155 } 156 157 /** 158 * Whenever the outgoing frame situation of an InstructionContext changes, all its successors are put [back] into the 159 * queue [as if they were unvisited]. The proof of termination is about the existence of a fix point of frame merging. 160 */ 161 private void circulationPump(final MethodGen m, final ControlFlowGraph cfg, final InstructionContext start, final Frame vanillaFrame, 162 final InstConstraintVisitor icv, final ExecutionVisitor ev) { 163 final Random random = new Random(); 164 final InstructionContextQueue icq = new InstructionContextQueue(); 165 166 start.execute(vanillaFrame, new ArrayList<>(), icv, ev); 167 // new ArrayList() <=> no Instruction was executed before 168 // => Top-Level routine (no jsr call before) 169 icq.add(start, new ArrayList<>()); 170 171 // LOOP! 172 while (!icq.isEmpty()) { 173 final InstructionContext u; 174 final ArrayList<InstructionContext> ec; 175 if (!DEBUG) { 176 final int r = random.nextInt(icq.size()); 177 u = icq.getIC(r); 178 ec = icq.getEC(r); 179 icq.remove(r); 180 } else { 181 u = icq.getIC(0); 182 ec = icq.getEC(0); 183 icq.remove(0); 184 } 185 186 @SuppressWarnings("unchecked") // ec is of type ArrayList<InstructionContext> 187 final ArrayList<InstructionContext> oldchain = (ArrayList<InstructionContext>) ec.clone(); 188 @SuppressWarnings("unchecked") // ec is of type ArrayList<InstructionContext> 189 final ArrayList<InstructionContext> newchain = (ArrayList<InstructionContext>) ec.clone(); 190 newchain.add(u); 191 192 if (u.getInstruction().getInstruction() instanceof RET) { 193//System.err.println(u); 194 // We can only follow _one_ successor, the one after the 195 // JSR that was recently executed. 196 final RET ret = (RET) u.getInstruction().getInstruction(); 197 final ReturnaddressType t = (ReturnaddressType) u.getOutFrame(oldchain).getLocals().get(ret.getIndex()); 198 final InstructionContext theSuccessor = cfg.contextOf(t.getTarget()); 199 200 // Sanity check 201 InstructionContext lastJSR = null; 202 int skipJsr = 0; 203 for (int ss = oldchain.size() - 1; ss >= 0; ss--) { 204 if (skipJsr < 0) { 205 throw new AssertionViolatedException("More RET than JSR in execution chain?!"); 206 } 207//System.err.println("+"+oldchain.get(ss)); 208 if (oldchain.get(ss).getInstruction().getInstruction() instanceof JsrInstruction) { 209 if (skipJsr == 0) { 210 lastJSR = oldchain.get(ss); 211 break; 212 } 213 skipJsr--; 214 } 215 if (oldchain.get(ss).getInstruction().getInstruction() instanceof RET) { 216 skipJsr++; 217 } 218 } 219 if (lastJSR == null) { 220 throw new AssertionViolatedException("RET without a JSR before in ExecutionChain?! EC: '" + oldchain + "'."); 221 } 222 final JsrInstruction jsr = (JsrInstruction) lastJSR.getInstruction().getInstruction(); 223 if (theSuccessor != cfg.contextOf(jsr.physicalSuccessor())) { 224 throw new AssertionViolatedException("RET '" + u.getInstruction() + "' info inconsistent: jump back to '" + theSuccessor + "' or '" 225 + cfg.contextOf(jsr.physicalSuccessor()) + "'?"); 226 } 227 228 if (theSuccessor.execute(u.getOutFrame(oldchain), newchain, icv, ev)) { 229 @SuppressWarnings("unchecked") // newchain is already of type ArrayList<InstructionContext> 230 final ArrayList<InstructionContext> newchainClone = (ArrayList<InstructionContext>) newchain.clone(); 231 icq.add(theSuccessor, newchainClone); 232 } 233 } else { // "not a ret" 234 235 // Normal successors. Add them to the queue of successors. 236 final InstructionContext[] succs = u.getSuccessors(); 237 for (final InstructionContext v : succs) { 238 if (v.execute(u.getOutFrame(oldchain), newchain, icv, ev)) { 239 @SuppressWarnings("unchecked") // newchain is already of type ArrayList<InstructionContext> 240 final ArrayList<InstructionContext> newchainClone = (ArrayList<InstructionContext>) newchain.clone(); 241 icq.add(v, newchainClone); 242 } 243 } 244 } // end "not a ret" 245 246 // Exception Handlers. Add them to the queue of successors. 247 // [subroutines are never protected; mandated by JustIce] 248 final ExceptionHandler[] excHds = u.getExceptionHandlers(); 249 for (final ExceptionHandler excHd : excHds) { 250 final InstructionContext v = cfg.contextOf(excHd.getHandlerStart()); 251 // TODO: the "oldchain" and "newchain" is used to determine the subroutine 252 // we're in (by searching for the last JSR) by the InstructionContext 253 // implementation. Therefore, we should not use this chain mechanism 254 // when dealing with exception handlers. 255 // Example: a JSR with an exception handler as its successor does not 256 // mean we're in a subroutine if we go to the exception handler. 257 // We should address this problem later; by now we simply "cut" the chain 258 // by using an empty chain for the exception handlers. 259 // if (v.execute(new Frame(u.getOutFrame(oldchain).getLocals(), 260 // new OperandStack (u.getOutFrame().getStack().maxStack(), 261 // (exc_hds[s].getExceptionType() == null ? Type.THROWABLE : exc_hds[s].getExceptionType())) ), newchain), icv, ev) { 262 // icq.add(v, (ArrayList) newchain.clone()); 263 if (v.execute(new Frame(u.getOutFrame(oldchain).getLocals(), new OperandStack(u.getOutFrame(oldchain).getStack().maxStack(), 264 excHd.getExceptionType() == null ? Type.THROWABLE : excHd.getExceptionType())), new ArrayList<>(), icv, ev)) { 265 icq.add(v, new ArrayList<>()); 266 } 267 } 268 269 } // while (!icq.isEmpty()) END 270 271 InstructionHandle ih = start.getInstruction(); 272 do { 273 if (ih.getInstruction() instanceof ReturnInstruction && !cfg.isDead(ih)) { 274 final InstructionContext ic = cfg.contextOf(ih); 275 // TODO: This is buggy, we check only the top-level return instructions this way. 276 // Maybe some maniac returns from a method when in a subroutine? 277 final Frame f = ic.getOutFrame(new ArrayList<>()); 278 final LocalVariables lvs = f.getLocals(); 279 for (int i = 0; i < lvs.maxLocals(); i++) { 280 if (lvs.get(i) instanceof UninitializedObjectType) { 281 addMessage("Warning: ReturnInstruction '" + ic + "' may leave method with an uninitialized object in the local variables array '" 282 + lvs + "'."); 283 } 284 } 285 final OperandStack os = f.getStack(); 286 for (int i = 0; i < os.size(); i++) { 287 if (os.peek(i) instanceof UninitializedObjectType) { 288 addMessage( 289 "Warning: ReturnInstruction '" + ic + "' may leave method with an uninitialized object on the operand stack '" + os + "'."); 290 } 291 } 292 // see JVM $4.8.2 293 Type returnedType = null; 294 final OperandStack inStack = ic.getInFrame().getStack(); 295 if (inStack.size() >= 1) { 296 returnedType = inStack.peek(); 297 } else { 298 returnedType = Type.VOID; 299 } 300 301 if (returnedType != null) { 302 if (returnedType instanceof ReferenceType) { 303 try { 304 if (!((ReferenceType) returnedType).isCastableTo(m.getReturnType())) { 305 invalidReturnTypeError(returnedType, m); 306 } 307 } catch (final ClassNotFoundException e) { 308 // Don't know what to do now, so raise RuntimeException 309 throw new IllegalArgumentException(e); 310 } 311 } else if (!returnedType.equals(m.getReturnType().normalizeForStackOrLocal())) { 312 invalidReturnTypeError(returnedType, m); 313 } 314 } 315 } 316 } while ((ih = ih.getNext()) != null); 317 318 } 319 320 /** 321 * Pass 3b implements the data flow analysis as described in the Java Virtual Machine Specification, Second Edition. 322 * Later versions will use LocalVariablesInfo objects to verify if the verifier-inferred types and the class file's 323 * debug information (LocalVariables attributes) match [TODO]. 324 * 325 * @see org.apache.bcel.verifier.statics.LocalVariablesInfo 326 * @see org.apache.bcel.verifier.statics.Pass2Verifier#getLocalVariablesInfo(int) 327 */ 328 @Override 329 public VerificationResult do_verify() { 330 if (!myOwner.doPass3a(methodNo).equals(VerificationResult.VR_OK)) { 331 return VerificationResult.VR_NOTYET; 332 } 333 334 // Pass 3a ran before, so it's safe to assume the JavaClass object is 335 // in the BCEL repository. 336 final JavaClass jc; 337 try { 338 jc = Repository.lookupClass(myOwner.getClassName()); 339 } catch (final ClassNotFoundException e) { 340 // FIXME: maybe not the best way to handle this 341 throw new AssertionViolatedException("Missing class: " + e, e); 342 } 343 344 final ConstantPoolGen constantPoolGen = new ConstantPoolGen(jc.getConstantPool()); 345 // Init Visitors 346 final InstConstraintVisitor icv = new InstConstraintVisitor(); 347 icv.setConstantPoolGen(constantPoolGen); 348 349 final ExecutionVisitor ev = new ExecutionVisitor(); 350 ev.setConstantPoolGen(constantPoolGen); 351 352 final Method[] methods = jc.getMethods(); // Method no "methodNo" exists, we ran Pass3a before on it! 353 354 try { 355 356 final MethodGen mg = new MethodGen(methods[methodNo], myOwner.getClassName(), constantPoolGen); 357 358 icv.setMethodGen(mg); 359 360 ////////////// DFA BEGINS HERE //////////////// 361 if (!(mg.isAbstract() || mg.isNative())) { // IF mg HAS CODE (See pass 2) 362 363 final ControlFlowGraph cfg = new ControlFlowGraph(mg); 364 365 // Build the initial frame situation for this method. 366 final Frame f = new Frame(mg.getMaxLocals(), mg.getMaxStack()); 367 if (!mg.isStatic()) { 368 if (mg.getName().equals(Const.CONSTRUCTOR_NAME)) { 369 Frame.setThis(new UninitializedObjectType(ObjectType.getInstance(jc.getClassName()))); 370 f.getLocals().set(0, Frame.getThis()); 371 } else { 372 Frame.setThis(null); 373 f.getLocals().set(0, ObjectType.getInstance(jc.getClassName())); 374 } 375 } 376 final Type[] argtypes = mg.getArgumentTypes(); 377 int twoslotoffset = 0; 378 for (int j = 0; j < argtypes.length; j++) { 379 if (argtypes[j] == Type.SHORT || argtypes[j] == Type.BYTE || argtypes[j] == Type.CHAR || argtypes[j] == Type.BOOLEAN) { 380 argtypes[j] = Type.INT; 381 } 382 f.getLocals().set(twoslotoffset + j + (mg.isStatic() ? 0 : 1), argtypes[j]); 383 if (argtypes[j].getSize() == 2) { 384 twoslotoffset++; 385 f.getLocals().set(twoslotoffset + j + (mg.isStatic() ? 0 : 1), Type.UNKNOWN); 386 } 387 } 388 circulationPump(mg, cfg, cfg.contextOf(mg.getInstructionList().getStart()), f, icv, ev); 389 } 390 } catch (final VerifierConstraintViolatedException ce) { 391 ce.extendMessage("Constraint violated in method '" + methods[methodNo] + "':\n", ""); 392 return new VerificationResult(VerificationResult.VERIFIED_REJECTED, ce.getMessage()); 393 } catch (final RuntimeException re) { 394 // These are internal errors 395 396 final StringWriter sw = new StringWriter(); 397 final PrintWriter pw = new PrintWriter(sw); 398 re.printStackTrace(pw); 399 400 throw new AssertionViolatedException("Some RuntimeException occurred while verify()ing class '" + jc.getClassName() + "', method '" 401 + methods[methodNo] + "'. Original RuntimeException's stack trace:\n---\n" + sw + "---\n", re); 402 } 403 return VerificationResult.VR_OK; 404 } 405 406 /** Returns the method number as supplied when instantiating. */ 407 public int getMethodNo() { 408 return methodNo; 409 } 410 411 /** 412 * Throws an exception indicating the returned type is not compatible with the return type of the given method. 413 * 414 * @param returnedType the type of the returned expression 415 * @param m the method we are processing 416 * @throws StructuralCodeConstraintException always 417 * @since 6.0 418 */ 419 public void invalidReturnTypeError(final Type returnedType, final MethodGen m) { 420 throw new StructuralCodeConstraintException("Returned type " + returnedType + " does not match Method's return type " + m.getReturnType()); 421 } 422}