11institutetext: Univ. Grenoble Alpes, Inserm, U1216, Grenoble Institut
Neurosciences, 38000, FR 22institutetext: Pixyl, Research and Development
Laboratory, 38000 Grenoble, FR 33institutetext: Univ. Grenoble Alpes, Inria,
CNRS, Grenoble INP, LJK, 38000 Grenoble, FR

# Anisotropic Hybrid Networks for liver tumor segmentation with uncertainty
quantification

Benjamin Lambert 11 2 2 Pauline Roca 22 Florence Forbes 33 Senan Doyle 22
Michel Dojat 11

###### Abstract

The burden of liver tumors is important, ranking as the fourth leading cause
of cancer mortality. In case of hepatocellular carcinoma (HCC), the
delineation of liver and tumor on contrast-enhanced magnetic resonance imaging
(CE-MRI) is performed to guide the treatment strategy. As this task is time-
consuming, needs high expertise and could be subject to inter-observer
variability there is a strong need for automatic tools. However, challenges
arise from the lack of available training data, as well as the high
variability in terms of image resolution and MRI sequence. In this work we
propose to compare two different pipelines based on anisotropic models to
obtain the segmentation of the liver and tumors. The first pipeline
corresponds to a baseline multi-class model that performs the simultaneous
segmentation of the liver and tumor classes. In the second approach, we train
two distinct binary models, one segmenting the liver only and the other the
tumors. Our results show that both pipelines exhibit different strengths and
weaknesses. Moreover we propose an uncertainty quantification strategy
allowing the identification of potential false positive tumor lesions. Both
solutions were submitted to the MICCAI 2023 Atlas challenge regarding liver
and tumor segmentation.

###### Keywords:

Hepatocellular carcinoma Liver Segmentation Uncertainty

##  1 Introduction

Liver cancer is the sixth most common cancer worldwide, the fourth most common
cause of cancer-related death and hepatocellular carcinoma (HCC) in particular
is the most common type of primary liver cancer in adults. HCC is a cancer
with large therapeutic choices depending on the tumor staging. In case of
unresectable HCC, transarterial radioembolisation (TARE) is one of the
recommended treatments: it consists of the delivering of 20–60 uM-sized
yttrium-90 (Y90) microspheres to the tumor arterial supply, causing tumor
necrosis through radiation-induced DNA damage and eventual cell death [13]. To
calculate dosimetry and plan the intervention, the spatial extent of the tumor
needs to be determined [14]. In clinical routine, the liver and tumor are
delineated using contrast-enhanced magnetic resonance imaging with four phases
(precontrast, arterial, portal venous, delayed phases) allowing to
differenciate the tumor from the liver parenchyma. These tasks are time-
consuming and required high medical expertise.

In this context, automatic tools could reduce intra- and inter-observer
variability and help radiologists to save time. Several studies [1, 16]
proposed CE-MRI based deep learning methods to segment liver and HCC tumors
using private datasets (of 174 and 190 patients respectively). However, open-
source MRI datasets are scarce, and existing ones [3] do not contain manual
annotations, inhibiting the development of automated algorithms. In this
context, the "A Tumor and Liver Automatic Segmentation" (ATLAS) challenge and
dataset have been proposed. The aim of the challenge is to produce automatic
segmentation maps of liver and the tumor(s) using CE-MRI of patients with
unresectable HCC based on a small annotated training dataset (60 patients)
[12]. This challenge is organised in collaboration with the Medical Image
Computing and Computer Assisted Intervention (MICCAI) Workshop on Resource-
Efficient Medical Image Analysis (REMIA) which will take place during the
MICCAI 2023 edition in Vancouver, Canada. This paper describes our
contribution to the challenge, including two different pipelines to segment
liver and HCC tumors in CE-MRI. The first pipeline correspond to a multiclass
model that simultaneously segment the liver and tumors. In the second
pipeline, we used two different binary models, one focusing on the liver and
the other on the tumors. Additionally, we propose to complement the
segmentations with the estimation of an uncertainty score for each identified
tumor lesion, potentially guiding the reviewing of the automated result by the
user.

##  2 Materials and Methods

###  2.1 Dataset

The ATLAS challenge dataset is composed of an open-source training fold (60
subjects), allowing the development of segmentation models, as well as an
hidden test set (30 subjects) for evaluation [12]. For each subject, a unique
CE-MRI sequence is available, with one of the following phase: arterial,
delayed, post-contrast, non-contrast or unknown. A ground truth segmentation
mask is associated to each image, containing 3-classes: background, healthy
liver and tumor lesions. Training images exhibit variable resolution, ranging
from $0.684mm$ to $1.4mm$ in the XY plane, and from $2mm$ to $4.6mm$ in the
Z-axis (see Figure 1). To develop our approach, we adopt a 5-fold cross
validation scheme. In each fold, 40 subjects are used for training, 8 for
validation and 12 for testing. The distribution of data in each fold is
resumed in Table 1.

| Training (N=40) | Validation (N=8) | Test (N=12)
---|---|---|---
Fold | A | D | NC | P | U | A | D | NC | P | U | A | D | NC | P | U
1 | 23 | 6 | 1 | 5 | 5 | 3 | 0 | 1 | 3 | 1 | 7 | 2 | 0 | 2 | 1
2 | 24 | 6 | 1 | 4 | 5 | 2 | 1 | 0 | 4 | 1 | 7 | 1 | 1 | 2 | 1
3 | 24 | 5 | 1 | 4 | 6 | 2 | 1 | 1 | 4 | 0 | 7 | 2 | 0 | 2 | 1
4 | 25 | 5 | 1 | 5 | 4 | 2 | 1 | 1 | 3 | 1 | 6 | 2 | 0 | 2 | 2
5 | 24 | 6 | 0 | 6 | 4 | 3 | 1 | 1 | 2 | 1 | 6 | 1 | 1 | 2 | 2
Table 1: Data distribution in each fold. A: arterial, D: delayed, NC: non-
contrast, P: portal, U: unkwon

###  2.2 Segmentation pipelines

In this section, we start by describing the design choices that are common to
both pipelines, namely the neural network architecture and loss function.
Then, we detail the particularity of both approaches (see Figure 2 for an
illustration).

Figure 1: Distribution of the spatial resolution in the training dataset.
Colors indicate the corresponding CE-MRI phase. To facilitate visualization,
the plot is generated using jitter.

####  2.2.1 Joint design choices

The first challenge to tackle is the anisotropy of the data, with the Z
resolution being up to 4 times that in the plane. Instead of preprocessing the
data to obtain a uniform spatial resolution, we instead chose to use a
segmentation neural network able to handle the intrinsic anisotropy of the raw
data. To this end, our two pipelines revolve around the use of the Anistropic
Hybrid U-Net (AHUNet) [8]. This architecture is composed of a pretrained 2D
convolutional encoder ignoring between-slice information, and a 3D
convolutional decoder that reconstitute the 3D context. Second, although not
the scope of the ATLAS challenge, we aim at enhancing the segmentation of the
models by an uncertainty quantification module allowing to estimate a
confidence score for each tumor lesion. Thus, the calibration of the output
probability is of primary importance, which is usually poor with modern
networks [5]. To circumvent this limitation, we resort to using the recently
proposed Margin-based Label Smoothing loss [9] which has been proposed to
improve the calibration of medical image segmentation models.

Figure 2: Illustration of our two proposed pipelines, namely multiclass and
binary.

###  2.3 Pipeline Multi-class

The most direct approach to obtain the segmentation of the liver and tumors is
to train a multi-class AHUnet using the 3-classes ground truth masks. We adopt
a patch-based approach, following which the input 3D MRI is divided into
patches that are processed independently by the model. To guide the selection
of the patches size, we computed bounding-boxes around each liver and tumor
lesion in the training dataset using the ground truth masks (see Figure 3).
This study indicates that defining a patch size of $256\times 256\times 64$
allows the encompassment of all tumor lesions, while also encompassing most of
the livers.

###  2.4 Dual binary pipeline

Motivated by the observation that the segmentation of the liver was a much
more easier task than tumor segmentation, we propose an alternative pipeline
that disentangles both tasks. To do so, two distinct binary models are
trained: i) a model that segments the _overall_ liver (concatenation of the
healthy liver class and the tumors) and ii) a model that segments the tumor
lesions. From the bounding-box analysis (Figure 3), we kept the patch size of
$256\times 256\times 64$ for the binary liver model. However, for the binary
tumor model, we use a smaller patch size of $128\times 128\times 64$ as it
allows to reduce the imbalance between background and tumor voxels, while
still encompassing most of the nodules. At inference, the input MRI is
processed by each model. The two resulting binary masks are then aggregated to
reconstitute the final 3-class segmentation.

###  2.5 Post-processing Module

Post-processing has been proved as an important step for the automated
segmentation of the liver in CT and MRI [4]. We adopt a 3-steps post-
processing procedure, which is similar for both pipelines:

  1. Step 1:

Only the largest connected component for the liver is kept. A binary
morphology _fill holes_ operation [15] is performed on the resulting binary
mask.

  2. Step 2:

Tumor lesions outside the liver are removed. This process differs slightly
depending on the pipeline. For the multi-class approach, the binary mask of
each identified tumor lesion is dilated. If this dilated mask has no
intersection with liver voxels, the lesion is deleted. For the binary-
approach, the process is more straight-forward, as we simply multiply the
liver mask by the tumor mask. As an effect, tumor voxels outside the liver are
filtered out.

  3. Step 3:

A binary closing morphological operation is applied to the remaining tumor
lesions to improve the smoothness of the borders.

Figure 3: Dimensions of bounding boxes encompassing the tumor lesions (left)
and liver (right) on the Atlas dataset. In overlay we present the selected
patch sizes of $256\times 256\times 64$ (red) and $128\times 128\times 64$
(blue).

###  2.6 Lesion Uncertainty Quantification

Additionally to the segmentation of the liver and tumors, we propose to add a
lesion uncertainty quantification module to our pipelines. This module
complements the segmentation with an uncertainty score for each unique nodule.
To achieve this, we collect the tumor probabilities $p_{i,tumor}$
($i\in[1,N]$) for each of the N voxels of the lesion. The _lesion-wise_
uncertainty score is then taken as:

$L_{unc}=1-\frac{1}{N}\sum_{i=1}^{N}p_{i,tumor}$ (1)

###  2.7 Evaluation Protocol

