Anti-Malware Sandbox Games

Malicious programs, or malware (M) for short, are a threat to individuals, companies, and even military units and intelligence agencies. One approach to stopping malware is to scan suspected programs with an anti-malware (AM) program, which can check the suspected program against a list of known, bad programs. In response, malware resort to manipulating its own code dynamically during runtime to bypass static signature scanning. To counter this, AM programs execute suspected programs in a contained, simulated environment, called a sandbox, in an attempt to trick the malware into showing its true malicious activity. This allows the AM to check program behavior at run-time against a list of known bad behaviors. In response, malware now checks its environment to make an intelligent decision on whether to attack by unleashing its true malicious activity Bulazel and Yener (2017). This raises the question, what is the optimal way for AM to protect machines defended by it, from malware developers who will study its behavior?

The tools of game theory are well suited to analyze the strategic interaction between malware developers (M) and anti-malware developers (AM) in our setting of sandboxing, where AM’s strategies involve the use of sandbox environments to dynamically analyze malware. Despite the large literature and wide application of game theoretic analysis of problems in physical Tambe (2011) and cyber Roy et al. (2010); Singh et al. (2010); Do et al. (2017) security, sandboxing has not been analyzed from a game-theoretic perspective.

We use computational game-theoretic methods to develop strategies and guidelines to improve the state of the art in sandbox analysis. Unfortunately, existing literature on game theoretic analysis of malware do not model the sandboxing problem, because the dynamics of the game and utility functions we study in this paper are quite different from previous work. See Section 2 for more details. We address the following key research question:

How can we model sandboxing as a game and characterize and compute optimal strategies for the anti-malaware?

Bulazel et al. Bulazel and Yener (2017) did a recent survey of automated malware analysis and evasion. There is extensive literature cataloging the various ways to detect emulators, virtual machines, and debuggers Raffetseder et al. (2007); Branco et al. (2012). There is also extensive work in engineering solutions that approximate transparent introspection of programs Deng et al. (2013); Balzarotti et al. (2010).

Sinha et al. Sinha et al. (2015) discusses techniques developed to address the challenges of scale, uncertainty, and imperfect observation by the attacker in security games modeled as Stackelberg games, and applications to cybersecurity. Stackelberg games have also been used to model security games involving web applications Vadlamudi et al. (2016), network security Vaněk et al. (2012); Durkota et al. (2015), competition among multiple malwares Lee et al. (2015), and audit games Blocki et al. (2013, 2015).

Our model has a number of differences with previous work. First, the AM must commit to the same strategy on every machine of the same type. Unlike security games, when AM can commit to mixed strategies, there are an infinite number of pure strategies for even a naïve AM which uses the same strategy on every machine. Each pure strategy is represented by a vector with a component for each type of machine whose value correspond to the probability with which AM creates a sandbox of that type. This means that unfortunately, standard algorithms and techniques for solving security games do not apply to the sandbox game.

We are given a set $\mathcal{M}$ of all types of environments, where each $\@vec{m}\in\mathcal{M}$ is represented by a $k$-vector of features (i.e., emulated clock time, fingerprint, network connection, etc.) that fully and uniquely describes machines of type $\@vec{m}$. Every real machine presents some environment in $\mathcal{M}$ natively. Similarly, every sandbox generated by AM presents also presents an environment in $\mathcal{M}$. Table 1 summarizes the notation used throughout this paper.

Similarly, M is said to be naïve, if its probability of attack does not depend on the environment it perceives, i.e., for every pair of possible environment types $\@vec{m},\@vec{m}^{\prime}\in\mathcal{M}$, it holds that $\@vec{\rho}_{\@vec{m}}=\@vec{\rho}_{\@vec{m}^{\prime}}$. M is deterministic if M is restricted to strategies $\rho$, where for each $\@vec{m}\in\mathcal{M}$, $\@vec{\rho}_{\@vec{m}}\in\{0,1\}$, i.e., in each environment M can either only always attack or always hide. Otherwise, M is non-deterministic. M is sophisticated when its strategy space is all of $\mathrm{P}$.

We note that in our formulation, for AM and M, deterministic strategies and non-deterministic strategies are pure strategies. In other words, there are infinite pure strategies, each of which assigns a number between $0$ and $1$ to each machine type, and deterministic strategies simply mean that each component is either $0$ or $1$ but not in-between.

