# Survey of Image Based Graph Neural Networks

###### Abstract

In this survey paper, we analyze image based graph neural networks and propose
a three-step classification approach. We first convert the image into
superpixels using the Quickshift algorithm so as to reduce $30\%$ of the input
data. The superpixels are subsequently used to generate a region adjacency
graph. Finally, the graph is passed through a state-of-art graph convolutional
neural network to get classification scores. We also analyze the spatial and
spectral convolution filtering techniques in graph neural networks. Spectral-
based models perform better than spatial-based models and classical CNN with
lesser compute cost.

Index Terms—  Graph neural network, Superpixels, Quickshift algorithm, Spatial
convolution, Spectral convolution

##  1 Introduction

Deep learning, particularly convolutional neural networks have in the recent
past revolutionized many machine learning tasks. Examples include image
classification, video processing, speech recognition, and natural language
processing. These applications are usually characterized by data drawn from
the Euclidean space. Recently, many studies on extending deep learning
approaches for graph data have emerged [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
13, 14, 15, 16, 17, 18, 19, 20, 21, 22]. The motivation for these studies
stems from the emergence of applications in which data is drawn from non-
euclidean domains and then represented as graphs so as to capture the complex
relationships and inter-dependency between objects. Indeed, many datasets and
associated problems can be more naturally represented and analyzed as graphs
[23]. For instance, graph neural networks (GNNs) have been increasingly used
for applications such as molecule and social network classification [24] and
generation [25], 3D Mesh classification and correspondence [26], modeling
behavior of dynamic interacting objects [27], program synthesis [28],
reinforcement learning tasks [29] and many other exciting problems.

While the utility of graph neural networks for emerging applications is
promising, the complexity of graph data imposes significant challenges on many
existing machine learning algorithms. For instance, in the area of image
processing, the use of Graph Convolutional Network (GCN) is still limited to a
few examples only [14, 10, 11]. By some carefully hand-crafted graph
construction methods or other supervised approaches, images can be converted
to structured graphs capable of processing by GCNs. In these GNNs, each pixel
of an image is considered as a graph node [15] which is cumbersome and in many
cases unnecessary. Instead of learning from individual image pixels, the use
of ’superpixels’ addresses this concern [30, 31] and helps in reducing the
graph size and thereby the computational complexity. Graphs also allow us to
impose a relational inductive bias in data for example via prior knowledge.
For instance, in case of human pose, the relational bias can be a graph of
skeleton joints of a human body [32]. Similarly, in case of videos, relational
bias can be a graph of moving bounding boxes [10, 13]. Another example is
making inferences about facial attributes and identify by representing facial
landmarks as a graph [33]. The literature on application of GNNs on images can
be broadly classified in to three groups (a) pixel-based graphs, (b)
superpixel-based graphs and (c) object-based graphs - sample illustrations of
these three methods are shown in Fig. 1. In addition to providing a
comprehensive review of graph techniques for images’ superpixels, this paper
paper also makes notable contribution by introducing new taxonomy based on how
graph represents an image as summarized in Table 1.

|  |
---|---|---
(a) | (b) | (c)

Fig. 1: An illustration of (a) Pixel-based graph, (b) Superpixel-based graph (c) Object-based graph [34]. Table 1: Classification of Proposals Graph Type | Proposals
---|---
Pixel-based Graph | [2, 15, 16]
Superpixel-based Graph | [30, 31, 17, 16, 18]
Object-based Graph | [3, 19, 20, 21, 34, 22]

##  2 Image Based GNNs

GNNs on images are characterized by unique challenges with respect to their
implementation. Most of the graph neural frameworks [2, 15, 16] are designed
for dense representations such as pixel-based graphs. One can achieve
effective parallelization on irregular sparse graphs (e.g., superpixel-based
graphs) by using fast localized spectral filtering [2] or hierarchichal multi
graph spatial convolutional neural networks [31]. Pixel, superpixel and
object-based graphs have been extensively used in the literature as summarized
in Table 1. For subsequent processing, superpixels have been widely used as an
effective way to reduce the number of image primitives. The literature
includes numerous methods for determining a superpixel representation from an
image, each with different strengths and weaknesses. Recently, many DNN-based
methods to identify superpixels have been proposed [35, 36]. But the most
popular of practices in GNN literature (on account of generally good results
and low compute complexity) are SLIC [37], Quickshift [38] and Felzenszwalb
[39]. Details of these methods are presented in the following.

|  |
---|---|---
|  |
SLIC | Quickshift | Felzenszwalb

Fig. 2: Superpixel segmentation techniques on MNIST digit: 9 and CIFAR-10
image: Ship.

###  2.1 Superpixel segmentation techniques

####  2.1.1 SLIC

The SLIC (simple linear iterative clustering) [37] algorithm simply performs
iterative clustering approach in the 5D space of color information and image
location. The algorithm quickly gained momentum and is now widely used due to
its speed, storage efficiency, and successful segmentation in terms of color
boundaries. However, the limitation of SLIC is that it often captures the
background pixels as shown in Fig. 2 – Column 1, and therefore does not
significantly help in data reduction for graph generation.

####  2.1.2 Quickshift

Quickshift [38] is a relatively recent 2D algorithm that is based on an
approximation of kernelized mean-shift [40]. It segments an image based on the
three parameters: $\epsilon$ for the standard deviation of the Gaussian
function, $\alpha$ for the weighting the color term and $S$ to limit the
calculating a window size of $S\times S$. Therefore, it belongs to the family
of local mode-seeking algorithms and is applied to the 5D space consisting of
color information and image location. One of the benefits of Quickshift is
that it actually computes a hierarchical segmentation on multiple scales
simultaneously. As shown in Fig. 2 – Column 2, it does not capture background
pixels and also reduces $30\%$ of input data for graph generation.

####  2.1.3 Felzenszwalb

This fast 2D image segmentation algorithm, proposed in [39], has a single
scale parameter that influences the segment size. The actual size and number
of segments can vary greatly, depending on local contrast. This segmentation
appeared to be less suitable in tests on a series of images, as its parameters
requires a special adjustment and consequently a static choice of this
parameter leads to unusable results. As shown in Fig. 2 – Column 3, it only
captures the pixels corresponding to the region of interest pixels but
performs poorly in graph generation procedure.

|  |
---|---|---
|  |

Fig. 3: Region Adjacency Graphs (RAG) generation from SLIC, Quickshift and
Felzenszwalb superpixels respectively.

###  2.2 Graph generation from superpixels

This subsection discusses two methods used for generating graphs from
superpixels. These are presented in the following.

####  2.2.1 Region Adjacency Graph (RAG)

After using a superpixel segmentation technique, a Region Adjacency Graph
(RAG) is generated by treating each superpixel as a node and adding edges
between all directly adjacent superpixels. Note that this differs from [41] as
it only connects to adjacent neighbors as compared to KNN. Each graph node can
have associated features, providing an aggregate information based on
characteristics of the superpixel itself. The superpixel segmentation
technique using Quickshift is one way to divide the image into homogeneous
regions. The regions obtained in the segmentation stage are represented as
vertices and relations between neighboring regions are represented as edges.
The search for the most similar pair of regions is repeated several times per
iteration and every search requires $\mathcal{O}(N)$ region similarity
computations. The graph is utilized so that the search is limited only to the
regions that are directly connected by the graph structure. As we can see in
Fig. 3, the representation of an image via a graph $G$, which consists of
superpixels representation $S$, has far fewer nodes in contrast to the grid
representation of the original image. For graph generation, Quickshift (see
Fig. 3 – Column 2) performs well as compared to SLIC and Felzenszwalb.

####  2.2.2 K-Nearest-Neighbors Graph (KNNG)

In a KNN graph, each vertex chooses exactly $K$ nearest neighbors to connect.
Superpixel graphs have connections that span more than one neighbour level,
with edges formed with the $K$ nearest neighbours [41]. For more details on
graph generation, see [41]. For subsequent processing, RAGs have less compute
complexity as compared to KNNG. This is the reason for passing RAGs to a graph
CNN so as to obtain good classification accuracy.

Table 2: Notations for Algorithms

Variable Description Variable Description $\mathcal{E}$ Set of edges
$\mathcal{V}$ Set of vertices $n$ $|\mathcal{E}|$ $m$ $|\mathcal{V}|$
$\mathcal{N}(v)$ Set of neighbors of vertex $v$ ${D_{G}}$ Diagonal matrix of
associated graph (G) $M_{G}$ Region adjacency matrix $W_{G}$ Weighted region
adjacency matrix $L_{G}$ Laplacian Matrix $\\{\lambda_{l}\\}_{l=0}^{n-1}$
Frequencies of graph $U$ Fourier basis $\hat{x}$ The graph Fourier transform
of signal $x$ $h_{\theta}(\Lambda_{G})$ Non-parametric filter $L$ Number of
GNN layers $h_{v}$ Input feature vector of vertex $v$ $h_{v}^{l}$ Hidden
feature vector of vertex $v$ $h_{v}^{L}$ Output feature vector of vertex $v$
$\phi_{v}^{l}$ Node and edge combination feature of layer l

Table 3: Evaluation Results showing comparison between classical CNN as well
as state-of-the-art GCNs.