The ATLAS challenge proposes to compare participants based on 9 metrics. The
Dice, Surface Dice (SD), Haussdorf Distance (HD) and the Average Symmetric
Surface Distance (ASD) are computed for both the _overall_ liver
(concatenation of the healthy liver and tumor voxels) and the tumors. Lastly,
the Root Mean Square Error (RMSE) on tumor burden is computed, based on the
computed volumes for the liver and tumors. To compare each pipeline, we train
models on each of the 5 folds, and metrics are aggregated over the 5 test
folds. Finally, qualitative assessment of the computed tumor uncertainty
scores is assessed by monitoring the distribution of uncertainties for TP
(non-zero intersection with the ground truth tumor mask) and FP (null
intersection) lesions.

###  2.8 Ablation Study

To demonstrate the positive impact of using AHUnet over standard 3D
segmentation architecture, we reproduced the multi-class pipeline by replacing
the AHUnet by a Dynamic Unet 3D (DynUnet) which has been successful in various
medical image segmentation challenges [6]. We also run the evaluation
procedure without post-processing to demonstrate its gain on performance.

###  2.9 Implementation Details

Our framework is implemented in Pytorch [10] and experiments are carried on a
Nvidia RTX A5000 GPU. AHUnet and DynUnet are implemented using the open-source
MONAI library [2]. Models are trained using the ADAM optimizer [7] with a
learning rate of $2e-4$ and a batch size of $2$, until the loss on validation
data stagnates over 30 epochs. During training we use Data Augmentation
implemented using the TorchIO library [11] comprising spatial (rotation,
flips, affine transforms) as well as intensity (contrast, gamma, bias, noise)
augmentations.

##  3 Results and Discussion

Table 2: Performance on the 60 subjects aggregated over the 5 test folds. Mean results are presented along the standard deviation. |  | Multi-class AHUnet | Dual binary AHUnet | DynUnet
---|---|---|---|---
| Post-processing | ✓ | $\times$ | ✓ | $\times$ | ✓
Liver | ASD $\downarrow$ | $2.06\pm 1.78$ | $3.31\pm 3.53$ | 1.99$\pm$2.35 | $5.03\pm 5.01$ | $2.57\pm 2.70$
Dice $\uparrow$ | 0.94$\pm$0.04 | $0.93\pm 0.04$ | 0.94$\pm$0.06 | $0.92\pm 0.07$ | $0.93\pm 0.06$
HD ($\times 10^{1}$) $\downarrow$ | $3.22\pm 1.78$ | $11.27\pm 6.03$ | 2.85$\pm$1.69 | $12.79\pm 6.76$ | $3.60\pm 2.60$
SD $\uparrow$ | $0.82\pm 0.10$ | $0.80\pm 0.11$ | 0.84$\pm$0.12 | $0.81\pm 0.12$ | $0.81\pm 0.13$
Tumor | ASD ($\times 10^{1}$) $\downarrow$ | 1.46$\pm$2.5 | $1.62\pm 2.50$ | 1.53$\pm$2.31 | $3.51\pm 4.21$ | $1.90\pm 2.25$
Dice $\uparrow$ | 0.57$\pm$0.28 | 0.57$\pm$0.28 | $0.54\pm 0.29$ | $0.49\pm 0.30$ | $0.49\pm 0.29$
HD ($\times 10^{1}$) $\downarrow$ | 6.73$\pm$3.84 | $8.87\pm 5.74$ | $7.77\pm 4.13$ | $18.0\pm 7.89$ | $8.49\pm 4.34$
SD $\uparrow$ | 0.40$\pm$0.21 | 0.40$\pm$0.21 | 0.41$\pm$0.22 | $33.9\pm 0.21$ | $0.33\pm 0.20$
RMSE ($\times 10^{-2}$) $\downarrow$ | $0.73\pm 1.38$ | $0.75\pm 0.01$ | 0.72$\pm$1.30 | $1.17\pm 2.10$ | $1.04\pm 2.19$

Segmentation performance of each pipeline is presented in Table 2. Qualitative
assessment of lesion uncertainty is presented in Figure 4.

For both pipelines, the liver is far better segmented than tumors. On the
multi-class AHUnet pipeline for example a mean Dice score of 0.94 is reached
for liver segmentation whereas for tumor we reached a value of 0.57. This can
be explained by the small volume of tumors as compared to the liver, and by
the important variability in appearance depending on the contrast phase.
Moreover, these results are similar to Bousabarah study [1] that obtained Dice
scores per case of 0.91 and 0.48 for liver and tumor segmentation respectively
using a deep-learning method based on the four phases of CE-MRI exams. Our
post-processing module enabled an important gain on the 9 metrics, for both
pipelines. The dual binary pipeline obtained better metrics on the liver than
the multi-class one. However, for tumor, the multi-class AHUnet is slightly
superior. Finally, the multi-class pipeline relying on the DynUnet (ablation
study) is worst than the multi-class AHUnet for all metrics, showing the
relevance of using a neural network specifically designed for anisotropic
data.

To assess if the differences between both proposed pipelines are statistically
significant, we performed a signifance analysis, presented in Table 3. We
first test the hypothesis that the obtained scores are drawn from a normal
distribution (Shapiro’s test). If the hypothesis is valid, one-sided student
T-test are performed, else we opt for Wilcoxon’s tests. Results show that the
Liver metrics are significativelly better for the Dual binary pipeline than
for the multiclass pipeline. On the contrary, the Tumor HD is significatively
lower for the multi-class pipeline than for the binary one. Other metrics are
not statistically different between both pipelines (Tumor ASD, Dice, HD and
RMSE).

Finally, the qualitative assessment of our lesion uncertainty module (Figure
4, left) shows that FP lesions tend to be attributed to higher uncertainty
scores than TP lesions). The proposed score could thus be used to draw the
user’s attention to uncertain lesions, that are more likely to be FP. The
proposed lesion uncertainty score is highly correlated with the lesion volume
(Figure 4, right), reaching a Spearman correlation coefficient of $-0.82$,
which is intuitive as FP lesions are more frequent among small lesions. To
complement this analysis, we provide two examples of the proposed lesion
quantification in Supplementary Material.

Figure 4: Qualitative evaluation of the tumor lesion uncertainty obtained with the multi-class pipeline. Left: histogram of uncertainty estimates with respect to the lesion status (TP or FP). Right: lesion uncertainty with respect to the lesion volume (in log-scale). Table 3: Significance analysis between the two pipelines. B: binary pipeline; M: multi-class pipeline. |  |  | Shapiro
---
p-value
Hypothesis | Test | p-value |  | Significance
---
($p<0.05$)
Liver | ASD $\downarrow$ | $4.9\times 10^{-13}$ | B < M | Wilcoxon | $6.2\times 10^{-4}$ | ✓
Dice $\uparrow$ | $7.1\times 10^{-14}$ | B > M | Wilcoxon | $7.1\times 10^{-14}$ | ✓
HD $\downarrow$ | $3.0\times 10^{-4}$ | B < M | Wilcoxon | $4.6\times 10^{-2}$ | ✓
SD $\uparrow$ | $1.9\times 10^{-9}$ | B > M | Wilcoxon | $1.1\times 10^{-7}$ | ✓
Tumor | ASD $\downarrow$ | $3.0\times 10^{-7}$ | M < B | Wilcoxon | $2.0\times 10^{-1}$ | $\times$
Dice $\uparrow$ | $2.3\times 10^{-4}$ | M > B | Wilcoxon | $2.3\times 10^{-1}$ | $\times$
HD $\downarrow$ | $4.1\times 10^{-4}$ | M < B | Wilcoxon | $1.4\times 10^{-3}$ | $\checkmark$
SD $\uparrow$ | $3.8\times 10^{-1}$ | B > M | T-test | $7.6\times 10^{-1}$ | $\times$
RMSE $\downarrow$ | $2.7\times 10^{-8}$ | B < M | Wilcoxon | $7.7\times 10^{-1}$ | $\times$

##  4 Conclusion

In this work, we addressed the problem of segmenting the liver and tumors in
CE-MRI. Using the AHUnet architecture as cornerstone, we propose two different
pipelines, multi-class and dual binary, demonstrating a gain on tumor and
liver segmentation respectively. Additionally, we propose to quantify the
uncertainty of identified nodules, which can be used to improve the
interpretability of the automated predictions. For the final ATLAS 2023
challenge submissions, models trained on the 5 folds are aggregated in an
ensemble, for each pipeline separately. Both pipelines (binary and multiclass)
are submitted as separate algorithms.

##  5 Supplementary Material

Figure 5: Case A: patient with a FP lesion (dashed arrow) associated with a
high uncertainty value ($=0.47$); Case B: patient presenting one TP lesion
(arrow) associated with a low lesion uncertainty (0.13) and a second FP lesion
(dashed arrows) associated with a low uncertainty (0.17) in hypersignal on
arterial phase. Complementary information (precontrast, portal and delayed CE-
MRI T1 phases) are required to assess if this nodule is a CHC.

