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