001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 2000 Feng Qian
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the
016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017: * Boston, MA 02111-1307, USA.
018: */
019:
020: /*
021: * Modified by the Sable Research Group and others 1997-1999.
022: * See the 'credits' file distributed with Soot for the complete list of
023: * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
024: */
025:
026: package soot.jimple.toolkits.annotation.arraycheck;
027:
028: import soot.options.*;
029:
030: import soot.*;
031: import soot.jimple.*;
032: import soot.util.*;
033: import soot.tagkit.*;
034: import soot.jimple.toolkits.annotation.tags.*;
035: import java.util.*;
036: import soot.options.ABCOptions;
037:
038: public class ArrayBoundsChecker extends BodyTransformer {
039: public ArrayBoundsChecker(Singletons.Global g) {
040: }
041:
042: public static ArrayBoundsChecker v() {
043: return G
044: .v()
045: .soot_jimple_toolkits_annotation_arraycheck_ArrayBoundsChecker();
046: }
047:
048: protected boolean takeClassField = false;
049: protected boolean takeFieldRef = false;
050: protected boolean takeArrayRef = false;
051: protected boolean takeCSE = false;
052: protected boolean takeRectArray = false;
053: protected boolean addColorTags = false;
054:
055: protected void internalTransform(Body body, String phaseName,
056: Map opts) {
057: ABCOptions options = new ABCOptions(opts);
058: if (options.with_all()) {
059: takeClassField = true;
060: takeFieldRef = true;
061: takeArrayRef = true;
062: takeCSE = true;
063: takeRectArray = true;
064: } else {
065: takeClassField = options.with_classfield();
066: takeFieldRef = options.with_fieldref();
067: takeArrayRef = options.with_arrayref();
068: takeCSE = options.with_cse();
069: takeRectArray = options.with_rectarray();
070: }
071:
072: addColorTags = options.add_color_tags();
073:
074: {
075: SootMethod m = body.getMethod();
076:
077: Date start = new Date();
078:
079: if (Options.v().verbose()) {
080: G.v().out
081: .println("[abc] Analyzing array bounds information for "
082: + m.getName());
083: G.v().out.println("[abc] Started on " + start);
084: }
085:
086: ArrayBoundsCheckerAnalysis analysis = null;
087:
088: if (hasArrayLocals(body)) {
089: analysis = new ArrayBoundsCheckerAnalysis(body,
090: takeClassField, takeFieldRef, takeArrayRef,
091: takeCSE, takeRectArray);
092: }
093:
094: SootClass counterClass = null;
095: SootMethod increase = null;
096:
097: if (options.profiling()) {
098: counterClass = Scene.v().loadClassAndSupport(
099: "MultiCounter");
100: increase = counterClass.getMethod("void increase(int)");
101: }
102:
103: Chain units = body.getUnits();
104:
105: IntContainer zero = new IntContainer(0);
106:
107: Iterator unitIt = units.snapshotIterator();
108:
109: while (unitIt.hasNext()) {
110: Stmt stmt = (Stmt) unitIt.next();
111:
112: if (stmt.containsArrayRef()) {
113: ArrayRef aref = stmt.getArrayRef();
114:
115: {
116: WeightedDirectedSparseGraph vgraph = (WeightedDirectedSparseGraph) analysis
117: .getFlowBefore(stmt);
118:
119: int res = interpretGraph(vgraph, aref, stmt,
120: zero);
121:
122: boolean lowercheck = true;
123: boolean uppercheck = true;
124:
125: if (res == 0) {
126: lowercheck = true;
127: uppercheck = true;
128: } else if (res == 1) {
129: lowercheck = true;
130: uppercheck = false;
131: } else if (res == 2) {
132: lowercheck = false;
133: uppercheck = true;
134: } else if (res == 3) {
135: lowercheck = false;
136: uppercheck = false;
137: }
138:
139: if (addColorTags) {
140: if (res == 0) {
141: aref.getIndexBox().addTag(
142: new ColorTag(255, 0, 0, false,
143: "ArrayCheckTag"));
144: } else if (res == 1) {
145: aref
146: .getIndexBox()
147: .addTag(
148: new ColorTag(255, 248,
149: 35, false,
150: "ArrayCheckTag"));
151: } else if (res == 2) {
152: aref
153: .getIndexBox()
154: .addTag(
155: new ColorTag(255, 163,
156: 0, false,
157: "ArrayCheckTag"));
158: } else if (res == 3) {
159: aref
160: .getIndexBox()
161: .addTag(
162: new ColorTag(45, 255,
163: 84, false,
164: "ArrayCheckTag"));
165: }
166: SootClass bodyClass = body.getMethod()
167: .getDeclaringClass();
168: Iterator keysIt = bodyClass.getTags()
169: .iterator();
170: boolean keysAdded = false;
171: while (keysIt.hasNext()) {
172: Object next = keysIt.next();
173: if (next instanceof KeyTag) {
174: if (((KeyTag) next).analysisType()
175: .equals("ArrayCheckTag")) {
176: keysAdded = true;
177: }
178: }
179: }
180: if (!keysAdded) {
181: bodyClass
182: .addTag(new KeyTag(
183: 255,
184: 0,
185: 0,
186: "ArrayBounds: Unsafe Lower and Unsafe Upper",
187: "ArrayCheckTag"));
188: bodyClass
189: .addTag(new KeyTag(
190: 255,
191: 248,
192: 35,
193: "ArrayBounds: Unsafe Lower and Safe Upper",
194: "ArrayCheckTag"));
195: bodyClass
196: .addTag(new KeyTag(
197: 255,
198: 163,
199: 0,
200: "ArrayBounds: Safe Lower and Unsafe Upper",
201: "ArrayCheckTag"));
202: bodyClass
203: .addTag(new KeyTag(
204: 45,
205: 255,
206: 84,
207: "ArrayBounds: Safe Lower and Safe Upper",
208: "ArrayCheckTag"));
209: }
210: }
211:
212: /*
213: boolean lowercheck = true;
214: boolean uppercheck = true;
215:
216: {
217: if (Options.v().debug())
218: {
219: if (!vgraph.makeShortestPathGraph())
220: {
221: G.v().out.println(stmt+" :");
222: G.v().out.println(vgraph);
223: }
224: }
225:
226: Value base = aref.getBase();
227: Value index = aref.getIndex();
228:
229: if (index instanceof IntConstant)
230: {
231: int indexv = ((IntConstant)index).value;
232:
233: if (vgraph.hasEdge(base, zero))
234: {
235: int alength = vgraph.edgeWeight(base, zero);
236:
237: if (-alength > indexv)
238: uppercheck = false;
239: }
240:
241: if (indexv >= 0)
242: lowercheck = false;
243: }
244: else
245: {
246: if (vgraph.hasEdge(base, index))
247: {
248: int upperdistance = vgraph.edgeWeight(base, index);
249: if (upperdistance < 0)
250: uppercheck = false;
251: }
252:
253: if (vgraph.hasEdge(index, zero))
254: {
255: int lowerdistance = vgraph.edgeWeight(index, zero);
256:
257: if (lowerdistance <= 0)
258: lowercheck = false;
259: }
260: }
261: }*/
262:
263: if (options.profiling()) {
264: int lowercounter = 0;
265: if (!lowercheck)
266: lowercounter = 1;
267:
268: units
269: .insertBefore(
270: Jimple
271: .v()
272: .newInvokeStmt(
273: Jimple
274: .v()
275: .newStaticInvokeExpr(
276: increase
277: .makeRef(),
278: IntConstant
279: .v(lowercounter))),
280: stmt);
281:
282: int uppercounter = 2;
283: if (!uppercheck)
284: uppercounter = 3;
285:
286: units
287: .insertBefore(
288: Jimple
289: .v()
290: .newInvokeStmt(
291: Jimple
292: .v()
293: .newStaticInvokeExpr(
294: increase
295: .makeRef(),
296: IntConstant
297: .v(uppercounter))),
298: stmt);
299:
300: /*
301: if (!lowercheck && !uppercheck)
302: {
303: units.insertBefore(Jimple.v().newInvokeStmt(
304: Jimple.v().newStaticInvokeExpr(increase,
305: IntConstant.v(4))), stmt);
306:
307: NullCheckTag nullTag = (NullCheckTag)stmt.getTag("NullCheckTag");
308:
309: if (nullTag != null && !nullTag.needCheck())
310: units.insertBefore(Jimple.v().newInvokeStmt(
311: Jimple.v().newStaticInvokeExpr(increase,
312: IntConstant.v(7))), stmt);
313: }
314: */
315: } else {
316: Tag checkTag = new ArrayCheckTag(
317: lowercheck, uppercheck);
318: stmt.addTag(checkTag);
319: }
320: }
321: }
322: }
323:
324: if (addColorTags && takeRectArray) {
325: RectangularArrayFinder raf = RectangularArrayFinder.v();
326: for (Iterator vbIt = body.getUseAndDefBoxes()
327: .iterator(); vbIt.hasNext();) {
328: final ValueBox vb = (ValueBox) vbIt.next();
329: Value v = vb.getValue();
330: if (!(v instanceof Local))
331: continue;
332: Type t = v.getType();
333: if (!(t instanceof ArrayType))
334: continue;
335: ArrayType at = (ArrayType) t;
336: if (at.numDimensions <= 1)
337: continue;
338: vb.addTag(new ColorTag(
339: raf.isRectangular(new MethodLocal(m,
340: (Local) v)) ? ColorTag.GREEN
341: : ColorTag.RED));
342: }
343: }
344:
345: Date finish = new Date();
346: if (Options.v().verbose()) {
347: long runtime = finish.getTime() - start.getTime();
348: G.v().out.println("[abc] ended on " + finish
349: + ". It took " + (runtime / 60000) + " min. "
350: + ((runtime % 60000) / 1000) + " sec.");
351: }
352: }
353: }
354:
355: private boolean hasArrayLocals(Body body) {
356: Iterator localIt = body.getLocals().iterator();
357:
358: while (localIt.hasNext()) {
359: Local local = (Local) localIt.next();
360: if (local.getType() instanceof ArrayType)
361: return true;
362: }
363:
364: return false;
365: }
366:
367: protected int interpretGraph(WeightedDirectedSparseGraph vgraph,
368: ArrayRef aref, Stmt stmt, IntContainer zero) {
369:
370: boolean lowercheck = true;
371: boolean uppercheck = true;
372:
373: {
374: if (Options.v().debug()) {
375: if (!vgraph.makeShortestPathGraph()) {
376: G.v().out.println(stmt + " :");
377: G.v().out.println(vgraph);
378: }
379: }
380:
381: Value base = aref.getBase();
382: Value index = aref.getIndex();
383:
384: if (index instanceof IntConstant) {
385: int indexv = ((IntConstant) index).value;
386:
387: if (vgraph.hasEdge(base, zero)) {
388: int alength = vgraph.edgeWeight(base, zero);
389:
390: if (-alength > indexv)
391: uppercheck = false;
392: }
393:
394: if (indexv >= 0)
395: lowercheck = false;
396: } else {
397: if (vgraph.hasEdge(base, index)) {
398: int upperdistance = vgraph.edgeWeight(base, index);
399: if (upperdistance < 0)
400: uppercheck = false;
401: }
402:
403: if (vgraph.hasEdge(index, zero)) {
404: int lowerdistance = vgraph.edgeWeight(index, zero);
405:
406: if (lowerdistance <= 0)
407: lowercheck = false;
408: }
409: }
410: }
411:
412: if (lowercheck && uppercheck)
413: return 0;
414: else if (lowercheck && !uppercheck)
415: return 1;
416: else if (!lowercheck && uppercheck)
417: return 2;
418: else
419: return 3;
420: }
421: }
|