## References

  * [1] Bousabarah, K., Letzen, B., Tefera, J., Savic, L., Schobert, I., Schlachter, T., Staib, L.H., Kocher, M., Chapiro, J., Lin, M.: Automated detection and delineation of hepatocellular carcinoma on multiphasic contrast-enhanced MRI using deep learning 46(1), 216–225, publisher: Springer
  * [2] Cardoso, M.J., Li, W., Brown, R., Ma, N., Kerfoot, E., Wang, Y., Murrey, B., Myronenko, A., Zhao, C., Yang, D., et al.: Monai: An open-source framework for deep learning in healthcare. arXiv preprint arXiv:2211.02701 (2022)
  * [3] Clark, K., Vendt, B., Smith, K., Freymann, J., Kirby, J., Koppel, P., Moore, S., Phillips, S., Maffitt, D., Pringle, M., et al.: The cancer imaging archive (tcia): maintaining and operating a public information repository. Journal of digital imaging 26, 1045–1057 (2013)
  * [4] Furtado, P.: Loss, post-processing and standard architecture improvements of liver deep learning segmentation from computed tomography and magnetic resonance. Informatics in Medicine Unlocked 24, 100585 (2021)
  * [5] Guo, C., Pleiss, G., Sun, Y., Weinberger, K.Q.: On calibration of modern neural networks. In: International conference on machine learning. pp. 1321–1330. PMLR (2017)
  * [6] Isensee, F., Petersen, J., Klein, A., Zimmerer, D., Jaeger, P.F., Kohl, S., Wasserthal, J., Koehler, G., Norajitra, T., Wirkert, S., et al.: nnu-net: Self-adapting framework for u-net-based medical image segmentation. arXiv preprint arXiv:1809.10486 (2018)
  * [7] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. 3rd International Conference on Learning Representations, ICLR 2015 (2015)
  * [8] Liu, S., Xu, D., Zhou, S.K., Pauly, O., Grbic, S., Mertelmeier, T., Wicklein, J., Jerebko, A., Cai, W., Comaniciu, D.: 3d anisotropic hybrid network: Transferring convolutional features from 2d images to 3d anisotropic volumes. In: Medical Image Computing and Computer Assisted Intervention–MICCAI 2018: 21st International Conference, Granada, Spain, September 16-20, 2018, Proceedings, Part II 11. pp. 851–858. Springer (2018)
  * [9] Murugesan, B., Liu, B., Galdran, A., Ayed, I.B., Dolz, J.: Calibrating segmentation networks with margin-based label smoothing. Medical Image Analysis 87, 102826 (2023)
  * [10] Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al.: Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems 32 (2019)
  * [11] Pérez-García, F., Sparks, R., Ourselin, S.: Torchio: a python library for efficient loading, preprocessing, augmentation and patch-based sampling of medical images in deep learning. Computer Methods and Programs in Biomedicine 208, 106236 (2021)
  * [12] Quinton, F., Popoff, R., Presles, B., Leclerc, S., Meriaudeau, F., Nodari, G., Lopez, O., Pellegrinelli, J., Chevallier, O., Ginhac, D., et al.: A tumour and liver automatic segmentation (atlas) dataset on contrast-enhanced magnetic resonance imaging for hepatocellular carcinoma. Data 8(5), 79 (2023)
  * [13] Reig, M., Forner, A., Rimola, J., Ferrer-Fàbrega, J., Burrel, M., Garcia-Criado, A., Kelley, R.K., Galle, P.R., Mazzaferro, V., Salem, R., Sangro, B., Singal, A.G., Vogel, A., Fuster, J., Ayuso, C., Bruix, J.: BCLC strategy for prognosis prediction and treatment recommendation: The 2022 update 76(3), 681–693. https://doi.org/10.1016/j.jhep.2021.11.018
  * [14] Smits, M.L., Elschot, M., Sze, D.Y., Kao, Y.H., Nijsen, J.F., Iagaru, A.H., de Jong, H.W., van den Bosch, M.A., Lam, M.G.: Radioembolization dosimetry: the road ahead. Cardiovascular and interventional radiology 38, 261–269 (2015)
  * [15] Virtanen, P., Gommers, R., Oliphant, T.E., Haberland, M., et al.: SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods 17, 261–272 (2020)
  * [16] Zheng, R., Wang, Q., Lv, S., Li, C., Wang, C., Chen, W., Wang, H.: Automatic liver tumor segmentation on dynamic contrast enhanced mri using 4d information: deep learning model based on 3d convolution and convolutional lstm. IEEE Transactions on Medical Imaging 41(10), 2965–2976 (2022)


# Game-Theoretic Malware Detection

Revan MacQueen  University of AlbertaCanada ,  Natalie Bombardieri  University
of AlbertaCanada ,  James R. Wright  University of AlbertaCanada and  Karim
Ali  University of AlbertaCanada

###### Abstract.

Malware attacks are costly. To mitigate against such attacks, organizations
deploy malware detection tools that help them detect and eventually resolve
those threats. While running only the best available tool does not provide
enough coverage of the potential attacks, running all available tools is
prohibitively expensive in terms of financial cost and computing resources.
Therefore, an organization typically runs a set of tools that maximizes their
coverage given a limited budget. However, how should an organization choose
that set? Attackers are strategic, and will change their behavior to
preferentially exploit the gaps left by a deterministic choice of tools. To
avoid leaving such easily-exploited gaps, the defender must choose a random
set.

In this paper, we present an approach to compute an optimal randomization over
size-bounded sets of available security analysis tools by modeling the
relationship between attackers and security analysts as a leader-follower
Stackelberg security game. We estimate the parameters of our model by
combining the information from the VirusTotal dataset with the more detailed
reports from the National Vulnerability Database. In an empirical comparison,
our approach outperforms a set of natural baselines under a wide range of
assumptions.

††journalyear: 2021

##  1\. Introduction

A recent study by the Ponemon Institute (Security, 2020) shows that malware
attacks have been steadily growing with an average cost of US$4.5 million per
attack. To mitigate against such attacks, companies typically run malware
detection tools that help security analysts find and eventually resolve
potential risks against their running systems. To achieve that, a company may
follow one of three approaches. First, a company may run the best tool that
they could acquire or develop. However, as the VirusTotal dataset (VirusTotal,
[n.d.]) shows, no single tool is sufficient to detect all attacks. In the
dataset, none of the 86 tools detect more than 84% of the vulnerabilities in
the analyzed malware files. Second, a company may run all possible available
tools. However, this is likely to be impractical due to prohibitive financial
costs and limited computing resources. In fact, in their 2019 study, Accenture
estimated that only 32% of companies worldwide deploy discovery and
investigation tools due to their rising costs (Accenture, 2021). Third, to
achieve the best results given a limited budget, the company may alternatively
run a set of tools that can detect most of the potential attack scenarios
against the company’s systems. But which set of tools should the company
choose to run?

A tempting solution is to run the set of tools with the _best historical_
coverage (e.g., that would have detected most historical attacks). However,
security is a strategic domain: attackers will change their behavior in
response to the defender’s actions. Any deterministic choice of tools that
does not provide exhaustive coverage will leave gaps that an attacker may
exploit. To avoid leaving an easily exploitable attack surface without
exhaustively running all available tools, the defender must randomly select
the set of tools to run. However, not all randomizations are equal.

In this paper, we present a method for finding the _optimal_ randomization
over size-bounded sets of tools, under the assumption that the attackers will
optimally respond to whichever randomization that the defender chooses. To
achieve that, we present a specialized version of a framework of game
theoretic models known as Stackelberg security games (Jain et al., 2010).
Prior work has applied the Stackelberg framework to a wide variety of security
problems such as airport security (Jain et al., 2010), preventing fare evasion
(Yin et al., 2012), and detecting and preventing illegal poaching (Yang et
al., 2014). Our work applies the framework to malware detection and provides
an algorithm for finding an optimal randomization over detection tools for the
defender.

Modelling any scenario game-theoretically requires a description of the
participants’ utilities; this is often specified manually by domain experts
(e.g., Jain et al., 2010). To estimate the utilities in our model, we use the
data from the VirusTotal dataset of malicious files (VirusTotal, [n.d.]) in
conjunction with information on the impact and difficulty of exploitation of
the associated vulnerabilities from the National Vulnerability Database
(Database, [n.d.]a). This estimate is not intended to be used “out of the
box”; rather, we use it to demonstrate the construction of a utility model
from real-world data, and to construct a realistic scenario for evaluating the
performance of our proposed model in comparison to several natural benchmarks.
When applying our framework, the utility model can and should be customized to
account for individual factors such as the available set of tools, the
effectiveness of the tools at detecting different attacks, the severity of
undetected attacks, and the relative costs of running tools.

Our empirical evaluation shows that our proposed randomization scheme
outperforms a number of deterministic strategies for choosing the _best
historical_ set of tools, as well as naive uniform randomization schemes. Some
parameters of our utility model represent subjective tradeoffs between
different costs such as the relative importance of detecting too many attacks
(i.e., false positives) compared to too few (i.e., false negatives). Our
evaluation includes a sensitivity analysis for this subset of parameters that
cannot be estimated from data; we find that our results do not qualitatively
differ across a wide range of reasonable settings.

To summarize, we make the following contributions:

  1. (1)

Formalize the malware detection problem within the Stackelberg security game
framework, and show how to use the mixed integer linear program formulation of
Jain et al. (2010) to find an optimal randomization over sets of tools.

  2. (2)

Estimate a realistic utility model for the attacker and defender using data
from the National Vulnerability Database (Database, [n.d.]a), the VirusTotal
malware dataset (VirusTotal, [n.d.]), and prior work on false positive rates
of malware detection tools (Zhu et al., 2020).

  3. (3)

Evaluate the performance of our proposed solution using the estimated utility
model in comparison to a set of natural baselines.

##  2\. Background

In this section, we begin by introducing Stackelberg games. We then define the
solution concept that we use, the strong Stackelberg equilibrium. Finally, we
describe a standard specialization of Stackelberg games for use in the
security domain.

###  2.1. Stackelberg Games

Stackelberg games (von Stackelberg et al., 2010) are non-cooperative games
between two players: a leader $L$ and a follower $F$. In a Stackelberg game,
the leader chooses a distribution over actions, then the follower chooses
their own action distribution, after having observed the leader’s action
distribution. An action for each player is then sampled from their chosen
distributions, and each player realizes a utility (i.e., payoff) based on the
pair of sampled actions.

Unlike normal-form games such as rock-paper-scissors or Prisoner’s Dilemma, in
which players choose their actions simultaneously, Stackelberg games are
played sequentially, with the leader making decisions first and the follower
second. Stackelberg games also differ from extensive-form games such as chess
or poker by the timing of the sampling of actions. In an extensive-form game,
one player’s action is sampled before the next player begins their turn; thus,
the second player’s strategy may only condition upon the first player’s
realized action. In Stakelberg games, the second player may condition on the
distribution of the first player’s actions.

Each player $i$ has a set $A_{i}$ of available _actions_. An _action profile_
$(a_{L},a_{F})\in A_{L}\times A_{F}$ is a joint assignment to actions for each
player. A _strategy_ $s_{i}\in S_{i}=\Delta(A_{i})$ for an agent $i$ is a
probability distribution over its action set $A_{i}$, where each action
$a_{i}\in A_{i}$ is played with probability $s_{i}(a_{i})$.111We denote the
set of all distributions over $X$ with the notation $\Delta(X)$. A _pure
strategy_ is a strategy that assigns probability 1 to a single action, whereas
a _mixed strategy_ is a strategy that assigns positive probability to multiple
actions. A _strategy profile_ ($s_{L},s_{F})\in S_{L}\times S_{F}$ is a joint
assignment of mixed strategies for each player.

The outcome of the game is fully determined by the realized action profile.
Each player $i$ has a _utility function_ $u_{i}:A_{L}\times
A_{F}\to\mathbb{R}$ that maps each action profile to a _utility_ that measures
how much the agent prefers the outcome, with each agent preferring higher-
utility outcomes. Each player aims to maximize their expected utility, where
the expectations are taken over the action distributions. Players seek only to
maximize their own utility function; the utilities of other players are
important to a player only insofar as they help to predict those players’
actions.

