Call Graph with Edges for Callbacks from Libraries

[moshethebeadle]

I tried creating a call graph using the class hierarchy algorithm. It did fine, except for code like this:

class C {
      Map<Long, String> mapLongsToStrings(List<Long> longs) {
        return longs
            .stream()
            .collect(
                Collectors.toMap(
                    Function.identity(),
                    this::longToString
                )
            );
    }

    String longToString(Long l) {
       return l.toString();
    }
}

Obviously, this is a simple version, but it was unable to create the edge from mapLongsToStrings to longToString.

My IDE can handle this just fine when I do Call Hierarchy, and I believe other analysis tools can as well.

Do I need to change my analysis options in order to make the algorithm add the missing edge?
(Note: I did not add the Java core library to the analysis because it took a long time).

I believe the core issue is that SootUp needs to model the library (Collectors.toMap) to be able to automatically add the edge. But I'm rather unfamiliar in this area.

[JonasKlauke]

Yeah you are correct, this is an indirect edge which is currently not modeled in SootUp.
It is indirect, because technically ToMap calls the longToString method.
This could be added as an implicite edge in the call graph algorithm.
Currently SootUp only adds clinit calls in the implicite edge step.
You could add your requested behaivor here

SootUp/sootup.callgraph/src/main/java/sootup/callgraph/AbstractCallGraphAlgorithm.java

Line 248 in ec86625

protected void resolveAllImplicitCallsFromSourceMethod(

[swissiety]

can we make implicit edges configurable?

[Liyw979]

Hi @JonasKlauke, implicit calls are really difficult to deal with. Is there any plan on this?

[moshethebeadle]

A little context on this: I'm doing a project to use LLMs to help with problems such as these. The idea is to insert LLMs into certain points into the analysis to essentially add missing edges... that way, you don't have to hand-code a special case for each scenario.

This might be one case where the LLM would just know that there's an implicit edge.

I suppose there's the chance I could integrate the work I do with SootUp... initially I'd just planned on keeping them separate (use SootUp to create the CallGraph, then the LLM to augment it with missing edges). But possibly there could be a way to interleave the analyses more closely.

Currently I'm focused on constructing just proper call graphs. But in the future I'd like to do full data-flow analyses (like for data lineage, similar to taint analysis), and would plan on also using LLMs to assist.

Would you guys be open to some contributions from me as I use this tool?

[JonasKlauke]

We thought about creating a Bachelor or Master Thesis around this.
The student should collect a list of implicit calls from established tools and literature.
Maybe they can also find potenitals for new implicit calls in newer Java Versions.
After they have accumulated the list, next step would be to also add them to SootUp, to show they are applicable in practice.

[JonasKlauke]

A little context on this: I'm doing a project to use LLMs to help with problems such as these. The idea is to insert LLMs into certain points into the analysis to essentially add missing edges... that way, you don't have to hand-code a special case for each scenario.

This might be one case where the LLM would just know that there's an implicit edge.

I suppose there's the chance I could integrate the work I do with SootUp... initially I'd just planned on keeping them separate (use SootUp to create the CallGraph, then the LLM to augment it with missing edges). But possibly there could be a way to interleave the analyses more closely.

Currently I'm focused on constructing just proper call graphs. But in the future I'd like to do full data-flow analyses (like for data lineage, similar to taint analysis), and would plan on also using LLMs to assist.

Would you guys be open to some contributions from me as I use this tool?

if it improves the call graph we could think about adding it as an sub module in SootUp. I also wonder if it would be better to do it as a post-processing like your intented way, or if a direct integartion would be better. But this would create a lot of LLM requests. But the post-processing solution would also mean that we need a good way to continue the call graph analysis on an established call graph, because if the LLM finds a complete new method, the call graph cotains no data about the method called by this method

[moshethebeadle]

Lukas Hermann and Pavel Parizek achieved really solid data-flow analysis in Java with Manta, but according to the paper, they had to hardcode all the specific scenarios for libraries, and I imagine implicit edges.

I've noticed that IDEs do a good job with implicit edges, e.g. Eclipse and IntelliJ -- that's why I've never even thought it would be an issue until using other tools to create call graphs. But of course it makes sense why it would be an issue.

I was drawn to LLMs because they intuitively know how to handle implicit edges and libraries. One use case I've dealt with in my fork of SootUp (not much there yet) is to include abstract methods in the call graph to support libraries such as Spring Data, which use interface methods to represent DB queries. LLMs, however, just "know" what to do with this. It's beautiful.

So obviously there are tradeoffs between traditional static analysis and LLMs. I love how fast SootUp is. Plus, there's additional algorithms that are amazing. But then there are the extra components that lie beyond language features, such as Spring config. It's possible to manually code for those... but LLMs just "get" it.

But their accuracy suffers as the context size grows. And how do you handle libraries (SootUp does well with this.. jars)?

So I've been doing iterative call-graph generation with the LLMs... first trying it with full context, but only expanding a handful of methods at a time. That still suffered a bit. So now I'm passing just limited context... which is a challenge, because how do you know "which" contextual code to add to the prompt?

To make sure you know my use case, what I'm doing is extracting not just the call graph nodes and edges but nodes for "External Resources" such as HTTP calls and endpoints and DB tables. The LLMs are great at doing this extra bit.

But yeah, I've been banging my head a bit on using the LLM for the call-graph generation... it's fickle, inconsistent, requiring lots of prompting.

Would love to chat more with you guys.

-- Jake Toronto (moshethebeadle is an old username)

P.S. Side note: Gemini Flash 2.0 understands Jimple IR quite well.