Input CNN/GCNN Type Model Datasets Accuracy (%) Compute Cost Pixel based RAG
Spectral Convolution Filtering ChebNet [2] MNIST 99.14
$\mathcal{O}(\log(K|\mathcal{E}|))$ ChebNet [2] CIFAR-10 98
$\mathcal{O}(\log(K|E|))$ Superpixel based RAG Spatial Graph Filtering EGCNN
[17] MNIST 98.025 $\mathcal{O}(\log(|\mathcal{V}^{2}|))$ GCN baseline MNIST
86.358 $\mathcal{O}(\log(Kmh_{i}^{l}+Kn{h_{i}^{l}}^{2}))$ EGCNN [17] CIFAR-10
75.230 $\mathcal{O}(\log(\mathcal{V}^{2}\Large))$ GCN baseline CIFAR-10 53.606
$\mathcal{O}(\log(Kmh_{i}^{l}+Kn{h_{i}^{l}}^{2}))$ Image Classical CNN VGG-16
MNIST 99.139 - Image Classical CNN VGG-16 CIFAR-10 93.5 -

###  2.3 Graph Convolutional Neural Network (GCNN)

GCNNs can be broadly classified into two categories: Spectral-based and
Spatial-based Models. Spectral-based models define graph convolutions by
introducing filters from the perspective of graph signal processing [42].
Spatial-based models on the other hand define convolutions by information
propagation. Spatial-based approaches have developed rapidly recently due to
their efficiency, flexibility and generality. They are discussed in the
following section.

Fig. 4: Illustrative examples of our proposed classification approach

####  2.3.1 Spectral Graph Convolutional Neural Networks

Laplacian is the core operator in spectral graph theory. Laplacian matrix is
the most natural form associated with a graph ($G$). Performing spectral
conlvolution on graphs includes four steps as shown in Algorithm 1.

Input: $x$, $D_{G}$, ${M}_{G}$

Output: $L_{G}$, $\hat{x}$, $y$

1 Compute graph Laplacian: $L_{G}\stackrel{{\scriptstyle
def}}{{=}}D_{G}-{M}_{G}$ Weighted adjacency matrix: $W_{G}={M}_{G}D_{G}^{-1}$
Laplacian matrix in normalized form:
$L_{G}=I_{n}-D_{G}^{\frac{-1}{2}}W_{G}D_{G}^{\frac{-1}{2}}$

2 Compute Fourier functions: $L_{G}=U\Lambda U^{T}$

3 Compute Fourier transform: $\hat{x}=U^{T}x\in{\mathbb{R}}^{n}$ and inverse
Fourier transform: $x=U\hat{x}$

Compute spectral convolution:
$\displaystyle\begin{split}y&=h_{\theta}(L_{G})x\\\ &=h_{\theta}(U\Lambda
U^{T})x\\\ &=Uh_{\theta}(\Lambda_{G})U^{T}x\\\ \end{split}$

Algorithm 1 Spectral Graph Convolution Table 4: Quickshift Parameters

Dataset Parameter $\large\bar{N}$ $N_{min}$ $N_{max}$ $\large\bar{deg}$
$deg_{min}$ $deg_{max}$ MNIST $\epsilon=2,\alpha=1,S=2$ 82.1 5 154 6.8 1 101
CIFAR-10 $\epsilon=1,\alpha=1,S=5$ 182 18 624 7.4 1 67

However, there are several issues with this convolutional structure. First,
the eigenvector matrix $U$ requires the explicit computation of the eigenvalue
decomposition of the graph Laplacian matrix, and hence suffers from the
$\mathcal{O}(n^{3})$ time complexity which is impractical for large-scale
graphs. Second, though the eigenvectors can be precomputed, the time
complexity of Algorithm 1 is still $\mathcal{O}(n^{3})$. Third, there are
$\mathcal{O}(n)$ parameters to be learned in each layer. Besides, these non-
parametric filters are not localized in the vertex domain.

To address these limitations, the ChebNet [2] proposed the use of K-polynomial
filters in the convolutional layers for localization. To compute fast spectral
convolutions in $\mathcal{O}(n)$ time, we have to define compact kernels [2].
Let a non-parametric filter, i.e., a filter whose parameters are all free be
defined as

$h_{\theta}(\Lambda)=diag(\theta)$ (1)

where parameter $\theta\in{\mathbb{R}}^{n}$ is a vector of Fourier
coefficients. There are however two limitations with non-parametric filters:
(1) They are not localized in space and (2) Their learning complexity is in
$\mathcal{O}(n)$, the dimensionality of the data. These issues can be overcome
with the use of a polynomial filter [2]:

$h_{\theta}(\Lambda)=\sum_{k=0}^{K-1}\theta_{k}\Lambda^{k},$ (2)

where the parameters $\theta\in{\mathbb{R}}^{K}$ is a vector of polynomial
coefficients. By [2], (2) can be expressed as Chebyshev polynomial

$h_{\theta}(\Lambda)=\sum_{k}\theta_{k}T_{k}(\hat{\Lambda})$ (3)

of order $K-1$, where the parameter $\theta\in{\mathbb{R}}^{K}$ is a vector of
Chebyshev coefficients and $T_{k}(\hat{\Lambda})\in{\mathbb{R}}^{n\times n}$
is the Chebyshev polynomial of order $K$ evaluated at
$\hat{\Lambda}=\frac{2\Lambda}{\lambda_{max}-I_{n}}$, a diagonal matrix of
scaled eigen values that lie in $[-1,1]$.

Input: Superpixels/Node embeddings

Output: Prediction score

1 Each neighbor sends a message:
${\mathbb{m}}_{w,v}^{(l)}=MESSAGE({\mathbb{h}}_{v}^{l-1},{\mathbb{h}}_{w}^{l-1})$

2 Messages are aggregated across all neighbors:
${\mathbb{a}}_{v}^{l}=AGGREGATE({{\mathbb{m}}_{w,v}^{(l)}:w\in\mathcal{N}(v)})$

3 Neighbor information is used to update node representation:
${\mathbb{h}}_{v}^{l}=UPDATE({\mathbb{h}}_{v}^{l-1},{\mathbb{a}}_{v}^{l})$

Prediction based on global readout of node embeddings:
${\mathbb{\phi}}(G)=MLP(\sum_{v\in V}{\mathbb{h}}_{v}^{(L)})$

Algorithm 2 Spatial Graph Convolution

####  2.3.2 Spatial Graph Convolutional Neural Network

In this subsection, we focus on the spatial graph convolutions that propagate
and aggregate the node representations from neighboring nodes in the vertex
domain [42, 17] as shown in Algorithm 2. The most popular implementation of
spatial convolution filtering is given as

$\small{\bf h}_{v}^{l}=\sigma({\bf W}_{1}{\bf h}_{v}^{(l-1)}+{\bf
W}_{2}\sum_{w\in\mathcal{N}(v)}C_{v,w}{\bf h}_{w}{(l-1)})$ (4)

Where $W_{1},W_{2}$ are trainable parameters and $C_{v,w}$ is Normalization
coefficient and structure dependent, i.e., $C_{v,w}=|\mathcal{N}(v)|^{-1}$.

##  3 Experimental Evaluation

We evaluate three models: ChebNet [2], EGCNN [17] and GNN baseline on image
based graph classification dataset: MNIST and CIFAR-10, in comparison with
classical CNN model: VGG-16. ChebNet is spectral-based model while GNN
baseline and EGCNN are spatial-based models. For each dataset there is a set
of graphs with different number of nodes (superpixels) and each graph $G$ has
a single categorical label that is to be predicted. Dataset details,
parameters and metrics are discussed in following subsections.

###  3.1 Datasets

The first dataset is MNIST (Modified National Institute of Standards and
Technology database). It is a large database of handwritten digits from $0$ to
$9$. It consists of $55,000$ training images, $5000$ validation images and
$10,000$ test images. The images are uniform on the scale $28\times 28$ pixels
and have only one color channel with grey values. The other dataset is
CIFAR-10 (Canadian Institute for Advanced Research dataset). It is a large
dataset of $60,000$ color images, each of which is exactly one of $10$
classes: airplane, car, bird, cat, deer, dog, frog, horse, ship and truck. It
consists of $45,000$ training images, $5000$ validation images and $10,000$
test images. The images are uniform size of scale $32\times 32$ pixels and
have three color channels. As shown in Fig. 4, $2$ preprocessing steps are
performed on both of these datasets. The first step is to generate superpixels
using Quickshift [38] (see section 2.1.2) and second step is graph generation
process from superpixels (see section 2.2.1). Using the Quickshift algorithm,
data reduction is approximately $30\%$ of input data i.e. $2150$
characteristics of image graph as compared to the number of features of the
original image ($32\times 32\times 3=3072$).

###  3.2 Parameters and Metrics

Quickshift parameters for MNIST and CIFAR-10 datasets are shown in table 4. We
use Softmax Regression 5 for multidimensional classification problem, that is
the probability distribution of classes $Y$ for the occurrence of input
$\mathbb{x}$. The exponential function in equation 5 highlighted the highest
values and weakened the significant values which are below the maximum.

$softmax(\mathbb{y})=\frac{exp({\mathbb{y}})}{\sum_{i}^{Y}exp({\mathbb{y}}_{i})}$
(5)

The cross-entropy loss is defined over an input set $X$ as

$H(\mathcal{X})=\frac{1}{|\mathcal{X}|}\sum_{x\in\mathcal{X}}(\hat{y}({\mathbb{x}}),log(y({\mathbb{x}})))$
(6)

To evaluate the results of a classification, the accuracy over an input set
$X$ as

$accuracy(\mathcal{X})=\frac{1}{|\mathcal{X}|}\sum_{x\in\mathcal{X}}max(-f+1,0)$
(7)

where $f=|argmax(y({\mathbb{x}}))-argmax(\hat{y}({\mathbb{x}}))|$ and
$argmax(y)=n$ if and only if $y_{n}>=y_{m}$ for $1<=m<=Y$. This describes the
proportion of correctly classified input data from the respective total amount
of training, validation and test data $X$ and is therefore a suitable mean of
determining the quality of classification network.