We overload the notation of the utility function to represent expected utility
when its arguments are strategies:

(1) $u_{i}(s_{L},s_{F})\doteq\sum_{(a_{L},a_{F})\in A_{L}\times
A_{F}}s_{L}(a_{L})s_{F}(a_{F})u_{i}(a_{L},a_{F}).$

Translating our informal description of Stackelberg games to use the notation
that we have just defined, a Stackelberg game proceeds as follows:

  1. (1)

The leader chooses a strategy $s_{L}\in S_{L}$.

  2. (2)

The follower observes $s_{L}$.

  3. (3)

The follower chooses a strategy $s_{F}\in S_{F}$.

  4. (4)

An action profile $(a_{L},a_{F})$ is sampled with $a_{L}\sim S_{L}$ and
$a_{F}\sim S_{F}$.

  5. (5)

Each agent $i$ receives utility $u_{i}(a_{L},a_{F})$.

###  2.2. Stackelberg Equilibrium

The utility that a player receives depends upon both its own actions, and the
actions of the other player. We say that an action is a _best response_ to the
strategy of the other player when its expected utility is maximal given the
strategy of the other player. Formally, we define the set of $i$’s best
responses to strategy $s_{-i}$ as

(2) $BR_{i}(s_{-i})\doteq\\{a_{i}\in A_{i}\mid u_{i}(a_{i},s_{-i})\geq
u_{i}(a^{\prime}_{i},s_{-i})\quad\forall a^{\prime}_{i}\in A_{i}\\}$

where $s_{-i}$ is the strategy of the other player.

In a Stackelberg game, a profile in which both players are behaving optimally
is called a Stackelberg equilibrium. There can be multiple such equilibria in
a game, especially when the follower is indifferent between multiple actions
given the strategy of the leader. In this paper, we focus on a particular
refinement of Stackelberg equilibrium called the strong Stackelberg
equilibrium (SSE), in which the attacker breaks ties in favor of the defender
(Von Stengel and Zamir, 2004).

###### Definition 0 (Strong Stackelberg Equilibrium).

A strategy profile $(s^{*}_{L},s^{*}_{F})$ is a _strong Stackelberg
equilibrium_ if it satisfies the following:

  1. (1)

$u_{L}(s^{*}_{L},BR_{F}(s^{*}_{L}))\geq
u_{L}(s^{\prime}_{L},BR_{F}(s^{\prime}_{L}))\quad\forall s^{\prime}_{L}\in
S_{L}$,

  2. (2)

$s_{F}(a_{F})>0\implies a_{F}\in BR_{F}(s^{*}_{L})\quad\forall a_{F}\in
A_{F}$, and

  3. (3)

$u_{L}(s^{*}_{L},s^{*}_{F})\geq(s^{*}_{L},a_{F})\quad\forall a_{F}\in
BR_{F}(s^{*}_{L})$.

It may seem implausible to assume that the follower would break ties in favor
of the leader; after all, does the follower not only care about their own
utility? Would it not be more conservative to assume that the follower will
break ties by choosing the best response with the _lowest_ utility to the
leader?222In fact, this assumption is sometimes made. A strategy profile in
which the follower breaks ties to minimize the leader’s utility is called a
_weak_ Stackelberg equilibrium. In fact, by changing their action distribution
by an arbitrarily small amount, the leader can always cause the follower to
strictly prefer one of their best responses. Since this change is very small,
the utility cost to the leader is also infinitesimal. Thus, assuming that the
follower will choose the best-response which is optimal for the leader is
essentially without loss of generality.

###  2.3. Security Games

Security games are a frequently used framework in which security situations
are modeled as a Stackelberg game (Avenhaus et al., 2002). The two players are
the _Defender_ , who plays the leader role, and the _Attacker_ , who plays the
follower role. In a security scenario, the attacker can typically observe the
defender’s actions (e.g., randomized patrols) over time before choosing their
own attack, allowing the attacker to estimate the defender’s random
distribution over actions. This setup motivates the use of Stackelberg games
for modeling these scenarios.

In this paper, we use the _compact security games_ framework of Kiekintveld et
al. (2009). The defender seeks to defend a set of _targets_
$T=\\{t_{1},\ldots,t_{n}\\}$ using a set of _resources_
$R=\\{r_{1},\ldots,r_{m}\\}$. The attacker’s action set consists of the
targets; they choose a target or distribution over targets to attack. The
defender’s actions set consists of the resources; they choose a resource or
distribution over resources before the attacker chooses an action.

A “resource” in the model may represent multiple actual real-world resources.
A single resource is intended to model a plan that the defender could feasibly
execute. For example, in the airport security domain, Jain et al. (2010)
represent a single feasible schedule of patrols and placements of vehicle
checkpoints as a resource. As we describe in Section 3, we represent a set of
malware detection tools to run as a single resource.

Each of the Defender’s resources $r$ induces a _coverage vector_
$\bm{p^{r}}\in[0,1]^{n}$, with each element $p^{r}_{t}$ representing the
probability that target $t$ will be “covered”. When the attacker attacks a
covered target, the attack fails; otherwise, the attack succeeds. When an
attack on target $t$ succeeds, the attacker receives utility $u^{1}_{a}(t)$
and the defender receives utility $u^{1}_{d}(t)$; when an attack on target $t$
fails, the attacker receives utility $u^{0}_{a}(t)$ and the defender receives
utility $u^{0}_{d}(t)$. These utilities are not constrained to be zero-sum;
i.e., it is not necessarily the case that $u^{1}_{d}(t)=-u^{1}_{a}(t)$.

The utility of a player $i$ when the attacker attacks target $t$ and the
defender chooses a resource $r$ with coverage vector $\bm{p}^{r}$ is thus

(3) $u_{i}(\bm{p}^{r},t)=p^{r}_{t}u_{i}^{0}(t)+(1-p^{r}_{t})u_{i}^{1}(t).$

When the defender chooses a mixed strategy $s_{d}\in\Delta(R)$ and the
attacker chooses a mixed strategy $s_{a}\in\Delta(T)$, the expected utilities
are computed in the straightforward way as

(4) $u_{i}(s_{d},s_{a})=\sum_{r\in R}\sum_{t\in
T}s_{d}(r)s_{a}(t)u_{i}(\bm{p}^{r},t).$

##  3\. Security Games for Malware Detection

Due to both time and resource constraints, it is not practical to use every
available detection tool to defend against malware. Nonetheless, if the
defender always uses the same subset of the available tools, then malware
authors may target vulnerabilities that the particular set of tools does a
poor job of detecting. We assume that the attacker is _strategic_ , in the
sense that they will adjust their behavior in response to the actions of the
defender. For this reason, simply using a tool (or set of tools) that performs
well on the historic distribution of attacks is not sufficient.

Our work applies the security games framework to malware detection. Although
our model assumes that there may be many non-colluding attackers, the model
represents attacks from different attackers as separate games, each with a
single attacker. This is why we refer to each game having a single attacker,
even though there would likely be more than one attacker in reality. However,
we assume all attackers have the same utility function and, therefore, the
optimal strategy for the defender generalizes over all games.

In our model, the organization/company plays the role of the defender in the
security game, while a potential hacker is the attacker. The attacker seeks to
upload a file that exploits a security vulnerability; the defender aims to
prevent this exploitation, while still providing access to their services. The
attacker’s action set consists of a set $V$ of vulnerabilities to target.

The defender has a set of malware detection tools available, each with
associated probabilities of detecting attacks on different vulnerabilities (as
well as false positive rates). We constrain the maximum number of tools that
the defender can use in each schedule by a budget $b$, the number of tools
that they are able or willing to run. The set $S$ of resources thus consists
of all subsets of detection tools containing $b$ or fewer tools. We refer to
these subsets as _schedules_ of detection tools, with a _budget_ of $b$. The
defender chooses a distribution over schedules before the attacker chooses
which vulnerability to attack. The goal with this approach is to determine an
optimal distribution, which is chosen once, and then sampled from without
further changing it.

###  3.1. Utility Model

Each schedule $s$ has an associated probability $p(s,v)$ of detecting an
attack targeting $v$, and an overall cost $c_{d}(s)$ of running the schedule.
In our empirical evaluation, we estimate the detection probabilities and false
positive rate of a schedule based on the detection probabilities and false
positive rates of the underlying tools, and construct a cost based on the
false positive rate. Other costs such as resource requirements and runtimes
can easily be included when implementing a model such as the one we present,
but such data was not available to us.

Different vulnerabilities have different impacts on the defender when attacked
without being detected. We say that a defender receives a negative “reward”
$r_{d}(v)$ for failing to detect an attack on vulnerability $v$. The attacker
receives a reward $r_{a}(v)$ for successfully attacking $v$, and incurs a cost
$c_{a}(v)$ for attacking $v$. We estimate the cost $c_{a}$ based on the
exploitability of the vulnerability (defined in Subsection 4.1) . We estimate
the reward $r_{a}(v)$ to the attacker and negative reward $r_{d}(v)$ to the
defender of a successful attack on $v$ based on the impact of the exploit.

The attacker’s utility from attacking vulnerability $v$ when the defender
chooses schedule $s$ is

(5) $u_{a}(s,v)\doteq(1-p(s,v))r_{a}(v)-\gamma_{a}c_{a}(v),$

where $\gamma_{a}$ represents the relative weighting of the units of reward
and the units of cost. The attacker incurs the cost $c_{a}(v)$ regardless of
whether the attack is detected, but only receives the reward $r_{a}(v)$ if the
attack is not detected.

The utility for the defender is

(6) $u_{d}(s,v)\doteq(1-p(s,v))r_{d}(v)-\gamma_{d}c_{d}(s),$

where $\gamma_{d}$ again trades off units of cost and units of reward. We
assume the reward for a detected attack to be zero for the defender. Equations
(5) and (6) differ from Equation (1) because they specify the utility of an
action profile (i.e., a schedule chosen by the defender, and a vulnerability
chosen by the attacker), whereas Equation (1) takes expectation over these
action profile utilities to compute the expected utility of a profile of mixed
strategies.

###  3.2. Finding Optimal Randomized Strategies

To solve for a strong Stackelberg equilbrium (SSE) for the game defined above,
we encode the game as a mixed integer linear program (MILP) (Jain et al.,
2010). By solving the MILP, we efficiently compute the optimal schedule
randomization for the defender, assuming that the attacker will best respond.
We first specify the MILP in Equations (7)–(13), translated from the notation
of Jain et al. (2010) to our own. We then describe the meaning of each
constraint.

