Abstract
This work addresses the practical challenge of quantifying system risk by evaluating attacker capabilities in terms of the safety requirements they can compromise. To avoid the computational redundancy of checking multiple properties individually, we propose an efficient coalgebraic model checking approach using enhanced coinduction. Applied to a real-world water treatment system, our method significantly reduces the state space exploration required for security verification.
Introduction
In security engineering, quantifying an attacker's threat level is often reduced to a list of their tools or access levels. However, a more impactful metric is the set of safety invariants an attacker can actually violate. In complex Cyber-Physical Systems (CPS), verifying hundreds of properties against various attacker models using traditional methods is computationally prohibitive due to redundant state space exploration. This paper introduces a formal framework to quantify attacker capability efficiently by leveraging the mathematical structure of the system.
Methodology: Coalgebraic Model Checking
The proposed approach moves beyond standard state-transition models to $F$-coalgebras, which are well-suited for systems with infinite behavioral streams. This framework allows for a more generalized treatment of system behaviors and properties.
The core of our methodology is the Verify algorithm, which optimizes property checking through two primary mechanisms:
- Enhanced Coinduction: By constructing a "precongruence closure," the algorithm can infer whether a state satisfies a property based on existing knowledge of other states or properties, rather than re-verifying from scratch.
- Algebraic Operators: We define operators (e.g.,
shift,add,swap) that capture system symmetries and physical laws. For instance, in a CPS, the relationship between water level and pressure allows the algorithm to infer violations of one property from another.
Evaluation and Results
The efficiency of the algorithm was evaluated across three scenarios:
- Synthetic Combination Lock: In a test with 10,000 safety properties, the algorithm successfully inferred the status of 9,046 properties (over 90%) using algebraic operators, demonstrating massive reductions in manual checking.
- BEEM Benchmark: Using a "swap" operator to exploit process symmetry in a concurrent puzzle reduced the explored state space and computation time by nearly 50%.
- Secure Water Treatment (SWaT) Testbed: In a real-world water treatment plant model, the method distinguished between Surge, Bias, and Stealthy attacks. It formally proved that "Stealthy" attackers are more capable as they can violate critical level and pressure requirements while remaining undetected by standard alarms.
Conclusion
By defining a formal "less capable" relation based on the set of violated properties, we provide a rigorous ranking for security threats. The primary innovation lies in knowledge reuse; by treating verification as a holistic task rather than isolated checks, we can prune the search space using physical invariants and symmetries. While the effectiveness depends on the selection of appropriate algebraic operators, the results indicate a significant leap in the feasibility of large-scale security verification for industrial control systems.
Summary updated