Verifying Weak and Strong k-Step Opacity
in Discrete-Event Systems

Opacity is an information-flow property used to study security and privacy questions of discrete-event systems, communication protocols, and computer systems. Besides security and privacy, an interesting application of opacity is its ability to express other state-estimation properties. In particular, Lin (2011) has shown how to express and verify observability, diagnosability, and detectability in terms of opacity.

Opacity guarantees that a system prevents an intruder from revealing its secret. The intruder is a passive observer that knows the structure of the system but has only limited observations of system’s behavior. Intuitively, the intruder estimates the behavior of the system, and the system is opaque if for every secret behavior, there is a nonsecret behavior that looks the same to the intruder. The secret is modeled as a set of secret states or as a set of secret behaviors. Modeling the secret as a set of secret states results in state-based opacity, introduced by Bryans et al. (2005, 2008) for Petri nets and transition systems, and adapted to automata by Saboori and Hadjicostis (2007). Modeling the secret as a set of secret behaviors results in language-based opacity, introduced by Badouel et al. (2007) and Dubreil et al. (2008). See the overview by Jacob et al. (2016) for more details.

Many notions of opacity have been discussed in the literature, including initial-state opacity and current-state opacity. While initial-state opacity prevents the intruder from revealing, at any time instant, whether the system started in a secret state, current-state opacity prevents the intruder “only” from revealing whether the system is currently in a secret state. This, however, does not exclude the possibility that the intruder later realizes that the system was in a secret state at a former step of the computation. For instance, if the intruder estimates that the system is in one of two possible states and, in the next step, the system proceeds by an observable event enabled only in one of the states, then the intruder reveals the state in which the system was one step ago.

Saboori and Hadjicostis (2007, 2012) addressed this issue and introduce the notion of weak $k$-step opacity. Weak $k$-step opacity requires that the intruder is not able to ascertain the secret in the current state and $k$ subsequent observable steps. For $k=0$ and $k=\infty$, weak $k$-step opacity coincides with current-state opacity and infinite-step opacity, respectively. The notion of infinite-step opacity may be confusing in the context of finite automata, because an $n$-state automaton is infinite-step opaque if and only if it is $(2^{n}-2)$-step opaque, see Yin and Lafortune (2017).

The verification of weak $k$-step opacity has been intensively studied in the literature, resulting in (at least) five different approaches: (1) the secret observer approach with complexity $O(\ell 2^{n(k+3)})$, where $n$ is the number of states and $\ell$ is the number of observable events, (2) the reverse comparison approach with complexity $O((n+m)(k+1)3^{n})$, where $m\leq\ell n^{2}$ is the number of transitions in an involved NFA, (3) the state estimator approach of Saboori and Hadjicostis (2011) with complexity $O(\ell(\ell+1)^{k}2^{n})$, (4) the two-way observer approach of Yin and Lafortune (2017) with complexity $O(\min\{n2^{2n},n\ell^{k}2^{n}\})$, already corrected by Lan et al. (2020), and (5) the projected automaton approach of Balun and Masopust (2021) of complexity $O((k+1)2^{n}(n+m\ell^{2}))$; see also Wintenberg et al. (2022) for more details on the state complexity and an experimental comparison. The reader can see that the complexity of all the algorithms depends on the parameter $k$. A partial exception is the two-way observer algorithm that does not depend on the parameter $k$ if $\ell^{k}>2^{n}$, that is, if $k$ is larger than the number of states divided by the logarithm of the number of observable events.

In this paper, we design a new algorithm verifying weak $k$-step opacity, the complexity of which does not depend on the parameter $k$. The state complexity of our algorithm is $O(n2^{n})$ and the time complexity is $O((n+m)2^{n})$, where $n$ is the number of states of the input automaton and $m\leq\ell n^{2}$ is the number of transitions of the projected input automaton. Hence, our algorithm is faster than all the existing algorithms, with the exception of a very small parameter $k$; namely, if $k$ is smaller than $2\log(n)/\log(\ell)$, where $n$ is the number of states of the input automaton and $\ell$ is its number of observable events, then the algorithms based on the state estimator and on the two-way observer are, in the worst-case, faster than our algorithm.

