#  AutoPruner: Transformer-Based Call Graph Pruning

Thanh Le-Cong  ,  Hong Jin Kang  ,  Truong Giang Nguyen  ,  Stefanus Agus
Haryono  ,  David Lo  Singapore Management UniversitySingaporeSingapore ,
Xuan-Bach D. Le  University of MelbourneMelbourneVictoriaAustralia and  Quyet
Thang Huynh  Hanoi University of Science and TechnologyHanoiVietnam

(2022)

###### Abstract.

Constructing a static call graph requires trade-offs between soundness and
precision. Program analysis techniques for constructing call graphs are
unfortunately usually imprecise. To address this problem, researchers have
recently proposed call graph pruning empowered by machine learning to post-
process call graphs constructed by static analysis. A machine learning model
is built to capture information from the call graph by extracting structural
features for use in a random forest classifier. It then removes edges that are
predicted to be false positives. Despite the improvements shown by machine
learning models, they are still limited as they do not consider the source
code semantics and thus often are not able to effectively distinguish true and
false positives.

In this paper, we present a novel call graph pruning technique, AutoPruner,
for eliminating false positives in call graphs via both statistical semantic
and structural analysis. Given a call graph constructed by traditional static
analysis tools, AutoPruner takes a Transformer-based approach to capture the
semantic relationships between the caller and callee functions associated with
each edge in the call graph. To do so, AutoPruner fine-tunes a model of code
that was pre-trained on a large corpus to represent source code based on
descriptions of its semantics. Next, the model is used to extract semantic
features from the functions related to each edge in the call graph. AutoPruner
uses these semantic features together with the structural features extracted
from the call graph to classify each edge via a feed-forward neural network.
Our empirical evaluation on a benchmark dataset of real-world programs shows
that AutoPruner outperforms the state-of-the-art baselines, improving on
F-measure by up to 13% in identifying false-positive edges in a static call
graph. Moreover, AutoPruner achieves improvements on two client analyses,
including halving the false alarm rate on null pointer analysis and over 10%
improvements on monomorphic call-site detection. Additionally, our ablation
study and qualitative analysis show that the semantic features extracted by
AutoPruner capture a remarkable amount of information for distinguishing
between true and false positives.

Call Graph Pruning, Static Analysis, Pretrained Language Model, Transformer

††copyright: acmlicensed††price: 15.00††doi:
10.1145/3540250.3549175††journalyear: 2022††submissionid:
fse22main-p1549-p††isbn: 978-1-4503-9413-0/22/11††conference: Proceedings of
the 30th ACM Joint European Software Engineering Conference and Symposium on
the Foundations of Software Engineering; November 14–18, 2022; Singapore,
Singapore††booktitle: Proceedings of the 30th ACM Joint European Software
Engineering Conference and Symposium on the Foundations of Software
Engineering (ESEC/FSE ’22), November 14–18, 2022, Singapore, Singapore††ccs:
Software and its engineering Automated static analysis††ccs: Computing
methodologies Machine learning

##  1\. Introduction

Call graphs construction is crucial for program analyses. Call graphs capture
invocations between functions of programs (Callahan et al., 1990; Ryder,
1979). An ideal call graph is (1) sound, i.e., it does not miss any true
invocations, and (2) precise, i.e., it does not produce any false positives.
However, even for small programs, constructing a sound and precise call graph
is difficult (Ali and Lhoták, 2012). A call graph analysis should make
reasonable trade-offs between soundness and precision. Unfortunately, recent
work (Utture et al., 2022) has found that widely used tools such as WALA (Fink
and Dolby, 2012) or Petablox (Mangal et al., 2015) construct imprecise call
graphs; up to 76% of edges in call graphs constructed by WALA are false
positives.

To address these issues, researchers (Bravenboer and Smaragdakis, 2009; Mangal
et al., 2015; Tan et al., 2016) have proposed to improve pointer analysis,
which is the core of many call graph constructions algorithms, by improving
context-sensitivity or flow-sensitivity of the analysis. Unfortunately, a
perfect pointer analysis is generally not possible (Rice, 1953). Specifically,
pointer analyses usually face an expensive trade-off between scalability and
precision (Li et al., 2018). For example, a context-sensitive analysis by WALA
only reduces 8.6% false positives rate over a context-insensitive analysis
while incurring a large performance overhead (Utture et al., 2022).

A recent approach, which we refer to as cgPruner (Utture et al., 2022),
achieved a breakthrough in improving the quality of call graphs. Instead of
directly improving pointer analysis, cgPruner performs call graph pruning as a
post-processing technique on a call graph constructed through static analysis.
Using machine learning techniques, the call graph pruner removes false
positives in a call graph. Specifically, cgPruner first extracts a set of
_structural_ features from the call graph, e.g., the number of outgoing edges
from the call-site and the in-degree of the callee. It then leverages a
learning model, i.e., Random Forest, to predict if a caller-callee edge is a
false positive (i.e., the caller does not invoke the callee in reality). The
call graph is updated by removing edges that are predicted to be false
positives. Since the cost of generating predictions is low, a machine
learning-based approach does not incur a significant performance overhead.
Their experiments show that cgPruner successfully improves over traditional
call graph analysis by producing call graphs that eliminate a large number of
false positives. However, cgPruner is still limited as it does not consider
source code semantics and thus is not able to distinguish true and false
postives effectively.

Figure 1. The parser.parse call depends on the parameter state. parsers.get
returns an object of one of multiple classes implementing
MathExpressionParser. Throughout the course of the program execution,
acceptState can be invoked with all possible values of state. Therefore,
despite the large number of outgoing edges from the same call site, all edges
to the parse nodes from acceptState in the statically computed call graph are
true edges. However, the large number of outgoing edges is a feature used to
prune false positives, which leads to the incorrect pruning of the edges
related to the parse calls.

In this paper, we propose a novel technique, AutoPruner, that incorporates
both structural and statistical semantic information to prune false positives
in call graphs effectively. AutoPruner combines structural features extracted
from a call graph with semantic features extracted from the source code of the
caller and callee functions. Similar to cgPruner, AutoPruner uses handcrafted
structural features. However, different from cgPruner, AutoPruner
automatically extracts semantic features via deep learning. AutoPruner thus
faces a unique challenge on how to use deep learning to automatically learn
from a limited dataset. To address this, we leverage recently proposed
transformer models of code, i.e., CodeBERT (Feng et al., 2020), that has been
pre-trained on a corpus containing millions of code functions. As our task
differs from CodeBERT’s pre-training task, AutoPruner first fine-tunes
CodeBERT such that it captures the statistical relationships between caller
and callee functions, learning to distinguish between true and false positive
edges based on their source code. Next, AutoPruner leverages the fine-tuned
model to extract semantic features of each edge, based on the source code of
the caller and callee functions. Each edge then has an embedding that
represents the semantic relationship between the caller and the callee. For
each embedding, AutoPruner combines it with the handcrafted structural
features to obtain a representation for each edge. Based on this
representation, AutoPruner employs a neural classifier to classify each edge
in a call graph as a true or false positive.

We evaluate AutoPruner on call graphs produced by three well-known tools,
i.e., WALA (Fink and Dolby, 2012), Doop (Bravenboer and Smaragdakis, 2009),
and Petablox (Mangal et al., 2015), for real-world programs taken from the
NJR-1 benchmark (Palsberg and Lopes, 2018) in the same setting of cgPruner
(Utture et al., 2022). We compare the call graph generated by AutoPruner
against multiple baselines, including the original call graphs produced by
WALA, Doop and Petablox, the call graphs pruned by state-of-the-art approach
cgPruner, as well as a graph neural network model, that applies deep learning
to the call graphs. The latter two baselines consider only structural
information. Our experiments show that AutoPruner improves over the state-of-
the-art approach by up to 13% in F-measure. Our experiments demonstrate that
the use of the semantic features extracted by the transformer-based model
enables AutoPruner to outperform approaches that consider only structural
information.

We investigate the effect of pruned call graphs produced by AutoPruner on
client analyses, which take the call graphs as input to perform other analyses
on the programs. We investigate two client analyses: null pointer analysis and
monomorphic call-site detection. On null pointer analysis, call graphs pruned
by our approach AutoPruner lead to significantly reduced false alarm rate of
only 12% while the call graphs pruned by cgPruner (Utture et al., 2022) and
the call graphs constructed by WALA (Fink and Dolby, 2012) have false alarm
rates in null pointer analysis of 23% and 73%. On monomorphic call-site
detection, AutoPruner improves over cgPruner by over 8% in terms of F-measure.

To better understand AutoPruner, we also perform qualitative analysis on its
performance. We leverage t-SNE (Van der Maaten and Hinton, 2008) to visualize
the embedding of the call graph edges in a two-dimensional space. We find that
the semantic features can separate the true and false-positive edges,
demonstrating that AutoPruner captures a remarkable amount of information from
the source code associated with each call graph edge.

In summary, we make the following contributions:

  * •

We introduce AutoPruner, a novel call graph pruner that uses both code and
structural feature to identify false-positive edges in a call graph.

  * •

