/** * Sets the leaving RET instruction. Must be invoked after all instructions are added. * Must not be invoked for top-level 'subroutine'. */ void setLeavingRET(){ if (localVariable == UNSET){ throw new AssertionViolatedException("setLeavingRET() called for top-level 'subroutine' or forgot to set local variable first."); } Iterator iter = instructions.iterator(); InstructionHandle ret = null; while(iter.hasNext()){ InstructionHandle actual = (InstructionHandle) iter.next(); if (actual.getInstruction() instanceof RET){ if (ret != null){ throw new StructuralCodeConstraintException("Subroutine with more then one RET detected: '"+ret+"' and '"+actual+"'."); } else{ ret = actual; } } } if (ret == null){ throw new StructuralCodeConstraintException("Subroutine without a RET detected."); } if (((RET) ret.getInstruction()).getIndex() != localVariable){ throw new StructuralCodeConstraintException("Subroutine uses '"+ret+"' which does not match the correct local variable '"+localVariable+"'."); } theRET = ret; }
/** * This (recursive) utility method makes sure that * no subroutine is calling a subroutine * that uses the same local variable for the RET as themselves * (recursively). * This includes that subroutines may not call themselves * recursively, even not through intermediate calls to other * subroutines. * * @throws StructuralCodeConstraintException if the above constraint is not satisfied. */ private void noRecursiveCalls(Subroutine sub, Set set){ Subroutine[] subs = sub.subSubs(); for (int i=0; i<subs.length; i++){ int index = ((RET) (subs[i].getLeavingRET().getInstruction())).getIndex(); if (!set.add(new Integer(index))){ // Don't use toString() here because of possibly infinite recursive subSubs() calls then. SubroutineImpl si = (SubroutineImpl) subs[i]; throw new StructuralCodeConstraintException("Subroutine with local variable '"+si.localVariable+"', JSRs '"+si.theJSRs+"', RET '"+si.theRET+"' is called by a subroutine which uses the same local variable index as itself; maybe even a recursive call? JustIce's clean definition of a subroutine forbids both."); } noRecursiveCalls(subs[i], set); set.remove(new Integer(index)); } }
/** * Returns the InstructionContextImpl with an JSR/JSR_W * that was last in the ExecutionChain, without * a corresponding RET, i.e. * we were called by this one. * Returns null if we were called from the top level. */ private InstructionContextImpl lastExecutionJSR(){ int size = executionPredecessors.size(); int retcount = 0; for (int i=size-1; i>=0; i--){ InstructionContextImpl current = (InstructionContextImpl) (executionPredecessors.get(i)); Instruction currentlast = current.getInstruction().getInstruction(); if (currentlast instanceof RET) { retcount++; } if (currentlast instanceof JsrInstruction){ retcount--; if (retcount == -1) { return current; } } } return null; }
/** * Sets the leaving RET instruction. Must be invoked after all instructions are added. * Must not be invoked for top-level 'subroutine'. */ void setLeavingRET() { if (localVariable == UNSET){ throw new AssertionViolatedException("setLeavingRET() called for top-level 'subroutine' or forgot to set local variable first."); } InstructionHandle ret = null; for (final InstructionHandle actual : instructions) { if (actual.getInstruction() instanceof RET){ if (ret != null){ throw new StructuralCodeConstraintException("Subroutine with more then one RET detected: '"+ret+"' and '"+actual+"'."); } else{ ret = actual; } } } if (ret == null){ throw new StructuralCodeConstraintException("Subroutine without a RET detected."); } if (((RET) ret.getInstruction()).getIndex() != localVariable){ throw new StructuralCodeConstraintException("Subroutine uses '"+ret+"' which does not match the correct local variable '"+localVariable+"'."); } theRET = ret; }
/** * Returns the InstructionContextImpl with an JSR/JSR_W * that was last in the ExecutionChain, without * a corresponding RET, i.e. * we were called by this one. * Returns null if we were called from the top level. */ public InstructionContext lastExecutionJSR(){ int retcount = 0; for( ExecutionPath ptr = this; ptr!=EMPTY; ptr=ptr.prev) { Instruction i = ptr.last.getInstruction().getInstruction(); if (i instanceof RET) retcount++; if (i instanceof JsrInstruction){ retcount--; if (retcount == -1) return ptr.last; } } return null; }
/** Checks if the constraints of operands of the said instruction(s) are satisfied. */ public void visitRET(RET o){ int idx = o.getIndex(); if (idx < 0){ constraintViolated(o, "Index '"+idx+"' must be non-negative."); } else{ int maxminus1 = max_locals()-1; if (idx > maxminus1){ constraintViolated(o, "Index '"+idx+"' must not be greater than max_locals-1 '"+maxminus1+"'."); } } }
public int[] getAccessedLocalsIndices(){ //TODO: Implement caching. Set acc = new HashSet(); if (theRET == null && this != TOPLEVEL){ throw new AssertionViolatedException("This subroutine object must be built up completely before calculating accessed locals."); } Iterator i = instructions.iterator(); while (i.hasNext()){ InstructionHandle ih = (InstructionHandle) i.next(); // RET is not a LocalVariableInstruction in the current version of BCEL. if (ih.getInstruction() instanceof LocalVariableInstruction || ih.getInstruction() instanceof RET){ int idx = ((IndexedInstruction) (ih.getInstruction())).getIndex(); acc.add(new Integer(idx)); // LONG? DOUBLE?. try{ // LocalVariableInstruction instances are typed without the need to look into // the constant pool. if (ih.getInstruction() instanceof LocalVariableInstruction){ int s = ((LocalVariableInstruction) ih.getInstruction()).getType(null).getSize(); if (s==2) { acc.add(new Integer(idx+1)); } } } catch(RuntimeException re){ throw new AssertionViolatedException("Oops. BCEL did not like NULL as a ConstantPoolGen object."); } } } int[] ret = new int[acc.size()]; i = acc.iterator(); int j=-1; while (i.hasNext()){ j++; ret[j] = ((Integer) i.next()).intValue(); } return ret; }
public int[] getAccessedLocalsIndices(){ //TODO: Implement caching. final Set<Integer> acc = new HashSet<Integer>(); if (theRET == null && this != TOPLEVEL){ throw new AssertionViolatedException("This subroutine object must be built up completely before calculating accessed locals."); } for (final InstructionHandle ih : instructions) { // RET is not a LocalVariableInstruction in the current version of BCEL. if (ih.getInstruction() instanceof LocalVariableInstruction || ih.getInstruction() instanceof RET){ int idx = IndexedInstruction.class.cast(ih.getInstruction()).getIndex(); acc.add(idx); // LONG? DOUBLE?. try { // LocalVariableInstruction instances are typed without the need to look into // the constant pool. if (ih.getInstruction() instanceof LocalVariableInstruction) { int s = LocalVariableInstruction.class.cast(ih.getInstruction()).getType(null).getSize(); if (s == 2) acc.add(idx + 1); } } catch(final RuntimeException re) { throw new AssertionViolatedException("Oops. BCEL did not like NULL as a ConstantPoolGen object."); } } } int[] ret = new int[acc.size()]; int j = 0; for (final int v : acc) { ret[j++] = v; } return ret; }
/** * This (recursive) utility method makes sure that * no subroutine is calling a subroutine * that uses the same local variable for the RET as themselves * (recursively). * This includes that subroutines may not call themselves * recursively, even not through intermediate calls to other * subroutines. * * @throws StructuralCodeConstraintException if the above constraint is not satisfied. */ private void noRecursiveCalls(final Subroutine sub, final Set<Integer> set){ for (final Subroutine subSub : sub.subSubs()) { int index = ((RET) (subSub.getLeavingRET().getInstruction())).getIndex(); if (!set.add(index)) { // Don't use toString() here because of possibly infinite recursive subSubs() calls then. final SubroutineImpl si = (SubroutineImpl)subSub; throw new StructuralCodeConstraintException("Subroutine with local variable '" + si.localVariable + "', JSRs '" + si.theJSRs+"', RET '" + si.theRET + "' is called by a subroutine which uses the same local variable index as itself; maybe even a recursive call? JustIce's clean definition of a subroutine forbids both."); } noRecursiveCalls(subSub, set); set.remove(index); } }
/** * These are the checks if constraints are satisfied which are described in the * Java Virtual Machine Specification, Second Edition as Static Constraints on * the instructions of Java Virtual Machine Code (chapter 4.8.1). * * @throws StaticCodeConstraintException if the verification fails. */ private void pass3StaticInstructionChecks(){ // Code array must not be empty: // Enforced in pass 2 (also stated in the static constraints of the Code // array in vmspec2), together with pass 1 (reading code_length bytes and // interpreting them as code[]). So this must not be checked again here. if (! (code.getCode().length < 65536)){// contradicts vmspec2 page 152 ("Limitations"), but is on page 134. throw new StaticCodeInstructionConstraintException("Code array in code attribute '"+code+"' too big: must be smaller than 65536 bytes."); } // First opcode at offset 0: okay, that's clear. Nothing to do. // Only instances of the instructions documented in Section 6.4 may appear in // the code array. // For BCEL's sake, we cannot handle WIDE stuff, but hopefully BCEL does its job right :) // The last byte of the last instruction in the code array must be the byte at index // code_length-1 : See the do_verify() comments. We actually don't iterate through the // byte array, but use an InstructionList so we cannot check for this. But BCEL does // things right, so it's implicitly okay. // TODO: Check how BCEL handles (and will handle) instructions like IMPDEP1, IMPDEP2, // BREAKPOINT... that BCEL knows about but which are illegal anyway. // We currently go the safe way here. InstructionHandle ih = instructionList.getStart(); while (ih != null){ Instruction i = ih.getInstruction(); if (i instanceof IMPDEP1){ throw new StaticCodeInstructionConstraintException("IMPDEP1 must not be in the code, it is an illegal instruction for _internal_ JVM use!"); } if (i instanceof IMPDEP2){ throw new StaticCodeInstructionConstraintException("IMPDEP2 must not be in the code, it is an illegal instruction for _internal_ JVM use!"); } if (i instanceof BREAKPOINT){ throw new StaticCodeInstructionConstraintException("BREAKPOINT must not be in the code, it is an illegal instruction for _internal_ JVM use!"); } ih = ih.getNext(); } // The original verifier seems to do this check here, too. // An unreachable last instruction may also not fall through the // end of the code, which is stupid -- but with the original // verifier's subroutine semantics one cannot predict reachability. Instruction last = instructionList.getEnd().getInstruction(); if (! ((last instanceof ReturnInstruction) || (last instanceof RET) || (last instanceof GotoInstruction) || (last instanceof ATHROW) )) { throw new StaticCodeInstructionConstraintException("Execution must not fall off the bottom of the code array. This constraint is enforced statically as some existing verifiers do - so it may be a false alarm if the last instruction is not reachable."); } }
/** * A utility method that calculates the successors of a given InstructionHandle * <B>in the same subroutine</B>. That means, a RET does not have any successors * as defined here. A JsrInstruction has its physical successor as its successor * (opposed to its target) as defined here. */ private static InstructionHandle[] getSuccessors(InstructionHandle instruction){ final InstructionHandle[] empty = new InstructionHandle[0]; final InstructionHandle[] single = new InstructionHandle[1]; final InstructionHandle[] pair = new InstructionHandle[2]; Instruction inst = instruction.getInstruction(); if (inst instanceof RET){ return empty; } // Terminates method normally. if (inst instanceof ReturnInstruction){ return empty; } // Terminates method abnormally, because JustIce mandates // subroutines not to be protected by exception handlers. if (inst instanceof ATHROW){ return empty; } // See method comment. if (inst instanceof JsrInstruction){ single[0] = instruction.getNext(); return single; } if (inst instanceof GotoInstruction){ single[0] = ((GotoInstruction) inst).getTarget(); return single; } if (inst instanceof BranchInstruction){ if (inst instanceof Select){ // BCEL's getTargets() returns only the non-default targets, // thanks to Eli Tilevich for reporting. InstructionHandle[] matchTargets = ((Select) inst).getTargets(); InstructionHandle[] ret = new InstructionHandle[matchTargets.length+1]; ret[0] = ((Select) inst).getTarget(); System.arraycopy(matchTargets, 0, ret, 1, matchTargets.length); return ret; } else{ pair[0] = instruction.getNext(); pair[1] = ((BranchInstruction) inst).getTarget(); return pair; } } // default case: Fall through. single[0] = instruction.getNext(); return single; }
public void visitRET( RET i ) { _out.println("il.append(new RET(" + i.getIndex() + ")));"); }
/** * A utility method that calculates the successors of a given InstructionHandle * <B>in the same subroutine</B>. That means, a RET does not have any successors * as defined here. A JsrInstruction has its physical successor as its successor * (opposed to its target) as defined here. */ private static InstructionHandle[] getSuccessors(InstructionHandle instruction){ Instruction inst = instruction.getInstruction(); if (inst instanceof RET){ return empty; } // Terminates method normally. if (inst instanceof ReturnInstruction){ return empty; } // Terminates method abnormally, because JustIce mandates // subroutines not to be protected by exception handlers. if (inst instanceof ATHROW){ return empty; } final InstructionHandle[] single = new InstructionHandle[1]; // See method comment. if (inst instanceof JsrInstruction){ single[0] = instruction.getNext(); return single; } if (inst instanceof GotoInstruction){ single[0] = ((GotoInstruction) inst).getTarget(); return single; } if (inst instanceof BranchInstruction){ if (inst instanceof Select){ // BCEL's getTargets() returns only the non-default targets, // thanks to Eli Tilevich for reporting. InstructionHandle[] matchTargets = ((Select) inst).getTargets(); InstructionHandle[] ret = new InstructionHandle[matchTargets.length+1]; ret[0] = ((Select) inst).getTarget(); System.arraycopy(matchTargets, 0, ret, 1, matchTargets.length); return ret; } else{ final InstructionHandle[] pair = new InstructionHandle[2]; pair[0] = instruction.getNext(); pair[1] = ((BranchInstruction) inst).getTarget(); return pair; } } // default case: Fall through. single[0] = instruction.getNext(); return single; }
/** * A utility method that calculates the successors of a given InstructionHandle * That means, a RET does have successors as defined here. * A JsrInstruction has its target as its successor * (opposed to its physical successor) as defined here. */ // TODO: implement caching! private InstructionHandle[] _getSuccessors(){ final InstructionHandle[] empty = new InstructionHandle[0]; final InstructionHandle[] single = new InstructionHandle[1]; final InstructionHandle[] pair = new InstructionHandle[2]; Instruction inst = getInstruction().getInstruction(); if (inst instanceof RET){ Subroutine s = subroutines.subroutineOf(getInstruction()); if (s==null){ //return empty; // RET in dead code. "empty" would be the correct answer, but we know something about the surrounding project... throw new AssertionViolatedException("Asking for successors of a RET in dead code?!"); } //TODO: remove throw new AssertionViolatedException("DID YOU REALLY WANT TO ASK FOR RET'S SUCCS?"); /* InstructionHandle[] jsrs = s.getEnteringJsrInstructions(); InstructionHandle[] ret = new InstructionHandle[jsrs.length]; for (int i=0; i<jsrs.length; i++){ ret[i] = jsrs[i].getNext(); } return ret; */ } // Terminates method normally. if (inst instanceof ReturnInstruction){ return empty; } // Terminates method abnormally, because JustIce mandates // subroutines not to be protected by exception handlers. if (inst instanceof ATHROW){ return empty; } // See method comment. if (inst instanceof JsrInstruction){ single[0] = ((JsrInstruction) inst).getTarget(); return single; } if (inst instanceof GotoInstruction){ single[0] = ((GotoInstruction) inst).getTarget(); return single; } if (inst instanceof BranchInstruction){ if (inst instanceof Select){ // BCEL's getTargets() returns only the non-default targets, // thanks to Eli Tilevich for reporting. InstructionHandle[] matchTargets = ((Select) inst).getTargets(); InstructionHandle[] ret = new InstructionHandle[matchTargets.length+1]; ret[0] = ((Select) inst).getTarget(); System.arraycopy(matchTargets, 0, ret, 1, matchTargets.length); return ret; } else{ pair[0] = getInstruction().getNext(); pair[1] = ((BranchInstruction) inst).getTarget(); return pair; } } // default case: Fall through. single[0] = getInstruction().getNext(); return single; }
