Optimal Attack Strategy Compromising Diagnosability of Automated Manufacturing Systems in Labeled Petri Nets

Optimal Attack Strategy Compromising Diagnosability of Automated Manufacturing Systems in Labeled Petri Nets Ruotian Liu, Agostino Marcello Mangini, Maria Pia Fanti Abstract— This paper addresses the diagnosability analysis problem under malicious attacks of a discrete event system modeled by labeled Petri net. We focus on a stealthy replacement attack to alter or corrupt the observation of the system. The aim of this work is, from an attacker viewpoint, to design a stealthy replacement attack for violating the diagnosability of system. To this end, we first build a new structure, called attack verifier that is used to enumerate all the attack paths. Then an optimal attack synthesis problem in terms of minimum energy cost is formulated by determining whether a bad path is generated via solving a set of integer linear programming problems. Finally, an automated manufacturing system is provided to illustrate the proposed attack strategy. I. INTRODUCTION Fault diagnosis is critical for highly automated manufacturing systems (AMSs). The attack scenario of AMSs have attracted much attention in the community of discrete event systems (DESs): mainly concerning the problems of attack detection and attack synthesis [1], [2]. This work focuses on the attack synthesis problem with optimization objectives for violating the diagnosability in DESs. In this work, we consider the permanent attack [3] (i.e., once an attack is performed and each transition is either associated with its original or a replaced label, then all the transition labels remain unchanged) rather than intermittent setting [4] (i.e., the attacked label can be recovered in finite time). Diagnosability is a system property determining whether the occurrence of a fault can be detected within finite steps, and has been studied in the framework of automata [5] and Petri nets [6]. Although recent works focus on diagnosability and fault diagnosis in the presence of attacks, they primarily deal with detecting or tolerating attacks rather than synthesizing attacks to violate diagnosability, which is the focus of our study. For example, the violation of safety caused by malicious interception and alteration of sensor readings is considered in [7]. Moreover, the work [8] investigates how an attacker with asymmetric observations can strategically corrupt outputs to maximize the operator’s diagnostic uncertainty. In addition, the violation of opacity is studied in [9]. The studies [3], [4] works on attack-synthesis problems in DESs that aim to hide the occurrence of faults. This work is a part of the IN2CCAM project. This project has received funding from the European Union’s Horizon Europe research and innovation program under grant agreement No. 101076791. This content reflects only the authors’ view and the European Commission is not responsible for any use that may be made of the information this publication contains. Ruotian Liu, Agostino Marcello Mangini and Maria Pia Fanti are with the Department of Electrical and Information Engineering, Polytechnic University of Bari, Italy (e-mails: [email protected], agostinomar- [email protected], [email protected]). To tackle the attack synthesis problem, there are mainly several approaches in the literature. The first type of approaches [2] employs a discrete structure to model the game-like interaction between the supervisor and the attacker, which incorporates all possible attacks; the second one transforms the attack synthesis problem into the supervisor synthesis problem [1]. Different from the existing approaches, we introduce a modified labeling function to model an attack, for making a system non-diagnosable by leveraging techniques of unfolded verifier structure in labeled Petri nets. The main contribution of this work is listed as follows. First, we formulate an optimal stealthy replacement attack problem in terms of minimum energy cost, which is determined by solving a set of integer programming problems. Since the classic verifier [10] can only update states when consecutive transition pairs have the same observation, it is unable to generate bad paths. To solve these issues, we then develop a new structure called attack verifier by integrating the attack capability. Finally, an illustrative example on automated manufacturing system is provided to show the proposed attack strategy. II. PRELIMINARIES A. Basic definitions of Petri net Let Nbe the set of non-negative integers. A Petri net is defined as a four-tuple N= (P, T, Pre, P ost), where P= {p1, ..., pm}is a set of m∈Nplaces, T={t1, ..., tn}is a set of n∈Ntransitions with P∪T=∅and P∩T=∅, Pre :P×T→Nand P ost :P×T→Nare the preand post-incidence matrices, respectively, denoting the weight of the arcs from places to transitions and transitions to places. The incidence matrix of a net is defined by C=Post−P re. A Petri net is said to be acyclic if there is no directed cycle. A marking is a mapping M:P→Nthat assigns to a place of a Petri net a non-negative integer of tokens. M(pi) is the number of tokens in place piat a marking M. A net system ⟨N, M0⟩is a net Nwith an initial marking M0. A transition t∈Tis enabled at a marking Mif M≥Pre(·, t) and may fire yielding a marking M′=M+C(·, t). We write M[σ⟩to denote that a transition sequence σ=t1t2· · · ti∈ T∗is enabled at M, and M[σ⟩M′to denote that the firing of σyields M′. The Parikh vector of σis denoted by π(σ) : T→Nnand maps a transition t∈Tto the number of occurrences of tin σ. A marking Mis reachable in ⟨N, M0⟩if there exists a firing sequence σ∈T∗such that M0[σ⟩M. The set of all markings reachable from M0, denoted by R(N, M0), defines the reachability set of ⟨N, M0⟩, i.e., R(N, M0) = {M∈ Nm|M0[σ⟩M}. The set of transition sequences enabled at the initial marking M0is defined as L(N, M0) = {σ∈T∗| M0[σ⟩}.Given a set H⊆L(N, M0),we denote H/σ the post transition sequence of Hafter σ, i.e., H/σ ={σ′∈T∗| σσ′∈H}. A net system ⟨N, M0⟩is said to be: bounded if it exists an integer k∈Nsuch that for all M∈R(N, M0) and for all pi∈P, M(pi)≤kholds; deadlock-free if for all M∈R(N, M0), there exists t∈T, M[t⟩. B. Labeled Petri net Given a Petri net N= (P, T, P re, P ost)and an event set Σ, a labeling function l:T→Σ∪ {ε}= Σεassigns to a transition either a symbol from the event set Σor the empty string symbol ε. A labeled Petri net (LPN) system S=⟨N, Σ, l, M0⟩is a Petri net system ⟨N, M0⟩with a labeling function land an event set Σ. A transition tis said to be unobservable if it is associated with the empty string ε, i.e., l(t) = ε. The set of unobservable transitions is denoted by Tu={t∈T|l(t) = ε}. The other transitions labeled with events from Σare called observable transitions, denoted as To={t∈T|l(t)∈Σ}. Furthermore, the set Tucan be divided into two disjoint sets Tfand Treg with Tu=Tf∪ Treg, where Tfand Treg denote the sets of fault transitions and regular unobservable transitions, respectively. The labeling function can be extended to a transition sequence σ=t1t2· · · tisuch that ω=l(σ) = l(t1)l(t2)· · · l(ti),which is called an observation corresponding to the sequence σ. Given a net system ⟨N, Σ, l, M0⟩, we define l−1(ω)as the set of all transition sequences consistent with ω∈Σ∗ ε,i.e., l−1(ω) = {σ∈L(N, M0)|l(σ) = ω}. The language generated by an LPN system Sis defined as L(N, M0) = {ω∈Σ∗ ε| ∃σ∈L(N, M0) : ω=l(σ)}. C. Extended basis reachability graphs In this part, we recall necessary notions of the extended basis markings in [6], [11], where the observable transition set is assumed to be Tα o=To∪Tf. Give a transition sequence σ∈T∗, we denote by Preg(σ)(resp., Pα o(σ)) the projection of σover Treg (resp., Tα o). Moreover, the restriction of incidence matrix Cof an LPN system to Treg is denoted by Creg. Definition 2.1 ( [6]): Given a marking M∈R(N, M0) and a transition t∈Tα oof an LPN system S=⟨N, Σ, l, M0⟩, the set of explanations of tat Mis defined by Σ(M, t) = {σ∈T∗ reg |M[σ⟩M′, M′[t⟩},and the set of their e-vector is denoted as Y(M, t) = {π(σ)|σ∈Σ(M, t)}. In addition, the set of minimal explanations of tat Mis denoted by Σmin(M, t) = {σ∈Σ(M, t)|∄σ′∈Σ(M, t) : π(σ′)⪇ π(σ)}and the minimal e-vector is defined as Ymin(M, t) = {π(σ)|σ∈Σmin(M, t)}. The set of extended basis markings, denoted as Xe, is recursively computed as follows: M0∈Xe; If M∈Xe, then for each t∈To∪Tf, y =π(σ)∈Ymin(M, t), (M′=M+Creg ·y+C(·, t)) ⇒(M′∈Xe).The extended basis reachability graph (EBRG) of Sis a nondeterministic finite state automaton Ge= (Xe, E, δ, M0), where Xeis the set of states; E⊆(To×Σ) ∪(Tf× {ε})is the set of event labels; δ⊆Xe×E×Xeis the transition relation; and M0is the initial state. A nonfailure EBRG, denoted by Ge,n = (Xe,n, En, δn, M0,n), is the EBRG derived from ⟨N′,Σ, l′, M0⟩following the assumption that the set of observable transitions is equal to To. III. DIAGNOSABILITY ANALYSIS PROBLEM WITH ATTACKS A. Replacement and stealthy attack To characterize the capability of an intruder that masks the transition labels, an attack structure is presented as follows. Definition 3.1 (Attack structure): Let S=⟨N, Σ, l, M0⟩ be an LPN system. An attack structure is defined as the set A∈2(To×Σε)×(To×Σε), i.e., Ais a set of transition pairs, each associated to its label: the first transition is associated to the original label while the second one is associated to the replaced label. To make the exposition clear, we denote by Ta={t∈ To| ∃e′∈Σε,((t, e),(t, e′)) ∈ A} the set of attacked transitions that can be targeted with respect to A, and denote by ΣA(t) = {e′∈Σε|((t, e),(t, e′)) ∈ A, t ∈Ta, e =l(t)} the set of replaced labels associated with transition twhile taking into account the attack structure A. We denote by lA(t) = {e|l(t) = e}∪{e′|e′∈ΣA(t)}. Definition 3.2 (Replacement attack): Let S=⟨N, Σ, l, M0⟩be an LPN system and Abe an attack structure. A replacement attack A(attack for short) is a modified labeling function that is the mapping la:T∗→Σ∗ εwhere •la(ε) = ε, •la(t) = l(t)if t∈T\Ta, l(t)or e′∈ΣA(t)if t∈Ta, •la(σt) = la(σ)la(t), σ ∈T∗, t ∈T. Under the attack A, each transition t∈Tais either associated with the original label l(t)or a replaced label e′∈ΣA(t). Subsequently, the given attack structure Amay cause multiple attack options. The considered replacement attack includes a particular removal case, such as when an observable transition is associated with an empty string. Definition 3.3 (Stealthy attack): Given an LPN system S=⟨N, Σ, l, M0⟩under an attack Ai, the attack Aiis said to be stealthy if for any transition sequence σ, its corrupted observations are contained in the language of LPN system, i.e., ∀σ∈L(N, M0), lai(σ)∈ L(N, M0). Precisely, stealthiness requires that the set of corrupted observations is contained in the set of observations without attacks. B. Diagnosability The fault transition set Tfcan be partitioned into rclasses Ti f, where i= 1, . . . , r. For the sake of simplicity, this work considers an LPN with a single fault class, i.e., Tf=T1 f. Nevertheless, the proposed approach could be extended to the nets with multiple fault classes with a slight modification of the method proposed in [5] for this purpose. Let T′be a subset of T. We define ψ(T′) = {σt ∈ L(N, M0)|σ∈T∗, t ∈T′}as the set of firing sequences in L(N, M0)that end with a transition t∈T′. Definition 3.4 ( [6]): An LPN system S=⟨N, Σ, l, M0⟩ having no deadlock after the occurrence of a fault tf∈Tf, is diagnosable with respect to the fault transition set Tfif ∀σ′∈ψ(Tf),∃K∈N,∀σ′′ ∈L(N, M0)/σ′, |σ′′| ≥ K=⇒ ∀σ∈l−1(l(σ′σ′′)),∃tf∈Tf:tf∈σ. C. Problem statement Before formulating the addressed problem, we first present a notion of optimality criterion, i.e., minimum cost. Specifically, each transition is associated with a replacement attack cost, i.e., a non-negative real value, which describes the difficulty of attack for replacing its transition label. The higher the value of the cost of the attack is, the more difficult the attack on the transition is, otherwise it is easier. In the rest of this work, we refer the optimal attack to the minimum cost one, and focus on the following problem: Problem 1: Given an LPN system S=⟨N, Σ, l, M0⟩ that is vulnerable to an attack structure A, the objective is to design an optimal stealthy replacement attack Aifor violating the diagnosability in the LPN system. The following assumptions hold for the diagnosability analysis under the attacks in the LPN systems. A1) The LPN system is bounded and deadlock-free after the occurrence of a fault. A2) The Tu-induced subnet is acyclic. A3) There exists a nonempty set of predetermined stealthy attacks As={As1, . . . , Asθ}, with 1≤θ≤Πt∈Ta[(|ΣA| + 1)] −1based on the attack structure A. IV. OPTIMAL ATTACK AGAINST DIAGNOSABILITY In this section, we first present an attack verifier that lists all the attack paths to be transformed into bad paths leading to the violation of diagnosability. Then, an optimal attack can be obtained by solving a set of linear programming problems. A. Attack Verifier An attack verifier Ua= (XU a, EU a, δU a, MU 0)is a finite state automaton, that shows all the possible attacked paths, presented in Algorithm 1. Step 1 initializes the set of states, transitions, events, and the initial state in the attack verifier. The main part in lines 2–15, at each untagged state, iteratively generates all the other states. In this process, for each transition pair (ti, tj), where ti∈To∪Tfand tj∈To, the verifier adds a new state (M′ 1, α′;M′ 2)if the transitions (M1, ti, M′ 1)∈δ, (M2, tj, M′ 2)∈δnand non-empty set lA(t1)∩lA(t2)hold from the current state (M1, α;M2). By accounting for transitions with the same observation under attack, the proposed verifier captures attack paths that may exploit differences in observation, which classical verifiers would ignore. Note that αcan be either Nto represent the normal behavior of system without the occurrence of fault from the initial state to this one, or Fto denote the occurrence of faulty behavior of system. Algorithm 1: Construction of an attack verifier Input: EBRGs Ge= (Xe, E, δ, M0),Ge,n = (Xe,n, En, δn, M0,n), and attack structure A Output: An attack verifier Ua= (XU a, EU a, δU a, MU 0) 1Let XU a={(M0, N;M0)},EU a=∅, δU a=∅, MU 0= (M0, N;M0)be the initial state ; 2while states with no tag exist do 3select a state (M1, α;M2) with no tag ; 4if (M1, α;M2) is same as a state in the path from MU 0to it then 5tag it “duplicate” and go to Step 2; 6for all t1∈To∪Tfand t2∈To,do 7if (M1, t1, M′ 1)∈δ, (M2, t2, M′ 2)∈ δn, lA(t1)∩lA(t2)=∅then 8add a state (M′ 1, α;M′ 2)and a transition (t1, t2)from (M1, α;M2)to (M′ 1, α;M′ 2); 9if t1∈Tf,(M1, t1, M′ 1)∈δthen 10 add a state (M′ 1, F;M2)and a transition (t1, λ)from (M1, α;M2)to (M′ 1, F;M2); 11 if t1∈To,(M1, t1, M′ 1)∈δ, ε ∈lA(t1)then 12 add a state (M′ 1, α;M2)and a transition (t1, λ)from (M1, α;M2)to (M′ 1, α;M2); 13 if t2∈To,(M2, t2, M′ 2)∈δn, ε ∈lA(t2)then 14 add a state (M1, α;M′ 2)and a transition (λ, t2)from (M1, α;M2)to (M1, α;M′ 2); 15 tag the state (M1, α;M2)“old”. The following definition presents the notion of bad path that leads to the violation of diagnosability. Precisely, the existence of this type of path shows that, two arbitrarily long transition sequences of LPN system have the same observation under attack and one of them contains the fault transition, such that the occurrence of the fault cannot be detected in a finite number of steps. Given an automaton G, we write Mσ −→ GM′to denote that M′is reached in Gfrom Mwith a sequence σ. Definition 4.1: Let S=⟨N, Σ, l, M0⟩be an LPN system, Xebe the set of extended basis markings, and Uabe a attack verifier constructed by its two EBRGs Geand Ge,n. A path eσ= (γi1, γj1)(γi2, γj2)· · · (γik, γjk)in Uais called a bad path if, by letting σα=γi1· · · γiq, σβ=γiq+1 · · · γik, σ′ α= γj1· · · γjq, and σ′ β=γjq+1 · · · γjk, there exist M, M′∈ Xeand an attack Aicorresponding to the modified labeling function laisatisfying: (1) M0 σα −−→ Ge Mσβ −−→ Ge M; (2) M0 σ′ α −−−→ Ge,n M′σ′ β −−−→ Ge,n M′; (3) lai(σα) = lai(σ′ α)and lai(σβ) = lai(σ′ β); (4) tf∈σασβ; (5) no prefix of eσsatisfies items (1)–(4). Proposition 4.2: An LPN system ⟨N, Σ, l, M0⟩satisfying (A1)–(A2) is diagnosable if and only if its attack verifier Ua has no bad paths. Proof: Following Definition 4.1 and a result proved in [10], [12] that the LPN system is diagnosable if and only if its classic unfolded verifier has no such a path, it could easily extend into our result. Using Algorithm 1, we enumerate all paths but focus only on those that can be attacked into a bad path that violates the diagnosability of the system. The following definition presents such an attack path. Definition 4.3: A path eσ= (γi1, γj1)(γi2, γj2)· · · (γik, γjk)in Uais called attack path if σα=γi1· · · γiq, σβ= γiq+1 · · · γik, σ′ α=γj1· · · γjq, and σ′ β=γjq+1 · · · γjk, there exist M, M′∈Xe, such that (i) the conditions (1)(2)(4)(5) in Definition 4.1 hold and (ii) an attacked transition t∈Ta exists such that t∈σασβor t∈σ′ ασ′ β. B. Optimal attack determination Before formally describing the attack strategy, we present some necessary notions of minimum cost attack for violating the diagnosability. We denote by the row vector c= [c1, . . . , cj, . . . , c|T|]the attack cost coefficient vector, that associates a non-negative real value cjto each possible attacked transition tj∈To, and assigns cj= 0 to each transition tj∈Tu, where cj= 0 means that transition tjcannot be attacked. Now, given an attack path eσk= (σk,1, σk,2), in order to select the possible attacks for violating the diagnosability, we define a vector vk= [vt1,k, . . . , vtj,k,..., vt|T|,k]T. In particular, vtj,k ∈ {0,1}for j= 1,...,|T|is a binary decision variable and vtj,k = 1 (resp., vtj,k = 0) means that the transition label of tjhas (resp., has not) been replaced under the replacement attack A. Moreover, it holds vtj,k = 0 for the set of transitions T\Tathat cannot be attacked. For the sake of clarity, we denote by ejand e′ jthe original label of transition and one replaced label of transition tj, i.e., ej=l(tj)and e′ j∈ΣA(tj), respectively. Based on the aforementioned notions, given a transition tjand its corresponding transition label pair (ej, e′ j), the corrupted observation of transition tjcan be expressed as vtj,k ·e′ j+ (1 −vtj,k)·ej. Precisely, in the case that vtj,k = 1 has the corrupted observation 1·e′ j=e′ j, while vtj,k = 0 holds its original observation with (1−0)ej=ej. When the sequence σis under an attack Ai, we can derive its compromised observation using the following expression lai(σ)=Πj|σ| j=j1[vtj,k ·e′ j+ (1 −vtj,k)ej]. Definition 4.4 (Corrupted option): Given an LPN system Svulnerable to an attack structure A, a corrupted option Cis defined as: each transition tj∈Tais associated with a corrupted label e′ j∈ΣA(tj), in which the amount of corrupted options is equal to Πt∈Ta|ΣA(t)|. And the set of corrupted options is denoted by C(A) = {Ci|i= 1,...,Πt∈Ta|ΣA(t)|}. Given an attack path and a corrupted option, the following lemma characterizes the possible attacks Aifor violating the diagnosability. Lemma 4.5: Let us consider the k-th attack path eσk= (σk,1, σk,2)with σk,1=σα,kσβ,k and σk,2=σ′ α,kσ′ β,k. Given an attack structure Aand a corrupted option C, the attacks Aito generate a bad path for violating the diagnosability are determined by the vectors vk= [vt1,k, . . . , vtj,k, . . . , vt|T|,k]Tthat satisfy the following constraints:                        a) vtj,k ∈ {0,1} ∀tj∈Ta b) vtj,k = 0 ∀tj∈T\Ta c) Πj|σα,k| j=j1[vtj,k ·e′ j+ (1 −vtj,k)ej] = Π j′ |σ′ α,k| j=j′ 1[vtj,k ·e′ j+ (1 −vtj,k)ej] d) Πj|σβ,k| j=j1[vtj,k ·e′ j+ (1 −vtj,k)ej] = Π j′ |σ′ β,k| j=j′ 1[vtj,k ·e′ j+ (1 −vtj,k)ej] (1) Proof: Constraints (a) show that each transition tj∈Ta is associated with a binary decision variable vtj,k ∈ {0,1}. Constraints (b) impose vtj,k = 0 for the set of transitions T\Ta. By performing an attack Aithat is the modified labeling function lai, constraints (c)(d) guarantee that two sequences σk,1=σα,kσβ,k and σk,2=σ′ α,kσ′ β,k generate the same observation, i.e., lai(σα,k) = lai(σ′ α,k)and lai(σβ,k) = lai(σ′ β,k). In the following, constraints (1.c) and (1.d) are linearized by replacing them with the constraints (2.c) and (2.d):                        a) vtj,k ∈ {0,1} ∀tj∈Ta b) vtj,k = 0 ∀tj∈T\Ta c) Pj|σα,k| j=j1[vtj,k ·e′ j+ (1 −vtj,k)ej] =Pj′ |σ′ α,k| j=j′ 1[vtj,k ·e′ j+ (1 −vtj,k)ej] d) Pj|σβ,k| j=j1[vtj,k ·e′ j+ (1 −vtj,k)ej] =Pj′ |σ′ β,k| j=j′ 1[vtj,k ·e′ j+ (1 −vtj,k)ej]. (2) The following lemma establishes the relationship between vectors vksatisfying constraints (1) and vectors vksatisfying constraints (2). Lemma 4.6: If vector vksatisfies constraints (1), then it also satisfies constraints (2). Proof: Constraints (2.c) (2.d) ensure that two sequences σk,1and σk,2generate the same amount of transition labels (without requirement on the label order), while constraints (1.c) (1.d) guarantee that two sequences generate the same observation (with requirement on the label order). Hence, it can be deduced that vector vksatisfies constraints (1), then it also satisfies constraints (2). By Lemma 4.6, we can deduce that the set of feasible solutions for constraints (1) is a subset of the set of feasible solutions for constraints (2). To formalize the new problem we introduce a set of vectors Vk, where each element vk∈Vksatisfies constraints (2) but violates constraints (1). To ensure these infeasible solutions vkare excluded from the solution of following ILP Problem 2, additional linear constraints are defined using a vector ykfor each vk∈Vk with ytj,k ∈ {0,1}for j= 1,...,|T|. ILP Problem 1: Consider an attack structure A, an attack cost coefficient vector cand a set of vectors Vkthat satisfies constraints (2) but does not satisfy constraints (1). The minimum attack cost zkin terms of k-th attack path and a corrupted option C, corresponding to attack Akfor violating the diagnosability can be obtained by solving the following ILP problem:            zk= min c·vk, s.t.the set of constraints (2), e.1) ytj,k ∈ {0,1} ∀tj∈T, e.2) Pj=|T| j=1 ytj,k ≥1 e.3) ytj,k ≤vtj,k +vtj,k ≤2−ytj,k ∀tj∈T, ∀vk∈Vk. Constraints (e.2) and (e.3) linearize vk=vkby enforcing that there exists at least one variable ytj,k ≥1. Indeed, if vk=vk, then each ytj,k = 0 and constraint (e.2) is not satisfied. C. Algorithm for optimal stealthy replacement attack In the following, Algorithm 2 outlines the steps to compute this optimal stealthy replacement attack. Algorithm 2: Computation of an optimal stealthy replacement attack Input: An attack verifier Ua= (XU a, EU a, δU a, MU 0), an attack structure A, a set of stealthy attacks Asand an attack cost coefficient vector c. 1List all the attack paths Π = {eσ1,...,eσk,...,eσh} from Uaby Definition 4.3 and obtain all the corrupted options C(A); 2Initialize k= 1, Z =∅, Vk=∅; 3for all eσk∈Πdo 4for each corrupted option C ∈ C(A)do 5Reset Vk=∅; 6if the ILP Problem 1 is feasible then 7if the solution vksatisfies constraints (1) and the corresponding Ak∈ Asthen 8zkis the objective value of solution vk; 9if zk= ˆcthen 10 bzk=zk,b Ak=Ak, go to Step 17; 11 else 12 Z={zk} ∪ Z, Vk=Vk∪ {vk}; 13 else 14 vk=vk; 15 Vk=Vk∪ {vk}and go to Step 6; 16 bz= min zk Z; 17 Return vkand b Ak; Step 1 obtains all the attack paths in the attack verifier Uaby the conditions in Definition 4.3 and all the corrupted options C(A). Step 2 initializes the index k, the set Zthat contains the attack costs corresponding to the computed attacks, and the set Vkcontaining the feasible solutions of ILP problem 2 that satisfy constraints (1). The main part (steps 3–15) analyzes each attack path until the attack cost is optimal (i.e., minimum cost) or all the attack paths have been analyzed. Theorem 4.7: Given an LPN system Ssatisfying Assumptions (A1)–(A3) vulnerable to an attack structure A, the attack Afor violating the diagnosability of the system S that is computed by Algorithm 2 is optimal. Proof: For each path eσk, the algorithm obtains all the possible attacks Akcorresponding to the path eσkand all the corrupted options C(A). For each corrupted option C, the set Vkcontaining the feasible solutions of ILP problem 1 and not satisfying constraints (1) is firstly reset as empty set. By Lemma 4.7, the part (steps 6–15) analyzes the minimum cost attack corresponding the path eσkand this corrupted option by guaranteeing the feasibility of solution, satisfying the constraints (1) and ensuring the stealthiness of attack (step 7), i.e., the obtained attack should be contained in the set of given stealthy attack As. Particularly, if the total attack cost zkis equal to its minimum coefficient ˆc, i.e., ˆc= min {j|tj∈To}cj, it implies that a minimum cost attack bzkis obtained, such that the algorithm returns the corresponding attack b Ak. Otherwise it stores the attack cost zkin the cost set Z. After analyzing all paths, we obtain the minimum cost bzkfrom Zand its corresponding attack b Ak. V. A CASE STUDY ON AUTOMATED MANUFACTURING SYSTEM In this section, to demonstrate the proposed attack approach, we consider an automated manufacturing system (AMS) taken from [13], [14], as shown in Fig. 1. This system consists of two entries (I1 and I2), two exits (O1 and O2), five machines (M1–M5), two buffers with capacity 4 (B1 and B2), four robots (R1–R4), and two AGVs (AGV1 and AGV2). It incorporates two separate production lines that manufacture different products, as summarized below. During operation, Robots R1 and R2 serve both lines: Robot R1 supports Machines M1, M2, and M4, while Robot R2 handles parts from M3 and M5. Line 1: R1 loads stock from I1 into M1/M2, R3 routes the identical intermediates through B1 to M3, and R2 puts the finished pieces on AGV1, which delivers them to O1 and brings fresh material. Line 2 mirrors this process where R1 feeds M4 from I2, R4 moves intermediates via B2 to M5, and R2 places the output on AGV2 for O2 before picking up new stock. The Petri net model of the considered AMS is shown in Fig. 2. The meaning of each place and each transition is described in detail in [14]. In Fig. 2, the set of unobservable transitions Tu={t7, t9, t12, t17, t21, t22}with two fault transitions t21(f1)and t22(f2). In detail, f1represents a situation that a raw material from entry I1 is directly put into buffer B1 without being processed by M1 or M2 and Fig. 1. An automated manufacturing system. f2denotes another situation that an intermediate part after processing by M4 is then machined by M5, without being put into the buffer B2. The set of observable transitions To=T\Tuwith l(t1) = a, l(t2) = l(t3) = l(t13) = b, l(t4) = l(t5) = c, l(t6) = d, l(t8) = l(t15) = e, l(t10) = l(t19) = f, l(t11) = g, l(t14) = l(t16) = h, l(t18) = l(t20) = k. We now explore the effectiveness of the attack strategy proposed in this paper. Suppose that an attacker can hijack the sensors at Robots 1–4, and has the attack capability by removing the label of transition t2and replacing the label of transition t4(resp., t13) from c to d (resp., from b to c), i.e., the attack structure A={(t2(b), t2(ε)),(t4(c), t4(d)),(t13(b), t13(c))}. By implementing Algorithm 2, it returns the following results with a computational time 2.35 mins that refers to the CPU seconds of a laptop with Intel CPU Core 2.3 GHz, 8GB memory and a Matlab tool. Specifically, an attack path eσ1= (t1, t1)(t21, t2)(t13, t13)(t14, t14)(t15, t15) (t16, t16)(t17, t17)(t18, t18)(t19, t19)(t20, t20)and the corrupted option C1={e′ 2=ε, e′ 4=d, e′ 13 =c}, we get the solution v1=[0100000000000000000000]T and its minimum attack cost z1= 1, which generates a bad path with la1(σ1,1) = la1(σ1,2) = a(bhekfk), such that the system becomes non-diagnosable. VI. CONCLUSION Algorithms addressing stealthy replacement attacks that undermine diagnosability in discrete event systems have been developed. We constructed an attack verifier to enumerate all attack paths leading to the violation of diagnosability. In addition, we formulated the optimal attack synthesis as a set of ILP problems, and solved them to obtain the optimal attack. Future work will first extend the proposed attack strategy by incorporating more advanced scenarios. REFERENCES [1] R. Su, “Supervisor synthesis to thwart cyber attack with bounded sensor reading alterations,” Automatica, vol. 94, pp. 35–44, 2018. Fig. 2. An automated manufacturing system under attack modeled by LPN. [2] R. Meira-G´ oes, E. Kang, R. H. Kwong, and S. Lafortune, “Synthesis of sensor deception attacks at the supervisory layer of cyber–physical systems,” Automatica, vol. 121, p. 109172, 2020. [3] R. Liu, A. M. Mangini, and M. P. Fanti, “Synthesis of optimal stealthy attacks against diagnosability in labeled Petri nets,” IEEE/CAA Journal of Automatica Sinica, 2025. [4] R. Liu, Y. Hu, A. M. Mangini, and M. P. Fanti, “K-corruption intermittent attacks for violating the codiagnosability,” IEEE/CAA Journal of Automatica Sinica, vol. 12, no. 1, pp. 159–172, 2025. [5] M. Sampath, R. Sengupta, S. Lafortune, K. Sinnamohideen, and D. Teneketzis, “Diagnosability of discrete-event systems,” IEEE Transactions on Automatic Control, vol. 40, no. 9, pp. 1555–1575, 1995. [6] M. P. Cabasino, A. Giua, and C. Seatzu, “Diagnosability of discrete event systems using labeled Petri nets,” IEEE Transactions on Automation Science and Engineering, vol. 11, no. 1, pp. 144–153, 2014. [7] T. Li, H. Ren, R. Liu, M. P. Fanti, and Z. Li, “Fault diagnosis of labeled Petri nets under attacks using integer linear programming,” IEEE Transactions on Automation Science and Engineering, 2025. [8] R. Liu, W. Duan, A. M. Mangini, and M. P. Fanti, “Attack synthesis in discrete event systems under asymmetric observation setting,” IFACPapersOnLine, vol. 58, no. 1, pp. 186–191, 2024. [9] J. Yao, S. Li, and X. Yin, “Sensor deception attacks against security in supervisory control systems,” Automatica, vol. 159, p. 111330, 2024. [10] N. Ran, A. Giua, and C. Seatzu, “Enforcement of diagnosability in labeled Petri nets via optimal sensor selection,” IEEE Transactions on Automatic Control, vol. 64, no. 7, pp. 2997–3004, 2018. [11] Y. Hu, R. Liu, M. P. Fanti, and Z. Li, “Robust fault diagnosis of networked discrete event systems using labeled Petri nets,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2025. [12] S. Hu, Z. Li, and R. Wisniewski, “Optimal sensor selection for diagnosability enforcement in labeled Petri nets,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 54, no. 5, pp. 2965– 2977, 2024. [13] G. Zhu, Z. Li, N. Wu, and A. Al-Ahmari, “Fault identification of discrete event systems modeled by Petri nets with unobservable transitions,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 49, no. 2, pp. 333–345, 2017. [14] M. Zhou and F. DiCesare, Petri net synthesis for discrete event control of manufacturing systems. Springer Science & Business Media, 2012, vol. 204.