We empirically demonstrate that pruned call graph produced by our approach can
help analysis tool significantly improve the false alarm rate and F-measure.
Notably, in the analysis client of null pointer analysis, AutoPruner leads to
over 150 more reported warnings while decreasing false alarm rate from 73% to
12%.

  * •

We perform an ablation study and qualitative analysis to better understand our
approach. Our analysis validates the use of our proposed approach for call
graph pruning.

The paper is structured as follows: Section 2 introduces the background of our
work. Section 3 describes our proposed approach. Section 4 presents our
experimental setup and results. Section 5 discusses our qualitative analysis
and threats to validity. Section 6 covers related work. Finally, Section 7
concludes and describes future directions.

##  2\. Background

In this section, we discuss a motivating example. Next, we present the formal
formulation of the call graph pruning problem and introduce Transformer-based
models of code and CodeBERT (Feng et al., 2020).

###  2.1. Motivating Example

In Figure 1, we present a motivating example to motivate our approach and
demonstrate the limitations of cgPruner that uses only structural features to
prune call graphs. The source code of the acceptState function contains a call
to the parse function. In the original unpruned call graph, the acceptState
node is connected to multiple parse nodes of classes that implement the
MathExpressionParser interface, e.g. the interface is implemented by
EndOfExpressionParser, FunctionLeftParenthesisParser, and other classes that
also override accept. At runtime, the
acceptState function is invoked multiple times with different values of state,
resulting in calls between acceptState and the multiple parse nodes. These
edges in the call graph are true edges as they represent calls that occur at
runtime.

Due to a large number of outgoing edges from the same call site, the local
structure of each acceptState to parse edge in the call graph resembles edges
that are false positives. A structural-only approach such as cgPruner,
therefore, incorrectly prunes all the edges between the acceptState node and
the accept node in the call graph. This highlights the limitation of
considering only the structural features of the call graph and motivates the
need for guiding call graph pruning with the semantics of the source code.
From analyzing the source code, we can correctly identify that a large number
of outgoing edges are possible, as the specific parse call depends on the
parameters of the function. Indeed, AutoPruner correctly leaves the edges
unpruned due to its use of semantic features extracted from the source code by
CodeBERT.

###  2.2. Call Graph Pruning

####  2.2.1. Problem Formulation

In this work, we formulate the call graph pruning problem as below.

Input: A static call graph $\mathcal{G}=(V,E)$ is a directed graph constructed
by a static analysis tool, where $V$ is the set of program’s functions
identified by a function signature and $E$ is the set of edges, i.e., function
calls, in the call graph. Each edge in $E$ is a tuple of (caller, callee,
offset), where caller is the calling function, callee is the called function,
and offset is the call-site in caller.

Output: A pruned call graph $\mathcal{G^{\prime}}=(V^{\prime},E^{\prime})$,
where $V^{\prime}=V$ and $E^{\prime}\subseteq E$

To address this problem, we aim to train a binary classifier $\mathcal{C}$,
which can classify each edge in a call graph $\mathcal{G}$ as true positive,
i.e., the edge represents a true call, or false positive, i.e., the edge does
not represents a true call. Using the classifier’s output, we prune the call
graph following Algorithm 1. We use the classifier $\mathcal{C}$ to classify
each edge in a call graph. Edges classified as false positives are pruned,
while edges classified as true positives are retained.

Input: Call Graph $\mathcal{G}=(V,E)$, Classifier $\mathcal{C}$

Output: Pruned Call Graph $\mathcal{G}=(V^{\prime},E^{\prime})$

1 $\mathcal{G^{\prime}}\leftarrow\mathcal{G}$

2 foreach  _$e$ in $\mathcal{G}$_ do

3 $p\leftarrow\mathcal{C}(e)$ $\triangleright$ prediction of binary classifier

4 if  _$p==$ False-positive_ then

5 $E^{\prime}=E^{\prime}\setminus\\{e\\}$ $\triangleright$ remove edge from
call graph

6

7 end if

8

9 end foreach

return $\mathcal{G^{\prime}}$

Algorithm 1 Call-graph Pruner

####  2.2.2. State-of-the-art

To prune call graphs, Utture et. al. (Utture et al., 2022) recently proposed
cgPruner, which uses a machine learning model, a random forest classifier,
based on 11 structural features extracted from a call graph for pruning edges.
Their experiments demonstrate that cgPruner could successfully boost the
precision of call graphs from 24% to 66% and reduce the false positive rate in
client tool from 73% to 23%. The approach, however, also substantially reduces
the call graph’s recall.

cgPruner relies only on structural features, which can not distinguish false-
positive and true-positive edges that share the same characteristics of
structure (as mentioned in Section 2.1). Similar to cgPruner, our approach,
i.e. AutoPruner, employs a machine learning model to prune call graphs.
However, unlike cgPruner, we use the semantic information from the source code
of both the caller and callee function of an edge in the call graph. The
information from the source code enables our approach to distinguish true-
positive edges from false positive edges (later demonstrated in Section 5.1).

###  2.3. Transformer Models of Code and CodeBERT

Transformer models (Vaswani et al., 2017) are deep learning models based on an
encoder-decoder architecture. Transformer models employ the attention
mechanism and have achieved remarkable performance in field of Natural
Language Processing (NLP) (Vaswani et al., 2017; Kenton and Toutanova, 2019;
Zhuang et al., 2021; Yang et al., 2019; Radford et al., 2019; Brown et al.,
2020). NLP models have also been employed for source code-related tasks, as
source code has been found to exhibit characteristics, such as repetitiveness
and regularity, similar to natural language (Hindle et al., 2016).

Recently, CodeBERT (Feng et al., 2020) was proposed as a Transformer model for
source code. A CodeBERT model is pre-trained on a large corpus, containing
over 6 million functions and 2 million pairs of comment-function. As input,
CodeBERT can be given a pair of data (e.g., source code and a code comment
that describes the semantics of the source code) to learn statistical
relationships between the pair of data. CodeBERT is pre-trained by two tasks,
Masked Language Modeling (MLM) and Replaced Token Detection (RTD). In the MLM
task, given an input sequence with a single token, CodeBERT has to predict the
value of the masked token. In the RTD task, given an input sequence where some
tokens are replaced with alternative tokens, CodeBERT detects the replaced
tokens. Previous studies have demonstrated the effectiveness of CodeBERT in
multiple tasks, including the capability for CodeBERT to be fine-tuned for
tasks that it was not initially trained for (Feng et al., 2020; Zhou et al.,
2021b). Prior studies have been built on top of CodeBERT for automating
various tasks that require an understanding of program semantics, e.g., type
inference (Kazerounian et al., 2021; Hellendoorn et al., 2018; Peng et al.,
2022), program repair (Mashhadi and Hemmati, 2021), etc. Motivated by these
success cases, our proposed solution (AutoPruner) built upon CodeBERT for
another task, namely call-graph pruning. Our solution tries to capture the
semantic relevance of code in the caller function to that of the callee
function to differentiate between true and false edges in a call graph.
Different from cgPruner, AutoPruner analyzes the source code of the functions
while cgPruner ignores them. Moreover, AutoPruner considers both caller and
callee functions while other pure program analysis methods analyze only the
caller function.

##  3\. Methodology

Figure 2. The overview of AutoPruner

Figure 2 illustrates the overall framework of AutoPruner. Before AutoPruner
can be applied, it has to be fine-tuned and trained. First, in the Fine-tuning
phase, we fine-tune a pre-trained CodeBERT model of code to enable it to
extract the semantic features of the edges in a call graph. Next, in the
Training phase, we use the fine-tuned model to extract semantic features for
the edges in the call graph. The semantic features are then combined with
structural features extracted from the call graph to construct the
representation of each edge. Then, we train a feed-forward neural network
classifier to identify false positive edges. Afterward, in the Application
phase, AutoPruner can be used as a call graph pruner for post-processing call
graphs to be used in other program analyses.

###  3.1. Fine-tuning

In this phase, we fine-tune CodeBERT. Before CodeBERT can be used for a task
different from its pretraining task, it has to be fine-tuned to adapt its
weights for the new task. CodeBERT takes a pair of data as input, and in
AutoPruner, we pass the source code of the caller and callee functions
associated with each edge as input. Specifically, AutoPruner uses a
preprocessor that extracts the source code of the caller and callee functions,
constructing a sequence of input tokens that matches the input format expected
by CodeBERT. Then, the sequences are input into CodeBERT for fine-tuning.
Below, we explain each component of the fine-tuning phase in detail.

####  3.1.1. Pre-processing.

The pre-processing step (① in Figure 2) produces the input sequences to
CodeBERT, enabling it to learn a representation of the semantic relationship
between the source code of the caller and callee functions. Initially, from
the call graph constructed by a static analysis tool (e.g., WALA or Doop), an
edge in the call graph is characterized by a pair of function signatures
identifying the caller and callee functions associated with it. We use java-
parser111https://javaparser.org/ to extract the source code of both the caller
and callee functions. Particularly, we parse the source code to obtain the
method descriptors for every methods and matches them against the output of
existing CG generators, which identifies methods using their descriptors. This
allows us to link the source code to the methods in the call graph. Then, we
use CodeBERT tokenizer222https://huggingface.co/microsoft/CodeBERT-
base/tree/main to tokenize the source code. Finally, following the input
format of CodeBERT, we construct an input sequence that encodes the source
code of the caller and callee functions in the form of:

