Verification of Probabilistic Security Systems

Critical digital infrastructure is increasingly threatened by attacks such as payment fraud, data breaches, and ransomware. Formal methods have been developed to rigorously analyse security protocols, which are the backbone of current digital security. Notably, automated tools, such as ProVerif, have been vital in analysing real-world protocols including TLS and Signal.A significant limitation in current formal methods stems from abstracting probabilistic behaviours to simplify the analysis. This leads to oversights in cases involving non-negligible probabilities, such as reasoning about distance-bounding protocols and electronic voting. Meanwhile probabilistic verification has been an active field for the past two decades, particularly in relation to cyber-physical systems and network protocols. Verification of security systems does not yet benefit from these advances, yielding a significant blind spot: modern security protocols with probabilistic behaviours and complex threat models remain vulnerable to undetected security flaws.The VePaSS project aims to build new interdisciplinary connections between security, games and symbolic computation, to address the ambitious goal of verifying probabilistic security systems. The primary challenge in such an integration is that algorithmic game theory has predominantly concentrated on finite stochastic games, whereas security protocols, when represented symbolically, are inherently infinite. We seek to leverage recent breakthroughs in countable stochastic games and symbolic computation to develop a unified model and to design decision procedures and practical tools for the automatic verification of complex stochastic protocols such as electronic voting and distance-bounding protocols. The project has a strong scientific impact by addressing open problems in verification and symbolic computation, economic impact by enhancing the security of digital systems, and societal impact through its work on electronic voting.