001: package soot.jimple.toolkits.infoflow;
002:
003: import soot.*;
004:
005: import java.util.*;
006: import soot.toolkits.graph.*;
007: import soot.toolkits.scalar.*;
008: import soot.jimple.internal.*;
009: import soot.jimple.*;
010:
011: // SimpleMethodInfoFlowAnalysis written by Richard L. Halpert, 2007-02-25
012: // Constructs a data flow table for the given method. Ignores indirect flow.
013: // These tables conservatively approximate how data flows from parameters,
014: // fields, and globals to parameters, fields, globals, and the return value.
015: // Note that a ref-type parameter (or field or global) might allow access to a
016: // large data structure, but that entire structure will be represented only by
017: // the parameter's one node in the data flow graph.
018:
019: public class SimpleMethodInfoFlowAnalysis extends ForwardFlowAnalysis {
020: SootMethod sm;
021: Value this Local;
022: InfoFlowAnalysis dfa;
023: boolean refOnly;
024:
025: MutableDirectedGraph infoFlowGraph;
026: Ref returnRef;
027:
028: FlowSet entrySet;
029: FlowSet emptySet;
030:
031: boolean printMessages;
032:
033: public static int counter = 0;
034:
035: public SimpleMethodInfoFlowAnalysis(UnitGraph g,
036: InfoFlowAnalysis dfa, boolean ignoreNonRefTypeFlow) {
037: this (g, dfa, ignoreNonRefTypeFlow, true);
038:
039: counter++;
040:
041: // Add all of the nodes necessary to ensure that this is a complete data flow graph
042:
043: // Add every parameter of this method
044: for (int i = 0; i < sm.getParameterCount(); i++) {
045: EquivalentValue parameterRefEqVal = InfoFlowAnalysis
046: .getNodeForParameterRef(sm, i);
047: if (!infoFlowGraph.containsNode(parameterRefEqVal))
048: infoFlowGraph.addNode(parameterRefEqVal);
049: }
050:
051: // Add every field of this class
052: for (Iterator it = sm.getDeclaringClass().getFields()
053: .iterator(); it.hasNext();) {
054: SootField sf = (SootField) it.next();
055: EquivalentValue fieldRefEqVal = InfoFlowAnalysis
056: .getNodeForFieldRef(sm, sf);
057: if (!infoFlowGraph.containsNode(fieldRefEqVal))
058: infoFlowGraph.addNode(fieldRefEqVal);
059: }
060:
061: // Add every field of this class's superclasses
062: SootClass super class = sm.getDeclaringClass();
063: if (super class.hasSuperclass())
064: super class = sm.getDeclaringClass().getSuperclass();
065: while (super class.hasSuperclass()) // we don't want to process Object
066: {
067: Iterator scFieldsIt = super class.getFields().iterator();
068: while (scFieldsIt.hasNext()) {
069: SootField scField = (SootField) scFieldsIt.next();
070: EquivalentValue fieldRefEqVal = InfoFlowAnalysis
071: .getNodeForFieldRef(sm, scField);
072: if (!infoFlowGraph.containsNode(fieldRefEqVal))
073: infoFlowGraph.addNode(fieldRefEqVal);
074: }
075: super class = super class.getSuperclass();
076: }
077:
078: // Add thisref of this class
079: EquivalentValue this RefEqVal = InfoFlowAnalysis
080: .getNodeForThisRef(sm);
081: if (!infoFlowGraph.containsNode(this RefEqVal))
082: infoFlowGraph.addNode(this RefEqVal);
083:
084: // Add returnref of this method
085: EquivalentValue returnRefEqVal = new CachedEquivalentValue(
086: returnRef);
087: if (!infoFlowGraph.containsNode(returnRefEqVal))
088: infoFlowGraph.addNode(returnRefEqVal);
089:
090: if (printMessages)
091: G.v().out.println("STARTING ANALYSIS FOR "
092: + g.getBody().getMethod() + " -----");
093: doFlowInsensitiveAnalysis();
094: if (printMessages)
095: G.v().out.println("ENDING ANALYSIS FOR "
096: + g.getBody().getMethod() + " -----");
097: }
098:
099: /** A constructor that doesn't run the analysis */
100: protected SimpleMethodInfoFlowAnalysis(UnitGraph g,
101: InfoFlowAnalysis dfa, boolean ignoreNonRefTypeFlow,
102: boolean dummyDontRunAnalysisYet) {
103: super (g);
104: this .sm = g.getBody().getMethod();
105: if (sm.isStatic())
106: this .this Local = null;
107: else
108: this .this Local = g.getBody().getThisLocal();
109: this .dfa = dfa;
110: this .refOnly = ignoreNonRefTypeFlow;
111:
112: this .infoFlowGraph = new MemoryEfficientGraph();
113: this .returnRef = new ParameterRef(g.getBody().getMethod()
114: .getReturnType(), -1); // it's a dummy parameter ref
115:
116: this .entrySet = new ArraySparseSet();
117: this .emptySet = new ArraySparseSet();
118:
119: printMessages = false;
120: }
121:
122: public void doFlowInsensitiveAnalysis() {
123: FlowSet fs = (FlowSet) newInitialFlow();
124: boolean flowSetChanged = true;
125: while (flowSetChanged) {
126: int sizebefore = fs.size();
127: Iterator stmtIt = graph.iterator();
128: while (stmtIt.hasNext()) {
129: Stmt s = (Stmt) stmtIt.next();
130: flowThrough(fs, s, fs);
131: }
132: if (fs.size() > sizebefore)
133: flowSetChanged = true;
134: else
135: flowSetChanged = false;
136: }
137: }
138:
139: public MutableDirectedGraph getMethodInfoFlowSummary() {
140: return infoFlowGraph;
141: }
142:
143: protected void merge(Object in1, Object in2, Object out) {
144: FlowSet inSet1 = (FlowSet) in1;
145: FlowSet inSet2 = (FlowSet) in2;
146: FlowSet outSet = (FlowSet) out;
147:
148: inSet1.union(inSet2, outSet);
149: }
150:
151: protected boolean isNonRefType(Type type) {
152: return !(type instanceof RefLikeType);
153: }
154:
155: protected boolean ignoreThisDataType(Type type) {
156: return refOnly && isNonRefType(type);
157: }
158:
159: // Interesting sources are summarized (and possibly printed)
160: public boolean isInterestingSource(Value source) {
161: return (source instanceof Ref);
162: }
163:
164: // Trackable sources are added to the flow set
165: public boolean isTrackableSource(Value source) {
166: return isInterestingSource(source) || (source instanceof Ref);
167: }
168:
169: // Interesting sinks are possibly printed
170: public boolean isInterestingSink(Value sink) {
171: return (sink instanceof Ref);
172: }
173:
174: // Trackable sinks are added to the flow set
175: public boolean isTrackableSink(Value sink) {
176: return isInterestingSink(sink) || (sink instanceof Ref)
177: || (sink instanceof Local);
178: }
179:
180: private ArrayList<Value> getDirectSources(Value v, FlowSet fs) {
181: ArrayList<Value> ret = new ArrayList<Value>(); // of "interesting sources"
182: EquivalentValue vEqVal = new CachedEquivalentValue(v);
183: Iterator fsIt = fs.iterator();
184: while (fsIt.hasNext()) {
185: Pair pair = (Pair) fsIt.next();
186: if (pair.getO1().equals(vEqVal))
187: ret.add(((EquivalentValue) pair.getO2()).getValue());
188: }
189: return ret;
190: }
191:
192: // For when data flows to a local
193: protected void handleFlowsToValue(Value sink, Value initialSource,
194: FlowSet fs) {
195: if (!isTrackableSink(sink))
196: return;
197:
198: List<Value> sources = getDirectSources(initialSource, fs); // list of Refs... returns all other sources
199: if (isTrackableSource(initialSource))
200: sources.add(initialSource);
201: Iterator<Value> sourcesIt = sources.iterator();
202: while (sourcesIt.hasNext()) {
203: Value source = sourcesIt.next();
204: EquivalentValue sinkEqVal = new CachedEquivalentValue(sink);
205: EquivalentValue sourceEqVal = new CachedEquivalentValue(
206: source);
207: if (sinkEqVal.equals(sourceEqVal))
208: continue;
209: Pair pair = new Pair(sinkEqVal, sourceEqVal);
210: if (!fs.contains(pair)) {
211: fs.add(pair);
212: if (isInterestingSource(source)
213: && isInterestingSink(sink)) {
214: if (!infoFlowGraph.containsNode(sinkEqVal))
215: infoFlowGraph.addNode(sinkEqVal);
216: if (!infoFlowGraph.containsNode(sourceEqVal))
217: infoFlowGraph.addNode(sourceEqVal);
218: infoFlowGraph.addEdge(sourceEqVal, sinkEqVal);
219: if (printMessages)
220: G.v().out.println(" Found " + source
221: + " flows to " + sink);
222: }
223: }
224: }
225: }
226:
227: // for when data flows to the data structure pointed to by a local
228: protected void handleFlowsToDataStructure(Value base,
229: Value initialSource, FlowSet fs) {
230: List<Value> sinks = getDirectSources(base, fs);
231: if (isTrackableSink(base))
232: sinks.add(base);
233: List<Value> sources = getDirectSources(initialSource, fs);
234: if (isTrackableSource(initialSource))
235: sources.add(initialSource);
236: Iterator<Value> sourcesIt = sources.iterator();
237: while (sourcesIt.hasNext()) {
238: Value source = sourcesIt.next();
239: EquivalentValue sourceEqVal = new CachedEquivalentValue(
240: source);
241: Iterator<Value> sinksIt = sinks.iterator();
242: while (sinksIt.hasNext()) {
243: Value sink = sinksIt.next();
244: if (!isTrackableSink(sink))
245: continue;
246: EquivalentValue sinkEqVal = new CachedEquivalentValue(
247: sink);
248: if (sinkEqVal.equals(sourceEqVal))
249: continue;
250: Pair pair = new Pair(sinkEqVal, sourceEqVal);
251: if (!fs.contains(pair)) {
252: fs.add(pair);
253: if (isInterestingSource(source)
254: && isInterestingSink(sink)) {
255: if (!infoFlowGraph.containsNode(sinkEqVal))
256: infoFlowGraph.addNode(sinkEqVal);
257: if (!infoFlowGraph.containsNode(sourceEqVal))
258: infoFlowGraph.addNode(sourceEqVal);
259: infoFlowGraph.addEdge(sourceEqVal, sinkEqVal);
260: if (printMessages)
261: G.v().out.println(" Found " + source
262: + " flows to " + sink);
263: }
264: }
265: }
266: }
267: }
268:
269: // handles the invoke expression AND returns a list of the return value's sources
270: // for each node
271: // if the node is a parameter
272: // source = argument <Immediate>
273: // if the node is a static field
274: // source = node <StaticFieldRef>
275: // if the node is a field
276: // source = receiver object <Local>
277: // if the node is the return value
278: // continue
279:
280: // for each sink
281: // if the sink is a parameter
282: // handleFlowsToDataStructure(sink, source, fs)
283: // if the sink is a static field
284: // handleFlowsToValue(sink, source, fs)
285: // if the sink is a field
286: // handleFlowsToDataStructure(receiver object, source, fs)
287: // if the sink is the return value
288: // add node to list of return value sources
289:
290: protected List handleInvokeExpr(InvokeExpr ie, FlowSet fs) {
291: // get the data flow graph
292: MutableDirectedGraph dataFlowGraph = dfa
293: .getInvokeInfoFlowSummary(ie, sm); // must return a graph whose nodes are Refs!!!
294: // if( ie.getMethodRef().resolve().getSubSignature().equals(new String("boolean remove(java.lang.Object)")) )
295: // {
296: // G.v().out.println("*!*!*!*!*!<boolean remove(java.lang.Object)> has FLOW SENSITIVE infoFlowGraph: ");
297: // ClassInfoFlowAnalysis.printDataFlowGraph(infoFlowGraph);
298: // }
299:
300: List returnValueSources = new ArrayList();
301:
302: Iterator<Object> nodeIt = dataFlowGraph.getNodes().iterator();
303: while (nodeIt.hasNext()) {
304: EquivalentValue nodeEqVal = (EquivalentValue) nodeIt.next();
305:
306: if (!(nodeEqVal.getValue() instanceof Ref))
307: throw new RuntimeException(
308: "Illegal node type in data flow graph:"
309: + nodeEqVal.getValue()
310: + " should be an object of type Ref.");
311:
312: Ref node = (Ref) nodeEqVal.getValue();
313:
314: Value source = null;
315:
316: if (node instanceof ParameterRef) {
317: ParameterRef param = (ParameterRef) node;
318: if (param.getIndex() == -1)
319: continue;
320: source = ie.getArg(param.getIndex()); // Immediate
321: } else if (node instanceof StaticFieldRef) {
322: source = node; // StaticFieldRef
323: } else if (ie instanceof InstanceInvokeExpr
324: && node instanceof InstanceFieldRef) {
325: InstanceInvokeExpr iie = (InstanceInvokeExpr) ie;
326: source = iie.getBase(); // Local
327: }
328:
329: Iterator sinksIt = dataFlowGraph.getSuccsOf(nodeEqVal)
330: .iterator();
331: while (sinksIt.hasNext()) {
332: EquivalentValue sinkEqVal = (EquivalentValue) sinksIt
333: .next();
334: Ref sink = (Ref) sinkEqVal.getValue();
335: if (sink instanceof ParameterRef) {
336: ParameterRef param = (ParameterRef) sink;
337: if (param.getIndex() == -1) {
338: returnValueSources.add(source);
339: } else {
340: handleFlowsToDataStructure(ie.getArg(param
341: .getIndex()), source, fs);
342: }
343: } else if (sink instanceof StaticFieldRef) {
344: handleFlowsToValue(sink, source, fs);
345: } else if (ie instanceof InstanceInvokeExpr
346: && sink instanceof InstanceFieldRef) {
347: InstanceInvokeExpr iie = (InstanceInvokeExpr) ie;
348: handleFlowsToDataStructure(iie.getBase(), source,
349: fs);
350: }
351: }
352: }
353:
354: // return the list of return value sources
355: return returnValueSources;
356: }
357:
358: protected void flowThrough(Object inValue, Object unit,
359: Object outValue) {
360: FlowSet in = (FlowSet) inValue;
361: FlowSet out = (FlowSet) outValue;
362: Stmt stmt = (Stmt) unit;
363:
364: if (in != out) // this method is reused for flow insensitive analysis, which uses the same FlowSet for in and out
365: in.copy(out);
366: FlowSet changedFlow = out;
367:
368: // Calculate the minimum subset of the flow set that we need to consider - OBSELETE optimization
369: // FlowSet changedFlow = new ArraySparseSet();
370: // FlowSet oldFlow = new ArraySparseSet();
371: // out.copy(oldFlow);
372: // in.union(out, out);
373: // out.difference(oldFlow, changedFlow);
374:
375: /*
376: Iterator changedFlowIt = changedFlow.iterator();
377: while(changedFlowIt.hasNext())
378: {
379: Pair pair = (Pair) changedFlowIt.next();
380: EquivalentValue defEqVal = (EquivalentValue) pair.getO1();
381: Value def = defEqVal.getValue();
382: boolean defIsUsed = false;
383: Iterator usesIt = stmt.getUseBoxes().iterator();
384: while(usesIt.hasNext())
385: {
386: Value use = ((ValueBox) usesIt.next()).getValue();
387: if(use.equivTo(def))
388: defIsUsed = true;
389: }
390: if(!defIsUsed)
391: changedFlow.remove(pair);
392: }
393: */
394:
395: // Bail out if there's nothing to consider, unless this might be the first run
396: // if(changedFlow.isEmpty() && !oldFlow.equals(emptySet))
397: // return;
398:
399: if (stmt instanceof IdentityStmt) // assigns an IdentityRef to a Local
400: {
401: IdentityStmt is = (IdentityStmt) stmt;
402: IdentityRef ir = (IdentityRef) is.getRightOp();
403:
404: if (ir instanceof JCaughtExceptionRef) {
405: // TODO: What the heck do we do with this???
406: } else if (ir instanceof ParameterRef) {
407: if (!ignoreThisDataType(ir.getType())) {
408: // <Local, ParameterRef and sources>
409: handleFlowsToValue(is.getLeftOp(), ir, changedFlow);
410: }
411: } else if (ir instanceof ThisRef) {
412: if (!ignoreThisDataType(ir.getType())) {
413: // <Local, ThisRef and sources>
414: handleFlowsToValue(is.getLeftOp(), ir, changedFlow);
415: }
416: }
417: } else if (stmt instanceof ReturnStmt) // assigns an Immediate to the "returnRef"
418: {
419: ReturnStmt rs = (ReturnStmt) stmt;
420: Value rv = rs.getOp();
421: if (rv instanceof Constant) {
422: // No (interesting) data flow
423: } else if (rv instanceof Local) {
424: if (!ignoreThisDataType(rv.getType())) {
425: // <ReturnRef, sources of Local>
426: handleFlowsToValue(returnRef, rv, changedFlow);
427: }
428: }
429: } else if (stmt instanceof AssignStmt) // assigns a Value to a Variable
430: {
431: AssignStmt as = (AssignStmt) stmt;
432: Value lv = as.getLeftOp();
433: Value rv = as.getRightOp();
434:
435: Value sink = null;
436: boolean flowsToDataStructure = false;
437:
438: if (lv instanceof Local) // data flows into the Local
439: {
440: sink = lv;
441: } else if (lv instanceof ArrayRef) // data flows into the base's data structure
442: {
443: ArrayRef ar = (ArrayRef) lv;
444: sink = ar.getBase();
445: flowsToDataStructure = true;
446: } else if (lv instanceof StaticFieldRef) // data flows into the field ref
447: {
448: sink = lv;
449: } else if (lv instanceof InstanceFieldRef) {
450: InstanceFieldRef ifr = (InstanceFieldRef) lv;
451: if (ifr.getBase() == this Local) // data flows into the field ref
452: {
453: sink = lv;
454: } else // data flows into the base's data structure
455: {
456: sink = ifr.getBase();
457: flowsToDataStructure = true;
458: }
459: }
460:
461: List sources = new ArrayList();
462: boolean interestingFlow = true;
463:
464: if (rv instanceof Local) {
465: sources.add(rv);
466: interestingFlow = !ignoreThisDataType(rv.getType());
467: } else if (rv instanceof Constant) {
468: sources.add(rv);
469: interestingFlow = !ignoreThisDataType(rv.getType());
470: } else if (rv instanceof ArrayRef) // data flows from the base's data structure
471: {
472: ArrayRef ar = (ArrayRef) rv;
473: sources.add(ar.getBase());
474: interestingFlow = !ignoreThisDataType(ar.getType());
475: } else if (rv instanceof StaticFieldRef) {
476: sources.add(rv);
477: interestingFlow = !ignoreThisDataType(rv.getType());
478: } else if (rv instanceof InstanceFieldRef) {
479: InstanceFieldRef ifr = (InstanceFieldRef) rv;
480: if (ifr.getBase() == this Local) // data flows from the field ref
481: {
482: sources.add(rv);
483: interestingFlow = !ignoreThisDataType(rv.getType());
484: } else // data flows from the base's data structure
485: {
486: sources.add(ifr.getBase());
487: interestingFlow = !ignoreThisDataType(ifr.getType());
488: }
489: } else if (rv instanceof AnyNewExpr) {
490: sources.add(rv);
491: interestingFlow = !ignoreThisDataType(rv.getType());
492: } else if (rv instanceof BinopExpr) {
493: BinopExpr be = (BinopExpr) rv;
494: sources.add(be.getOp1());
495: sources.add(be.getOp2());
496: interestingFlow = !ignoreThisDataType(be.getType());
497: } else if (rv instanceof CastExpr) {
498: CastExpr ce = (CastExpr) rv;
499: sources.add(ce.getOp());
500: interestingFlow = !ignoreThisDataType(ce.getType());
501: } else if (rv instanceof InstanceOfExpr) {
502: InstanceOfExpr ioe = (InstanceOfExpr) rv;
503: sources.add(ioe.getOp());
504: interestingFlow = !ignoreThisDataType(ioe.getType());
505: } else if (rv instanceof UnopExpr) {
506: UnopExpr ue = (UnopExpr) rv;
507: sources.add(ue.getOp());
508: interestingFlow = !ignoreThisDataType(ue.getType());
509: } else if (rv instanceof InvokeExpr) {
510: InvokeExpr ie = (InvokeExpr) rv;
511: sources.addAll(handleInvokeExpr(ie, changedFlow));
512: interestingFlow = !ignoreThisDataType(ie.getType());
513: }
514:
515: if (interestingFlow) {
516: if (flowsToDataStructure) {
517: Iterator sourcesIt = sources.iterator();
518: while (sourcesIt.hasNext()) {
519: Value source = (Value) sourcesIt.next();
520: handleFlowsToDataStructure(sink, source,
521: changedFlow);
522: }
523: } else {
524: Iterator sourcesIt = sources.iterator();
525: while (sourcesIt.hasNext()) {
526: Value source = (Value) sourcesIt.next();
527: handleFlowsToValue(sink, source, changedFlow);
528: }
529: }
530: }
531: } else if (stmt.containsInvokeExpr()) // flows data between receiver object, parameters, globals, and return value
532: {
533: handleInvokeExpr(stmt.getInvokeExpr(), changedFlow);
534: }
535:
536: // changedFlow.union(out, out); - OBSELETE optimization
537: }
538:
539: protected void copy(Object source, Object dest) {
540:
541: FlowSet sourceSet = (FlowSet) source;
542: FlowSet destSet = (FlowSet) dest;
543:
544: sourceSet.copy(destSet);
545:
546: }
547:
548: protected Object entryInitialFlow() {
549: return entrySet.clone();
550: }
551:
552: protected Object newInitialFlow() {
553: return emptySet.clone();
554: }
555:
556: public void addToEntryInitialFlow(Value source, Value sink) {
557: EquivalentValue sinkEqVal = new CachedEquivalentValue(sink);
558: EquivalentValue sourceEqVal = new CachedEquivalentValue(source);
559: if (sinkEqVal.equals(sourceEqVal))
560: return;
561: Pair pair = new Pair(sinkEqVal, sourceEqVal);
562: if (!entrySet.contains(pair)) {
563: entrySet.add(pair);
564: }
565: }
566:
567: public void addToNewInitialFlow(Value source, Value sink) {
568: EquivalentValue sinkEqVal = new CachedEquivalentValue(sink);
569: EquivalentValue sourceEqVal = new CachedEquivalentValue(source);
570: if (sinkEqVal.equals(sourceEqVal))
571: return;
572: Pair pair = new Pair(sinkEqVal, sourceEqVal);
573: if (!emptySet.contains(pair)) {
574: emptySet.add(pair);
575: }
576: }
577:
578: public Value getThisLocal() {
579: return thisLocal;
580: }
581: }
|