# Microwave lymphedema assessment using deep learning with contour assisted
backprojection

Yuyi Chang, Nithin Sugavanam, and Emre Ertin  Department of Electrical and
Computer Engineering
The Ohio State University
Columbus, OH 43210, USA
Email<EMAIL_ADDRESS>
###### Abstract

This paper presents a microwave imaging based method for detection of
lymphatic fluid accumulation in lymphedema patients. The proposed algorithm
uses contour information of the imaged limb surface to approximate the wave
propagation velocity locally to solve the eikonal equation for implementing
the adjoint imaging operator. This modified backprojection algorithm results
in focused imagery close to the limb surface where lymphatic fluid
accumulation presents itself. Next, a deep neural network based on U-Net
architecture is employed to identify the location and extent of the lymphatic
fluid. Simulation studies with various upper and lower arm profiles are used
to compare the proposed contour assisted backprojection imaging with the
baseline approach that assumes homogeneous media. The empirical results of the
simulation experiments show that the proposed imaging method significantly
improves the ability of the deepnet model to identify the location and the
volume of the body fluid.

###### Index Terms:

microwave imaging, lymphedema, tomographic imaging, bioelectromagnetics

##  I Introduction

Lymphedema is a chronic and progressive disease caused by impaired lymphatic
drainage. This disease is a disabling, painful, and disfiguring complication
of nodal therapy for various cancer types, affecting roughly 2-3 million
people in the United States alone, representing 10-30% of cancer survivors
[1]. Various assessment methods for lymphedema are available in the clinical
setting such as perometry, and other forms of limb volume assessment with
limited utility for early detection or intervention. Microwave bio-radar
sensing is an emerging non-invasive biosensing modality, which can be used to
assess the dielectric properties of subcutaneous tissues. These sensors are
low cost, easy to deploy, and applicable for both home and clinical care
settings. However, inferring the dielectric properties of internal tissues
from microwave measurements is an ill-posed inverse problem [2, 3]. The ill-
conditioning of the forward operator is worsened it there exists an air gap
between the antenna elements and the skin surface. As this leads to an abrupt
change in relative permittivity from air-skin interface and consequently a
large reflection coefficient as compared to returns from internal tissues.
Additionally, the transfer function of the antenna elements needs to be
calibrated in situ, as it is uncertain when placed in close proximity of the
body, increasing the number of parameters that needs to be estimated[4, 3].

###  I-A Related works

Secondary lymphedema is a chronic and progressive disease caused by impaired
lymphatic drainage, which results in the accumulation of interstitial protein-
rich fluid and subsequent swelling of the limbs [5]. Existing medical imaging
modalities like Magnetic Resonance Imaging (MRI) and X-ray can be used to
detect abnormalities in the tissue structure with the use of contrast agents
such as Indocyanine green [1]. The detection is accurate but the associated
costs adversely increased the patients’ burdens to receive proper healthcare.

Multiple studies have investigated the use of radiofrequency (RF) based
sensors to detect stroke, detect brain tumor, and screen breast cancer [6, 7,
8, 9] and established the efficacy of this modality in detecting permittivity
changes. Existing work commonly assume that the antenna is well matched to the
skin layer, which is achieved by optimizing the impedance of the antenna to
match the tissue profile or by using an additional matching medium. Yet, this
complicate the clinical implementation due to near field radiation and
undermine patient comfort. Microwave imaging for lymphedema diagnostics have
yet received much attention, with the only known study [10] focuses on antenna
design perspective.

Deep learning have achieved state-of-the-art performances in many imaging
tasks on both medical and natural image domains [11, 12]. Microwave imaging
uses deep learning to facilitate reconstruction backscattered signals and
identifying abnormal tissues in biosensing scenarios [13, 14]. Yet, the
learning tasks typically focus on a narrow frequency, most limited by the
antenna design, and are developed on limited datasets.

###  I-B Contributions

Figure 1: Illustration of our methodology: (a) a limb profile that is being
assessed for lymphedema, with accumulated body fluid denoted in red and is
unknown to the model; (b) tomographic data $P_{i}(t),i=1,2,...,M$
collected/simulated based on the limb profile; (c) Contour guided
backprojection image $I(\vec{r})$; (d) deep learning U-Net model for
localizing lymphedema; (e) model prediction of lymphatic fluid location
superimposed on the limb profile.

In this paper, we develop a deep learning method that uses contour guided
backprojection to precisely identify the presence of excess body fluid within
the tissues. Rather than requiring a matching medium with controlled
dielectric properties, we operate with air gap between the antennas and the
body and assume that the surface contour of the imaged limb is available from
a separate modality (e.g. stereo imaging, millimeter wave radar, etc). We use
the contour information to create an approximate velocity map and employ a
time domain backprojection technique tailored for heterogeneous media which
leads to focused imagery close to the limb surface where lymphatic fluid
accumulation presents itself. We test the proposed algorithm with data from
simulation experiments with various upper and lower arm profiles.
Specifically, we pair a deep learning based detector with both the proposed
contour assisted backprojection imaging method and the baseline approach that
assumes homogeneous media, and compare lymphatic fluid detection performance
using various metrics.

Our results show that the model can detect the presence and extent of
lymphatic fluid better than the baseline approach that combines standard
backprojection with a deep learning model.

This paper focuses specifically on identifying lymphedema, but the methodology
is flexible on any segmentation problems presented in microwave biosensing
(e.g., finding tumors/stroke), in which the cancerous/abnormal tissues have
different EM permittivity profiles compared to other tissues.

##  II Counter guided time domain backprojection algorithm

We consider a circular radar array with $M$ individual elements that operates
in a monostatic transmit and receive setting sensing the spatial domain
$\Omega$. Each transceiver element comprising of a transmitter (TX) and a
receiver (RX) element are spaced at a known distance $d$, taking $M$
tomographic measurements around the limb equally spaced covering 360°. We
further assume the surface contour of the limb is available from a secondary
modality to provide an occupancy mask to guide the backprojection algorithm.
In the following, we first review traditional time domain backprojection
algorithm in a homogeneous medium based on the Time-of-Flight (ToF)
calculations. Next, we present a contour guided locally interpolated (CGLI)
backprojection approach that takes into account a spatially varying EM
propagation speed by taking into consideration the tissue profile prior using
fast marching method that uses local plane wave assumptions.

###  II-A Review of time-domain backprojection in homogeneous medium

We consider a 2D spatial grid $\Omega$ containing $M$ radar elements. Each
element, indexed by $i=1,...,M$, is equipped with a transmitter TX at
$\vec{T}_{i}\in\Omega$ and a receiver RX at $\vec{R}_{i}\in\Omega$. For any
point $\vec{r}=(x,y)\in\Omega$, the travel time $t_{i}$ to $i^{th}$ radar
element can be calculated by time-of-flight (ToF).

$\displaystyle\begin{split}t_{i}(\vec{r})&=t_{T_{i}}(\vec{r})+t_{R_{i}}(\vec{r})\\\
&=\frac{1}{v}\left(||\vec{T}_{i}-\vec{r}||_{2}+||\vec{R}_{i}-\vec{r}||_{2}\right).\end{split}$
(1)

where $v=c/\sqrt{\epsilon}$ is the wave propagation speed determined by
permittivity $\epsilon$ of the medium with respect to the speed of light in a
vacuum $c$.

The radar system produces a series of tomographic measurements
$P(t)=\\{P_{1}(t),P_{2}(t),...,P_{M}(t)\\}$. We sample the backscattered
received signal $P_{i}^{S}[m]=P_{i}(m\cdot\Delta t)$ at constant sampling
interval $\Delta t$ for $m=0,1,...,M$. Signal contribution from the $i^{th}$
transmit-receive pair $I_{i}(\vec{r})$ can be determined by interpolating
$P_{i}(t)$ between $t_{k}$ and $(t_{k}+\Delta t)$ where
$t_{k}<t_{i}(\vec{r})\leq t_{k}+\Delta t$:

$\displaystyle\begin{split}I_{i}(\vec{r})&=P_{i}(t_{k})\cdot\frac{t_{i}(\vec{r})-t_{k}}{\Delta
t}\\\ &+P_{i}(t_{k}+\Delta t)\cdot\frac{(t_{k}+\Delta
t)-t_{i}(\vec{r})}{\Delta t}\end{split}$ (2)

The backprojected signal intensity, denoted as $I(\vec{r})$, is determined by
the superposition of signals from all $M$ transmit-receive pairs.

$I(\vec{r})=\sum_{i=1}^{M}I_{i}(\vec{r})$ (3)

###  II-B Contour guided locally interpolated backprojection

We now examine the backprojection for the $i^{th}$ tx-rx pair $P_{i}(t)$ in a
heterogeneous medium with spatially varying permittivity. Wave propagation in
this setup leads to multiple reflections due to the changing permittivity.
More importantly, the wave velocity slows down due to increased permittivity
in biological tissues resulting in increased spatial resolution when compared
with free space propagation, thereby posing a challenge in identifying body
fluid within internal tissues.

Given the $i^{th}$ radar element, we start by creating a travel time map
$\tau_{T_{i}}(\vec{r})$ and $\tau_{R_{i}}(\vec{r})$ that denotes the shortest
propagation time to each point $\vec{r}=(x,y)$ in the scene originating from
transmitter $T_{i}$ and receiver $R_{i}$ respectively.

Inspired by the success in tracing the travel wave in geoscience applications,
we employ an Anisotropic Locally Interpolated Fast Marching Method (ALI-FMM)
[15] to compute a 2D travel time in heterogeneous media. The algorithm
utilizes the velocity map of the propagation medium and iteratively calculates
the total travel time from a starting point to all points on the spatial grid.

We find the shortest travel time by solving the eikonal equation given by

$|\nabla\tau(\vec{r})|=\frac{1}{v\left(\vec{r},\nabla\tau/|\nabla\tau|\right)}$
(4)

subject to boundary conditions:

$\displaystyle\tau_{T_{i}}(\vec{T}_{i})$
$\displaystyle=0\quad\tau_{R_{i}}(\vec{R}_{i})=0.$ (5)

where $\tau(\vec{r})$ is the shortest travel path, and
$v(\vec{r},\nabla\tau/|\nabla\tau|)$ is the speed of the anisotropy media at
point $\vec{r}=(x,y)$.

In this work, we consider biological tissues are isotropic [16]. The wave
velocity at point $\vec{r}$ is independent of the traveling directions and can
be reduced to $v(\vec{r},\nabla\tau/|\nabla\tau|)=v(\vec{r})$.