(7) maximize $\displaystyle\widetilde{U_{d}}$ (8) subject to
$\displaystyle\widetilde{y}_{v}\in\\{0,1\\}\quad\forall v\in V$ (9)
$\displaystyle\sum_{v\in V}\widetilde{y}_{v}=1$ (10) $\displaystyle
0\leq\widetilde{p}_{s}\leq 1\quad\forall s\in S$ (11) $\displaystyle\sum_{s\in
S}\widetilde{p}_{s}=1$ (12) $\displaystyle\widetilde{U_{d}}-\sum_{s\in
S}\widetilde{p}_{s}u_{d}(s,v)\leq(1-\widetilde{y}_{v})Z\quad\forall v\in V$
(13) $\displaystyle 0\leq$ $\displaystyle\widetilde{U_{a}}-\sum_{s\in
S}\widetilde{p}_{s}u_{a}(s,v)\leq(1-\widetilde{y}_{v})Z\quad\forall v\in V$

The defender’s decision variables are the set $\widetilde{p}_{s}\;\forall s\in
S$, where $\widetilde{p}_{s}$ gives the probability of running schedule $s$.
Constraints (10) and (11) ensure that the vector $\widetilde{p}$ is a valid
probability distribution.

The attacker’s decision variables are the set $\widetilde{y}_{v}\;\forall v\in
V$, where $\widetilde{y}_{v}$ gives the probability of attacking vulnerability
$v$. Constraints (8) and (9) ensure that exactly one element of
$\widetilde{y}$ will be set to 1, with all others set to 0; i.e., the Attacker
is constrained to deterministically attack a single vulnerability. As
discussed in Section 2.2, this is essentially without loss of generality.

Constraint (13) forces the attacker strategy $\widetilde{y}$ to be a best
response to the defender’s strategy, as follows. First, for the vulnerability
$v^{*}$ that is exploited, $\widetilde{U_{a}}$ must exactly equal the
attacker’s expected utility $\sum_{s\in S}\widetilde{p}_{s}u_{a}(s,v^{*})$,
because the difference between $\widetilde{U_{a}}$ and the attacker’s expected
utility must be both weakly greater and weakly less than zero. Second, for
every other vulnerability $v$ that is not exploited, the same variable
$\widetilde{U_{a}}$ must be weakly greater than the expected utility of
attacking $v$; i.e., there must not be any other vulnerability with a strictly
greater expected utility, given the strategy of the defender. The constant $Z$
is an arbitrary large value; its presence allows us to upper bound the
difference between $\widetilde{U_{a}}$ and expected utility for $v^{*}$ only,
while removing the upper bound for the other vulnerabilities.

Constraint (13) serves a similar role for the defender’s expected utility: The
variable $\widetilde{U_{d}}$ is required to be weakly less than the defender’s
expected utility given its mixed strategy $\widetilde{p}$ and the
vulnerability chosen for attack. Since $\widetilde{U_{d}}$ is the maximization
objective, there is no need for a lower bound to force equality.

##  4\. Estimating Parameters of Our Utility Model

Our utility model has a number of free parameters that we need to specify: the
set $V$ of vulnerabilities, the set $S$ of schedules, the probabilities
$p(s,v)$ of detection, the costs $c_{a}$ and $c_{d}$, the rewards $r_{a}$ and
$r_{d}$, and the tradeoffs $\gamma_{a}$ and $\gamma_{d}$ between rewards and
costs. For the purposes of evaluating the security game framework empirically,
we estimated these parameters using a malware dataset made available by
VirusTotal (VT) (VirusTotal, [n.d.]). The dataset provides over 30,000 live
malware samples, as well as results from associated scans with 86 antivirus
tools. Each individual scan contains information such as the tool version,
whether it flagged the file as malicious, and a label describing why the file
was flagged, the file type, tags, other submissions of the same file, and how
many tools flagged the file as malicious.

The “tags” section of the VT reports may include one or more CVE tags, which
are unique identifiers that differentiate software vulnerabilities. These tags
allow us to determine which CVEs are targeted among the files present in VT,
allowing us to map out the possible attacks that an attacker may attempt,
representing all of the attack targets. We let the set $V$ of vulnerabilities
be the set of all CVEs that are tagged on at least one file in the VT dataset.

The set of 86 antivirus tools used in the VT dataset is the set of underlying
tools available to the defender. We evaluate schedules with size limits
varying from $b=1$ to $b=4$ tools.

###  4.1. Impact and Difficulty

CVEs represent different classes of software vulnerabilities, and in our case,
different attack targets. We use this information to relate the
vulnerabilities to the National Vulnerability Database (NVD) (Database,
[n.d.]a). For each unique CVE number, NVD provides a detailed report
containing more information about the vulnerability. This information includes
two parameters for each CVE, which we use in our model: _impact score_ and
_exploitability score_.

The impact score represents the severity of the exploited vulnerability. NVD
calculates this score by numerically quantifying three factors; the degree to
which confidential information is made available to the attacker, the degree
to which the affected device or network can be modified by a successful
attack, and the degree to which access to the affected device or network is
interrupted/prevented (Database, [n.d.]b). The numbers are multiplied together
with a constant to give a rating out of 10, with higher numbers representing
more dangerous exploits. For each CVE $v$, we set the reward $r_{a}(v)$ that
the attacker receives in the case of a successful attack to be the impact
score of the CVE. We correspondingly set $r_{d}(v)=-r_{a}(v)$. However, our
final utility model is not be zero-sum, because the costs of the attacker and
the defender differ.

The exploitability score represents the difficulty of carrying out an attack
on the vulnerability. This score is calculated by numerically quantifying four
factors: how remotely the attack can be made, the conditions and knowledge
that must be present for the attack to be successful, the degree of privilege
that the attacker must have to be successful, and the degree of interaction
required by a user of the targeted system (Database, [n.d.]b). These numbers
are then multiplied together with a constant, which gives a rating out of 10,
with higher numbers representing vulnerabilities that are harder to exploit.
For each CVE, our model uses this number as the attacker’s cost $c_{a}(v)$ for
carrying out an attack on that vulnerability.

###  4.2. Detection Probabilities

To estimate the detection probability of a tool detecting each vulnerability,
we count the number of files in the VT dataset tagged with the vulnerability’s
CVE that the tool flags as malicious. We then divide that count by the number
of files tagged with the CVE on which the tool was run.333Not every tool was
run on every file. We do not require that the tool report the “correct”
vulnerability, because each tool typically reports an opaque, tool-specific
vulnerability code that often does not directly correspond to a CVE.

Estimating the detection rate for a schedule containing more than a single
tool is more complicated, because the detection probabilities for multiple
tools are, in general, not independent. This observation is consistent with
the findings of Zhu et al. (2020) who did a similar experiment using
clustering. The authors found that 16 of the tools in VT are highly related,
with one cluster of 6 tools having nearly identical labels for 98% of the
dataset.

We estimate the detection rates of schedules in a similar manner to how we
calculate the single tool detection rates. For a given schedule $s$ and
vulnerability $v$, we first find the set of all files tagged with the
vulnerability’s CVE on which _at least one_ of the schedule’s tools were run.
We then estimate the detection rate $p(s,v)$ as the number of files in this
set that were flagged as malicious by _any_ of the schedule’s tools, divided
by the total size of the set. This approach accounts empirically for the
dependence in tools’ detection rates, although it potentially underestimates a
schedule’s detection rate. This is because a file on which not every tool of
the schedule was run which was flagged as benign might have been flagged as
malicious by one of the omitted tools.

###  4.3. False Positives as Defender Costs

The cost $c_{d}(s)$ to the defender of running a schedule $s$ may incorporate
a number of factors such as runtime, memory requirements, and false positive
rates. For the purposes of our empirical evaluation, we assume that all
schedules have approximately the same resource requirements. Therefore, we
calculate $c_{d}(s)$ based solely on an estimate of the false positive rate.

False positives can pose a high potential cost. In VT, the majority of tools
the dataset returned false positives when tested on a benign set of obfuscated
files, with about 25% of tools tagging over 70% of benign files scanned as
malicious (Zhu et al., 2020). Some tools may have extremely high detection
rates not because they are good at finding malware, but because they are too
“trigger-happy,” or are overly sensitive when scanning for viruses (i.e., they
have a high false positive rate in addition to a high true positive rate).

To estimate the false positive rate for every tool, we used the dataset
provided by Zhu et al. (2020). To achieve that, we divided the number of times
that a tool gave a false positive by the number of times that a tool was run
on benign files. For schedules of sizes greater than one, we divide the number
of times that at least one tool in that schedule gave a false positive by the
number of files that include at least one tool from the schedule. This
calculation gives us an overall false positive rate for each schedule, which
we use as the schedule cost $c_{d}(s)$.

###  4.4. Reward-Cost Tradeoff

Since we parameterize our model using a variety of scores from NVD and
elsewhere, there is no clear method of comparing one unit of reward against
one unit of cost. For example, the attacker’s costs are given by the NVD
exploitability score and its rewards are given by the impact score. We have no
prior knowledge how an attacker may weight the relative importance of each
score. Instead, our model contains the parameters $\gamma_{a}$ and
$\gamma_{d}$, defined in Equations (5) and (6). These values represent the
trade-off between costs and rewards for the attacker and defender. A
relatively low value of $\gamma$ corresponds to a player who values a unit of
reward much more than a unit of cost. A high value is for a player who is
deeply concerned about costs. These parameters may be tuned to represent
different types of players. For example, if $\gamma_{a}=0$, then the
attacker’s utility does not account for costs, analogous to an attacker with
much more resources than needed for any attack. On the other hand,
$\gamma_{a}=10$ represents a very cost-cautious attacker. We present the
effects of changing $\gamma_{a}$ and $\gamma_{d}$ in Section 5.3.

###  4.5. Limitations

Our approach to estimating the parameters of our model has a few limitations:

  1. (1)

Limited CVE Availability: Although the VT dataset includes over 30,000 files
that span tens of platforms, only a fraction of these files (3,515) have
corresponding CVE tags, limiting us to those files.

  2. (2)

False Positives: The VT dataset does not include benign files, making it
impossible to estimate false positive rates. We thus estimated false positive
rates using a dataset provided by Zhu et al. (2020).

  3. (3)

