Don't Bury your Head in Warnings: A Game-Theoretic Approach for Intelligent Allocation of Cyber-security Alerts

1 Introduction

Automated intrusion detection and prevention systems (IDPS) and security information and event management tools (SIEM) are important for computer network security. The alerts generated by these systems must be investigated by human cybersecurity analysts to assess whether they were generated by malicious activity, and if so, how to respond. Unfortunately, these automated systems are notorious for generating high rates of false positives [Spathoulas and Katsikas, 2013]. Expert analysts are in short supply, so organizations face a key challenge in managing the enormous volume of alerts they receive using the limited time of analysts. Failing to solve this problem can render the entire system insecure, e.g., in the 2013 attack on Target, IDPS raised alarms, but they were missed in the deluge of alerts [Riley et al., 2014].

There are many approaches for mitigating this problem by reducing the number of alerts. IDPS can be carefully configured, alert thresholds can be tuned, and the classification methods underlying the detections can be improved [Sommer and Paxson, 2010; Barbara and Jajodia, 2002; Laszka et al., 2016]. Other techniques include aggregating alerts [Zimmerman, 2014], and visualizing alerts for faster analysis [Patton et al., 2011]. Even when using all of these techniques, there are still too many alerts for the analysts to investigate all of them in depth. Our work focuses on the remaining problem of assigning limited analysts to investigate alerts after automated pre-processing methods have been applied.

The typical approach to managing alerts is either ad-hoc or first investigates alerts with the highest priority (e.g., risk). However, this fails to account for the adversarial nature of the cyber security setting. An attacker who can learn about a predictable alert management policy can exploit this knowledge to launch a successful attack. For example, if we had a policy that only inspects alerts from high valued assets from our network, an attacker who can learn this evades detection indefinitely by only attacking lower valued assets.

To address this shortcoming of the previous method, our first contribution is a Cyber-alert Allocation Game (CAG), a game-theoretic model for optimizing the assignment of cyber alerts to a limited group of cyber analysts. Using game theory allows us to explicitly model the strategies an attacker could take to avoid detection. By following a randomized, unpredictable assignment strategy the defender can improve the effectiveness of alert assignments against strategic attackers. Our model considers the characteristics of the alerts (e.g., criticality of origin system), as well as the capabilities of the analysts in formulating the optimal policy for the defender.

Our second contribution in this paper is to show that finding the optimal strategy for a CAG is NP-hard, posing a major computational challenge. Third, we present an algorithm for finding optimal, implementable CAG policies. Fourth, we devise novel heuristics to solve large CAGs, and we provide empirical evaluation of our algorithms and model.

2 RelatedWork

There is a large body of work on automated detection of cyber attacks using machine learning (e.g., [Hu et al., 2003; Hofmeyr and Forrest, 1999; Wu et al., 2015]). However, these methods have significant detection error and suffer from generating too many alerts [Sommer and Paxson, 2010]. In modern security operations a team of human cyber analysts work to investigate the alerts generated by automated detectors [DAmico and Whitley, 2008]. A recent line of work [Ganesan et al., 2016] has used decision theory to optimize the scheduling of cyber-security analysts for screening over multiple time periods, but this approach does not consider the response of a strategic attacker.

Our approach draws on the principles and modeling techniques of a large body of work that applies game theory to security problems [Tambe, 2011]. The existing work on security games focuses heavily on applications to physical security (e.g., patrolling), with some exceptions (e.g., [Laszka et al., 2016; Durkota et al., 2015]). However, CAG significantly differs from traditional security games [Tambe, 2011; Jain et al., 2010b] due to the absence of an explicit set of targets, a large number of benign alerts and varying time requirements for inspections. A model that is closely related to ours is the Threat Screening Game (TSG) introduced in [Brown et al., 2016] for screening passengers at airports. There are some crucial differences with the cybersecurity domain: (1) Screening in airports is a quick scan of a passenger; in CAGs, investigating a threat may take varying amounts of time leading to a different "non-implementability" [Korzhyk et al., 2010] issue for CAG as compared to TSG and other security games which require novel techniques to resolve, (2) CAG does not consider teams of resources, and (3) in CAGs attacks result in a probability distribution over a set of alerts.