(1) $[CLS]\langle\text{caller's source code}\rangle[SEP]\langle\text{callee's
source code}\rangle[EOS]$

where [CLS], [SEP], and [EOS] are tokens separating the pair of data, as
required by CodeBERT.

####  3.1.2. CodeBERT Fine-tuning.

As the pre-training tasks of CodeBERT, (i.e., the Masked Language Modeling and
Replaced Token Detection tasks) differs from our task (i.e., identifying false
positive edges), we perform a fine-tuning step to adapt the pre-trained
CodeBERT model for our task, following the common practice in transfer
learning (Torrey and Shavlik, 2010; Zhuang et al., 2020) and other
applications of CodeBERT (Zhou et al., 2021b; Mashhadi and Hemmati, 2021;
Applis et al., 2021; Zhou et al., 2021a). This step aims to transfer the
knowledge based on the pre-training task associated with an extremely large
amount of data onto our task where collecting data is expensive (as obtaining
the ground truth labels in our task requires careful human analysis and the
execution of test cases).

We fine-tune the CodeBERT model directly on the training dataset of our task
of identifying false positive edges in the call graph. Specifically, we feed
input sequences in the input format of CodeBERT, obtained from pre-processing
step into the CodeBERT model. Next, the model extract features from the input
sequences. Then, we pass the extracted features into a fully connected layer
to classify each edge in the call graph into true and false positive edges (②
in Figure 2).

During the fine-tuning phase, the parameters of the CodeBERT model are updated
by Adam optimizer (Kingma and Ba, 2015) to minimize the Cross-Entropy Loss.
After this fine-tuning phase, we freeze all parameters of the CodeBERT model.
In the subsequent phases, AutoPruner uses the fine-tuned CodeBERT model to
extract semantic features from the source code of the caller and callee
functions associated with each edge.

###  3.2. Training

In the training phase, our objective is to train the binary classifier that
predicts if a given edge is a true positive or false positive (the Classifier
C in Algorithm 1). To this end, we construct the representation of an edge in
a call graph by extracting and combining features of both types: semantic
features (extracted from the source code by fine-tuned language model) and
structural features (extracted from the call graph). Then, we train a neural
classifier to predict whether an edge is true or false positive. Below, we
explain each component of the pipeline.

Table 1. Types of structural features Feature | Description
---|---
src-node-in-deg | number of edges ending in caller
src-node-out-deg | number of edges out of caller
dest-node-in-deg | number of edges ending in callee
dest-node-out-deg | number of edges out of callee
depth | length of shortest path from main to caller
repeated-edges | number of edges from caller to callee
L-fanout | number of edges from the same call-site
node-count | number of nodes in call graph
edge-count | number of edges in call graph
avg-degree | average src-node-out-deg in call graph
avg-L-fanout | average L-fanout value in call graph

####  3.2.1. Feature Extraction

We extract into a feature set (③ in Figure 2) the two types of features as
follows:

  * •

Semantic features. The semantic features are extracted from the source code of
caller and callee functions using our fine-tuned CodeBERT model. To capture
this information, we first apply the same pre-processing step as described in
the Fine-tuning step (④ in Figure 2). Next, the fine-tuned CodeBERT model
extracts a high-dimensional vector that encodes the statistical relationship
between the caller and callee function (⑤ in Figure 2). As a result, we obtain
semantic features of an edge in call graph as follows:

(2) $f_{sem}=\left\langle
v^{sem}_{1},v^{sem}_{2},...,v^{sem}_{k_{c}}\right\rangle$

where $k_{c}=768$ is the embedding dimension of CodeBERT.

  * •

Structural features. The structural feature captures graphical information
related to each edge. The features include metrics about the neighborhood of
the edge (local information) or the entire call graph (global information). We
use the same features proposed by Utture et al. (Utture et al., 2022).
Detailed information of the features is presented in Table 1. We represent the
structural features of an edge in a call graph as follows:

(3) $f_{struct}=\left\langle
v^{struct}_{1},v^{struct}_{2},...,v^{struct}_{k_{s}}\right\rangle$

where $k_{s}=22$ is the number of structural features. Based on the work by
Utture et al. (Utture et al., 2022), there are two features of each type
listed in Table 1, one for transitive calls and one for direct calls, so we
have 22 structural features.

####  3.2.2. Feature Fusion

In this step, we combine semantic features and structural features of each
edge in the call graph into a final representation. We first use one fully
connected layer for each feature (⑥ in Figure 2). Then, the output of these
layers are concatenated to produce the final representation. More formally,

(4) $f^{\prime}_{sem}=FCN_{k_{c}\times h}(f_{sem})$ (5)
$f^{\prime}_{struct}=FCN_{k_{s}\times h}(f_{struct})$ (6) $f=\left\langle
f^{\prime}_{sem},f^{\prime}_{struct}\right\rangle$

where $FCN_{m\times n}$ denotes a fully connected layer that takes a
$m$-dimensional input and outputs a $n$-dimensional vector. We set $h$, which
is the size of the hidden feature vector, as 32. $k_{c}$ and $k_{s}$ is the
size of semantic and structural feature vector, respectively.

####  3.2.3. Neural Classifier

Given the representation of an edge obtained from feature extraction, we
obtain a score that approximates the probability that an edge is a true
positive.

The score is computed through a feed-forward neural network (⑦ in Figure 2)
consisting of one hidden layer and one output layer. More formally,

(7) $f^{\prime}=FCN_{2h\times 2}(f)$ (8) $prob=OutLayer(f^{\prime})$

where, $FCN_{m\times n}$ denotes a fully connected layer inputs a
$m$-dimensional vector and outputs a $n$-dimensional one, $OutLayer$ is a
softmax function (Goodfellow et al., 2016). $f$ and $f^{\prime}$ are the edge
representation and output features, respectively.
$prob=\\{prob_{FP},prob_{TP}\\}$ is the output probabilities, where
$prob_{FP}$ and $prob_{TP}$ is the probability that an edge is false positive
and true positive, respectively. An edge with $prob_{TP}$ larger than
$prob_{FP}$ is considered as a true positive. Otherwise, the edge are
considered as a false positive.

During the training phase, the parameters of AutoPruner except CodeBERT’s
parameters are updated by Adam optimizer (Kingma and Ba, 2015) to minimize the
cross-entropy loss (Goodfellow et al., 2016).

###  3.3. Application

After the Training Phase, AutoPruner can now be deployed for use as a call
graph pruner. Given a call graph generated by a static analysis tool,
AutoPruner preprocesses the call graph and extracts semantic and structural
features. Based on these features, the neural classifier produces predictions
for each edge in the call graph. Using the predictions of the neural
classifier, AutoPruner removes the edges predicted to be false positives, and
outputs an improved call graph with fewer false positives.

AutoPruner can be integrated into other static analyses (i.e., client
analyses) that takes a call graph as input. Since call graphs pruned by
AutoPruner have fewer false positives compared to the original ones, the
performance of the client analyses should improve given the more precise call
graphs.

##  4\. Empirical Evaluation

###  4.1. Research Question

Our evaluation aims to answer the following research questions:

RQ1: Is AutoPruner effective in pruning false positives from static call
graphs? This research question concerns the ability of AutoPruner in
identifying false positive edges in a static call graph. To evaluate our
approach, we evaluate AutoPruner on a dataset of 141 real-world programs in
NJR-1 dataset (Palsberg and Lopes, 2018) in terms of Precision, Recall, and
F-measure. We compare our approach to multiple baselines, including the state-
of-the-art technique, cgPruner (Utture et al., 2022), as well as a graph
neural network, and the original call graphs produced by static analysis
tools.

RQ2: Can AutoPruner boost the performance of client analyses? This research
question investigates the impact of pruned call graphs produced by AutoPruner
on client analysis. To answer this question, we use pruned call graph as input
for client analyses and investigate its performance compared to original call
graph and cgPruner (Utture et al., 2022) on two client analyses used by
cgPruner: null-pointer analysis and monomorphic call-site detection.

RQ3: Which components of AutoPruner contributes to its performance? AutoPruner
uses multiple types of features, including the semantic features extracted
from both the caller and callee functions, and the structural features
extracted from the call graph. We investigate the contribution of each feature
in an ablation study by dropping each type of feature and observing the change
in AutoPruner’s performance.

###  4.2. Experimental Setup

####  4.2.1. Dataset

To evaluate effectiveness of our approach, we use a dataset of 141 programs,
initially constructed by Utture et al. (Utture et al., 2022), from the NJR-1
benchmark suite (Palsberg and Lopes, 2018). We follow the same experimental
setting as prior work (Utture et al., 2022).

