Package sootup.callgraph

Class RapidTypeAnalysisAlgorithm

java.lang.Object
sootup.callgraph.AbstractCallGraphAlgorithm
sootup.callgraph.RapidTypeAnalysisAlgorithm
All Implemented Interfaces:
CallGraphAlgorithm
public class RapidTypeAnalysisAlgorithm extends AbstractCallGraphAlgorithm
This class implements the Rapid Type Analysis call graph algorithm. In this algorithm, every virtual call is resolved to the all implemented overwritten methods of subclasses in the entire class path which have been instantiated by a new expression.

Compared to the CHA algorithm, this algorithm is more precise because it only considers instantiated subclasses as call targets and CHA considers all subclasses.

  • Field Details

  • Constructor Details

    • RapidTypeAnalysisAlgorithm

      public RapidTypeAnalysisAlgorithm(@Nonnull View view)
      The constructor of the RTA algorithm.
      Parameters:
      view - it contains the data of the classes and methods

  • Method Details

    • initialize

      @Nonnull public CallGraph initialize()
      Description copied from interface: CallGraphAlgorithm
      This method initializes and starts the call graph algorithm without given entry points. Before the algorithm is started, all main methods are searched and set as entry points.
      Returns:
      a generated call graph with every main class as starting point.

    • initialize

      @Nonnull public CallGraph initialize(@Nonnull List<MethodSignature> entryPoints)
      Description copied from interface: CallGraphAlgorithm
      This method initializes and starts the call graph algorithm with given entry points. The entry points define the start methods in the call graph algorithm.
      Parameters:
      entryPoints - a list of entry points for the call graph algorithm. The algorithm starts at these methods and inspects all reachable methods.
      Returns:
      a generated call graph with every entry point as starting point.

    • collectInstantiatedClassesInMethod

      protected List<ClassType> collectInstantiatedClassesInMethod(SootMethod method)
      This method is called to collect all instantiation of classes in a given method body. This is important since the RTA algorithm resolves virtual calls only to instantiated classes
      Parameters:
      method - this object contains the method body which is inspected.

    • resolveCall

      @Nonnull protected Stream<MethodSignature> resolveCall(SootMethod sourceMethod, InvokableStmt invokableStmt)
      In the RTA algorithm, every virtual call is resolved by using the hierarchy and a hashset containing every instantiated class. Every subclass of the class is considered as target if it is instantiated and if it contains an implementation of the methods called in the invoke expression.
      Specified by:
      resolveCall in class AbstractCallGraphAlgorithm
      Parameters:
      sourceMethod - the method object that contains the given invoke expression in the body.
      invokableStmt - the statement containing the call which is resolved.
      Returns:
      a stream containing all reachable method signatures after applying the RTA call graph algorithm

    • preProcessingMethod

      protected void preProcessingMethod(View view, MethodSignature sourceMethod, @Nonnull Deque<MethodSignature> workList, @Nonnull MutableCallGraph cg)
      Preprocessing of a method in the RTA call graph algorithm

      Before processing the method, all instantiated types are collected inside the body of the sourceMethod. If a new instantiated class has previously ignored calls to this class, they are added to call graph

      Specified by:
      preProcessingMethod in class AbstractCallGraphAlgorithm
      Parameters:
      view - view
      sourceMethod - the processed method
      workList - the current work list
      cg - the current cg

    • includeIgnoredCallsToClass

      protected void includeIgnoredCallsToClass(ClassType classType, MutableCallGraph cg, Deque<MethodSignature> workList)
      This method will add all saved ignored calls from a given class to the call graph. All new targets will be added to the worklist
      Parameters:
      classType - the class type which is the target of all ignored calls
      cg - the call graph that will be extended by the ignored calls
      workList - the work list that will be extended by the new targets of ignored calls.

    • postProcessingMethod

      protected void postProcessingMethod(View view, MethodSignature sourceMethod, @Nonnull Deque<MethodSignature> workList, @Nonnull MutableCallGraph cg)
      Postprocessing is not needed in RTA
      Specified by:
      postProcessingMethod in class AbstractCallGraphAlgorithm
      Parameters:
      view - view
      sourceMethod - the processed method
      workList - the current worklist that is extended by methods that have to be analyzed.
      cg - the current cg is extended by new call targets and calls