Skip to content

Improve CHA runtime and improve InvokeInterface resolving#734

Merged
JonasKlauke merged 24 commits intodevelopfrom
improve/CallgraphRuntime
Nov 20, 2023
Merged

Improve CHA runtime and improve InvokeInterface resolving#734
JonasKlauke merged 24 commits intodevelopfrom
improve/CallgraphRuntime

Conversation

@JonasKlauke
Copy link
Copy Markdown
Collaborator

@JonasKlauke JonasKlauke commented Oct 30, 2023

  • Reworked CHA algorithm to save runtime
  • Removed Utilityclass MethodDispatchResolver
  • ICFGDotExporter uses callgraph to decide dispatches
  • Callgraph algorithm ignore Library classes
  • Added Comparator to sort classes by their hierarchy

@codecov
Copy link
Copy Markdown

codecov bot commented Nov 16, 2023

Codecov Report

Attention: 15 lines in your changes are missing coverage. Please review.

Comparison is base (23503d7) 63.64% compared to head (0ddd798) 63.58%.

Files Patch % Lines
...a/sootup/callgraph/AbstractCallGraphAlgorithm.java 89.58% 3 Missing and 2 partials ⚠️
...tup/callgraph/ClassHierarchyAnalysisAlgorithm.java 92.85% 0 Missing and 3 partials ⚠️
...a/sootup/callgraph/RapidTypeAnalysisAlgorithm.java 92.68% 0 Missing and 3 partials ⚠️
...analysis/interprocedural/icfg/ICFGDotExporter.java 92.00% 0 Missing and 2 partials ⚠️
...sootup/core/typehierarchy/HierarchyComparator.java 75.00% 1 Missing and 1 partial ⚠️
Additional details and impacted files
@@              Coverage Diff              @@
##             develop     #734      +/-   ##
=============================================
- Coverage      63.64%   63.58%   -0.06%     
+ Complexity      3360     3338      -22     
=============================================
  Files            317      317              
  Lines          15124    15072      -52     
  Branches        2551     2543       -8     
=============================================
- Hits            9625     9583      -42     
+ Misses          4608     4601       -7     
+ Partials         891      888       -3     

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

Copy link
Copy Markdown
Collaborator

@swissiety swissiety left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

looks good!
just not sure about whether the other methods (currently unused by the framework) from MethodDispatchResolver would still be a nice addition to the framework?

@JonasKlauke
Copy link
Copy Markdown
Collaborator Author

Which Method do you mean?
I think the only interesting method would be concreteDispatch which is still contained in the AbstractCallGraphAlgorithm.
I'm not sure how interesting a method is which just list all implementations of the same method in Subtypes, because subtypes which have no implementation could use default methods of interfaces.
Additionally, it is quite easy to develop such a method with our provided API

MethodSignature baseMethod ....
view.getTypeHierarchy().subtypesOf(classtype)
   .map(clazz ->view.getIdentifierFactory().getMethodSignature(
      clazz , baseMethod.getSubMethodSignature))
   .map(ms -> view.getMethod(ms))
   .filter(Optional::isPresent)
   .map(Optional::get)

Sourcecode might not be correct. I wrote this down from mind

@JonasKlauke
Copy link
Copy Markdown
Collaborator Author

But we could think about if we want to provide an option to define a maximum depth for a call graph algorithm. For example a method which just looks at the given method and does not continue further. But for RTA we have the problem that we miss instantiations of classes which result in new targets. But CHA should be okay

@JonasKlauke JonasKlauke merged commit 208413c into develop Nov 20, 2023
@JonasKlauke JonasKlauke deleted the improve/CallgraphRuntime branch November 20, 2023 14:33
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

2 participants