Detecting network intrusions via sampling: a game theoretic approach

Detecting Network Intrusions via Sampling : A Game Theoretic Approach
{muralik, lakshman}@bell-labs.com a more detailed examination of the packet. To prevent packet In this paper, we consider the problem of detecting an in- mis-ordering or reduction of link throughput this examination truding packet in a communication network. Detection is ac- has to be done preferably at line rates. Packet sampling has complished by sampling a portion of the packets transiting se- been previously proposed for a variety of networking purposes.
lected network links (or router interfaces). Since sampling en- For instance, the SRED scheme in [6] uses packet sampling to tails incurring network costs for real-time packet sampling and estimate the number of active TCP flows in order to stabilize packet examination hardware, we would like to develop a net- network buffer occupancy for TCP traffic. Only packet headers work packet sampling strategy to effectively detect network in- need be examined for this scheme. The scheme proposed in [7], trusions while not exceeding a given total sampling budget. We also uses packet sampling and it is used for fair link-bandwidth consider this problem in a game theoretic framework, where the allocation. Sampling has also been proposed to infer network intruder picks paths (or the network ingress point if only short- traffic and routing characteristics [3]. Whereas, these applica- est path routing is possible) to minimize chances of detection tions require only sampling based on packet header compar- and where the network operator chooses a sampling strategy to isons, intrusion detection may entail a more thorough exami- maximize the chances of detection. We formulate the game the- nation of sampled packets. Also, unlike some of the sampling oretic problem, and develop sampling schemes that are optimal applications mentioned above, sampling for intrusion detection requires near line-speed packet examination since copying sam-pled packets or packet-headers for off-line analysis is not suffi-cient to prevent intruding packets from getting through. Hence, in the design of an intrusion detection scheme it is imperative In this paper, we consider the problem of detecting intrusions in a communication network. There is growing literature on We study this intrusion detection via sampling problem in providing security in communication networks. Two key areas a game theoretic setting. Game theory has been used exten- of interest in security are intrusion detection and intrusion pre- sively to model different networking problems. This work in- vention. In this paper, we deal with the problem of intrusion cludes the work of Shenker for modeling service disciplines detection. Intrusion in networks takes many forms including [10], Akella et. al. for TCP performance [2], and Korilis, denial of service attacks, viruses introduced into the networks, Lazar and Orda [5] for modeling routing problems. To the etc. Typically, in an intrusion problem, the intruder attempts to best of our knowledge, this is the first attempt to model intru- gain access to a particular file server or website in the network.
sion detection via sampling in communication networks using In this paper, we consider a stylized intrusion problem. In this a game-theoretic framework. This work is closely related to problem, the intruder attempts to send a malicious packet to a drug interdiction models. In particular the work of Washburn given node in the network. The network attempts to detect this and Wood [11] who considered drug interdiction in a game the- intrusion. The detection mechanism is packet sampling and ex- oretic framework. This work differs from the drug interdic- tion models in two ways. First, in the drug interdiction models The idea in sampling is that some portion of packets travers- the objective is to deploy agents which is a discrete allocation ing designated links (or router interfaces) are sampled and ex- problem. In our case, the detection is by means of sampling.
amined in detail to determine whether the packet is an intruder Therefore the game theoretic results are much more natural packet. This packet examination may be simple (limited to spe- than the discrete allocation models. Secondly, in our case, the cific packet header fields as in packet filtering) or may involve game theoretic problem naturally leads to a routing problem (to maximize the service provider’s chances of detecting intruding packets) which is absent in the drug interdiction problem. Thesolution to the game theoretic formulation is a maximum flowproblem and the routing problem can be formulated as a multi-commodity flow problem. We also consider various extensionsand variants to the basic models.
The problem set-up is outlined in three steps. First, we de- scribe the network, then we define the adversaries in the game-theoretic framework, and finally we describe the objective of the game that is played between the adversaries.
and hence detect the malicious packet. Sampling the packets We consider a network G = (N, E) where N is the set of flowing on a link involves setting up the appropriate sampling nodes and E is the set of unidirectional links in the network.
filters and examining the packets. These can be fairly expen- We assume that there are n nodes and m links in the network.
sive operations to perform in real time. Therefore, we assume We assume that the capacity of link e ∈ E is denoted by c that the service provider has a sampling bound of B packets the amount of traffic flowing on link e is denoted by f per second over the entire network. This sampling effort can be two nodes u and v in the network, let Pv distributed arbitrarily over the links in the network. One way paths from u to v in G. Given an m-vector w, we use M of implementing the sampling scheme is for each link to pick to denote the maximum flow that can be sent from node u to some fraction of the packets flowing through it and send it to a node v using w as the link capacities. We use the parameter w central intrusion detection node in the network which examines the packet in more detail. The sampling bound can be viewed uv () to indicate that dependence of the maximum flow on the link capacities. Corresponding to this as the maximum rate at which the intrusion detection node can maximum flow between nodes u and v, there is a minimum cut process packets in real time. If a link e that has a traffic of fe comprising of a set of links in the network. This set of links in flowing on it, is sampled at rate se then the probability of detect- this minimum cut will be represented by Cv( ing a malicious packet on this link is given by p mulate the game theoretic problems in terms of p that both the players have complete information about the topol- The network intrusion detection game is played on the net- ogy of the network and all the link flows in the network. The work between two players: the Service Provider and the In- service provider can have access to this information either from truder. The objective of the intruder is to inject a malicious link-state routing protocols with traffic engineering extensions packet from some attack node a ∈ N with the intention of at- that distribute flow information throughout a network area or tacking a target node t ∈ N. We assume that an intrusion is by explicit link polling from management systems. We assume successful when the malicious packet reaches the desired tar- that the adversary injecting intruding packets has this informa- get t node without detection. In order to detect and prevent the tion available as well since this makes the service provider’s intrusion, the service provider is allowed to sample packets in detection problem more difficult. Similarly, we also assume the network. We assume that sampling takes place on the links that the intruder is capable of picking paths in the network so in the network. It is easy to modify the model to consider the as to make the detection problem for the service provider more case, where the sampling is done at the nodes in the network. If difficult. However, in Section V-A, we also consider the case during the course of sampling, the service provider samples the where only shortest path routing is allowed in the network.
malicious packet then the intrusion is assumed to be detected 1) Strategies for the Two Players: In the case of the intruder, and thwarted. The game is pictorially illustrated in Figure 1.
a pure strategy would be to pick a path from P ∈ Pta for the ma-licious packet to traverse from s to t. The intruder, in general, C. The Objective and the Constraints of the Game can use a mixed strategy. In the case of a mixed strategy, the in- If there is no bound on the amount of sampling that can be truder has a probability distribution q over the set of paths in Pta done by the service provider, then the service provider can po- tentially inspect every packet that flows through the network represent the set of feasible probability allocations over the set of paths between a and t. The intruder then picks path P ∈ Pta detected as it goes from a to t. For a given path P ∈ Pta, the with probability q(P ). The strategy for the service provider is expected number of times that a packet is detected is given by to determine a set of links on which sampling has to be done.
The probability that this path P is picked by the The strategy for the service provider is to choose the sampling intruder is given by q(P ). Therefore the expected number of rate se on link e such that times a packet is detected as it goes from the source to the des- packet traverses link e with a sampling rate of se on a link with tination for a fixed strategy from both adversaries is given by flow fe results in the malicious packet being detected with prob-ability pe = se/fe. Let U = {p : the set of detection probability vectors p that satisfy the sam- pling budget constraint. (Note that p is an m- vector.) Instead of viewing the service provider as picking the sampling rates Interchanging the order of summation, we get at the links, we view the service provider as picking a set of detection probabilities at the links which belongs in the set U .
Figures 2 and 3 depict the intruder’s and the service provider’s Intruders Strategy: Pick a path from a to t This can be equivalently written in a matrix form as qT M pwhere M is an m × |Pta| path-arc incidence matrix. Each rowin M represents a link in the network and each column of Mrepresents a path between nodes a and t. The entry correspond- ing to row e and column P is set to one if e ∈ P and to zero otherwise. A more natural payoff, is the probability of detec- tion of the malicious packet as opposed to the expected num-ber of times the malicious packet is detected. In this case fora fixed path P ∈ Pta, the probability of the malicious packetbeing detected is given by 1 − Defenders Strategy: Pick the sampling rates at the links is non-linear in pe which makes the game theoretic problemintractable. However, the two payoffs that we outlined above coincide if the optimal solution for the service provider is tosample at most one link on any path P ∈ Pta with q(P ) > 0.
We call this strategy a minimal sampling strategy. We showlater that for all the problems we consider, the optimal solutionis a minimal sampling strategy.
that if his strategy is known to the service providerthen tive of the intruder is to pick a distribution q() that minimizes The objective of the service provider, using a similar argument 2) Payoff Matrix: Assume that the intruder and the service provider each have chosen a strategy. This implies that the in- truder has picked a probability distribution q over the set of a and the service provider has picked a set of de- tection probabilities p at the links. The payoff that we con- This is a classical two person zero-sum game and the following sider, is the expected number of times the malicious packet is Theorem 1: There exists an optimal solution to the intrusion Interpreting q(P ) as a flow on path P , the constraint restricts the flow on a link e to be f can be interpreted as the capacity of link e. The constraint q(P ) = 1 enforces one unit of flow to be sent from the source to the destination. Assume that fe is the capacity of link e in the network. The objective then is to determine the where θ is the value of the game.
smallest scaling factor λ, on the links in the network so that a In the rest of this paper, we show how this minmax optimal flow of one unit can be sent from the source to the destination.
solution can be computed for the intrusion detection game and use that insight to route flows in the network.
• Assume that link e has capacity fe and determine the max- imum flow, Mat(f ) from the a to t using these capacities.
• Set λ = Mat(f )−1. By scaling the capacities by λ, note We now consider the solution of the minmax problem formu- that a flow of one unit is sent from a to t.
lated in the last section. The idea is to get some insight into the • The value of the game θ = BMat(f )−1.
structure of the problem which will enable us to extend the so- Any maximum flow from a to t can be decomposed into a set lution to more complex cases. Consider the intruders problem.
of flows on paths from a to t using standard flow decomposition techniques. From network flow duality, note that corresponding to the maximum flow value there is a minimum cut. The stable operating point for the intruder and the service provider are the For a fixed q ∈ V the inner maximization problem is the fol- • Intruders Strategy: Solve the maximum flow Mat(f ), from a to t using a capacity of fe on link e. Using stan-dard flow decomposition techniques, decompose the max- imum flow into flow on paths P1, P2, . . . , Pl from a to t. with flows of m1, m2, . . . , ml respectively. (Note that li=1 mi = Mat(f ).) licious packet along the path Pi with probability mi ∗ • Service Providers Strategy: The service provider com- putes the maximum flow from a to t using f Associating a dual variable λ with the budget constraint, we obtain the following dual optimization problem.
1, e2, . . . , er denote the arcs in the cor- responding minimum cut with flows f1, f2, . . . , fr. From ri=1 fi = Mat(f ). The service provider samples link ei at rate BfiMat(f )−1.
We now illustrate the above results on the example shown in Figure 4. The numbers next to the links are the flows on the links. How these flows are generated is discussed in detail ina subsequent section. For now assume that the flows on the Substituting this optimization problem in the intruders minmax links are given. Assume that there is a sampling budget B of formulation makes it the following minimization problem.
5 units. and a = 1 and t = 5 are the attack and target nodes respectively. The links (1, 2), (4, 5) belonging to the minimuma − t cut are shown in thick lines. The minimum cut (and hence the maximum flow) has a value of 11.5 units. The intruder’s • Introduce the malicious packet along the path 1-2-5 with • Introduce the malicious packet along the path 1-2-6-5 with • Introduce the malicious packet along the path 1-3-4-5 with The minmax strategy for the service provider is the follow- • Sample link 1-2 at rate 5/11.5 giving a total sampling rate of (5 × 7.5)/11.5 on that link.
• Sample link 4-5 at rate 5/11.5 giving a total sampling rate of (5 × 4.0)/11.5 on that link.
Note that θ = 5/11.5 is the value of the game.
The following observations can be made about the minmax • The optimal strategy for the service provider is to sample packets on the mincut with respect to the traffic flows. Thisimplies that along any path that the intruder would choose, for commodity k will be represented by s(k), the destination the malicious packet will be sampled at most on one link.
node by d(k) and the amount of demand (bandwidth) that has Therefore this is a minimal sampling scheme.
to be routed for this source-destination pair is b(k). The service • If B ≥ Mat(f ) then note that the malicious packet will al- provider has to route these flows in the network respecting the ways be detected. If B < Mat(f ) then there is a non-null link capacity constraints. For the example shown in Figure 4, probability that the malicious packet will not be detected.
each link is assumed to have a capacity of 10 units. The dif-ferent source-destination pairs and the corresponding demands IV. ROUTING TO IMPROVE THE VALUE OF THE GAME are shown in Table I. These demands have to be routed in the In the last section, we showed that the value of the network network such that the link capacity constraints are respected.
intrusion game is given by BMat(f )−1. All along, we assumed There are several ways of routing these demands. One com- that the flow f on the links is fixed. The flows on the links are monly used method is to route the demands such that the max- a result of routing the demands (aggregate traffic between node imum link utilization in the network is minimized. (This can pairs) in the network. In this section, we explore the case where be solved as a maximum concurrent flow problem.) The link the service provider adjusts the flows in the network in order to flows shown in Figure 4 are a result of routing the demands in maximize the value of the game. Corresponding to each pair order to minimize the maximum utilization in the network. The of nodes in the network, there could potentially be demands that have to be routed from the first node in this pair to the We now explore the case where the service provider routes second node. Each node pair between which there is some de- these flows such that the value of the network intrusion game mand that has to be routed is termed a source-destination pair is maximized. In other words, the service provider routes the or a commodity. We assume that there are K source-destination source-destination demands such that the maximum probabil- demand pairs (commodities) in the network. The source node ity of detection of the malicious packet is increased. We first formulate this problem and then explore different heuristics Instead of minimizing the left hand side of the inequality, we to solve the problem. Recall that Pd(k) minimize the upper bound represented by the right hand side of paths between the source node s(k) and the destination node the inequality. Since c is fixed, this is equivalent to maximizing d(k) for commodity k. For notational simplicity, we refer to x(P )) subject to the constraint that x X. We write this more formally as: Note that Pk represents the set of valid paths to route commodity k. Let X = {x(P ) : ≤ ce ∀e ∈ E}. Note that X denotes an allocation of flow on paths in the network which meets the demand for each commodity while satisfying the ca-pacity constraints on the links in the network. Given a fea- sible routing vector, x ∈ X, the flow on link e is given by x(P ). From Section III, the value of the game is given by B/Mat(f ). The objective of the ser- vice provider then is to route the source destination demands such that the resulting value of Mat(f ) is as small as possible.
Therefore the objective of the service provider is to solve the It is easy to view this as a multi-commodity flow problem with K + 1 commodities. There are the original K commodities andan additional commodity between a and t. The size of the de- mands for the first K commodities are known. We perform a bisection search to determine the largest value of the commod-ity K + 1 that still results in a feasible routing for the first K commodities. In order to develop an efficient algorithm it is better to formulate the problem as a maximum concurrent flow problem and perform the bisection search for this problem in-stead. We do not give the details of the solution procedure. In Unfortunately this problem cannot be solved as a linear pro- the case of the flow flushing algorithm, the link flows for the ex- gramming problem. It is possible to reformulate this problem ample in Figure 4 are shown in Figure 5 and the corresponding as a non-convex optimization problem but it is not clear if there is a solution technique to solve this problem. We therefore de-velop two different heuristics to get good solutions to this opti- Let the m-vectors c and f represent the link capacity and the flow on the link respectively. The flow on the links is a result of routing the different source- destination demands in Mat(f) + Mat(c − f) ≤ Mat(c). This is true since the set of flows in the two terms on the lefthand side of the inequality is a feasible flow for the right hand side of the inequality. Therefore M at(f ) ≤ Mat(c) − Mat(c − f ). If f is the result of routing the source-destination demands x(P )) ≤ M(c)−M(c− at(f ) on this network is 9.95 units.
The value of the game θ = 5/9.95. We now outline another heuristic that can be used by the service provider to improve Fig. 6. Cut Saturation Algorithm Network Set-up the probability of detection of the malicious packet.
This algorithm relies on the fact that the maximum flow be- tween a and t is upper bounded by the size of any a − t cut.
Let C represent the set of links in some a − t cut. Given any link e ∈ E, let α(e) and β(e) represent the start and end nodes of that link. The cut saturation algorithm picks some a − tcut and tries to direct flow away from this cut. Once the source- destination demands are routed, this cut will be small and hence will limit the maximum a − t flow. This is done as follows: In-troduce two new nodes s and t . Introduce an arc between node s and all nodes α(e) for all e ∈ C. Similarly introduce links between each node β(e) for each e ∈ C and the node t . The objective now is to determine the highest flow that can be sentfrom s to t while maintaining the feasibility of routing thesource-destination demands. The modification of the network saturation algorithm gives a better solution that the flow flush- is shown in Figure 6. The only links shown in the network are This problem can be solved almost identically to the Flow Flushing Algorithm, except that the K + 1 commodity flows go between nodes s and t . One way of choosing the cut that is We consider several variants of the problem outlined above.
to be saturated is as follows: Assume that we currently have a The first variant that we consider is the case where the intruder routing of the source-destination demands resulting in a flow of can introduce the malicious packet at one of a set of nodes A ⊂ f (e) on link e. Determine a minimum a − t cut (using these ∈ A. The second variant that we consider flows f as the capacities). Take this cut to be C and now at- is the case where the objective of the intruder is to reach any one tempt to saturate this cut. Continuing the example in Figure of of a set of nodes T ⊂ N. We assume that A ∩ T = ∅. Both 4, assume that the cut that we saturate comprises of the links these cases are easy to solve by introducing a super source node (1, 2) and (4, 5). The links flows are shown in Figure 7 and the that is connected to all nodes in A and connecting all nodes incorresponding flows are shown in Table IV.
T to a super sink node. The game is now played between the The maximum flow Mat(f ) on this network is 8.0 units. The super source node and the super sink node. Another variant is value of the game θ = 5/8. Therefore, in this example, the cut the case where the intruder can introduce the packet at any one Note that L(d) represents the maximum flow that can be sent from all the nodes in A to the destination node d. The value of In this section we evaluated the algorithms developed on two networks. The first network is shown in Figure 8. Each undi- rected link in the figure represents two directed links each hav- ing a capacity of 10 units. We performed the following experi- of a set of nodes A but we assume that the intruder does not have control of the routing in the network. Instead, we assume that the routing in the network is shortest path routing like inOSPF or IS- IS. We term this a shortest path routing game.
We now consider the problem where the routing in the net- work is along shortest paths. We assume that each link has alength and packets are routed from the source to the destination along shortest paths according to this length metric. We assume that ties are broken arbitrarily. Therefore given any two nodesin the network, there is a unique path from one node to the other.
Given a target node, all packets arriving at this node traverse theshortest path tree. Shortest path routing implies that there is a unique tree rooted at the destination. A packet introduced at any • Single attack node and single target node. (3 problems).
node in the network traverses the unique path from that node to • Multiple attack node and single target node. (1 problem).
the destination along the links in the shortest path tree. We use • Multiple attack node and multiple target node. (1 prob- A to represent the set of nodes that the intruder can introduce a malicious packet into the network. The objective of the intruder For each of the cases, we ran three different algorithms.
is to determine which node of this set A to introduce the packet 1) Routing to minimize the highest utilized link with f1 rep- into and the objective for the service provider is to determine resenting the m-vector of link flows as a result of this the sampling rate at the links subject to a sampling budget of B. The main difference between this problem and the problem 2) Routing with flow flushing algorithm with f2 represent- that we originally studied is the fact that it is easy to compute ing the m-vector of link flows as a result of this routing the maximum flow and hence the minimum cut on a tree. The algorithm for solving this problem is the following: 3) Routing with cut saturation algorithm with f3 represent- • Eliminate all leaf nodes in the routing tree that do not be- ing the m-vector of link flows as a result of this routing long to A. Let T represent this tree. Let P (i) represent the predecessor of node i on T .
Let M (fi) for i = 1, 2, 3 represent the maximum flow that can • Set L(i) = ∞ for all leaf nodes.
be sent from node a to t using fi as the link capacities. If B is • While there are no leaf nodes do the sampling budget, then the value of the game θ = B/M (). – Pick a leaf node i. Let e be the edge connecting i to
Table V shows the values of M () instead of θ. The smaller P (i). Set L(P (i)) ← L(P (i)) + min{L(i), fe}. that value of M , the better the chances of detection for a given • Output L(t).
COMPARISON OF DIFFERENT ROUTING ALGORITHMS From the table, note that the maximum flow value and hence the value of the game can be changed significantly by changing the routing in the network. In most of the examples the perfor-mance of the flow flusing algorithm and the cut saturation algo- rithm are quite similar, and better than the simple minimization Max. Utilization vs. Link Capacity for flow routing to minimize A. Effect of Capacity on the Value of the Game As the amount of spare capacity in a network increases, the opportunity to reroute flows increases. This implies that theservice provider can improve the probability of detection byexploiting the spare capacity to reroute flows. We illustrate this in the following set of experiments, using a second example network, where the capacity of the links in the example network are fixed at some constant value C. If the value of C increases,then the opportunity to reroute flows goes up. We consider theintrusion detection game between nodes a = 1 and t = 13. The demands in the network are uniformly distributed between zeroand one. We first run the algorithm to route the flow such that maximum utilization of any link is minimized. This maximumutilization value versus the link capacity C is shown in Figure9. As the maximum utilization becomes lower, the amount of spare capacity to reroute flows increases in the network. This implies that both the flow flushing algorithm as well as the cut saturation algorithm will have more alternate paths. In Figure10, we show the performance of the flow flushing algorithm as Fig. 10. Performance of flow flushing algorithm for different link capacities the value of C increases. The straight line in the plot showsthe performance of the base case which is the routing algorithmthat minimizes the maximum utilization. The a − t maximum packet sampling and examination in real-time can be expen- flow is independent of the value of C. In the case of the flow sive, the network operator must devise an effective sampling flushing algorithm, the a − t maximum flow value decreases scheme to detect intruding packets injected into the network with increasing link capacity. It asymptotes at about 8.8. The by an adversary. We considered the scenario where the adver- same kind of performance was observed in the case of other sary has considerable information about the network and can attack-target pairs as well as the case for multiple attack sites.
either pick paths to minimize chances of detection or can pick asuitable network ingress-point if only shortest path routing is al-lowed. The detection via sampling problem was formulated in a game-theoretic framework. The solution to this game-theoretic We considered the problem of detecting intruding packets problem is a max-flow problem from which the stable operat- in a network by means of network packet sampling. Since ing points are obtained. We also considered the network op- erator’s problem of routing aggregate traffic between ingress-egress pairs as to to maximize the chances of detection withina given packet sampling budget. We proposed two heuristic al-gorithms for solving this problem. Finally, we evaluated theperformance of the developed algorithms on some sample net-works.
[1] R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows: Theory, Algo- rithms, and Applications, Prentice Hall, 1993.
[2] Akella, A., Karp, R., Papadimitriou, C., Seshan, S., Shenker, S., “Selfish Behavior and the Stability of the Internet: A Game Theoretic Analysis ofTCP”, Proceedings of SIGCOMM 2002, 2002.
[3] Duffield, N., Greenberg, A., Grossglauser, M., Rexford, J., “A Framework for Passive Packet Measurement”. IETF Draft, work in progress, draft-duffield-framework-papame-01, February 2002.
onemann, J., “Faster and Simpler Algorithms for Multi- commodity Flow and other Fractional Packing Problems”, Proceedingsof the 39th Annual Symposium on Foundations of Computer Science,pp.300-309, 1998.
[5] Korilis, Y., Lazar, A., Orda, A., “Architecting Noncooperative Networks”, IEEE Journal on Selected Areas in Communications, pp. 1241-1251,September 1995.
[6] Ott, T. J., and Lakshman, T. V., and Wong, L. H., “SRED: Stabilized RED”, Proceedings of Infocom 1999, pp. 1346-1355, 1999.
[7] Pan, R., Prabhakar, B., Psounis, K., “CHOKE, A Stateless Active Queue Management Scheme for Approximating Fair Bandwidth Allocation”,Proceedings of Infocom 200, pp. 942-951, 2000.
[8] Owen, G., Game Theory, Academic Press, New York.
[9] Shahrokhi, F., and Matula, D., “The Maximum Concurrent Flow Prob- lem”, Journal of the ACM, 37, pp. 318-334, 1990.
[10] Shenker, S., “Making Greed Work in Networks: A Game-Theoretic Anal- ysis of Switch Service Disciplines”, IEEE/ACM Transactions on Net-working, 1995.
[11] Washburn, A., and Wood, K., “Two-Person Zero-Sum Games for Net- work Interdiction”, Operations Research, 43, pp. 243-251, 1995.

Source: http://www.ieee-infocom.org/2003/papers/46_02.PDF