Robust Satisfaction of Metric Interval Temporal Logic Objectives in Adversarial Environments

Luyao Niu, Bhaskar Ramasubramanian, Andrew Clark, Radha Poovendran

TL;DR

This paper introduces "durational stochastic games" (DSGs) to model cyber-physical systems (CPSs) facing adversaries that can attack both system inputs and timing information. They propose methods to synthesize robust controllers that ensure time-critical tasks, specified using metric interval temporal logic (MITL), are met even under these sophisticated attacks, demonstrated on a traffic network.

What Problem Does This Paper Address?

Cyber-physical systems (CPSs) often need to perform complex, time-sensitive tasks. Specifying these tasks and ensuring their reliable execution in the face of adversaries is a significant challenge. Traditional models for adversarial interactions, like stochastic games (SGs), don't account for the crucial element of time, making them unsuitable for time-critical objectives. Furthermore, adversaries can be more sophisticated than just manipulating system inputs; they can also tamper with the timing information that the CPS relies on, creating a "timing attack." This paper addresses the problem of synthesizing controllers for CPSs that can guarantee the satisfaction of time-critical objectives (expressed in MITL) even when an adversary can launch both "actuator attacks" (manipulating inputs) and "timing attacks" (manipulating perceived time).

Methods

The core contribution is the introduction of Durational Stochastic Games (DSGs), which extend traditional SGs by incorporating the time taken for state transitions. This allows for the modeling of time-critical objectives. The authors define three notions of robustness:

  • Spatial Robustness: Measures how much a system's non-temporal behavior can be perturbed without violating the objective.
  • Temporal Robustness: Quantifies the maximum allowable perturbation in timing without violating the objective.
  • Spatio-Temporal Robustness: A unified measure that combines spatial and temporal perturbations.

For scenarios where the adversary only launches actuator attacks, they develop algorithms to compute controllers that guarantee a desired level of spatio-temporal robustness. When the adversary can launch both actuator and timing attacks, the problem becomes harder because the CPS cannot accurately assess its temporal robustness. In this case, they relax the robustness constraint and propose a value iteration-based approach to compute a finite-state controller that maximizes the probability of satisfying the MITL objective. They also introduce the concept of a Finite-State Controller (FSC) to handle the uncertainty introduced by timing attacks.

Datasets

Not discussed in the paper. The paper uses a simulated signalized traffic network as a case study.

Key Insights and Ideas

  • Time is Crucial for Adversarial CPS: Traditional game models are insufficient for time-critical CPSs; explicitly modeling transition durations is essential.
  • Timing Attacks are a New Frontier: Adversaries can exploit the timing information perceived by CPSs, making robust control significantly more challenging.
  • Robustness is Multi-faceted: Simply ensuring a task is completed isn't enough; understanding how much it can be perturbed in space and time without failing is key.
  • Finite-State Controllers for Timing Uncertainty: When timing information is unreliable, a finite-state controller can help the CPS track its state and detect potential attacks.
  • Trade-off in Timing Attacks: When timing attacks are present, the goal shifts from guaranteed robustness to maximizing the probability of success.

Key Results

The paper presents algorithms for computing spatial, temporal, and spatio-temporal robustness. For actuator-only attacks, they can synthesize controllers that guarantee spatio-temporal robustness. In the presence of both actuator and timing attacks, they demonstrate a value iteration approach to maximize the probability of satisfying MITL objectives.

In their case study on a signalized traffic network:

  • For actuator-only attacks, their Algorithm 4 computed a policy in 264 seconds.
  • For actuator and timing attacks, their Algorithm 5 computed a policy in 720 seconds.
  • In the timing attack scenario, their approach achieved probabilities of satisfying MITL specifications of 0.7000, 0.6857, and 0.4390 for three different objectives, outperforming baselines that had zero probability of success.

Limitations and Future Work

  • Partial Observability: The current work assumes full observability of the system state. Future work aims to generalize DSGs to address partial observations by the CPS and adversary.
  • Non-rational Adversaries: The current model assumes the adversary always plays its best response. Future work will investigate scenarios where the adversary might not be rational.
  • Scalability: While algorithms are presented, their computational complexity might be a concern for very large systems. The paper mentions the complexity of their algorithms in terms of state and transition counts.
  • General MITL: The work focuses on MITL fragments representable by deterministic timed Büchi automata. Generalizing to arbitrary MITL formulae would be a significant extension.

Summary updated

Abstract

This paper studies the synthesis of controllers for cyber-physical systems (CPSs) that are required to carry out complex time-sensitive tasks in the presence of an adversary. The time-sensitive task is specified as a formula in the metric interval temporal logic (MITL). CPSs that operate in adversarial environments have typically been abstracted as stochastic games (SGs); however, because traditional SG models do not incorporate a notion of time, they cannot be used in a setting where the objective is time-sensitive. To address this, we introduce durational stochastic games (DSGs). DSGs generalize SGs to incorporate a notion of time and model the adversary’s abilities to tamper with the control input (actuator attack) and manipulate the timing information that is perceived by the CPS (timing attack). We define notions of spatial, temporal, and spatio-temporal robustness to quantify the amounts by which system trajectories under the synthesized policy can be perturbed in space and time without affecting satisfaction of the MITL objective. In the case of an actuator attack, we design computational procedures to synthesize controllers that will satisfy the MITL task along with a guarantee of its robustness. In the presence of a timing attack, we relax the robustness constraint to develop a value iteration-based procedure to compute the CPS policy as a finite-state controller to maximize the probability of satisfying the MITL task. A numerical evaluation of our approach is presented on a signalized traffic network to illustrate our results.
BibTeX
@inproceedings{niu2023robust,
  author = {Luyao Niu and Bhaskar Ramasubramanian and Andrew Clark and Radha Poovendran},
  title = {{Robust Satisfaction of Metric Interval Temporal Logic Objectives in Adversarial Environments}},
  booktitle = {Games},
  year = {2023},
  url = {https://openreview.net/forum?id=zet07NdLq1},
}
Figure