###  3.3 Quantitative Evaluation

As we can see in table 3, overall spectral-based GNN: ChebNet [2] perform
better than the Embedded GCN model and classical model: VGG-16. Although the
GCN make use of pixel or superpixel based RAG and classical CNN utilizes
original images for classification but the accuracy of ChebNet [2] is better
than all other models with lesser compute cost.

##  4 Conclusion

In this survey paper, we thoroughly reviewed and provided several ways for
image classification utilizing graph neural networks. Our purposed technique
suggests to convert image into superpixels using Quickshift algorithm and then
use superpixles to generate region adjacency graph. For classification task,
this graph is passed through different GNN models. We also analyzed the
spatial and spectral convolutions filtering techniques for classification.
Spectral-based models perform better than spatial-based models and classical
CNN with lesser compute cost.

## References

  * [1] M. Henaff, J. Bruna, and Y. LeCun, “Deep convolutional networks on graph-structured data,” _arXiv preprint arXiv:1506.05163_ , 2015.
  * [2] M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,” in _Advances in neural information processing systems_ , 2016, pp. 3844–3852.
  * [3] A. Jain, A. R. Zamir, S. Savarese, and A. Saxena, “Structural-rnn: Deep learning on spatio-temporal graphs,” in _Proceedings of the ieee conference on computer vision and pattern recognition_ , 2016, pp. 5308–5317.
  * [4] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” _arXiv preprint arXiv:1609.02907_ , 2016.
  * [5] Z. Wang, T. Chen, J. Ren, W. Yu, H. Cheng, and L. Lin, “Deep reasoning with knowledge graph for social relationship understanding,” _arXiv preprint arXiv:1807.00504_ , 2018.
  * [6] V. G. Satorras and J. B. Estrach, “Few-shot learning with graph neural networks,” 2018.
  * [7] M. Narasimhan, S. Lazebnik, and A. Schwing, “Out of the box: Reasoning with graph convolution nets for factual visual question answering,” in _Advances in Neural Information Processing Systems_ , 2018, pp. 2654–2665.
  * [8] H. Hu, J. Gu, Z. Zhang, J. Dai, and Y. Wei, “Relation networks for object detection,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 3588–3597.
  * [9] J. Gu, H. Hu, L. Wang, Y. Wei, and J. Dai, “Learning region features for object detection,” in _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2018, pp. 381–395.
  * [10] X. Wang, Y. Ye, and A. Gupta, “Zero-shot recognition via semantic embeddings and knowledge graphs,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 6857–6866.
  * [11] C.-W. Lee, W. Fang, C.-K. Yeh, and Y.-C. Frank Wang, “Multi-label zero-shot learning with structured knowledge graphs,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 1576–1585.
  * [12] S. Qi, W. Wang, B. Jia, J. Shen, and S.-C. Zhu, “Learning human-object interactions by graph parsing neural networks,” in _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2018, pp. 401–417.
  * [13] K. Marino, R. Salakhutdinov, and A. Gupta, “The more you know: Using knowledge graphs for image classification,” _arXiv preprint arXiv:1612.04844_ , 2016\.
  * [14] M. Kampffmeyer, Y. Chen, X. Liang, H. Wang, Y. Zhang, and E. P. Xing, “Rethinking knowledge graph propagation for zero-shot learning,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 11 487–11 496.
  * [15] M. Edwards and X. Xie, “Graph based convolutional neural network,” _arXiv preprint arXiv:1609.08965_ , 2016.
  * [16] Q. Liu, L. Xiao, J. Yang, and Z. Wei, “Cnn-enhanced graph convolutional network with pixel-and superpixel-level feature fusion for hyperspectral image classification,” _IEEE Transactions on Geoscience and Remote Sensing_ , 2020.
  * [17] M. Fey and J. E. Lenssen, “Fast graph representation learning with pytorch geometric,” _arXiv preprint arXiv:1903.02428_ , 2019.
  * [18] S. Wan, C. Gong, P. Zhong, B. Du, L. Zhang, and J. Yang, “Multiscale dynamic graph convolutional network for hyperspectral image classification,” _IEEE Transactions on Geoscience and Remote Sensing_ , vol. 58, no. 5, pp. 3162–3177, 2019.
  * [19] M. Qi, J. Qin, A. Li, Y. Wang, J. Luo, and L. Van Gool, “stagnet: An attentive semantic rnn for group activity recognition,” in _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2018, pp. 101–117.
  * [20] P. Zhou and M. Chi, “Relation parsing neural network for human-object interaction detection,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2019, pp. 843–851.
  * [21] F. Z. Zhang, D. Campbell, and S. Gould, “Spatio-attentive graphs for human-object interaction detection,” _arXiv preprint arXiv:2012.06060_ , 2020\.
  * [22] J. Tompson, A. Jain, Y. LeCun, and C. Bregler, “Joint training of a convolutional network and a graphical model for human pose estimation,” _arXiv preprint arXiv:1406.2984_ , 2014.
  * [23] N. T. Bliss and M. C. Schmidt, “Confronting the challenges of graphs and networks,” _Lincoln laboratory journal_ , vol. 20, no. 1, 2013.
  * [24] B. Knyazev, X. Lin, and R. Mohamed, “Amer, and graham w taylor. spectral multigraph networks for discovering and fusing relationships in molecules,” in _NeurIPS Workshop on Machine Learning for Molecules and Materials_ , 2018\.
  * [25] M. Simonovsky and N. Komodakis, “Dynamic edge-conditioned filters in convolutional neural networks on graphs,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 3693–3702.
  * [26] M. Fey, J. E. Lenssen, F. Weichert, and H. Müller, “Splinecnn: Fast geometric deep learning with continuous b-spline kernels,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 869–877.
  * [27] T. Kipf, E. Fetaya, K.-C. Wang, M. Welling, and R. Zemel, “Neural relational inference for interacting systems,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 2688–2697.
  * [28] M. Allamanis, M. Brockschmidt, and M. Khademi, “Learning to represent programs with graphs,” _arXiv preprint arXiv:1711.00740_ , 2017.
  * [29] V. Bapst, A. Sanchez-Gonzalez, C. Doersch, K. Stachenfeld, P. Kohli, P. Battaglia, and J. Hamrick, “Structured agents for physical construction,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 464–474.
  * [30] X. Liang, X. Shen, J. Feng, L. Lin, and S. Yan, “Semantic object parsing with graph lstm,” in _European Conference on Computer Vision_. Springer, 2016, pp. 125–143.
  * [31] B. Knyazev, X. Lin, M. R. Amer, and G. W. Taylor, “Image classification with hierarchical multigraph networks,” _arXiv preprint arXiv:1907.09000_ , 2019\.
  * [32] S. Yan, Y. Xiong, and D. Lin, “Spatial temporal graph convolutional networks for skeleton-based action recognition,” in _Proceedings of the AAAI conference on artificial intelligence_ , vol. 32, no. 1, 2018.
  * [33] E. Antonakos, J. Alabort-i Medina, and S. Zafeiriou, “Active pictorial structures,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2015, pp. 5435–5444.
  * [34] Y. Jiang, H. Koppula, and A. Saxena, “Hallucinated humans as the hidden context for labeling 3d scenes,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2013, pp. 2993–3000.
  * [35] F. Yang, Q. Sun, H. Jin, and Z. Zhou, “Superpixel segmentation with fully convolutional networks,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 13 964–13 973.
  * [36] V. Jampani, D. Sun, M.-Y. Liu, M.-H. Yang, and J. Kautz, “Superpixel sampling networks,” in _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2018, pp. 352–368.
  * [37] R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, and S. Süsstrunk, “Slic superpixels compared to state-of-the-art superpixel methods,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 34, no. 11, pp. 2274–2282, 2012.
  * [38] A. Vedaldi and S. Soatto, “Quick shift and kernel methods for mode seeking,” in _European conference on computer vision_. Springer, 2008, pp. 705–718.
  * [39] P. F. Felzenszwalb and D. P. Huttenlocher, “Efficient graph-based image segmentation,” _International journal of computer vision_ , vol. 59, no. 2, pp. 167–181, 2004.
  * [40] D. Comaniciu and P. Meer, “Mean shift: A robust approach toward feature space analysis,” _IEEE Transactions on pattern analysis and machine intelligence_ , vol. 24, no. 5, pp. 603–619, 2002.
  * [41] F. Monti, D. Boscaini, J. Masci, E. Rodola, J. Svoboda, and M. M. Bronstein, “Geometric deep learning on graphs and manifolds using mixture model cnns,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2017, pp. 5115–5124.
  * [42] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu, “A comprehensive survey on graph neural networks,” _arXiv preprint arXiv:1901.00596_ , 2019\.


Towards the Detection of Malicious Java Packages

Piergiorgio Ladisa, Henrik Plate, Matias Martinez, Olivier Barais, Serena Elisa Ponta

Open-source software supply chain attacks aim at infecting downstream users by poisoning open-source packages.
The common way of consuming such artifacts is through package repositories and the development of vetting strategies to detect such attacks is ongoing research.
Despite its popularity, the Java ecosystem is the less explored one in the context of supply chain attacks.

In this paper, we present indicators of malicious behavior that can be observed statically through the analysis of Java bytecode. Then we evaluate how such indicators and their combinations perform when detecting malicious code injections. We do so by injecting three malicious payloads taken from real-world examples into the Top-10 most popular Java libraries from libraries.io.

We found that the analysis of strings in the constant pool and of sensitive APIs in the bytecode instructions aid in the task of detecting malicious Java packages
by significantly reducing the information, thus, making also manual triage possible.

Citing this paper

