private static void myDebug(String message) { logger.info("start debug... " + message); { CallGraph cg = Scene.v().getCallGraph(); Iterator<Edge> edges = cg .edgesOutOf(Scene .v() .getMethod( "<android.accounts.IAccountAuthenticatorResponse$Stub$Proxy: void onError(int,java.lang.String)>")); while (edges.hasNext()) { Edge e = edges.next(); logger.info("edge: " + e); } } logger.info("end debug... " + message); }
private void visit(Set<SootMethod> alreadyVisited, SootMethod current, int depth) { if (depth >= ConfigCHA.v().getGraphOutMaxDepth()) return; Iterator<Edge> it = cg.edgesOutOf(current); while (it.hasNext()) { Edge e = it.next(); SootMethod tgt = e.tgt(); for (int i=0; i < ConfigCHA.v().getGraphOutMaxDepth(); i++) { if (depth <= i) out.get(i).println(current+";"+tgt); } if (alreadyVisited.contains(tgt)) continue; alreadyVisited.add(tgt); visit(alreadyVisited, tgt, depth+1); } }
@Override public Collection<SootMethod> load(Unit u) throws Exception { ArrayList<SootMethod> res = null; //only retain callers that are explicit call sites or Thread.start() Iterator<Edge> edgeIter = new EdgeFilter().wrap(cg.edgesOutOf(u)); while(edgeIter.hasNext()) { Edge edge = edgeIter.next(); SootMethod m = edge.getTgt().method(); if(m.hasActiveBody()) { if (res == null) res = new ArrayList<SootMethod>(); res.add(m); } else if(IDESolver.DEBUG) System.err.println("Method "+m.getSignature()+" is referenced but has no body!"); } if (res != null) { res.trimToSize(); return res; } else return Collections.emptySet(); }
private List<SootMethod> findTargetMethods(Unit unit, CallGraph cg, boolean canBeNullList, boolean canBeNative){ List<SootMethod> target = new ArrayList<SootMethod>(); Iterator<Edge> it = cg.edgesOutOf(unit); while (it.hasNext()){ Edge edge = it.next(); SootMethod targetMethod = edge.tgt(); if (targetMethod.isNative() && !canBeNative ) continue; if (edge.kind() == Kind.CLINIT ) continue; target.add(targetMethod); } if (target.size() < 1 && !canBeNullList){ throw new RuntimeException("No target method for: "+unit); } return target; }
@Override public Collection <SootMethod> neighbours(SootMethod obj) { SootMethod m = (SootMethod) obj; Set <SootMethod> result = new HashSet <SootMethod>(); for (Iterator <Edge> it = cg.edgesOutOf(m); it.hasNext(); ) { Edge e = it.next(); // Do not consider spurious loops enabled by clinit. if (e.isClinit()) continue; if ((e.tgt().getName().equals("<init>")) && cba.isActive(e)) { Map<SootMethod, String> ir = cba.resolve(e); if (ir != null) { result.addAll(ir.keySet()); } } else result.add(e.getTgt().method()); } return result; }
/** * Auxiliary methods that taken a pointstoset representing a set * of objects origins and a method identifying as establishing a * link between origin objects and destination objects, gives * back an over-approximation of the set of destination methods * potentially linked to those origins objects * @param orig the set of origins abstracted as a pointstoset * @param lm the link method represented by the name of the * method and the position of the origin and destination * parameters in a call. * @return the destination objects abstracted as a pointstoset */ private PointsToSet resolveLinkThrough (PointsToSet orig, LinkMethod lm) { Iterator <Edge> ite = callgraph.edgesInto(lm.method); Union result = new MemoryEfficientRasUnion(); while(ite.hasNext()) { Edge inedge = ite.next(); InvokeExpr ie = inedge.srcStmt().getInvokeExpr(); if (ie != null) { PointsToSet ptFrom = getPointsTo(ie,lm.fromIndex); if(Union.hasNonEmptyIntersection(orig, ptFrom)) { PointsToSet ptTo = getPointsTo(ie,lm.toIndex); result.addAll(ptTo); } } } return result; }
/** * Gives the type of all the broadcast receiver that may be aborted. It looks at all the calls to abortBroadcast and through the Points-to analysis at the * actual class of the base arguments of the calls. * @return a set of soot type that may be empty. */ private Set<String> abortedBroadcastsTypes() { Set <String> result = new HashSet<String>(); try { SootClass receiverClass = scene.getSootClass(ANDROID_CONTENT_BROADCASTRECEIVER); SootMethod abortMethod = receiverClass.getMethod(BROADCAST_ABORT_SIGNATURE); Iterator<Edge> edges = cg.edgesInto(abortMethod); while(edges.hasNext()) { Edge edge = edges.next(); InvokeExpr ie = edge.srcStmt().getInvokeExpr(); if (ie == null || ! (ie instanceof InstanceInvokeExpr)) continue; Value base = ((InstanceInvokeExpr) ie).getBase(); if (!(base instanceof Local)) continue; PointsToSet basePTS = pag.reachingObjects((Local) base); addAll(result,basePTS.possibleTypes()); } } catch (RuntimeException e) { Out.getLog().println("Error while computing aborted broadcast " + e.getMessage()); } return result; }
public static boolean checkForPermission (Edge e, Set<String> mpSet, Stack<SootMethod> stack) { SootMethod src = e.getSrc().method(); // is in the stack SootMethod tgt = e.getTgt().method(); // is not in the stack String tgtS = tgt.getName(); if (!isCheckPermissionMethod(tgt)) return false; AnalysisType.v().start(); logger.info("check for permission: "+ e); // At this point we are sure that the target of the edge is a method // which checks Android permissions getStringFromMethod (stack, stack.size()-1, tgt, 0, mpSet); int mpSetSize = mpSet.size(); AnalysisType.v().cur().setNbrPermissions(mpSetSize); if (mpSetSize == 0) { logger.warn("WWWWWWWWW we could not find a perm string in "+ src); logger.warn(Util.printStack(stack)); // we add the UNKNOWN permisson mpSet.add(UNKNOWN_PERM); } AnalysisType.v().end(); return true; }
private boolean isInheritedMethod(Stmt stmt, String... classNames) { Iterator<Edge> edgeIt = Scene.v().getCallGraph().edgesOutOf(stmt); while (edgeIt.hasNext()) { Edge edge = edgeIt.next(); String targetClass = edge.getTgt().method().getDeclaringClass().getName(); for (String className : classNames) if (className.equals(targetClass)) return true; } return false; }
public Pair<Node, Node> addInterproceduralAssignment(Node from, Node to, Edge e) { Pair<Node, Node> val = new Pair<Node, Node>(from, to); if ( runGeomPTA ) { Set<Edge> sets = assign2edges.get(val); if ( sets == null ) { sets = new HashSet<Edge>(); assign2edges.put(val, sets); } sets.add(e); } return val; }
public static int countCallEdgesForCallsite(Stmt callsite, boolean stopForMutiple) { CallGraph cg = Scene.v().getCallGraph(); int count = 0; for ( Iterator<Edge> it = cg.edgesOutOf(callsite); it.hasNext(); ) { it.next(); ++count; if ( stopForMutiple && count > 1) break; } return count; }
/** * Searching the points-to results for field expression such as p.f. * * @param sootEdge * @param l * @param field * @param visitor * @return */ @SuppressWarnings("rawtypes") public boolean contextsByAnyCallEdge(Edge sootEdge, Local l, SparkField field, PtSensVisitor visitor) { Obj_full_extractor pts_l = new Obj_full_extractor(); if ( contexsByAnyCallEdge(sootEdge, l, pts_l) == false ) return false; visitor.prepare(); for ( IntervalContextVar icv : pts_l.outList ) { AllocNode obj = (AllocNode)icv.var; AllocDotField obj_f = geomPts.findAllocDotField(obj, field); if ( obj_f == null ) continue; IVarAbstraction objField = geomPts.findInternalNode(obj_f); if ( objField == null ) continue; long L = icv.L; long R = icv.R; assert L < R; objField.get_all_context_sensitive_objects(L, R, visitor); } pts_l = null; visitor.finish(); return visitor.numOfDiffObjects() != 0; }
/** * Standard K-CFA querying for field expression. * * @param callEdgeChain: callEdgeChain[0] is the farthest call edge in the chain. * @param l * @param field * @param visitor * @return */ @SuppressWarnings("rawtypes") public boolean contextByCallChain(Edge[] callEdgeChain, Local l, SparkField field, PtSensVisitor visitor) { // We first obtain the points-to information for l Obj_full_extractor pts_l = new Obj_full_extractor(); if ( contextsByCallChain(callEdgeChain, l, pts_l) == false ) return false; // We compute the points-to information for l.field visitor.prepare(); for ( IntervalContextVar icv : pts_l.outList ) { AllocNode obj = (AllocNode)icv.var; AllocDotField obj_f = geomPts.findAllocDotField(obj, field); if ( obj_f == null ) continue; IVarAbstraction objField = geomPts.findInternalNode(obj_f); if ( objField == null ) continue; long L = icv.L; long R = icv.R; assert L < R; objField.get_all_context_sensitive_objects(L, R, visitor); } pts_l = null; visitor.finish(); return visitor.numOfDiffObjects() != 0; }
/** * Data structures that only specific to geometric solver are created here. * The initialized container sizes are empirically chosen from the primes. * We believe most of the machine today can afford the memory overhead. */ private void prepareContainers() { // All kinds of variables consG = new HashMap<Node, IVarAbstraction>(39341); // Only the pointer variables pointers = new ZArrayNumberer<IVarAbstraction>(25771); // Only the heap variables allocations = new ZArrayNumberer<IVarAbstraction>(); // The constraints extracted from code constraints = new ZArrayNumberer<PlainConstraint>(25771); // The statements that fork a new thread thread_run_callsites = new HashSet<Stmt>(251); // The virtual callsites that have multiple call targets multiCallsites = new HashSet<Stmt>(251); // The fake virtual call edges created by SPARK // obsoletedEdges = new Vector<CgEdge>(4021); // A linkedlist used for traversing the call graph queue_cg = new LinkedList<Integer>(); // Containers for functions and call graph edges func2int = new HashMap<SootMethod, Integer>(5011); int2func = new HashMap<Integer, SootMethod>(5011); edgeMapping = new HashMap<Edge, CgEdge>(19763); consG.clear(); constraints.clear(); func2int.clear(); edgeMapping.clear(); }
protected HashMutableDirectedGraph<EquivalentValue> getInvokeInfoFlowSummary( InvokeExpr ie, Stmt is, SootMethod context) { // get the data flow graph for each possible target of ie, // then combine them conservatively and return the result. HashMutableDirectedGraph<EquivalentValue> ret = null; SootMethodRef methodRef = ie.getMethodRef(); String subSig = methodRef.resolve().getSubSignature(); CallGraph cg = Scene.v().getCallGraph(); for(Iterator<Edge> edges = cg.edgesOutOf(is); edges.hasNext();) { Edge e = edges.next(); SootMethod target = e.getTgt().method(); // Verify that this target is an implementation of the method we intend to call, // and not just a class initializer or other unintended control flow. if(target.getSubSignature().equals(subSig)) { HashMutableDirectedGraph<EquivalentValue> ifs = getMethodInfoFlowSummary( target, context.getDeclaringClass().isApplicationClass()); if(ret == null) ret = ifs; else { for(EquivalentValue node : ifs.getNodes()) { if(!ret.containsNode(node)) ret.addNode(node); for(EquivalentValue succ : ifs.getSuccsOf(node)) ret.addEdge(node, succ); } } } } return ret; // return getMethodInfoFlowSummary(methodRef.resolve(), context.getDeclaringClass().isApplicationClass()); }
protected EdgeFilter() { super(new EdgePredicate() { @Override public boolean want(Edge e) { return e.kind().isExplicit() || e.kind().isThread() || e.kind().isExecutor() || e.kind().isAsyncTask() || e.kind().isClinit() || e.kind().isPrivileged(); } }); }
@Override public Collection<Unit> load(SootMethod m) throws Exception { ArrayList<Unit> res = new ArrayList<Unit>(); //only retain callers that are explicit call sites or Thread.start() Iterator<Edge> edgeIter = new EdgeFilter().wrap(cg.edgesInto(m)); while(edgeIter.hasNext()) { Edge edge = edgeIter.next(); res.add(edge.srcUnit()); } res.trimToSize(); return res; }
/** * Return all possible values for an integer local variable. * * @param start The statement where the analysis should start. * @param local The local variable whose values we are looking for. * @param visitedStmts The set of visited statement. * @return The set of possible values for the local variable. */ private Set<Object> findIntAssignmentsForLocal(Stmt start, Local local, Set<Stmt> visitedStmts) { List<DefinitionStmt> assignStmts = findAssignmentsForLocal(start, local, true, new HashSet<Pair<Unit, Local>>()); Set<Object> result = new HashSet<>(assignStmts.size()); for (DefinitionStmt assignStmt : assignStmts) { Value rhsValue = assignStmt.getRightOp(); if (rhsValue instanceof IntConstant) { result.add(((IntConstant) rhsValue).value); } else if (rhsValue instanceof LongConstant) { result.add(((LongConstant) rhsValue).value); } else if (rhsValue instanceof ParameterRef) { ParameterRef parameterRef = (ParameterRef) rhsValue; Iterator<Edge> edges = Scene.v().getCallGraph() .edgesInto(AnalysisParameters.v().getIcfg().getMethodOf(assignStmt)); while (edges.hasNext()) { Edge edge = edges.next(); InvokeExpr invokeExpr = edge.srcStmt().getInvokeExpr(); Value argValue = invokeExpr.getArg(parameterRef.getIndex()); if (argValue instanceof IntConstant) { result.add(((IntConstant) argValue).value); } else if (argValue instanceof LongConstant) { result.add(((LongConstant) argValue).value); } else if (argValue instanceof Local) { Set<Object> newResults = findIntAssignmentsForLocal(edge.srcStmt(), (Local) argValue, visitedStmts); result.addAll(newResults); } else { result.add(TOP_VALUE); } } } else { return Collections.singleton((Object) TOP_VALUE); } } return result; }
private void handleInvokeExpr(InvokeExpr ie, Stmt is) { // if(is.toString().contains("hashCode")) // System.out.println(); CallGraph cg = Scene.v().getCallGraph(); for(Iterator<Edge> edges = cg.edgesOutOf(is); edges.hasNext();) { Edge e = edges.next(); SootMethod target = e.getTgt().method(); //if(method.getDeclaringClass().isApplicationClass()) if(!Util.skipPackage(target.getDeclaringClass().getPackageName())) { //SootMethodRef methodRef = ie.getMethodRef(); //String subSig = methodRef.resolve().getSubSignature();//MAY NOT BE SOUND // Verify that this target is an implementation of the method we intend to call, // and not just a class initializer or other unintended control flow. //if(target.getSubSignature().equals(subSig)) { analyze(target); } } } }
/** Checks whether an edge in the callgraph (a call in the * program) corresponds to a call to a method that should be * translated in the activation of a callback */ public boolean isActive(Edge edge) { // This is a special kind of edge that cannot be taken recursively // Taking it would create stupid loops. if (edge.isClinit()) return false; Stmt stmt = edge.srcStmt(); InvokeExpr ie = stmt.getInvokeExpr(); SootMethod m = ie.getMethod(); return table.containsKey(m); }
/** Given an edge which is a call to a callback activator, gives * back a map whose keys are the methods potentially used as * callbacks and the associated value is an explanation message * (stored in the configuration file) of the kind of callback * resolution * @param e regularly called edge, * @return a map from potential methods to explanations. */ public Map <SootMethod,String> resolve(Edge e) { // [SootMethod] Set InvokeExpr ie = e.srcStmt().getInvokeExpr(); SootMethod m = ie.getMethod(); Translation trans = (Translation) table.get(m); // Ok there is no translation registered, tell to keep this // method call as is. if(trans==null) return null; HashMap <SootMethod,String> result = new HashMap <SootMethod,String> (); do { PointsToSet ptArg = getPointsTo(ie,trans.argument); if (trans.linkThrough != null) { for(LinkMethod lm : trans.linkThrough) { ptArg = resolveLinkThrough(ptArg,lm); } } Set <Type> types = ptArg.possibleTypes(); for(Type t : types) { if (! (t instanceof RefType)) continue; SootClass c = ((RefType) t).getSootClass(); SootMethod devirtualized = null; try { devirtualized = c.getMethod(trans.target); } catch (Exception exc) { System.out.println("Cannot find [" + trans.target + "]"); } if (devirtualized != null) result.put(devirtualized, trans.message); } trans = trans.followup; } while (trans != null); return result; }
private static void visitAncestors(CallGraph cg, Set<Edge> seen, Deque<SootMethod> stack, Visitor visitor, SootMethod m) { Iterator <Edge> it = cg.edgesInto(m); stack.push(m); while(it.hasNext()) { Edge e = it.next(); if (seen.contains(e)) continue; seen.add(e); visitor.visit(e,stack); visitAncestors(cg, seen, stack, visitor, e.src()); } stack.pop(); }
/** * Launch the call rules on a given invoke expression. * @param ad context of analysis * @param ie the instruction (expression) under study * @param st the statement that contains the invoke. * @throws Alert if anything goes wrong */ public void spy(MethodSpyAnalysis ad, InvokeExpr ie, Unit st) throws Alert { SootMethod m = ie.getMethod(); try { HashSet<SpyMethod> todolist = new HashSet<SpyMethod>(); if (ie instanceof InstanceInvokeExpr) { if (ie instanceof InterfaceInvokeExpr || m.getSignature().equals(NEW_INSTANCE_SIGNATURE)) { solveMethod(m,todolist); } for(Iterator <Edge> it = callgraph.edgesOutOf(st); it.hasNext();) { SootMethod tgt = it.next().tgt(); solveMethod(tgt,todolist); } } else { solveMethod(m,todolist); } if (todolist.size() > 0) { for(SpyMethod def : todolist) { def.spy(ad, ie, st); } } } catch (Exception e) { e.printStackTrace(Out.getLog()); throw Alert.raised(e, "Error in spy: " + e.getMessage() + " in unit " + ie + " in method " + ad.method); } }
/** * Gives back the set of types of broadcast receivers for dynamic filters that match a set of given actions. * @param actions set of actions captured by receivers of interest. * @return */ private Set <String> dynamicallyFilteredBroadcastTypes(String action) { Set <String> result = new HashSet<String>(); SootClass contextClass; SootClass intentFilterClass; try { contextClass = scene.getSootClass(ANDROID_CONTENT_CONTEXT_WRAPPER); intentFilterClass = scene.getSootClass(ANDROID_CONTENT_INTENT_FILTER); SootField actionField = intentFilterClass.getField(ACTION_FIELD_SIGNATURE); for(String registerSig : REGISTER_SIGNATURES) { SootMethod regMethod = contextClass.getMethod(registerSig); Iterator<Edge> edges = cg.edgesInto(regMethod); while(edges.hasNext()) { Edge edge = edges.next(); InvokeExpr ie = edge.srcStmt().getInvokeExpr(); if (ie.getArgCount() < 2) continue; Value filter = ie.getArg(1); if (! (filter instanceof Local)) continue; PointsToSet pts = pag.reachingObjects((Local) filter, actionField); Set <String> filteredActions = pts.possibleStringConstants(); if (filteredActions == null || ! filteredActions.contains(action)) continue; Value receivers = ie.getArg(0); if (! (receivers instanceof Local)) continue; PointsToSet ptsReceiver = pag.reachingObjects((Local) receivers); addAll(result,ptsReceiver.possibleTypes()); } } } catch (RuntimeException e) { Out.getLog().println("Error while computing dynamic aborted broadcast " + e.getMessage()); } return result; }
private void analyzeEdge(Edge edge) { SootMethod m=edge.tgt(); if (edge.isThreadRunCall()) { threadsEntryMethod.add(m); dprintln("Found thread entry method: "+m.getSignature()); } }
/** * Resolves virtual calls using the default call graph and returns * a list of methods which are the targets of explicit edges. * TODO: Should we consider thread/clinit edges? */ @Override public List<SootMethod> resolveTargets(SootMethod method, Unit node) { List<SootMethod> targets = new LinkedList<SootMethod>(); Iterator<Edge> it = Scene.v().getCallGraph().edgesOutOf(node); while(it.hasNext()) { Edge edge = it.next(); if (edge.isExplicit()) { targets.add(edge.tgt()); } } return targets; }
public static List<SootMethod> getSparkExplicitEdges(Unit callStmt) { Iterator<Edge> edges = Scene.v().getCallGraph().edgesOutOf(callStmt); List<SootMethod> targets = new LinkedList<SootMethod>(); while (edges.hasNext()) { Edge edge = edges.next(); if (edge.isExplicit()) { targets.add(edge.tgt()); } } return targets; }
public static List<SootMethod> getSparkExplicitEdges(SootMethod sootMethod) { Iterator<Edge> edges = Scene.v().getCallGraph().edgesOutOf(sootMethod); List<SootMethod> targets = new LinkedList<SootMethod>(); while (edges.hasNext()) { Edge edge = edges.next(); if (edge.isExplicit()) { targets.add(edge.tgt()); } } return targets; }
private static long countCallChains(SootMethod method, int k) { if (k == 0) return 1; long count = 1; Iterator<Edge> edges = Scene.v().getCallGraph().edgesOutOf(method); while(edges.hasNext()) { Edge edge = edges.next(); if (edge.isExplicit()) { SootMethod target = edge.tgt(); count = count + countCallChains(target, k-1); } } return count; }
private static void search(CallGraph cg, SootMethod l, Stack<SootMethod> stack, int depth) { logger.debug(" <"+ depth +"> propagate from "+ l); if (depth == 1) currentWrapper = l; if (depth == 2) { currentEntryPoint = l; if (currentEntryPoint.toString().contains("GenerationGG") || //currentEntryPoint.toString().contains("init>") || currentEntryPoint.toString().contains("ServicesInit:")) { } else { if (!currentEntryPoint.toString().contains("DumbClass:")) { EntryPointKey epk = new EntryPointKey(currentWrapper, currentEntryPoint); entryPointsToPermissionSet.put(epk, null); } } } if (alreadyComputed.contains(l)) { addPermissionsToStack(stack, l); return; } Iterator<Edge> it = cg.edgesOutOf(l); while (it.hasNext()) { Edge e = it.next(); SootMethod outMethod = e.tgt(); if (outMethod.toString().equals(l.toString())){ logger.warn("outMethod same as l: "+ l); continue; } if (stack.contains(outMethod)) throw new RuntimeException("cycle in stack!\n" + outMethod +"\n"+ Util.printStack(stack)); addPermissionsToStack(stack, outMethod); stack.push(outMethod); search(cg, outMethod, stack, depth+1); stack.pop(); } alreadyComputed.add(l); if (!methodToPermissionSet.containsKey(l)) methodToPermissionSet.put(l, new HashSet<String>()); }
public boolean isStaticFieldWrite(SootMethod method, SootField variable, Set<SootMethod> runList) { // Without a body, we cannot say much if (!method.hasActiveBody()) return false; // Do not process the same method twice if (!runList.add(method)) return false; // Do we already have an entry? Map<SootField, StaticFieldUse> entry = staticFieldUses.get(method); if (entry != null) { StaticFieldUse b = entry.get(variable); if (b != null && b != StaticFieldUse.Unknown) { return b == StaticFieldUse.Write; } } // Scan for references to this variable for (Unit u : method.getActiveBody().getUnits()) { if (u instanceof AssignStmt) { AssignStmt assign = (AssignStmt) u; if (assign.getLeftOp() instanceof StaticFieldRef) { SootField sf = ((StaticFieldRef) assign.getLeftOp()).getField(); registerStaticVariableUse(method, sf, StaticFieldUse.Write); return true; } } if (((Stmt) u).containsInvokeExpr()) for (Iterator<Edge> edgeIt = Scene.v().getCallGraph().edgesOutOf(u); edgeIt.hasNext(); ) { Edge e = edgeIt.next(); if (isStaticFieldWrite(e.getTgt().method(), variable, runList)); return true; } } // Variable is not read registerStaticVariableUse(method, variable, StaticFieldUse.Unwrite); return false; }
/** * Checks whether the given method or one of its transitive callees has * side-effects or calls a sink method * @param method The method to check * @param runList A set to receive all methods that have already been * processed * @param cache The cache in which to store the results * @return True if the given method or one of its transitive callees has * side-effects or calls a sink method, otherwise false. */ private boolean hasSideEffectsOrCallsSink(SootMethod method, Set<SootMethod> runList) { // Without a body, we cannot say much if (!method.hasActiveBody()) return false; // Do we already have an entry? Boolean hasSideEffects = methodSideEffects.get(method); if (hasSideEffects != null) return hasSideEffects; Boolean hasSink = methodSinks.get(method); if (hasSink != null) return hasSink; // Do not process the same method twice if (!runList.add(method)) return false; // If this is an Android stub method that just throws a stub exception, // this will never happen in practice and can be removed if (methodIsAndroidStub(method)) { methodSideEffects.put(method, false); return false; } // Scan for references to this variable for (Unit u : method.getActiveBody().getUnits()) { if (u instanceof AssignStmt) { AssignStmt assign = (AssignStmt) u; if (assign.getLeftOp() instanceof FieldRef || assign.getLeftOp() instanceof ArrayRef) { methodSideEffects.put(method, true); return true; } } Stmt s = (Stmt) u; // If this method calls another method for which we have a taint // wrapper, we need to conservatively assume that the taint wrapper // can do anything if (taintWrapper != null && taintWrapper.supportsCallee(s)) { methodSideEffects.put(method, true); return true; } if (s.containsInvokeExpr()) { // If this method calls a sink, we need to keep it if (sourceSinkManager != null && sourceSinkManager.isSink((Stmt) u, icfg, null)) { methodSinks.put(method, true); return true; } // Check the callees for (Iterator<Edge> edgeIt = Scene.v().getCallGraph().edgesOutOf(u); edgeIt.hasNext(); ) { Edge e = edgeIt.next(); if (hasSideEffectsOrCallsSink(e.getTgt().method(), runList)) return true; } } } // Variable is not read methodSideEffects.put(method, false); return false; }
/** * Checks whether the given method or one of its transitive callees has * side-effects or calls a sink method * @param method The method to check * @param runList A set to receive all methods that have already been * processed * @param cache The cache in which to store the results * @return True if the given method or one of its transitive callees has * side-effects or calls a sink method, otherwise false. */ private boolean hasSideEffectsOrReadsThis(SootMethod method, Set<SootMethod> runList) { // Without a body, we cannot say much if (!method.hasActiveBody()) return false; // Do we already have an entry? Boolean hasSideEffects = methodSideEffects.get(method); if (hasSideEffects != null) return hasSideEffects; // Do not process the same method twice if (!runList.add(method)) return false; // If this is an Android stub method that just throws a stub exception, // this will never happen in practice and can be removed if (methodIsAndroidStub(method)) { methodSideEffects.put(method, false); return false; } // Scan for references to this variable Local thisLocal = method.isStatic() ? null : method.getActiveBody().getThisLocal(); for (Unit u : method.getActiveBody().getUnits()) { if (u instanceof AssignStmt) { AssignStmt assign = (AssignStmt) u; if (assign.getLeftOp() instanceof FieldRef || assign.getLeftOp() instanceof ArrayRef) { methodSideEffects.put(method, true); return true; } } Stmt s = (Stmt) u; // If this statement uses the "this" local, we have to // conservatively assume that is can read data if (thisLocal != null) for (ValueBox vb : s.getUseBoxes()) if (vb.getValue() == thisLocal) return true; if (s.containsInvokeExpr()) { // Check the callees for (Iterator<Edge> edgeIt = Scene.v().getCallGraph().edgesOutOf(u); edgeIt.hasNext(); ) { Edge e = edgeIt.next(); if (hasSideEffectsOrReadsThis(e.getTgt().method(), runList)) return true; } } } // Variable is not read methodSideEffects.put(method, false); return false; }
public Set<Edge> lookupEdgesForAssignment(Pair<Node, Node> val) { return assign2edges.get(val); }
/** * Report the virtual callsites resolution result for the user's code. */ public void checkCallGraph() { int[] limits = new int[] { 1, 2, 4, 8 }; evalRes.total_call_edges = new Histogram(limits); CallGraph cg = Scene.v().getCallGraph(); for ( Stmt callsite : ptsProvider.multiCallsites ) { Iterator<Edge> edges = cg.edgesOutOf(callsite); if ( !edges.hasNext() ) continue; evalRes.n_callsites++; // get an edge Edge anyEdge = edges.next(); SootMethod src = anyEdge.src(); if ( !ptsProvider.isReachableMethod(src) || !ptsProvider.isValidMethod(src) ) continue; // get the base pointer CgEdge p = ptsProvider.getInternalEdgeFromSootEdge(anyEdge); LocalVarNode vn = (LocalVarNode)p.base_var; // test the call graph int edge_cnt = 1; while ( edges.hasNext() ) { ++edge_cnt; edges.next(); } evalRes.n_geom_call_edges += edge_cnt; if ( edge_cnt == 1 ) ++evalRes.n_geom_solved_all; // test app method if ( !src.isJavaLibraryMethod() ) { InvokeExpr ie = callsite.getInvokeExpr(); if ( edge_cnt == 1 ) { ++evalRes.n_geom_solved_app; if ( ptsProvider.getOpts().verbose() ) { outputer.println(); outputer.println("<<<<<<<<< Additional Solved Call >>>>>>>>>>"); outputer.println(src.toString()); outputer.println(ie.toString()); } } else { // We try to test if this callsite is solvable // under some contexts Histogram call_edges = new Histogram(limits); test_1cfa_call_graph(vn, src, ie.getMethod(), call_edges); evalRes.total_call_edges.merge(call_edges); call_edges = null; } evalRes.n_geom_user_edges += edge_cnt; evalRes.n_user_callsites++; } } ptsProvider.ps.println(); ptsProvider.ps.println("--------> Virtual Callsites Evaluation <---------"); ptsProvider.ps.printf("Total virtual callsites (app code): %d (%d)\n", evalRes.n_callsites, evalRes.n_user_callsites); ptsProvider.ps.printf("Total virtual call edges (app code): %d (%d)\n", evalRes.n_geom_call_edges, evalRes.n_geom_user_edges); ptsProvider.ps.printf("Virtual callsites additionally solved by geomPTA compared to SPARK (app code) = %d (%d)\n", evalRes.n_geom_solved_all, evalRes.n_geom_solved_app); evalRes.total_call_edges.printResult(ptsProvider.ps, "Testing of unsolved callsites on 1-CFA call graph: "); if (ptsProvider.getOpts().verbose()) ptsProvider.outputNotEvaluatedMethods(); }
/** * Usually, users specify the last K paths as the context. We call it k-CFA context. * However, k-CFA is too restrictive, users want to specify the call edges anywhere in the context path. * A common usage is specifying only one edge in the context path. * We implement this common usage here. * * @param sootEdge: the specified context edge in soot edge format * @param l: the querying pointer * @param visitor: container for querying result * @return false, l does not have points-to information under the contexts induced by the given call edge */ @SuppressWarnings("rawtypes") public boolean contexsByAnyCallEdge( Edge sootEdge, Local l, PtSensVisitor visitor ) { // Obtain the internal representation of specified context CgEdge ctxt = geomPts.getInternalEdgeFromSootEdge(sootEdge); if ( ctxt == null || ctxt.is_obsoleted == true ) return false; // Obtain the internal representation for querying pointer LocalVarNode vn = geomPts.findLocalVarNode(l); if ( vn == null ) { // Normally this could not happen, perhaps it's a bug return false; } IVarAbstraction pn = geomPts.findInternalNode(vn); if ( pn == null ) { // This pointer is no longer reachable return false; } pn = pn.getRepresentative(); if ( !pn.hasPTResult() ) return false; // Obtain the internal representation of the method that encloses the querying pointer SootMethod sm = vn.getMethod(); int target = geomPts.getIDFromSootMethod(sm); if ( target == -1 ) return false; // Start call graph traversal long L = ctxt.map_offset; long R = L + max_context_size_block[rep_cg[ctxt.s]]; assert L < R; visitor.prepare(); prepareIntervalPropagations(); if ( propagateIntervals(ctxt.t, L, R, target) ) { // We calculate the points-to results ContextsCollector targetContexts = contextsForMethods[target]; for ( SimpleInterval si : targetContexts.bars ) { assert si.L < si.R; pn.get_all_context_sensitive_objects(si.L, si.R, visitor); } // Reset targetContexts.clear(); } visitor.finish(); return visitor.numOfDiffObjects() != 0; }
/** * Standard K-CFA querying for arbitrary K. * * @param callEdgeChain: last K call edges leading to the method that contains l. callEdgeChain[0] is the farthest call edge in the chain. * @param l: the querying pointer * @param visitor: the querying result container * @return false, l does not have points-to information under the given context */ @SuppressWarnings("rawtypes") public boolean contextsByCallChain(Edge[] callEdgeChain, Local l, PtSensVisitor visitor) { // Prepare for initial contexts SootMethod firstMethod = callEdgeChain[0].src(); int firstMethodID = geomPts.getIDFromSootMethod(firstMethod); if ( firstMethodID == -1 ) return false; // Obtain the internal representation for querying pointer LocalVarNode vn = geomPts.findLocalVarNode(l); if ( vn == null ) { // Normally this could not happen, perhaps it's a bug return false; } IVarAbstraction pn = geomPts.findInternalNode(vn); if (pn == null) { // This pointer is no longer reachable return false; } pn = pn.getRepresentative(); if ( !pn.hasPTResult() ) return false; SootMethod sm = vn.getMethod(); if ( geomPts.getIDFromSootMethod(sm) == -1 ) return false; // Iterate the call edges and compute the contexts mapping iteratively visitor.prepare(); long L = 1; for ( int i = 0; i < callEdgeChain.length; ++i ) { Edge sootEdge = callEdgeChain[i]; CgEdge ctxt = geomPts.getInternalEdgeFromSootEdge(sootEdge); if ( ctxt == null || ctxt.is_obsoleted == true ) return false; // Following searching procedure works for both methods in SCC and out of SCC // with blocking scheme or without blocking scheme int caller = geomPts.getIDFromSootMethod(sootEdge.src()); // We obtain the block that contains current offset L long block_size = max_context_size_block[rep_cg[caller]]; long in_block_offset = (L-1) % block_size; // Transfer to the target block with the same in-block offset L = ctxt.map_offset + in_block_offset; } long ctxtLength = max_context_size_block[rep_cg[firstMethodID]]; long R = L + ctxtLength; pn.get_all_context_sensitive_objects(L, R, visitor); visitor.finish(); return visitor.numOfDiffObjects() != 0; }
/** * Obtain the edge representation internal to geomPTA. */ public CgEdge getInternalEdgeFromSootEdge( Edge e ) { return edgeMapping.get(e); }