This dataset of programs was curated by Utture et al. (Utture et al., 2022)
based on the criteria that each program has over 1,000 functions, has over
2,000 call graph edges, and has over 100 functions that are invoked at
runtime, and has a high overall code coverage (68%). In total, the dataset
comprises over 860,000 call graph edges. The ground-truth label of each edge
was obtained based on instrumentation and dynamic analysis (Utture et al.,
2022). We use 100 programs as our training set and the remaining programs for
the test set.

####  4.2.2. Evaluation Metrics

We estimate the quality of a static call graph using standard evaluation
metrics: Precision, Recall, and F-measure, which are defined as follows:

(9) $Precision=\dfrac{|S\cap G|}{|S|}$ (10) $Recall=\dfrac{|S\cap G|}{|G|}$
(11) $F-measure=\frac{2\times Precision\times Recall}{Precision+Recall}$

where $S$ and $G$ are the edge set in the static call graph and ground-truth
respectively.

Among these evaluation metrics, Precision is the proportion of edges in call
graph that are true calls. A high Precision is desirable for reducing
developer effort in inspecting false positives (Christakis and Bird, 2016).
Recall refers to the proportion of true edges that are retained in call graph.
Finally, we consider F-measure, which is the harmonic mean of Precision and
Recall. We use F-measure as a summary statistic to capture the tradeoff
between Precision and Recall.

Following previous work (Utture et al., 2022), we compute the average
Precision, Recall, and F-measure for the evaluation set by taking the mean
over Precision, Recall, and F-measure of individual programs. We also report
the standard deviation of each metric.

####  4.2.3. Client analyses

A better static call graph should lead to practical improvements on client
analyses using the call graph. To assess the effect of the improvements to the
call graph from AutoPruner, we run experiments on two client analyses, null
pointer analysis, and monomorphic call-site detection, using the call graph
produced by WALA. To perform a direct comparison, the client analyses selected
are the same as those considered by Utture et al. (Utture et al., 2022). For
each client analysis, we compare AutoPruner against the baseline that produced
the best call graph.

Null pointer analysis. In the first client analysis, we use analysis by Hubert
et al. (Hubert et al., 2008), which is implemented in Wala (Fink and Dolby,
2012), to detect possible null pointer dereferences related to uninitialized
instance fields based on the input static call graph. This analysis is
context-insensitive and field-insensitive. Improving the analysis would reduce
the amount of developer effort spent inspecting false alarms, which is known
to be a barrier to the adoption of bug detection tools based on static
analysis (Johnson et al., 2013). For this client analysis, we refer to
incorrect warnings reported as “false alarms” to distinguish them from “false
positives” from the call graph construction. This analysis is independently
checked by two human annotators to manually determine if the warnings are
false alarms. In cases where the two annotators disagree on the decision, we
involve a third annotator, an author of the paper, for a discussion to reach a
consensus. We report the total number of reported warnings and the false alarm
rate of the null pointer analyzer. As the ground-truth labels of all warnings
are not known, we are not able to compute Recall and, therefore, we do not
compare the approaches on F-measure.

Monomorphic call-site detection. In the second client analysis, the static
call graph is used to detect monomorphic call sites. A call site is
monomorphic when only one concrete function can be invoked. The detection of
monomorphic call sites is useful, for example, for function inlining to reduce
the runtime cost of function dispatch (Utture et al., 2022). A better call
graph would allow us to safely inline more functions, improving the
performance of programs. The ground-truth of this analysis is determined by
running the analysis on the ground-truth call graph. We report the precision,
recall, and F-measure of the monomorphic call site detector.

Table 2. The classification threshold values of cgPruner for different static call graphs Call Graph | WALA | Doop | Petablox
---|---|---|---
Balanced point | 0.4500 | 0.4028 | 0.4279
Default | 0.4500 | 0.5000 | 0.5000

####  4.2.4. Baselines

To assess the effectiveness of AutoPruner, we compare our approach with the
following baselines:

  * •

the original call graphs are call graphs constructed by static analysis tools.
In this work, we consider the 0-CFA static call graphs constructed by three
standard static analysis tools, WALA (Fink and Dolby, 2012), Doop (Bravenboer
and Smaragdakis, 2009), and Petablox (Mangal et al., 2015). The choice of
these three analysis tools follows the previous work(Utture et al., 2022) for
a fair comparison.

  * •

a random baseline that randomly removes $N$% of edges in a call graph. For a
fair comparison, we set $N$ as the percentage of edges that are removed by
AutoPruner.

  * •

cgPruner (Utture et al., 2022) is the state-of-the-art technique in call graph
pruning task. cgPruner constructs a decision tree based on the 11 types of
structural features (listed in Table 1) extracted from the call graphs to
identify false positive edges. We run cgPruner using the paper’s replication
package333https://doi.org/10.5281/zenodo.5177161. cgPruner uses a
classification threshold to determine if an edge is a false positive. A higher
threshold results in higher precision as it accepts only a few edges which are
more likely to be the ground-truth call graph. The threshold enables a trade-
off between precision and recall. We report the result of cgPruner at two
different thresholds. The first is determined based on the “balanced point”,
where the threshold is tuned such that the average precision and recall of the
call graph are equal when evaluated on the test dataset, following the
procedure used by Utture et al. (Utture et al., 2022) to determine the optimal
balance between precision and recall. Note that, in the cgPruner paper, the
”balanced points” are identified using the evaluation dataset. In this paper,
we selected the points using the training dataset to reduce likelihood of
overfitting.
The second threshold is the default threshold obtained from the replication
package. Note that, for WALA, both thresholds share the same value of 0.45, so
we report just one set of results. The thresholds are shown in Table 2.

  * •

GCN (Welling and Kipf, 2016) is an standard, off-the-shelf, graph neural
network (GNN). In this task, we use it perform edge classification. GNNs are
common for machine learning on graph-structured data. As input, we pass the
call graph constructed from static analysis along with 11 types of structural
features described in Table 1. Then, we use the GCN, which considers
information based on the nodes in the neighborhood, to predict if an edge in
the call graph is a false positive.

####  4.2.5. Implementation details

For AutoPruner, we implement the proposed approach using PyTorch library and
the Python programming language. The models are trained and evaluated on two
NVIDIA RTX 2080 Ti GPU with 11GB of graphics memory. For CodeBERT, we fine-
tune the model with a learning rate of 1e-5, following prior works (Zhou et
al., 2021b; Feng et al., 2020) and a batch size of 10 in 2 epochs. We trained
the neural classifier with a learning rate of 5e-6 with a batch size of 50 in
5 epochs.

###  4.3. Experimental Results

####  4.3.1. Effectiveness of AutoPruner

We report the comparison of our approach, AutoPruner against the baselines
approaches. The detailed results are shown in Table 3.

Table 3. Comparison of the effectiveness of AutoPruner with the baselines on
static call graph generated by WALA, Doop, and Petablox.
$\text{{cgPruner}{}}_{bal}$ and $\text{{cgPruner}{}}_{def}$ denotes the result
of cgPruner at balanced point (where the precision and recall are equal on the
test dataset) and default threshold (as provided in replication package),
respectively. For WALA, these thresholds are the same, so we report only one
set of results as cgPruner. The bold and underlined number denotes the best
result for F-measure.

Tool | Technique | Precision | Recall | F-measure
---|---|---|---|---
| $original$ | 0.24 $\pm$ 0.21 | 0.95 $\pm$ 0.14 | 0.34 $\pm$ 0.24
| random | 0.24 $\pm$ 0.21 | 0.48 $\pm$ 0.07 | 0.27 $\pm$ 0.17
WALA | cgPruner | 0.66 $\pm$ 0.19 | 0.66 $\pm$ 0.32 | 0.60 $\pm$ 0.25
| GCN | 0.48 $\pm$ 0.2 | 0.74 $\pm$ 0.37 | 0.54 $\pm$ 0.29
| AutoPruner | 0.69 $\pm$ 0.21 | 0.71 $\pm$ 0.19 |  0.68 $\pm$ 0.19
| $original$ | 0.23 $\pm$ 0.21 | 0.92 $\pm$ 0.14 | 0.33 $\pm$ 0.25
| random | 0.23 $\pm$ 0.22 | 0.46 $\pm$ 0.07 | 0.26 $\pm$ 0.17
| $\text{{cgPruner}{}}_{bal}$ | 0.67 $\pm$ 0.19 | 0.67 $\pm$ 0.30 | 0.61 $\pm$ 0.22
Doop | $\text{{cgPruner}{}}_{def}$ | 0.72 $\pm$ 0.19 | 0.53 $\pm$ 0.32 | 0.54 $\pm$ 0.26
| GCN | 0.49 $\pm$ 0.23 | 0.77 $\pm$ 0.31 | 0.55 $\pm$ 0.25
| AutoPruner | 0.64 $\pm$ 0.24 | 0.75 $\pm$ 0.15 |  0.66 $\pm$ 0.19
| $original$ | 0.30 $\pm$ 0.25 | 0.89 $\pm$ 0.14 | 0.40 $\pm$ 0.27
| random | 0.3 $\pm$ 0.24 | 0.45 $\pm$ 0.08 | 0.31 $\pm$ 0.18
| $\text{{cgPruner}{}}_{bal}$ | 0.67 $\pm$ 0.19 | 0.67 $\pm$ 0.27 | 0.61 $\pm$ 0.20
Petablox | $\text{{cgPruner}{}}_{def}$ | 0.73 $\pm$ 0.19 | 0.52 $\pm$ 0.35 | 0.52 $\pm$ 0.29
| GCN | 0.52 $\pm$ 0.23 | 0.78 $\pm$ 0.28 | 0.58 $\pm$ 0.23
| AutoPruner | 0.67 $\pm$ 0.21 | 0.69 $\pm$ 0.21 |  0.65 $\pm$ 0.18

