1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 * 17 */ 18 package org.apache.bcel.verifier.structurals; 19 20 21 import java.io.PrintWriter; 22 import java.io.StringWriter; 23 import java.util.ArrayList; 24 import java.util.List; 25 import java.util.Random; 26 import java.util.Vector; 27 28 import org.apache.bcel.Const; 29 import org.apache.bcel.Repository; 30 import org.apache.bcel.classfile.JavaClass; 31 import org.apache.bcel.classfile.Method; 32 import org.apache.bcel.generic.ConstantPoolGen; 33 import org.apache.bcel.generic.InstructionHandle; 34 import org.apache.bcel.generic.JsrInstruction; 35 import org.apache.bcel.generic.MethodGen; 36 import org.apache.bcel.generic.ObjectType; 37 import org.apache.bcel.generic.RET; 38 import org.apache.bcel.generic.ReferenceType; 39 import org.apache.bcel.generic.ReturnInstruction; 40 import org.apache.bcel.generic.ReturnaddressType; 41 import org.apache.bcel.generic.Type; 42 import org.apache.bcel.verifier.PassVerifier; 43 import org.apache.bcel.verifier.VerificationResult; 44 import org.apache.bcel.verifier.Verifier; 45 import org.apache.bcel.verifier.exc.AssertionViolatedException; 46 import org.apache.bcel.verifier.exc.StructuralCodeConstraintException; 47 import org.apache.bcel.verifier.exc.VerifierConstraintViolatedException; 48 49 /** 50 * This PassVerifier verifies a method of class file according to pass 3, 51 * so-called structural verification as described in The Java Virtual Machine 52 * Specification, 2nd edition. 53 * More detailed information is to be found at the do_verify() method's 54 * documentation. 55 * 56 * @version $Id$ 57 * @see #do_verify() 58 */ 59 60 public final class Pass3bVerifier extends PassVerifier{ 61 /* TODO: Throughout pass 3b, upper halves of LONG and DOUBLE 62 are represented by Type.UNKNOWN. This should be changed 63 in favour of LONG_Upper and DOUBLE_Upper as in pass 2. */ 64 65 /** 66 * An InstructionContextQueue is a utility class that holds 67 * (InstructionContext, ArrayList) pairs in a Queue data structure. 68 * This is used to hold information about InstructionContext objects 69 * externally --- i.e. that information is not saved inside the 70 * InstructionContext object itself. This is useful to save the 71 * execution path of the symbolic execution of the 72 * Pass3bVerifier - this is not information 73 * that belongs into the InstructionContext object itself. 74 * Only at "execute()"ing 75 * time, an InstructionContext object will get the current information 76 * we have about its symbolic execution predecessors. 77 */ 78 private static final class InstructionContextQueue{ 79 private final List<InstructionContext> ics = new Vector<>(); 80 private final List<ArrayList<InstructionContext>> ecs = new Vector<>(); add(final InstructionContext ic, final ArrayList<InstructionContext> executionChain)81 public void add(final InstructionContext ic, final ArrayList<InstructionContext> executionChain) { 82 ics.add(ic); 83 ecs.add(executionChain); 84 } isEmpty()85 public boolean isEmpty() { 86 return ics.isEmpty(); 87 } remove(final int i)88 public void remove(final int i) { 89 ics.remove(i); 90 ecs.remove(i); 91 } getIC(final int i)92 public InstructionContext getIC(final int i) { 93 return ics.get(i); 94 } getEC(final int i)95 public ArrayList<InstructionContext> getEC(final int i) { 96 return ecs.get(i); 97 } size()98 public int size() { 99 return ics.size(); 100 } 101 } // end Inner Class InstructionContextQueue 102 103 /** In DEBUG mode, the verification algorithm is not randomized. */ 104 private static final boolean DEBUG = true; 105 106 /** The Verifier that created this. */ 107 private final Verifier myOwner; 108 109 /** The method number to verify. */ 110 private final int method_no; 111 112 /** 113 * This class should only be instantiated by a Verifier. 114 * 115 * @see org.apache.bcel.verifier.Verifier 116 */ Pass3bVerifier(final Verifier owner, final int method_no)117 public Pass3bVerifier(final Verifier owner, final int method_no) { 118 myOwner = owner; 119 this.method_no = method_no; 120 } 121 122 /** 123 * Whenever the outgoing frame 124 * situation of an InstructionContext changes, all its successors are 125 * put [back] into the queue [as if they were unvisited]. 126 * The proof of termination is about the existence of a 127 * fix point of frame merging. 128 */ circulationPump(final MethodGen m,final ControlFlowGraph cfg, final InstructionContext start, final Frame vanillaFrame, final InstConstraintVisitor icv, final ExecutionVisitor ev)129 private void circulationPump(final MethodGen m,final ControlFlowGraph cfg, final InstructionContext start, 130 final Frame vanillaFrame, final InstConstraintVisitor icv, final ExecutionVisitor ev) { 131 final Random random = new Random(); 132 final InstructionContextQueue icq = new InstructionContextQueue(); 133 134 start.execute(vanillaFrame, new ArrayList<InstructionContext>(), icv, ev); 135 // new ArrayList() <=> no Instruction was executed before 136 // => Top-Level routine (no jsr call before) 137 icq.add(start, new ArrayList<InstructionContext>()); 138 139 // LOOP! 140 while (!icq.isEmpty()) { 141 InstructionContext u; 142 ArrayList<InstructionContext> ec; 143 if (!DEBUG) { 144 final int r = random.nextInt(icq.size()); 145 u = icq.getIC(r); 146 ec = icq.getEC(r); 147 icq.remove(r); 148 } 149 else{ 150 u = icq.getIC(0); 151 ec = icq.getEC(0); 152 icq.remove(0); 153 } 154 155 @SuppressWarnings("unchecked") // ec is of type ArrayList<InstructionContext> 156 final 157 ArrayList<InstructionContext> oldchain = (ArrayList<InstructionContext>) (ec.clone()); 158 @SuppressWarnings("unchecked") // ec is of type ArrayList<InstructionContext> 159 final 160 ArrayList<InstructionContext> newchain = (ArrayList<InstructionContext>) (ec.clone()); 161 newchain.add(u); 162 163 if ((u.getInstruction().getInstruction()) instanceof RET) { 164 //System.err.println(u); 165 // We can only follow _one_ successor, the one after the 166 // JSR that was recently executed. 167 final RET ret = (RET) (u.getInstruction().getInstruction()); 168 final ReturnaddressType t = (ReturnaddressType) u.getOutFrame(oldchain).getLocals().get(ret.getIndex()); 169 final InstructionContext theSuccessor = cfg.contextOf(t.getTarget()); 170 171 // Sanity check 172 InstructionContext lastJSR = null; 173 int skip_jsr = 0; 174 for (int ss=oldchain.size()-1; ss >= 0; ss--) { 175 if (skip_jsr < 0) { 176 throw new AssertionViolatedException("More RET than JSR in execution chain?!"); 177 } 178 //System.err.println("+"+oldchain.get(ss)); 179 if ((oldchain.get(ss)).getInstruction().getInstruction() instanceof JsrInstruction) { 180 if (skip_jsr == 0) { 181 lastJSR = oldchain.get(ss); 182 break; 183 } 184 skip_jsr--; 185 } 186 if ((oldchain.get(ss)).getInstruction().getInstruction() instanceof RET) { 187 skip_jsr++; 188 } 189 } 190 if (lastJSR == null) { 191 throw new AssertionViolatedException("RET without a JSR before in ExecutionChain?! EC: '"+oldchain+"'."); 192 } 193 final JsrInstruction jsr = (JsrInstruction) (lastJSR.getInstruction().getInstruction()); 194 if ( theSuccessor != (cfg.contextOf(jsr.physicalSuccessor())) ) { 195 throw new AssertionViolatedException("RET '"+u.getInstruction()+"' info inconsistent: jump back to '"+ 196 theSuccessor+"' or '"+cfg.contextOf(jsr.physicalSuccessor())+"'?"); 197 } 198 199 if (theSuccessor.execute(u.getOutFrame(oldchain), newchain, icv, ev)) { 200 @SuppressWarnings("unchecked") // newchain is already of type ArrayList<InstructionContext> 201 final 202 ArrayList<InstructionContext> newchainClone = (ArrayList<InstructionContext>) newchain.clone(); 203 icq.add(theSuccessor, newchainClone); 204 } 205 } 206 else{// "not a ret" 207 208 // Normal successors. Add them to the queue of successors. 209 final InstructionContext[] succs = u.getSuccessors(); 210 for (final InstructionContext v : succs) { 211 if (v.execute(u.getOutFrame(oldchain), newchain, icv, ev)) { 212 @SuppressWarnings("unchecked") // newchain is already of type ArrayList<InstructionContext> 213 final 214 ArrayList<InstructionContext> newchainClone = (ArrayList<InstructionContext>) newchain.clone(); 215 icq.add(v, newchainClone); 216 } 217 } 218 }// end "not a ret" 219 220 // Exception Handlers. Add them to the queue of successors. 221 // [subroutines are never protected; mandated by JustIce] 222 final ExceptionHandler[] exc_hds = u.getExceptionHandlers(); 223 for (final ExceptionHandler exc_hd : exc_hds) { 224 final InstructionContext v = cfg.contextOf(exc_hd.getHandlerStart()); 225 // TODO: the "oldchain" and "newchain" is used to determine the subroutine 226 // we're in (by searching for the last JSR) by the InstructionContext 227 // implementation. Therefore, we should not use this chain mechanism 228 // when dealing with exception handlers. 229 // Example: a JSR with an exception handler as its successor does not 230 // mean we're in a subroutine if we go to the exception handler. 231 // We should address this problem later; by now we simply "cut" the chain 232 // by using an empty chain for the exception handlers. 233 //if (v.execute(new Frame(u.getOutFrame(oldchain).getLocals(), 234 // new OperandStack (u.getOutFrame().getStack().maxStack(), 235 // (exc_hds[s].getExceptionType()==null? Type.THROWABLE : exc_hds[s].getExceptionType())) ), newchain), icv, ev) { 236 //icq.add(v, (ArrayList) newchain.clone()); 237 if (v.execute(new Frame(u.getOutFrame(oldchain).getLocals(), 238 new OperandStack (u.getOutFrame(oldchain).getStack().maxStack(), 239 exc_hd.getExceptionType()==null? Type.THROWABLE : exc_hd.getExceptionType())), 240 new ArrayList<InstructionContext>(), icv, ev)) { 241 icq.add(v, new ArrayList<InstructionContext>()); 242 } 243 } 244 245 }// while (!icq.isEmpty()) END 246 247 InstructionHandle ih = start.getInstruction(); 248 do{ 249 if ((ih.getInstruction() instanceof ReturnInstruction) && (!(cfg.isDead(ih)))) { 250 final InstructionContext ic = cfg.contextOf(ih); 251 // TODO: This is buggy, we check only the top-level return instructions this way. 252 // Maybe some maniac returns from a method when in a subroutine? 253 final Frame f = ic.getOutFrame(new ArrayList<InstructionContext>()); 254 final LocalVariables lvs = f.getLocals(); 255 for (int i=0; i<lvs.maxLocals(); i++) { 256 if (lvs.get(i) instanceof UninitializedObjectType) { 257 this.addMessage("Warning: ReturnInstruction '"+ic+ 258 "' may leave method with an uninitialized object in the local variables array '"+lvs+"'."); 259 } 260 } 261 final OperandStack os = f.getStack(); 262 for (int i=0; i<os.size(); i++) { 263 if (os.peek(i) instanceof UninitializedObjectType) { 264 this.addMessage("Warning: ReturnInstruction '"+ic+ 265 "' may leave method with an uninitialized object on the operand stack '"+os+"'."); 266 } 267 } 268 //see JVM $4.8.2 269 Type returnedType = null; 270 final OperandStack inStack = ic.getInFrame().getStack(); 271 if (inStack.size() >= 1) { 272 returnedType = inStack.peek(); 273 } else { 274 returnedType = Type.VOID; 275 } 276 277 if (returnedType != null) { 278 if (returnedType instanceof ReferenceType) { 279 try { 280 if (!((ReferenceType) returnedType).isCastableTo(m.getReturnType())) { 281 invalidReturnTypeError(returnedType, m); 282 } 283 } catch (final ClassNotFoundException e) { 284 // Don't know what do do now, so raise RuntimeException 285 throw new RuntimeException(e); 286 } 287 } else if (!returnedType.equals(m.getReturnType().normalizeForStackOrLocal())) { 288 invalidReturnTypeError(returnedType, m); 289 } 290 } 291 } 292 } while ((ih = ih.getNext()) != null); 293 294 } 295 296 /** 297 * Throws an exception indicating the returned type is not compatible with the return type of the given method 298 * @throws StructuralCodeConstraintException always 299 * @since 6.0 300 */ invalidReturnTypeError(final Type returnedType, final MethodGen m)301 public void invalidReturnTypeError(final Type returnedType, final MethodGen m) { 302 throw new StructuralCodeConstraintException( 303 "Returned type "+returnedType+" does not match Method's return type "+m.getReturnType()); 304 } 305 306 /** 307 * Pass 3b implements the data flow analysis as described in the Java Virtual 308 * Machine Specification, Second Edition. 309 * Later versions will use LocalVariablesInfo objects to verify if the 310 * verifier-inferred types and the class file's debug information (LocalVariables 311 * attributes) match [TODO]. 312 * 313 * @see org.apache.bcel.verifier.statics.LocalVariablesInfo 314 * @see org.apache.bcel.verifier.statics.Pass2Verifier#getLocalVariablesInfo(int) 315 */ 316 @Override do_verify()317 public VerificationResult do_verify() { 318 if (! myOwner.doPass3a(method_no).equals(VerificationResult.VR_OK)) { 319 return VerificationResult.VR_NOTYET; 320 } 321 322 // Pass 3a ran before, so it's safe to assume the JavaClass object is 323 // in the BCEL repository. 324 JavaClass jc; 325 try { 326 jc = Repository.lookupClass(myOwner.getClassName()); 327 } catch (final ClassNotFoundException e) { 328 // FIXME: maybe not the best way to handle this 329 throw new AssertionViolatedException("Missing class: " + e, e); 330 } 331 332 final ConstantPoolGen constantPoolGen = new ConstantPoolGen(jc.getConstantPool()); 333 // Init Visitors 334 final InstConstraintVisitor icv = new InstConstraintVisitor(); 335 icv.setConstantPoolGen(constantPoolGen); 336 337 final ExecutionVisitor ev = new ExecutionVisitor(); 338 ev.setConstantPoolGen(constantPoolGen); 339 340 final Method[] methods = jc.getMethods(); // Method no "method_no" exists, we ran Pass3a before on it! 341 342 try{ 343 344 final MethodGen mg = new MethodGen(methods[method_no], myOwner.getClassName(), constantPoolGen); 345 346 icv.setMethodGen(mg); 347 348 ////////////// DFA BEGINS HERE //////////////// 349 if (! (mg.isAbstract() || mg.isNative()) ) { // IF mg HAS CODE (See pass 2) 350 351 final ControlFlowGraph cfg = new ControlFlowGraph(mg); 352 353 // Build the initial frame situation for this method. 354 final Frame f = new Frame(mg.getMaxLocals(),mg.getMaxStack()); 355 if ( !mg.isStatic() ) { 356 if (mg.getName().equals(Const.CONSTRUCTOR_NAME)) { 357 Frame.setThis(new UninitializedObjectType(ObjectType.getInstance(jc.getClassName()))); 358 f.getLocals().set(0, Frame.getThis()); 359 } 360 else{ 361 Frame.setThis(null); 362 f.getLocals().set(0, ObjectType.getInstance(jc.getClassName())); 363 } 364 } 365 final Type[] argtypes = mg.getArgumentTypes(); 366 int twoslotoffset = 0; 367 for (int j=0; j<argtypes.length; j++) { 368 if (argtypes[j] == Type.SHORT || argtypes[j] == Type.BYTE || 369 argtypes[j] == Type.CHAR || argtypes[j] == Type.BOOLEAN) { 370 argtypes[j] = Type.INT; 371 } 372 f.getLocals().set(twoslotoffset + j + (mg.isStatic()?0:1), argtypes[j]); 373 if (argtypes[j].getSize() == 2) { 374 twoslotoffset++; 375 f.getLocals().set(twoslotoffset + j + (mg.isStatic()?0:1), Type.UNKNOWN); 376 } 377 } 378 circulationPump(mg,cfg, cfg.contextOf(mg.getInstructionList().getStart()), f, icv, ev); 379 } 380 } 381 catch (final VerifierConstraintViolatedException ce) { 382 ce.extendMessage("Constraint violated in method '"+methods[method_no]+"':\n",""); 383 return new VerificationResult(VerificationResult.VERIFIED_REJECTED, ce.getMessage()); 384 } 385 catch (final RuntimeException re) { 386 // These are internal errors 387 388 final StringWriter sw = new StringWriter(); 389 final PrintWriter pw = new PrintWriter(sw); 390 re.printStackTrace(pw); 391 392 throw new AssertionViolatedException("Some RuntimeException occured while verify()ing class '"+jc.getClassName()+ 393 "', method '"+methods[method_no]+"'. Original RuntimeException's stack trace:\n---\n"+sw+"---\n", re); 394 } 395 return VerificationResult.VR_OK; 396 } 397 398 /** Returns the method number as supplied when instantiating. */ getMethodNo()399 public int getMethodNo() { 400 return method_no; 401 } 402 } 403