1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 package org.apache.bcel.verifier.structurals;
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
51
52
53
54
55
56
57 public final class Pass3bVerifier extends PassVerifier {
58
59
60
61
62
63
64
65
66
67
68
69
70
71 private static final class InstructionContextQueue {
72
73
74 private final List<InstructionContext> ics = new Vector<>();
75
76 private final List<ArrayList<InstructionContext>> ecs = new Vector<>();
77
78
79
80
81
82
83
84 public void add(final InstructionContext ic, final ArrayList<InstructionContext> executionChain) {
85 ics.add(ic);
86 ecs.add(executionChain);
87 }
88
89
90
91
92
93
94
95 public ArrayList<InstructionContext> getEC(final int i) {
96 return ecs.get(i);
97 }
98
99
100
101
102
103
104
105 public InstructionContext getIC(final int i) {
106 return ics.get(i);
107 }
108
109
110
111
112
113
114 public boolean isEmpty() {
115 return ics.isEmpty();
116 }
117
118
119
120
121
122
123 public void remove(final int i) {
124 ics.remove(i);
125 ecs.remove(i);
126 }
127
128
129
130
131
132
133 public int size() {
134 return ics.size();
135 }
136 }
137
138
139 private static final boolean DEBUG = true;
140
141
142 private final Verifier myOwner;
143
144
145 private final int methodNo;
146
147
148
149
150
151
152 public Pass3bVerifier(final Verifier myOwner, final int methodNo) {
153 this.myOwner = myOwner;
154 this.methodNo = methodNo;
155 }
156
157
158
159
160
161 private void circulationPump(final MethodGen m, final ControlFlowGraph cfg, final InstructionContext start, final Frame vanillaFrame,
162 final InstConstraintVisitor icv, final ExecutionVisitor ev) {
163 final Random random = new Random();
164 final InstructionContextQueue icq = new InstructionContextQueue();
165
166 start.execute(vanillaFrame, new ArrayList<>(), icv, ev);
167
168
169 icq.add(start, new ArrayList<>());
170
171
172 while (!icq.isEmpty()) {
173 final InstructionContext u;
174 final ArrayList<InstructionContext> ec;
175 if (!DEBUG) {
176 final int r = random.nextInt(icq.size());
177 u = icq.getIC(r);
178 ec = icq.getEC(r);
179 icq.remove(r);
180 } else {
181 u = icq.getIC(0);
182 ec = icq.getEC(0);
183 icq.remove(0);
184 }
185
186 @SuppressWarnings("unchecked")
187 final ArrayList<InstructionContext> oldchain = (ArrayList<InstructionContext>) ec.clone();
188 @SuppressWarnings("unchecked")
189 final ArrayList<InstructionContext> newchain = (ArrayList<InstructionContext>) ec.clone();
190 newchain.add(u);
191
192 if (u.getInstruction().getInstruction() instanceof RET) {
193
194
195
196 final RET ret = (RET) u.getInstruction().getInstruction();
197 final ReturnaddressType t = (ReturnaddressType) u.getOutFrame(oldchain).getLocals().get(ret.getIndex());
198 final InstructionContext theSuccessor = cfg.contextOf(t.getTarget());
199
200
201 InstructionContext lastJSR = null;
202 int skipJsr = 0;
203 for (int ss = oldchain.size() - 1; ss >= 0; ss--) {
204 if (skipJsr < 0) {
205 throw new AssertionViolatedException("More RET than JSR in execution chain?!");
206 }
207
208 if (oldchain.get(ss).getInstruction().getInstruction() instanceof JsrInstruction) {
209 if (skipJsr == 0) {
210 lastJSR = oldchain.get(ss);
211 break;
212 }
213 skipJsr--;
214 }
215 if (oldchain.get(ss).getInstruction().getInstruction() instanceof RET) {
216 skipJsr++;
217 }
218 }
219 if (lastJSR == null) {
220 throw new AssertionViolatedException("RET without a JSR before in ExecutionChain?! EC: '" + oldchain + "'.");
221 }
222 final JsrInstruction jsr = (JsrInstruction) lastJSR.getInstruction().getInstruction();
223 if (theSuccessor != cfg.contextOf(jsr.physicalSuccessor())) {
224 throw new AssertionViolatedException("RET '" + u.getInstruction() + "' info inconsistent: jump back to '" + theSuccessor + "' or '"
225 + cfg.contextOf(jsr.physicalSuccessor()) + "'?");
226 }
227
228 if (theSuccessor.execute(u.getOutFrame(oldchain), newchain, icv, ev)) {
229 @SuppressWarnings("unchecked")
230 final ArrayList<InstructionContext> newchainClone = (ArrayList<InstructionContext>) newchain.clone();
231 icq.add(theSuccessor, newchainClone);
232 }
233 } else {
234
235
236 final InstructionContext[] succs = u.getSuccessors();
237 for (final InstructionContext v : succs) {
238 if (v.execute(u.getOutFrame(oldchain), newchain, icv, ev)) {
239 @SuppressWarnings("unchecked")
240 final ArrayList<InstructionContext> newchainClone = (ArrayList<InstructionContext>) newchain.clone();
241 icq.add(v, newchainClone);
242 }
243 }
244 }
245
246
247
248 final ExceptionHandler[] excHds = u.getExceptionHandlers();
249 for (final ExceptionHandler excHd : excHds) {
250 final InstructionContext v = cfg.contextOf(excHd.getHandlerStart());
251
252
253
254
255
256
257
258
259
260
261
262
263 if (v.execute(new Frame(u.getOutFrame(oldchain).getLocals(), new OperandStack(u.getOutFrame(oldchain).getStack().maxStack(),
264 excHd.getExceptionType() == null ? Type.THROWABLE : excHd.getExceptionType())), new ArrayList<>(), icv, ev)) {
265 icq.add(v, new ArrayList<>());
266 }
267 }
268
269 }
270
271 InstructionHandle ih = start.getInstruction();
272 do {
273 if (ih.getInstruction() instanceof ReturnInstruction && !cfg.isDead(ih)) {
274 final InstructionContext ic = cfg.contextOf(ih);
275
276
277 final Frame f = ic.getOutFrame(new ArrayList<>());
278 final LocalVariables lvs = f.getLocals();
279 for (int i = 0; i < lvs.maxLocals(); i++) {
280 if (lvs.get(i) instanceof UninitializedObjectType) {
281 addMessage("Warning: ReturnInstruction '" + ic + "' may leave method with an uninitialized object in the local variables array '"
282 + lvs + "'.");
283 }
284 }
285 final OperandStack os = f.getStack();
286 for (int i = 0; i < os.size(); i++) {
287 if (os.peek(i) instanceof UninitializedObjectType) {
288 addMessage(
289 "Warning: ReturnInstruction '" + ic + "' may leave method with an uninitialized object on the operand stack '" + os + "'.");
290 }
291 }
292
293 Type returnedType = null;
294 final OperandStack inStack = ic.getInFrame().getStack();
295 if (inStack.size() >= 1) {
296 returnedType = inStack.peek();
297 } else {
298 returnedType = Type.VOID;
299 }
300
301 if (returnedType != null) {
302 if (returnedType instanceof ReferenceType) {
303 try {
304 if (!((ReferenceType) returnedType).isCastableTo(m.getReturnType())) {
305 invalidReturnTypeError(returnedType, m);
306 }
307 } catch (final ClassNotFoundException e) {
308
309 throw new IllegalArgumentException(e);
310 }
311 } else if (!returnedType.equals(m.getReturnType().normalizeForStackOrLocal())) {
312 invalidReturnTypeError(returnedType, m);
313 }
314 }
315 }
316 } while ((ih = ih.getNext()) != null);
317
318 }
319
320
321
322
323
324
325
326
327
328 @Override
329 public VerificationResult do_verify() {
330 if (!myOwner.doPass3a(methodNo).equals(VerificationResult.VR_OK)) {
331 return VerificationResult.VR_NOTYET;
332 }
333
334
335
336 final JavaClass jc;
337 try {
338 jc = Repository.lookupClass(myOwner.getClassName());
339 } catch (final ClassNotFoundException e) {
340
341 throw new AssertionViolatedException("Missing class: " + e, e);
342 }
343
344 final ConstantPoolGen constantPoolGen = new ConstantPoolGen(jc.getConstantPool());
345
346 final InstConstraintVisitor icv = new InstConstraintVisitor();
347 icv.setConstantPoolGen(constantPoolGen);
348
349 final ExecutionVisitor ev = new ExecutionVisitor();
350 ev.setConstantPoolGen(constantPoolGen);
351
352 final Method[] methods = jc.getMethods();
353
354 try {
355
356 final MethodGen mg = new MethodGen(methods[methodNo], myOwner.getClassName(), constantPoolGen);
357
358 icv.setMethodGen(mg);
359
360
361 if (!(mg.isAbstract() || mg.isNative())) {
362
363 final ControlFlowGraph cfg = new ControlFlowGraph(mg);
364
365
366 final Frame f = new Frame(mg.getMaxLocals(), mg.getMaxStack());
367 if (!mg.isStatic()) {
368 if (mg.getName().equals(Const.CONSTRUCTOR_NAME)) {
369 Frame.setThis(new UninitializedObjectType(ObjectType.getInstance(jc.getClassName())));
370 f.getLocals().set(0, Frame.getThis());
371 } else {
372 Frame.setThis(null);
373 f.getLocals().set(0, ObjectType.getInstance(jc.getClassName()));
374 }
375 }
376 final Type[] argtypes = mg.getArgumentTypes();
377 int twoslotoffset = 0;
378 for (int j = 0; j < argtypes.length; j++) {
379 if (argtypes[j] == Type.SHORT || argtypes[j] == Type.BYTE || argtypes[j] == Type.CHAR || argtypes[j] == Type.BOOLEAN) {
380 argtypes[j] = Type.INT;
381 }
382 f.getLocals().set(twoslotoffset + j + (mg.isStatic() ? 0 : 1), argtypes[j]);
383 if (argtypes[j].getSize() == 2) {
384 twoslotoffset++;
385 f.getLocals().set(twoslotoffset + j + (mg.isStatic() ? 0 : 1), Type.UNKNOWN);
386 }
387 }
388 circulationPump(mg, cfg, cfg.contextOf(mg.getInstructionList().getStart()), f, icv, ev);
389 }
390 } catch (final VerifierConstraintViolatedException ce) {
391 ce.extendMessage("Constraint violated in method '" + methods[methodNo] + "':\n", "");
392 return new VerificationResult(VerificationResult.VERIFIED_REJECTED, ce.getMessage());
393 } catch (final RuntimeException re) {
394
395
396 final StringWriter sw = new StringWriter();
397 final PrintWriter pw = new PrintWriter(sw);
398 re.printStackTrace(pw);
399
400 throw new AssertionViolatedException("Some RuntimeException occurred while verify()ing class '" + jc.getClassName() + "', method '"
401 + methods[methodNo] + "'. Original RuntimeException's stack trace:\n---\n" + sw + "---\n", re);
402 }
403 return VerificationResult.VR_OK;
404 }
405
406
407 public int getMethodNo() {
408 return methodNo;
409 }
410
411
412
413
414
415
416
417
418
419 public void invalidReturnTypeError(final Type returnedType, final MethodGen m) {
420 throw new StructuralCodeConstraintException("Returned type " + returnedType + " does not match Method's return type " + m.getReturnType());
421 }
422 }