However, Falcone and Marchand (2015) have later noticed that even weak $k$-step opacity may not be as confidential as intuitively expected. In particular, the intruder may realize that the system was in a secret state, although it cannot deduce the exact time when this has happened (see an example in Section 4 or in Falcone and Marchand (2015) for more details). This problem motivated Falcone and Marchand (2015) to introduce strong $k$-step opacity as the notion of $k$-step opacity with a higher level of confidentiality. The idea is that whereas weak $k$-step opacity prevents the intruder from revealing the exact time when the system was in a secret state during the last $k$ observable steps, strong $k$-step opacity prevents the intruder from revealing that the system was in a secret state during the last $k$ observable steps.

Ma et al. (2021) pointed out without proofs that strong and weak $k$-step opacity are incomparable in the sense that neither strong $k$-step opacity implies weak $k$-step opacity nor vice versa. In fact, under the assumption that there are no neutral states (states that are neither secret nor nonsecret), which is assumed in most of the literature, including this paper, strong $k$-step opacity implies weak $k$-step opacity (see Appendix A for more details).

However, the verification of one type of $k$-step opacity cannot be directly used for the verification of the other. We show how to do it indirectly. Namely, we construct a polynomial-time transformation of strong $k$-step opacity to weak $k$-step opacity, which makes it possible to verify strong $k$-step opacity by the algorithms for weak $k$-step opacity. In addition, using our new algorithm verifying weak $k$-step opacity results in a new algorithm to verify strong $k$-step opacity with a lower complexity that does not depend on the parameter $k$.

We assume that the reader is familiar with discrete-event systems, see Cassandras and Lafortune (2021) for more details. For a set $S$, $|S|$ denotes the cardinality of $S$, and $2^{S}$ denotes the power set of $S$. An alphabet $\Sigma$ is a finite nonempty set of events. A string over $\Sigma$ is a sequence of events from $\Sigma$; the empty string is denoted by $\varepsilon$. The set of all finite strings over $\Sigma$ is denoted by $\Sigma^{*}$. A language $L$ over $\Sigma$ is a subset of $\Sigma^{*}$. For a string $u\in\Sigma^{*}$, $|u|$ denotes the length of $u$.

A nondeterministic finite automaton (NFA) over an alphabet $\Sigma$ is a structure $G=(Q,\Sigma,\delta,I,F)$, where $Q$ is a finite set of states, $I\subseteq Q$ is a nonempty set of initial states, $F\subseteq Q$ is a set of marked states, and $\delta\colon Q\times\Sigma\to 2^{Q}$ is a transition function that can be extended to the domain $2^{Q}\times\Sigma^{*}$ by induction; we often consider the transition function $\delta$ as the corresponding relation $\delta\subseteq Q\times\Sigma\times Q$. In addition, for a set $S\subseteq\Sigma^{*}$, we define $\delta(Q,S)=\cup_{s\in S}\,\delta(Q,s)$. For a set $Q_{0}\subseteq Q$, the set $L_{m}(G,Q_{0})=\{w\in\Sigma^{*}\mid\delta(Q_{0},w)\cap F\neq\emptyset\}$ is the language marked by $G$ from the states of $Q_{0}$, and $L(G,Q_{0})=\{w\in\Sigma^{*}\mid\delta(Q_{0},w)\neq\emptyset\}$ is the language generated by $G$ from the states of $Q_{0}$. The languages marked and generated by $G$ are defined as $L_{m}(G)=L_{m}(G,I)$ and $L(G)=L(G,I)$, respectively. The NFA $G$ is deterministic (DFA) if $|I|=1$ and $|\delta(q,a)|\leq 1$ for every $q\in Q$ and $a\in\Sigma$. In this case, we identify the singleton $I=\{q_{0}\}$ with its element $q_{0}$, and simply write $G=(Q,\Sigma,\delta,q_{0},F)$ instead of $G=(Q,\Sigma,\delta,\{q_{0}\},F)$.

A discrete-event system (DES) $G$ over $\Sigma$ is an NFA over $\Sigma$ together with the partition of $\Sigma$ into $\Sigma_{o}$ and $\Sigma_{uo}$ of observable and unobservable events, respectively. If we want to specify that the DES is modeled by a DFA, we talk about deterministic DES. If the marked states are irrelevant, we omit them and simply write $G=(Q,\Sigma,\delta,I)$.

