# Pretending to Be Someone Else: A Stealth Sensor Attack on DES

Eric Fabre

► To cite this version:

Eric Fabre. Pretending to Be Someone Else: A Stealth Sensor Attack on DES. 2024. hal-04883298

HAL Id: hal-04883298

https://inria.hal.science/hal-04883298v1

Preprint submitted on 13 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Pretending to Be Someone Else :
A Stealth Sensor Attack on DES

Eric Fabre

*Abstract*— We consider attacks on discrete event systems where the aim of the attacker is to modify sensor readings produced by some plant $\mathcal{A}$ in order to lure an observer into believing that plant $\mathcal{B}$ is actually running. This setting captures numerous situations of interest: the attacker may want to prevent the detection by the observer of some specific event in plant $\mathcal{A}$ (e.g. prevent fault diagnosis). Or the attacker may wish to hide from a controller that plant $\mathcal{A}$ has entered some dangerous mode where a corrective action is needed. Or the attacker may want to fake that some behavior of $\mathcal{A}$ never occurs, making it appear as malfunctioning. It is shown that transducers offer the appropriate modeling formalism for such attacks, and directly lead to the arena where the attack design can be solved as a game. Successful and undetectable attacks can be obtained in polynomial time. Successful stealth attacks do not always exist. For stochastic plants $\mathcal{A}$, one can however build attack strategies that maximize chances of success.

## I. INTRODUCTION

The flexibility of networked systems comes at the price of a greater exposure to man-in-the-middle attacks. An attacker on communication channels may alter the sensor readings coming from a remote plant and/or the remote commands sent back to this plant, possibly driving it to dangerous behaviors. Several authors have addressed this problem in the setting of discrete event systems (DES), focusing mainly on closed-loop systems, and considering two perspectives. First, the defender standpoint, with the aim of synthesizing controllers robust to sensor reading attacks [6], [7], [9], [12] or to synthesize robust observers/diagnosers for open loop systems [11]. The general approach is to consider that sensor attacks add noise to the observable behavior of the plant, so controllers/observers should be robust to such an expansion of the plant (visible) language. Still on the defender side, other contributions have considered modeling and detecting attacks before trying to mitigate their effects [4], [5], and also on verifying the existence of vulnerabilities [10]. The complementary standpoint is of course that of the attacker, where the aim is to synthesize sensor attacks [8] that would go unnoticed. This is the topic of this paper.

Modeling systems under attack suggests a connection with game theory, and the existence of a finite arena where the role of the two players appears. Such arenas have been evidenced in [8], [9], [11], specifically with the introduction of the AIDA (all insertion/deletion attack structure). However, its derivation remains rather complex. This is due first to a modeling via synchronous products, which imposes complex event relabelings, and secondly to numerous

independent difficulties that blur the core of the problem: non-determinism of the plant, partial observations, uncontrollable events... We explore here a much simpler and natural approach for modeling attacks, relying on transducers, as in [6]. The setting is further simplified by focusing first on open-loop systems and assuming a fully observed and deterministic plant. The advantage is that the arena pops up very naturally, allowing one to define maximally permissive strategies that satisfy several nested objectives: complying with the allowed attack patterns (admissibility), remaining undetected (stealthiness), and achieving an attack goal (successfulness) expressed as preserving a regular property. It is shown that these three objectives correspond to a progressive/modular refinement of strategies, each step relying on part of the plant+attack+objective model. This approach better evidences the connection with game theory, which is illustrated by moving to stochastic games, for example to maximize chances for an attack to remain stealth or to reach its objective when no successful strategy exists.

## II. NOTATION AND PRELIMINARIES

The DES considered here are automata and their variants. A finite automaton $\mathcal{A} = (S, \Sigma, T, s_0)$ over the alphabet of actions $\Sigma$ is made of states $S$, initial state $s_0 \in S$ and transition set $T \subseteq S \times \Sigma \times S$. For transition $t = (s, \alpha, s') \in T$ we also denote $t^- = s$, $t^+ = s'$ and $\sigma(t) = \alpha$. AT places, $T$ is used as a transition (partial) function: $T(s, \alpha) = \{s' \in S : (s, \alpha, s') \in T\}$, which extends naturally to sets $T(S', \Sigma')$ by union. A path $u = t_1t_2...t_n$ is a sequence of transitions such that $t_i^+ = t_{i+1}^-$. By extension $u^+ = t_n^+$, $u^- = t_1^-$ and $\sigma(u) = \sigma(t_1)...\sigma(t_n)$. Path $u$ is a run of $\mathcal{A}$ if $u^- = s_0$. The set of runs of $\mathcal{A}$ is $R(\mathcal{A})$ and the language of $\mathcal{A}$ is $L(\mathcal{A}) = \sigma(R(\mathcal{A}))$. For simplicity here we do not assume marked or final states in $\mathcal{A}$. Equivalently, all states are accepting, so $L(\mathcal{A})$ is prefix closed. When necessary, we use subscripts to specify which automaton is referred, as in $S_{\mathcal{A}}$, $T_{\mathcal{A}}$ etc.

$\mathcal{A}$ is trim iff there exists a path from initial state $s_0$ to any $s \in S$. $\mathcal{A}$ is live iff $\forall s \in S, T(s, \Sigma) \neq \emptyset$, i.e. there is at least one transition originating from $s$. $\mathcal{A}$ is complete iff $\forall (s, \alpha) \in S \times \Sigma, T(s, \alpha) \neq \emptyset$, i.e. every action $\alpha$ is possible from every state $s$. $\mathcal{A}$ can be made complete by adding a dummy (absorbing) state $\perp$ to $S$ to which the missing transitions point. The completed automaton $\mathcal{A}^c = (S^c, \Sigma, T^c, s_0)$ is thus given by $S^c = S \cup \{\perp\}$ and $T^c = T \cup \{\perp\} \times \Sigma \times \{\perp\} \cup \{(s, \alpha, \perp) : T(s, \alpha) = \emptyset\}$. $\mathcal{A}$ is deterministic iff $\forall (s, \alpha) \in S \times \Sigma, |T(s, \alpha)| \le 1$, i.e. for each $\alpha \in \Sigma$ there is at most one transition labeled by $\alpha$ from any state $s$. $\mathcal{A}$ can be turned into an equivalent deterministic automaton $\mathcal{B} = \text{Det}(\mathcal{A})$ by