The evaluation results demonstrate that AutoPruner successfully boosts the
performance of the call graphs produced by WALA, Doop, and Petablox by
0.25–0.34, up to 100% improvement ((0.68-0.34)/0.34) in F-measure. Overall,
the use of AutoPruner led to gains in Precision (up to 178% improvements)
which are substantially larger than the slight losses in Recall (up to just
24%).

With respect to the state-of-the-art baseline, cgPruner, AutoPruner further
improves the baseline by 13% in terms of F-measure for the call graph produced
by WALA. For the call graph of Doop and Petablox, our approach improves over
the optimally balanced cgPruner by 8% and 7%, respectively. The improvements
of AutoPruner over cgPruner in F-measure are statistically significant
(p-value ¡ 0.05) using a Wilcoxon signed-rank test.

Note that the results above, obtained from $\text{{cgPruner}{}}_{bal}$, is
from cgPruner with a classification threshold carefully tuned on the testing
dataset to produce the optimal balance between precision and recall.
Therefore, $\text{{cgPruner}{}}_{bal}$ represents the optimal performance of
cgPruner given the testing dataset. It may not always be possible to obtain
the optimal threshold in practice. Despite that, we observe that AutoPruner
still outperforms cgPruner on call graphs produced by all three static
analysis tools with improvements in F-measure ranging from 7%-13%.

When compared against $\text{{cgPruner}{}}_{def}$, which is not optimally
balanced on the testing dataset and uses the threshold listed in Table 2, the
improvements of AutoPruner are more evident. In terms of F-measure, AutoPruner
outperforms cgPruner by 13%–25% .

Our approach performs better than the GCN baseline by 26%, 20%, and 12% in
terms of F-measure for call graph of WALA, Doop, and Petablox, respectively.
Interestingly, GCN undeperforms cgPruner. Both GCN and cgPruner use only
structural features from the call graph and differ only in the classifiers
used (decision tree versus a graph neural network). This shows that for our
task of call graph pruning, the more complex classifier does not outperform
the simpler classifier. One possible reason for this result is that the
increased complexity of the GCN causes it to overfit the training data.
Overall, AutoPruner outperforming both GCN and cgPruner suggests that the
semantic features used by AutoPruner have predictive power.

Answer to RQ1: Overall, AutoPruner outperforms every baseline approach,
including the state-of-the-art call graph pruner. The call graphs pruned by
AutoPruner improves over the state-of-the-art baseline by up to 13% in F1 when
the baseline is optimally balanced and by up to 25% when it is not. Overall,
AutoPruner outperforms all baselines.

####  4.3.2. Effect on Client Analyses

To investigate the effect of our pruned call graph on the client analyses
(i.e., static analysis tools), we apply our call graph to two client analyses,
i.e., null-pointer analysis and monomorphic call-site detection, following the
experimental setup of prior work (Utture et al., 2022).

Table 4. Comparison of the effectiveness of AutoPruner with the baselines and original call graph on null-pointer analysis. The bold and underline number denotes the best result for F-measure. Techniques | Total warnings | False Alarms Rate
---|---|---
original | 8,842 | 73%
cgPruner | 757 | 23%
AutoPruner | 915 | 12%

Null-pointer analysis. To investigate the impact of AutoPruner in null pointer
analysis, we pass the pruned call graph as input to a null pointer analysis
(Hubert et al., 2008), implemented in WALA. This analysis produces a set of
warnings. Each warning is associated with a code location. If the call graph
is less accurate, the null-pointer analysis produces more false alarms.

To evaluate AutoPruner and the baseline tools, we use the same evaluation
procedure as Utture et al. (Utture et al., 2022) by performing manual analysis
on the reported warnings. Specifically, one author (with four years of coding
experience) and one non-author (with two years of coding experience) annotator
independently manually inspect warnings produced by an analysis (Hubert et
al., 2008) implemented in WALA. A warning is considered a “true alarm” if the
author can trace the backward slice of a dereference to an instance field that
was uninitialized by the end of a constructor (Utture et al., 2022). If
another exception is encountered before dereferencing the null pointer, or if
the label of a warning cannot be verified in 10 minutes or is otherwise
unverifiable by the authors, then the warning is considered a “false alarm”.
This labelling criteria for the human annotators considers only the warnings
produced by the program analysis (Hubert et al., 2008), and therefore, is not
a complete definition of a null pointer dereference. It is designed for a
analysis that is within the cognitive ability of a human annotator to assess
the call graphs produced by call graph pruners. In the cases where the two
annotators disagree on the decision, we involve a third annotator, an author
of the paper (with three years of coding experience), for a discussion to
reach a consensus. Finally, we compute the false alarm rate of null-pointer
analysis by dividing the number of false alarms by the number of warnings. The
results are presented in Table 4. Furthermore, to assess the inter-rater
reliability of the two annotators, we compute Cohen’s Kappa (Cohen, 1960) and
obtained a value of 0.93, which is considered as almost perfect agreement
(Landis and Koch, 1977).

Using the call graph pruned by AutoPruner, the null pointer analysis produces
warnings with a false alarm rate of just 12%. Christakis and Bird (Christakis
and Bird, 2016) suggest that program analysis should aim for a false alarm
rate no higher than 15-20%, which is satisfied by AutoPruner. Meanwhile, both
the original call graph and call graph produced by cgPruner resulted in false
alarm rates higher than 20% (72% and 23% respectively). Our approach has a
false alarm rate that is less than half of the cgPruner’s false positive rate
while reporting 158 more warnings. With respect to the original call graph,
our approach reduces the proportion of false alarms by six times, from 73% to
12%.

Table 5. Comparison of the effectiveness of AutoPruner with the baselines on
monomorphic call-site detection using the call graph produced by WALA, Doop
and Petablox. $\text{{cgPruner}{}}_{bal}$ and $\text{{cgPruner}{}}_{def}$
denotes the result of cgPruner at balanced point (where the precision and
recall are equal) and default threshold (as provided in the replication
package), respectively. For WALA, these thresholds are the same, so we report
only one set of results for cgPruner. The bold and underlined number denotes
the best result for F-measure.

Tool | Techniques | Precision | Recall | F-measure
---|---|---|---|---
| original | 0.52 $\pm$ 0.23 | 0.93 $\pm$ 0.15 | 0.64 $\pm$ 0.21
WALA | cgPruner | 0.68 $\pm$ 0.18 | 0.68 $\pm$ 0.32 | 0.62 $\pm$ 0.25
| AutoPruner | 0.71 $\pm$ 0.22 | 0.72 $\pm$ 0.19 |  0.69 $\pm$ 0.19
| original | 0.51 $\pm$ 0.24 | 0.92 $\pm$ 0.14 | 0.63 $\pm$ 0.22
Doop | $\text{{cgPruner}{}}_{bal}$ | 0.68 $\pm$ 0.19 | 0.71 $\pm$ 0.31 | 0.63 $\pm$ 0.23
| $\text{{cgPruner}{}}_{def}$ | 0.68 $\pm$ 0.21 | 0.56 $\pm$ 0.37 | 0.53 $\pm$ 0.30
| AutoPruner | 0.66 $\pm$ 0.24 | 0.78 $\pm$ 0.16 |  0.69 $\pm$ 0.20
| original | 0.52 $\pm$ 0.23 | 0.9 $\pm$ 0.15 | 0.63 $\pm$ 0.21
Petablox | $\text{{cgPruner}{}}_{bal}$ | 0.68 $\pm$ 0.19 | 0.72 $\pm$ 0.28 | 0.63 $\pm$ 0.21
| $\text{{cgPruner}{}}_{def}$ | 0.73 $\pm$ 0.19 | 0.58 $\pm$ 0.34 | 0.56 $\pm$ 0.26
| AutoPruner | 0.69 $\pm$ 0.21 | 0.75 $\pm$ 0.20 |  0.68 $\pm$ 0.19

Monomorphic call-site detection. In the task of monomorphic call site
detection, the call graph is used to identify call sites where there is only
one concrete call at a code location. As shown in Table 5, for the call graph
constructed by WALA, AutoPruner outperforms the original call graph and
cgPruner in F-measure. AutoPruner outperforms cgPruner by 11% in F-measure,
with improvements in both precision and recall.

We observe similar performances on the call graph of Doop and Petablox. On
Doop’s call graph, AutoPruner outperforms cgPruner by 30% in F-measure.
Compared to the original graph, AutoPruner improves in F-measure by 10%.
Similarly, on the call graph produced by Petablox, AutoPruner improves over
both cgPruner and the original call graph by 8% in terms of F-measure.

