PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Games for Security in Networks with Interdependent Nodes

Kien C. Nguyen, Tansu Alpcan, Tamer Basar

arXiv:1003.2440v1cs.CRcs.GT

TL;DR

The paper addresses security-game models that leave assets independent or omit compromise dynamics. It combines influence networks for correlated security assets and vulnerabilities with a zero-sum stochastic game, establishing a unique solution vector and finite expected payoff.

  • Problem

    Earlier models either assumed independent security assets or did not account for the dynamics as nodes are compromised.

    Source: §I · p. 1

  • Method

    The paper combines linear influence networks for security assets and vulnerabilities with a zero-sum stochastic game between an Attacker and a Defender.

    Source: §I · p. 1, B. A zero-sum stochastic game model… · p. 5

  • Results

    The game has zero probability of infinite play and finite expected payoff, and exactly one vector satisfies the stated solution equations.

    Source: C. Existence, uniqueness, and… · p. 5

  • Takeaways & Limitations

    The resulting optimal solution describes rational attacker behavior and provides IDSs with guidelines for allocating resources.

    Source: §V · p. 7

Abstract

from arXiv · show

This paper studies a stochastic game theoretic approach to security and intrusion detection in communication and computer networks. Specifically, an Attacker and a Defender take part in a two-player game over a network of nodes whose security assets and vulnerabilities are correlated. Such a network can be modeled using weighted directed graphs with the edges representing the influence among the nodes. The game can be formulated as a non-cooperative zero-sum or nonzero-sum stochastic game. However, due to correlation among the nodes, if some nodes are compromised, the effective security assets and vulnerabilities of the remaining ones will not stay the same in general, which leads to complex system dynamics. We examine existence, uniqueness, and structure of the solution and also provide numerical examples to illustrate our model.

I. INTRODUCTION

Earlier intrusion-detection games left security assets independent or omitted compromise dynamics. This paper extends stochastic-game modeling to correlate nodes in both security assets and vulnerabilities.

I. INTRODUCTION

  • Earlier models left a gap: assumed independent security assets and omitted compromise dynamics, while modeled vulnerability correlation but retained independent assets and zero-sum games.Source: §I · p. 1
  • The proposed linear influence network model lets stochastic games represent correlation among nodes in both security assets and vulnerabilities.Source: §I · p. 1

Summary of notations and variables used in this paper

II. LINEAR INFLUENCE NETWORK MODELS FOR SECURITY ASSETS AND FOR VULNERABILITIES

The network model uses two weighted directed graphs to represent interdependence among nodes: one for security assets and one for vulnerabilities.

  • The model represents security-asset relationships and vulnerability correlations with separate weighted directed graphs.Source: §II · p. 2

A. Linear influence network model for security assets

Security assets are modeled as influence distributed across a weighted directed graph, producing effective assets that change when nodes are compromised. The model conserves total assets while treating a compromised node's effective asset as the network's security loss.

A. Linear influence network model for security assets

B. Linear influence network model for vulnerabilities

A directed support network models how nodes influence one another's vulnerabilities. When a supporting node goes down, support can fall and the compromise probability of a node under attack can rise.

B. Linear influence network model for vulnerabilities

A. A brief overview of zero-sum stochastic games

A zero-sum stochastic game represents each game element with a matrix of payoffs and transition probabilities. Its value vector and stage-dependent strategies describe expected payoffs and player choices across the game.

A. A brief overview of zero-sum stochastic games

  • At game element Γk, each matrix entry combines a payoff to player 1 with probabilities of moving to another game element or ending play.The expected payoff to player 1 is accumulated across stages; the probability of infinite play is zero under the stated condition.Source: A. A brief overview of zero-sum… · p. 4
  • Each player’s strategy specifies a probability vector for every game element and stage, with stationary strategies using vectors that do not vary by stage.Player 1’s vectors assign probabilities to pure strategies; player 2’s strategy is defined similarly.Source: A. A brief overview of zero-sum… · p. 4
  • The value component for each game element is the value, in mixed strategies, of its associated matrix game.The expected-payoff vector has one component per game element.Source: A. A brief overview of zero-sum… · p. 5