<footnote>E. Fabre is with Univ Rennes and with INRIA Rennes Bretagne Atlantique, France</footnote>
classical subset construction. Det($\mathcal{A}$) is also called a state estimator of $\mathcal{A}$, or the belief automaton of $\mathcal{A}$.

A morphism $\phi: \mathcal{A}_1 \to \mathcal{A}_2$ between automata $\mathcal{A}_i = (S_i, \Sigma_i, T_i, s_{i,0})$ is a pair of functions $(\phi_S, \phi_\Sigma)$, where $\phi_S: S_1 \to S_2$ and $\phi_\Sigma: \Sigma_1 \to \Sigma_2$, that preserves initial state $\phi_S(s_{1,0}) = s_{2,0}$ and transitions: $(s_1, \alpha, s'_1) \in T_1 \Rightarrow (\phi_S(s_1), \phi_\Sigma(\alpha), \phi_S(s'_1)) \in T_2$. Consequently, $\phi$ extends into a mapping from runs of $\mathcal{A}_1$ to runs of $\mathcal{A}_2$, and $\phi_\Sigma(L(\mathcal{A}_1)) \subseteq L(\mathcal{A}_2)$. If $\phi_\Sigma$ is the identity, $\phi$ is a simulation of $\mathcal{A}_1$ in $\mathcal{A}_2$.

We need to consider sensor attacks performing label trans-
formations. A natural model for such attacks is through the
notion of transducer. A transducer $\mathcal{P} = (S, (\Sigma_I, \Sigma_O), T, s_0)$ is
simply an automaton $(S, \Sigma, T, s_0)$ over alphabet $\Sigma = (\Sigma_I \cup$
$\{\varepsilon\}) \times (\Sigma_O \cup \{\varepsilon\}) \setminus \{(\varepsilon, \varepsilon)\}$, where $\varepsilon$ denotes the empty
label. $\Sigma_I$ is the input alphabet and $\Sigma_O$ the output alphabet.
Transitions are thus labeled by pairs $(\alpha, \beta)$ where $\alpha$ or $\beta$
can be the empty label $\varepsilon$, but not both. Automaton $\mathcal{A} =$
$(S, \Sigma, T, s_0)$ can be considered as a transducer $(S, (\Sigma, \Sigma), T, s_0)$
by duplicating transition labels. For run $u \in R(\mathcal{P})$, one has
$\sigma(u) = (w_1, w_2) \in \Sigma_I^* \times \Sigma_O^*$, which we denote as $\sigma_I(u) = w_1$
and $\sigma_O(u) = w_2$. The input language $L_I(\mathcal{P})$ is the restric-
tion of $L(\mathcal{P})$ to the input word, i.e. $L_I(\mathcal{P}) = \sigma_I(L(\mathcal{P}))$,
and similarly for the output language $L_O(\mathcal{P}) = \sigma_O(L(\mathcal{P}))$.
Transducer $\mathcal{P}$ may be completed by the addition of a dummy
state $\perp$ in order to accept $\Sigma_I^*$ as input language. $\mathcal{P}^c$ denotes
this completed transducer.

In the sequel, the notion of strategy focuses on the input
part of a transducer, through the following notions.

**Definition 1:** Input action $\alpha \in \Sigma_I$ is enabled at state $s$ in $\mathcal{P}$ if either there exists a transition $(s, (\alpha, \beta), s') \in T$ for some $\beta \in \Sigma_O \cup \{\varepsilon\}$, or there exists a transition $(s, (\varepsilon, \beta), s') \in T$, $\beta \in \Sigma_O$, and $\alpha$ is enabled at $s'$.

In other words, $\mathcal{P}$ can accept $\alpha$ from $s$, either directly or after a few output label insertions.

**Definition 2:** Transducer $\mathcal{P}$ is input deterministic iff $\forall s \in S$, if $\alpha \in \Sigma_I$ is enabled at $s$, there exists a unique path $t_1 \dots t_n$ in $\mathcal{P}$ such that $t_1^- = s$, $\sigma_I(t_1 \dots t_{n-1}) = \varepsilon$, $\sigma_I(t_n) = \alpha$.

Unless stated otherwise “deterministic” transducer refers to
“input deterministic” in the sequel.

**Definition 3:** State $s'$ in $\mathcal{P}$ is a stopping state if $\exists (s, (\alpha, \beta), s') \in T$ such that $\alpha \neq \varepsilon$.

Stopping states are points where the transducer can stop just
after accepting the last input symbol $(\alpha)$ and wait for the
next one. By extension, a stopped run $u = t_1 \dots t_n \in R(\mathcal{P})$ is
such that $\sigma_I(t_n) \neq \varepsilon$.

Transducers can be connected to one another, the output al-
phabet of the first one being used as the input alphabet of the
second one. This notion generalizes the synchronous (or par-
allel) product of automata. Let $\mathcal{P}_1 = (S_1, (\Sigma_1, \Sigma_2), T_1, s_{1,0})$,
$\mathcal{P}_2 = (S_2, (\Sigma_2, \Sigma_3), T_2, s_{2,0})$ be two transducers, their product
$\mathcal{P} = \mathcal{P}_1 \times \mathcal{P}_2 = (S, (\Sigma_1, \Sigma_3), T, s_0)$ is defined as $S = S_1 \times S_2$,
$s_0 = (s_{1,0}, s_{2,0})$ and for transitions

