Systematic Classification of Attackers via Bounded Model Checking

Eric Rothstein Morris, Jun Sun, Sudipta ChattopadhyayVMCAI 2019 · OpenReview

Abstract

In this work, we study the problem of verification of systems in the presence of attackers using bounded model checking. Given a system and a set of security requirements, we present a methodology to generate and classify attackers, mapping them to the set of requirements that they can break. A naive approach suffers from the same shortcomings of any large model checking problem, i.e., memory shortage and exponential time. To cope with these shortcomings, we describe two sound heuristics based on cone-of-influence reduction and on learning, which we demonstrate empirically by applying our methodology to a set of hardware benchmark systems.

1. Introduction

Security is not an absolute property; it is inherently defined against a specific attacker model. For instance, a cryptographic protocol may be deemed secure if an adversary can only observe encrypted traffic, yet it becomes vulnerable if the adversary gains control over a private key. In the context of complex hardware systems—modeled as And-Inverter Graphs (AIGs)—the number of potential attacker models is astronomical. For a system with $n$ components, there are $2^n$ possible sets of components an attacker might control.

Manually verifying every combination to determine if it violates a security requirement (e.g., "the secret key must never be exposed on this wire") is computationally infeasible. System designers require a systematic method to identify the "security frontier": the minimal set of compromised components that allow an attacker to succeed.

2. Methodology

We treat attacker classification as a formal verification problem using Bounded Model Checking (BMC). The system equations are modified to allow an attacker to "hijack" specific components, overriding their functional behavior with arbitrary values at any time step.

Figure 1: Hardware system model illustrating components (w, g, v) and security requirements (r). The model allows for the systematic injection of attacker control into specific nodes.

To navigate the exponential search space of $2^n$ attackers, we introduce two primary heuristics:

2.1 Isolation (Cone-of-Influence)

If a component is logically disconnected from a specific security requirement—meaning it lies outside the requirement's "Cone of Influence"—an attacker controlling that component cannot influence that requirement. This allows the methodology to immediately prune irrelevant attackers from the search space.

2.2 Monotonicity and Minimal Attackers

The core insight of this work is the property of monotonicity. If a "weak" attacker (controlling a set of components $A$) can break a requirement, then any "stronger" attacker (controlling a superset $A \cup B$) can also break it. Conversely, if a strong attacker cannot violate a requirement, no subset of their controlled components can either.

Figure 2: A lattice representation of the attacker space. Monotonicity allows the tool to classify entire branches of the lattice as 'safe' (green) or 'unsafe' (red) based on a few key checks.

By focusing on finding Minimal Successful Attackers, we can definitively classify the status of all "stronger" attackers automatically, significantly reducing the number of required BMC calls.

3. Experimental Evaluation

The methodology was evaluated using standard hardware verification benchmarks, including 230 instances from the Hardware Model-Checking Competition (HWMCC). A primary case study involved the pdtvsarmultip benchmark, which consists of 130 latches and over 2,700 gates, representing a search space of $2^{130}$ potential attackers.

Key Results

  • Efficiency: The combination of Isolation and Monotonicity heuristics consistently outperformed naive brute-force methods.
  • Coverage: In the pdtvsarmultip case study, the tool classified nearly 98% of the possible attacker space for specific requirements within 30 time steps.
  • Performance Trade-offs: While Isolation prunes the search space, its removal occasionally allowed the SAT solver to reuse internal knowledge more effectively, though it generally increased average classification time per requirement.

4. Discussion and Limitations

While the methodology is highly effective, it faces the "state explosion" problem common in BMC. As the number of time steps ($t$) increases, the complexity of solving the resulting SAT formulas can grow exponentially. Furthermore, because BMC is bounded, the results are "sound" but "incomplete": if an attack is found, it is valid, but the absence of an attack within $t$ steps does not guarantee security for $t+1$.

Future work will explore causality analysis to further refine the search for minimal attackers by reducing large successful attacks to their necessary components, rather than building them up from scratch.

Summary updated

Abstract

In this work, we study the problem of verification of systems in the presence of attackers using bounded model checking. Given a system and a set of security requirements, we present a methodology to generate and classify attackers, mapping them to the set of requirements that they can break. A naive approach suffers from the same shortcomings of any large model checking problem, i.e., memory shortage and exponential time. To cope with these shortcomings, we describe two sound heuristics based on cone-of-influence reduction and on learning, which we demonstrate empirically by applying our methodology to a set of hardware benchmark systems.
BibTeX
@inproceedings{morris2019systematic,
  author = {Eric Rothstein Morris and Jun Sun and Sudipta Chattopadhyay},
  title = {{Systematic Classification of Attackers via Bounded Model Checking}},
  booktitle = {VMCAI},
  year = {2019},
  url = {https://openreview.net/forum?id=GBkMRQykjz},
}
Figure