We first consider the case where AM defends all machines. In this case $\@vec{d}_{\@vec{m}}=\@vec{e}_{\@vec{m}}$ for all $\text{M}\in\mathcal{M}$. We will prove that Existence is the optimal strategy to generate sandboxes when AM defends all real machines when AM is naïve in Theorem 1. This involves randomly generating sandboxes according to the distribution $\@vec{e}$, i.e., for each real machine $\@vec{r}\in R$, and possible environment $\@vec{m}\in\mathcal{M}$, $\@vec{\pi}^{\@vec{r}}_{\@vec{m}}=\@vec{e}_{\@vec{m}}$. When AM can commit to a sophisticated strategy, the solution is even more simple and intuitive: deterministically create a sandbox of the same type as the real machine being defended. In equilibrium, AM is guaranteed a utility of $0.75$, as we prove in Theorem 2.

Note that in the special case where M is naïve, AM’s optimal strategy is any strategy that always creates a sandbox on any real machine. This is because a naïve M cannot distinguish between different types of machines and the game degenerates into a single-type model. The example below shows different cases where AM and a non-naïve M are restricted on different strategy spaces.

Theorems 1 and 2 follow from the observation that (1) when AM defends all machines, we are faced with a zero-sum game, and (2) identifying an equilibrium under which AM achieves the highest possible utility under any equilibrium.

In this section, we consider the case where AM defends at most half the real machines, there is an AM-optimal strategy where every machine that AM defends is protected in equilibrium, and Undefended is one such strategy.

In this paragraph we provide a method to compute M’s best response given a fixed AM strategy. This will be the basis of our QCQP framework. Before we proceed further, we rewrite the utility functions of AM and M in vector notation for convenience:

where $\odot$ is the component-wise multiplication operator between two vectors, and $\Pi$ is the matrix of AM’s strategies, whose $\@vec{r}$-th row-vector is $\@vec{\pi}^{\@vec{r}}$. For a fixed AM strategy $\pi$, we can solve for M’s best response $\rho^{*}$ using the Lagrange multipliers for the optimization problem $\max_{\@vec{\rho}}u_{M}(\@vec{\pi},\@vec{\rho})$ which are: $\forall\@vec{m}\in\mathcal{M},L_{\@vec{m}}=\frac{\partial u_{\text{M}}(\@vec{\pi},\@vec{\rho})}{\partial\@vec{\rho}_{\@vec{m}}}=\@vec{e}_{\@vec{m}}-2\@vec{d}_{\@vec{m}}\@vec{\pi}_{\@vec{m}}\@vec{\rho}_{\@vec{m}}-\allowbreak\sum_{\@vec{l}\in\mathcal{M}\setminus\{\@vec{m}\}}(\@vec{d}_{\@vec{m}}\@vec{\pi}_{\@vec{l}}+\@vec{d}_{\@vec{l}}\@vec{\pi}_{\@vec{m}})\@vec{\rho}_{l}$.

Computing $\@vec{\rho}^{*}$ involves computing the solutions to the following $3^{|\mathcal{M}|}-1$ systems of linear equations, and picking the solution that is feasible and maximizes M’s utility. Each system of linear equations is indexed by an $|\mathcal{M}|$-vector $\@vec{c}\in\{0,1,b\}^{|\mathcal{M}|}$ (except $\@vec{c}=\@vec{0}$), where $b$ means “between $0$ and $1$”, and is constructed by adding the $|\mathcal{M}|$ equations as follows: (i) $\@vec{\rho}_{\@vec{m}}=0$if $\@vec{c}_{\@vec{m}}=0$, (ii) $\@vec{\rho}_{\@vec{m}}=1$, if $\@vec{c}_{\@vec{m}}=1$, or (iii) $L_{\@vec{m}}=0$if $\@vec{c}_{\@vec{m}}=[0,1]$.

We now shift our focus to settings where $D>\frac{1}{2}$. Algorithm 1 provides a general quadratically constrained quadratic program (QCQP) formulation of the problem of computing AM-optimal SPNEs. We simultaneously solve for AM’s strategy $\pi^{*}$ and M’s strategy $\rho^{*}$ by setting $u_{\text{AM}}$ to be the objective, under the constraint that $\rho^{*}$ is the best response to the output strategy for AM $\pi^{*}$.