3 Motivating Domain

While many organizations face the challenge of cyber alert allocation, we highlight a scenario developed in consultation with experts at the United States Air Force (USAF). The USAF relies on extensive global cyber systems to support its missions, which are monitored by IDPS to prevent attacks on the network by intelligent adversaries. The Air Force Cyber defense unit (AFCYBER) is responsible for investigating and resolving alerts generated by these IDPS [afc, 2017]. Due to the global scale of USAF computer systems, millions of alerts are generated every day, associated with different types of events. Prescreening of the alerts eliminates a large fraction of insignificant events, but thousands remain to be investigated. Any of these remaining alerts could indicate a malicious attack, but a large fraction are false positives.

Two primary features are used to prioritize the most critical alerts to investigate. First, each alert has a risk classification (e.g., high, medium, low) based on the type of event detected by the IDPS. Second, each alert has an origin location within the global network (e.g., a specific host, system); some locations (e.g., headquarters) are more critical to operations.

The AFCYBER has a limited number of Incident Response Team (IRT) cyber analysts who investigate significant alerts after prescreening [aft, 2016]. Each analyst has different areas of expertise, and may therefore be more effective and/or faster at investigating certain types of incidents. The USAF also must protect against an adaptive adversary who can observe strategies through beaconing and other techniques. The problem AFCYBER faces is an excellent example of our central analyst assignment problem in the real world.

4 Cyber-alert Allocation Games

We model the Cyber-alert Allocation Game (CAG) as a (zerosum) Stackelberg game played between the defender (e.g., AFCYBER) and an adversary (e.g., hacker). The defender commits to a mixed strategy to assign alerts to cyber analysts. We make the worst-case assumption that the attacker moves with complete knowledge of the defender's strategy and plays a best-response attack strategy [Kiekintveld et al., 2009]. However, in a zero-sum game the optimal strategy for the defender is the same as the Nash equilibrium (i.e., when the attacker moves simultaneously) [Yin et al., 2010], so the order of the moves is not consequential in the model.

Systems and Alerts: The defender responds to alerts originating from a set of systems k ∈ K. A "system" in our model could represent any level of abstraction, ranging from a specific server to a complete network.IDPS for each system generate alerts of different types, a ∈ A. The alert types correspond to levels of severity (e.g., high, medium, and low), reflecting the likelihood of a malicious event. We represent the combination of the alert type and the origin system as an alert category, c ∈ C, where c = (k, a). The alerts in a given category are not differentiable, so the defender must investigate all alerts within a category with the same probability. The total number of alerts for a given category c is denoted by Nc. We assume that the both the defender and attacker know the typical value of Nc from historical averages (similar to [Ganesan et al., 2016]).

Attack Methodologies: Attackers can choose from many attack methodologies. These fall into high-level categories such as denial of service attacks, malware, web exploitation, or social engineering. We represent these broad classes of attacks as attack methods m ∈ M. For every attack method there is a corresponding probability distribution βm a which represents the probability that the IDPS generates an alert of type a for an attack method m. For example, if the attacker chooses m = DoS the corresponding alert probabilities could be βDoS High = .8, βDoS Medium = .15 and βDoS Low = .05.

Cybersecurity Analysts: Cybersecurity analysts R are assigned to investigate alerts. The time required for an analyst to resolve an alert type a varies, and is represented by T r a . Intuitively, T r a represents the portion of a time period that an analyst needs to resolve an alert of type a. A time period may be a shift, an hour or other fixed scheduling period. For example, if an analyst needs half a time period to resolve a, then T r a = 0.5. In our model: T r a ≤ 1, ∀ a ∈ A, i.e., an analyst can address multiple alerts within a time period. In addition to T r a , we allow modeling of the effectiveness of an analyst against an attack method, representing her expertise, via a parameter Erm.