The state estimation is modeled by projection $P\colon\Sigma^{*}\to\Sigma_{o}^{*}$, which is a morphism for concatenation defined by $P(a)=\varepsilon$ if $a\in\Sigma_{uo}$, and $P(a)=a$ if $a\in\Sigma_{o}$. The action of $P$ on a string $a_{1}a_{2}\cdots a_{n}$ is to erase all unobservable events, that is, $P(a_{1}a_{2}\cdots a_{n})=P(a_{1})P(a_{2})\cdots P(a_{n})$. The definition can be readily extended to languages.

Let $G$ be a DES over $\Sigma$, and let $P\colon\Sigma^{*}\to\Sigma_{o}^{*}$ be the corresponding projection. The projected automaton of $G$ is the NFA $P(G)$ obtained from $G$ by replacing every transition $(p,a,q)$ by $(p,P(a),q)$, followed by the standard elimination of the $\varepsilon$-transitions. In particular, if $\delta$ is the transition function of $G$, then the transition function $\gamma\colon Q\times\Sigma_{o}\to 2^{Q}$ of $P(G)$ is defined as $\gamma(q,a)=\delta(q,P^{-1}(a))$. The projected automaton $P(G)$ is an NFA over $\Sigma_{o}$ with the same states as $G$ that recognizes the language $P(L_{m}(G))$ and that can be constructed in polynomial time, see Hopcroft et al. (2006).

We call the DFA constructed from $P(G)$ by the standard subset construction a full observer of $G$. The accessible part of the full observer of $G$ is called an observer of $G$, cf. Cassandras and Lafortune (2021). The full observer has exponentially many states compared with $G$. In the worst case, the same holds for the observer as well, see Wong (1998); Jirásková and Masopust (2012) for more details.

For two DESs $G_{i}=(Q_{i},\Sigma,\delta_{i},I_{i})$, $i=1,2$, over the common alphabet $\Sigma$, the product automaton of $G_{1}$ and $G_{2}$ is defined as the DES $G_{1}\times G_{2}=(Q_{1}\times Q_{2},\Sigma,\delta,I_{1}\times I_{2})$, where $\delta((q_{1},q_{2}),a)=\delta_{1}(q_{1},a)\times\delta_{2}(q_{2},a)$, for every pair of states $(q_{1},q_{2})\in Q_{1}\times Q_{2}$ and every event $a\in\Sigma$. Notice that the definition does not restrict the state space of the product automaton to its reachable part.

In this section, we recall the definition of weak $k$-step opacity for DESs, and design a new algorithm to verify weak $k$-step opacity. To this end, we denote by $\mathbb{N}_{\infty}=\mathbb{N}\cup\{\infty\}$ the set of all nonnegative integers together with their limit. For $k\in\mathbb{N}_{\infty}$, weak $k$-step opacity asks whether the intruder cannot reveal the secret of a system in the current and $k$ subsequent states.

  Verification of weak $k$-step opacity

Algorithm 3 describes our new algorithm verifying weak $k$-step opacity. The idea of the algorithm is as follows. We first compute the observer of $G$, denoted by $G^{obs}$, and the projected automaton of $G$, denoted by $P(G)$. Then, for every reachable state $X$ of $G^{obs}$, we add the pairs $(x,X\cap Q_{NS})$ to the set $Y$, where $x$ is a secret state of $X$ and $X\cap Q_{NS}$ is the set of all nonsecret states of $X$. Intuitively, in these states, the intruder estimates that $G$ may be in the secret state $x$ or in the nonsecret states of $X\cap Q_{NS}$. To verify that the intruder does not reveal the secret state, we need to check that every possible path of length up to $k$ starting in $x$ is accompanied by a path with the same observation starting in a nonsecret state of $X\cap Q_{NS}$. To this end, we construct the automaton $H$ as the part of the full observer of $G$ consisting only of states reachable from the states forming the second components of the pairs in $Y$, and the automaton $\operatorname{\mathcal{C}}=P(G)\times H$ as the product automaton of the projected automaton of $G$ and $H$. In $\operatorname{\mathcal{C}}$, all transitions are observable, and every path from a secret state $x$ is synchronized with all the possible paths with the same observation starting in the states of $X\cap Q_{NS}$. Thus, if there is a path from the secret state $x$ of length up to $k$ that is not accompanied by a path with the same observation from a state of $X\cap Q_{NS}$, then this path from the state $x$ in $P(G)$ ends up in a state, say, $q$, whereas all paths in $H$ with the same observation from the state $X\cap Q_{NS}$ end up in the state $\emptyset$. Here, $X\cap Q_{NS}$ and $\emptyset$ are understood as the states of the full observer of $G$. Thus, if the DES $G$ is not weakly $k$-step opaque, there is a state of $Y$ from which a state of the from $(q,\emptyset)$ is reachable in at most $k$ steps. Therefore, we search the automaton $\operatorname{\mathcal{C}}$ and mark all its states that are reachable from a state of $Y$ in at most $k$ steps. If a state of the from $(q,\emptyset)$ is marked, then $G$ is not weakly $k$-step opaque; otherwise, it is.

