KickJava   Java API By Example, From Geeks To Geeks.

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


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
20 import java.io.PrintWriter JavaDoc;
21 import java.io.StringWriter JavaDoc;
22 import java.util.ArrayList JavaDoc;
23 import java.util.List JavaDoc;
24 import java.util.Random JavaDoc;
25 import java.util.Vector JavaDoc;
26 import org.apache.bcel.Constants;
27 import org.apache.bcel.Repository;
28 import org.apache.bcel.classfile.JavaClass;
29 import org.apache.bcel.classfile.Method;
30 import org.apache.bcel.generic.ConstantPoolGen;
31 import org.apache.bcel.generic.InstructionHandle;
32 import org.apache.bcel.generic.JsrInstruction;
33 import org.apache.bcel.generic.MethodGen;
34 import org.apache.bcel.generic.ObjectType;
35 import org.apache.bcel.generic.RET;
36 import org.apache.bcel.generic.ReturnInstruction;
37 import org.apache.bcel.generic.ReturnaddressType;
38 import org.apache.bcel.generic.Type;
39 import org.apache.bcel.verifier.PassVerifier;
40 import org.apache.bcel.verifier.VerificationResult;
41 import org.apache.bcel.verifier.Verifier;
42 import org.apache.bcel.verifier.exc.AssertionViolatedException;
43 import org.apache.bcel.verifier.exc.VerifierConstraintViolatedException;
44
45 /**
46  * This PassVerifier verifies a method of class file according to pass 3,
47  * so-called structural verification as described in The Java Virtual Machine
48  * Specification, 2nd edition.
49  * More detailed information is to be found at the do_verify() method's
50  * documentation.
51  *
52  * @version $Id: Pass3bVerifier.java 384759 2006-03-10 10:38:59Z tcurdt $
53  * @author Enver Haase
54  * @see #do_verify()
55  */
56
57 public final class Pass3bVerifier extends PassVerifier{
58     /* TODO: Throughout pass 3b, upper halves of LONG and DOUBLE
59                         are represented by Type.UNKNOWN. This should be changed
60                         in favour of LONG_Upper and DOUBLE_Upper as in pass 2. */
61
62     /**
63      * An InstructionContextQueue is a utility class that holds
64      * (InstructionContext, ArrayList) pairs in a Queue data structure.
65      * This is used to hold information about InstructionContext objects
66      * externally --- i.e. that information is not saved inside the
67      * InstructionContext object itself. This is useful to save the
68      * execution path of the symbolic execution of the
69      * Pass3bVerifier - this is not information
70      * that belongs into the InstructionContext object itself.
71      * Only at "execute()"ing
72      * time, an InstructionContext object will get the current information
73      * we have about its symbolic execution predecessors.
74      */
75     private static final class InstructionContextQueue{
76         private List JavaDoc ics = new Vector JavaDoc(); // Type: InstructionContext
77 private List JavaDoc ecs = new Vector JavaDoc(); // Type: ArrayList (of InstructionContext)
78 public void add(InstructionContext ic, ArrayList JavaDoc executionChain){
79             ics.add(ic);
80             ecs.add(executionChain);
81         }
82         public boolean isEmpty(){
83             return ics.isEmpty();
84         }
85         public void remove(){
86             this.remove(0);
87         }
88         public void remove(int i){
89             ics.remove(i);
90             ecs.remove(i);
91         }
92         public InstructionContext getIC(int i){
93             return (InstructionContext) ics.get(i);
94         }
95         public ArrayList JavaDoc getEC(int i){
96             return (ArrayList JavaDoc) ecs.get(i);
97         }
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 Verifier myOwner;
108
109     /** The method number to verify. */
110     private int method_no;
111
112     /**
113      * This class should only be instantiated by a Verifier.
114      *
115      * @see org.apache.bcel.verifier.Verifier
116      */
117     public Pass3bVerifier(Verifier owner, 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      */
129     private void circulationPump(ControlFlowGraph cfg, InstructionContext start, Frame vanillaFrame, InstConstraintVisitor icv, ExecutionVisitor ev){
130         final Random JavaDoc random = new Random JavaDoc();
131         InstructionContextQueue icq = new InstructionContextQueue();
132         
133         start.execute(vanillaFrame, new ArrayList JavaDoc(), icv, ev); // new ArrayList() <=> no Instruction was executed before
134 // => Top-Level routine (no jsr call before)
135 icq.add(start, new ArrayList JavaDoc());
136
137         // LOOP!
138 while (!icq.isEmpty()){
139             InstructionContext u;
140             ArrayList JavaDoc ec;
141             if (!DEBUG){
142                 int r = random.nextInt(icq.size());
143                 u = icq.getIC(r);
144                 ec = icq.getEC(r);
145                 icq.remove(r);
146             }
147             else{
148                 u = icq.getIC(0);
149                 ec = icq.getEC(0);
150                 icq.remove(0);
151             }
152             
153             ArrayList JavaDoc oldchain = (ArrayList JavaDoc) (ec.clone());
154             ArrayList JavaDoc newchain = (ArrayList JavaDoc) (ec.clone());
155             newchain.add(u);
156
157             if ((u.getInstruction().getInstruction()) instanceof RET){
158 //System.err.println(u);
159 // We can only follow _one_ successor, the one after the
160 // JSR that was recently executed.
161 RET ret = (RET) (u.getInstruction().getInstruction());
162                 ReturnaddressType t = (ReturnaddressType) u.getOutFrame(oldchain).getLocals().get(ret.getIndex());
163                 InstructionContext theSuccessor = cfg.contextOf(t.getTarget());
164
165                 // Sanity check
166 InstructionContext lastJSR = null;
167                 int skip_jsr = 0;
168                 for (int ss=oldchain.size()-1; ss >= 0; ss--){
169                     if (skip_jsr < 0){
170                         throw new AssertionViolatedException("More RET than JSR in execution chain?!");
171                     }
172 //System.err.println("+"+oldchain.get(ss));
173 if (((InstructionContext) oldchain.get(ss)).getInstruction().getInstruction() instanceof JsrInstruction){
174                         if (skip_jsr == 0){
175                             lastJSR = (InstructionContext) oldchain.get(ss);
176                             break;
177                         }
178                         else{
179                             skip_jsr--;
180                         }
181                     }
182                     if (((InstructionContext) oldchain.get(ss)).getInstruction().getInstruction() instanceof RET){
183                         skip_jsr++;
184                     }
185                 }
186                 if (lastJSR == null){
187                     throw new AssertionViolatedException("RET without a JSR before in ExecutionChain?! EC: '"+oldchain+"'.");
188                 }
189                 JsrInstruction jsr = (JsrInstruction) (lastJSR.getInstruction().getInstruction());
190                 if ( theSuccessor != (cfg.contextOf(jsr.physicalSuccessor())) ){
191                     throw new AssertionViolatedException("RET '"+u.getInstruction()+"' info inconsistent: jump back to '"+theSuccessor+"' or '"+cfg.contextOf(jsr.physicalSuccessor())+"'?");
192                 }
193                 
194                 if (theSuccessor.execute(u.getOutFrame(oldchain), newchain, icv, ev)){
195                     icq.add(theSuccessor, (ArrayList JavaDoc) newchain.clone());
196                 }
197             }
198             else{// "not a ret"
199
200                 // Normal successors. Add them to the queue of successors.
201 InstructionContext[] succs = u.getSuccessors();
202                 for (int s=0; s<succs.length; s++){
203                     InstructionContext v = succs[s];
204                     if (v.execute(u.getOutFrame(oldchain), newchain, icv, ev)){
205                         icq.add(v, (ArrayList JavaDoc) newchain.clone());
206                     }
207                 }
208             }// end "not a ret"
209
210             // Exception Handlers. Add them to the queue of successors.
211 // [subroutines are never protected; mandated by JustIce]
212 ExceptionHandler[] exc_hds = u.getExceptionHandlers();
213             for (int s=0; s<exc_hds.length; s++){
214                 InstructionContext v = cfg.contextOf(exc_hds[s].getHandlerStart());
215                 // TODO: the "oldchain" and "newchain" is used to determine the subroutine
216 // we're in (by searching for the last JSR) by the InstructionContext
217 // implementation. Therefore, we should not use this chain mechanism
218 // when dealing with exception handlers.
219 // Example: a JSR with an exception handler as its successor does not
220 // mean we're in a subroutine if we go to the exception handler.
221 // We should address this problem later; by now we simply "cut" the chain
222 // by using an empty chain for the exception handlers.
223 //if (v.execute(new Frame(u.getOutFrame(oldchain).getLocals(), new OperandStack (u.getOutFrame().getStack().maxStack(), (exc_hds[s].getExceptionType()==null? Type.THROWABLE : exc_hds[s].getExceptionType())) ), newchain), icv, ev){
224 //icq.add(v, (ArrayList) newchain.clone());
225 if (v.execute(new Frame(u.getOutFrame(oldchain).getLocals(), new OperandStack (u.getOutFrame(oldchain).getStack().maxStack(), (exc_hds[s].getExceptionType()==null? Type.THROWABLE : exc_hds[s].getExceptionType())) ), new ArrayList JavaDoc(), icv, ev)){
226                     icq.add(v, new ArrayList JavaDoc());
227                 }
228             }
229
230         }// while (!icq.isEmpty()) END
231
232         InstructionHandle ih = start.getInstruction();
233         do{
234             if ((ih.getInstruction() instanceof ReturnInstruction) && (!(cfg.isDead(ih)))) {
235                 InstructionContext ic = cfg.contextOf(ih);
236                 Frame f = ic.getOutFrame(new ArrayList JavaDoc()); // TODO: This is buggy, we check only the top-level return instructions this way. Maybe some maniac returns from a method when in a subroutine?
237 LocalVariables lvs = f.getLocals();
238                 for (int i=0; i<lvs.maxLocals(); i++){
239                     if (lvs.get(i) instanceof UninitializedObjectType){
240                         this.addMessage("Warning: ReturnInstruction '"+ic+"' may leave method with an uninitialized object in the local variables array '"+lvs+"'.");
241                     }
242                 }
243                 OperandStack os = f.getStack();
244                 for (int i=0; i<os.size(); i++){
245                     if (os.peek(i) instanceof UninitializedObjectType){
246                         this.addMessage("Warning: ReturnInstruction '"+ic+"' may leave method with an uninitialized object on the operand stack '"+os+"'.");
247                     }
248                 }
249             }
250         }while ((ih = ih.getNext()) != null);
251         
252     }
253
254     /**
255      * Pass 3b implements the data flow analysis as described in the Java Virtual
256      * Machine Specification, Second Edition.
257      * Later versions will use LocalVariablesInfo objects to verify if the
258      * verifier-inferred types and the class file's debug information (LocalVariables
259      * attributes) match [TODO].
260      *
261      * @see org.apache.bcel.verifier.statics.LocalVariablesInfo
262      * @see org.apache.bcel.verifier.statics.Pass2Verifier#getLocalVariablesInfo(int)
263      */
264     public VerificationResult do_verify(){
265         if (! myOwner.doPass3a(method_no).equals(VerificationResult.VR_OK)){
266             return VerificationResult.VR_NOTYET;
267         }
268
269         // Pass 3a ran before, so it's safe to assume the JavaClass object is
270 // in the BCEL repository.
271 JavaClass jc;
272         try {
273             jc = Repository.lookupClass(myOwner.getClassName());
274         } catch (ClassNotFoundException JavaDoc e) {
275             // FIXME: maybe not the best way to handle this
276 throw new AssertionViolatedException("Missing class: " + e.toString());
277         }
278
279         ConstantPoolGen constantPoolGen = new ConstantPoolGen(jc.getConstantPool());
280         // Init Visitors
281 InstConstraintVisitor icv = new InstConstraintVisitor();
282         icv.setConstantPoolGen(constantPoolGen);
283         
284         ExecutionVisitor ev = new ExecutionVisitor();
285         ev.setConstantPoolGen(constantPoolGen);
286         
287         Method[] methods = jc.getMethods(); // Method no "method_no" exists, we ran Pass3a before on it!
288
289         try{
290
291             MethodGen mg = new MethodGen(methods[method_no], myOwner.getClassName(), constantPoolGen);
292
293             icv.setMethodGen(mg);
294                 
295             ////////////// DFA BEGINS HERE ////////////////
296 if (! (mg.isAbstract() || mg.isNative()) ){ // IF mg HAS CODE (See pass 2)
297
298                 ControlFlowGraph cfg = new ControlFlowGraph(mg);
299
300                 // Build the initial frame situation for this method.
301 Frame f = new Frame(mg.getMaxLocals(),mg.getMaxStack());
302                 if ( !mg.isStatic() ){
303                     if (mg.getName().equals(Constants.CONSTRUCTOR_NAME)){
304                         Frame._this = new UninitializedObjectType(new ObjectType(jc.getClassName()));
305                         f.getLocals().set(0, Frame._this);
306                     }
307                     else{
308                         Frame._this = null;
309                         f.getLocals().set(0, new ObjectType(jc.getClassName()));
310                     }
311                 }
312                 Type[] argtypes = mg.getArgumentTypes();
313                 int twoslotoffset = 0;
314                 for (int j=0; j<argtypes.length; j++){
315                     if (argtypes[j] == Type.SHORT || argtypes[j] == Type.BYTE || argtypes[j] == Type.CHAR || argtypes[j] == Type.BOOLEAN){
316                         argtypes[j] = Type.INT;
317                     }
318                     f.getLocals().set(twoslotoffset + j + (mg.isStatic()?0:1), argtypes[j]);
319                     if (argtypes[j].getSize() == 2){
320                         twoslotoffset++;
321                         f.getLocals().set(twoslotoffset + j + (mg.isStatic()?0:1), Type.UNKNOWN);
322                     }
323                 }
324                 circulationPump(cfg, cfg.contextOf(mg.getInstructionList().getStart()), f, icv, ev);
325             }
326         }
327         catch (VerifierConstraintViolatedException ce){
328             ce.extendMessage("Constraint violated in method '"+methods[method_no]+"':\n","");
329             return new VerificationResult(VerificationResult.VERIFIED_REJECTED, ce.getMessage());
330         }
331         catch (RuntimeException JavaDoc re){
332             // These are internal errors
333
334             StringWriter JavaDoc sw = new StringWriter JavaDoc();
335             PrintWriter JavaDoc pw = new PrintWriter JavaDoc(sw);
336             re.printStackTrace(pw);
337
338             throw new AssertionViolatedException("Some RuntimeException occured while verify()ing class '"+jc.getClassName()+"', method '"+methods[method_no]+"'. Original RuntimeException's stack trace:\n---\n"+sw+"---\n");
339         }
340         return VerificationResult.VR_OK;
341     }
342
343     /** Returns the method number as supplied when instantiating. */
344     public int getMethodNo(){
345         return method_no;
346     }
347 }
348
Popular Tags