On the Fragility of Network Security Verification in Rare-Observation Regimes*

This paper develops a conceptual framework for network security verification, and provides an understanding of the inherent difficulties that arise due to two phenomena: (a) incomplete information, e.g., due to observation noise, and (b) rare observations, e.g., those triggered by an attack or very low probability failures. A Hidden Markov Model (HMM) is adopted as an abstraction of the network dynamics and information structure. It is shown that due to incomplete state information, certain rare observations can completely overhaul strong prior beliefs about the states of the network. In particular, certain rare observations may lead to situations in which the entropy of the best estimate of the past (or current) states becomes unacceptably large. Furthermore, these phenomena can occur even when the noise in sensory information is arbitrarily small. Simulation results over random, random regular, and scale free networks highlight remarkable similarities in patterns of emergence of fragility across different network topologies. These results are relevant for security applications such as intrusion detection, failure recovery and digital forensics in complex networks and cyber-physical systems.