Answer to RQ2: The call graph produced by AutoPruner leads to improvements in
both null pointer analysis and monomorphic call site detection. Based on the
call graph from WALA, AutoPruner decreases the false alarm rate from null
pointer analysis by 11%. On monomorphic call site detection, AutoPruner
improves over the state-of-the-art call graph pruner by 11% in F-measure.

Figure 3. The visualization of semantic features produced by CodeBERT in 6
sample programs. The green circles and red triangles represent true positive
and false positive edges respectively.

####  4.3.3. Ablation Study

In answer this question, we investigate two different ablation studies:

  * •

Semantic versus Structure

  * •

Caller versus Callee function

Table 6. Comparison of the effectiveness of the semantic features and the structural features. The bold and underline number denotes the best result for F-measure. Techniques | Precision | Recall | F-measure
---|---|---|---
$\text{{AutoPruner}{}}_{struct}$ | 0.58 | 0.75 | 0.62
$\text{{AutoPruner}{}}_{sem}$ | 0.67 | 0.71 | 0.66
AutoPruner | 0.69 | 0.71 | 0.68

Semantic vs. Structure. In this experiment, we evaluate the relative
contribution of AutoPruner’s semantic versus structural features for call
graph pruning. Table 6 shows the results of our experiments.
$\text{{AutoPruner}{}}_{sem}$ refers to AutoPruner using only the semantic
features extracted from the source code, and $\text{{AutoPruner}{}}_{struct}$,
refers to the AutoPruner using only the structural features. Using only the
semantic features, $\text{{AutoPruner}{}}_{sem}$ outperforms
$\text{{AutoPruner}{}}_{struct}$ in F-measure by 6%. By using with both types
of features, AutoPruner outperforms $\text{{AutoPruner}{}}_{sem}$ by 3% in
F-measure. The decreases in F-measure when either the semantic features or
structural features are removed are statistically significant (p-value ¡
0.05). This indicates that both types of features are important, but
relatively larger decrease in F-measure when removing the semantic features
indicates that the semantic features are more important compared to the
structural features.

Overall, when AutoPruner uses only one type of feature, AutoPruner has a lower
F-measure. This suggests that both semantic and structural features are
important for AutoPruner to perform effectively.

Table 7. Comparison of the effectiveness of the caller features and the callee features. The bold and underline number denotes the best result for F-measure. Techniques | Precision | Recall | F-measure
---|---|---|---
$\text{{AutoPruner}{}}_{caller}$ | 0.69 | 0.60 | 0.58
$\text{{AutoPruner}{}}_{callee}$ | 0.68 | 0.66 | 0.60
AutoPruner | 0.69 | 0.71 | 0.68

Caller vs. Callee. Next, we assess the relative importance of the features
extracted from the caller and callee functions. We evaluate the performances
of AutoPruner when only considering source code from either caller and callee
and compare them with AutoPruner’s. To perform this study, we fine-tuned
CodeBERT with only either the source code of the caller or the callee
function.

$\text{{AutoPruner}{}}_{caller}$ refers to AutoPruner using only the source
code from the caller function, and $\text{{AutoPruner}{}}_{callee}$ refers to
AutoPruner using only the source code from the callee function. AutoPruner
outperforms $\text{{AutoPruner}{}}_{caller}$ and
$\text{{AutoPruner}{}}_{callee}$ by up to 17%. The decreases in F-measure are
statistically significant (p-value ¡ 0.05). This suggests that the semantic
features extracted from the source code of both the caller and callee
functions are crucial for the performance of AutoPruner.

Answer to RQ3: Our ablation study shows that all features contribute to the
effectiveness of AutoPruner. The semantic features are more important than the
structural features, while both the caller and callee functions are essential.

##  5\. Discussion

###  5.1. Qualitative Analysis

In this section, we perform a qualitative analysis of AutoPruner. We have seen
that AutoPruner consistently outperforms the state-of-the-art approach, and
our ablation study indicates that the semantic features extracted by CodeBERT
are essential for the effective performance of AutoPruner. Here, our goal is
to investigate if the pre-trained transformer model of code, i.e., CodeBERT,
is able to separate true positive edges from false positives in the call
graph. To this end, we use t-SNE (Van der Maaten and Hinton, 2008), an
unsupervised method for visualization, to visualize the semantic features from
the call graphs of 6 programs in two-dimensional space. If the semantic
features have predictive power, we would expect the call graph edges, which
are false positives, to be separated from the true positives.

Figure 3 presents the visualizations, where the green and red points are
features of true-positive and false-positive edges, respectively. Indeed, we
observe that the majority of the green points are clustered and are located
relatively close to one another. Furthermore, the clusters of green points are
also typically far away from the majority of the red points. The observation
suggests that CodeBERT was able to be trained to extract semantic features
from the caller and callee function such that the true positives can be
separated from the false positives in the vector space. This validates our use
of a fine-tuned CodeBERT model for extracting semantic features, as the model
demonstrates a remarkable ability to distinguish between true and false
positives.

Still, a small but significant proportion of red and green points are located
close to one another, indicating that using only semantic features is not
enough to separate these edges. This suggests that other features (e.g.,
structural features) should be used to improve the model’s classifier ability.
Indeed, as shown in Section 4.3.3, the structural features are complementary
to the semantic features. The addition of structural features increases the
Precision of AutoPruner by 3% while keeping the same Recall, leading to 3%
improvement on F-Measure. Nevertheless, we acknowledge the modest contribution
of the structural features which may be from how the structural and semantic
features are combined. Currently, after they are independently extracted, they
are combined with a small feed-forward neural network (FFNN). As a result, the
FFNN may fail to capture more complex interactions between the semantic and
structural features.

###  5.2. Efficiency

In this section, we investigate the efficiency of AutoPruner. For pre-training
model, AutoPruner uses an existing pretrained model,
CodeBERT444https://github.com/microsoft/CodeBERT. For the offline fine-tuning
(Section 3.1) and training (Section 3.2) phase wherein both the CodeBERT and
the binary classifier needs to be finetuned and trained only once, AutoPruner
takes around 36 hours. For the inference phase which is integrated in
downstream applications, AutoPruner takes around 0.04 second on average to
predict a label for an edge.

###  5.3. Threats to validity

####  5.3.1. External validity

Threats to external validity concern the generalizability of our findings. Our
experiments are performed on the same dataset as prior work (Utture et al.,
2022), constructed from the NJR-1 benchmark(Palsberg and Lopes, 2018). This
may be a threat to external validity since AutoPruner may not generalize
beyond the programs outside the NJR-1 dataset. However, this threat is minimal
as the dataset consists of a large number of data points, and the NJR-1
benchmark is large and was carefully constructed to ensure their diversity
(Palsberg and Lopes, 2018).

####  5.3.2. Internal validity

Threats to internal validity refer to possible errors in our experiments. In
this study, following the experimental procedure of prior work (Utture et al.,
2022), we perform a manual inspection of null-pointer analysis, which may
introduce human error. To minimize the risk, we asked one author of this paper
and a non-author to independently inspect and label the reported warnings. We
have measured the inter-rater reliability, obtaining Cohen’s kappa of 0.93,
which can be interpreted as almost perfect agreement (Landis and Koch, 1977).
Therefore, we believe that there are minimal threats from this issue.

####  5.3.3. Construct validity

Threats to construct validity relate to the suitability of our evaluation. To
minimize risks to construct validity, we have used the same experimental setup
as a previous study (Utture et al., 2022), including the same dataset and
ground-truth labels. Some bias could be introduced in the construction of the
ground truth. Manual labeling requires extensive human effort, which limits
the scale of the experiments. Hence, we use the same automated labeling
procedure from prior work (Utture et al., 2022) that runs test cases to
identify ground truth edges. The imperfect code coverage of the test cases may
introduce bias. However, the code coverage in our experiments (68%) is higher
than the code coverage of real-world programs (less than 40%) reported in
prior studies (Kochhar et al., 2017).

Another threat to construct validity is the definition of null pointer
analysis of warnings produced by (Hubert et al., 2008). For analyzing static
analysis warnings, prior works often employ a human study with several
annotators (Tomassi and Rubio-González, 2021; Habib and Pradel, 2018). This
human study is expensive and the task given to the annotators must be within
the cognitive ability of humans. To make the annotation task tractable to
humans and reduce its cost, we use the true-alarm identification task
definition used in the prior work(Utture et al., 2022).

##  6\. Related Work

In Section 2, we have discussed the studies related to call graph pruning and
CodeBERT. Here, we discuss other related studies.

Call graph construction has been widely studied. As our approach does not use
runtime information, it falls into the class of static approaches (Murphy et
al., 1998; Utture et al., 2022; Sui et al., 2020; Reif et al., 2019) for
constructing call graphs. Approaches that use dynamic analysis (Xie and
Notkin, 2002; Hejderup et al., 2018) result in fewer false positives but are
less scalable.