We prove the correctness of Algorithm 3 and analyze its complexity in detail below. Intuitively, the correctness follows from the fact that the BFS visits all nodes at distance $d$ before visiting any nodes at distance $d+1$. In other words, all states of $\operatorname{\mathcal{C}}$ reachable from the states of $Y$ in at most $k$ steps are visited (and marked) before any state at distance $k+1$. The implementation of the BFS is, however, the key step to obtain the claimed complexity. Namely, the classical BFS of Cormen et al. (2009) maintains an array to store the shortest distances (aka the number of hops) of every node to an initial node. Since storing a number less than or equal to $k$ requires $\log(k)$ bits, using the classical BFS requires the space of size $O(\log(k)n2^{n})$ to store the shortest distance of every state of $\operatorname{\mathcal{C}}$ to a state of $Y$, because $\operatorname{\mathcal{C}}$ has $O(n2^{n})$ states.

For our purposes, we do not need to know the shortest distance of every state to a state of $Y$, but we rather need to keep track of the number of hops from the states of $Y$ made so far.

We can achieve this by modifying the classical BFS so that we do not store the shortest distances for every state of $\operatorname{\mathcal{C}}$, but only the current distance. We store the current distance in the queue used by the BFS, see Algorithm 3. In particular, we first push number 0 to the queue, followed by all the states of $Y$. Assuming that $k>0$, number 0 is processed in such a way that it is dequeued from the queue, and number 1 is enqueued. After processing all the states of $Y$ from the queue, that is, having number 1 at the head of the queue, we know that all the elements of the queue after number 1 are the states at distance one from the states of $Y$ and not less. The algorithm proceeds this way until it has either visited all the states of $\operatorname{\mathcal{C}}$ or the number stored in the queue is $k$. The algorithm marks all states of $\operatorname{\mathcal{C}}$ that it visits.

This approach requires to store only one $\log(k)$-bit number at a time rather than $n2^{n}$ such numbers, and hence the complexity of the algorithm then basically follows from the fact that the distance is bounded by the number of states of $\operatorname{\mathcal{C}}$, and not by the parameter $k$.

Since Algorithm 3 is a minor modification of the BFS of Cormen et al. (2009), very similar arguments show its correctness and complexity. For this reason, we do not further discuss the correctness and complexity of Algorithm 3.

  The Breadth-First Search used in Algorithm 3

Before we prove Theorem 2 below showing that $G$ is weakly $k$-step opaque if and only if no state of the form $(\cdot,\emptyset)$ is marked in $\operatorname{\mathcal{C}}$, we illustrate Algorithm 3 in the following two examples.

In the first example, we consider one-step opacity of the DES $G$ depicted in Figure 1(a) where all events are observable, state $2$ is secret, and state $4$ is nonsecret. The other states are neutral, meaning that they are neither secret nor nonsecret.¹¹1The meaning of neutral states is not yet clear in the literature. They are fundamental in language-based opacity, but questionable in state-based opacity. In any case, we cannot simply handle neutral states as nonsecret states. The observer $G^{obs}$ of $G$ is depicted in Figure 1(b).

Since $G$ has no unobservable events, the projected automaton $P(G)=G$. Now, only the state $X=\{2,4\}$ of $G^{obs}$ contains a secret state, and hence intersecting it with $Q_{S}$ results in the set $Y=\{(2,\{4\})\}$. Notice that state $\{4\}$ is not in the observer $G^{obs}$, and therefore we need to add it to $H$ together with all the states that are reachable from state $\{4\}$ in the full observer of $G$. The resulting automaton $H$ is depicted in Figure 1(b) and is formed by the observer $G^{obs}$ together with the dashed state $\{4\}$ and the dashed transition from $\{4\}$ to $\{5\}$. Notice that, by the definition of the (full) observer, all the missing transitions in Figure 1(b) indeed lead to state $\emptyset$, for instance, $\delta(\{1\},b)=\delta(\{5\},a)=\emptyset$. However, to keep the figures simple, we do not depict state $\emptyset$ and the transitions to state $\emptyset$. The marked part of the automaton $\operatorname{\mathcal{C}}_{1}=P(G)\times H$ reachable from the states of $Y$ in at most one step is depicted in Figure 2. Since state $(3,\emptyset)$ is marked in $\operatorname{\mathcal{C}}_{1}$, $G$ is not one-step opaque; indeed, observing the string $ab$, the intruder reveals that $G$ must have been in the secret state $2$ one step ago.