B. A zero-sum stochastic game model for network security

The network security problem is formulated as a zero-sum stochastic game in which players choose actions at each network state. Correlated assets and vulnerabilities affect attack outcomes as compromised nodes change the effective assets and supports of remaining nodes.

B. A zero-sum stochastic game model for network security

  • At each network state, the Attacker can attack one of n nodes or do nothing, and the Defender can defend one node or do nothing.Each player therefore has n + 1 pure actions.Source: B. A zero-sum stochastic game model… · p. 5
  • The payoff for attacking depends on attack success probability and the target node’s effective security asset.The attack-success probabilities depend on node supports and thus reflect vulnerability correlation; effective assets and supports are recalculated after a node is compromised.Source: B. A zero-sum stochastic game model… · p. 5
  • The stochastic formulation allows play to continue through network states or end, with failed attacks potentially returning the network to its initial state.The described state transitions include detection and restart outcomes.Source: B. A zero-sum stochastic game model… · p. 5

C. Existence, uniqueness, and structure of the solution

The proposed game has finite expected payoff and a unique value vector. A recursive procedure computes that vector and yields optimal stationary mixed strategies for the Attacker and Defender.

C. Existence, uniqueness, and structure of the solution

  • The game has zero probability of infinite play and a finite expected payoff for the Attacker, which is also the Defender’s expected cost.The proof uses positive probabilities of game termination for each game element.Source: C. Existence, uniqueness, and… · p. 5
  • There is exactly one value vector satisfying the game’s defining equations, and it determines a pair of stationary mixed-strategy Nash equilibria at each state.Source: C. Existence, uniqueness, and… · p. 5
  • A recursive procedure approximates the value vector and obtains strategies that converge to optimal stationary strategies of the stochastic game.The recursion can stop at a desired accuracy; the players’ strategies at each state are the mixed-strategy equilibria of the corresponding matrix game.Source: C. Existence, uniqueness, and… · p. 5

IV. A NUMERICAL EXAMPLE

A three-node numerical example uses a simplified state-transition model to compute optimal strategies and a game value vector. The example shows how the players’ mixed strategies allocate security resources across nodes.

IV. A NUMERICAL EXAMPLE

  • The simulation allows one additional node to become compromised per step, a return to the same state, or a transition back to S1(0,0,0).This is a simplified state diagram for the three-node network.Source: §IV · p. 5
  • When all nodes are up and running, the Attacker targets node 1 with probability 0.6126 and node 3 with 0.3874; the Defender protects node 1 with 0.0702 and node 3 with 0.9298.At this state, the effective security assets of nodes 1, 2, and 3 are 11, 7, and 22, respectively.Source: §IV · p. 6
  • The recursive procedure computes optimal strategies and a value vector, which converges to an accuracy of 10^-4 after 56 iterations.Table III is identified as the value vector, representing the Attacker’s expected payoffs and the Defender’s expected losses at each game element.Source: §IV · p. 6, Table III · p. 6
  • The mixed strategies can also be interpreted as the players’ resource allocations in the security game.The Attacker’s distribution allocates attacks across nodes, while the Defender’s distribution allocates monitoring and defense.Source: §IV · p. 6

V. CONCLUSION

The paper proposes a linear influence network model for interdependence in security assets and vulnerabilities and formulates an Attacker–Defender game using zero-sum stochastic game theory. Its solution characterizes rational attacker behavior and offers IDS resource-allocation guidelines; the authors identify nonzero-sum games and incomplete information as research directions.

V. CONCLUSION

  • The proposed linear influence network model represents interdependence among nodes in both security assets and vulnerabilities.The paper’s initial game formulation uses zero-sum stochastic game theory.Source: §V · p. 7
  • The optimal solution helps characterize rational attacker behavior and provides IDSs with guidelines for allocating resources.The authors also note that linear influence network models facilitate solving security games with software programs.Source: §V · p. 7
  • The authors identify nonzero-sum stochastic games and games with incomplete information as directions for future research.These directions address more flexible payoff formulations and settings where neither player fully knows the network and its correlations.Source: §V · p. 7
Loading 1003.2440v1…