Some recent studies on call graph construction have focused on dynamic
languages. Salis et al. (Salis et al., 2021) and Nielson et al. (Nielsen et
al., 2021) present approaches for constructing call graphs of Python programs
and Javascript programs. Unlike language-specific techniques, AutoPruner can
be used to improve call graphs of any language.

There are many client analyses using call graphs. Recently, call graphs have
been used for practical applications, including scanning applications for
vulnerable library usage (Nielsen et al., 2021), generating exploits of
vulnerabilities (Iannone et al., 2021), and impact analysis (Hejderup et al.,
2018). We have explored two classic client analyses, null pointer analysis and
monomorphic call site detection, to validate that the improvements from
pruning the call graph lead to further improvements in practical applications.

Apart from applying CodeBERT to call graph contruction, researchers have
proposed other applications of deep learning models on source code. Other
researchers had success using deep learning models for type inference
(Hellendoorn et al., 2018; Allamanis et al., 2020; Pradel et al., 2020; Peng
et al., 2022), code completion (Hindle et al., 2016; Raychev et al., 2014;
Svyatkovskiy et al., 2019), code clone detection (Saini et al., 2018), program
repair (Mashhadi and Hemmati, 2021; Chen et al., 2019), fault localization
(Nguyen et al., 2022; Lou et al., 2021), among other analyses on source code
(LeClair et al., 2019; Lu et al., 2021; Bui et al., 2021; Nguyen-Truong et
al., 2022). Our work is similar as AutoPruner successfully applies deep
learning techniques on source code analysis, but is unique as previous studies
have not previously applied deep learning to call graph analysis.

##  7\. Conclusion and Future Work

We propose AutoPruner, a novel call graph pruner that leverages both
structural and semantic features. AutoPruner employs CodeBERT to extract
semantic features from both the caller and callee function associated with
each edge in the call graph. Our empirical evaluation shows that AutoPruner
outperforms multiple baselines, including the state-of-the-art approach that
uses only structural features. The improvements from AutoPruner also lead to
tangible improvements on downstream applications. In particular, the
proportion of false alarms reported by a baseline null pointer analysis is
halved, decreasing from 23% to just 12%.

Our ablation study shows that the semantic features complement the structural
features. Moreover, our qualitative analysis reveals that the semantic
features extracted by CodeBERT effectively separate true and false positive
edges.

In the future, we will evaluate AutoPruner on call graphs constructed using
additional static analysis tools and for other programming languages, as well
as assess the impact on call graph pruning on other client analyses. We will
also explore more ways to improve AutoPruner, such as jointly extracting
semantic and structural features, and providing more contextual information by
incorporating the $k$-hop callers (e.g. the caller of the caller) of each
function call to enrich the semantic features. Another interesting direction
is to use AutoPruner for proposing edges in the call graph missing due to an
unsoundness program analysis.

Data availability. AutoPruner’s dataset and implementation are publicly
available at https://github.com/soarsmu/AutoPruner/.

## Acknowledgement

This project is supported by the National Research Foundation, Singapore and
National University of Singapore through its National Satellite of Excellence
in Trustworthy Software Systems (NSOE-TSS) office under the Trustworthy
Computing for Secure Smart Nation Grant (TCSSNG) award no. NSOE-TSS2020-02.
Any opinions, findings and conclusions or recommendations expressed in this
material are those of the author(s) and do not reflect the views of National
Research Foundation, Singapore and National University of Singapore (including
its National Satellite of Excellence in Trustworthy Software Systems (NSOE-
TSS) office).

Xuan-Bach D. Le is supported by the Australian Government through the
Australian Research Council’s Discovery Early Career Researcher Award, project
number DE220101057.