The travel time calculation is iterative starting from a source point
$\vec{T}_{i}$ or $\vec{R}_{i}$ and propagate to all $\vec{r}\in\Omega$. Once
the time travel maps $\tau_{T_{i}}(\vec{r})$ and $\tau_{R_{i}}(\vec{r})$ are
determined, the total travel time map $t_{i}(\vec{r})$ is simply given by:

$t_{i}(\vec{r})=\tau_{T_{i}}(\vec{r})+\tau_{R_{i}}(\vec{r}).$ (6)

We solve the eikonal equation iteratively, by following the steps in [15] and
introduce three states for any point to keep track of the progress of
traversal: known, close, and far. At the beginning, all points are initialized
to far state where none of the point has been visited. The points are updated
to close as soon as they have been traversed, indicating a middle state where
a precise travel time has not been determined. Traversal to a point is
considered completed when it becomes known state, meaning a travel time has
been set after multiple optimization iterations. The iterations take a similar
form as breadth-first search (BFS) search algorithm where the algorithm
advances to the next closest spatial grid at each steps. However, in order to
achieve a higher accuracy and to avoid quantization error, the methodology
employs a collection of 32 stencils to better approximate traveling wavefront
using locally linear wavefronts. This results in additional search steps to
select a stencil that achieves the best approximation. Again the backprojected
image $I(\vec{r})$ can be obtained by aggregating individual single images
$I_{i}(\vec{r})$ following equation 2-3.

Figure 2: Obtaining backprojected image $I(\vec{r})$ from collected
measurements $P(t)$ using CGLI backprojection method: (a) velocity map
$v(\vec{r})$ constructed based on limb occupancy; (b) two way travel time
$t_{i}(\vec{r})=\tau_{T_{i}}(\vec{r})+\tau_{R_{i}}(\vec{r})$; (c)
backprojected image $I_{i}(\vec{r})$ from a single TX/RX Pair. (d) full
backprojected image $I(\vec{r})$.

Fig. 2 illustrates individual steps to obtained a full backprojected image
using CGLI method. A velocity map (Fig. 2) is constructed based on arm
occupancy information using an effective permittivity $\epsilon_{eff}=5$. The
velocity map enables travel time $\tau(\vec{r})$ (Fig. 2) calculation. Fig. 2
shows single angle backprojected image $I_{i}(\vec{r})$ by interpolating
received signal $P_{i}(t)$ at the first radar element $i=1$. The final
backprojected image $I(\vec{r})$ is obtained by repeating the previous steps
for all 24 radar elements and aggregating the backprojection results (Fig. 2).

##  III Deep learning model

In this paper, we focus on a segmentation problem using a deep learning model
designed to detect and localize lymphatic fluids. Using a backprojected image
$I(\vec{r})$ as the input, the model produces a mask that contains
probabilistic measurements ranged from 0 to 1 indicating the likelihood of a
given pixel containing body fluid. The detection of an elevated presence of
body fluid is indicative of lymphedema.

Our model is a deep convolutional neural network that is based on U-Net
architecture [17]. The U-Net model is first introduced for medical image
segmentation tasks, and its design has demonstrated robust performances for
other computer vision problems across different domains [17, 18]. The
architecture consists of an encoding path and a decoding path, forming a
U-shape structure as shown in Fig. 3. Skip connections are placed between
individual encoding and decoding levels in order to mitigate information loss
during convolutional down/upsampling operations.

We follow the configuration as in the original U-Net model [17] to construct
our model. Starting from a raw input image, the encoding path at every level
condenses the input features to a higher-level description through multiple
convolutional blocks. Each convolution block contains two sequentially
operated 2D convolution, batch normalization and ReLU activation layers. At
the end of each encoding level, the feature channel is doubled. An identical
copy is cropped and passed through the skip connection to its corresponding
decoder step, and a max pooling layer downsamples the original features by
half for the next encoding step. At each decoding level on the decoding path,
the skip connected features is concatenated with features from previous step.
The combined features are upsampled by a convolutional layer and processed by
the convolutional blocks following the same setup as in the encoding path.

A final convolutional blocks contains a sigmoid layer, and is used to produce
probability mask for localizing lymphatic fluid. Under binary segmentation
formulation, the final sigmoid layer is typically combined into loss function
for improved numerical stability. We further employ residual connections [19]
on encoding path to promote network’s ability to identifying underlining body
fluid. This results a hybrid deep learning model based on U-Net architecture
[17] for improved segmentation capacity.

Figure 3: Illustration of deep learning U-Net model. The model contains
multiple 3x3 convolutional blocks designed to extract image features at
different dimensions. The model has a encoding (orange blocks) and a decoding
path (purple blocks) that performs convolutional down/upsampling,
respectively. The skip connections (dashed line) form direct connections
between encoding and decoding paths to mitigate information loss.

##  IV Experiments

###  IV-A Datasets

We constructed upper extremity phantoms based on measurements from typical
healthy adults. Ten base phantoms were generated, each incorporating layers
representing skin, fat, muscle and bone tissues. A cylindrical shape body
fluid object is introduced within the fat layer mimicking the presence of
lymphedema. The severity of lymphedema was controlled by varying the radius of
the body fluid object.

EM backscattered data were obtained through FDTD simulations using gprMax
software [20]. A tomography scan comprised samples taken at 24 uniformly
spaced angles with a 20 x 20 cm domain. The simulation utilized a built-in
bow-tie antenna, operating at 1.5 GHz with an approximate 1 GHz bandwidth.
Calibration to simulated data was performed involving aligning time axis using
a set of size varying PEC cylinders, and free space calibration to enable
coherently subtract antenna effects.

The EM dataset contain 676 samples which corresponds to 16224 individual
simulations. We performed a random split of the dataset based on phantom
profiles into training, validation and testing datasets. The distribution of
samples is as follows: 520 samples for training, 52 samples for validation,
and 104 samples for testing.

EM simulations are inherently CPU intensive and time consuming tasks, making
it crucial to accelerate data generations to support data driven methods. We
leverage GPU accelerated computing by offloading CPU tasks to multiple GPUs. A
load balancing application was built to support executing a simulation task
pool across multiple GPUs. This resulted approximately an 80x acceleration
compared to running solely on CPU.

###  IV-B Implementation details

Backprojected images take the shape of 256x256 with a single pixel
representing roughly 0.78x0.78 mm grid in spatial domain. A min/max scaling is
applied to all resulting images to have min/max values set to in between 0 to
1. This ensure our received signals are always up to scale.

PyTorch framework is used for training and testing lymphedema segmentation.
The training and testing are performed on a single Nvidia Quadro RTX 6000 GPU
and Intel Xeon CPU server. The training data are augmented through random
rotation and flipping. Our U-Net model contains five encoding/decoding steps,
compressing the input feature up to 512 channels as shown in Fig. 3. We use
pretrained ResNet-34 [19] as the backbone for U-Net encoders. The model takes
single channel backprojected image as input and produces a single channel
output. A sigmoid layer is applied the model output to produce probability map
of body fluid. Binary cross entropy (BCE) loss is used for training between
the output and ground truth segmentation masks. The model is trained 200
epochs, and the model weights that achieve the lowest validation loss is used
for further evaluation.

###  IV-C Evaluation metrics

We evaluate our methodology by comparing segmentation performance to the non-
contour assisted backprojection algorithm (Section II-A) using our test
dataset. In addition to BCE test losses, we analyze the sensitivity of the
models based on probability of detection $P_{D}$ and probability of false
alarm $P_{FA}$ from receiver operating characteristic (ROC) curves. The ideal
threshold setting for segmenting lymphatic fluid is determined by fixing a
$P_{FA}$. We further analyze the model performances by the F1 and the
intersection over union (IoU) scores:

$F1=\frac{TP}{TP+0.5\left(FP+FN\right)}$ (7)

$IoU=\frac{TP}{\left(TP+FP+FN\right)}.$ (8)

##  V Results

###  V-A Backprojection using different strategies

Fig. 4 presents single angle backprojected image $I_{i}(\vec{r})$ using ToF
method (Fig. 4) ad our CGLI method (Fig. 4). To better understand the effects
of backprojecting in a heterogeneous medium, a vertical slice is taken at the
center of Fig. 4 to show the progression of backprojected signal intensity at
the imaging plane that is orthogonal to the radar (Fig. 4). We examine the
relationships between the sliced backprojection and the original received
signal (Fig. 4). The red dashed lines on each sides of the two images indicate
the duration of backprojected time range. The orange and green markers
indicate the duration during which the backprojected signal is within the
phantom boundary. Between the two range markers, we can clearly see the signal
presented in Fig. 4 appeared to be the stretched version compared to original
signal in Fig. 4 due a slower propagation speed happening within the tissue.
In addition, the effects of shadowing were observed where a mirrored copies of
the original signals appear in the backprojected image. The shadowing occurs
due to EM wave travel times are the same when penetrating the limb and travel
along the air-skin interface before entering the internal tissues. Highlighted
in purple, the local minima around 150 and 180 in Fig. 4 are symmetric around
the purple marker in Fig. 4 at the lower regime of the phantom, which is also
evident by examining the total travel time map (Fig. 2) by drawing equal
travel time contours. The effect is predominant due to skin effects during EM
wave propagation [21]. However, the effect do not contribute significantly to
the backprojected results as the shadowing effects only occur in the lower
regime of the lime when the backscattered signal intensity is low.

Figure 4: Comparing backprojected image $I_{i}(\vec{r})$ obtained from a
single angle using (a) ToF based backprojection and (b) our CGLI
backprojecting methodology. (c) Original received signal $P_{i}(t)$ shown to
compared with (d) a vertical cut showing progression of backprojected
intensity. The triangular markers show the backprojected signal is within the
tissue boundary. The circle markers highlights the dual local maxima as a
result of shadowing.

###  V-B Lymphedema segmentation using deep learning models

We now present deep learning results for identifying lymphatic fluid within
the tissues using a U-Net model. Fig 5 presents the receiver operating
characteristic (ROC) curves showing probability of detection $P_{D}$ with
respect to false alarm probability $P_{FA}$. The result shows our model
achieves better detection accuracy compared to two baselines with different
permittivity assumption under a fixed $P_{FA}$. At $P_{FA}=10^{-3}$, the
detection probability of our model is $P_{D}=0.85$ over baselines’ $0.32$ and
$0.20$. We bias the model at $P_{FA}=10^{-3}$ and evaluate F1 score and IoU,
in addition to BCE loss reported during testing, as presented in Table I.
Having the lowest testing BCE loss, our contour guided backprojection method
continue to achieves strong performance over other baseline models with F1
score of 0.565 and IoU of 0.393.

