Package sootup.callgraph

Class AbstractCallGraphAlgorithm

java.lang.Object
sootup.callgraph.AbstractCallGraphAlgorithm
All Implemented Interfaces:
CallGraphAlgorithm
Direct Known Subclasses:
ClassHierarchyAnalysisAlgorithm, RapidTypeAnalysisAlgorithm
public abstract class AbstractCallGraphAlgorithm extends Object implements CallGraphAlgorithm
The AbstractCallGraphAlgorithm class is the super class of all call graph algorithm. It provides basic methods used in all call graph algorithm. It is abstract since it has no implemented functionality to resolve method calls because it is decided by the applied call graph algorithm

  • Field Details

    • view

      protected final @NonNull View view

    • typeHierarchy

      protected final @NonNull TypeHierarchy typeHierarchy

    • threadType

      protected final @NonNull ClassType threadType

  • Constructor Details

    • AbstractCallGraphAlgorithm

      protected AbstractCallGraphAlgorithm(@NonNull View view)

  • Method Details

    • includeCall

      protected boolean includeCall(@NonNull SootMethod method, @NonNull InvokableStmt statement)
      Decide whether a call from method represented by statement shall be added to the call graph. Default: accept everything. Subclasses can override this method to implement pruning.
      Parameters:
      method - the source (caller) method
      statement - the invokable statement causing the call

    • initializeCallGraph

      protected MutableCallGraph initializeCallGraph(List<MethodSignature> entryPoints, List<MethodSignature> clinits)
      This method creates the mutable call graph which is used in the call graph algorithm. Overwrite it to change the used mutable call graph
      Returns:
      the initialized call graph used in the call graph algorithm

    • getClinitFromEntryPoints

      protected List<MethodSignature> getClinitFromEntryPoints(List<MethodSignature> entryPoints)
      This method returns a list of static initializers that should be considered by the given entry points
      Parameters:
      entryPoints - the entry points of the call graph algorithm

    • addCallToCG

      protected void addCallToCG(@NonNull MethodSignature source, @NonNull MethodSignature target, @NonNull InvokableStmt invokeStmt, @NonNull MutableCallGraph cg, @NonNull Deque<MethodSignature> workList)
      Adds the defined call to the given call graph. If the source or target method was added as vertex to the call graph, they will be added to the worklist
      Parameters:
      source - the method signature of the caller
      target - the method signature of the callee
      invokeStmt - the stmt causing the call
      cg - the call graph that will be updated
      workList - the worklist in which the method signature of newly added vertexes will be added

    • addCallToCG

      protected void addCallToCG(@NonNull CallGraph.Call call, @NonNull MutableCallGraph cg, @NonNull Deque<MethodSignature> workList)
      Adds the defined call to the given call graph. If the source or target method was added as vertex to the call graph, they will be added to the worklist
      Parameters:
      call - the call that should be added to the call graph
      cg - the call graph that will be updated
      workList - the worklist in which the method signature of newly added vertexes will be added

    • resolveAllCallsFromSourceMethod

      protected void resolveAllCallsFromSourceMethod(@NonNull SootMethod sourceMethod, @NonNull MutableCallGraph cg, @NonNull Deque<MethodSignature> workList)
      This method resolves all calls from a given source method. resolveCall is called for each invokable statements in the body of the source method that is implemented in the corresponding call graph algorithm. If new methods will be added as vertexes in the call graph, the work list will be updated
      Parameters:
      sourceMethod - this signature is used to access the statements contained method body of the specified method
      cg - the call graph that will receive the found calls
      workList - the work list that will be updated of found target methods

    • implicitStartRunCall

      protected void implicitStartRunCall(@NonNull SootMethod sourceMethod, @NonNull MutableCallGraph cg, @NonNull Deque<MethodSignature> workList)
      It resolves the start-run implicit calls caused by the given source method
      Parameters:
      sourceMethod - the inspected source method
      cg - implicit start-run calls will be added to the call graph
      workList - new run methods will be added to the work list

    • resolveAllImplicitCallsFromSourceMethod

      protected void resolveAllImplicitCallsFromSourceMethod(@NonNull SootMethod sourceMethod, @NonNull MutableCallGraph cg, @NonNull Deque<MethodSignature> workList)
      It resolves all implicit calls caused by the given source method
      Parameters:
      sourceMethod - the inspected source method
      cg - new calls will be added to the call graph
      workList - new target methods will be added to the work list

    • resolveAllStaticInitializerCalls

      protected void resolveAllStaticInitializerCalls(@NonNull SootMethod sourceMethod, @NonNull MutableCallGraph cg, @NonNull Deque<MethodSignature> workList)
      It resolves all static initializer calls caused by the given source method
      Parameters:
      sourceMethod - the inspected source method
      cg - clinit calls will be added to the call graph
      workList - found clinit methods will be added to the work list

    • preProcessingMethod

      protected abstract void preProcessingMethod(@NonNull MethodSignature sourceMethod, @NonNull Deque<MethodSignature> workList, @NonNull MutableCallGraph cg)
      This method enables optional pre-processing of a method in the call graph algorithm
      Parameters:
      sourceMethod - the processed method
      workList - the current work list that might be extended
      cg - the current cg that might be extended

    • postProcessingMethod

      protected abstract void postProcessingMethod(@NonNull MethodSignature sourceMethod, @NonNull Deque<MethodSignature> workList, @NonNull MutableCallGraph cg)
      This method enables optional post-processing of a method in the call graph algorithm
      Parameters:
      sourceMethod - the processed method
      workList - the current work list that might be extended
      cg - the current cg that might be extended

    • addClass

      public @NonNull CallGraph addClass(@NonNull CallGraph oldCallGraph, @NonNull ClassType classType)
      Description copied from interface: CallGraphAlgorithm
      Adds a class to the call graph. All methods will be set as entry points in the call graph algorithm. Starts the call graph algorithm. The found edges will be added to the call graph.
      Specified by:
      addClass in interface CallGraphAlgorithm
      Parameters:
      oldCallGraph - the call graph which will be modified.
      classType - the type of the calls.
      Returns:
      the modified call graph containing all methods of the given class

    • findMainMethod

      public MethodSignature findMainMethod()
      The method iterates over all classes present in view, and finds method with name main and SourceType - Application. This method is used by initialize() method used for creating call graph and the call graph is created by considering the main method as an entry point.

      The method throws an exception if there is no main method in any of the classes or if there are more than one main method.

      Returns:
      - MethodSignature of main method.

    • resolveCall

      protected abstract @NonNull Stream<MethodSignature> resolveCall(SootMethod method, InvokableStmt invokableStmt)
      This method resolves the possible targets of a given invoke expression. The results are dependable of the applied call graph algorithm. therefore, it is abstract.
      Parameters:
      method - the method object that contains the given invoke expression in the body.
      invokableStmt - it contains the call which is resolved.
      Returns:
      a stream of all reachable method signatures defined by the applied call graph algorithm.

    • resolveConcreteDispatch

      public static @NonNull Optional<MethodSignature> resolveConcreteDispatch(View view, MethodSignature m)
      Searches for the signature of the method that is the concrete implementation of m. This is done by checking each superclass and the class itself for whether it contains the concrete implementation.

    • findConcreteMethod

      protected static Optional<? extends SootMethod> findConcreteMethod(@NonNull View view, @NonNull MethodSignature sig)
      searches the method object in the given hierarchy
      Parameters:
      view - it contains all classes
      sig - the signature of the searched method
      Returns:
      the found method object, or null if the method was not found.

    • findMethodInHierarchy

      protected static Optional<SootMethod> findMethodInHierarchy(@NonNull View view, @NonNull SootClass sootClass, @NonNull MethodSubSignature targetMethodSignature)

    • findDefaultMethod

      protected static Optional<? extends SootMethod> findDefaultMethod(@NonNull View view, @NonNull SootClass sootClass, @NonNull MethodSubSignature defaultSignature)
      Searches the default method that would be used as a target of the given SootClass and MethodSubSignature. All interfaces are checked and it returns that SootMethod object of the interface which is the subtype of all possible fitting default method.
      Parameters:
      view - The view contains the hierarchy information and the classes and methods
      sootClass - the sootClass which defines the start of the search
      defaultSignature - the method-subsignature which defines the target method
      Returns:
      An Optional containing the default method or an empty Optional if there is no default method, or a superclass is not in the view.

    • isInterface

      protected boolean isInterface(ClassType classType)