Defender Strategies: A pure strategy P for the defender is a non-negative matrix of integers of size |C| × |R|. Each c,r entry is the number of alerts in category c assigned to be investigated by cyber analyst r, denoted by Pc,r. The set of all pure strategies ˆ P is all allocations that satisfy the following constraints; Ca denotes all categories with the alert type a:

Inequality (1) ensures that each analyst is assigned a valid number of alerts, while inequality 2 ensures we do not assign more alerts than the total in a category.

Example CAG. Consider a CAG with two systems K = {k1, k2}, two alert levels A = {a1, a2}, and two analysts r = {r1, r2}. There are four alert categories C = {c1, c2, c3, c4}, where c1 = (k1, a1), c2 = (k1, a2), c3 = (k2, a1) and c4 = (k2, a2). For the alert categories we have Nc1 = 3, Nc2 = 2, Nc3 = 0, and Nc4 = 1. For r1, assume T r1 a1 = 1 and T r1 a2 = 0.5; For r2, assume T r2 a1 = 0.4 and T r2 a2 = 0.2. The analyst capacity constraint (Inequality (1)) for r1 is instantiated as follows (the other columns are similar):

For c1 the alert capacity constraint (Inequality (2)) we have (the other rows are similar):

An example of a pure strategy P is given in Figure 1(a). The dashed boxes in Figure 1(a) represent the set of variables in the analyst capacity constraints, i.e. constraints of type (1). We show an example marginal strategy in Figure 1(b). This drops constraint (3), but satisfies constraints (1) and (2).

We define a mixed strategy q over pure strategies P ∈ ˆ P (∑P ∈ ˆ P qP = 1, 0 ≤ qP ≤ 1). From the mixed strategy we can calculate the marginal (expected) number of alerts of category c assigned to each analyst r, denoted by nc,r = ∑P qPPc,r. The marginal allocation is denoted by n with component nc,r representing the expected number of alerts in category c assigned to analyst r. The adversary plays a best response to the defender's marginal strategy n which amounts to choosing a system k to attack and an attack method m.

Utilities Since the alerts in a category are indistinguishable they are all investigated with the same probability nc,r/Nc, which is the probability that an alert in category c is investigated by analyst r. The probability of detecting an attack of type m that results in an alert of type c is calculated as: xc,m = ∑r∈R Ermnc,r/Nc. The payoffs for the defender depend on the system k that is attacked, the attack method m, and if the adversary is detected (or undetected) during investigation. This is denoted by U d δ,c and U u δ,c , respectively, where c refers to the category (k, a) and δ is the defender. We formulate a CAG as a zero-sum game, hence the payoffs for the adversary (θ) are U d θ,c = -U d δ,c and U u θ,c = -U u δ,c . If the adversary chooses k, m, and given βm a , the defender's utility is:

5 Defender's Optimal Strategy

We start with a linear program, denoted as MixedStrategyLP, that computes the defender's optimal mixed strategy (as the maximin strategy):

This LP requires exponentially many pure strategies P ∈ ˆ P. The objective function in Equation 5 maximizes the defender's utility, v. Equation 6, which uses Equation (4), ensures the adversary selects a best response over all m ∈ M and k ∈ K. Equation 7 calculates the detection probabilities x from the marginal strategy n, which is computed by Equation 8. Equation 9 ensures the mixed strategy is valid.

Computing the maximin mixed strategy for the defender was shown to be NP-hard in the case of TSGs [Brown et al., 2016]. The computational hardness arises from the underlying team formation of applying a group of screening resources to screen incoming passengers. However, in CAGs we do not have teams of analysts, we only need to assign the alerts to individual analysts. Thus, one might hope that this could simplify the problem and admit a polynomial time algorithm. Unfortunately, this turns out not to be the case. Specifically, we show in Theorem 1 that the problem is still NP-hard, where the hardness arises from a different domain feature, i.e., the time values, T r a , for the analysts. All proofs can be found in the on-line appendix 1 .

Theorem 1. Computing the defender maximin strategy is weakly NP-hard when there is only one resource, and is strongly NP-hard with multiple resources.