Low Occurrence Rates: Some CVE samples occur very infrequently in the VT
dataset, which may lead to extreme estimates of detection probabilities close
to either 0 or 1. We mitigate this effect by adding _pseudocounts_ to the
underlying data; this leaves the estimates of detection probabilities for CVEs
with many occurrences largely unaffected, while normalizing the detection
probabilities of CVEs with low occurrence counts to be closer to uniform. We
give the probability of a schedule $s$ detecting an attack against
vulnerability $v$ as:

(14) $\displaystyle p(s\ \text{detects}\ v)$ $\displaystyle=\dfrac{\text{ \\#
files where $s$ detects $v$}+n}{\text{ \\# files with $s$ and $v$}+2n},$

where $n$ is a parameter determining the weight given by the prior to a
uniform distribution. We use $n=2$.

##  5\. Evaluation

We evaluate our model through the following research questions:

  * RQ1: How does our proposed method of randomization compare to the baseline strategies?

  * RQ2: Does changing the reward-cost tradeoff for the attacker ($\gamma_{a}$) or the defender ($\gamma_{d}$) change our results?

###  5.1. Experimental Setup

We conducted all our experiments on a system with 2 AMD EPYC 7351 2.4 GHz
16-core processors with 32 KB L1 data cache, 64 KB L1 instruction cache, 512
KB L2 cache and 8,192 KB L3 cache, 472 GB of RAM and running Ubuntu 18.04.4
LTS. We used IBM CPLEX 12.10 for solving the MILP.

Algorithm 1 Compute Deterministic Best Response

1:$\triangleright$ $BR_{a}(s)$:= attackers best response $\forall s\in S$

2:for $s\in S$ do

3: $BR_{a}(s)\leftarrow\operatornamewithlimits{argmax}\limits_{v\in
V}u_{a}(s,v)$

4:$s^{*}\leftarrow\operatornamewithlimits{argmax}\limits_{s\in
S}u_{d}(s,BR_{a}(s))$ $\triangleright$ defender best response

5:$v^{*}\leftarrow BR_{a}(s^{*})$ $\triangleright$ attacker best response to
$s^{*}$

6:return $u_{d}(s^{*},v^{*}),u_{a}(s^{*},v^{*})$ $\triangleright$ utilities
for players

To assess the effectiveness of optimally randomized malware detection, we
evaluate our method against a number of other strategies that the defender may
use:

  1. (1)

Uniform Randomization: Defender uniformly randomizes over all schedules in
$S$.

  2. (2)

Best Average Detection Rate: The defender always runs the schedule
$s^{\prime}$ with the best average detection rate.

(15) $\displaystyle s^{\prime}\in\operatornamewithlimits{argmax}\limits_{s\in
S}\frac{1}{|V|}\sum_{v\in V}p(s\ \text{detects}\ v)$

  3. (3)

Randomized Best Average Detection Rate: Extension of best average to uniformly
randomize over the $m$ strategies with highest average detection rates.

  4. (4)

Highest Expected Utility: The defender chooses a schedule $s^{\prime}$ with
the highest expected utility, calculated by taking the expectation of utility
over the likelihood of vulnerabilities being exploited.

(16) $\displaystyle s^{\prime}\in\operatornamewithlimits{argmax}\limits_{s\in
S}\sum_{v\in V}u_{d}(s,v)\cdot p(v),$

where the probability of each CVE is given by its occurrence frequency in the
VirusTotal database.

  5. (5)

Randomized Highest Expected Utility: As with best average detection rate, we
extend the highest expected utility strategy to allow for uniform
randomization over the $m$ strategies with the highest values of Equation
(16).

  6. (6)

Deterministic Best Response: The defender best responds to the attacker by
only choosing a single schedule $s^{*}$. Unlike the above strategies,
deterministic best response takes into consideration the actions of the
attacker. Algorithm 1 gives the procedure for finding $s^{*}$, the attacker’s
best response $v^{*}$ to $s^{*}$, and the utilities for each player. This
baseline is a restricted case of our proposed strategy (Section 3.2), where
the defender assigns probability 1 to $s^{*}$ and 0 to all other schedules.

###  5.2. Comparison to Baselines (RQ1)

Figure 1. Comparing our proposed randomized best response strategy (r_br) to
various baseline strategies. Reward-cost tradeoffs are set to $\gamma_{a}$ = 1
and $\gamma_{d}=2$ for the attacker and the defender, respectively. Utilities
closer to 0 indicate better performance. Our proposed method of optimal
randomization r_br outperforms all baselines.

We evaluate the following strategies: best average detection rate (ba),
randomized best average detection rate where $m$ = 10 (u10), uniform
randomization (uall), highest expected utility (e1), randomized highest
expected utility where $m$ = 10 (e10), deterministic best response (d_br), and
our proposed randomized best response (r_br). In all cases, the defender has a
negative expected utility because the defender cannot “win” this game, they
only seek to minimize their losses. A perfect strategy in a world without
costs, detects all attacks with no false positives, and gives the defender a
utility of 0. Therefore, the closer to 0 that a strategy’s utility is, the
better it performs.

Figure 1 shows the main results of the comparison. The $x$-axis is the the
defender budget $b$. The $y$-axis represents the expected utility of the
defender for each strategy. Regardless of the budget, randomized best response
(r_br) outperforms all other strategies. The difference between randomized
best response and deterministic best response (d_br) shows the benefit that
the defender realizes through randomization. This is because a deterministic
best response is more easily exploited by the attacker than a randomized best
response. For the remaining strategies, the defender does not take into
consideration the actions of the attacker and thus generally earns a much
lower utility.

For budgets $b\in\\{1,2,3,4\\}$, Table 1 shows the deterministic best response
and the associated expected utility, while Table 2 shows the full randomized
best response and expected utility. If the defender chooses a randomized best
response, the expected utility for a budget of 3 (-2.269) is only a marginal
improvement over the utility for a budget of 2 (-2.270). A budget of 4 yields
no additional utility over 3, implying that increasing the budget beyond 2
yields diminishing results for the defender. In other words, given the optimal
randomization that our approach computes, the defender achieves the same
coverage using fewer tools.

RQ1: Randomizing and considering the actions of attackers increase defender
utility. For all schedule sizes, our model (r_br) outperforms all baselines.

Table 1. Deterministic best response: schedules and probabilities ($\gamma_{a}=1$, $\gamma_{d}=2$). For each budget, we show the defender utility and the chosen schedule. Since this strategy chooses one schedule, the probability for each chosen schedule is 1. Budget | Utility |  Schedule
---|---|---
1 | -3.528 |  F-Secure
2 | -2.601 |  TheHacker, ZoneAlarm
3 | -2.599 |  DrWeb, Kaspersky, TheHacker
4 | -2.591 |  Antiy AVL, ESET NOD32, NANO Antivirus, TheHacker

###  5.3. Does Varying $\gamma_{a}$ and $\gamma_{d}$ Affect Results? (RQ2)

Next we consider whether changes in the attacker’s and defender’s cost-reward
trade-offs ($\gamma_{a}$ and $\gamma_{d}$, respectively) affects our results.
By varying $\gamma_{d}$ in Equation (5), we vary the importance of detection
cost to the defender, which in our model is the false positives rate. Varying
$\gamma_{a}$ in Equation (6) controls the relation between impact and
exploitability for the attacker.

Since these parameters cannot be estimated from data, we empirically study the
effect of varying them on r_br. To achieve that, we consider two scenarios:
first we hold $\gamma_{d}$ constant and vary $\gamma_{a}$, then we hold
$\gamma_{a}$ constant and vary $\gamma_{d}$.

In the first experiment, we set $\gamma_{d}$ to be 2 and vary $\gamma_{a}$ to
be a value of $\\{0,0.25,0.5,0.75,1,2\\}$. We chose non-negative values for
$\gamma_{a}$ because values less than 0 do not make sense in our model, as
this would give the attacker a bonus for choosing a more costly attack. We
upper-bounded $\gamma_{a}$ at 2; values higher than 2 leave the attacker with
a negative utility, because the costs outweigh the benefits of attacking. An
attacker with a negative utility for any given attack would certainly choose
not to attack, thus preventing this game from ever taking place.

For each setting of $\gamma_{a}$, we compute the optimal strategy r_br and all
the baselines. The first row of Figure 2 shows the results for the defender’s
utility in each case. Each subplot shows one setting of $\gamma_{a}$. Our
results show that varying $\gamma_{a}$ does not change the fact the r_br is
optimal in every case and still outperforms all baselines.

In the second experiment, we vary $\gamma_{d}$ using a set of reasonable
values: $\\{0,1,2,5,8,10\\}$. We restrict our attention to non-negative values
for $\gamma_{d}$, because a negative value incentivizes the defender to choose
schedules with a high false positive rate. We chose 10 as an upper bound for
$\gamma_{d}$ because that threshold implies that the maximum penalty for
failing to detect an attack (a 10 in the NVD impact score) is equal to the
maximum cost the defender may incur, which occurs when the false positive rate
is $1.0$. The second row of Figure 2 shows the utility of r_br and all
baselines under different settings of $\gamma_{d}$. Similar to our first
experiment, changing $\gamma_{d}$ does not affect the optimality of r_br,
which still outperforms all baselines. Moreover, the results show that
increasing $\gamma_{d}$ greatly diminishes the performance of many of the
baselines. This is because a large $\gamma_{d}$ heavily penalizes schedules
with a high false positive rate. Thus, strategies that do not take false
positives into account (e.g., ba, u10, and uall) perform very poorly for high
values of $\gamma_{d}$, whereas strategies that do take this cost into account
(d_br and r_br) are much less affected.

RQ2: Varying $\gamma_{d}$ and $\gamma_{a}$ does not qualitatively affect our
conclusion that r_br is optimal compared to all other strategies for all
considered settings of these parameters.

Table 2. Randomized best response: schedules and probabilities ($\gamma_{a}=1$, $\gamma_{d}=2$). For each budget, we show the defender utility, chosen schedules, and respective probability for choosing each schedule. Budget | Utility |  Schedule | Probability
---|---|---|---
1 | -2.341 |  Avira | 0.185
ClamAV | 0.024
ESET NOD32 | 0.029
F-Secure | 0.019
TrendMicro | 0.119
ZoneAlarm | 0.625
2 | -2.270 |  ClamAV, F-Prot | 0.237
DrWeb, Kaspersky | 0.322
Kaspersky, TACHYON | 0.119
TheHacker, ZoneAlarm | 0.322
3 | -2.269 |  Avast-Mobile, ClamAV, F-Prot | 0.237
DrWeb, Kaspersky, TheHacker | 0.203
DrWeb, Kaspersky, TotalDefense | 0.441
Kaspersky, SUPERAntiSpyware, TheHacker | 0.119
4 | -2.269 |  Avast-Mobile, ClamAV, F-Prot | 0.237
DrWeb, Kaspersky, TheHacker, TotalDefense | 0.763

(a) $\gamma_{d}=2$, varying $\gamma_{a}$

(b) $\gamma_{a}=1$, varying $\gamma_{d}$

Figure 2. Expected utility of the defender with varying $\gamma_{d}$ and
varying $\gamma_{a}$. On the first row, we fix $\gamma_{d}=2$ and vary
$\gamma_{a}$. On the second row, we fix $\gamma_{a}=1$ and vary $\gamma_{a}$.
We compare our proposed randomized best response (r_br) to deterministic best
response (d_br) and other baselines, described in Section 1. Utilities closer
to zero indicate better performance. In all cases r_br outperforms all
baselines.

###  5.4. Resource Use

Table 3. The runtime of all the stages in our pipeline (in seconds). Load
parameters is the time needed to load model parameters from VirusTotal and
generate utility matrices for the defender and attacker. Generate MILP is the
time needed to write the MILP to a file. Read MILP is the time to read the
MILP into CPLEX. CPLEX Presolve and Probe are CPLEX optimization stages that
reduce the size of the MILP before solving. Solve is the wall time to solve
the MILP.

Budget | Load Parameters | Generate MILP | CPLEX Read MILP | CPLEX Presolve | CPLEX Probe | CPLEX Solve
---|---|---|---|---|---|---
1 | 0.397 $\pm$ 0.021 | 0.055$\pm$ 0.003 | 0.010 $\pm$ 0.000 | 0.035 $\pm$ 0.009 | 0.006 $\pm$ 0.009 | 0.207 $\pm$ 0.110
2 | 0.408 $\pm$ 0.019 | 1.759 $\pm$ 0.118 | 0.245 $\pm$ 0.016 | 1.306 $\pm$ 0.290 | 0.093 $\pm$ 0.025 | 3.447 $\pm$ 1.349
3 | 0.916 $\pm$ 0.033 | 36.934 $\pm$ 4.855 | 5.562 $\pm$ 0.921 | 32.118 $\pm$ 8.573 | 0.217 $\pm$ 0.064 | 66.400 $\pm$ 32.553
4 | 14.313 $\pm$ 0.691 | 523.592 $\pm$ 91.450 | 84.752 $\pm$ 20.274 | 457.395 $\pm$ 135.952 | 1.249 $\pm$ 0.384 | 873.180 $\pm$ 391.370

To evaluate the performance of our proposed r_br strategy, we have measured
its runtime as well its memory consumption. Computing optimal strategies uses
the following pipeline:

  1. (1)

Load Parameters: Load model parameters from VirusTotal dataset and generate
utility matrices $u_{d}$ and $u_{a}$.

  2. (2)

Generate MILP: Generate and write the MILP to a file.

  3. (3)

CPLEX Read: CPLEX reads the MILP.

  4. (4)

CPLEX Presolve/CPLEX Probing: CPLEX applies optimizations which reduce the
size and complexity of the MILP.

  5. (5)

CPLEX Solve: CPLEX solves the reduced-size MILP and outputs a solution.

Averaged over 12 runs per budget, Table 3 gives the runtime results for each
of the following stages in our pipeline. The number of schedules is
exponential in the size of the budget; a budget of $b=1$ has 86 possible
schedules, $b=2$ has 3,741, $b=3$ has 106,081 and $b=4$ has 2,229,636. As a
result, the runtime of each stage in determining optimal randomization also
increases exponentially as tool budget increases. Determining optimal
randomization for $b\in\\{1,2,3\\}$ can be computed efficiently, in a matter
of seconds or minutes, but $b=4$ requires roughly ~0.5 hours to compute.

We further show the runtimes for computing baseline strategies in Table 4
Since the baseline strategies do not require an MILP to solve them, they are
computed in fractions of a second, compared to solving for r_br, which takes
minutes. Therefore, across all budgets, calculating the baseline strategies is
179–889$\times$ faster than calculating the strategy in our proposed model.

While the baseline have a much faster runtime for computing optimal
strategies, this does not make our model prohibitively expensive to implement.
Once the optimal randomization r_br is computed, sampling from the
distribution at runtime (e.g., when a file must be scanned) can be done in
constant time. If enough files are scanned, the amortized runtime will be
comparable to the baselines.

Table 4. Runtime to solve games for baseline strategies, averaged over 12 runs. Baselines share parameter loading, which has a runtime of $0.3967\pm 0.0205$ for budget 1, $0.4079\pm 0.0191$ for budget 2, $0.9158\pm 0.0334$ for budget 3 and $14.3128\pm 0.6912$ for budget 4. We detail the baseline strategy abbreviations in Section 1. Baseline Strategy | Budget | Solve Time (s)
---|---|---
ba | 1 | 0.00024 $\pm$ 0.00003
2 | 0.00121 $\pm$ 0.00031
3 | 0.03064 $\pm$ 0.00588
| 4 | 0.69511 $\pm$ 0.09305
u10 | 1 | 0.0003 $\pm$ 0.00002
2 | 0.00093 $\pm$ 0.00002
3 | 0.02670 $\pm$ 0.00034
| 4 | 0.65883 $\pm$ 0.07263
uall | 1 | 0.00017 $\pm$ 0.00002
2 | 0.00116 $\pm$ 0.00004
3 | 0.02723 $\pm$ 0.00185
| 4 | 0.62969 $\pm$0.13856
e1 | 1 | 0.00066 $\pm$ 0.00023
2 | 0.00225 $\pm$ 0.00055
3 | 0.04842 $\pm$ 0.00077
| 4 | 1.12192 $\pm$ 0.13744
e10 | 1 | 0.00037 $\pm$ 0.00002
2 | 0.00165 $\pm$ 0.00007
3 | 0.04780 $\pm$ 0.00122
| 4 | 1.12371 $\pm$ 0.12602
d_br | 1 | 0.00012 $\pm$ 0.00002
2 | 0.00120 $\pm$ 0.00048
3 | 0.03026 $\pm$ 0.00408
| 4 | 0.71663 $\pm$ 0.12118

To evaluate the memory cost of generating and solving these models, we
measured the peak RAM usage for each budget size, for both the generation and
solving of the MILP. For MILP generation, budgets 1, 2, 3, and 4 used an
average of 147,244 $\pm$ 132 kb , 171,827 $\pm$ 254 kb, 1,455,271 $\pm$ 92 kb
and 28,664,755 $\pm$ 170 kb respectively. For MILP solving, budgets 1, 2, 3
and 4 used an average of 45,612 $\pm$ 136 kb, 572,383 $\pm$ 659 kb, 7,490,626
$\pm$ 50,617 kb and 95,986,773 $\pm$ 20,583 kb respectively. We recorded these
numbers using the time Linux command to record the peak RAM usage of each
budget three times for both generating and solving each MILP. Due to the low
variance for all of these values, we determined that four runs are sufficient
for obtaining precise measurements.

Due to the number of schedules our MILP compares, it faces a high memory cost
when computing the optimal distribution. Fortunately, this high cost is only
required once, as once an optimal distribution is calculated, sampling from it
is trivial.

##  6\. Related Work

The work related to this paper is from three domains; security games, game
theory for cybersecurity, and malware detection.

###  6.1. Security Games

Over the last decade, Stackelberg security games have been applied to a wide
variety of security domains. Sinha et al. (2018) provide an excellent overview
of the field. In this section, we highlight two particularly relevant works.

Our work is inspired by the work of Jain et al. (2010), which employs the use
of Stackelberg security games to assign security resources in the LAX airport.
Their work innovates by considering the different values for defense targets.
While our work incorporates many ideas from their paper, we also present
several improvements to their model. The first, and most important difference
is that they apply their model for security in a traditional, physical
setting, whereas our approach is for a more abstract defense. Attacks in the
domain of malware detection are much lower risk for an attacker to make
compared to terror attacks carried out in-person. Therefore, our domain,
naturally, has a higher ratio of attackers to defenders. Additionally, while
their model considers the several factors when judging the value of attacking
certain targets, it does not consider the difficulty of carrying out an attack
on the target, which our model incorporates.

To model the assignment of transit police patrol scheduling, Yin et al. (2012)
applied security problems on the domain of graph patrolling. Like our own
work, but unlike the work of Jain et al. (2010) which considers terrorist
attacks, Yin et al. model a domain in which attacks are relatively low-cost,
and thus may frequently succeed. Since attackers are commuters with routines,
they plausibly will only change their decision of whether or not to buy a
ticket, whereas attackers in our model may always change the type of their
attack.

###  6.2. Game Theory for Cybersecurity

Game theory and security games have historically been used to optimize
cybersecurity defenses. In our discussion, we will focus more on the
application of game theory to digital defenses than how to more effectively
detect new malware.

Zaffarano et al. (2015) present a system for designing metrics for modeling
non-static software defense. Our work expands on their model by adding costs
for attackers and defenders, making the game non-zero sum. This change allows
our model to avoid computing sub-optimal strategies as a result of ignoring
these costs.

Chung et al. (2016) criticize the use of game theoretic approaches to malware
detection, including vulnerability to novel attacks, and a lack of a true
measure of costs and rewards. The authors present a game theoretic approach
for automated responses to network breaches, allowing systems to defend
themselves without the need for human administrator action. Their approach
specializes in domains where knowledge of attacks and their payoffs is
limited, which is not the case in our work.

Wang et al. (2014) present a many-player game theoretic approach to security
in mobile ad-hoc networks (MANETs). Their model allows normal users in MANETs
to make distributed security defense decisions, allowing the MANET to be more
resilient to being compromised, while also minimizing the resources required
to do so. Their work uses system resource constraints as a budget, which is
similar to our use of budgets as a constraining factor.

Game theory has also been employed in “honeypotting,” where vulnerable “bait”
systems are distributed to hide real ones, to waste attacker time, warn
against incoming attacks, and understand new vulnerability exploits. Píbil et
al. (2012) uses game theory to optimally decide how vulnerable to make the
bait systems, as well as how many to use, to maximize their effectiveness.
Their later work (Kiekintveld et al., 2015) considers attackers who use probes
to detect if a system is real, and uses attack graphs to better model an
attacker’s knowledge of a system. Attack probes explain why attackers can be
best responding (by having perfect information) in our model, as an attacker
is able to repeatedly probe our defenses to see which attacks are more likely
to succeed.

###  6.3. Malware Detection

In the vein of malware detection, Zhu et al. (2020) provide insights about the
VirusTotal (VirusTotal, [n.d.]) dataset. The authors suggest that tool
dependencies have a high bearing on the results that tools give, and that the
top tools may be clustered into closely related sets.

Zolotukhin and Hämäläinen (2013) argue that signature-based malware detection
and classification is flawed, because it requires systems to be compromised
before new signatures can be detected. Their alternative to this approach is
to first analyze the bytecode of known malicious samples and look for patterns
that are later used to detect new malware exhibiting similar behavior but
possibly carrying a different signature. Their work studies how to find novel
forms of malware, whereas our work focuses on effectively using existing tools
to detect malware.

Much other research in malware detection has explored using machine learning
techniques. These solutions seek optimal use of limited defensive resources,
and are thus a complementary approach to ours. For example, to prioritize
attacks that pose larger threats to an enterprise, Oprea et al. (2018) use
supervised learning to analyze security logs. Sharif et al. (2018) use neural
networks to predict the likelihood of a user encountering malicious web
domains and take preventative measures. Stefanova and Ramachandran (2018) use
reinforcement learning to detect and respond optimally to network attacks.
Xiao et al. (2017) studies the problem of balancing the high computing cost of
scanning mobile devices for malware, with the low computing and battery power
associated with the devices. They use cloud computing to analyze a
documentation of the system state. They present two malware detection
strategies; Dyna-Q, which offers faster scans, and PDS, which offers higher
malware detection accuracy.

##  7\. Conclusion

There are a plethora of malware detection tools available, each with their own
strengths and weaknesses. To improve coverage, an organization may therefore
wish to use a suite of tools to defend against potential malware attacks,
which immediately raises the question of which subset to run. A subset that is
large enough to detect every attack would potentially require more computing
resources and incur more financial costs than feasible. However, attackers are
strategic. If the organization deterministically chooses any subset of tools
that leave some vulnerabilities open, then those vulnerabilities will be
preferentially attacked. The solution is to randomly select a subset of tools
to run. In this work, we have presented a novel approach for computing an
optimal randomization over feasible sets of malware detection tools that
incorporates the costs for both the attacker and the defender. Our empirical
evaluation shows that our best-responding randomization strategy outperforms
deterministic strategies, as well as naive randomization strategies.

The defender’s costs depend on some factors that are objective (e.g., false
positive rates for different tools on different attacks) and others that are
subjective (e.g., relative costs of different vulnerabilities’ being
exploited). For this work, we estimated objective factors from past studies
(Zhu et al., 2020) and the VirusTotal dataset, and chose values for subjective
factors about the severity of attacks using standard ratings in the National
Vulnerability Dataset. However, an advantage of our approach is that the
utility model can be customized to reflect the individual costs, preferences,
and available tools for each specific domain to which it is applied.

It is less straightforward to estimate the attacker’s utility than the
defender’s. A defender who wishes to take a conservative approach can assign a
utility to the attacker that is equal to the severity of each attack for the
defender. If partial information is known about the attacker’s utility, then
it can be incorporated into the model as well. Our approach does not require
full knowledge of the attacker’s utility; rather, it takes advantage of
whatever knowledge might be available to the defender.

The process of finding and exploiting vulnerabilities is fundamentally
strategic. To the best of our knowledge, our work is the first to explicitly
account for strategic attacker behavior while optimizing the tradeoff between
costs and benefits in the malware detection domain.

## References

  * (1)
  * Accenture (2021) Accenture. 2021\.  The Cost of Cybercrime.  https://www.accenture.com/_acnmedia/PDF-96/Accenture-2019-Cost-of-Cybercrime-Study-Final.pdf
  * Avenhaus et al. (2002) Rudolf Avenhaus, Bernhard von Stengel, and Shmuel Zamir. 2002\.  Chapter 51 Inspection games.  _Handbook of Game Theory with Economic Applications_ 3 (12 2002), 1947–1987.  https://doi.org/10.1016/S1574-0005(02)03014-X
  * Chung et al. (2016) K. Chung, C. A. Kamhoua, K. A. Kwiat, Z. T. Kalbarczyk, and R. K. Iyer. 2016\.  Game Theory with Learning for Cyber Security Monitoring. In _2016 IEEE 17th International Symposium on High Assurance Systems Engineering (HASE)_. 1–8.
  * Database ([n.d.]a) National Vulnerability Database. [n.d.]a.  https://nvd.nist.gov.
  * Database ([n.d.]b) National Vulnerability Database. [n.d.]b.  https://nvd.nist.gov/vuln-metrics/cvss/v3-calculator.
  * Jain et al. (2010) Manish Jain, Jason Tsai, James Pita, Christopher Kiekintveld, Shyamsunder Rathi, Milind Tambe, and Fernando Ordónez. 2010.  Software assistants for randomized patrol planning for the lax airport police and the federal air marshal service.  _Interfaces_ 40, 4 (2010), 267–290.
  * Kiekintveld et al. (2009) Christopher Kiekintveld, Manish Jain, Jason Tsai, James Pita, Fernando Ordóñez, and Milind Tambe. 2009.  Computing optimal randomized resource allocations for massive security games.  _AMAAS-2009 Conf_ 2, 689–696.  https://doi.org/10.1145/1558013.1558108
  * Kiekintveld et al. (2015) Christopher Kiekintveld, Viliam Lisý, and Radek Píbil. 2015\.  _Game-Theoretic Foundations for the Strategic Use of Honeypots in Network Security_.  Springer International Publishing, Cham, 81–101.  https://doi.org/10.1007/978-3-319-14039-1_5
  * Oprea et al. (2018) Alina Oprea, Zhou Li, Robin Norris, and Kevin D. Bowers. 2018\.  MADE: Security Analytics for Enterprise Threat Detection.  _Proceedings of the 34th Annual Computer Security Applications Conference_ (2018).
  * Píbil et al. (2012) Radek Píbil, Viliam Lisý, Christopher Kiekintveld, Branislav Bošanský, and Michal Pěchouček. 2012.  Game Theoretic Model of Strategic Honeypot Selection in Computer Networks. In _Decision and Game Theory for Security_ , Jens Grossklags and Jean Walrand (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 201–220.
  * Security (2020) IBM Security. 2020\.  Cost of a Data Breach Report.  https://www.capita.com/sites/g/files/nginej146/files/2020-08/Ponemon-Global-Cost-of-Data-Breach-Study-2020.pdf
  * Sharif et al. (2018) Mahmood Sharif, Junpei Urakawa, Nicolas Christin, Ayumu Kubota, and Akira Yamada. 2018.  Predicting Impending Exposure to Malicious Content from User Behavior.  _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security_ (2018).
  * Sinha et al. (2018) Arunesh Sinha, Fei Fang, Bo An, Christopher Kiekintveld, and Milind Tambe. 2018.  Stackelberg security games: Looking beyond a decade of success. In _Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence_.
  * Stefanova and Ramachandran (2018) Zheni Stefanova and Kandethody M. Ramachandran. 2018\.  Off-Policy Q-learning Technique for Intrusion Response in Network Security.  _World Academy of Science, Engineering and Technology, International Journal of Computer, Electrical, Automation, Control and Information Engineering_ 12 (2018), 225–231.
  * VirusTotal ([n.d.]) VirusTotal. [n.d.].  https://www.virustotal.com/gui/home/upload.
  * von Stackelberg et al. (2010) H. von Stackelberg, D. Bazin, R. Hill, and L. Urch. 2010\.  _Market Structure and Equilibrium_.  Springer Berlin Heidelberg.  https://books.google.ca/books?id=dghH9OH5fDoC
  * Von Stengel and Zamir (2004) Bernhard Von Stengel and Shmuel Zamir. 2004.  _Leadership with commitment to mixed strategies_.  Technical Report. Citeseer.
  * Wang et al. (2014) Y. Wang, F. R. Yu, H. Tang, and M. Huang. 2014\.  A Mean Field Game Theoretic Approach for Security Enhancements in Mobile Ad hoc Networks.  _IEEE Transactions on Wireless Communications_ 13, 3 (2014), 1616–1627.
  * Xiao et al. (2017) L. Xiao, Y. Li, X. Huang, and X. Du. 2017\.  Cloud-Based Malware Detection Game for Mobile Devices with Offloading.  _IEEE Transactions on Mobile Computing_ 16, 10 (2017), 2742–2750.
  * Yang et al. (2014) Rong Yang, Benjamin Ford, Milind Tambe, and Andrew Lemieux. 2014\.  Adaptive resource allocation for wildlife protection against illegal poachers. In _Proceedings of the 2014 International Conference on Autonomous Agents and Multi-Agent Systems_. 453–460.
  * Yin et al. (2012) Zhengyu Yin, Albert Xin Jiang, Milind Tambe, Christopher Kiekintveld, Kevin Leyton-Brown, Tuomas Sandholm, and John P. Sullivan. 2012\.  TRUSTS: Scheduling Randomized Patrols for Fare Inspection in Transit Systems Using Game Theory.  _AI Magazine_ 33, 4 (2012), 59–72.  http://www.aaai.org/ojs/index.php/aimagazine/article/view/2432
  * Zaffarano et al. (2015) Kara Zaffarano, Joshua Taylor, and Samuel Hamilton. 2015\.  A Quantitative Framework for Moving Target Defense Effectiveness Evaluation. In _Proceedings of the Second ACM Workshop on Moving Target Defense_ (Denver, Colorado, USA) _(MTD ’15)_. Association for Computing Machinery, New York, NY, USA, 3–10.  https://doi.org/10.1145/2808475.2808476
  * Zhu et al. (2020) Shuofei Zhu, Jianjun Shi, Limin Yang, Boqin Qin, Ziyi Zhang, Linhai Song, and Gang Wang. 2020.  Measuring and Modeling the Label Dynamics of Online Anti-Malware Engines. In _29th USENIX Security Symposium (USENIX Security 20)_. USENIX Association, Boston, MA.  https://www.usenix.org/conference/usenixsecurity20/presentation/zhu
  * Zolotukhin and Hämäläinen (2013) M. Zolotukhin and T. Hämäläinen. 2013.  Support vector machine integrated with game-theoretic approach and genetic algorithm for the detection and classification of malware. In _2013 IEEE Globecom Workshops (GC Wkshps)_. 211–216.