Figure 5: Reciver operating characteristics (ROC) of our method and baseline models showing probability of detection $P_{D}$ and probability of false alarm $P_{FA}$. TABLE I: Test results based on backprojection method Backprojection Method | BCE loss | F1 Score | IoU
---|---|---|---
ToF Baseline 1 ($\epsilon_{eff}=2.5$) | 0.00546 | 0.171 | 0.094
ToF Baseline 2 ($\epsilon_{eff}=1.0$) | 0.00328 | 0.255 | 0.146
Contour guided (CGLI) | 0.00145 | 0.565 | 0.393

In the following we use two of the individual test samples to demonstrate the
effectiveness of the proposed method over the alternative baseline methods
discussed above in Fig. 6. The first test sample shows a lower limb with
lymphatic fluid radius $r=2.5$ mm, representing a mild state of lymphedema
where a just-in-time intervention is necessary (Fig. 6). The second test
sample comes from a upper limb profile with a severe state of lymphedema at
radius $r=6$ mm (Fig. 6). From top to bottom, we present 1) logit outputs from
deep learning models, 2) predicted probability mask after the sigmoid of the
final layer, and 3) predicted lymphedema location superimposed on the ground
truth profile. Compared to baseline method with either permittivity
assumption, our method precisely locate the location of lymphatic fluid on the
phantom with less false positive. With contour guided methodology, the target
location is already aligned with actual geometry, so no additional calibration
needs to be learned by the U-Net to establish the transformation between the
lymphatic fluid location in microwave imaging domain to spatial domain.

Figure 6: Individual test samples comparing our method to baseline methods
(left to right columns). On each subplot, intermediate model outputs including
logits (row 1) and prediction probability map (row 2) are presented with
assessment output superimposed on the ground truth profile (row 3). Our model
shows confident and accurate predictions on (a) a lower limb with mild
lymphedema $r=2.5$mm, and (b) a upper limb showing severe lymphedema $r=6$mm
compared to baseline methods.

##  VI Conclusion

In this paper, we presented a contour based backprojection imaging method when
paired with a deep learning network can localize lymphedema present
subcutaneously. We use prior information about the surface contour of the limb
to to backproject received signals to spatial domain accounting different
propagation speed inside and outside of the limb profile. The identification
of lymphatic fluid is enabled by a deep learning segmentation U-Net model,
which takes the backprojected image and produces a probability map where the
fluid may be presented on the phantom profile. We evaluated our methodology on
a synthetic microwave imaging dataset and compared our method to baseline
method. For future work, we will 1) develop a model that can infer and segment
further subcutaneous structures like fat tissue, 2) expand our dataset to
include a more diverse set of lymphatic fluid composition, and 3) evaluate on
other existing microwave imaging datasets. We will make the model and the
imaging code publicly available to facilitate microwave bio-imaging research.

## Acknowledgment

This work is partly supported by NSF Grant CBET-2037398 and NIH Grant
P41EB028242.

## References

  * [1] J. C. Rasmussen, I.-C. Tan, M. V. Marshall, K. E. Adams, S. Kwon, C. E. Fife, E. A. Maus, L. A. Smith, K. R. Covington, and E. M. Sevick-Muraca, “Human lymphatic architecture and dynamic transport imaged using near-infrared fluorescence,” _Translational Oncology_ , vol. 3, no. 6, pp. 362–IN7, 2010.
  * [2] D. W. Winters, E. J. Bond, B. D. Van Veen, and S. C. Hagness, “Estimation of the frequency-dependent average dielectric properties of breast tissue using a time-domain inverse scattering technique,” _IEEE Transactions on Antennas and Propagation_ , vol. 54, no. 11, pp. 3517–3528, 2006.
  * [3] B. C. Civek and E. Ertin, “Bayesian sparse blind deconvolution using MCMC methods based on normal-inverse-gamma prior,” _IEEE Transactions on Signal Processing_ , vol. 70, pp. 1256–1269, 2022.
  * [4] Y. Chang, N. Sugavanam, and E. Ertin, “Removing antenna effects using an invertible neural network for improved estimation of multilayered tissue profiles using UWB radar,” in _2023 IEEE USNC-URSI Radio Science Meeting (Joint with AP-S Symposium)_. IEEE, 2023, pp. 53–54.
  * [5] A. K. Greene, “Epidemiology and morbidity of lymphedema,” in _Lymphedema_. Springer, 2015, pp. 33–44.
  * [6] S. Y. Semenov, D. R. Corfield _et al._ , “Microwave tomography for brain imaging: Feasibility assessment for stroke detection,” _International Journal of Antennas and Propagation_ , vol. 2008, 2008.
  * [7] M. Hopfer, R. Planas, A. Hamidipour, T. Henriksson, and S. Semenov, “Electromagnetic tomography for detection, differentiation, and monitoring of brain stroke: A virtual data and human head phantom study.” _IEEE Antennas and Propagation Magazine_ , vol. 59, no. 5, pp. 86–97, 2017.
  * [8] G. N. Bindu, S. Abraham, A. Lonappan, V. Thomas, C. Aanandan, and K. Mathew, “Active microwave imaging for breast cancer detection,” _Progress In Electromagnetics Research_ , vol. 58, pp. 149–169, 2006.
  * [9] A. T. Mobashsher, A. Mahmoud, and A. Abbosh, “Portable wideband microwave imaging system for intracranial hemorrhage detection using improved back-projection algorithm with model of effective head permittivity,” _Scientific reports_ , vol. 6, no. 1, p. 20459, 2016.
  * [10] D. Russo, “Preliminary investigation on microwave sensing for early detection of lymphoedema,” Ph.D. dissertation, Politecnico di Torino, 2021.
  * [11] S. K. Zhou, H. Greenspan, C. Davatzikos, J. S. Duncan, B. Van Ginneken, A. Madabhushi, J. L. Prince, D. Rueckert, and R. M. Summers, “A review of deep learning in medical imaging: Imaging traits, technology trends, case studies with progress highlights, and future promises,” _Proceedings of the IEEE_ , vol. 109, no. 5, pp. 820–838, 2021.
  * [12] J. Chai, H. Zeng, A. Li, and E. W. Ngai, “Deep learning in computer vision: A critical review of emerging techniques and application scenarios,” _Machine Learning with Applications_ , vol. 6, p. 100134, 2021.
  * [13] W. Shao and Y. Du, “Microwave imaging by deep learning network: Feasibility and training method,” _IEEE transactions on antennas and propagation_ , vol. 68, no. 7, pp. 5626–5635, 2020.
  * [14] B. Gerazov and R. C. Conceicao, “Deep learning for tumour classification in homogeneous breast tissue in medical microwave imaging,” in _IEEE EUROCON 2017-17th International Conference on Smart Technologies_. IEEE, 2017, pp. 564–569.
  * [15] J. Ludlam, K. Tant, V. Dolean, and A. Curtis, “Travel times and ray paths for acoustic and elastic waves in generally anisotropic media,” _Journal of Computational Physics_ , vol. 494, p. 112500, 2023.
  * [16] X. Zhang, S. Zhu, and B. He, “Imaging electric properties of biological tissues by RF field mapping in MRI,” _IEEE transactions on medical imaging_ , vol. 29, no. 2, pp. 474–481, 2010.
  * [17] O. Ronneberger, P. Fischer, and T. Brox, “U-net: Convolutional networks for biomedical image segmentation,” in _Medical Image Computing and Computer-Assisted Intervention–MICCAI 2015: 18th International Conference, Munich, Germany, October 5-9, 2015, Proceedings, Part III 18_. Springer, 2015, pp. 234–241.
  * [18] V. Khoshdel, M. Asefi, A. Ashraf, and J. LoVetri, “Full 3d microwave breast imaging using a deep-learning technique,” _Journal of Imaging_ , vol. 6, no. 8, p. 80, 2020.
  * [19] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778.
  * [20] C. Warren, A. Giannopoulos, and I. Giannakis, “gprMax: Open source software to simulate electromagnetic wave propagation for ground penetrating radar,” _Computer Physics Communications_ , vol. 209, pp. 163–170, 2016.
  * [21] A. Vander Vorst, A. Rosen, and Y. Kotsuka, _RF/microwave interaction with biological tissues_. John Wiley & Sons, 2006.


# Know Your Neighborhood: General and Zero-Shot Capable Binary Function Search
Powered by Call Graphlets

Josh Collyer
Loughborough University  Tim Watson
Loughborough University  Iain Phillips
Loughborough University

###### Abstract

Binary code similarity detection is an important problem with applications in
areas like malware analysis, vulnerability research and plagiarism detection.
This paper proposes a novel graph neural network architecture combined with a
novel graph data representation called call graphlets. A call graphlet encodes
the neighborhood around each function in a binary executable, capturing the
local and global context through a series of statistical features. A
specialized graph neural network model is then designed to operate on this
graph representation, learning to map it to a feature vector that encodes
semantic code similarities using deep metric learning.

The proposed approach is evaluated across four distinct datasets covering
different architectures, compiler toolchains, and optimization levels.
Experimental results demonstrate that the combination of call graphlets and
the novel graph neural network architecture achieves state-of-the-art
performance compared to baseline techniques across cross- architecture, mono-
architecture and zero shot tasks. In addition, our proposed approach also
performs well when evaluated against an out-of-domain function inlining task.
Overall, the work provides a general and effective graph neural network-based
solution for conducting binary code similarity detection.

##  1 Introduction

Binary code similarity detection (BCSD) aims to find compiled functions that
are similar to a given query function. It has a wide range of applications,
from identifying vulnerabilities in firmware to analyzing code reuse across
malware variants. BCSD can enhance security assessments of closed-source
software by accurately identifying the components used, such as libraries
embedded within statically linked executables and firmware binaries.

Implementing effective BCSD approaches is challenging due to the diversity of
architectures, compiler toolchains, and optimization levels used to build
software. These factors can lead to significant variations in the binary
representations of the same source code, making it challenging to distinguish
between similar and dissimilar functions. While optimization level has the
biggest impact on these variations, recent research shows that call graph
features are most resilient to these transformations, presenting an
opportunity to develop improved, general BCSD approaches [10].