To illustrate an affirmative case, we again consider the DES $G$, but this time we assume that the event $c$ is unobservable. We denote by $\tilde{G}$ the DES $G$ where events $a,b$ are observable, the event $c$ is unobservable, state $2$ is secret, and state $4$ is nonsecret. The projected automaton $P(\tilde{G})$ and the observer $\tilde{G}^{obs}$ are depicted in Figure 3. The only state of $\tilde{G}^{obs}$ containing a secret state is the state $X=\{2,4,5\}$, which results in the set $Y=\{(2,\{4\})\}$. Again, state $\{4\}$ is not in $\tilde{G}^{obs}$, and hence we construct the relevant part $\tilde{H}$ of the full observer of $\tilde{G}$ by extending $\tilde{G}^{obs}$ by state $\{4\}$ and all the reachable states from it. The result (without state $\emptyset$ and the transitions to state $\emptyset$) is depicted in Figure 3(b), both the solid and the dashed part. The marked part of $\operatorname{\mathcal{C}}_{2}=P(\tilde{G})\times\tilde{H}$ is depicted in Figure 4. Since no state of the form $(\cdot,\emptyset)$ is marked in $\operatorname{\mathcal{C}}_{2}$, $\tilde{G}$ is one-step opaque.

We now prove the correctness of our algorithm.

We now discuss the complexity of our algorithm.

We now briefly review the complexity of existing algorithms verifying weak $k$-step opacity. First, notice that the complexity of existing algorithms is exponential, which seems unavoidable because the problem is PSpace-complete, see Balun and Masopust (2021, 2022a) for more details.²²2It is a long-standing open problem of computer science whether PSpace-complete problems can be solved in polynomial time. In particular, Saboori and Hadjicostis (2011) designed an algorithm with complexity $O(\ell(\ell+1)^{k}2^{n})$, where $n$ is the number of states and $\ell$ is the number of observable events. Considering the verification of weak $\infty$-step opacity, Saboori and Hadjicostis (2012) designed an algorithm with complexity $O(\ell 2^{n^{2}+n})$. Yin and Lafortune (2017) introduced the notion of a two-way observer and applied it to the verification of weak $k$-step opacity with complexity $O(\min\{n2^{2n},n\ell^{k}2^{n}\})$, and to the verification of weak $\infty$-step opacity with complexity $O(n2^{2n})$; the formulae already include a correction by Lan et al. (2020). Balun and Masopust (2021) designed algorithms verifying weak $k$-step opacity and weak $\infty$-step opacity with complexities $O((k+1)2^{n}(n+m\ell^{2}))$ and $O((n+m\ell)2^{n})$, respectively, where $m\leq\ell n^{2}$ is the number of transitions in the projected automaton. These algorithms outperform the two-way observer if $k$ is polynomial in $n$ or larger than $2^{n}-2$, since weak $(2^{n}-2)$-step opacity and weak $\infty$-step opacity coincide, see Yin and Lafortune (2017). Wintenberg et al. (2022) discussed and experimentally compared four approaches to the verification of weak $k$-step opacity based on (i) the secret observer, (ii) the reverse comparison, (iii) the state estimator, and (iv) the two-way observer. Their respective state complexities are $O(2^{n(k+3)})$, $O(n(k+1)3^{n})$, $O((\ell+1)^{k}2^{n})$, and $O(\min\{2^{n},\ell^{k}\}2^{n})$.³³3The state complexity of the two-way observer is correct. The correction of Lan et al. (2020) consists in adding a time bound to compute the intersection of two sets, and hence it does not influence the number of states.