Algorithm 1 involves (1) enumerating M’s possible responses represented by the possible values that $\@vec{c}$ (line 7-10) can take on. For each $\@vec{c}$, the algorithm solves the QCQP problem to compute an optimal AM strategy $\@vec{\pi}$ in equilibrium and the corresponding best response strategy $\@vec{\rho}$ of M strategy (line 12), under the constraints $\@vec{c}$. Notice that here, $\@vec{\pi}$ is an optimal AM strategy in equilibrium when M is constrained by $\@vec{c}$. In line 13, the algorithm tests constraint violations and discards the solution if some constraints are violated. This test is necessary because of limitations of current QCQP solvers. In lines 14-16, we fix the AM strategy to be $\@vec{\pi}$, and compute $\@vec{\rho}^{\prime}$ which is M’s best response to $\@vec{\pi}$ without any constraints on M, using the technique described in Section 6, and test if $u_{\text{M}}(\@vec{\pi},\@vec{\rho})\geq u_{\text{M}}(\@vec{\pi},\@vec{\rho}^{\prime})$. If the inequality holds, the constrained best response $\@vec{\rho}$ is also M’s global best response, and $(\@vec{\pi},\@vec{\rho})$ is an equilibrium, and added to $S$. If the inequality does not hold, the algorithm discards the solution. Finally, the algorithm chooses the equilibrium with the highest AM utility from $S$.

When AM is installed only on machines of a single type, we can solve for AM’s optimal strategy efficiently as follows. The algorithm follows from the observation that $u_{\text{AM}}$ becomes a linear function in $\@vec{\pi}$, with no critical points in the interval $[0,1]$. Thus we pick the solution which maximizes AM’s utility from solving the $3^{|\mathcal{M}|}-1$ sets of equations for every combination of setting $\@vec{\pi}_{\@vec{m}}$’s to either $0$ or $1$ and the corresponding Lagrangian first order conditions on M’s strategy.

Based on Theorems 1, 2 and 3, we refer to a setting as easy, if either AM defends all machines, or it defends at most half of all machines. In these cases, we have analytical solutions to AM optimal SPNE. We refer to other settings as hard, and solve them using our QCQP-based Algorithm 1.

Here, we summarize our findings and provide guidelines for sandboxing AMs. Specifically, we answer the following questions through experiments: Are there natural and easy to compute strategies for AM, assuming M best responds, without compromising utility when compared to the optimal strategy? We consider some natural strategies which are summarized in Table 2.

For hard settings, the QCQP SPNE computed using Algorithm 1 and the Existence strategy yield AM utility close to that of the BruteForce SPNE on average. Defended also performs consistently well in practice, yielding AM utility close to both QCQP and Existence strategies on average.

We provided the first game theoretic analysis of the sandbox game and the first theoretical results and practical algorithms for sandboxing. Specifically, our results provide concrete guidelines for deploying sandboxing AMs, allowing an AM developer to compute AM-optimal strategies under several natural restrictions on the strategy space of AM and M which correspond to different practical considerations in the deployment of AM and M. When AM either defends every machine or defends fewer than half of all real machines, we identify natural and easy to compute strategies that are optimal for AM in equilibrium. The problem of computing an optimal AM strategy becomes harder when AM defends more than half of the real machines but not all of them. Our QCQP algorithm compute an optimal AM strategy but is computationally expensive. However, as we show empirically, the natural and easy to compute Existence strategy achieves AM utility that is close to optimal in practice.

There are several exciting avenues for future work: selecting AM strategies that are robust to M’s selection of strategies in response to AM, and modeling the resource constraints as AM’s ability to generate sandboxes, or M’s inability to perfectly observe AM. Indeed, AM and M may often have different levels of information about a given deployment or constraints on the computational resources at their disposal. For example, commercially distributed AM may not be aware of the exact distribution of real machines where it may be deployed, and therefore be forced to commit to a naïve strategy. While our results already identify some natural and easy to compute AM-optimal solutions, fully exploring the impact of different constraints of information and computational resources on AM and M, and how to compute effective strategies for AM are an interesting question for future work.