Synthesis of Sensor Deception Attacks at the Supervisory Layer of Cyber-Physical Systems

1 Introduction

• The paper targets sensor-deception attacks that manipulate measurements received by the supervisor to drive a CPS toward a prespecified unsafe state.The motivation is the potential for undesired CPS behavior to damage physical systems or people relying on them.Source: §1 · pp. 1–2
• Unlike Su (2018), the approach does not require a normality condition to create an attack strategy and considers two additional attack models beyond bounded sensor deception.Su (2018) imposes normality when obtaining the supremal controllable and normal language under its attack model.Source: §1 · p. 2
• Wakaiki et al. (2018) study observability with an assumed attack model, while earlier discrete-event intrusion work models attackers as faulty behavior and uses fault diagnosis.Robust supervisory-control work did not study robustness against attacks, while opacity and privacy work focused on information release rather than effects on physical components.Source: §1 · p. 2
• The attacker is assumed to know the system and supervisor, observe system events, and alter sensor information received by the supervisor.The paper assumes a discrete abstraction of the underlying CPS so it can use discrete-event-system supervisory-control techniques.Source: §1 · pp. 1–2
• The Insertion-Deletion Attack structure (IDA) models supervisor–environment interaction and represents stealthy scenarios from which successful attack strategies can be extracted.The environment comprises the system and attacker, and IDAs support three attack types.Source: §1 · p. 2
• The paper frames its synthesis framework as a way for CPS engineers to detect and address potential vulnerabilities in control systems.Its approach is inspired by prior discrete structures for modeling game-like interactions.Source: §1 · p. 2

2 Supervisory control system model

• A finite-state automaton G is a tuple of states, events, a partial transition function, and an initial state; its generated language contains strings executable from that initial state.The model assumes the CPS has already been abstracted as a discrete transition system.Source: §2 · p. 2
• The active events ΓG(S) are the events enabled at at least one state in the subset S.For a single state x, the notation ΓG(x) abbreviates ΓG({x}).Source: §2 · p. 2
• The event set is partitioned into controllable and uncontrollable events, and admissible supervisor decisions must always include every uncontrollable event.The uncontrolled language L(G) contains all possible executions of G.Source: §2 · p. 3
• The supervisor dynamically enables or disables controllable events to enforce safety, while observable and unobservable events are separated to model limited sensing.The supervisor is modeled as a partial-observation function and may be realized as a deterministic automaton.Source: §2 · p. 3
• Fig. 1 presents a system automaton together with its supervisor.The model also defines unobservable reach, observable next states, and string-prefix notation for subsequent development.Source: Figure 1 · p. 3, §2 · p. 3

3.1 The general attack model

• The attacker observes system events and can insert fictitious events or delete legitimate readings from compromised sensor channels.The editable event set Σa is a subset of observable events, and the attack function is nondeterministic.Source: §3.1 · pp. 3–4

3.2 The controlled behavior under sensor deception attack

• The controlled behavior accounts for supervisor decisions on edited observations and plant execution of unobservable events enabled by those decisions.The attacker’s possible edits can produce nondeterministic supervisor decisions, which the analysis handles through a deterministic part of the induced supervisor.Source: §3.2 · p. 4

3.3 Attacker objectives

• The attacker seeks to reach a critical unsafe state while keeping the supervisor’s received strings within normal controlled behavior.A strong attack guarantees critical-state reachability; a relaxed version requires that a critical state could be reached.Source: §3.3 · p. 5, §3.4 · p. 6

3.4 Problem formulation

• The synthesis problem requires an admissible attack that remains stealthy and makes a critical state reachable, either surely or possibly.The attacker is assumed to know the plant and supervisor models; the paper frames this as a worst-case scenario.Source: §3.4 · pp. 5–6

3.5 Attack scenarios

• Three application-dependent attack functions distinguish unbounded, bounded, and interruptible modifications.The unbounded scenario lets the attacker finish any modification before the system executes an event; the bounded scenario limits modifications, while the interruptible scenario allows the system to interrupt at any point.Source: §3.5 · p. 6

4.1 Definition

• An IDA is a bipartite game structure whose supervisor and environment states each track the system’s state estimate and the supervisor’s state.The supervisor selects a control decision at an S-state; the environment selects an observable event at an E-state.Source: §4.1 · pp. 6–7
• Environment-to-supervisor transitions represent unaltered system events, attacker insertions, or attacker deletions, subject to the IDA’s transition constraints.Insertions must be consistent with the supervisor’s control decision; deletions apply only to actual observable events generated by the system.Source: §4.1 · p. 7
• A race-free IDA lets the attacker wait for the system’s response before deciding whether to pass through or suppress an event.Without race-freedom at an E-state, an insertion must occur before the system responds to the latest control decision.Source: §4.1 · p. 8
• An embedded attack function needs to cover modified strings consistent with controlled system behavior, and the IDA tracks the supervisor state and possible system states after those strings.The definition does not require the attack function to specify behavior outside the controlled behavior.Source: §4.1 · p. 8

5 All Insertion-Deletion Attack Structure

• The AIDA is a specific IDA that embeds all insertion and deletion actions available to the attacker for a given system, supervisor, and compromised-event set.It is constructed to be as large as possible while retaining the stated conditions.Source: §5 · p. 8, §5.1 · p. 8