Existing approaches predominantly focus on function-level artifacts like
control flow graphs, disassembly, or intermediate representations, neglecting
the potential of call graph features. Additionally, some approaches rely on
the assumption of dynamically linked standard library functions such as those
from libc are easily recoverable, which does not hold for embedded devices and
malware where static linking is common, restricting their applicability across
different software ecosystems.

Furthermore, the evaluation methodologies employed in binary function search
often lack rigor. Existing approaches predominantly rely on "in-domain"
evaluation data, utilizing subsets of functions from the training binaries
themselves. This practice introduces the risk of data leakage, potentially
inflating reported performance metrics. More crucially, it fails to assess the
true generalization capability of the approach when faced with previously
unseen functions, a scenario referred to as "out-of-domain" data.
Comprehensive evaluation necessitates testing on entirely separate datasets to
obtain an accurate understanding of real-world performance and
generalizability. This is an area we tackle head on with evaluation across
four distinct datasets.

This paper proposes a novel approach that aims to exploit the additional
information available when including call graph features and addresses the
limitations of existing methods. It employs a comprehensive evaluation
methodology, including both in-domain and out-of-domain assessments across
four large datasets, to ensure robust and generalizable findings. The proposed
approach does not rely on the identification of standard library
functionality, making it applicable across a broader range of binary types and
scenarios.

###  1.1 Key Contributions

Within this work, we propose a general function search approach utilizing
function level call graphlets inspired by the results presented in TikNib [10]
and PSS [2]. Our contributions are as follows:

  1. 1.

We introduce a novel call graph level function format we name call graphlets.
This format incorporates a functions callers as well as callees to provide a
graphlet neighborhood which provides structure alongside a set of simple
function level features as node attributes.

  2. 2.

We present a simple, yet powerful Graph Neural Network (GNN) trained using
deep metric learning which is capable performing well in and out of domain
across a number of tasks.

  3. 3.

We present a robust evaluation using previous research datasets of our
approach as well as compare against a range of benchmarks.

  4. 4.

We present conduct an ablation study to investigate how our graph neural
network (GNN) design choices contribute to our performance.

###  1.2 Paper Overview

The remainder of this paper is organized as follows: We begin by reviewing the
relevant prior work to establish a foundation for our contributions. Next, we
present a detailed description of the methodology used in this study. This
includes explaining how a call graphlet is constructed, the features used for
nodes and edges, the Graph Neural Network (GNN) architectural choices, and the
datasets employed. Following this, we present a comprehensive section on the
experiments conducted to evaluate our approach. We start with an evaluation in
a cross-architecture context, followed by experiments on the model’s
performance in a mono-architecture setting (x86-64 only), cross-architecture
with function inlining setting, zero-shot vulnerability search setting, and
then conclude with an ablation study. Finally, we conclude the paper by
exploring some fundamental limitations of our approaches and providing our
concluding remarks.

##  2 Related Work

The problem of identifying similar functions across different binary
architectures has been tackled using various methods in the existing
literature. These methods can generally be classified into three main
categories: sequence-based approaches and graph-based approaches, or a
combination of both. In this section, we start by briefly reviewing the
sequence-based approaches. Then, we provide a more detailed review of the
graph-based literature. Finally, we will discuss alternative methods and
highlight the limitations of previous works in this area.

###  2.1 Sequence Based Approaches

Sequence based approaches use either assembly, pseudo-code or intermediate
representations extracted from binaries for each function to generate
representations suitable for comparison. These sorts of approaches have been
applied to individual assembly instructions[13], sequences of assembly
instructions[23], sequences of intermediate representations[4] and even
execution sequences [18].

All approaches share the common objective of seeking to learn useful
representations of input by adapting approaches developed in the natural
language processing (NLP) literature. This is typically done via a two stage
process of pre-training and then fine-tuning. Researchers have used a range of
different pre-training tasks ranging from standard approaches such as Masked
Language Modelling (MLM) to domain specific tasks such as jump target
prediction [23] and instruction data flow relationship prediction [13]. Once
pre-trained, the models are then fine-tuned for a given down stream task such
as binary code similarity detection (BCSD) or N-day vulnerability detection
typically using contrastive methods such as deep metric learning.

###  2.2 Graph Based Approaches

All of these approaches however miss an opportunity to use broader information
related to a single function such as type information and calling
relationships and instead focus on data contained within the a single function
boundary. Graph based approaches on the other hand, look to exploit the
inherent data structure within compiled binaries such as call graphs and
control flow graphs (CFG). These data structures are then paired with graph
neural network approaches to create learnt representations that perform well
at downstream tasks such as BCSD.

XBA [11] is a graph neural networks approach which works on a basic block
level for a given function as well as incorporating key external information
such as string literals and external function calls. This novel representation
is then fed into a GCN based GNN to generate cross-architecture and cross-
platform embeddings. PDM [17] is another example of a graph neural network
which instead works on a combined control flow and data flow representation
named ACFG+. This representation is then used alongside a Capsule GNN to
generate embeddings.

CFG2VEC [25] is an example of a more complicated approach to ours and was used
as inspiration for our approach. CFG2VEC is a hierarchical method whereby a
single input is a binaries entire call graph and each node is a P-code Based
control flow graph. The P-Code based CFG representation is then fed into a
graph neural network to create node-embeddings for the higher level call
graph. These node embeddings are then subsequently used to support binary code
similarity detection tasks. PSS [2] propose an interesting graph spectra
approach which operates primarily on the call graphs structure. This approach
is used for whole binary identification so can be considered tangential to the
other papers within this section but has been included primarily because it
was also a large the main inspiration for this work. HermesSim [8] also used a
P-Code representation of a target function but instead creates a novel graph
representation where nodes are P-code operations or memory locations and the
edges are relationships such as read and writes. This is again fed into a GNN
approach to create function level representations that can be used for BCSD
tasks. HermesSim can be considered the current state of the art in this area
having reported impressive results recently.

###  2.3 Alternative Methods

In addition to sequence, graph and combinatorial methods, some researchers
have sort to adopt alternative methods. BinFinder [19] is an example of this
were instead of using sequences, a series of statistical count features were
used based on a VEX IR lifted representation and counts of glibc calls. This
approach has one major drawback and that is the reliance on glibc functions
being recoverable and external. This has potential to limit its usage in cases
such as statically linked binaries or blob firmware. The approach however does
perform very well and is one our a key baselines.

###  2.4 Limitations of Previous Work

There are several limitations of the works mentioned above. Firstly, several
of the approaches [19, 11] rely on recoverable function names to build
fundamental parts of there feature space. This is error-prone and something
that may not always be possible in all settings such as when you are faced
with obfuscated or statically linked binaries. Secondly, most existing
approaches [17, 13, 4, 23, 18] analyze individual functions in isolation
without considering the broader relationships and interactions between
functions within the software binary. This potentially overlooks valuable
information that is inherent in the overall structure and interconnections
present in the binary.

Thirdly, when approaches utilize external information like global call graphs
[25, 2], they encounter two primary limitations. First, a global call graph is
a coarse representation, and its structure, and consequently its
effectiveness, can be significantly affected by obfuscation techniques and
function inlining. Secondly, errors in accurately recovering the correct
calling relationships may propagate throughout the entire graph, even though
these errors may only impact a subset of the functions within the binary
executable, the effect may still be significant.

##  3 Methodology

###  3.1 Call Graphlet Neighborhoods

Our work utilizes a novel data format we call call graphlets (visually
depicted Figure 1). This approach was inspired by the work described in PSS
[2] but instead of operating with binary level call graphs, we opt to work
with function level ones. A call graphlet is a weighted directed graph made up
of a tuple $G=V,E,W$ whereby: $V$ represents a set of functions, $E$
represents a set of calling relationship in the format of $(x,y)\;|\;x\neq y$
and $W$ represent the weights for a given edge. A target function’s call
graphlet neighborhood includes a node for the target function itself, any
functions that call the target function (callers), any functions the target
function calls (callees) and any functions that are called by the target
functions callees (callees of callees). We excluded callers of callers from
our call graphlets to prevent creating excessively large call graphlets,
particularly for widely used functions like utilities and standard libraries,
and because we felt that callee relationships better characterize a function.
The weights for all edges correspond to there respective edge betweenness
value that is calculated at a call graphlet level rather than a global call
graph level.

The reasons for working at a call graphlet level are twofold. Firstly, recent
work suggests that features derived from the call graph are the most robust to
changes in compilation toolchains [10]. We however viewed using global call
graphs as too coarse and instead formulated a more fine grained data
representation with the aim of developing a high performing function-level
BCSD approach. Secondly, we wanted to create a data representation that took
the calling behaviour between a function, its callers and callees into
account. We view this relationship as something that will likely be similar
within software compiled from the same source code regardless of compilation
variations. This provides a means to focus on a higher level representation
rather than solely focusing on function level differences or changes such as
patches or refactoring.

Figure 1: Call Graphlet Example Data Structure

###  3.2 Graph Features

####  3.2.1 Node Features

Each of the functions within a given call graphlet neighborhood have the six
straightforward features derived from function level metadata recovered during
the disassembly process. Features such as in-degree (number of callers), out-
degree (number of callees) and total number of edges provide global
information whilst features such as total number of instructions, number of
arguments and number of local variables provide local information. The
hypothesis is that this combination of local and global level information
provides the model the ability to discern between a range of different
functions. For example, a complex function that is infrequently called may
have a low in-degree but a high number of instructions, out-degree and number
of local variables whereas a wrapper function for a commonly used library
function such as memcpy may have a low instruction count and out-degree but a
very high in-degree suggesting it is called frequently. The full feature list
can be found in Table 1.

Feature Name |  Description
---|---
Num Instructions |  The number of instruction in the function
Num Edges |  The sum of in-degree and out-degree edges
Total Indegree |  The number of in-degree edges. Denotes callers
Total Outdegree |  The number of out-degree edges. Denotes callees
Num Locals |  The number of local variables
Num Args |  Number of arguments from the recovered function prototype
Table 1: Function/Node Level Features

####  3.2.2 Edge Weights

Alongside the node-level function metadata, we also generate a weight for each
edge within the call graphlet using edge betweenness centrality.

The edge betweenness for edge $e$ is calculated as follows:

$C_{b}(e)=\sum_{s,t\in V}\frac{\sigma(s,t|e)}{\sigma(s,t)}$ (1)

where $V$ is the set of nodes, $\sigma(s,t)$ is the number of shortest paths
between the nodes $s$ and $t$ and $\sigma(s,t|e)$ is the number of shortest
paths that pass through $e$.

