A Scalable Decomposition Method for the Dynamic Defense of Cyber Networks

We investigate the problem of defending a cyber network against progressive attacks from an adversary. The defender is unable to perfectly observe attacks and the network’s security status and instead must use its imperfect observations to determine a defense strategy. The nature of the defender’s imperfect information is assumed to be non-probabilistic. Thus, the defender takes a conservative (minmax) approach to defending the network, attempting to construct a defense policy that minimizes the worst-case damage. Determining an optimal minmax defense strategy proves to be computationally intractable even for small-scale networks. To address this dimensionality issue, we propose a scalable decomposition method which involves the construction of multiple local defense problems, each equipped with a corresponding local defense policy. The local defense policies communicate information with one another with the goal of achieving network-wide security. The local defense problem’s construction is based on a decomposition of the network into clusters. For the decomposition, we use the notion of an influence graph to describe the dependencies among the security states of the network’s nodes. These dependencies, along with the available computational capability, are used to determine clusters of nodes, with each cluster corresponding to a local defense problem. After clusters are specified, we design the information structure of the network, that is, the information each local defense problem has over time to defend its own cluster; this information includes the data the local defense problem gathers from the environment along with the data communicated by other local defense policies. We illustrate the decomposition methodology with an example.