Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  package soot.jimple.toolkits.infoflow;
  
  import soot.*;
  
  import java.util.*;
  import soot.jimple.*;
  
 // SimpleMethodInfoFlowAnalysis written by Richard L. Halpert, 2007-02-25
 // Constructs a data flow table for the given method.  Ignores indirect flow.
 // These tables conservatively approximate how data flows from parameters,
 // fields, and globals to parameters, fields, globals, and the return value.
 // Note that a ref-type parameter (or field or global) might allow access to a
 // large data structure, but that entire structure will be represented only by
 // the parameter's one node in the data flow graph.
 
 {
 	boolean refOnly// determines if primitive type data flow is included
 	boolean includeInnerFields// determines if flow to a field of an object (other than this) is treated like flow to that object
 	
 	
 	boolean printMessages;
 	
 	public static int counter = 0;
 	
 	{
 		 = g;
 		this. = g.getBody().getMethod();
 		if(.isStatic())
 			this. = null;
 		else
 			this. = g.getBody().getThisLocal();
 		this. = dfa;
 		
 		
 		this. = new ParameterRef(g.getBody().getMethod().getReturnType(), -1); // it's a dummy parameter ref
 		
 //		this.entrySet = new ArraySparseSet();
 //		this.emptySet = new ArraySparseSet();
 		
 		 = false//dfa.printDebug();
 		
 		++;
 		
 		// Add all of the nodes necessary to ensure that this is a complete data flow graph
 		
 		// Add every parameter of this method
 		for(int i = 0; i < .getParameterCount(); i++)
 		{
 			EquivalentValue parameterRefEqVal = InfoFlowAnalysis.getNodeForParameterRef(i);
 			if(!.containsNode(parameterRefEqVal))
 				.addNode(parameterRefEqVal);
 		}
 		
 		// Add every relevant field of this class (static methods don't get non-static fields)
 		for(Iterator it = .getDeclaringClass().getFields().iterator(); it.hasNext(); )
 		{
 			SootField sf = (SootFieldit.next();
 			if(sf.isStatic() || !.isStatic())
 			{
 				EquivalentValue fieldRefEqVal;
 				if(!.isStatic())
 					fieldRefEqVal = InfoFlowAnalysis.getNodeForFieldRef(sf.retrieveActiveBody().getThisLocal());
 				else
 					fieldRefEqVal = InfoFlowAnalysis.getNodeForFieldRef(sf);
 					
 				if(!.containsNode(fieldRefEqVal))
 					.addNode(fieldRefEqVal);
 			}
 		}
 		
 		// Add every field of this class's superclasses
 		SootClass superclass = .getDeclaringClass();
 		if(superclass.hasSuperclass())
 			superclass = .getDeclaringClass().getSuperclass();
 		while(superclass.hasSuperclass()) // we don't want to process Object
 		{
 	        Iterator scFieldsIt = superclass.getFields().iterator();
 	        while(scFieldsIt.hasNext())
 	        {
 				SootField scField = (SootFieldscFieldsIt.next();
 				if(scField.isStatic() || !.isStatic())
 				{
 					EquivalentValue fieldRefEqVal;
 					if(!.isStatic())
						fieldRefEqVal = InfoFlowAnalysis.getNodeForFieldRef(scField.retrieveActiveBody().getThisLocal());
					else
						fieldRefEqVal = InfoFlowAnalysis.getNodeForFieldRef(scField);
					if(!.containsNode(fieldRefEqVal))
						.addNode(fieldRefEqVal);
				}
	        }
			superclass = superclass.getSuperclass();
		}
		// Add thisref of this class
		if(!.isStatic())
		{
			EquivalentValue thisRefEqVal = InfoFlowAnalysis.getNodeForThisRef();
			if(!.containsNode(thisRefEqVal))
				.addNode(thisRefEqVal);
		}
		// Add returnref of this method
		if(.getType() != VoidType.v() && !.containsNode(returnRefEqVal))
			.addNode(returnRefEqVal);
		// Do the analysis
		Date start = new Date();
		int counterSoFar = ;
			G.v()..println("STARTING SMART ANALYSIS FOR " + g.getBody().getMethod() + " -----");
		// S=#Statements, R=#Refs, L=#Locals, where generally (S ~= L), (L >> R)
		// Generates a data flow graph of refs and locals where "flows to data structure" is represented in a single node
		// Generates a data flow graph of refs where "flows to data structure" has been resolved
		generateInfoFlowSummary(); // O( R*(L+R) )
		{
	    	long longTime = ((new Date()).getTime() - start.getTime());
	    	float time = (longTime) / 1000.0f;
			G.v()..println("ENDING   SMART ANALYSIS FOR " + g.getBody().getMethod() + " ----- " + 
								( - counterSoFar + 1) + " analyses took: " + time + "s");
			G.v()..println("  AbbreviatedDataFlowGraph:");
			G.v()..println("  DataFlowSummary:");
		}
	}
	{
		Iterator stmtIt = .iterator();
		while(stmtIt.hasNext())
		{
			Stmt s = (StmtstmtIt.next();
		}
	}
	{
		while(nodeIt.hasNext())
		{
			EquivalentValue node = (EquivalentValuenodeIt.next();
			List<EquivalentValuesources = sourcesOf(node);
			Iterator<EquivalentValuesourcesIt = sources.iterator();
			while(sourcesIt.hasNext())
			{
				EquivalentValue source = sourcesIt.next();
				if(source.getValue() instanceof Ref)
				{
					.addEdge(sourcenode);
				}
			}
		}
	}
	public List<EquivalentValuesourcesOf(EquivalentValue node) { return sourcesOf(nodenew HashSet<EquivalentValue>(), new HashSet<EquivalentValue>()); }
	private List<EquivalentValuesourcesOf(EquivalentValue nodeSet<EquivalentValuevisitedSourcesSet<EquivalentValuevisitedSinks)
	{
		visitedSources.add(node);
			return ret;
		// get direct sources
		Iterator predsIt = preds.iterator();
		while(predsIt.hasNext())
		{
			EquivalentValue pred = (EquivalentValuepredsIt.next();
			if(!visitedSources.contains(pred))
			{
				ret.add(pred);
				ret.addAll(sourcesOf(predvisitedSourcesvisitedSinks));
			}
		}
		// get sources of (sources of sinks, of which we are one)
		List<EquivalentValuesinks = sinksOf(nodevisitedSourcesvisitedSinks);
		Iterator<EquivalentValuesinksIt = sinks.iterator();
		while(sinksIt.hasNext())
		{
			EquivalentValue sink = sinksIt.next();
			if(!visitedSources.contains(sink))
			{
				EquivalentValue flowsToSourcesOf = new CachedEquivalentValue(new AbstractDataSource(sink.getValue()));
				if.getPredsOfAsSet(sink).contains(flowsToSourcesOf) )
				{
					ret.addAll(sourcesOf(flowsToSourcesOfvisitedSourcesvisitedSinks));
				}
			}
		}
		return ret;
	}
	public List<EquivalentValuesinksOf(EquivalentValue node) { return sinksOf(nodenew HashSet<EquivalentValue>(), new HashSet<EquivalentValue>()); }
	private List<EquivalentValuesinksOf(EquivalentValue nodeSet<EquivalentValuevisitedSourcesSet<EquivalentValuevisitedSinks)
	{
//		if(visitedSinks.contains(node))
//			return ret;
		visitedSinks.add(node);
			return ret;
		// get direct sinks
		Iterator succsIt = succs.iterator();
		while(succsIt.hasNext())
		{
			EquivalentValue succ = (EquivalentValuesuccsIt.next();
			if(!visitedSinks.contains(succ))
			{
				ret.add(succ);
				ret.addAll(sinksOf(succvisitedSourcesvisitedSinks));
			}
		}
		// get sources of (sources of sinks, of which we are one)
		succsIt = succs.iterator();
		while(succsIt.hasNext())
		{
			EquivalentValue succ = (EquivalentValuesuccsIt.next();
			if(succ.getValue() instanceof AbstractDataSource)
			{
				// It will have ONE successor, who will be the value whose sources it represents
				EquivalentValue v = (EquivalentValuevHolder.iterator().next(); // get the one and only
				if(!visitedSinks.contains(v))
				{
//					Set<EquivalentValue> 
					ret.addAll(sourcesOf(vvisitedSinksvisitedSinks)); // these nodes are really to be marked as sinks, not sources
				}
			}
		}
		return ret;
	}
	{
	}
	{
	}
	protected boolean isNonRefType(Type type)
	{
		return !(type instanceof RefLikeType);
	}
	protected boolean ignoreThisDataType(Type type)
	{
		return  && isNonRefType(type);
	}
	// For when data flows to a local
	protected void handleFlowsToValue(Value sinkValue source)
	{
		EquivalentValue sinkEqVal;
		EquivalentValue sourceEqVal;
		if(sink instanceof InstanceFieldRef)
		{
			sinkEqVal = InfoFlowAnalysis.getNodeForFieldRef(ifr.getField(), (Localifr.getBase()); // deals with inner fields
		}
		else
			sinkEqVal = new CachedEquivalentValue(sink);
		if(source instanceof InstanceFieldRef)
		{
			sourceEqVal = InfoFlowAnalysis.getNodeForFieldRef(ifr.getField(), (Localifr.getBase()); // deals with inner fields
		}
		else
			sourceEqVal = new CachedEquivalentValue(source);
		ifsource instanceof Ref && !.containsNode(sourceEqVal))
		ifsink instanceof Ref && !.containsNode(sinkEqVal))
		.addEdge(sourceEqValsinkEqVal);
	}
	// for when data flows to the data structure pointed to by a local
	protected void handleFlowsToDataStructure(Value baseValue source)
	{
		EquivalentValue sourcesOfBaseEqVal = new CachedEquivalentValue(new AbstractDataSource(base));
		EquivalentValue baseEqVal = new CachedEquivalentValue(base);
		EquivalentValue sourceEqVal;
		if(source instanceof InstanceFieldRef)
		{
			sourceEqVal = InfoFlowAnalysis.getNodeForFieldRef(ifr.getField(), (Localifr.getBase()); // deals with inner fields
		}
		else
			sourceEqVal = new CachedEquivalentValue(source);
		ifsource instanceof Ref && !.containsNode(sourceEqVal))
		if(!.containsNode(sourcesOfBaseEqVal))
			.addNode(sourcesOfBaseEqVal);
		.addEdge(sourceEqValsourcesOfBaseEqVal);
		.addEdge(sourcesOfBaseEqValbaseEqVal); // for convenience
	}
	// For inner fields... we have base flow to field as a service specifically
	// for the sake of LocalObjects... yes, this is a hack!
	protected void handleInnerField(Value innerFieldRef)
	{
/*
		InstanceFieldRef ifr = (InstanceFieldRef) innerFieldRef;
		EquivalentValue baseEqVal = new CachedEquivalentValue(ifr.getBase());
		EquivalentValue fieldRefEqVal = dfa.getEquivalentValueFieldRef(sm, ifr.getField()); // deals with inner fields
		if(!abbreviatedInfoFlowGraph.containsNode(baseEqVal))
			abbreviatedInfoFlowGraph.addNode(baseEqVal);
		if(!abbreviatedInfoFlowGraph.containsNode(fieldRefEqVal))
			abbreviatedInfoFlowGraph.addNode(fieldRefEqVal);
		abbreviatedInfoFlowGraph.addEdge(baseEqVal, fieldRefEqVal);
*/
	}
	// handles the invoke expression AND returns a list of the return value's sources
		// for each node
			// if the node is a parameter
				// source = argument <Immediate>
			// if the node is a static field
				// source = node <StaticFieldRef>
			// if the node is a field
				// source = receiver object <Local>
			// if the node is the return value
				// continue
			// for each sink
				// if the sink is a parameter
					// handleFlowsToDataStructure(sink, source, fs)
				// if the sink is a static field
					// handleFlowsToValue(sink, source, fs)
				// if the sink is a field
					// handleFlowsToDataStructure(receiver object, source, fs)
				// if the sink is the return value
					// add node to list of return value sources
	protected List handleInvokeExpr(InvokeExpr ieStmt is)
	{
		// get the data flow graph
		HashMutableDirectedGraph dataFlowSummary = .getInvokeInfoFlowSummary(ieis); // must return a graph whose nodes are Refs!!!
		if(false// DEBUG!!!
		{
			SootMethod method = ie.getMethodRef().resolve();
			{
				G.v()..println("Attempting to print graph (will succeed only if ./dfg/ is a valid path)");
				MutableDirectedGraph abbreviatedDataFlowGraph = .getInvokeAbbreviatedInfoFlowGraph(ie);
				InfoFlowAnalysis.printGraphToDotFile("dfg/" + method.getDeclaringClass().getShortName() + "_" + method.getName() + ( ? "" : "_primitive"), 
					abbreviatedDataFlowGraphmethod.getName() + ( ? "" : "_primitive"), false);
			}
		}
//		if( ie.getMethodRef().resolve().getSubSignature().equals(new String("boolean remove(java.lang.Object)")) )
//		{
//			G.v().out.println("*!*!*!*!*!<boolean remove(java.lang.Object)> has FLOW SENSITIVE infoFlowSummary: ");
//			ClassInfoFlowAnalysis.printDataFlowGraph(infoFlowSummary);
//		}
		List returnValueSources = new ArrayList();
		Iterator<ObjectnodeIt = dataFlowSummary.getNodes().iterator();
		while(nodeIt.hasNext())
		{
			EquivalentValue nodeEqVal = (EquivalentValuenodeIt.next();
			if(!(nodeEqVal.getValue() instanceof Ref))
				throw new RuntimeException("Illegal node type in data flow summary:" + nodeEqVal.getValue() + " should be an object of type Ref.");
			Ref node = (RefnodeEqVal.getValue();
			List sources = new ArrayList();
//			Value source = null;
			if(node instanceof ParameterRef)
			{
				ParameterRef param = (ParameterRefnode;
				if(param.getIndex() == -1)
					continue;
				sources.add(ie.getArg(param.getIndex()));
//				source = ; // Immediate
			}
			else if(node instanceof StaticFieldRef)
			{
				sources.add(node);
//				source = node; // StaticFieldRef
			}
			else if(node instanceof InstanceFieldRef && ie instanceof InstanceInvokeExpr)
			{
				if(iie.getBase() == )
				{
					sources.add(node);
//					source = node;
				}
				{
					iffalse ) // isNonRefType(node.getType()) ) // TODO: double check this policy
					{
						// primitives flow from the parent object
						if(ifr.getBase() instanceof FakeJimpleLocal)// && ((FakeJimpleLocal) ifr.getBase()).getRealLocal() != null)
// sources.add(((FakeJimpleLocal) ifr.getBase()).getRealLocal());
						else
							sources.add(ifr.getBase());
					}
					else
					{
						// objects flow from both
						if(ifr.getBase() instanceof FakeJimpleLocal)// && ((FakeJimpleLocal) ifr.getBase()).getRealLocal() != null)
// sources.add(((FakeJimpleLocal) ifr.getBase()).getRealLocal());
						else
							sources.add(ifr.getBase());
						sources.add(node);
					}
//					source = node;
//					handleInnerField(source);
				}
				else
				{
					sources.add(iie.getBase());
//					source = iie.getBase(); // Local
				}
			}
			else if(node instanceof InstanceFieldRef && )
			{
				iffalse ) // isNonRefType(node.getType()) ) // TODO: double check this policy
				{
					// primitives flow from the parent object
					if(ifr.getBase() instanceof FakeJimpleLocal)// && ((FakeJimpleLocal) ifr.getBase()).getRealLocal() != null)
// sources.add(((FakeJimpleLocal) ifr.getBase()).getRealLocal());
					else
						sources.add(ifr.getBase());
				}
				else
				{
					// objects flow from both
					if(ifr.getBase() instanceof FakeJimpleLocal)// && ((FakeJimpleLocal) ifr.getBase()).getRealLocal() != null)
// sources.add(((FakeJimpleLocal) ifr.getBase()).getRealLocal());
					else
						sources.add(ifr.getBase());
					sources.add(node);
				}
//				source = node;
//				handleInnerField(source);
			}
			else if(node instanceof ThisRef && ie instanceof InstanceInvokeExpr)
			{
				sources.add(iie.getBase());
//				source = iie.getBase(); // Local
			}
			else
			{
				throw new RuntimeException("Unknown Node Type in Data Flow Graph: node " + node + " in InvokeExpr " + ie);
			}
			Iterator sinksIt = dataFlowSummary.getSuccsOfAsSet(nodeEqVal).iterator();
			while(sinksIt.hasNext())
			{
				EquivalentValue sinkEqVal = (EquivalentValuesinksIt.next();
				Ref sink = (RefsinkEqVal.getValue();
				if(sink instanceof ParameterRef)
				{
					ParameterRef param = (ParameterRefsink;
					if(param.getIndex() == -1)
					{
						returnValueSources.addAll(sources);
					}
					else
					{
						for(Iterator sourcesIt = sources.iterator(); sourcesIt.hasNext(); )
						{
							Value source = (ValuesourcesIt.next();
						}
					}
				}
				else if(sink instanceof StaticFieldRef)
				{
					for(Iterator sourcesIt = sources.iterator(); sourcesIt.hasNext(); )
					{
						Value source = (ValuesourcesIt.next();
						handleFlowsToValue(sinksource);
					}
				}
				else if(sink instanceof InstanceFieldRef && ie instanceof InstanceInvokeExpr)
				{
					if(iie.getBase() == )
					{
						for(Iterator sourcesIt = sources.iterator(); sourcesIt.hasNext(); )
						{
							Value source = (ValuesourcesIt.next();
							handleFlowsToValue(sinksource);
						}
					}
					{
						for(Iterator sourcesIt = sources.iterator(); sourcesIt.hasNext(); )
						{
							Value source = (ValuesourcesIt.next();
							iffalse ) // isNonRefType(sink.getType()) ) // TODO: double check this policy
							{
								// primitives flow to the parent object
								if(ifr.getBase() instanceof FakeJimpleLocal)// && ((FakeJimpleLocal) ifr.getBase()).getRealLocal() != null)
// handleFlowsToDataStructure(((FakeJimpleLocal) ifr.getBase()).getRealLocal(), source);
								else
							}
							else
							{
								// objects flow to the field
								handleFlowsToValue(sinksource);
							}
						}
					}
					else
					{
						for(Iterator sourcesIt = sources.iterator(); sourcesIt.hasNext(); )
						{
							Value source = (ValuesourcesIt.next();
						}
					}
				}
				else if(sink instanceof InstanceFieldRef && )
				{
					for(Iterator sourcesIt = sources.iterator(); sourcesIt.hasNext(); )
					{
						Value source = (ValuesourcesIt.next();
						iffalse ) // isNonRefType(sink.getType()) ) // TODO: double check this policy
						{
							// primitives flow to the parent object
							if(ifr.getBase() instanceof FakeJimpleLocal)// && ((FakeJimpleLocal) ifr.getBase()).getRealLocal() != null)
// handleFlowsToDataStructure(((FakeJimpleLocal) ifr.getBase()).getRealLocal(), source);
							else
						}
						else
						{
							handleFlowsToValue(sinksource);
						}
					}
				}
			}
		}
		// return the list of return value sources
		return returnValueSources;
	}
	protected void addFlowToCdfg(Stmt stmt)
	{
		if(stmt instanceof IdentityStmt// assigns an IdentityRef to a Local
		{
			IdentityStmt is = (IdentityStmtstmt;
			if(ir instanceof JCaughtExceptionRef)
			{
				// TODO: What the heck do we do with this???
			}
			else if(ir instanceof ParameterRef)
			{
				{
					// <Local, ParameterRef and sources>
				}
			}
			else if(ir instanceof ThisRef)
			{
				{
					// <Local, ThisRef and sources>
				}
			}
		}
		else if(stmt instanceof ReturnStmt// assigns an Immediate to the "returnRef"
		{
			ReturnStmt rs = (ReturnStmtstmt;
			Value rv = rs.getOp();
			if(rv instanceof Constant)
			{
				// No (interesting) data flow
			}
			else if(rv instanceof Local)
			{
				{
					// <ReturnRef, sources of Local>
				}
			}
		}
		else if(stmt instanceof AssignStmt// assigns a Value to a Variable
		{
			AssignStmt as = (AssignStmtstmt;
			Value lv = as.getLeftOp();
			Value rv = as.getRightOp();
			Value sink = null;
			boolean flowsToDataStructure = false;
			if(lv instanceof Local// data flows into the Local
			{
				sink = lv;
			}
			else if(lv instanceof ArrayRef// data flows into the base's data structure
			{
				ArrayRef ar = (ArrayReflv;
				sink = ar.getBase();
				flowsToDataStructure = true;
			}
			else if(lv instanceof StaticFieldRef// data flows into the field ref
			{
				sink = lv;
			}
			else if(lv instanceof InstanceFieldRef)
			{
				ififr.getBase() ==  ) // data flows into the field ref
				{
					sink = lv;
				}
				else if )
				{
					iffalse ) //isNonRefType(lv.getType()) ) // TODO: double check this policy
					{
						// primitives flow to the parent object
						sink = ifr.getBase();
						flowsToDataStructure = true;
					}
					else
					{
						// objects flow to the field
						sink = lv;
					}
				}
				else // data flows into the base's data structure
				{
					sink = ifr.getBase();
					flowsToDataStructure = true;
				}
			}
			List sources = new ArrayList();
			boolean interestingFlow = true;
			if(rv instanceof Local)
			{
				sources.add(rv);
				interestingFlow = !ignoreThisDataType(rv.getType());
			}
			else if(rv instanceof Constant)
			{
				sources.add(rv);
				interestingFlow = !ignoreThisDataType(rv.getType());
			}
			else if(rv instanceof ArrayRef// data flows from the base's data structure
			{
				ArrayRef ar = (ArrayRefrv;
				sources.add(ar.getBase());
				interestingFlow = !ignoreThisDataType(ar.getType());
			}
			else if(rv instanceof StaticFieldRef)
			{
				sources.add(rv);
				interestingFlow = !ignoreThisDataType(rv.getType());
			}
			else if(rv instanceof InstanceFieldRef)
			{
				ififr.getBase() ==  ) // data flows from the field ref
				{
					sources.add(rv);
					interestingFlow = !ignoreThisDataType(rv.getType());
				}
				else if )
				{
					iffalse ) // isNonRefType(rv.getType()) ) // TODO: double check this policy
					{
						// primitives flow from the parent object
						sources.add(ifr.getBase());
					}
					else
					{
						// objects flow from both
						sources.add(ifr.getBase());
						sources.add(rv);
					}
					interestingFlow = !ignoreThisDataType(rv.getType());
				}
				else // data flows from the base's data structure
				{
					sources.add(ifr.getBase());
					interestingFlow = !ignoreThisDataType(ifr.getType());
				}
			}
			else if(rv instanceof AnyNewExpr)
			{
				sources.add(rv);
				interestingFlow = !ignoreThisDataType(rv.getType());
			}
			else if(rv instanceof BinopExpr// does this include compares and others??? yes
			{
				BinopExpr be = (BinopExprrv;
				sources.add(be.getOp1());
				sources.add(be.getOp2());
				interestingFlow = !ignoreThisDataType(be.getType());
			}
			else if(rv instanceof CastExpr)
			{
				CastExpr ce = (CastExprrv;
				sources.add(ce.getOp());
				interestingFlow = !ignoreThisDataType(ce.getType());
			}
			else if(rv instanceof InstanceOfExpr)
			{
				sources.add(ioe.getOp());
				interestingFlow = !ignoreThisDataType(ioe.getType());
			}
			else if(rv instanceof UnopExpr)
			{
				UnopExpr ue = (UnopExprrv;
				sources.add(ue.getOp());
				interestingFlow = !ignoreThisDataType(ue.getType());
			}
			else if(rv instanceof InvokeExpr)
			{
				InvokeExpr ie = (InvokeExprrv;
				sources.addAll(handleInvokeExpr(ieas));
				interestingFlow = !ignoreThisDataType(ie.getType());
			}
			if(interestingFlow)
			{
				if(flowsToDataStructure)
				{
					Iterator sourcesIt = sources.iterator();
					while(sourcesIt.hasNext())
					{
						Value source = (ValuesourcesIt.next();
					}
				}
				else
				{
					Iterator sourcesIt = sources.iterator();
					while(sourcesIt.hasNext())
					{
						Value source = (ValuesourcesIt.next();
//						if(flowsToBoth && sink instanceof InstanceFieldRef)
//							handleFlowsToDataStructure(((InstanceFieldRef)sink).getBase(), source);
						handleFlowsToValue(sinksource);
					}
				}
			}
		}
		else if(stmt.containsInvokeExpr()) // flows data between receiver object, parameters, globals, and return value
		{
		}
	}
	{
		return ;
	}
New to GrepCode? Check out our FAQ X