Quantifying Attacker Capability Via Model Checking Multiple Properties (Extended Version)

Eric Rothstein Morris, Jun SunarXiv 2018 · OpenReview

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.

Coalgebraic framework for model checking

The core of our methodology is the Verify algorithm, which optimizes property checking through two primary mechanisms:

  1. 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.
  2. 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.
The Verify algorithm utilizing enhanced coinduction

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

Abstract

This work aims to solve a practical problem, i.e., how to quantify the risk brought upon a system by different attackers. The answer is useful for optimising resource allocation for system defence. Given a set of safety requirements, we quantify the attacker capability in terms of the set of safety requirements an attacker can compromise. Given a system (in the presence of an attacker), model checking it against each safety requirement one by one is expensive and wasteful since the same state space is explored many times. We thus propose model checking multiple properties efficiently by means of coalgebraic model checking using enhanced coinduction techniques. We apply the proposed technique to a real-world water treatment system and the results show that our approach can effectively reduce the effort required for model checking.
BibTeX
@misc{morris2018quantifying,
  author = {Eric Rothstein Morris and Jun Sun},
  title = {{Quantifying Attacker Capability Via Model Checking Multiple Properties (Extended Version)}},
  year = {2018},
  eprint = {1811.10400},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.10400},
}
Figure