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.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected static class	RapidTypeAnalysisAlgorithm.Call This private class is used to save reachable calls.

Field Summary

Fields

Modifier and Type	Field and Description
protected Map<ClassType,List<RapidTypeAnalysisAlgorithm.Call>>	ignoredCalls
protected Set<ClassType>	instantiatedClasses

Fields inherited from class sootup.callgraph.AbstractCallGraphAlgorithm

view

Constructor Summary

Constructors

Constructor and Description
RapidTypeAnalysisAlgorithm(View view) The constructor of the RTA algorithm.

Method Summary

Modifier and Type	Method and Description
protected List<ClassType>	collectInstantiatedClassesInMethod(SootMethod method) This method is called to collect all instantiation of classes in a given method body.
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.
CallGraph	initialize() This method initializes and starts the call graph algorithm without given entry points.
CallGraph	initialize(List<MethodSignature> entryPoints) This method initializes and starts the call graph algorithm with given entry points.
protected void	postProcessingMethod(View view, MethodSignature sourceMethod, Deque<MethodSignature> workList, MutableCallGraph cg) Postprocessing is not needed in RTA
protected void	preProcessingMethod(View view, MethodSignature sourceMethod, Deque<MethodSignature> workList, MutableCallGraph cg) Preprocessing of a method in the RTA call graph algorithm
protected Stream<MethodSignature>	resolveCall(SootMethod sourceMethod, AbstractInvokeExpr invokeExpr) In the RTA algorithm, every virtual call is resolved by using the hierarchy and a hashset containing every instantiated class.

Methods inherited from class sootup.callgraph.AbstractCallGraphAlgorithm

addClass, addImplicitEdgesOfEntryPoints, findConcreteMethod, findMainMethod, initializeCallGraph, resolveAllImplicitCallsFromSourceMethod, resolveAllStaticInitializerCallsFromSourceMethod, resolveConcreteDispatch

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

instantiatedClasses

@Nonnull
protected Set<ClassType> instantiatedClasses

ignoredCalls

@Nonnull
protected Map<ClassType,List<RapidTypeAnalysisAlgorithm.Call>> ignoredCalls

Constructor Detail

RapidTypeAnalysisAlgorithm

public RapidTypeAnalysisAlgorithm(@Nonnull
                                  View view)

The constructor of the RTA algorithm.

Parameters:

view - it contains the data of the classes and methods

Method Detail

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,
                                                       AbstractInvokeExpr invokeExpr)

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.

invokeExpr - it contains 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