Synthesis of covert actuator attackers for free

In this paper, we shall formulate and address a problem of covert actuator attacker synthesis for cyber-physical systems that are modeled by discrete-event systems. We assume the actuator attacker partially observes the execution of the closed-loop system and is able to modify each control command issued by the supervisor on a specified attackable subset of controllable events. We provide straightforward but in general exponential-time reductions, due to the use of subset construction procedure, from the covert actuator attacker synthesis problems to the Ramadge-Wonham supervisor synthesis problems. It then follows that it is possible to use the many techniques and tools already developed for solving the supervisor synthesis problem to solve the covert actuator attacker synthesis problem for free. In particular, we show that, if the attacker cannot attack unobservable events to the supervisor, then the reductions can be carried out in polynomial time. We also provide a brief discussion on some other conditions under which the exponential blowup in state size can be avoided. Finally, we show how the reduction based synthesis procedure can be extended for the synthesis of successful covert actuator attackers that also eavesdrop the control commands issued by the supervisor.

1. There is in fact an exception. In sensor insertion scenario, Carvalho et al. (2018) assumes the attacker knows the model of the supervisor.

2. The supervisor could be designed in such a way that either every disabled event is non-attackable, which makes (enablement) attack impossible, or every disabled attackable event cannot bring the system to damage, which makes attack futile.

3. We write δ(q, σ)! to mean δ(q, σ) is defined and write ¬δ(q, σ)! to mean δ(q, σ) is undefined. As usual, δ is naturally extended to the partial transition function \(\delta : Q \times {\varSigma }^{*} \rightarrow Q\) such that, for any q ∈ Q, any s ∈ Σ^∗ and any σ ∈ Σ, δ(q, 𝜖) = q and δ(q, sσ) = δ(δ(q, s), σ). We define \(\delta (Q^{\prime } ,\sigma )=\{\delta (q, \sigma ) \mid q \in Q^{\prime }\}\) for any \(Q^{\prime }\subseteq Q\).

4. This assumption may be removed, by imposing the constraint that the attacker does not change its attack decision whenever σ ∈ Σ_uo is executed in the plant, even when the execution of σ may be observed by the attacker, if σ ∈ Σ_uo ∩ Σ_{o, A}, and thus may lead to state change in the attacker. The analysis of this general case is left to the future work.

5. The supervisor is not sure whether σ has been disabled by an attacker, even if disabling σ may result in deadlock, as the supervisor is never sure whether: 1) deadlock has occurred due to actuator attack, or 2) σ will possibly fire soon (according to the internal mechanism of the plant).

6. The requirement \({\varSigma }_{c, A} \subseteq {\varSigma }_{c}\) is not essential, as it is only used in Remark 2, i.e., used in the discussion of when the reduction can be carried out in polynomial time.

7. The relaxation of this requirement makes our synthesis approach incomplete in general.

8. In Lima et al. (2017), when the supervisor detects the presence of an attacker, all controllable events will be disabled, while uncontrollable events can still occur (i.e., immediate halt by reset is impossible). This is not difficult to accommodate, by working on the damage automaton H that defines the set of damage-inflicting strings L_m(H). In particular, if uncontrollable events can still occur after the detection, then we only need to use the new damage automaton \(H^{\prime }\) with \(L_{m}(H^{\prime })=L_{m}(H) \cup L_{m}(H)/{\varSigma }_{uc}^{*}\), where \(L_{m}(H)/{\varSigma }_{uc}^{*}:=\{s \in {\varSigma }^{*} \mid \exists s^{\prime } \in {\varSigma }_{uc}^{*}, ss^{\prime } \in L_{m}(H)\}\), as the renewed set of damage-inflicting strings. An alternative approach is to add self-loops of each uncontrollable event at the state x_halt of S^A and at the state \(\varnothing \) of \(P_{{\varSigma }_{o}}(S\lVert G)\) to allow execution of uncontrollable events after the detection; the definition of these two components will be explained soon.

9. The same monitoring mechanism indeed works for both covert attackers and risky attackers (Lin et al. 2019b).

10. Alternatively, we can use the equivalent set \(\{(q, x, D, y, w) \in Q \times (X \cup \{x_{halt}\}) \times 2^{X \times Q} \times Y \times W \mid D=\varnothing \wedge w \notin W_{m}\}\) for specifying the violation of covertness.

11. Theorem 1 requires the synthesis of a safe and nonblocking supervisor, while Theorem 2 only requires the synthesis of a safe and nonempty supervisor. The maximally permissive supervisor synthesis algorithm in Yin and Lafortune (2016) is of exponential time complexity and can be adapted for both scenarios.

12. In another setup (Lin et al. 2019b), the supervisor sends a control command each time when it fires an observable transition \(\zeta (x, \sigma )=x^{\prime }\) satisfying \(\varGamma (x) \neq \varGamma (x^{\prime })\). To solve the (covert) actuator attacker synthesis problem for this setup requires the concept of dynamic observation (Arnold et al. 2003) that is beyond the scope of this work.

This work is financially supported by Singapore Ministry of Education Academic Research Grant RG91/18-(S)-SU RONG (VP), which is gratefully acknowledged.

Authors and Affiliations

1. Electrical and Electronic Engineering, Nanyang Technological University, Singapore, Singapore

   Liyong Lin, Yuting Zhu & Rong Su

Corresponding author

Correspondence to Liyong Lin.

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article belongs to the Topical Collection: Smart Manufacturing - A New DES Frontier

Guest Editors: Rong Su and Bengt Lennartson

Reprints and permissions