The edge betweenness is calculated at a call graphlet level instead of a
global call graph level because we want to quantify the control each edge
exerts over information flow within the call graphlet. Edges with high
betweenness centrality can be viewed as critical pathways or bottlenecks. In
our particular case, we viewed edge betweenness centrality as a useful
addition because it provides a means of identifying functions that exhibit
high call fan-out (i.e., a large number of callees) and participate in
critical calling relationships with ancestor functions in the call hierarchy.
This additional information is hypothesized to improve the model’s performance
by capturing the interplay between a function’s calling behavior and its
position within the program’s overall call structure.

###  3.3 Datasets

####  3.3.1 Training Dataset

The training dataset used within this paper is the Dataset-1 released as part
of the work of [15]. This dataset contains seven popular open source projects:
ClamAV, Curl, Nmap, Openssl, Unrar, z3 and zlib. Each of these are compiled
for ARM32, ARM64, MIPS32, MIPS64, x86 and x86-64 using 4 different versions of
Clang and GCC alongside 5 different optimization levels. Each project has 24
unique configurations. The same sized train, test and validation splits were
created as described in [15] and [8] to support robust comparison.

It is worth noting that the processed call-graphlet dataset created from
Dataset-1 using bin2ml is significantly larger than what is reported in [15]
and [8]. This is because our data representation allows us to relax the
filtering requirements such as number of instruction or basic blocks within a
function. Since our method uses a functions neighborhood, we can include
smaller functions as they will be augmented by their neighbors who may not fit
the filtering requirements.

Our data representation also likely results in more varied examples of each
function because, due to architectural, compiler or optimization differences,
the variations present within a functions neighborhood are included as well.
This is especially interesting because even when the node features of a
function are duplicates, each call graphlet may be different and therefore,
continue to be included within our dataset. With this being said, in order to
facilitate robust and fair comparison, we firstly subset the data into the
same binary-level splits described in [15] and then use random sampling to
create identically sized samples from within the binaries within the split.
This methodology is replicated to generate the corresponding Dataset-1 test
set split as well.

####  3.3.2 Evaluation Datasets

In order to robustly evaluate our approach, we use four open source benchmark
datasets and focus exclusively on out-of-domain evaluation. The reason for
focusing exclusively on out-of-domain performance is that it provides
experimental evidence of our approaches performs well when given a collection
of binaries it has not already seen as well as being the most comparable to a
real-world setting.

Firstly, we use the test set from Dataset-1. This dataset includes a subset
binaries which encompasses the Z3 and Nmap projects, all of which are not
present within the train dataset. This dataset contains 522003 functions which
is identical to the size used within [8] and [15].

Secondly, we use Dataset-2 also presented in [15]. This dataset is a subset of
the evaluation dataset used within [18] and ensures there is no intersection
between the software packages contained within Dataset-1. Dataset-2 includes
the following 10 libraries: Binutils,coreutils, diffutils, findutils, GMP,
ImageMagick, Libmicrohttpd, LibTomCrypt, PuTTy and SQLite. Due to issues
processing ar archives with our data processing tool, Libmicrohttpd and
LibTomCrypt were omitted from our evaluation dataset. Both of these binaries
are however included within the later datasets. The binaries within this
dataset include versions compiled for x86, x64, ARM32, ARM64, MIPS32 and
MIPS64 across four optimization levels (O0, O1, O2, O3) using the GCC-7.5
compiler. This dataset shares the same overall configuration in terms of
architectures, optimization levels and compiler version but has unique
binaries within it.

Thirdly, we use BinKit NoInline dataset presented within [10]. This dataset
contains 51 unique packages/libraries across 8 architectures (x86, x64, ARM32,
ARM64, MIPS32, MIPS64, MIPS32EB and MIPS64EB), 9 different versions of
compiler (five unique versions of GCC, four unique versions of Clang) as well
as five different optimization levels (O0, O1, O2, O3, Os). All of the
binaries have also been compiled with function inlining turned off. This
results in a total of 67,680 binaries. This dataset does share some common
software projects to Dataset-2 but does not share any with the training
dataset. This dataset introduces two previously unseen architecture variants,
additional compilers as well as an additional optimization level.

And finally, we use the BinKit Normal dataset also presented within [10]. This
is an identical dataset to the Binkit NoInline dataset described above but
with one fundamental difference - The compilers are able to inline functions.
Function inlining has been referenced as a significant weakness across a
number of binary function similarity approaches [24, 6] and therefore this
dataset allows us to tackle this area head on and generate empirical results
of how well our approach fairs when faced with function inlining.

####  3.3.3 Data Preparation

A uniform data preparation pipeline was implemented to process all datasets
outlined above. This process can be broken down into five key stages:
extraction, fusion, deduplication, augmentation and sub-setting.

Extraction: The initial stage involved extracting call graphs and function
metadata for each binary within the datasets. This was achieved by utilizing
the bin2ml tool which uses radare2 as the underlying software reverse
engineering tool to load, process and output the required data.

Fusion: Following extraction, the extracted call graph and function metadata
were combined. This process resulted in the creation of function-level call
graphlets. Each call graphlet encapsulated the functions local call graph
structure whereby each node’s features was it’s corresponding function’s
metadata. Each call graphlet was output as a Networkx [7] compatible JSON
object to support seamless loading into our chosen graph neural network
framework, PyTorch Geometric [5].

Deduplication: The next stage focused on eliminating redundant call graphlets
within the datasets. The methodology employed here was inspired by previous
related work [15, 4, 8]. The deduplication process is outlined as follows:

  1. 1.

Call graphlets are initially grouped based on the software binary from which
they originated. This binary-specific grouping facilitates a more efficient
deduplication process.

  2. 2.

Subsequently, each call graphlet within a group is hashed using a suitable
hashing algorithm. The resulting hash values are then stored within a hash
set. This hash set serves as a mechanism to track unique call graphlets
encountered for each binary.

  3. 3.

In the event that a duplicate hash is identified, the call graphlet is removed
from the dataset. This ensures the presence of a single example for each
unique call graphlet.

All of the remaining, unique call graphlets are saved and form the basis of
the given dataset used to train or evaluate our proposed approach.

Augmentation: Once deduplication was complete, each graph was loaded into
Networkx and the edge betweenness values were generated and then appended to
the graph as floating point edge weights.

Subsetting: The last stage focused on sub-setting the data. This was not
necessary for all datasets but in the case of BinkitNormal and BinkitNoInline,
due to the number of unique functions call graphlets generated, it was not
feasible to evaluate a model on all functions present due to hardware
limitations. For both, we used a random sampling strategy to create test
datasets. Each sample contained a total of 1 million functions. This subset
was created once for each source dataset and then saved for re-use. Both of
these splits are provided as part of the release of this research.

###  3.4 Model

Figure 2: KYN Model Architecture

The model used within our approach is a bespoke 3-layer graph neural network
incorporating several different GNN components to create a novel GNN
architecture. A diagram visually representing the model can be seen in Figure
2

GraphConv Message Passing GNN

The graph convolution operator used within this study is the operator proposed
in [16]. It computes the updated feature representation $x_{i}^{\prime}$ for a
node $i$ in a graph by combining two components: 1) a linear transformation of
the node’s own input features $W_{1}x_{i}$, and 2) a weighted sum of the
features of its neighboring nodes $\sum_{j\in N(i)}e_{j,i}\cdot x_{j}$, where
the neighbors’ features are first weighted by the strength of their
connections $e_{j,i}$ and then linearly transformed $W_{2}$. The resulting
output feature vector $x_{i}^{\prime}$ captures both the node’s intrinsic
features and the information from its local neighborhood. This operator has
been shown to be able to capture higher-order graph structures and outperform
a range of standard GNN and graph kernel approaches. This is due to approach
considering structures within the graphs at varying scales.

$x_{i}\prime=W_{1}x_{i}+W_{2}\sum_{j\in N(i)}e_{j,i}\cdot x_{j}$ (2)

Instance Normalization

We adopt Instance Normalization (IN) [22] as the graph normalization technique
omitting the learnable scale and shift parameters $\gamma$ and $\beta$, as
described in Equation 3. IN is applied to the node features, where
$x_{i}\prime$ represents the normalized node feature for node $i$. It centers
the features by subtracting the mean $E[x]$ across all nodes within a given
graph, scales them by dividing by the square root of the variance $Var[x]$
plus a small constant $\epsilon$ (set to $1e-05$). This normalization
technique aims to stabilize the training process by reducing the internal
covariate shift, ensuring consistent distribution of node features across the
layers of the graph neural network.

$x_{i}{\prime}=\frac{x-E[x]}{\sqrt{Var[x]+\epsilon}}$ (3)

Due to the cross-architecture context of our research, the selection of
architecture, compiler, and optimization combinations can significantly
influence a function’s structure and form. IN exhibits an interesting property
wherein it performs normalization on each function independently at the graph
level. This means that variations among features within our examples are
handled separately, which is crucial in our domain due to substantial
variations across multiple features, such as the number of instructions, total
number of edges, in-degree, and out-degree.

Softmax Aggregation

Similar to other recent works such as HermesSim [8], we opt use the Softmax
aggregation function as defined as follows:

$softmax(X|t)=\sum_{x_{i}\in X}\frac{exp(t\cdot x_{i})}{\sum_{x_{j}\in
X}exp(t\cdot x_{j})}\cdot x_{i}$ (4)

where $t$ controls the softness of the softmax aggregation over the input
feature set $X$, which in our case is set to 1. This differs from the usage
within HermesSim in two key ways. Firstly, we adopt the vanilla version of
softmax aggregation which omits the multi-headed attention extensions. And
secondly, we use the softmax aggregation function as the GNN’s aggregation
function as opposed to using it as a global graph pooling operator. The
softmax operator is used to create node-level representations at each message
passing step.

Layer-Wise Connections + Max Pool

We opt to have Layer-Wise feature connections from each of the graph neural
network layers to store the node level representations from each convolution.
The node-level representations are stored from each layer-wise connection
before each of them being max pooled to create a graph level representation
where the resulting feature vector is a feature-wise maximum across the node
features of that layer. This operation can be seen in Equation 5.

$X_{i}=max_{n=1}^{N_{i}}X_{n}$ (5)

Global max pooling was chosen to provide a means of identifying the most
distinct features from across the call graphlet node representations. This was
viewed favorably given our objective is to identify similar functions across
architectures, compilers and optimization levels which requires distinct
representations.

Mapping to Embedding