In some special cases, it is possible to compute the optimal marginal strategy in polynomial time. Specifically, if all T r a for a given analyst r are identical ∀a ∈ A, then the optimal marginal strategy can be found with an LP which is stated in Proposition 1. This result is discussed further in Section 6.

Proposition 1. When T r ai = T r aj ∀ai, aj ∈ A for each resource, then there is a polynomial time algorithm for computing the maximin strategy.

5.1 Defender's Optimal Marginal Strategy

In the security games literature, two approaches are commonly used to handle scale-up: marginal strategies [Kiekintveld et al., 2009; Letchford and Conitzer, 2013] and column generation [Jain et al., 2010a]. We adopt a marginal strategy based approach which finds the defender's marginal strategy n and does not need to explicitly enumerate the exponential number of pure strategies. We now introduce a relaxed version of LP (5)∼(9) in LP (10)∼(14). LP (10)∼(14)

1 https://teamcore.usc.edu/papers/2017/ars17.Appendix.pdf

is similar to LP (5)∼(9) except that we replace equations (8) and (9) with equations (13) and (14) to model the relaxed marginal space. Recall that marginal strategies satisfy constraints (1)∼(2) (which lead to Equations 13 and 14) but drop constraint (3). The optimal marginal strategy n for the defender can then be found by solving the following MarginalStrategyLP (MSLP):

Though MarginalStrategyLP computes the optimal marginal strategy n, it may not correspond to any valid mixed strategy q, i.e., there may not exist a corresponding mixed strategy q such that n = ∑P∈ ˆ P qPP, ∑p∈ ˆ P qP = 1. Marginal strategies of this type are called non-implementable. However, when T r a have a particular structure, we can show the marginal strategy returned is the optimal for the defender. The intuition is that when T r a = 1 wa where wa ∈ Z+, the extreme points of the marginal polytope are all integer. In these cases, we can efficiently compute the defender's optimal implementable marginal strategy using the MSLP.

Theorem 2. For any feasible marginal strategy n to MSLP, there is a corresponding mixed strategy q that implements n whenever T r a = 1 wa where wa ∈ Z+, ∀r ∈ R,∀a ∈ A and Nc ≥ ∑r∈R 1 T r a , ∀c ∈ C for a given CAG.

6 CAGAlgorithmic Approach

The problem of non-implementability of marginals in security games has been studied in previous research [Letchford and Conitzer, 2013; Brown et al., 2016], but the nonimplementability arose because of spatio-temporal resource constraints and constraints from combining resources into teams. For our problem, non-implementability arises from the presence of the T r a coefficients (we discuss an example later). In this section, we present an algorithm that takes the initial constraints on a CAG and converts them to ensure the implementability of the marginal strategy. To that end, [Budish et al., 2013] presents a useful approach, as they define a special condition on the constraints on the marginals called a bihierarchy. A bihierarchy captures a sufficient condition needed to guarantee the implementability of the defender's marginal strategy n. Unfortunately, constraints on CAGs rarely satisfy the conditions for a bihierarchy and must be converted to achieve the bihierarchy condition.

Definitions and Notation The marginal assignments n for the defender form a |C| × |R| matrix. The assignment constraints on the defender's marginal strategy, namely Equations 13 and 14, are a summation of nc,r over a set S ⊂ |C| × |R| with an integral upper bound. For example, based on Equation 14, {{c1, r1}, {c1, r2}} forms a constraint subset for the example CAG. The collection of all such S form a constraint structure H when all coefficients in the constraints are unitary, as they are in Equation 14.

A marginal strategy n is said to be implementable with respect to H if there exists a distribution (a.k.a., mixed strategy) q such that n = ∑P∈ ˆ P qPP. A constraint structure H is said to be a hierarchy if, for any two constraint sets in H, we have that either one is a subset of the other or they are disjoint. More concretely, we have the following: ∀S1, S2 ∈ H, S1 ⊂ S2, S2 ⊂ S1 or S1 ∩ S2 = ∅. H is said to be a bihierarchy if there exists hierarchies H1 and H2, such that H = H1 ∪ H2 and H1 ∩ H2 = ∅.

