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