KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > bcel > verifier > structurals > ModifiedPass3bVerifier


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