For any CAG, the row constraints ∑r∈R nc,r ≤ Nc form a hierarchy H1. However, the column constraints, one for each resource r ∈ R, do not form a hierarchy: ∑a∈A ∑c∈Ca T r a nc,r ≤ 1. As mentioned earlier, the culprit lies in the T r a coefficients, as they can be non-unitary, and to achieve a hierarchy H2 on the column constraints, and thus give us a bihierarchy, all T r a coefficients must be removed.

Constraint Conversion The T r a coefficients admits possibly non-implementable marginal strategies to be returned. For instance, in Figure 1(b) the marginal strategy is nonimplementable, because it is impossible to get nc1,r2 = 2.5 by mixing pure assignments. This is because constraints (1) and (3), force the relevant pure strategy Pc1,r2 ≤ ⌊1/0.4⌋ = 2. We aim to convert the column constraints, namely: ∑a∈A ∑c∈Ca T r a nc,r ≤ 1 into a hierarchy by removing the T r a coefficients. The conversion can be completed by grouping together all nc,r which have the same T r a and introducing a new constraint on these sets of nc,r. Specifically, each column constraint (equation 13) is replaced with |A| constraints:

This conversion must be done for all analysts r ∈ R for the column constraints to form a hierarchy H2. LCa r gives an upper bound on the number of alerts of type a that an analyst can solve. The choices of LCa r must satisfy the original capacity constraint, namely: ∑a∈A T r a LCa r ≤ 1 and LCa r ∈ Z.

Conversion Example We refer to the example CAG where the marginal strategy is given in Figure 2. We must convert the column constraints to a hierarchy. We highlight how this conversion is done for r1 (as r2 is converted in the same manner). Initially, for r1 we have the following constraint:

We remove the T r a coefficients by grouping together all nc,r which share T r a and introducing two new constraints like (15). This leads to two new constraints:

These new constraints are shown for r1 in Figure 2 on the right of the arrow. Next, we must set the LCa r variables. One possible combination is H2 = {nc1,r1 + nc3,r1 ≤ 0, nc2,r1 + nc4,r1 ≤ 2} (H2 also includes constraints on r2 which are not shown). This satisfies the original the original analyst capacity constraints as: LCa1 r1 + 0.5 · LCa2 r1 ≤ 1. However, there is another choice for LCa r , H2 = {nc1,r1 + nc3,r1 ≤ 1, nc2,r1 + nc4,r1 ≤ 0}. Given either of the two hierarchies H2, we now have a bihierarchy. The original marginals shown in Figure 2 do not satisfy these new constraints; but solving the MSLP with these additional constraints in H2 is guaranteed to give an implementable marginal.

6.1 Branch-and-Bound Search

So far, we have seen that a marginal strategy n for a CAG output from the MSLP may be non-implementable. Our goal is to ensure that the marginal strategy output by MSLP is implementable by adding new column constraints, i.e., by realizing a bihierarchy. The addition of new constraints as outlined above gives us a bihierarchy, but there are multiple ways to set the values of LCa r variables (as shown in the above example), creating a choice of what bihierarchy to create. Indeed, we may need to search through the combinatorially many ways to convert the constraints of CAG to a bihierarchy. Previous work [Brown et al., 2016] proposed the Marginal Guided Algorithm (MGA) for creating bihierarchies, but MGA does not apply to CAGs as it does not deal with the non-unitary coefficients present in CAGs.

Here we propose a novel branch-and-bound search: out of the set of constraints that could be added to MSLP, find the best that would give the defender the optimal utility v∗ . At the root node, we have the original constraints (13) and (14); running MSLP potentially yields a non-implementable marginal strategy n. Then we branch from this root, where at each level in the tree, we add new constraints for an analyst r, and the children are expanded with the following rules:

1. Substitute ∑a∈A ∑c∈Ca T r a nc,r ≤ 1 with |A| constraints: ∑c∈Ca nc,r ≤ LCa r for all a ∈ A. The |A| new constraints form a set H2(r). A branch is created for all combinations of LCa r which satisfy ∑a∈A T r a ∗LCa r ≤ 1.
2. Solve theMarginalStrategyLP at each node with the modified constraints.