Each of the max pooled graph-level embeddings are then concatenated together
$X_{c}=(X_{1},X_{2},X_{3})$ resulting in a single vector of size
$3*X_{input}$. This feature vector is then passed into a two layer linear
network, mapping from $3*hidden_{d}\to hidden_{d}\to\frac{hidden_{d}}{2}$. The
output of this is then normalized using $F2$ normalization to produce the
final embedding.

###  3.5 Training

The model was trained using pair-based deep metric learning using a BatchHard
mining scheme [9]. We paid special attention to the sampling methodology to
ensure that each batch contained multiple (2 in our case) versions of any
function present. This ensured that it was always possible to create a
positive pair for each function present as well as provide a rich range of
possible negative samples.

The model’s configuration was a hidden dimension size of 256 and an output
embedding dimension of 128. Circle loss [21] was used as the loss function
configured with $m$ set to 0.25 and $\gamma$ set to 256. Circle loss and the
hyper parameters were chosen due to good results presented in previous works
[4]. The model was optimized using the Adam optimizer [12]. The model was
trained for 350 epochs with each epoch having 100K graphs randomly sampled
from the total training dataset. A cosine simulated annealing with warm
restarts learning rate schedule starting at 0.0005 and finishing at 0.0001 was
used and each batch had 256 graphs within it. The number of epochs before warm
restart started at 50 and doubled for 2 subsequent times (50 -> 100 -> 200)
for a total of 350 training epochs.

##  4 Evaluation

We implement KYN using PyTorch Geometric [5]. We use bin2ml alongside radare2
to generate the data for all the experiments outlined below. All
experimentation was conducted on a workstation with 64GB RAM alongside a
NVIDIA 4090 24GB GPU.

We conducted several in-depth experiments to answer the following research
questions:

  1. 1.

RQ1: How does KYN perform when faced with unseen libraries, compilers and
compiler options in a cross-architecture setting?

  2. 2.

RQ2: How does KYN perform when faced with unseen libraries, compilers and
compiler options in a mono-architecture setting?

  3. 3.

RQ3: How does KYN perform when faced with function inlining when this is not
present in the training data?

  4. 4.

RQ4: Is KYN capable of performing zero-shot architecture search?

  5. 5.

RQ5: What aspects of the KYN model contribute to it’s overall performance?

###  4.1 Tasks

The evaluation tasks have been formulated to provide a means of holistically
evaluating the performance of KYN over a large collection of binaries drawn
from several benchmark datasets.

For RQ1, RQ2 and RQ3 we adopt the same approach described in [15] by creating
search pools of $N$ size whereby for a given function $f$, the generated
search pool includes a single positive and $N-1$ negatives. Due to reporting
both cross-architecture and mono-architecture results, we have two key
subtasks:

  1. 1.

For cross-architecture datasets, we report results for the XM task described
in [15]. The XM task imposes no restrictions on what architecture, bitness,
compiler or optimization level can be chosen and can be considered
representative of real life.

  2. 2.

For mono-architecture datasets (which are all x86-64), we report results
comparable to the XC task described in [15]. The XC task imposes restrictions
on the architecture and bitness that can be chosen but no restrictions on
compiler or optimization level.

For both cross and mono-architecture evaluation, we provide results across a
range of search pool sizes ranging from 100 to 10000. The search pool size of
100 and 10000 are used to compare against other SOTA approaches with the
remaining provided for future researchers to compare against.

For RQ4, we adopt the vulnerability search task described in [15] with an
addition of compiling the same version of libcrypto.so for RISC-V 32-bit and
PowerPC 32-bit. And finally for RQ5, we evaluate the architecture choice
impact using the XM tasks described above.

|  | 100 | 10,000
---|---|---|---
Approach | Summary | R@1 | MRR@10 | R@1 | MRR@10
Trex [18] | Disasm + Traces | 0.24 | 0.34 | 0.09 | 0.11
GMN [14] | CFG + BoW opc 200 | 0.45 | 0.54 | 0.11 | 0.16
FASER NRM [4] | ESIL IR Strings | 0.51 | 0.57 | - | -
GraphMoco [20] | ASM Basic Block + GNN | 0.55 | 0.60 | - | -
BinFinder [19] | VEX IR + Metadata | 0.73 | 0.80 | - | -
HermesSim [8] | PCode SOG | 0.75 | 0.80 | 0.44 | 0.51
KYN (Ours) | Call Graphlets + Metadata | 0.76 | 0.80 | 0.45 | 0.50
Table 2: Dataset-1 (Cisco Talos Binary Similarity [15]) Test Results across
search pools of 100 and 10,000 compared against relevant benchmarks

###  4.2 Metrics

To facilitate robust comparison, we adopt the same metrics used within the
domain of Recall at 1 (R@1) and Mean Reciprocal Rank at 10 (MRR@10) [15].
These metrics are used for all results presented as part of RQ1, RQ2 and RQ3.
At points throughout reporting the results for RQ1, RQ2 and RQ3 we also report
Normalized Discount Cumulative Gain at 10 (NDCG@10). NDCG is an alternative
metric to MRR and unlike MRR, considered results throughout the K selected
rather than just the first occurrence. The NDCG@10 scores have been provided
to aid future researchers compare against our approach. For RQ4, we report the
ranks at which the vulnerable function was present at after the search was
conducted. This is the same as previous studies [15]. We also report the mean
and median rank to support comparison in a similar manner to [4].

###  4.3 Baseline Approaches

In order to robustly evaluate our approach, we have chosen a range of state-
of-the-art baselines approaches which include both graph and sequence based
models.

  1. 1.

Trex [18] is a transformer model trained on both disassembly and micro traces
in order to learn execution semantics before then being fine-tuned for the
binary function search task.

  2. 2.

GMN [14] is a variant of the GNN proposed in the same paper and have been
shown to outperform alternative baseline graph neural network approaches [15].
This approach does however rely on 1-to-1 matching across the entire
comparison corpus which is a significant drawback.

  3. 3.

FASER [4] is cross-architecture binary code similarity detection approach that
combines long context transformers with radare2’s native intermediate
representation.

  4. 4.

GraphMoco [20] is a hybrid model which first encoded basic blocks before then
generating embedding representations with a GNN.

  5. 5.

Binfinder [19] is a simple feed-forward neural network which leverages VEX IR
and several statistical features to identify similar features.

  6. 6.

HermesSim [8] is a state of the art approach that leverages a novel graph data
structure named Semantic Orientated Graph alongside a graph neural network to
embed functions before then comparing them.

For the mono-architecture experiments, we also compare against jTrans [23].
jTrans is a transformer model trained using a novel jump orientated pre-
training task on a large x86-64 dataset and can be considered as one of the
state of the art models for x86-64 mono-architecture binary function search.

###  4.4 Cross Architecture Binary Function Search (RQ1)

####  4.4.1 Dataset 1

|  | XA + XO
---|---|---
Approach | Summary | R@1 | MRR@10
Trex | 512 Tokens | 0.46 | 0.53
GNN (from athors of GMN) | CFG + BoW opc 200 | 0.57 | 0.67
GMN | CFG + BoW opc 200 | 0.61 | 0.71
KYN (Ours) | Call Graphlets | 0.76 | 0.82
Table 3: Dataset-2 Test Results across search pools of 100 compared against
relevant benchmarks. Comparison scores taken directly from [15]

The results presented in the Table 2 show the results generated for search
pools 100 and 10000. Starting first with the results for the smaller, 100
negative search pool size, our approaches performs comparably to the current
state of the art approaches, HermesSim [8] and BinFinder [19] with reported
metrics that are near identical. When comparing against our other chosen SOTA
GNN baselines, GraphMoco [20] and GMN [14], our approach significantly
outperforms across all collected metrics with a R@1 relative increase of 32%
and 51.2% and a MRR@10 relative increase of 28.6% and 38.8% respectively. When
compared against two state of the art cross-architecture Transformer models
FASER [4] and Trex [18], our approach again significantly outperforms them
with a R@1 relative increase of 39.8% and 104% and a MRR@10 relative increase
of 33.6% and 80.7%. Turning now to the larger search pool size of 10000, our
proposed approach again reports near identical results to HermesSim with a
marginally better R@1 but a lower MRR@10 suggesting both approaches are
performing similarly.

In addition to the search pools sizes of 100 and 10,000, we also present
results for the search pool sizes of 250 and 1000 in Table 3. This was
primarily due to how significant the difference is for the results between 100
and 10,000 is and provides a means of reasoning about the performance
degradation as the pool size increases as well as providing future researchers
empirical results to compare against.

The results presented in Table 3 show that, as expected, all metrics degrade
as the search pool size increases, with the degradation occurring steadily.
Notably however, our approach even outperforms the bottom four baselines
(Trex, GMN, FASER, GraphMoco) when faced with search pools containing 1,000
functions compared to when each of the approaches is dealing with only 100
functions. This demonstrates the effectiveness of our approach, especially
when faced with a larger number of possible candidate functions to search.

####  4.4.2 Dataset-2

The results shown Table 4 demonstrate that our approach significantly
outperforms all the baseline approaches. Compared to the best baseline, our
method achieves a 22.9% increase in R@1 (recall at 1) and a 14.8% increase in
MRR@10 (mean reciprocal rank at 10). Interestingly, the performance of our
approach is comparable to the results we obtained for Dataset-1. This is not
the case for the baseline approaches, which perform better on this dataset
than on Dataset-1. This suggests that not only does our model outperform the
baselines in terms of the metric scores, but it also exhibits more consistent
performance across different datasets.

Search Pool Size | R@1 | MRR@10 | NDCG@10
---|---|---|---
250 | 0.670 | 0.711 | 0.735
1000 | 0.572 | 0.616 | 0.641
Table 4: Results for Dataset-1 Across Different Search Pools

In a similar manner to Dataset-1, we also generated results for search pools
of 250, 1000 and 10,000. The results for this are presented in Table 5. As the
search pool size increases, the performance degradation is more significant.
From theorising why this may be, we think this is likely due to the
composition of the Dataset-1 test set. The test set split is dominated by the
Z3 (in terms of on-disk size and number of functions) resulting in an
intrinsically varied sample. When faced with a dataset with more scope for
similar functions from different binaries and when at large pool sizes, the
task becomes more challenging therefore reducing overall performance.

Search Pool Size | R@1 | MRR@10 | NDCG@10
---|---|---|---
250 | 0.674 | 0.737 | 0.765
1000 | 0.566 | 0.641 | 0.679
10000 | 0.328 | 0.417 | 0.461
Table 5: Results for Dataset-2 Across Different Search Pools

