Optimal Detection for Bayesian Attack Graphs Under Uncertainty in Monitoring and Reimaging

Bayesian attack graphs (BAGs) are powerful models to capture the time-varying progression of attacks in complex interconnected networks. Network elements are modeled by graph nodes, and connections among components are represented through edges. The nodes take binary values, representing the compromised and uncompromised state of the network components. BAGs also offer a probabilistic representation of the likelihood of external and internal attacks progressing through exploit probabilities. The accuracy and timely detection of attacks are the main objectives in the security analysis of networks modeled by BAGs. This can ensure network safety by identifying network vulnerabilities and designing better defense strategies (e.g., reimaging devices, installing firewalls, changing connections, etc.). Two main challenges in achieving accurate detection in complex networks are 1) the partial monitoring of the network components due to the limited available resources and 2) the uncertainty in identifying and removing some compromises in the network due to the ever-evolving complexity of attacks. For a general class of BAGs, this paper presents an optimal minimum mean square error (MMSE) attack detection technique with arbitrary uncertainty in the monitoring and reimaging process. As with the Kalman filtering approach used for linear Gaussian state-space models, the derived solution exhibits the same optimality. A recursive matrix-form implementation of the proposed detection method is introduced, and its performance is examined through numerical experiments using a synthetic BAG.