Thus, at each level of the tree, we have substituted the capacity constraint of some analysts, and for these, we have constraints of type (15), but for others, we still have constraint (13). This set of constraints does not form a hierarchy H2 as T r a coefficients are present in some analyst constraints. Still, at an intermediate node we have upper bound on the defender's utility v which is stated in Proposition 2, as each conversion from (13) to (15) introduces new constraints on the defender's strategy space.

Proposition 2. Each intermediate node in the tree gives an upper bound on the defender's utility v for all subsequent conversions for the remaining analyst capacity constraints.

A leaf in the search tree has column constraints only of the form: ∑a∈A nc,r ≤ LCa r . Hence, they form a hierarchy H2 as all nc,r have unitary coefficients and an integer upper bound. At a leaf, we can then solve the MSLP with the resulting bihierarchical constraints to find a lower bound on the defender's utility v. Combining this with Proposition 2 gives the components needed for a branch-and-bound search tree which returns the optimal bihierarchy for the defender.

Heuristic Search The full branch-and-bound procedure struggles with large CAG. To find good bihierarchies, we can take advantage of the optimal marginal strategy n∗ returned from MSLP at an intermediate node to reduce the amount of branching done. The intuition for this strategy, is that the optimal bihierarchy either contains, or is near, n∗ . For example, in the conversion done in Figure 2, we could set the LCa r values close to n. We set LCa1 r2 = ⌊1/.4⌋ = 2, while the leftover capacity for r2 is used to set LCa2 r2 = 1. LCa1 r2 could be set to another value, but our choice must stay close to n∗ .

For the heuristic search, we use the following rules to expand child nodes which must set the LCa r values for an analyst r: (1) LCa r = ⌈nCa,r⌉, (2) LCa r = ⌊nCa,r⌋ or (3) LCa r = ⌊ 1-∑a∈A T r a ∗LCa r T r a ⌋, where nCa,r = ∑c∈Ca nc,r. The third rule is used whenever an LCa r value cannot be set to the roof or floor of n∗ , and is set to be the max value given the leftover analyst capacity. These choices are done in an attempt to capture the optimal marginal strategy n∗ . The set of all valid combinations of the LCa r values using the above rules which satisfy ∑a∈A T r a LCa r ≤ 1 constitute the search space at each intermediate node. These rules then significantly re-

duce the branching at intermediate nodes in the search tree.

Convex Hull Extension The above searches return a set of good bihierarchies for obtaining a high value of v∗ for the defender when solving MSLP, as each leaf contains a bihierarchy Hi. Each bihierarchy Hi contains a portion of the defender's mixed strategy space (due to new constraints). Thus, taking a convex hull over these bihierarchies increases the size of the defender's strategy space and hence, will only improve the defender's utility. Note, as each bihierarchy is implementable, the convex hull will also be implementable [Brown et al., 2016].

To take the convex hull, first notice each bihierarchy Hi is a set of linear constraints and can be written as Din ≤ bi for matrix Di and vector bi. Hence, by definition n(Hi) = {n|Din ≤ bi}. Using a result from [Balas, 1985] that represents the convex hull using linear constraints, we can write: conv(n(H1), . . . , n(Hl)) = {n| ∑i ni,Dini ≤ λibi, λi ≥ 0, ∑i λi = 1}. The convex hull of the bihierarchies can then be computed efficiently using an LP similar to MSLP.

In terms of the convex hull we have two options available: (1) Take the convex hull of all bihierarchies or (2) build the convex hull iteratively. In some cases, the set of bihierarchies available to the defender can be very large and hence, optimizing over all bihierarchies is not feasible. To alleviate this issue, the convex hull can be built iteratively. This is done by first sorting the bihierarchies by the defender utility v. Next, we take the convex hull of the top two bihierarchies which gives a utility v′ to the defender. We continue adding bihierarchies to the convex hull while the utility v′ returned increases by at least some ϵ, and stop otherwise.