####  4.4.3 Binkit Noinline

The results from evaluating our approach for binkit-noinline architecture
presented in Table 6. Our approach again performs consistently across all of
the metrics collected and reports similar results to those collected when
using Dataset-1 and Dataset-2.

Search Pool Size | R@1 | MRR@10 | NDCG@10
---|---|---|---
100 | 0.824 | 0.873 | 0.893
250 | 0.774 | 0.831 | 0.858
1000 | 0.636 | 0.714 | 0.751
10000 | 0.436 | 0.529 | 0.574
Table 6: Binkit-Noinline Metrics Across Different Search Pools

####  4.4.4 Summary

In summary, the results above demonstrate that, after robust evaluation across
a range of different binary benchmark datasets, that our approach performs
equally or significantly better to comparison benchmarks. The breadth of
datasets used for evaluation demonstrates that our approach could be
considered a general approach which can generalize to unseen binaries within a
cross-architecture setting.

###  4.5 Mono-Architecture Binary Function Search (x86-64) (RQ2)

Turning now to our mono-architecture evaluation. For this, we use two distinct
KYN models, one trained in a cross-architecture fashion (the same as the one
used to generate the results above) and another trained solely with x86-64
examples.

The results from these experiments are in Table 7. Both of our model variants
out-perform the baseline approaches across both of the reported search pool
sizes of 100 and 10000. Our KYN-Cross model performs the strongest within the
100 search pool size with a relative percentage increase of 23.4% R@1 and
12.2% MRR@10 when compared against jTrans and a relative percentage increase
of 6.1% R@1 and 2.6% MRR@10 when compared against HermesSim. The difference in
performance increases significantly when looking at the large search pool size
of 10,000. Both model variants significantly outperform both of the benchmark
approaches with the relative percentage increases of 53.95% (KYN-Cross) /
55.29% (KYN-x8664) R@1 and 46.25% (KYN-Cross) / 44.97% (KYN-x8664) MRR@10 when
compared against jTrans. When compared against HermesSim, the performance
increase is less but still significant with a relative percentage increase of
12.66% (KYN-Cross) / 14.11% (KYN-x8664) R@1 and 9.26% (KYN-Cross) / 7.92%
(KYN-x8864).

| Cisco D1 - XC
---|---
| 100 | 10000
jTrans | 65.0/73.8 | 31.4/37.4
HermesSim | 75.6/80.7 | 48.1/54.6
KYN-Cross | 80.2/82.8 | 54.6/59.9
KYN-x8664 | 77.2/80.4 | 55.4/59.1
Table 7: x86-64 Mono-Architecture results on Cisco Dataset-1. Results are
presented with R@1 first and then MRR@10.

To further evaluate our model and understand its performance when faced with a
larger x86-64 dataset, we also evaluated it against BinaryCorp-3M with and
without duplicates. These results can be seen in Table 8 and show that both
model variants perform similarly with the cross-architecture variant typically
edging ahead. There are several areas of note. Firstly, the performance of the
models when faced with a different mono-architecture dataset is significantly
degraded. This highlights the need to evaluate against a range of different
dataset to get a true understanding of a models performance. Secondly, the
performance is inflated significantly when duplicates are present across both
search pool sizes tested. This suggests that the inclusion of duplicates
within evaluation datasets is a critical mistake and may lead to
misrepresentation of the quality and performance of approaches.

| BinaryCorp3M-WD | BinaryCorp3M-ND
---|---|---
| 100 | 10000 | 100 | 10000
KYN-Cross | 68.0/73.9 | 38.8/44.1 | 51.6/58.8 | 31.2/36.9
KYN-x86-64 | 67.0/73.6 | 36.6/41.9 | 51.8/58.0 | 31.4/36.2

Table 8: Mono-Architecture Binary Function Search Results. WD denotes "with
duplicates" whilst ND denotes "no duplicates"

The evaluation results show that the two KYN model variants (KYN-Cross and
KYN-x8664) outperform the baseline jTrans and HermesSim approaches across
different search pool sizes for the mono-architecture setting, with relative
performance increases ranging from a few percent to over 50% depending on the
metric and search pool size. Additionally, the presence of duplicates in the
evaluation datasets is shown to significantly inflate the performance metrics,
suggesting that including duplicates can misrepresent the true quality and
performance of the approaches.

| ARM32 | Mean Rank | Median Rank | MIPS32 | Mean Rank | Median Rank
---|---|---|---|---|---|---
ARM32 | 1, 1, 1, 1 | 1 | 1 | 68, 14, 85, 182, 4, 44 | 66 | 56
MIPS32 | 8, 8, 347, 1 | 91 | 8 | 2, 2, 301, 12, 1, 1 | 53 | 2
X86-64 | 1, 1, 1, 1 | 1 | 1 | 79, 14, 125, 119, 6, 72 | 69 | 75.5
X86-32 | 1, 1, 1, 1 | 1 | 1 | 74, 14, 55, 144, 22, 33 | 57 | 44
RISCV-32 | 1, 1, 1, 326 | 82 | 1 | 106, 17, 34, 59, 3, 17 | 39 | 25.5
PowerPC32 | 967, 192, 76, 2 | 309 | 134 | 491, 467, 583, 63, 991, 3 | 433 | 479
Table 9: Zero Shot Vulnerability Search Results

###  4.6 Cross-Architecture Binary Function Search with Inlining (RQ3)

The following section evaluates KYN in the presence of the potential of
function inlining. Function inlining introductions the possibility for callee
functions to be merged into (or inlined) into a caller function. If this
occurs, the structure of the caller function can change significantly. This is
an area which is typically highlighted as a limitation of approaches or
something that is explicitly turned off [19, 15]. We chose instead of tackle
this area head-on and evaluate our approach against a BinKit variant called
BinKit-Normal. Within this dataset, all of the binaries have been compiled
where there is a possibility for function inlining. The results presented
below in Table 10 show the metric value for a given search pool size as well
as the percentage difference when compared against the results present for
BinkitNoInline in Table 6.

SP | R@1 | $\Downarrow$ | MRR@10 | $\Downarrow$ | NDCG@10 | $\Downarrow$
---|---|---|---|---|---|---
100 | 0.73 | 11.6% | 0.79 | 9.3% | 0.82 | 8.17%
250 | 0.66 | 14.99% | 0.72 | 13.36% | 0.75 | 12.47%
1000 | 0.59 | 7.39% | 0.66 | 7.42% | 0.69 | 7.86%
10000 | 0.33 | 23.39% | 0.42 | 20.23% | 0.47 | 18.47%

Table 10: Binkit-Normal Metrics Across Different Search Pools with comparison
against Binkit-NoInline. The percentages represent percentage decrease when
function inlining was present.

The key observations from the results are as follows. Across all search pool
sizes, there is a performance degradation of between 7% to 23.5% or in other
works between 0.07 and 0.1 in absolute terms across the reported metrics.
These results do show that function inlining does have a negative impact on
our methods performance but is not dramatic. Considering that our approach was
trained with a dataset that does not include function inlining , the results
show our model has learnt general representation allowing it to maintain
reasonable performance when faced with function inlining.

###  4.7 Zero-Shot Cross-Architecture Vulnerability Search (RQ4)

We also conduct a zero-shot experiment using the same methodology as the N-day
vulnerability search task described in [15] but compile the same libcrypto.so
library for RISC-V and PowerPC 32-bit to evaluate our approaches model within
a zero-shot context with the results reported in Table 9.

The performance within a zero-shot context area mixed depending on the
architecture used for search pool functions (i.e the architecture of what is
being searched). Focusing on the ARM32 firmware image, KYN demonstrates high
accuracy and precision in identifying OpenSSL vulnerabilities when provided
with ARM32, x86-64, and x86-32 query functions, evidenced by a mean rank of 1
and median rank of 1. However, when faced with a MIPS32 query function, the
model’s performance degrades, with a mean rank of 91 and a median rank of 8.
Regarding zero-shot architectures, the RISCV-32 performance is acceptable,
with a mean rank of 82 and a median rank of 1, albeit skewed by a single poor
retrieval. Conversely, the PowerPC results are significantly worse, with a
mean rank of 309, a median rank of 134, and a particularly high ranking of
967, indicating high variance in the model’s performance depending on the
function encountered.

In addition to the ARM32 firmware image, we also report the results for the
MIPS32 image within the same dataset. This is something that other works have
typically omitted. Examining the MIPS32 architecture firmware, the results
with a MIPS32 query function are satisfactory but inferior to the ARM32 vs.
ARM32 results, with a mean score of 53 and a median of 2. When considering the
in-domain architectures of ARM32, X86-64, and X86-32, the model performs
acceptably, with mean ranks ranging from 57-69 and median ranks from 44-75.5,
albeit not as well as the ARM32 vs. In-Domain experiments. Notably, for the
out-of-domain RISCV-32 architecture, the mean and median ranks outperform all
in-domain architectures. However, consistent with the ARM32 results, PowerPC32
performs poorly, with a mean rank of 433 and a median rank of 479.

The results are mixed but show promise when compared against those reported
within [4], especially for zero-shot performance of RISCV-32 $\to$ ARM32. Our
findings are however consistent with [4] in terms of MIPS32 being inherently
more difficult and challenging that other architectures. The reasons for this
are unclear and may warrant additional research.

###  4.8 Ablation Study (RQ5)

In order to understand the performance of our model in more detail and the
impact of our design decisions, we trained several models on the same dataset
and then evaluated them on the same test set, utilizing a search pools of 100
for evaluation generate empirical evidence. KYN is the model architecture used
within the rest of the paper above, KYN-NE is the same model architecture but
the input graphs have no edge weights and therefore the edge support for
GraphConv layers was not used and KYN-NES further amended whereby we replace
the softmax aggregation function for add within each of the convolutional
layers. The results for each of these settings can be seen below in Table 11.

Setting | MRR@10 | R@1
---|---|---
KYN | 0.80 | 0.76
KYN-NE | 0.76 | 0.71
KYN-NES | 0.75 | 0.7
Table 11: Metric scores across search pools of size 100

The results demonstrate that both the softmax aggregation and edge features
contribute to increasing performance. The softmax aggregation provides a
modest performance absolute improvement of 0.01 for both MRR@10 and R@1. The
edge feature information however contributes to a significant absolute
improvement of 0.04 MRR@10 and 0.05 of R@1. These results suggest that
incorporating edge weights, in our case edge betweenness, increases the
quality of the function representations for graph neural network based binary
code similarity detection tasks.