This is a pre-print of the paper that appears in the Proceedings of the 2022 ACM Workshop on Software Supply Chain Offensive Research and Ecosystem Defenses (SCORED ’22), November 11, 2022, Los Angeles, CA, USA.

If you wish to cite this work, please refer to it as follows:

author={Piergiorgio Ladisa and Henrik Plate and Matias Martinez and Olivier Barais and Serena Elisa Ponta},

booktitle={2022 ACM Workshop on Software Supply Chain Offensive Research and Ecosystem Defenses (SCORED ’22)},

title={Towards the Detection of Malicious Java Packages},

Towards the Detection of Malicious Java Packages

Piergiorgio Ladisa

SAP Security Research
805, avenue du Dr Maurice Donat

University of Rennes 1/INRIA/IRISA
263 avenue du Général Leclerc
35 042

Henrik Plate

SAP Security Research
805, avenue du Dr Maurice Donat

Matias Martinez

Université Polytechnique Hauts-de-France
Campus Mont Houy

Olivier Barais

University of Rennes 1/INRIA/IRISA
263 avenue du Général Leclerc
35 042

Serena Elisa Ponta

SAP Security Research
805, avenue du Dr Maurice Donat

Open-source software supply chain attacks aim at infecting downstream users by poisoning open-source packages.
The common way of consuming such artifacts is through package repositories and the development of vetting strategies to detect such attacks is ongoing research.
Despite its popularity, the Java ecosystem is the less explored one in the context of supply chain attacks.

In this paper we present indicators of malicious behavior that can be observed statically through the analysis of Java bytecode. Then we evaluate how such indicators and their combinations perform when detecting malicious code injections. We do so by injecting three malicious payloads taken from real-world examples into the Top-10 most popular Java libraries from libraries.io.

We found that the analysis of strings in the constant pool and of sensitive APIs in the bytecode instructions aid in the task of detecting malicious Java packages
by significantly reducing the information, thus, making also manual triage possible.

<concept_desc>Security and privacy Malware and its mitigation</concept_desc>

[500]Security and privacy Malware and its mitigation

§ INTRODUCTION

Today's software supply chains make extensive use of open-source components.
Despite the clear advantages, the lack of transparency and reliance on unknown
stakeholders and systems pose several risks.

OSS supply chain attacks are characterized by the injection of malicious code into
open-source components as a means for spreading malwares <cit.> and there exist many attack vectors <cit.>.
Package repositories for OSS (e.g., npm, PyPI, Maven Central) are commonly used by downstream users to consume OSS packages and several scientific works focus on vetting mechanisms at scale. Most of those tackle interpreted languages (e.g., JavaScript, Python), whereas the Java ecosystem is less explored despite its popularity <cit.> .

Based on the study of real-world attacks, our goal is to find and evaluate indicators of malicious
behavior in Java packages. Since the usual way of consuming the latter is through pre-compiled JARs, we focus on Java bytecode. Indicators of malicious behavior can be used by package repositories vetting the submitted packages or by downstream users checking the downloaded dependencies.

We set out to answer the following research questions:

RQ1 – What are some of the possible indicators of malicious behavior that can be observed from the bytecode?

RQ2 – How do these indicators and their combinations perform in the detection of malicious Java packages?