$$
\begin{align*}
& ((s_1, s_2), (\alpha, \gamma), (s'_1, s'_2)) \in T \\
\Leftrightarrow & \exists \beta \neq \varepsilon, (s_1, (\alpha, \beta), s'_1) \in T_1, (s_2, (\beta, \gamma), s'_2) \in T_2 \\
& \text{or } (s_1, (\alpha, \varepsilon), s'_1) \in T_1, s'_2 = s_2 \\
& \text{or } (s_2, (\varepsilon, \gamma), s'_2) \in T_2, s'_1 = s_1 \tag{1}
\end{align*}
$$

This construction can produce transitions labeled $(\alpha, \gamma) = (\varepsilon, \varepsilon)$. To comply with our definition, we assume the resulting transducteur is $\varepsilon$-reduced, by merging an epsilon transition with all its possible successors before removing it, and recursively until convergence. This situation does not occur here. Without loss of generality, we assume $\mathcal{P}$ is also trimmed. In the sequel, composite states like $(s_1, s_2)$ are sometimes called configurations. As automata can be considered as transducers, we might connect automata to transducers, and transducers to automata. Notice that definition (1) amounts to the usual synchronous product of automata $\mathcal{A}_1 \times \mathcal{A}_2$, with $\mathcal{A}_i = (S_i, \Sigma_i, T_i, s_{i,0})$, if $\mathcal{A}_i$ is mapped to a transducer over $\Sigma_1 \times (\Sigma_1 \cap \Sigma_2)$ and $\mathcal{A}_2$ to a transducer over $(\Sigma_1 \cap \Sigma_2) \times \Sigma_2$ (details are left to the reader).

III. ATTACK STRATEGIES ON OPEN LOOP SYSTEMS

Let plant $\mathcal{A} = (S, \Sigma, T, s_0)$ be modeled as a deterministic, live and fully observed automaton. We are mostly interested in the (visible) language of $\mathcal{A}$, so our model deliberately ignores both unobservable labels and non-determinism, although these ingredients could be reintroduced with minor technicalities (typically epsilon reduction of unobservable transitions and determinization). Liveness ensures that $\mathcal{A}$ can run forever and produces run $u = t_1 \dots t_n \dots$. The label sequence $\sigma(u) = \alpha_1 \dots \alpha_n \dots$ produced by $u$ corresponds to sensor readings that may for example feed a supervisor in a feedback loop enabling or disabling actions in $\mathcal{A}$ (see [9] for a definition of a supervised plant).

We model the sensor reading modifications allowed to the attacker as a transducer $\mathcal{P} = (X, \Sigma, \bar{\Sigma}, T_{\mathcal{P}}, x_0)$ over $(\Sigma, \bar{\Sigma})$, that we call the protocol. See Fig. 1 (center) for an example. The flexibility of transducers allows one to model the unaltered transmission of a sensor reading, as transition label $(\alpha, \bar{\alpha})$, but also its substitution as $(\alpha, \bar{\beta})$, its deletion as $(\alpha, \varepsilon)$, or even the insertion of a fake event as $(\varepsilon, \bar{\beta})$. We use overlined letters for the sake of clarity, in order to distinguish input from output symbols, although in practice one may of course consider $\bar{\Sigma} = \Sigma$. The fact that $\mathcal{P}$ has an internal state enables the modeling of constraints on possible attacks. For example insertions and deletions should alternate, or the number of deletions minus the number of insertions should remain within some range, to ensure that the pace of the output sequence does not drift away from the pace of the input sequence.

The goal of the attacker is to modify sensor readings
collected on $\mathcal{A}$, following protocol $\mathcal{P}$, in order to lure
an observer into believing that plant $\mathcal{A}' = (\bar{S}, \bar{\Sigma}, \bar{T}, \bar{s}_0)$ is
actually running, where $\mathcal{A}'$ is another live deterministic
automaton. In practice, $\mathcal{A}'$ might be a sub-automaton of $\mathcal{A}$.
The attacker thus wants to hide from an external observer
that some specific event occurred in $u$, or that a prefix $t_1 \dots t_n$
of $u$ satisfies some regular property, or that $u$ crossed some
specific state. Formally, this is a “safety” objective: the
attacker has to avoid bad configurations, as we illustrate in
the sequel. The attacker knows of course $\mathcal{A}$, $\mathcal{P}$ and $\mathcal{A}'$.

Fig. 1 illustrates this situation: the objective of the attacker
is to modify the words in $\{a, b, c\}^*$ produced by $\mathcal{A}$ to output
<figure><img src="image_2.png" /><figcaption>Fig. 1. Plant $\mathcal{A}$ (left), sensor attack transducer $\mathcal{P}$ (center) and target automaton $\tilde{\mathcal{A}}$ (right). Empty label is depicted as a dot. The dashed parts represent completion to enable any word as input. “?” stands for any letter.</figcaption></figure>

an alternation of $\bar{a}$ and $\bar{b}$, which amounts to hiding every crossing of state 3 in plant $\mathcal{A}$. The protocol allows to forward $a$ and $b$ at any time (they become $\bar{a}$ and $\bar{b}$ in our notation), but only $a$ or $c$ (in alternance) may be either erased or changed into $\bar{b}$. And some $\bar{b}$ may be inserted, but only at state 2 of the protocol.

### A. Attack strategy

Given input plant $\mathcal{A}$, attack protocol $\mathcal{P}$ and target behavior $\tilde{\mathcal{A}}$, let $\mathcal{P}^c$ and $\mathcal{A}^c$ be the completed transducers that accept respectively $\Sigma^*$ and $\tilde{\Sigma}^*$ as input languages. Consider transducer $M = \mathcal{A} \times \mathcal{P}^c \times \mathcal{A}^c$. Recall (Def. 3) that $(s, x, \bar{s}) \in S \times X \times \bar{S}$ is a stopping configuration of $M$ iff there exists some transition $t \in T$ in $M$ such that $\sigma_I(t) = \alpha \neq \varepsilon$, i.e. $(s, x, \bar{s})$ just follows the absorption of some input label $\alpha \in \Sigma$ produced by $\mathcal{A}$.

**Definition 4:** A strategy $\mathcal{S}$ for $(\mathcal{A}, \mathcal{P}, \tilde{\mathcal{A}})$ is a (trim) sub-transducer of $M = \mathcal{A} \times \mathcal{P}^c \times \tilde{\mathcal{A}}^c$ such that for every stopping configuration $(s, x, \bar{s}) \in S \times X \times \bar{S}$ of $\mathcal{S}$, and any input label $\alpha \in \Sigma$, if $\alpha$ is enabled at $(s, x, \bar{s})$ in $M$, then it is also enabled in $\mathcal{S}$.

Thus a strategy selects which label transforms remain enabled for an input label $\alpha$ chosen by $\mathcal{A}$, but it cannot block this label. Notice that the condition in Def. 4 only applies to stopping configurations, from which the next input label must be processed. A strategy may also have transient configurations, only accessible through transitions labeled by $(\varepsilon, \bar{\beta})$, i.e. with no input label.

**Proposition 1:** One has $L_I(\mathcal{S}) = L_I(\mathcal{M}) = L(\mathcal{A})$.

*Proof:* As $L_O(\mathcal{A}) = L(\mathcal{A}) \subseteq \Sigma^*$ and $\mathcal{P}^c$ accepts $\Sigma^*$ as input language, $L_I(\mathcal{A} \times \mathcal{P}^c) = L(\mathcal{A})$. Similarly $L_O(\mathcal{A} \times \mathcal{P}^c) \subseteq \tilde{\Sigma}^*$ and $\tilde{\mathcal{A}}^c$ accepts $\tilde{\Sigma}^*$ as input language, so $L_I(\mathcal{A} \times \mathcal{P}^c \times \tilde{\mathcal{A}}^c) = L_I(\mathcal{A} \times \mathcal{P}^c) = L(\mathcal{A})$. Not only $M$ accepts all input words produced by $\mathcal{A}$, but it is also non-blocking: any path taken to accept an input word in $L(\mathcal{A})$ can be extended to accept a suffix of that word. $\mathcal{S}$ being a sub-transducer of $M$, one has $L_I(\mathcal{S}) \subseteq L_I(\mathcal{M})$. But the restriction in the selection of edges of $M$ that remain in $\mathcal{S}$ actually ensures equality of input languages. $\mathcal{S}$ is also non-blocking. ■

Observe that the union of two strategies is a strategy, so there exists a maximal one, which coincides with $M$.

Fig. 2 illustrates the construction of $M$ for $\mathcal{A}$ and $\mathcal{P}$ in Fig. 1 but assuming $\tilde{\mathcal{A}}$ is a single state automaton accepting $\tilde{\Sigma}^*$. As $\tilde{\mathcal{A}}$ plays no part in the composition, it can be ignored and is not represented in the figure. One can check that $L_I(\mathcal{M}) = L(\mathcal{A})$. As a maximal strategy, $M$

<figure><img src="image_3.png" /><figcaption>Fig. 2. Transducer $\mathcal{A} \times \mathcal{P}^c$ connecting the first two elements of Fig. 1. Transitions following a configuration with a $\perp$ are not represented.</figcaption></figure>

enables three choices for processing input label $a$ in the initial configuration: transmission as $\bar{a}$, transform into $\bar{b}$, or deletion. Observe that no run is blocking (configurations following $(1, \perp)$ are not represented). However, some runs $u$ are not compatible with protocol $\mathcal{P}$, which is characterized by the fact that $u^+ = (s, \perp)$. Such strategies must be removed.

### B. Admissible and winning strategies

**Definition 5:** A strategy $\mathcal{S}$ for $(\mathcal{A}, \mathcal{P}, \tilde{\mathcal{A}})$ is admissible iff no configuration $(s, \perp, \bar{s})$ is reachable (included $\bar{s} = \perp$).

**Proposition 2:** Finding admissible strategies in $M$ can be solved in quadratic time (in the size of $M$).

*Proof:* This is a standard safety property which can be solved classically by backtracking from bad configurations $(s, \perp, \bar{s})$. If some transition $t$ of $M$ stops at a bad configuration, i.e. $\sigma_I(t) = \alpha \neq \varepsilon$ and $t^+$ is a bad configuration, then $t$ can not be part of an admissible strategy and must be removed. If for some configuration $(s, x, \bar{s})$ of $\mathcal{S}$, some input label $\alpha \in \Sigma$ was enabled in $M$ but is not enabled in the current pruning of $M$, then $(s, x, \bar{s})$ can not be a stopping configuration in any strategy and is declared as bad. And so on until convergence. Notice the similarity with a 2-player game. $M$ can actually be easily transformed into an arena where plant $\mathcal{A}$ (player 1) selects the next input label $\alpha$ and makes its transition accordingly, while the attacker (player 2) needs to select a processing for the proposed $\alpha$ that matches protocol $\mathcal{P}$. ■

In the example of Fig. 2, configuration (3,1) becomes bad as its unique transition for input label $c$ leads to a bad configuration. Consequently, the transition from (2,1) to (3,1) through $(a, \bar{a})$ can not be part of any admissible strategy and must be removed.

It is possible that no admissible strategy exist for some triple $(\mathcal{A}, \mathcal{P}, \tilde{\mathcal{A}})$. In that case, one has $L_I(\mathcal{M}) \subseteq L(\mathcal{A})$ and there exists at least one input word produced by plant $\mathcal{A}$ that will violate the attack protocol.

**Proposition 3:** If there exists at least one admissible strategy for $(\mathcal{A}, \mathcal{P}, \tilde{\mathcal{A}})$, then there exists a maximal (or most permissive) one denoted $S_a$. Any sub-strategy $\mathcal{S}$ of $S_a$ is also admissible.

*Proof:* The union of two admissible strategies is an admissible strategy, whence the existence of $S_a$. It coincides with the pruning of $M$ described in the proof of Prop. 2. ■

Remark. An admissible strategy may exhibit zenoness, i.e. enable loops where the attack can repeatedly insert
(output) labels to $\tilde{\mathcal{A}}$ without ever absorbing a new (input) label $\alpha$ from $\mathcal{A}$. Nevertheless, the possibility of absorbing any new input label allowed by $\mathcal{A}$ remains open.

**Proposition 4:** In an admissible strategy $\mathcal{S}$ for $(\mathcal{A}, \mathcal{P}, \tilde{\mathcal{A}})$ every configuration leads to a stopping configuration.

*Proof:* Just like $\mathcal{M}$, any strategy $\mathcal{S}$ is non-blocking, thus can absorb any new input label produced by $\mathcal{A}$. This holds for admissible strategies. As $\mathcal{A}$ is live, there is always a new input label to come. ■

Zenoness is useless in a strategy as it leads to no new configuration of the output pair $\mathcal{P} \times \tilde{\mathcal{A}}$. It can be removed by a post-processing in $\mathcal{S}$, left to the reader.

*Definition 6:* A strategy $\mathcal{S}$ for $(\mathcal{A}, \mathcal{P}, \tilde{\mathcal{A}})$ is winning iff it is admissible and no configuration $(s, x, \perp)$ is reachable.

**Proposition 5:** Finding winning strategies of $\mathcal{M}$ can be solved in quadratic time (in the size of $\mathcal{M}$).

*Proof:* Similar to Prop. 2.

Again, it is possible that no winning strategy exists.

**Proposition 6:** If there exists at least one winning strategy for $(\mathcal{A}, \mathcal{P}, \tilde{\mathcal{A}})$, then there exists a maximal (or most permissive) one, denoted $\mathcal{S}_w$. Any sub-strategy $\mathcal{S}$ of $\mathcal{S}_w$ is also winning.

*Proof:* Similar to Prop. 3.

When it exists, the maximally permissive winning strategy $\mathcal{S}_w$ can be obtained by further pruning $\mathcal{S}_a$ by backtracking from bad configurations $(s, x, \perp)$, as in the proof of Prop. 2. Notice that $\mathcal{S}_w$ (just like $\mathcal{S}_a$) may still contain bad configurations, but they can not be stopping. They are necessarily transient, i.e. reachable only by transitions with a silent input in order to reach another stopping configuration. See below for an example.

By construction, any transition in $\mathcal{S}_w$ is part of a valid response to some input label $\alpha$ freely chosen by $\mathcal{A}$. It will be compatible with the attack protocol and will lure an observer into believing that $\tilde{\mathcal{A}}$ is actually running. $\mathcal{S}_w$ is generally not deterministic and may allow several ways of transforming some sensor reading $\alpha$, among which the attacker can freely choose. One can obviously prune a winning strategy to make it deterministic.

<figure><img src="image_4.png" /><figcaption>Fig. 3. Transducer $\mathcal{A} \times \mathcal{P}^c \times \tilde{\mathcal{A}}^c$ connecting the 3 elements of Fig. 1. For the sake of clarity, transitions participating to a non-admissible strategy (leading to some $(s, \perp, \bar{s})$) have been removed, and transitions following a losing state $(s, x, \perp)$ are not represented.</figcaption></figure>

Fig. 3 displays the transducer $\mathcal{M} = \mathcal{A} \times \mathcal{P}^c \times \tilde{\mathcal{A}}^c$ used to find winning strategies for components in Fig. 1. For clarity, runs violating the attack protocol $\mathcal{P}$ have been pruned, so

only admissible strategies remain, and transitions following a losing state $(s, x, \perp)$ are not represented. Transitions to bad configurations $(s, x, \perp)$ must be removed. Configuration (2, 2, 1) becomes bad because its unique way to accept input label $b$ leads to a bad configuration (1, 2, $\perp$). Consequently, transition labeled $(a, \varepsilon)$ from (1, 1, 1) to (2, 2, 1) must be removed. This does not make (1, 1, 1) a bad configuration as it still has a way of accepting $a$ as input label. (2, 2, 1) remains in $\mathcal{S}_w$ as a transient configuration, which is necessary for accepting input label $a$ from configuration (2, 2, 2). After removing all bad transitions, bad stopping configurations and pruning the result, one gets the $\mathcal{S}_w$ depicted in Fig. 4. $\mathcal{S}_w$ is not deterministic. For example, there are three ways to process $c$ from (3, 2, 2).

<figure><img src="image_5.png" /><figcaption>Fig. 4. Maximally permissive winning strategy $\mathcal{S}_w$ for plant $\mathcal{A}$, attack protocol $\mathcal{P}$ and target $\tilde{\mathcal{A}}$ of Fig. 1.</figcaption></figure>

### C. Projection of a strategy

Let $\phi: \tilde{\mathcal{A}}^c \to \tilde{\mathcal{B}}^c$ be a morphism between two target automata, preserving labels and such that $\phi(s) = \perp \Rightarrow s = \perp$. $\phi$ extends into a natural morphism between $\mathcal{M} = \mathcal{A} \times \mathcal{P}^c \times \tilde{\mathcal{A}}^c$ and $\mathcal{M}' = \mathcal{A} \times \mathcal{P}^c \times \tilde{\mathcal{B}}^c$, also denoted by $\phi$, defined by $\phi(s, x, \bar{s}) = (s, x, \phi(\bar{s}))$.

**Proposition 7:** If $\mathcal{S}$ is an admissible (resp. winning) strategy in $\mathcal{M}$, then $\phi(\mathcal{S})$ is an admissible (resp. winning) strategy in $\mathcal{M}'$.

*Proof:* Observe first that $\mathcal{S}' = \phi(\mathcal{S})$ is a sub-transducer of $\mathcal{M}'$. As labels are preserved, $\mathcal{S}'$ is also a strategy. The middle state variable $x$ is untouched by $\phi$, so if $x = \perp$ is unreachable in $\mathcal{S}$ it is also unreachable in $\mathcal{S}'$, which proves preservation of admissibility. The rightmost state variable $\bar{s}$ can not become $\perp$ through $\phi$ unless $\bar{s} = \perp$, so if $\bar{s} = \perp$ is unreachable in $\mathcal{S}$, this also holds in $\mathcal{S}'$, which proves preservation of the winning property. ■

Let $\mathcal{S}'_w$ be the maximal winning strategy in $\mathcal{M}'$. Then Prop. 7 proves $\phi(\mathcal{S}_w) \subseteq \mathcal{S}'_w$, but equality does not hold in general. There may exist other winning strategies for target $\tilde{\mathcal{B}}$, as it is less restrictive than $\tilde{\mathcal{A}}$. By contrast, one has $\phi(\mathcal{S}_a) = \mathcal{S}'_a$, where $\mathcal{S}'_a$ is the maximal admissible strategy for $\mathcal{M}'$.

Consider now the forgetful morphism $\psi: \mathcal{M} \to \mathcal{A} \times \mathcal{P}^c$ defined as $\psi(s, x, \bar{s}) = (s, x)$ and preserving labels. By definition of the product, one has

$$ \forall \mathcal{S} \subseteq \mathcal{M}, \mathcal{S} \subseteq \psi(\mathcal{S}) \times \tilde{\mathcal{A}}^c \quad (2) $$

with equality when $\mathcal{S} = \mathcal{M}$.

**Definition 7:** The projection of strategy $\mathcal{S} \subseteq \mathcal{A} \times \mathcal{P}^c \times \tilde{\mathcal{A}}^c$ to $\mathcal{A} \times \mathcal{P}^c$ is defined as $\psi(\mathcal{S})$.
The notion of admissible strategy extends naturally to $\mathcal{A} \times \mathcal{P}^c$. Let $\mathcal{S}'_a$ denote the maximally permissive admissible strategy in $\mathcal{A} \times \mathcal{P}^c$.

**Proposition 8:** One has $\psi(\mathcal{S}_w) \subseteq \mathcal{S}'_a$ and $\psi(\mathcal{S}_a) = \mathcal{S}'_a$. This entails $\mathcal{S}_w \subseteq \mathcal{S}'_a \times \tilde{\mathcal{A}}^c$.

*Proof:* As $\psi$ forgets the "$\tilde{\mathcal{A}}^c$ part" of $\mathcal{M}$, $\psi(\mathcal{M})$ is isomorphic to the $\phi(\mathcal{M})$ built above for $\tilde{\mathcal{B}}$ the trivial automaton with a single state and accepting all $\Sigma_O^*$. Therefore Prop. 7 applies, and $\psi(\mathcal{S}_w)$ is a winning strategy in $\mathcal{A} \times \mathcal{P}^c$, but all admissible strategies are actually winning strategies since losing is not possible in target $\tilde{\mathcal{B}}$. This proves $\psi(\mathcal{S}_w) \subseteq \mathcal{S}'_a$. The second equality follows similarly. For the last part, (2) yields $\mathcal{S}_w \subseteq \psi(\mathcal{S}_w) \times \tilde{\mathcal{A}}^c \subseteq \mathcal{S}'_a \times \tilde{\mathcal{A}}^c$. ■

This result is of practical interest: it means that winning strategies for the triple $(\mathcal{A}, \mathcal{P}, \tilde{\mathcal{A}})$ can be derived by first looking for the maximal admissible strategy $\mathcal{S}'_a$ in $\mathcal{A} \times \mathcal{P}^c$ (see bold part in Fig. 2), then combining it with the target $\tilde{\mathcal{A}}^c$ by $\mathcal{S}'_a \times \tilde{\mathcal{A}}^c$ (Fig. 3), and pruning the latter into $\mathcal{S}_w$ (bold part in Fig. 3, or Fig. 4).

#### IV. SUCCESSFUL STEALTH ATTACKS

The special case $\tilde{\mathcal{A}} = \mathcal{A}$ deserves attention. It corresponds to a setting where the attacker wants to modify sensor readings in a way that remains undetectable to the observer.

**Definition 8:** The maximal stealth sensor attack on $\mathcal{A}$ for protocol $\mathcal{P}$ is the maximal winning strategy for triple $(\mathcal{A}, \mathcal{P}, \mathcal{A})$. It is denoted $\mathcal{S}_s$.

If there exists at least one stealth attack strategy on $\mathcal{A}$, then $\mathcal{S}_s$ is non-trivial (i.e. not reduced to the trivial transducer, with no transition), and $L_I(\mathcal{S}_s) = L(\mathcal{A})$. By construction, one also has $L_O(\mathcal{S}_s) \subseteq L(\mathcal{A})$, so the observer has no way to discover that sensor readings are modified. From Prop. 8, $\mathcal{S}_s$ can be obtained by first selecting admissible strategies, combining them with $\mathcal{A}$ to further filter out non-stealth strategies.

Faking a different behaviour of $\mathcal{A}$ by following $\mathcal{S}_s$ is not useful in itself: the attacker may now want to exert some weak form of control by enforcing a strict (regular) sub-language $L(\mathcal{B}) \subseteq \mathcal{L}(\mathcal{A})$ on the observer side. For example to hide that $\mathcal{A}$ has entered in some specific state (e.g. state 3 in our running example). If $\mathcal{A}$ is the diagnoser of some plant $\mathcal{G}$, the attacker could thus prevent the detection of a fault in $\mathcal{G}$ by the observer, by hiding that diagnoser $\mathcal{A}$ is in a state where detection takes place [11]. Similarly, if $\mathcal{A}$ is an observer of the initial state in plant $\mathcal{G}$ (i.e. $\mathcal{A}$ is a deterministic automaton that updates at each new observation the possible initial states of $\mathcal{G}$), then the attacker could hide from the observer that the initial state of $\mathcal{G}$ was necessarily a secret state [12]. If $\mathcal{A}$ is an observer of plant $\mathcal{G}$, it can also be used to drive a supervisor of $\mathcal{G}$ that enables/disables controllable events. The attacker may thus lure the observer into a belief state of $\mathcal{G}$ (i.e. a state of $\mathcal{A}$) where some potentially dangerous actions are not disabled thus putting plant $\mathcal{G}$ at risk. More generally, the attacker wants to pretend that some extra regular property on words of $\mathcal{A}$ always/never takes place. Without loss of generality, we assume that the

target behavior $L(\mathcal{B}) \subseteq L(\mathcal{A})$ is actually defined by a sub-automaton $\mathcal{B} \subseteq \mathcal{A}$.

**Definition 9:** Let $\mathcal{B}$ be a sub-automaton of $\mathcal{A}$, defining the target sub-language $L(\mathcal{B}) \subseteq L(\mathcal{A})$. The maximal stealth and successful attack of the 4-tuple $(\mathcal{A}, \mathcal{P}, \mathcal{A}, \mathcal{B})$ is the maximal winning strategy $\mathcal{S}_w$ of $(\mathcal{A}, \mathcal{P}, \mathcal{B})$.

As $\mathcal{B}$ is a sub-automaton of $\mathcal{A}$, a winning strategy must not only comply with $\mathcal{A}$ (so be stealth) but also with $\mathcal{B}$ (so achieve the objective defined by target $\mathcal{B}$). Again, by a recursive application of Prop. 8, the maximal stealth and successful attack can be derived by first computing the maximal stealth strategy $\mathcal{S}_s$ and further pruning $\mathcal{S}_s \times \mathcal{B}^c$ to filter out losing strategies which output language can not stay within $L(\mathcal{B})$. In the running example of Fig. 1, the target automaton $\tilde{\mathcal{A}}$ was already a sub-automaton of $\mathcal{A}$, so Fig. 4 illustrates the maximal stealth and successful sensor reading attack that follows protocol $\mathcal{P}$ and hides from the observer that $\mathcal{A}$ is in state 3.

#### V. MOST PROMISING STEALTH ATTACK

There may not exist a successful stealth attack strategy for $(\mathcal{A}, \mathcal{P}, \mathcal{A}, \mathcal{B})$ where $\mathcal{B} \subseteq \mathcal{A}$. Either an admissible attack remains stealth but fails to fake the target behavior $\mathcal{B}$, or worse it does not even manage to fake $\mathcal{A}$ and gets detected. But when input $\mathcal{A}$ is stochastic, there may exist strategies that reach one of the above objectives with a reasonable probability.

Due to space limitations, we focus on a simple setting with only two plants: input plant $\mathcal{A}$, a stochastic automaton, and target $\mathcal{P}^c$ (which could also be $\mathcal{P}^c \times \mathcal{A}^c$ or $\mathcal{P}^c \times \mathcal{B}^c$). $\mathcal{A} = (S, \Sigma, P, s_0)$ is defined by its transition probability $P$: $S \times \Sigma \times S \to \mathbb{R}^+$ such that $\forall s \in S$, $\sum_{\alpha, s'} P(s, \alpha, s') = 1$. The transition set $T$ of $\mathcal{A}$ is the support of $P$, $T = \text{supp}(P)$. Our assumption that $\mathcal{A}$ is deterministic remains, so once $\alpha$ is (randomly) selected at $s$, the resulting state $s'$ is unique. Consider deterministic strategies $\mathcal{S} \subseteq \mathcal{M} = \mathcal{A} \times \mathcal{P}^c$, and assume there is no admissible one: for all such $\mathcal{S}$, there exists an input word $w \in L(\mathcal{A})$ that violates protocol $\mathcal{P}$, i.e. the single stopped run $u \in R(\mathcal{S})$ such that $\sigma_I(u) = w$ satisfies $u^+ = (s, \perp)$. Observe that in a deterministic strategy there exists a unique stopped run $u$ matching any input word $w \in L(\mathcal{A})$, i.e. $\mathcal{S}$ has a unique way to react to $w$, which maps the probability $P$ defining $\mathcal{A}$ to runs of $\mathcal{S}$. Therefore it makes sense to look for deterministic strategies that minimize the probability to reach $S \times \{\perp\}$, i.e. that maximize the probability to remain admissible (stealth or winning in the general case).

In transducer $\mathcal{M} = \mathcal{A} \times \mathcal{P}^c$, deterministic strategies can not be read out easily due to the intermediate output label injections of $\mathcal{P}^c$ that take place before a new input label from $\mathcal{A}$ can be processed. A simple way around consists in performing an $\varepsilon$-reduction of $\mathcal{M}$ by merging each transition carrying no input label by each of its successors, before removing it, and recursively untill all transitions carry an input label. For lack of space, this technical step is omitted here, and we directly consider that each transition in $\mathcal{P}^c$ absorbs one input label from $\mathcal{A}$. Fig. 5 gives an example
where $\mathcal{P}^c$ is an automaton. A deterministic strategy consists in selecting one transition of $\mathcal{M}$ for each possible input $\alpha$ of $\mathcal{A}$. For example, in configuration $(2,1)$, if $\mathcal{A}$ chooses to produce an $a$ (probability $\frac{1}{2}$), component $\mathcal{P}^c$ must select one of the two possible branches labeled $a$ in $\mathcal{M}$: either go to $(3,1)$ or to $(3,2)$.

This setting is a specific case of a Markov Decision Process, where the randomness comes from $\mathcal{A}$ and the decision from $\mathcal{P}^c$. The objective here is to minimize the probability to reach a state $(s, \perp)$, i.e. to be non-consistent with the attack protocol $\mathcal{P}$. It is known that stochastic strategies (that would randomly select an output branch for each submitted input label) do not achieve better performance than deterministic strategies. Finding the best deterministic strategy can be solved by linear programming [1] (Thm. 10.100 Chap. 10.6.1).

Specifically, let us attach some value $V(s,x)$ to each configuration $(s,x)$ of $\mathcal{M}$, with $V(s, \perp) = 1$. $V(s,x)$ is the minimal probability to reach a losing configuration over all possible deterministic strategies. In our restricted (epsilon-reduced) setting, if input label $\alpha$ is firable at state $s$ in $\mathcal{A}$ and can lead to $s'$, then $\alpha$ is also firable from $(s,x)$ by construction of $\mathcal{M}$. The resulting state $s' = T_{\mathcal{A}}(s, \alpha)$ in $\mathcal{A}$ is unique, and protocol $\mathcal{P}^c$ has to select one possible resulting state $x' \in T_{\mathcal{P}^c}(x, \alpha)$. The optimal value function thus has to satisfy for all $(s,x)$ with $x \neq \perp$

$$V(s,x) = \sum_{\alpha \in \Sigma} P(\alpha|s) \min_{(s',x') \in T_{\mathcal{A}}((s,x),\alpha)} V(s',x') \quad (3)$$

where the argument of the min points to the optimal branch for input label $\alpha$ at configuration $(s,x)$ and thus defines the optimal deterministic strategy.

In the example of Fig. 5, the optimal values $V(s,x)$ are 1 for pairs $(2, \perp)$, $(2,1)$, $(3, \perp)$, $(3,1)$, and 0 for pairs $(3,3)$, $(3,2)$, $(2,2)$. Notice that at $(2,2)$, the two possible choices for input $c$ yield identical values. One then has $V(1,1) = 1/3$ and this minimal value is obtained by opting for state $(2,2)$ under input $a$ instead of state $(2,1)$. For input $b$ at state $(1,1)$ there is no other option than going to $(3,1)$ which incurs a losing probability of $1/3$. The optimal deterministic strategy is depicted by bold lines.

<figure><img src="image_6.png" /><figcaption>Fig. 5. Stochastic plant $\mathcal{A}$ (top left) feeding attack protocol $\mathcal{P}^c$ (top right) represented as an automaton. Below, the composite system $\mathcal{M} = \mathcal{A} \times \mathcal{P}^c$ with one deterministic (non-admissible) strategy depicted by bold lines.</figcaption></figure>

It is possible that several best deterministic strategies exist,

or even that all deterministic strategies have probability 0 to be admissible. Then one would like to select the longest lasting strategy, i.e. the one with the longest average distance to $\perp$ (conditionally to reaching $\perp$). The computation of this distance is explained in [3] for a fixed deterministic strategy. It remains to be combined with an optimization as in (3) to select the best one.

## VI. DISCUSSION

Transducers offer a natural model for attack protocols on sensor readings. They quickly lead to an arena where the attacker can express its different objectives. They are flexible enough to capture extensions to multiple objectives attacks, or to complex coordinated attacks on different sensors, with and without communication. Stochastic plants offer other appealing research directions when stealth winning strategies do not exist. By recycling results from stochastic games or MDPs, one can look for strategies maximizing chances of success, or for the longest lasting strategies when all are doomed to fail. One can also imagine balancing different objectives and for example trading discretion (increasing risk of being detected) for success (increasing probability to remain within the target behavior). Finally, notice that for a stochastic input plant the notion of stealth attack must be refined: even if the target language is satisfied, the likelihood of output words can lead to detection. For example, in the long run, the relative frequencies of letters in the output words of $\mathcal{P}^c$ may trigger statistical tests about the presence of an attack [2].

## REFERENCES

[1] Christel Baier, Joost-Pieter Katoon. "Principles of Model Ckecking." MIT Press, 2008.

[2] T. Chen, S. Kiefer. "On the total variation distance of labelled Markov chains." Proc. Joint Meeting EACSL Annual Conference on Computer Science Logic (CSL) and ACM/IEEE Symposium on Logic in Computer Science (LICS), 2014.

[3] H. Bazille, E. Fabre, B. Genest. "Symbolically Quantifying Response Time in Stochastic Models Using Moments and Semirings." Found. of Soft. Sc. and Comp. Struct., FoSSaCS 2018.

[4] R. Fritz, P. Zhang. "Modeling and detection of cyber attacks on discrete event systems." IFAC-PapersOnLine, vol. 51, no. 7, pp. 285-290, 2018.

[5] L. Kawakami Carvalho, Y.-C. Wu, R. Kwong, S. Lafortune. "Detection and mitigation of classes of attacks in supervisory control systems." Automatica (97), pp. 121-133, 2018.

[6] Y. Wang, M. Pajic. "Supervisory Control of Discrete Event Systems in the Presence of Sensor and Actuator Attacks." 58th Conference on Decision and Control (CDC), pp. 5350-5355, 2019.

[7] M. Wakaiki, P. Tabuada, J.P. Hespanha. "Supervisory Control of Discrete-Event Systems Under Attacks." Dyn. Games Appl. (9) 965-983, 2019.

[8] R. Meira-Góes, E. Kang, R. H. Kwong, S. Lafortune. "Synthesis of sensor deception attacks at the supervisory layer of Cyber-Physical Systems." Automatica (121), 2020.

[9] R. Meira-Góes, S. Lafortune, H. Marchand. "Synthesis of Supervisors Robust Against Sensor Deception Attacks." IEEE Trans. on Automatic Control, vol. 66, no. 10, pp. 4990-4997, 2021.

[10] Y. Tong, Y. Wang, A. Giua. "A Polynomial Approach to Verifying the Existence of a Threatening Sensor Attacker." IEEE Control Systems Letters, vol. 6, pp. 2930-2935, 2022.

[11] T. Kang, C. Seatzu, Z. Li, A. Giua. "Fault Diagnosis of Discrete Event Systems Under Attack." 62nd IEEE Conference on Decision and Control (CDC), pp. 7923-7929, 2023.

[12] J. Yao, S. Li, X. Yin. "Sensor deception attacks against security in supervisory control systems." Automatica (159), 2024.