5.1 Definition

• The AIDA is the largest IDA satisfying conditions that prevent races and stop exploration after attack detection or when the attacker’s goal is reached.The definition also requires an available intact or deleted-event transition for relevant observable events.Source: §5.1 · p. 8

5.2 Construction

• Construct-AIDA uses breadth-first search to enumerate reachable supervisor and environment states, and Theorem 14 establishes that it correctly constructs the AIDA.Search stops at a supervisor dead state or when an environment state’s system estimate is a subset of Xcrit; the AIDA has at most 2|X|+1|Q̃| states, or 2|X||Q̃| when Σuo = ∅.Source: §5.2 · p. 9

6.1 Pruning Process

• Pruning removes states where the supervisor reaches dead and enforces race-freeness at every E-state, yielding a race-free stealthy IDA.The modified algorithm has quadratic worst-time complexity in the number of Atrim states.Source: §6.1 · pp. 9–10
• The ISDA embeds all possible interruptible stealthy insertion-deletion attack strategies for the specified compromised events, supervisor, and system.A qualifying attack is embedded in the ISDA, and an attack constructed from it satisfies stealthiness; admissibility may require an extension.Source: §6.1 · p. 10

6.2 Synthesis of Stealthy Interruptible Functions

• Theorem 21 characterizes strong attacks by an E-state whose possible system states are all critical, and weak attacks by one with at least one critical state.The conditions are necessary and sufficient for synthesizing interruptible attack functions.Source: §6.2 · p. 10
• The synthesis algorithm finds a shortest path to a qualifying critical state, then expands the function to satisfy admissibility.In Example 22, defining the function only along the shortest path is inadmissible; added definitions for off-path strings make it admissible.Source: §6.2 · p. 11
• The ISDA represents the solution space, while the presented extraction algorithm is only one way to select an interruptible function.The paper does not focus on synthesizing minimally invasive strategies, defined as using the fewest edits to reach a critical state.Source: §6.2 · p. 11

7 Other Attack Scenarios

• The paper modifies the pruning and path-expansion procedures for the two remaining attack functions, with changes reflecting each function’s assumptions.The synthesis algorithms are omitted because they are similar to Algorithm 3.Source: §7 · p. 11

7.1 Deterministic Unbounded Attacks

• For deterministic unbounded attacks, insertions may continue before the system reacts, so the pruned IDA need not be race-free.The modified pruning procedure relaxes controllability and race-free conditions, flags states, and permits only insertions from flagged states.Source: §7.1 · p. 11
• The USDA embeds all possible deterministic unbounded stealthy insertion-deletion attack strategies for the specified compromised events, supervisor, and system.The paper states corresponding embedding and stealthiness results for this attacker type.Source: §7.1 · pp. 11–12

7.2 Deterministic Bounded Attacks

• The BAIDA tracks modifications already made so bounded attacks can respect their edit limit, combining interruptible behavior at the limit with unbounded behavior before it.The authors omit a separate structure definition and the corresponding lemmas and theorems, leaving those details to the reader.Source: §7.2 · p. 12

• The attacker is a nondeterministic edit function that reacts to plant outputs and its previous edits while ensuring stealthiness.Source: §8 · p. 12
• The game-based solution constructs an AIDA that captures the environment–supervisor game and embeds all valid attacker actions.Source: §8 · pp. 12–13
• Pruning the AIDA for each attack type yields stealthy ISDA and USDA structures for synthesizing an attack function that reaches unsafe critical states undetected, if one exists.Source: §8 · p. 13
• Future work will investigate modifying susceptible supervisors and directly designing supervisors robust to deception attacks.Source: §8 · p. 13

• The proof uses induction on the length of sA.Source: Proof of Lemma 12 · p. 13
• Across an IDA transition from an S-state to an E-state, the supervisor state is unchanged because it receives no observable event.Source: Proof of Lemma 12 · p. 14
• The induction hypothesis assumes the stated relation for indices i in N_k when k is less than n, followed by an induction step at k + 1.Source: Proof of Lemma 12 · p. 14

• The algorithm’s construction directly establishes conditions 1 and 2; the proof then establishes maximality by contradiction.Source: Proof of Theorem 14 · p. 14
• Assuming a larger valid IDA leads to a contradiction whether it adds transitions among the same states or adds states.Source: Proof of Theorem 14 · p. 14
• An exhaustive breadth-first search cannot omit a transition when all states are covered, and any additional reachable state would prevent the algorithm from converging to A.Source: Proof of Theorem 14 · p. 14

Proof of Lemma 18

• A stealthy admissible interruptible attack omitted from the ISDA must either lack a valid AIDA transition or be removed by Algorithm 2.A missing transition can mean the attacker inserted an event disallowed by the supervisor, violating stealthiness; pruning removes strategies that are non-stealthy, non-interruptible, or inadmissible.Source: Proof of Lemma 18 · p. 14

Proof of Lemma 19

• The proof of Lemma 19 follows directly from the ISDA construction.Source: Proof of Lemma 19 · p. 14

Proof of Theorem 20

• The proof of Theorem 20 follows from Lemmas 18 and 19.Source: Proof of Theorem 20 · p. 14

Proof of Theorem 21

• The proof of Theorem 21 follows from Theorem 20.Source: Proof of Theorem 21 · p. 14