## References

  * (1)
  * Ali and Lhoták (2012) Karim Ali and Ondřej Lhoták. 2012.  Application-only call graph construction. In _European Conference on Object-Oriented Programming_. Springer, 688–712.
  * Allamanis et al. (2020) Miltiadis Allamanis, Earl T Barr, Soline Ducousso, and Zheng Gao. 2020.  Typilus: Neural type hints. In _Proceedings of the 41st acm sigplan conference on programming language design and implementation_. 91–105.
  * Applis et al. (2021) Leonhard Applis, Annibale Panichella, and Arie van Deursen. 2021\.  Assessing Robustness of ML-Based Program Analysis Tools using Metamorphic Program Transformations. In _2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 1377–1381.
  * Bravenboer and Smaragdakis (2009) Martin Bravenboer and Yannis Smaragdakis. 2009.  Strictly declarative specification of sophisticated points-to analyses. In _Proceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications_. 243–262.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020\.  Language models are few-shot learners.  _Advances in neural information processing systems_ 33 (2020), 1877–1901.
  * Bui et al. (2021) Nghi DQ Bui, Yijun Yu, and Lingxiao Jiang. 2021.  Infercode: Self-supervised learning of code representations by predicting subtrees. In _2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE)_. IEEE, 1186–1197.
  * Callahan et al. (1990) David Callahan, Alan Carle, Mary W. Hall, and Ken Kennedy. 1990\.  Constructing the procedure call multigraph.  _IEEE Transactions on Software Engineering_ 16, 4 (1990), 483–487.
  * Chen et al. (2019) Zimin Chen, Steve Kommrusch, Michele Tufano, Louis-Noël Pouchet, Denys Poshyvanyk, and Martin Monperrus. 2019.  Sequencer: Sequence-to-sequence learning for end-to-end program repair.  _IEEE Transactions on Software Engineering_ 47, 9 (2019), 1943–1959.
  * Christakis and Bird (2016) Maria Christakis and Christian Bird. 2016.  What developers want and need from program analysis: an empirical study. In _Proceedings of the 31st IEEE/ACM international conference on automated software engineering_. 332–343.
  * Cohen (1960) Jacob Cohen. 1960\.  A coefficient of agreement for nominal scales.  _Educational and psychological measurement_ 20, 1 (1960), 37–46.
  * Feng et al. (2020) Zhangyin Feng, Daya Guo, Duyu Tang, Nan Duan, Xiaocheng Feng, Ming Gong, Linjun Shou, Bing Qin, Ting Liu, Daxin Jiang, et al. 2020\.  CodeBERT: A Pre-Trained Model for Programming and Natural Languages. In _Findings of the Association for Computational Linguistics: EMNLP 2020_. 1536–1547.
  * Fink and Dolby (2012) Stephen Fink and Julian Dolby. 2012.  WALA–The TJ Watson Libraries for Analysis.
  * Goodfellow et al. (2016) Ian Goodfellow, Yoshua Bengio, and Aaron Courville. 2016\.  _Deep learning_.  MIT press.
  * Habib and Pradel (2018) Andrew Habib and Michael Pradel. 2018.  How many of all bugs do we find? a study of static bug detectors. In _2018 33rd IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 317–328.
  * Hejderup et al. (2018) Joseph Hejderup, Arie van Deursen, and Georgios Gousios. 2018\.  Software ecosystem call graph for dependency management. In _2018 IEEE/ACM 40th International Conference on Software Engineering: New Ideas and Emerging Technologies Results (ICSE-NIER)_. IEEE, 101–104.
  * Hellendoorn et al. (2018) Vincent J Hellendoorn, Christian Bird, Earl T Barr, and Miltiadis Allamanis. 2018.  Deep learning type inference. In _Proceedings of the 2018 26th acm joint meeting on european software engineering conference and symposium on the foundations of software engineering_. 152–162.
  * Hindle et al. (2016) Abram Hindle, Earl T Barr, Mark Gabel, Zhendong Su, and Premkumar Devanbu. 2016.  On the naturalness of software.  _Commun. ACM_ 59, 5 (2016), 122–131.
  * Hubert et al. (2008) Laurent Hubert, Thomas Jensen, and David Pichardie. 2008\.  Semantic foundations and inference of non-null annotations. In _International Conference on Formal Methods for Open Object-Based Distributed Systems_. Springer, 132–149.
  * Iannone et al. (2021) Emanuele Iannone, Dario Di Nucci, Antonino Sabetta, and Andrea De Lucia. 2021.  Toward Automated Exploit Generation for Known Vulnerabilities in Open-Source Libraries. In _2021 IEEE/ACM 29th International Conference on Program Comprehension (ICPC)_. IEEE, 396–400.
  * Johnson et al. (2013) Brittany Johnson, Yoonki Song, Emerson Murphy-Hill, and Robert Bowdidge. 2013.  Why don’t software developers use static analysis tools to find bugs?. In _2013 35th International Conference on Software Engineering (ICSE)_. IEEE, 672–681.
  * Kazerounian et al. (2021) Milod Kazerounian, Jeffrey S Foster, and Bonan Min. 2021\.  SimTyper: sound type inference for Ruby using type equality prediction.  _Proceedings of the ACM on Programming Languages_ 5, OOPSLA (2021), 1–27.
  * Kenton and Toutanova (2019) Jacob Devlin Ming-Wei Chang Kenton and Lee Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In _Proceedings of NAACL-HLT_. 4171–4186.
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba. 2015.  Adam: A Method for Stochastic Optimization. In _ICLR (Poster)_.
  * Kochhar et al. (2017) Pavneet Singh Kochhar, David Lo, Julia Lawall, and Nachiappan Nagappan. 2017.  Code coverage and postrelease defects: A large-scale study on open source projects.  _IEEE Transactions on Reliability_ 66, 4 (2017), 1213–1228.
  * Landis and Koch (1977) J Richard Landis and Gary G Koch. 1977.  The measurement of observer agreement for categorical data.  _biometrics_ (1977), 159–174.
  * LeClair et al. (2019) Alexander LeClair, Siyuan Jiang, and Collin McMillan. 2019\.  A neural model for generating natural language summaries of program subroutines. In _2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE)_. IEEE, 795–806.
  * Li et al. (2018) Yue Li, Tian Tan, Anders Møller, and Yannis Smaragdakis. 2018.  Scalability-first pointer analysis with self-tuning context-sensitivity. In _Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_. 129–140.
  * Lou et al. (2021) Yiling Lou, Qihao Zhu, Jinhao Dong, Xia Li, Zeyu Sun, Dan Hao, Lu Zhang, and Lingming Zhang. 2021\.  Boosting coverage-based fault localization via graph-based representation learning. In _Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_. 664–676.
  * Lu et al. (2021) Shuai Lu, Daya Guo, Shuo Ren, Junjie Huang, Alexey Svyatkovskiy, Ambrosio Blanco, Colin Clement, Dawn Drain, Daxin Jiang, Duyu Tang, et al. 2021\.  Codexglue: A machine learning benchmark dataset for code understanding and generation.  _arXiv preprint arXiv:2102.04664_ (2021).
  * Mangal et al. (2015) Ravi Mangal, Xin Zhang, Aditya V Nori, and Mayur Naik. 2015\.  A user-guided approach to program analysis. In _Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering_. 462–473.
  * Mashhadi and Hemmati (2021) Ehsan Mashhadi and Hadi Hemmati. 2021.  Applying codebert for automated program repair of java simple bugs. In _2021 IEEE/ACM 18th International Conference on Mining Software Repositories (MSR)_. IEEE, 505–509.
  * Murphy et al. (1998) Gail C Murphy, David Notkin, William G Griswold, and Erica S Lan. 1998.  An empirical study of static call graph extractors.  _ACM Transactions on Software Engineering and Methodology (TOSEM)_ 7, 2 (1998), 158–191.
  * Nguyen et al. (2022) Thanh-Dat Nguyen, Thanh Le-Cong, Duc-Ming Luong, Van-Hai Duong, Xuan Bach Le Dinh, David Lo, and Thang Huynh-Quyet. 2022.  FFL: Fine grained Fault Localization for Student Programs via Syntactic and Semantic Reasoning. In _Proceedings of the 38th IEEE International Conference on Software Maintenance and Evolution_. IEEE.
  * Nguyen-Truong et al. (2022) Giang Nguyen-Truong, Thanh Le-Cong, Hong Jin Kang, Xuan-Bach Dinh Le, and David Lo. 2022.  VulCurator: A Vulnerability-Fixing Commit Detector. In _Proceedings of the 30th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_. ACM.
  * Nielsen et al. (2021) Benjamin Barslev Nielsen, Martin Toldam Torp, and Anders Møller. 2021.  Modular call graph construction for security scanning of Node. js applications. In _Proceedings of the 30th ACM SIGSOFT International Symposium on Software Testing and Analysis_. 29–41.
  * Palsberg and Lopes (2018) Jens Palsberg and Cristina V Lopes. 2018.  NJR: A normalized Java resource. In _Companion Proceedings for the ISSTA/ECOOP 2018 Workshops_. 100–106.
  * Peng et al. (2022) Yun Peng, Cuiyun Gao, Zongjie Li, Bowei Gao, David Lo, Qirun Zhang, and Michael Lyu. 2022.  Static inference meets deep learning: a hybrid type inference approach for python. In _Proceedings of the 44th International Conference on Software Engineering_. 2019–2030.
  * Pradel et al. (2020) Michael Pradel, Georgios Gousios, Jason Liu, and Satish Chandra. 2020.  Typewriter: Neural type prediction with search-based validation. In _Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_. 209–220.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019\.  Language models are unsupervised multitask learners.  _OpenAI blog_ 1, 8 (2019), 9.
  * Raychev et al. (2014) Veselin Raychev, Martin Vechev, and Eran Yahav. 2014\.  Code completion with statistical language models. In _Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation_. 419–428.
  * Reif et al. (2019) Michael Reif, Florian Kübler, Michael Eichberg, Dominik Helm, and Mira Mezini. 2019.  Judge: Identifying, understanding, and evaluating sources of unsoundness in call graphs. In _Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis_. 251–261.
  * Rice (1953) Henry Gordon Rice. 1953\.  Classes of recursively enumerable sets and their decision problems.  _Transactions of the American Mathematical society_ 74, 2 (1953), 358–366.
  * Ryder (1979) Barbara G Ryder. 1979\.  Constructing the call graph of a program.  _IEEE Transactions on Software Engineering_ 3 (1979), 216–226.
  * Saini et al. (2018) Vaibhav Saini, Farima Farmahinifarahani, Yadong Lu, Pierre Baldi, and Cristina V Lopes. 2018\.  Oreo: Detection of clones in the twilight zone. In _Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_. 354–365.
  * Salis et al. (2021) Vitalis Salis, Thodoris Sotiropoulos, Panos Louridas, Diomidis Spinellis, and Dimitris Mitropoulos. 2021\.  Pycg: Practical call graph generation in python. In _2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE)_. IEEE, 1646–1657.
  * Sui et al. (2020) Li Sui, Jens Dietrich, Amjed Tahir, and George Fourtounis. 2020\.  On the recall of static call graph construction in practice. In _2020 IEEE/ACM 42nd International Conference on Software Engineering (ICSE)_. IEEE, 1049–1060.
  * Svyatkovskiy et al. (2019) Alexey Svyatkovskiy, Ying Zhao, Shengyu Fu, and Neel Sundaresan. 2019.  Pythia: AI-assisted code completion system. In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 2727–2735.
  * Tan et al. (2016) Tian Tan, Yue Li, and Jingling Xue. 2016.  Making k-object-sensitive pointer analysis more precise with still k-limiting. In _International Static Analysis Symposium_. Springer, 489–510.
  * Tomassi and Rubio-González (2021) David A Tomassi and Cindy Rubio-González. 2021.  On the Real-World Effectiveness of Static Bug Detectors at Finding Null Pointer Exceptions. In _2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 292–303.
  * Torrey and Shavlik (2010) Lisa Torrey and Jude Shavlik. 2010.  Transfer learning.  In _Handbook of research on machine learning applications and trends: algorithms, methods, and techniques_. IGI global, 242–264.
  * Utture et al. (2022) Akshay Utture, Shuyang Liu, Christian Gram Kalhauge, and Jens Palsberg. 2022.  Striking a Balance: Pruning False-Positives from Static Call Graphs.  _The 44rd IEEE/ACM International Conference on Software Engineering (ICSE 2022)_ (2022).
  * Van der Maaten and Hinton (2008) Laurens Van der Maaten and Geoffrey Hinton. 2008.  Visualizing data using t-SNE.  _Journal of machine learning research_ 9, 11 (2008).
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ 30 (2017).
  * Welling and Kipf (2016) Max Welling and Thomas N Kipf. 2016.  Semi-supervised classification with graph convolutional networks. In _J. International Conference on Learning Representations (ICLR 2017)_.
  * Xie and Notkin (2002) Tao Xie and David Notkin. 2002.  An empirical study of java dynamic call graph extractors.  _University of Washington CSE Technical Report_ (2002), 02–12.
  * Yang et al. (2019) Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. 2019\.  Xlnet: Generalized autoregressive pretraining for language understanding.  _Advances in neural information processing systems_ 32 (2019).
  * Zhou et al. (2021b) Jiayuan Zhou, Michael Pacheco, Zhiyuan Wan, Xin Xia, David Lo, Yuan Wang, and Ahmed E Hassan. 2021b.  Finding A Needle in a Haystack: Automated Mining of Silent Vulnerability Fixes. In _2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 705–716.
  * Zhou et al. (2021a) Xin Zhou, DongGyun Han, and David Lo. 2021a.  Assessing Generalizability of CodeBERT. In _2021 IEEE International Conference on Software Maintenance and Evolution (ICSME)_. IEEE, 425–436.
  * Zhuang et al. (2020) Fuzhen Zhuang, Zhiyuan Qi, Keyu Duan, Dongbo Xi, Yongchun Zhu, Hengshu Zhu, Hui Xiong, and Qing He. 2020\.  A comprehensive survey on transfer learning.  _Proc. IEEE_ 109, 1 (2020), 43–76.
  * Zhuang et al. (2021) Liu Zhuang, Lin Wayne, Shi Ya, and Zhao Jun. 2021\.  A Robustly Optimized BERT Pre-training Approach with Post-training. In _Proceedings of the 20th Chinese National Conference on Computational Linguistics_. Chinese Information Processing Society of China, Huhhot, China, 1218–1227.  https://aclanthology.org/2021.ccl-1.108