7 Evaluation

We evaluate the CAG model and solution algorithms with experiments inspired by the operations of the AFCYBER. The game payoffs are set to be zero-sum, i.e. U u δ,c = -U u θ,c , and the defender's payoffs are randomly generated with U u δ,c uniformly distributed in [-1, -10]. The rest of the game payoffs, U d δ,c and U d θ,c , are set to be zero. For each experiment we average over 30 randomly generated game instances.

• (c) Runtime Comparison

Figure 3: Experimental Results for CAG instances.

Full vs Heuristic Search Whether the heuristic approach of staying close to n∗ would yield the right solution qualityspeed tradeoff remains to be seen. To test this, we compare the performance of the full branch-and-bound search (Full) to the heuristic search (Heur). For this experiment we test two variations of the full search: Full-1 which uses the full convex hull and Full-2 which uses the iterative convex hull. For the Heuristic search we test the same two variations, labeled as Heur-1 and Heur-2. For these instances we have 20 systems, 3 attack methods, and 3 alert types.

In Figure 3(a) we vary the number of resources on the xaxis and we show the runtime in seconds on the y-axis. As can be seen the runtime of the full search explodes exponentially as the number of resources is increased. However, the average runtime of the heuristic approach is under 1 second in all cases and provides up to a 100x runtime improvement for 5 resources. In Figure 3(b) the number of resources are on the x-axis while the y-axis shows the defender's expected utility. This graph shows that all variations perform similarly, with the heuristic suffering less than 1% solution in defender utility compared to the full search for all game sizes. Hence, these results show that our heuristic significantly improves runtime without sacrificing solution quality.

Solving large CAG Another important feature of realworld domains are the larger number of cybersecurity analysts available to investigate alerts. Accordingly, our next experiment tests the scalability of our heuristic approach to large CAG instances. The parameters for these experiments are 100 systems, 10 attack methods, and 3 alert levels.

In Figure 3(c) we show the runtime results with the number of analysts on the x-axis and the runtime in seconds on the y-axis. For example, Heur-1 takes an average of 40 seconds to solve a CAG with 10 analysts. This graph shows the heuristic runs in under a minute, even as we increase the analysts from 6 to 14. In Figure 3(d) we show the solution quality results with the number of analysts on the x-axis and the defender's expected utility on the y-axis. We compare the solution quality to the (potentially non-implementable) MSLP solution. This graph highlights that the heuristic approach achieves a utility close to the theoretical optimal value. Therefore, this experiment shows that our approaches scale to large CAG without sacrificing much solution quality.

Allocation Approach Our last experiment aim to show that our game theoretic apporach for CAGs outperform approaches used in practice. In addition to our heuristic, we compare against a greedy approach which investigates the highest priority alerts from the most critical bases first and a random approach for the allocation. The parameters for this experiment are 20 systems, 5 attack methods, and 10 analysts. In Figure 4(a) we show the solution quality results. On the x-axis we vary the number of alert types and on the yaxis we show the defender's utility. For example, with 4 alert types the heuristics achieve a utility of -7.52 while the greedy and randomized allocations give -9.09 and -9.65, respectively. This difference is statistically significant (p < 0.05). In Figure 4(b), we show a solution comparison for a specific CAG instance. This graph gives intuition for why our approach performs so well. The greedy and random approaches tend to overprotect some systems (system 4) while leaving others without adequate protection (system 2).

8 Conclusion

In this paper we address the pressing problem in cyber security operations of how to allocate cyber alerts to a limited number of analysts. We introduce the Cyber-alert Allocation Game (CAG) to analyze this problem and show computing optimal strategies for the defender is NP-hard. To solve CAG, we present a novel approach to address implementability issues in computing the defender's optimal marginal strategy. Finally, we give heuristics to solve large CAGs, and give empirical evaluation of the CAG model and solution algorithms.

Acknowledgments

This research was supported by the U.S. Army Research Office under award number W911NF-15-1-0515 and by the U.S. Department of Homeland Security Summer Research Team program.