Design of attack tolerant detection topologies for distributed systems
Sam Nazari, Bahram Shafai, Amirreza Oghbaee · 2017
Let G = (VG,εG) be a network consisting of n agents such that kH, εH) be a subgraph within G consisting of agents equipped with detection filters to identify intrusions by malicious agents. Assume that G is also under attack from an external adversary whose goal is to disconnect the largest set of vertices in H by sabotaging ϵ fraction of its edge set, leaving the detection filters unable to sense intrusions from malicious agents. This paper establishes the algebraic and combinatorial conditions under which H is maximally robust to attacks from external adversaries. It is shown that the combinatorial problem of extracting a robust topology for H can be formulated as an optimization problem involving the Laplacian spectrum of G. An algorithm is given to recover the desired topology with the property that after an e fraction of the edges are adversarially removed, the network still maintains a connected component that spans at least (1 -ϵ/2φ) fraction of the vertices, with φ denoting the conductance of G. For the class of similar graphs that are cospectral, we also relate the algebraic connectivity to the third moment of the adjacency matrix of G, paving the way for alternative means of obtaining H instead of the spectral approach.