To answer those questions we analyze both the constant pool (e.g., to detect obfuscated strings) and bytecode instructions (e.g., to detect sensitive APIs). We assess the performance of the identified indicators by analyzing the Top-10 Java projects from libraries.io[<https://libraries.io/>], both the original, benign ones as well as infected ones, containing malicious payloads taken from three real-world attacks.

The remainder of the paper is organized as follows.
Section <ref> presents related works.

Section <ref> motivates the need for improving the detection of malicious JARs in the context of OSS supply chain attacks.

Section <ref> describes background information.
Section <ref> presents our static analysis of JVM bytecode and answers to RQ1.
Section <ref> answers RQ2 by evaluating the indicators of malicious behavior in the Java bytecode.
Section <ref> discusses the limitations of our approach, while Section <ref> highlights the conclusions and discusses future works.

§ RELATED WORKS

Table <ref> shows work to date about the detection of malicious open-source packages.

Sejfia et al. <cit.> propose a machine learning-based approach for the automated detection
of malicious npm packages trained on a labeled dataset. We port some of the considered features in the context of Java,
in particular the concept of sensitive APIs (e.g., process creation, dynamic code generation) and the usage of Shannon entropy to detect obfuscation. While they apply the latter at the file level to detect the presence of compiled or minified code, we apply it to the strings found in the Java class file's constant pool.

Vu et al. <cit.> analyze the discrepancy between source code and the deployed package in PyPI as a way to detect malicious injections in the Python ecosystem. Scalco et al. <cit.> perform the same in the context of JavaScript. Conversely, we do not consider the source code.

Duan et al. <cit.> propose a classifier based both on dynamic and static analysis to classify packages in npm, PyPI, and RubyGems. Among the selected features for the static analysis, they also suggest considering sensitive APIs and to perform data flow analysis to highlight dangerous flows.

Ohm et al. <cit.> leverage sandboxes to collect forensic artifacts related to the execution of malicious JavaScript and Python packages
and describe the observed dynamic behaviors. In another work <cit.> they propose a clustering model based on signatures
produced from the AST of malicious JavaScript samples. Our approach is instead only static and focuses on Java.

Garret et al. <cit.> propose an anomaly detection approach based on the observation of code features in JavaScript (e.g.,
opening of connections, read/write to the file system).

Fass et al. <cit.> extract features from the AST of JavaScript codes to build a classifier capable
of detecting obfuscation.

In the scope of Java malware detection, related works focus on the detection of malicious code in applets or purely malicious JARs.

Schlumberger et al. <cit.> propose a static approach for applets based on
machine learning. Among the selected features they consider sensitive APIs (e.g., for obfuscation and code behavior).
Compared to their work, our focus is on OSS packages that may contain a small portion of malicious code, while malicious applets do not need to piggyback
on existing benign functionalities. In addition, some of the APIs for applets are not relevant in the scope of Java libraries (e.g.,
APIs for MIDlets).

Pinheiro et al. <cit.> propose a dynamic approach for the automated detection of malicious JARs. They extract forensic features related to the execution of purely malicious samples in a sandboxed environment to train a classifier based on artificial neural networks. Instead, we perform a static analysis of packages where malicious code was injected.

Other relevant works come from the Android ecosystem <cit.>, especially the ones about the static inspection of Dalvik bytecode.
In this case, Aafer et al. <cit.> analyze Android malware samples to extract their commonly used APIs, then build a KNN classifier. As opposed to their work, not having many malicious samples available, our search for relevant APIs is based on the manual inspection of malicious packages.
Specific aspects of the Android ecosystem make the problem of detecting malicious Java libraries different. On the one hand, because malware running on mobile devices has different objectives, e.g., financial gain by sending SMS or reading contacts. On the other hand, there are technical differences between Java for Android and for the JVM (e.g., permissions, intents, or APIs existing only for Android).

1lReference   1lYear     1l[origin=c]57Ruby     1l[origin=c]57Python      1l[origin=c]57JavaScript     1l[origin=c]57Java$^*$
(lr)1-2 (lr)3-6

1lSejfia et al. <cit.>    1c2022    1c     1c      1c     1c

1lScalco et al. <cit.>    1c2022     1c     1c      1c     1c

1lDuan et al. <cit.>    1c2021     1c     1c      1c     1c

1lVu et al. <cit.>    1c2021     1c     1c      1c     1c

1lOhm et al. <cit.>    1c2020     1c     1c      1c     1c

1lOhm et al. <cit.>    1c2020     1c     1c      1c     1c

1lGarret et al. <cit.>    1c2019     1c     1c      1c     1c

1lFass et al. <cit.>    1c2018     1c     1c      1c     1c

Ecosystems covered by recent scientific works on the detection of malicious open-source packages. ($^*$): here we intend the case of JVM bytecode

§ MOTIVATION

This section motivates our work by presenting OSS supply chain attacks and reports on the detection capabilities of popular AVs.

§.§ Open-Source Software Supply Chain Attacks

[language=Java, label=lst:backstabbed1, caption=Malicious code snippet from HttpServlet.java contained in
protected void doGet(HttpServletRequest req)
throws ServletException, IOException
.exec("bash -c echo,YmFz**SHORTENED**JjE=

OSS supply chain attacks target open-source components as a means of spreading malware.
As Ladisa et al. <cit.> pointed out, there are many possible attack vectors.

As demonstrated by multiple examples of malicious OSS packages <cit.>,
most of them prove to have a small fraction of harmful code hidden in a bigger corpus of legitimate code. This is similar to the case of piggybacking in Android malwares, where a legitimate application (carrier) is repackaged by grafting a malicious code (rider) <cit.>.

Listing <ref> shows the malicious code snippet
present in the package<EMAIL_ADDRESS>Its source version consists of 149 files,
77 of which are in java format and a total of 13458 LOC.
The malicious payload is present in only one line of code of the file HttpServlet.java, which consists of a total of 749 LOC.

§.§ VirusTotal Scan

Percentage of antivirus softwares detecting the malicious samples provided, compared per-ecosystem.

To understand the level of detection by common AVs we submitted the 2886 samples available in the BKC <cit.> (813 Ruby samples, 261 in Python, 1807 in JavaScript,
and 4 in Java) to VirusTotal[<https://www.virustotal.com>] (as of July 2022). The latter offers the possibility to inspect files or hashes with over 70 AV softwares.

Figure <ref> depicts the percentage of responses provided by all the AVs accessible through the VirusTotal API. The results show the average calculated per ecosystem.

Ruby is the ecosystem with the highest percentage of AVs correctly recognizing malicious packages.
$18\%$ of AVs flagged the samples as malicious, while $60\%$ responded with undetected
and $1\%$ reached a timeout during the scan.

In the case of Python, $2\%$ of antiviruses flagged the samples as malicious, while $76\%$ responded undetected.

For JavaScript, $1\%$ of AVs flagged the samples as malicious, $1\%$ reached a timeout when processing
the samples, while $77\%$ responded undetected.

For Java, only one sample out of 4 was recognized as malicious by 9 AVs. On average, 3% of AVs responded with malicious, 79% with undetected, and 1% reached a timeout.

Over the total dataset, $\sim21\%$ of antiviruses do not support the file formats, $72\%$ do not detect the samples, and only the $6\%$ correctly categorized the packages as malicious.

Considering the reporting year of the packages that no AV flagged as malicious, we observe that 278 malicious packages were reported more than two years ago and 45 are older than 5 years, and still, they are not detected by AVs.

These observations highlight the need for AV softwares to improve the detection of malicious code in open-source components.

Indexing mechanism in the constant pool.

§ BACKGROUND

This section describes the Java class file format and highlights the main features of malwares in the scope of OSS supply chain attacks.

§.§ Java class file format

In the JIT compilation, the Java source code is compiled into a class file, which contains a platform-independent intermediate representation that is transformed into machine code by the JVM.

Each bytecode instruction consists of a one-byte opcode followed by zero or more bytes for the operands <cit.>.

When the operands are constants, they are represented by symbolic information contained in the constant pool. The latter act as a symbol table and each element is characterized by index, type, and value.
Constant pool entries of type  hold constant string values.
Constants with types such as , , or  contain instead the index value pointing to the associated  entry.

Figure <ref> shows an example of such an indexing mechanism.

§.§ Malwares Categories

Primary objectives in OSS supply chain attacks
are reverse shell, dropper, data exfiltration, DoS, and financial gain <cit.>.

Reverse shell spawns a shell process and redirects both its input and output through an open socket to the attacker machine.

Droppers connect to an attacker-controlled host to download a second-stage payload that will be then executed. The remote payload can be read directly through the connection or be temporarily stored in a local file.

Data exfiltration (most common behavior <cit.>) reads
sensitive files as well as environmental information and sends it to a remote endpoint.

DoS is typically achieved either through resource exhaustion (e.g., fork-bombs) or by deleting system files.

Financial gain is achieved by executing crypto miners in the target system. We consider the case of stealing cryptocurrencies belonging to the category of data exfiltration.

1l     5cBehaviors

1lClasses     1lExecution     1lConnection      1lFile Input     1lFile Output     1lReading Environment
(lr)1-1 (lr)2-6

1lReverse Shell     1c     1c      1c     1c     1c

1lDropper     1c     1c      1c     1c     1c

1lData Exfiltration     1c     1c      1c     1c     1c

1lDoS     1c     1c      1c     1c     1c

1lFinancial Gain     1c     1c      1c     1c     1c

Behaviors required by malwares in our scope to achieve their primary objectives.

§ INDICATORS OF MALICIOUS BYTECODE

Description of the static analysis of a JAR for the detection of malicious bytecode.

This section highlights the main observations from the manual inspection of malwares, then presents the indicators for the detection of malicious code at the bytecode level (Figure <ref>).

§.§ Manual Malwares Inspection

To find relevant indicators of malicious JARs, we start by inspecting the four Java samples from the BKC <cit.>. Two of them are different versions of the same package, and their malicious payload is identical.
Because of the scarcity of malware samples in Java, we also analyzed some examples written in other programming languages and ported their code to Java.

We observe that the strings contained in the malwares may contain shell commands, URLs, or paths to sensitive files either in an encoded format (e.g., base64) or unencoded.

The inspection of the Java samples and ported versions from other languages also allowed us to collect some of the Java APIs required to implement the malicious functionalities.
We augment such a list by searching in the Java SE documentation <cit.> for similar APIs to accomplish the same tasks. We categorize the sensitive APIs according to the behaviors (cf. Table <ref>) used by the malwares types described in Section <ref>.
The entire list of Java APIs is available in Table <ref>, Appendix <ref>.

We also observe that in many samples the malicious code is included in a single method and usually within a try block associated with an empty catch. This suggested us to implement an intra-procedural data-flow analysis and look for such try-catch blocks.

§.§ Constant Pool Analysis

Since malwares can contain hardcoded strings, the extraction and analysis of strings is a common practice in malware analysis to obtain evidence about malicious behavior  <cit.>.

In our work, we extract strings from the constant pool of each class composing the analyzed JAR using the indexing mechanism described in Section <ref>. In the following we present different approaches to detecting suspicious strings, highlighting their benefits and limitations.

§.§.§ Entropy Analysis

In information theory, entropy measures the average level of information
associated with the possible outcomes of a random variable <cit.>.

To detect the presence of obfuscation (e.g., base64) we measure the Shannon entropy of each string (independent of one another). In fact, obfuscated strings usually have higher entropy than their unencoded counterpart due to their higher variability.
For example,  has an entropy value of 2, while
its base64 encoding (i.e., ) has a value of 2.75.
However, short strings and small alphabets (e.g., base16), due to their low variability, could lead the Shannon entropy approach to fail to identify malicious strings.

Since the constant pool often contains log messages for the user, usually in English, we also consider a filtering mechanism based on a measure of relative entropy, such as the Kullbac-Leibler divergence <cit.>.
The latter measures the distance between two probability distributions.

In our context, we measure the distance between the probability distribution of the characters of a supplied string and the one of the characters in the English language.
This approach is limited to detecting phrases in English and, additionally, URLs containing English words (e.g., domain names) would be filtered out because they have a probability distribution similar to the one of the English language.

§.§.§ Language-Based Filtering

To solve the problem of filtering out strings that resemble sentences we also consider a probabilistic detection of the language by using the Compact Language Detector (CLD2) <cit.>.
The main benefit of this approach, compared to the one based on the relative entropy described above, is that in this case, we would also remove output messages in languages other than English.

Before checking the detection value of a given string, we make it lowercase, tokenize it with NLTK[<https://www.nltk.org/>], and remove all the non-alphanumerical characters and the duplicates. Two examples are provided in Listing <ref>, Appendix <ref>.

If a language is detected, then the string is filtered out. Thus, we consider suspicious those where the language detection failed.

§.§.§ Sensitive Keywords

From the inspection of the BKC we observe that many payloads contain keywords related to bash commands (e.g., ) or sensitive file paths (e.g., , ) <cit.>. Those are strong indicators of malicious behavior.

To detect such keywords we have built an extensive list from offensive security cheat sheets <cit.>.
It covers the most popular ways of creating reverse shells, e.g., via bash, netcat, python, or perl. Regarding data exfiltration, it also covers common directories used when testing for LFI vulnerabilities, e.g., .
Also included are popular domains used for IP lookups (e.g., whatismyip.org), and the keywords  and  to detect URLs.

The entire corpus of 178 keywords is stored in unencoded format, in different encodings (base64, base32, base16, a85, b85, rot-13, uuencode and url-encoding), and in reverse order (e.g.,  for ).
When analyzing given JARs, we search for the presence of those keywords in constant pool strings.

§.§ Bytecode Instructions Analysis

The analysis of bytecode instructions aims at collecting pieces of evidence of malicious behavior from the operations of a Java program.

§.§.§ Sensitive APIs

As described in Section <ref>, the malwares in scope require execution, networking, file I/O, and the
read environment information to achieve their goal.
Using the list of sensitive Java APIs related to these behaviors presented in Section <ref> (cf. Table <ref>, Appendix <ref>), we inspect the bytecode instructions to detect their invocation (e.g., via  or ).
In our analysis we only consider native Java APIs to evaluate if this is sufficient to detect the malicious samples.

Execution APIs provides the ability to run shell commands or to evaluate scripts, possibly in other languages than Java <cit.>. These APIs potentially allow any shell command to be executed. Therefore, an attacker can achieve any malicious behavior through these methods as long as the specified payload is compatible with the system executing it.

Connection APIs provide networking capabilities. They allow the creation of sockets and the redirection of inputs and outputs in the case of a reverse shell. Droppers need also to connect to remote servers to download second-stage payloads.
A connection is also required for data exfiltration to send the stolen information to the attacker.

Dynamic Programming APIs leverage Java reflection <cit.> to load classes and execute their methods at runtime. From the perspective of droppers, an attacker can host a malicious class remotely and have the victim use it via reflection. Reflection makes it harder for the static analyzer to detect the presence of critical APIs.

Encoding and Cryptographic APIs can be used to obfuscate code in order to evade detection by AVs.

Nearly half of the samples of the BKC use this technique, the most common encoding being Base64 <cit.>.

Evironment Reading APIs are relevant in the case of data exfiltration, e.g., to read environment variables, user name, or hostname.

§.§.§ Empty Catch Clauses

Most API calls listed in Table <ref>, Appendix <ref> throw exceptions to the runtime system <cit.>.

To not alert the victim with a message in case of error or halt program execution altogether, malware developers often include the malicious code within a try block associated with an empty catch block
(cf. Listing <ref>, Appendix <ref>).

Therefore, for each class, we report all the empty catch blocks and in which method they are present. We then scan the instructions of the corresponding try block to search for the presence of sensitive API calls.

§.§.§ Data Flow Analysis

To increase confidence in detecting malicious JARs, we complement the detection of sensitive APIs with data flow analysis.
The goal is to detect cases where malicious payloads flow into sensitive APIs. We carry out an intra-procedural analysis (implemented with ASM <cit.>) by interpreting the instructions and by simulating the JVM stack. Once we reach the sensitive API we check the top of the stack to extract the value of the payload.

[enhanced,breakable,arc=0mm, title=Response to RQ1]
We consider the following indicators as relevant from a security perspective.

Constant pool: the presence of high-entropy strings, sensitive keywords (e.g., shell commands), and strings for which no language can be determined.

Bytecode instructions: the presence of sensitive APIs (execution, networking, file i/o, environment reading, dynamic programming, and encoding/cryptographic), especially in combination with empty catch clauses and the use of string literals defined in the same respective method.

§ EXPERIMENT

In this section, we describe the experiment to assess the effectiveness of the simple indicators described in Section <ref> for the detection of malicious Java bytecode.

§.§ Setup

Figure <ref> shows an overview of the experiment.
We select the Top-10 most popular projects from libraries.io,
which at the time of writing (July 2022) are: , , , , , , , , , and .

We artificially created infected versions of the latest version of each project as follows.
We convert the three malicious Java code excerpts (payloads) from BKC in bytecode using ASMifier <cit.>. We refer to Listing <ref> as Payload 1 (P1), Listing <ref> as Payload 2 (P2), and Listing  <ref> as Payload 3 (P3).
Then, we extract the JARs of the benign packages, randomly select a class file,  add the payload via bytecode injection at the beginning of the first available method in the class, and re-create the archives.
Therefore the final set of packages consists of 40 JARs: the 10 Original versions (O) and the 30 versions infected with P1, P2, and P3 respectively.

P1 uses an execution API to run a bash command that decodes a base64 string and executes its content. This payload is placed in a try block associated with an empty catch.

P2 uses reflection to dynamically invoke the content of a malicious class that is hosted and read directly from the internet. This payload does not have an empty catch clause.

P3 downloads a Groovy script, stores it in a local file, and executes its content. Similarly to P1, also P3 is placed in a try block associated with an empty catch clause.

The original JARs and the infected ones are analyzed as described in the following section. The "JAR scanner" component in Figure <ref> applies the analyses described in Section <ref>.

Experiment to assess the analysis of malicious Java bytecode.

§.§ Analysis

We evaluate the capabilities of the indicators of Section <ref> and their combination to recognize malicious JARs.

§.§.§ Constant Pool

1l     1cPS
1cP     1cR     1cbA
1cP    1cR     1cbA
1cP    1cR     1cbA
1cP    1cR     1cbA
1cP    1cR     1cbA
1cP    1cR     1cbA

(lr)2-2 (lr)3-5 (lr)6-8 (lr)9-11 (lr)12-14 (lr)15-17 (lr)18-20

1lP1:     1c1
1c.003      1c1.0     1c.738
1c.005      1c1.0     1c.847
1c.013     1c1.0     1c.933
1c.239     1c1.0     1c.996

1c.453     1c1.0     1c.998
1c.157     1c1.0     1c.989

1lP2:     1c3
1c.006      1c.667     1c.572
1c.004     1c.30     1c.525
1c.013     1c.333     1c.559
1c0.0     1c0.0     1c.498

1c0.0    1c0.0     1c.498
1c.157    1c.333     1c.662

1lP3:     1c2
1c.006      1c1.0     1c.738
1c.004     1c0.45     1c.571
1c.013     1c.5     1c.683
1c.239     1c.5     1c.746

1c.453     1c0.5     1c.749
1c.157     1c.5     1c.739

Average results of different filtering mechanisms applied to strings in the constant pool. In red are the worst results; in bold are the best ones. PS: number of strings introduced by the malicious payload. For each filtering mechanism we present the precision (P), recall (R), and balanced accuracy (bA).
LC: language detection applied to all strings.
SH: filter based on Shannon entropy at JAR (SH$_{J}$) and class (SH$_{C}$) level.
SH+KL: Shannon-based filter combined with Kullbac-Leibler divergence using thresholds of 2 and 10.
SH+LC: Shannon-based filter combined with language detection.

We evaluate the efficiency of different combinations of filtering methods (cf. Section <ref>) and
Table <ref> shows the average results for all the infected packages.

First, we evaluate the removal of strings that are recognized as sentences by the language detector (cf. column LC).
Secondly, we evaluate the removal of strings characterized by a Shannon entropy below the third quartile computed in two cases: at JAR and the class level (cf. columns SH$_{J}$ and SH$_{C}$, resp.).
On the total of 30 infected packages, we observe that filtering at the class level performs better than at the JAR level: SH$_{J}$ globally shows lower precision, recall, and accuracy than SH$_{C}$.
Finally, we combine SH$_{C}$ and LC with two methods for the removal of output messages: the one based on Kullbac-Leibler divergence (using thresholds of 2 and 10) and the other based on language detection.

For P1 and P3, the Shannon-based filter at the class level associated with Kullbac-Leibler using a threshold of 10 (cf. column SH$_{C}$+KL$_{10}$) reduces most strings without removing those belonging to the malicious injection. However, the filter based on relative entropy misses the significant strings of P2 (i.e., the URL). This happens because the probability distribution of an URL containing a domain (e.g., ) rather than an IP address is comparable with the one of English characters.
Therefore, the best trade-off between precision, recall, and accuracy is offered by the Shannon filter at the class level combined with language detection (cf. column SH$_{C}$+LC) and is adopted in the subsequent analysis.

Except for the LC case, which retains 2 of the 3 strings added by P2, the recall value is low for P2 and P3. This is because strings such as  (cf. Listing <ref>) or  (cf. Listing <ref>) have a low Shannon entropy and thus are filtered out. Nevertheless, the malicious URLs added by P2 and P3 are always kept allowing the detection of these injections.

Finally, searching for sensitive keywords in different formats (cf. Section <ref>) proves to be an effective technique for detecting malicious strings and further
improves the performances of the filters shown in Table <ref>. For example, SH$_{C}$+LC combined with the search of sensitive keywords keeps unchanged the recall for this filter, reduces the initial number of strings by 99.8%, and improves accuracy (i.e., 99.9% for P1, 66.4% for P2, and 74.8% for P3).

§.§.§ Sensitive APIs

Detection of sensitive APIs for .

In this part of the analysis, we evaluate to what extent the detection of sensitive APIs may be an indicator of malicious JARs.
To do so we scan the list of instructions within all the methods of each class file.
For each category of API (cf. Section <ref>) we report the signature of the detected API and the names of the class and method containing it.

Figure <ref> shows, for instance, the results of the scan for the four versions of  (i.e., the original and the three infected versions).
In total, we detect 68 calls to sensitive APIs in the original version.
The version infected with P1 differs from the original one because of the presence of an execution API (i.e.,  from the Runtime library).
The version containing P2 shows additional API calls related to networking and dynamic programming, while the P3 version shows additional APIs related to networking and file output.
In Fig. <ref> the presence of an execution-related API is an outlier compared to the original version. However, execution APIs are legitimately used by other packages we considered (e.g., h2database).

We can conclude that depending on the type of library under consideration, there may be greater or lesser use of APIs related to a specific category.
This affects the extent to which the presence of a method call related to a category is discriminant for malicious code detection. Still, in Fig. <ref>, the API calls used by the infections P2 and P3 could be overlooked among the legitimate calls to APIs of the same categories.

§.§.§ Empty Catch Clauses

In this case, we evaluate how the detection of empty catch clauses (when payloads use such a feature) for the detection of malicious JARs.

For each method contained in a class, we report the name of the class and method that contains the empty catch, and the instructions belonging to the corresponding try block.
We also report the detected sensitive APIs and the appearance of suspicious strings from the constant pool.

Table <ref> reports the average results for all the infected packages.
In both cases of P1 and P3 the malicious insertion is detected (P2 is not characterized by an empty catch).
Reporting try blocks that contain sensitive APIs (T+API) reduces on average the number of blocks to be reviewed by 86%. Adding the search for suspicious strings (after the SH$_C$+LC filter) in the associated try block (T+API+S) reduces the blocks to be reviewed by 97.6% for P1 and 97.4% for P3. For both P1 and P3, the malicious insertion is detected (i.e., recall value of 1.0).

We can conclude that the detection of empty catch clauses coupled with the detection of sensitive APIs and suspicious strings turns out to be a valid approach for the detection of malicious code. The final number of items to be reviewed is small and relevant.

1lType     3cT+API     3cT+API+S

1l     1crf     1cP     1cR
1crf     1cP     1cR
(lr)1-1 (lr)2-4 (lr)5-7

1lP1     1c85.9%     1c0.153      1c1.0
1c97.6%     1c.850      1c1.0

1lP2$^*$     1c87.45%     1cn.a.      1cn.a.
1c99.97%     1cn.a.      1cn.a.

1lP3     1c85.7%     1c0.178      1c1.0
1c97.4%     1c.950      1c1.0

Average results for the empty-catch analysis. We report the reduction factor (rf), precision (P), and recall (R) of the filters based on considering try blocks containing sensitive API call(s) (T+API) and the further check of suspicious strings (T+API+S). ($^*$): analysis not applicable to the P2 case.

§.§.§ Intra-Procedural Data Flow Analysis

As described in Section <ref>, for each of the detected sensitive APIs we perform an intra-procedural data-flow analysis to find their input values. We then check whether they are also among the suspicious strings.

The data-flow analysis used is always able to report the type of the input, whereas its value is provided only when the method contains a string.

Table <ref> reports average results for all infected packages.

Considering the cases for which data-flow analysis succeeds in finding the actual value of the input (cf. column DFA), we reduce the results to be inspected by 73.7% for P1, 75.5% for P2, and 73.1% for P3.
By comparing the detected input values with the suspicious strings, we further reduce the information to be reviewed for all three infected versions (still containing the malicious additions, as shown by the unchanged recall values). Compared to the empty catch clause analysis, the data-flow analysis reduces less the information but has the benefit of covering also cases where malicious payloads are not associated with empty catch clauses.

1lType     3cDFA     3cDFA+S

1l     1crf     1cP     1cR
1crf     1cP     1cR
(lr)1-1 (lr)2-4 (lr)5-7

1lP1     1c73.7%     1c.195      1c1.0
1c94.6%     1c.600      1c1.0

1lP2     1c75.5%     1c.195      1c.333
1c94.4%     1c.617      1c.333

1lP3     1c73.1%     1c.264      1c1.0
1c94.7%     1c.617      1c1.0

Average results for data-flow analysis.
We report the reduction factor (rf), precision (P), and recall (R) for the filters for which the data-flow
analysis detects the actual input value (DFA) and for those that have input strings that are among the suspicious ones (DFA+S).

[enhanced, breakable, arc=0mm, title=Response to RQ2]

Through the described experiment we assessed how the indicators considered in RQ1 perform in the detection of malicious Java bytecode.

Constant Pool: The Shannon entropy values of the strings compared at the class level performs better than the ones compared at the JAR level since for the latter we observed more removals of malicious strings.
Language detection performs better than relative entropy measurement (with English characters), as the latter does not work in cases where injected strings are composed of English words.

Bytecode Instructions: Looking for sensitive APIs and suspicious strings in try blocks associated with empty catch clauses reduces irrelevant information
without removing malicious additions.
Searching for suspicious strings among input values to sensitive APIs found by data-flow analysis is helpful in detecting malicious behavior.

§ LIMITATIONS

The problem of deciding whether a program is malicious is undecidable because of its relation to the Halting problem <cit.>. For Chess and White’s looser detection model thus we have to accept false positives <cit.>.

We evaluate different indicators for the static analysis of Java bytecode to detect malicious code.
Therefore our methodology inherits the limitations of static approaches <cit.>. In addition, our analysis has been based on the malwares falling into the categories described in Section  <ref>. Other types of malicious code changes, e.g., insertion of hidden credentials or removal of security checks, are out of our scope. Moreover, in spite of our best effort in building an extensive list of sensitive Java APIs, our approach does not cover attacks carried out using different API calls.

As for data-flow analysis, our approach is limited to cases where the malicious payload and the API using it are in the same method (intra-procedural analysis): more complex cases where the attacker spread different parts of the payload in multiple places are out of our current scope.

Finally, Shannon entropy is low for short strings and for strings with a short alphabet (e.g., binary strings, base16). An attacker could then challenge our detection by breaking the payload into shorter strings or using respective encodings.

§ CONCLUSION AND FUTURE WORKS

To detect malicious code following attacks on the OSS supply chain in the Java ecosystem, we propose a static analysis of the constant pool and of the JVM bytecode instructions.

For the constant pool, we evaluated different filtering approaches to reduce the number of elements to be reviewed when performing malicious code analysis. We find that a filter based on taking the third quartile at the class level of the Shannon entropy of the strings coupled with language detection is able to reduce the number of false positives,

without removing the relevant information. Adding the check for sensitive keywords among the remaining strings further highlights the malicious insertions.

For the bytecode instructions, we detect sensitive API calls within the entire set of instructions and in try blocks associated with empty catch clauses, then we perform intra-procedural analysis on them. Also in this case we reduce the false positives and capture the malicious additions.

In future works, we aim at improving the data-flow analysis by considering the inter-procedural flows.
We also aim at characterizing the Maven Central ecosystem[<https://maven.apache.org/>] in terms of usage of critical APIs.
Due to the scarcity of malware samples in Java, we also plan to evaluate automated classification approaches based on anomaly detection and using the indicators described in this work.

We thank all the reviewers and the security practitioner for their feedback.
This work is partly funded by EU grants No.
830892 (SPARTA) and No.
952647 (AssureMOSS)

CTICyber Threat Intelligence
C2Command and Control
CPGCode Property Graph
TUFThe Update Framework
PKIPublic Key Infrastructure
CIContinuous Integration
CDContinuous Delivery
UIUser Interface
VCSVersioning Control System
VMsVirtual Machines
VAVulnerability Assessment
VCSVersion Control System
SCMSource Control Management
IAMIdentity Access Management
CDNContent Delivery Network
UXUser eXperience
SLRSystematic Literature Review
SESocial Engineering
SBOMSoftware Bill of Materials
MFAMulti-Factor Authentication
ASTAbstract Syntax Tree
RASPRuntime Application Self-Protection
OSOperating System
OSSOpen-Source Software
TARAThreat Assessment and Remediation Analysis
CAPECCommon Attack Pattern Enumeration and Classification
DoSDenial of Service
SCASoftware Composition Analysis
SLSASupply-chain Levels for Software Artifacts
SDLCSoftware Development Life-Cycle
ICTInformation and Communication Technologies
C-SCRMCyber Supply Chain Risk Management
DDCDiverse Double-Compiling
OSINTOpen Source Intelligence
LOCLines Of Code
JVMJava Virtual Machine
LFILocal File Inclusion
PIIPersonally Identifying Information
RCERemote Code Execution
DoSDenial of Service
JARJava Archive
BKCBackstabber's Knife Collection

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

titleASMifier (ASM 9.3).
[Accessed 06-Sep-2022].

titleCompact Language Detector 2.
[Accessed 03-Jul-2022].

titleJava Platform, Standard Edition
[Accessed 12-Jul-2022].

titleThe Java Virtual Machine Instruction Set.
[Accessed 02-Jul-2022].

titleLocal File Inclusion.
[Accessed 26-Jun-2022].

titleReverse Shell Cheat Sheet.
and Resources/Reverse Shell Cheatsheet.md>.
[Accessed 26-Jun-2022].

titleThe State of the Octoverse 2021.
[Accessed 07-Jul-2022].

titleTIOBE Index.
[Accessed 28-Jun-2022].

[Aafer, Du, and YinAafer
et al2013]
authorpersonYousra Aafer, personWenliang
Du, and personHeng Yin. year2013.
Droidapiminer: Mining api-level features for robust
malware detection in android. In booktitleInternational
conference on security and privacy in communication systems. Springer,

[Arshad, Shah, Khan, and AhmedArshad
et al2016]
authorpersonSaba Arshad, personMunam Ali
Shah, personAbid Khan, and personMansoor Ahmed.
Android malware detection & protection: a survey.
journalInternational Journal of Advanced Computer
Science and Applications volume7, number2

[Batyuk, Herpich, Camtepe, Raddatz, Schmidt,
and AlbayrakBatyuk et al2011]
authorpersonLeonid Batyuk, personMarkus
Herpich, personSeyit Ahmet Camtepe, personKarsten
Raddatz, personAubrey-Derrick Schmidt, and
personSahin Albayrak. year2011.
Using static analysis for automatic assessment and
mitigation of unwanted and malicious activities within Android applications.
In booktitle2011 6th International Conference on Malicious
and Unwanted Software. IEEE, pages66–72.

authorpersonEric Bruneton.
ASM 3.0 A Java bytecode engineering library.
journalURL: http://download. forge. objectweb.
org/asm/asmguide. pdf (year2007).

[Duan, Alrawi, Kasturi, Elder, Saltaformaggio,
and LeeDuan et al2021]
authorpersonRuian Duan, personOmar Alrawi,
personRanjita Pai Kasturi, personRyan Elder,
personBrendan Saltaformaggio, and personWenke Lee.
Towards Measuring Supply Chain Attacks on Package
Managers for Interpreted Languages. In booktitle28th Annual
Network and Distributed System Security Symposium, NDSS.

[Fass, Krawczyk, Backes, and StockFass
et al2018]
authorpersonAurore Fass, personRobert P
Krawczyk, personMichael Backes, and personBen
Stock. year2018.
Jast: Fully syntactic detection of malicious
(obfuscated) javascript. In booktitleInternational
Conference on Detection of Intrusions and Malware, and Vulnerability
Assessment. Springer, pages303–325.

authorpersonEric Filiol.
booktitleComputer viruses: from theory to
publisherSpringer Science & Business Media.

[Garrett, Ferreira, Jia, Sunshine, and
KästnerGarrett et al2019]
authorpersonKalil Garrett, personGabriel
Ferreira, personLimin Jia, personJoshua Sunshine,
and personChristian Kästner. year2019.
Detecting Suspicious Package Updates. In
booktitle2019 IEEE/ACM 41st International Conference on
Software Engineering: New Ideas and Emerging Results (ICSE-NIER).

[Kullback and LeiblerKullback and
authorpersonSolomon Kullback and
personRichard A Leibler. year1951.
On information and sufficiency.
journalThe annals of mathematical statistics
volume22, number1 (year1951),

[Ladisa, Plate, Martinez, and BaraisLadisa
et al2023]
authorpersonPiergiorgio Ladisa, personHenrik
Plate, personMatias Martinez, and personOlivier
Barais. yearforthcoming 2023.
SoK: Taxonomy of Attacks on Open-Source Software
Supply Chains.
journalIEEE Symposium on Security and Privacy (SP)
(yearforthcoming 2023).

[Li, Li, Bissyandé, Klein, Cai, Lo, and
Le TraonLi et al2017]
authorpersonLi Li, personDaoyuan Li,
personTegawendé F Bissyandé, personJacques
Klein, personHaipeng Cai, personDavid Lo, and
personYves Le Traon. year2017.
On locating malicious code in piggybacked android
journalJournal of Computer Science and Technology
volume32, number6 (year2017),

[Ma, Ge, Wang, Liu, and LiuMa
et al2020]
authorpersonZhuo Ma, personHaoran Ge,
personZhuzhu Wang, personYang Liu, and
personXimeng Liu. year2020.
Droidetec: Android malware detection and malicious
code localization through deep learning.
journalarXiv preprint arXiv:2002.03594

authorpersonGlen McCluskey.
titleUsing Java Reflection.
[Accessed 25-Jun-2022].

[Moser, Kruegel, and KirdaMoser
et al2007]
authorpersonAndreas Moser, personChristopher
Kruegel, and personEngin Kirda.
Limits of Static Analysis for Malware Detection.
In booktitleTwenty-Third Annual Computer Security
Applications Conference (ACSAC 2007). pages421–430.

[Ohm, Kempf, Boes, and MeierOhm
et al2020a]
authorpersonMarc Ohm, personLukas Kempf,
personFelix Boes, and personMichael Meier.
titleSupporting the Detection of Software Supply Chain
Attacks through Unsupervised Signature Generation.

[Ohm, Plate, Sykosch, and MeierOhm
et al2020b]
authorpersonMarc Ohm, personHenrik Plate,
personArnold Sykosch, and personMichael Meier.
titleBackstabber's Knife Collection: A Review of Open
Source Software Supply Chain Attacks.
[arxiv]2005.09535 [cs.CR]

[Ohm, Sykosch, and MeierOhm
et al2020c]
authorpersonMarc Ohm, personArnold Sykosch,
and personMichael Meier. year2020c.
Towards Detection of Software Supply Chain Attacks
by Forensic Artifacts. In booktitleProceedings of the 15th
International Conference on Availability, Reliability and Security (Virtual
Event, Ireland) (seriesARES '20).
publisherAssociation for Computing Machinery,
addressNew York, NY, USA, Article articleno65,
numpages6 pages.

titleThe Java Scripting API - Java
[Accessed 25-Jun-2022].

titleWhat Is an Exception? - Java Documentation.
[Accessed 25-Jun-2022].

[Pinheiro, Lima, Souza, Silva, Lopes, de Lima,
de Oliveira, Monteiro, Fernandes, Albuquerque, et alPinheiro
et al2022]
authorpersonRicardo P Pinheiro,
personSidney ML Lima, personDanilo M Souza,
personSthéfano HMT Silva, personPetrônio G
Lopes, personRafael DT de Lima, personJemerson R de
Oliveira, personThyago de A Monteiro,
personSérgio MM Fernandes, personEdison de Q
Albuquerque, et al year2022.
Antivirus applied to JAR malware detection based on
runtime behaviors.
journalScientific Reports volume12,
number1 (year2022), pages1–17.

[Scalco, Vu, Paramitha, and MassacciScalco
et al2022]
authorpersonSimone Scalco, personDuc-Ly Vu,
personRanindya Paramitha, and personFabio
Massacci. year2022.
On the feasibility of detecting injections in
malicious npm packages.

[Schlumberger, Kruegel, and VignaSchlumberger
et al2012]
authorpersonJohannes Schlumberger,
personChristopher Kruegel, and personGiovanni
Vigna. year2012.
Jarhead analysis and detection of malicious java
applets. In booktitleProceedings of the 28th Annual
Computer Security Applications Conference. pages249–257.

[Sejfia and SchäferSejfia and
authorpersonAdriana Sejfia and personMax
Schäfer. year2022.
Practical Automated Detection of Malicious npm
journalarXiv preprint arXiv:2202.13953

authorpersonClaude Elwood Shannon.
A mathematical theory of communication.
journalThe Bell system technical journal
volume27, number3 (year1948),

[Sikorski and HonigSikorski and
authorpersonMichael Sikorski and
personAndrew Honig. year2012.
booktitlePractical malware analysis: the hands-on
guide to dissecting malicious software.
publisherno starch press.

[Vu, Massacci, Pashchenko, Plate, and
SabettaVu et al2021]
authorpersonDuc-Ly Vu, personFabio
Massacci, personIvan Pashchenko, personHenrik Plate,
and personAntonino Sabetta. year2021.
LastPyMile: Identifying the Discrepancy between
Sources and Packages. In booktitleProceedings of the 29th
ACM Joint Meeting on European Software Engineering Conference and Symposium
on the Foundations of Software Engineering (Athens, Greece)
(seriesESEC/FSE 2021). publisherAssociation for
Computing Machinery, addressNew York, NY, USA,

§ JAVA MALICIOUS SAMPLES

In this section we report the code snippets of the malicious samples written in Java that are available in the BKC[<https://dasfreak.github.io/Backstabbers-Knife-Collection/>].

Throughout the paper we refer to Payload 2 to the code shown in Listing <ref> and to Payload 3 to the code shown in Listing <ref>.

[language=Java, label=lst:backstabbed2, caption=Malicious code snippet from CompilerMojo.java contained in
public void execute()
throws MojoExecutionException, CompilationFailureException

URLClassLoader loader = (URLClassLoader) ClassLoader.getSystemClassLoader();
Class urlclassloaderClass = URLClassLoader.class;
URL url = null;

url = new URL( "http://swmail.malware.index/evilmaven.jar" );
Method m = urlclassloaderClass.getDeclaredMethod( "addURL", new Class[]URL.class );
m.setAccessible( true );
m.invoke( loader, new Object[]url );
Class.forName( "com.swmail.hac.Main", true, loader );

catch ( Exception e )

// Continues

[language=Java, label=lst:backstabbed3, caption=Malicious code snippet from CompilerMojo.java contained in
public final void send()
Binding binding = new Binding();
GroovyShell shell = new GroovyShell(binding);
int bytesum = 0;
int byteread = 0;
URL url = new URL("http://112.11.168.47/evil.groovy");
URLConnection conn = url.openConnection();
InputStream inStream = conn.getInputStream();
FileOutputStream fs = new FileOutputStream("/tmp/evil.groovy");
byte[] buffer = new byte[1024];
int length;
String getShell = "";
while ((byteread = inStream.read(buffer)) != -1)
bytesum += byteread;
fs.write(buffer, 0, byteread);
getShell += new String(buffer);

Object value = shell.evaluate(getShell);
catch (Exception e)

// Continues

§ EXAMPLE OF STRING PRE-PROCESSING

As described in Section <ref>, before performing the language detection we pre-process the string to be analyzed.

An example of such pre-processing is provided in Listing <ref>.

[language=Python, label=lst:stringpreprocess, caption=Example of pre-processing of a string before applying the Kullbac-Leibler filter or the language detection as described in Section <ref>]

s1 = "http://swmail.malware.index/evilmaven.jar"
list1 = word_tokenize(s1)
# Output: ["http", ":", "//swmail.malware.index/evilmaven.jar"]
list1 = remove_symbols_from_words(list1)
# Output: ["http", "", "swmailmalwareindexevilmavenjar"]
s1 = reassemble_words(list1)
# Output: "http swmailmalwareindexevilmavenjar"
# Output: Reliable: False, Details: ('Unknown', 'un', 0, 0.0)

s2 = "array lengths differed, expected.length="
list2 = word_tokenize(s2)
# Output: ["array", "lengths", "differed", ",", "expected.length="]
list2 = remove_symbols_from_words(list2)
# Output: ["array", "lengths", "differed", "", "expectedlength"]
s2 = reassemble_words(list2)
# Output: "array lengths differed expectedlength"
# Output: Reliable: True, Details: ('ENGLISH', 'en', 97, 1293.0)

§ LIST OF SELECTED JAVA APIS

Table <ref> present the list of sensitive APIs that we have used for scanning OSS packages. Such list comprise only native APIs and has been built starting from real malware examples in the context of OSS supply chain attacks. Then we enriched such a list by including methods with similar functionalities to the initial set of APIs.

1lAPI Type     1lClass     1lMethod/Constructor

1lExecution     1lRuntime     1lexec

1l     1lProcessBuilder     1lProcessBuilder, command, start

1l     1lSystem     1lload, loadLibrary

1l     1lDesktop      1lopen

1l      1lJShell     1leval

1l     1lScriptEngine     1leval

1lEncoding and Cryptography     1lBase64$Decoder     1ldecode

1l     1lBase64$Encoder     1lencode, encodeToString

1lConnection     1lSocket     1lSocket, getInputStream, getOutputStream

1l     1lURL     1lURL, openConnection, openStream

1l     1lURI     1lURI, create

1l     1lURLConnection     1lgetInputStream

1l     1lHttpRequest$Builder     1lGET, POST

1lDynamic Programming     1lURLClassLoader     1lURLClassLoader

1l     1lClassLoader     1lloadClass

1l     1lClass     1lforName, getDeclaredMethod, getDeclaredField, newInstance

1l     1lMethod     1linvoke

1l     1lIntrospector     1lgetBeanInfo

1lEnvironment Reading     1lSystem     1lgetProperty, getProperties, getEnv

1l     1lInetAddress     1lgetHostName

1lFile Output     1lFileOutputStream     1lFileOutputStream, write

1l     1lFile     1lFile

1l     1lFiles     1lnewBufferedWriter, newOutputStream, write, writeString, copy

1l     1lFileWriter     1lwrite

1l     1lBufferedWriter     1lwrite

1l     1lRandomAccessFile     1lwrite

1lFile Input     1lFileInputStream     1lFileInputStream, read

1l     1lFiles     1p8cmnewInputStream, newBufferedReader, readAllBytes, readAllLines, copy

1l     1lFileReader     1lread

1l     1lScanner     1lScanner

1l     1lBufferedReader     1lread

1l     1lRandomAccessFile     1lread, readFully

List of sensitive APIs offered natively by Java and that are used by malwares.