During the experimentation and model development for this study, several
experiments were run to understand the usefulness of various types of graph
normalization techniques. Namely Layer Normalization [1], GraphNorm
Normalization [3] and Instance Normalization [22]. To understand the effect of
each, we trained the same model with the same train and test set but changed
the normalization technique used within each of the 3 GNN layers.

| MRR@10 | R@1
---|---|---
KYN + GraphNorm | 0.52 | 0.46
KYN + LayerNorm | 0.63 | 0.57
KYN + InstanceNorm | 0.80 | 0.76
Table 12: Metric cross across Normalization Choices

The results presented for the normalization experiments in Table 12 are clear.
They suggest that, for our data at least, the chosen normalization approach
has a profound impact of the overall performance. When comparing GraphNorm to
Instance Normalization, the impact of choosing GraphNorm over Instance
Normalization is approximately a 0.3 absolute difference or a 42% relative
difference. The effects are marginally less for LayerNorm but still
significant with approximately a 0.17 absolute difference or 25% relative
difference when compared against InstanceNorm.

The reason for this large performance difference likely lies within the large
variations, in particular with the number of instructions within our chosen
coarse node feature vectors and how both LayerNorm and GraphNorm apply
normalization. Both of these normalization approaches seek to learn a
normalization function for batches of graphs. Given that each of our batches
contain graphs sampled from across both architectures and software projects,
the variation within the batches is likely to be high. During training, the
normalization functions are trained and this variation is normalized as
expected. When moving to test however, when the model is faced with new
software projects whereby the call graphlets have a completely different set
of nodes and therefore distribution, when the learnt normalization function is
applied, the normalization performs poorly. This is especially true when you
look at the binaries contained within the train and test sets of the Dataset-1
where the model is initially faced with several modestly sized projects during
training before then being faced with a test dataset dominated by a very large
and complex project (z3). This issue however does not effect InstanceNorm
because the normalization is applied to each graph independently within a
batch.

##  5 Limitations

Despite the promising results achieved by the KYN approach, there are several
limitations that warrant further investigation. One potential limitation lies
in the computational requirements associated with generating the call graphlet
representations. As the size and complexity of the target binaries increase,
the computational overhead involved in extracting call graphs and constructing
the graphlet neighborhoods may become prohibitive, especially in resource-
constrained environments or time-sensitive applications. Future work could
explore more efficient techniques for graph extraction and representation.

Another limitation of the current approach is its reliance on accurate
disassembly and call graph recovery. While the methodology employed in this
work assumes reliable disassembly and call graph extraction, real-world
scenarios may involve obfuscated or heavily optimized binaries, which could
impede accurate recovery of these structures. Techniques such as control flow
flattening, virtualization obfuscation, or extreme inlining could potentially
undermine the effectiveness of the proposed approach. To address this
limitation, future research could investigate incorporating deobfuscation
strategies or developing more robust graph recovery mechanisms that can handle
adversarial obfuscation techniques.

Furthermore, the current evaluation framework primarily focuses on open-source
software and benchmark datasets. While these datasets provide a valuable
foundation for assessing the approach’s performance, they may not fully
capture the diversity and complexity present in real-world binary analysis
scenarios, such as those encountered in embedded software reverse engineering
or malware analysis settings. Future work should aim to expand the evaluation
scope by incorporating a broader range of proprietary software, firmware, and
malware samples to further validate the approach’s generalizability and
robustness under diverse and potentially adversarial conditions.

##  6 Conclusions

In this work, we proposed a novel graph neural network architecture called KYN
that leverages one-hop call graphlets for effective cross-architecture binary
function similarity detection. Our approach demonstrated state-of-the-art
performance across multiple evaluation tasks spanning several benchmark
datasets, consistently outperforming previous methods in both cross-
architecture and mono-architecture settings. Furthermore, KYN exhibited
promising results even in challenging scenarios involving function inlining
and zero-shot vulnerability search across unseen architectures. Through
ablation studies, we highlighted the importance of incorporating edge features
and leveraging instance normalization in our model design. Overall, the
proposed KYN approach provides a robust, zero-shot capable and generalizable
solution for binary code similarity detection, with potential applications in
areas such as N-day vulnerability detection, software forensics and malware
analysis. Future research directions include extending the approach to handle
advanced obfuscation techniques and exploring its applicability to other
domains within the binary analysis landscape.

## Acknowledgments

I would like to acknowledge the significant contribution of the authors of
[15] who have provided a foundation for robust comparison within this domain
and stimulated significant research interest.

## Availability

All components of this paper are publicly available. The training dataset,
model training and evaluation code as well as the model artifacts themselves
can be found http://repository-to-be-made. The tool used to generate the
dataset is also open source and can be found here
https://github.com/br0kej/bin2ml.

## References

  * [1] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton.  Layer normalization.  arXiv preprint arXiv:1607.06450, 2016.
  * [2] Tristan Benoit, Jean-Yves Marion, and Sébastien Bardin.  Scalable program clone search through spectral analysis.  arXiv preprint arXiv:2210.13063, 2022.
  * [3] Tianle Cai, Shengjie Luo, Keyulu Xu, Di He, Tie-yan Liu, and Liwei Wang.  Graphnorm: A principled approach to accelerating graph neural network training.  In International Conference on Machine Learning, pages 1204–1215. PMLR, 2021.
  * [4] Josh Collyer, Tim Watson, and Iain Phillips.  Faser: Binary code similarity search through the use of intermediate representations.  arXiv preprint arXiv:2310.03605, 2023.
  * [5] Matthias Fey and Jan E. Lenssen.  Fast graph representation learning with PyTorch Geometric.  In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
  * [6] Jian Gao, Yu Jiang, Zhe Liu, Xin Yang, Cong Wang, Xun Jiao, Zijiang Yang, and Jiaguang Sun.  Semantic learning and emulation based cross-platform binary vulnerability seeker.  IEEE Transactions on Software Engineering, 47(11):2575–2589, 2019.
  * [7] Aric Hagberg, Pieter Swart, and Daniel S Chult.  Exploring network structure, dynamics, and function using networkx.  Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 2008.
  * [8] Haojie He, Xingwei Lin, Ziang Weng, Ruijie Zhao, Shuitao Gan, Libo Chen, Yuede Ji, Jiashui Wang, and Zhi Xue.  Code is not natural language: Unlock the power of semantics-oriented graph representation for binary code similarity detection.  In 33rd USENIX Security Symposium (USENIX Security 24), PHILADELPHIA, PA, 2024.
  * [9] Alexander Hermans, Lucas Beyer, and Bastian Leibe.  In defense of the triplet loss for person re-identification.  arXiv preprint arXiv:1703.07737, 2017.
  * [10] Dongkwan Kim, Eunsoo Kim, Sang Kil Cha, Sooel Son, and Yongdae Kim.  Revisiting binary code similarity analysis using interpretable feature engineering and lessons learned.  IEEE Transactions on Software Engineering, 49(4):1661–1682, 2022.
  * [11] Geunwoo Kim, Sanghyun Hong, Michael Franz, and Dokyung Song.  Improving cross-platform binary analysis using representation learning via graph alignment.  In Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis, pages 151–163, 2022.
  * [12] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [13] Xuezixiang Li, Yu Qu, and Heng Yin.  Palmtree: Learning an assembly language model for instruction embedding.  In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pages 3236–3251, 2021.
  * [14] Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli.  Graph matching networks for learning the similarity of graph structured objects.  In International conference on machine learning, pages 3835–3845. PMLR, 2019.
  * [15] Andrea Marcelli, Mariano Graziano, Xabier Ugarte-Pedrero, Yanick Fratantonio, Mohamad Mansouri, and Davide Balzarotti.  How machine learning is solving the binary function similarity problem.  In 31st USENIX Security Symposium (USENIX Security 22), pages 2099–2116, 2022.
  * [16] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe.  Weisfeiler and leman go neural: Higher-order graph neural networks.  In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602–4609, 2019.
  * [17] Zulie Pan, Taiyan Wang, Lu Yu, and Yintong Yan.  Position distribution matters: A graph-based binary function similarity analysis method.  Electronics, 11(15):2446, 2022.
  * [18] Kexin Pei, Zhou Xuan, Junfeng Yang, Suman Jana, and Baishakhi Ray.  Trex: Learning execution semantics from micro-traces for binary similarity.  arXiv preprint arXiv:2012.08680, 2020.
  * [19] Abdullah Qasem, Mourad Debbabi, Bernard Lebel, and Marthe Kassouf.  Binary function clone search in the presence of code obfuscation and optimization over multi-cpu architectures.  In Proceedings of the 2023 ACM Asia Conference on Computer and Communications Security, pages 443–456, 2023.
  * [20] Runjin Sun, Shize Guo, Jinhong Guo, Wei Li, Xingyu Zhang, Xi Guo, and Zhisong Pan.  Graphmoco: A graph momentum contrast model for large-scale binary function representation learning.  Neurocomputing, 575:127273, 2024.
  * [21] Yifan Sun, Changmao Cheng, Yuhan Zhang, Chi Zhang, Liang Zheng, Zhongdao Wang, and Yichen Wei.  Circle loss: A unified perspective of pair similarity optimization.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 6398–6407, 2020.
  * [22] Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky.  Instance normalization: The missing ingredient for fast stylization.  arXiv preprint arXiv:1607.08022, 2016.
  * [23] Hao Wang, Wenjie Qu, Gilad Katz, Wenyu Zhu, Zeyu Gao, Han Qiu, Jianwei Zhuge, and Chao Zhang.  Jtrans: Jump-aware transformer for binary code similarity detection.  In Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis, pages 1–13, 2022.
  * [24] Huaijin Wang, Pingchuan Ma, Yuanyuan Yuan, Zhibo Liu, Shuai Wang, Qiyi Tang, Sen Nie, and Shi Wu.  Enhancing dnn-based binary code function search with low-cost equivalence checking.  IEEE Transactions on Software Engineering, 49(1):226–250, 2022.
  * [25] Shih-Yuan Yu, Yonatan Gizachew Achamyeleh, Chonghan Wang, Anton Kocheturov, Patrick Eisen, and Mohammad Abdullah Al Faruque.  Cfg2vec: Hierarchical graph neural network for cross-architectural software reverse engineering.  In 2023 IEEE/ACM 45th International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP), pages 281–291. IEEE, 2023.