Notice that these bounds are formulated only in the number of states of the constructed automata, disregarding the number of transitions and the time of the construction. Therefore, the time-complexity bounds differ from the state-complexity bounds at least by the factor of $\ell$, if the constructed automata are deterministic, or by a factor of $m\leq\ell n^{2}$ if the construction of the automaton involves an NFA, such as in the case of the reverse comparison. Namely, the time-complexity bounds are $O(\ell 2^{n(k+3)})$ for the secret observer, where $n$ is the number of states and $\ell$ is the number of observable events, $O((n+m)(k+1)3^{n})$ for the reverse comparison, where $m\leq\ell n^{2}$ is the number of transitions in an involved NFA, $O(\ell(\ell+1)^{k}2^{n})$ for the state estimator, and $O(\min\{n2^{2n},n\ell^{k}2^{n}\})$ for the two-way observer.

As the reader may notice, the above complexities depend on the parameter $k$. A partial exception is the two-way observer that does not depend on $k$ if $\ell^{k}\geq 2^{n}$, that is, if $k$ is larger than the number of states divided by the logarithm of the number of observable events.

Since the complexity of Algorithm 3 is $O((n+m)2^{n})$, where $n$ is the number of states of the input DES $G$ and $m\leq\ell n^{2}$ is the number of transitions of the projected automaton of $G$, it does not depend on the parameter $k$ and, in general, outperforms the existing algorithms. An exception is the case of a very small parameter $k$. In particular, if $k<2\log(n)/\log(\ell)$, the algorithms based on the state estimator and on the two-way observer are, in the worst-case, faster than our algorithm. Notice that this theoretical result agrees with the experimental results of Wintenberg et al. (2022).

Although weak $k$-step opacity seems confidential enough, Falcone and Marchand (2015) have pointed out that it is actually not as confidential as intuitively expected. Namely, the intruder may realize that the system previously was in a secret state, though it is not able to deduce the exact time when that happened, see Falcone and Marchand (2015) for more details and examples. Consequently, they defined strong $k$-step opacity as a variation of $k$-step opacity with a higher level of confidentiality.

Before we recall the definition of strong $k$-step opacity as formulated by Falcone and Marchand (2015), we illustrate the problem with weak $k$-step opacity. To this end, we consider the system depicted in Figure 5, where state $2$ is secret and the other states are nonsecret, and where the event $a$ is observable and the event $u$ is unobservable. Observing the string $aa$, the intruder realizes that the system must have been in the secret state $2$, though it cannot say whether it was one or two steps ago. Actually, even observing the string $a$ already reveals that the system currently is or one step ago was in the secret state $2$.

In accordance with Falcone and Marchand (2015), we consider strong $k$-step opacity only for deterministic DES where all states that are not secret are nonsecret, that is, $Q_{NS}=Q-Q_{S}$. It means that every state has its own secret/nonsecret status and there are no neutral states.

Notice that whereas weak $k$-step opacity prevents the intruder from revealing the exact time when the system was in a secret state during the last $k$ observable steps, strong $k$-step opacity prevents the intruder from revealing that the system was in a secret state during the last $k$ observable steps.

For an illustration, we again consider the system depicted in Figure 5, where state $2$ is secret and event $u$ is unobservable. The system is weakly one-step opaque, but not strongly one-step opaque, because for $s=aua$, the only $w$ with the same observation as $s$ is $w=aua$, and hence the prefixes $w^{\prime}$ for which $|P(w)|-|P(w^{\prime})|\leq 1$ are the strings $w^{\prime}=a$, $w^{\prime}=au$, and $w^{\prime}=aua$. However, for $w^{\prime}=a$, we obtain that $\delta(1,a)=2\in Q_{S}$, which violates the definition of strong one-step opacity.

In fact, the system is neither strongly 0-step opaque, because for $s=au$, the only $w$ with the same observation as $s$ are the strings $au$ and $a$, and therefore the prefixes $w^{\prime}$ for which $|P(w)|-|P(w^{\prime})|\leq 0$ is either $w^{\prime}=a$ or $w^{\prime}=au$. However, for $w^{\prime}=a$, we obtain that $\delta(1,a)=2\in Q_{S}$, which violates the definition of strong $0$-step opacity. On the other hand, the system is obviously current-state opaque. Consequently, the notions of strong 0-step opacity and current-state opacity⁴⁴4Current-state opacity is a synonym for weak 0-step opacity. do not coincide.

We show in Theorem 8 below that unobservable transitions from secret states to nonsecret states, as in our example, are the only issues making the difference between strong 0-step opacity and weak 0-step (current-state) opacity. To this end, we define the notion of a normal DES.