Op imal A ack S a egy Comp omising Diagnosabili y o Au oma ed
Manu ac u ing Sys ems in Labeled Pe i Ne s
Ruo ian Liu, Agos ino Ma cello Mangini, Ma ia Pia Fan i
Abs ac — This pape add esses he diagnosabili y analysis
p oblem unde malicious a acks o a disc e e e en sys em
modeled by labeled Pe i ne . We ocus on a s eal hy eplace-
men a ack o al e o co up he obse a ion o he sys em.
The aim o his wo k is, om an a acke iewpoin , o design
a s eal hy eplacemen a ack o iola ing he diagnosabili y
o sys em. To his end, we i s build a new s uc u e, called
a ack e i ie ha is used o enume a e all he a ack pa hs.
Then an op imal a ack syn hesis p oblem in e ms o minimum
ene gy cos is o mula ed by de e mining whe he a bad pa h is
gene a ed ia sol ing a se o in ege linea p og amming p ob-
lems. Finally, an au oma ed manu ac u ing sys em is p o ided
o illus a e he p oposed a ack s a egy.
I. INTRODUCTION
Faul diagnosis is c i ical o highly au oma ed manu ac-
u ing sys ems (AMSs). The a ack scena io o AMSs ha e
a ac ed much a en ion in he communi y o disc e e e en
sys ems (DESs): mainly conce ning he p oblems o a ack
de ec ion and a ack syn hesis [1], [2]. This wo k ocuses
on he a ack syn hesis p oblem wi h op imiza ion objec i es
o iola ing he diagnosabili y in DESs. In his wo k, we
conside he pe manen a ack [3] (i.e., once an a ack is
pe o med and each ansi ion is ei he associa ed wi h i s
o iginal o a eplaced label, hen all he ansi ion labels
emain unchanged) a he han in e mi en se ing [4] (i.e.,
he a acked label can be eco e ed in ini e ime).
Diagnosabili y is a sys em p ope y de e mining whe he
he occu ence o a aul can be de ec ed wi hin ini e
s eps, and has been s udied in he amewo k o au oma a
[5] and Pe i ne s [6]. Al hough ecen wo ks ocus on
diagnosabili y and aul diagnosis in he p esence o a acks,
hey p ima ily deal wi h de ec ing o ole a ing a acks a he
han syn hesizing a acks o iola e diagnosabili y, which
is he ocus o ou s udy. Fo example, he iola ion o
sa e y caused by malicious in e cep ion and al e a ion o
senso eadings is conside ed in [7]. Mo eo e , he wo k [8]
in es iga es how an a acke wi h asymme ic obse a ions
can s a egically co up ou pu s o maximize he ope a o ’s
diagnos ic unce ain y. In addi ion, he iola ion o opaci y is
s udied in [9]. The s udies [3], [4] wo ks on a ack-syn hesis
p oblems in DESs ha aim o hide he occu ence o aul s.
This wo k is a pa o he IN2CCAM p ojec . This p ojec has ecei ed
unding om he Eu opean Union’s Ho izon Eu ope esea ch and inno a ion
p og am unde g an ag eemen No. 101076791. This con en e lec s only
he au ho s’ iew and he Eu opean Commission is no esponsible o any
use ha may be made o he in o ma ion his publica ion con ains.
Ruo ian Liu, Agos ino Ma cello Mangini and Ma ia Pia Fan i a e
wi h he Depa men o Elec ical and In o ma ion Enginee ing, Poly ech-
nic Uni e si y o Ba i, I aly (e-mails: [email p o ec ed], agos inoma -
[email p o ec ed], [email p o ec ed]).
To ackle he a ack syn hesis p oblem, he e a e mainly
se e al app oaches in he li e a u e. The i s ype o ap-
p oaches [2] employs a disc e e s uc u e o model he
game-like in e ac ion be ween he supe iso and he a -
acke , which inco po a es all possible a acks; he second
one ans o ms he a ack syn hesis p oblem in o he su-
pe iso syn hesis p oblem [1]. Di e en om he exis ing
app oaches, we in oduce a modi ied labeling unc ion o
model an a ack, o making a sys em non-diagnosable by
le e aging echniques o un olded e i ie s uc u e in labeled
Pe i ne s.
The main con ibu ion o his wo k is lis ed as ollows.
Fi s , we o mula e an op imal s eal hy eplacemen a ack
p oblem in e ms o minimum ene gy cos , which is de e -
mined by sol ing a se o in ege p og amming p oblems.
Since he classic e i ie [10] can only upda e s a es when
consecu i e ansi ion pai s ha e he same obse a ion, i is
unable o gene a e bad pa hs. To sol e hese issues, we hen
de elop a new s uc u e called a ack e i ie by in eg a ing
he a ack capabili y. Finally, an illus a i e example on
au oma ed manu ac u ing sys em is p o ided o show he
p oposed a ack s a egy.
II. PRELIMINARIES
A. Basic de ini ions o Pe i ne
Le Nbe he se o non-nega i e in ege s. A Pe i ne is
de ined as a ou - uple N= (P, T, P e, P os ), whe e P=
{p1, ..., pm}is a se o m∈Nplaces, T={ 1, ..., n}is a
se o n∈N ansi ions wi h P∪T=∅and P∩T=∅,
P e :P×T→Nand P os :P×T→Na e he p e- and
pos -incidence ma ices, espec i ely, deno ing he weigh o
he a cs om places o ansi ions and ansi ions o places.
The incidence ma ix o a ne is de ined by C=Pos −P e.
A Pe i ne is said o be acyclic i he e is no di ec ed cycle.
A ma king is a mapping M:P→N ha assigns o a
place o a Pe i ne a non-nega i e in ege o okens. M(pi)
is he numbe o okens in place pia a ma king M. A ne
sys em ⟨N, M0⟩is a ne Nwi h an ini ial ma king M0. A
ansi ion ∈Tis enabled a a ma king Mi M≥P e(·, )
and may i e yielding a ma king M′=M+C(·, ). We w i e
M[σ⟩ o deno e ha a ansi ion sequence σ= 1 2· · · i∈
T∗is enabled a M, and M[σ⟩M′ o deno e ha he i ing
o σyields M′. The Pa ikh ec o o σis deno ed by π(σ) :
T→Nnand maps a ansi ion ∈T o he numbe o
occu ences o in σ.
A ma king Mis eachable in ⟨N, M0⟩i he e exis s a
i ing sequence σ∈T∗such ha M0[σ⟩M. The se o all
ma kings eachable om M0, deno ed by R(N, M0), de ines
he eachabili y se o ⟨N, M0⟩, i.e., R(N, M0) = {M∈
Nm|M0[σ⟩M}. The se o ansi ion sequences enabled a
he ini ial ma king M0is de ined as L(N, M0) = {σ∈T∗|
M0[σ⟩}.Gi en a se H⊆L(N, M0),we deno e H/σ he
pos ansi ion sequence o Ha e σ, i.e., H/σ ={σ′∈T∗|
σσ′∈H}. A ne sys em ⟨N, M0⟩is said o be: bounded i
i exis s an in ege k∈Nsuch ha o all M∈R(N, M0)
and o all pi∈P, M(pi)≤kholds; deadlock- ee i o all
M∈R(N, M0), he e exis s ∈T, M[ ⟩.
B. Labeled Pe i ne
Gi en a Pe i ne N= (P, T, P e, P os )and an e en
se Σ, a labeling unc ion l:T→Σ∪ {ε}= Σεassigns
o a ansi ion ei he a symbol om he e en se Σo he
emp y s ing symbol ε. A labeled Pe i ne (LPN) sys em
S=⟨N, Σ, l, M0⟩is a Pe i ne sys em ⟨N, M0⟩wi h a
labeling unc ion land an e en se Σ. A ansi ion is said
o be unobse able i i is associa ed wi h he emp y s ing ε,
i.e., l( ) = ε. The se o unobse able ansi ions is deno ed
by Tu={ ∈T|l( ) = ε}. The o he ansi ions labeled
wi h e en s om Σa e called obse able ansi ions, deno ed
as To={ ∈T|l( )∈Σ}. Fu he mo e, he se Tucan be
di ided in o wo disjoin se s T and T eg wi h Tu=T ∪
T eg, whe e T and T eg deno e he se s o aul ansi ions
and egula unobse able ansi ions, espec i ely.
The labeling unc ion can be ex ended o a ansi ion
sequence σ= 1 2· · · isuch ha ω=l(σ) = l( 1)l( 2)· · ·
l( i),which is called an obse a ion co esponding o he
sequence σ. Gi en a ne sys em ⟨N, Σ, l, M0⟩, we de ine
l−1(ω)as he se o all ansi ion sequences consis en wi h
ω∈Σ∗
ε,i.e., l−1(ω) = {σ∈L(N, M0)|l(σ) = ω}.
The language gene a ed by an LPN sys em Sis de ined as
L(N, M0) = {ω∈Σ∗
ε| ∃σ∈L(N, M0) : ω=l(σ)}.
C. Ex ended basis eachabili y g aphs
In his pa , we ecall necessa y no ions o he ex ended
basis ma kings in [6], [11], whe e he obse able ansi ion
se is assumed o be Tα
o=To∪T . Gi e a ansi ion sequence
σ∈T∗, we deno e by P eg(σ)( esp., Pα
o(σ)) he p ojec ion
o σo e T eg ( esp., Tα
o). Mo eo e , he es ic ion o
incidence ma ix Co an LPN sys em o T eg is deno ed
by C eg.
De ini ion 2.1 ( [6]): Gi en a ma king M∈R(N, M0)
and a ansi ion ∈Tα
oo an LPN sys em S=⟨N, Σ, l, M0⟩,
he se o explana ions o a Mis de ined by Σ(M, ) =
{σ∈T∗
eg |M[σ⟩M′, M′[ ⟩},and he se o hei e- ec o
is deno ed as Y(M, ) = {π(σ)|σ∈Σ(M, )}. In addi ion,
he se o minimal explana ions o a Mis deno ed by
Σmin(M, ) = {σ∈Σ(M, )|∄σ′∈Σ(M, ) : π(σ′)⪇
π(σ)}and he minimal e- ec o is de ined as Ymin(M, ) =
{π(σ)|σ∈Σmin(M, )}.
The se o ex ended basis ma kings, deno ed as Xe, is
ecu si ely compu ed as ollows: M0∈Xe; I M∈Xe,
hen o each ∈To∪T , y =π(σ)∈Ymin(M, ),
(M′=M+C eg ·y+C(·, )) ⇒(M′∈Xe).The ex ended
basis eachabili y g aph (EBRG) o Sis a nonde e minis ic
ini e s a e au oma on Ge= (Xe, E, δ, M0), whe e Xeis
he se o s a es; E⊆(To×Σ) ∪(T × {ε})is he se o
e en labels; δ⊆Xe×E×Xeis he ansi ion ela ion;
and M0is he ini ial s a e. A non ailu e EBRG, deno ed by
Ge,n = (Xe,n, En, δn, M0,n), is he EBRG de i ed om
⟨N′,Σ, l′, M0⟩ ollowing he assump ion ha he se o
obse able ansi ions is equal o To.
III. DIAGNOSABILITY ANALYSIS PROBLEM WITH
ATTACKS
A. Replacemen and s eal hy a ack
To cha ac e ize he capabili y o an in ude ha masks he
ansi ion labels, an a ack s uc u e is p esen ed as ollows.
De ini ion 3.1 (A ack s uc u e): Le S=⟨N, Σ, l, M0⟩
be an LPN sys em. An a ack s uc u e is de ined as he
se A∈2(To×Σε)×(To×Σε), i.e., Ais a se o ansi ion pai s,
each associa ed o i s label: he i s ansi ion is associa ed
o he o iginal label while he second one is associa ed o
he eplaced label.
To make he exposi ion clea , we deno e by Ta={ ∈
To| ∃e′∈Σε,(( , e),( , e′)) ∈ A} he se o a acked
ansi ions ha can be a ge ed wi h espec o A, and deno e
by ΣA( ) = {e′∈Σε|(( , e),( , e′)) ∈ A, ∈Ta, e =l( )}
he se o eplaced labels associa ed wi h ansi ion while
aking in o accoun he a ack s uc u e A. We deno e by
lA( ) = {e|l( ) = e}∪{e′|e′∈ΣA( )}.
De ini ion 3.2 (Replacemen a ack): Le S=⟨N, Σ, l,
M0⟩be an LPN sys em and Abe an a ack s uc u e. A
eplacemen a ack A(a ack o sho ) is a modi ied labeling
unc ion ha is he mapping la:T∗→Σ∗
εwhe e
•la(ε) = ε,
•la( ) = l( )i ∈T Ta,
l( )o e′∈ΣA( )i ∈Ta,
•la(σ ) = la(σ)la( ), σ ∈T∗, ∈T.
Unde he a ack A, each ansi ion ∈Tais ei he
associa ed wi h he o iginal label l( )o a eplaced label
e′∈ΣA( ). Subsequen ly, he gi en a ack s uc u e Amay
cause mul iple a ack op ions. The conside ed eplacemen
a ack includes a pa icula emo al case, such as when an
obse able ansi ion is associa ed wi h an emp y s ing.
De ini ion 3.3 (S eal hy a ack): Gi en an LPN sys em
S=⟨N, Σ, l, M0⟩unde an a ack Ai, he a ack Aiis said
o be s eal hy i o any ansi ion sequence σ, i s co up ed
obse a ions a e con ained in he language o LPN sys em,
i.e., ∀σ∈L(N, M0), lai(σ)∈ L(N, M0).
P ecisely, s eal hiness equi es ha he se o co up ed
obse a ions is con ained in he se o obse a ions wi hou
a acks.
B. Diagnosabili y
The aul ansi ion se T can be pa i ioned in o classes
Ti
, whe e i= 1, . . . , . Fo he sake o simplici y, his wo k
conside s an LPN wi h a single aul class, i.e., T =T1
.
Ne e heless, he p oposed app oach could be ex ended o he
ne s wi h mul iple aul classes wi h a sligh modi ica ion o
he me hod p oposed in [5] o his pu pose.
Le T′be a subse o T. We de ine ψ(T′) = {σ ∈
L(N, M0)|σ∈T∗, ∈T′}as he se o i ing sequences
in L(N, M0) ha end wi h a ansi ion ∈T′.
De ini ion 3.4 ( [6]): An LPN sys em S=⟨N, Σ, l, M0⟩
ha ing no deadlock a e he occu ence o a aul ∈T ,
is diagnosable wi h espec o he aul ansi ion se T i
∀σ′∈ψ(T ),∃K∈N,∀σ′′ ∈L(N, M0)/σ′,
|σ′′| ≥ K=⇒ ∀σ∈l−1(l(σ′σ′′)),∃ ∈T : ∈σ.
C. P oblem s a emen
Be o e o mula ing he add essed p oblem, we i s p esen
a no ion o op imali y c i e ion, i.e., minimum cos . Speci i-
cally, each ansi ion is associa ed wi h a eplacemen a ack
cos , i.e., a non-nega i e eal alue, which desc ibes he
di icul y o a ack o eplacing i s ansi ion label. The
highe he alue o he cos o he a ack is, he mo e di icul
he a ack on he ansi ion is, o he wise i is easie . In he
es o his wo k, we e e he op imal a ack o he minimum
cos one, and ocus on he ollowing p oblem:
P oblem 1: Gi en an LPN sys em S=⟨N, Σ, l, M0⟩
ha is ulne able o an a ack s uc u e A, he objec i e
is o design an op imal s eal hy eplacemen a ack Ai o
iola ing he diagnosabili y in he LPN sys em.
The ollowing assump ions hold o he diagnosabili y
analysis unde he a acks in he LPN sys ems.
A1) The LPN sys em is bounded and deadlock- ee a e
he occu ence o a aul .
A2) The Tu-induced subne is acyclic.
A3) The e exis s a nonemp y se o p ede e mined s eal hy
a acks As={As1, . . . , Asθ}, wi h 1≤θ≤Π ∈Ta[(|ΣA|
+ 1)] −1based on he a ack s uc u e A.
IV. OPTIMAL ATTACK AGAINST DIAGNOSABILITY
In his sec ion, we i s p esen an a ack e i ie ha lis s
all he a ack pa hs o be ans o med in o bad pa hs leading
o he iola ion o diagnosabili y. Then, an op imal a ack can
be ob ained by sol ing a se o linea p og amming p oblems.
A. A ack Ve i ie
An a ack e i ie Ua= (XU
a, EU
a, δU
a, MU
0)is a ini e
s a e au oma on, ha shows all he possible a acked pa hs,
p esen ed in Algo i hm 1.
S ep 1 ini ializes he se o s a es, ansi ions, e en s, and
he ini ial s a e in he a ack e i ie . The main pa in lines
2–15, a each un agged s a e, i e a i ely gene a es all he
o he s a es. In his p ocess, o each ansi ion pai ( i, j),
whe e i∈To∪T and j∈To, he e i ie adds a
new s a e (M′
1, α′;M′
2)i he ansi ions (M1, i, M′
1)∈δ,
(M2, j, M′
2)∈δnand non-emp y se lA( 1)∩lA( 2)hold
om he cu en s a e (M1, α;M2). By accoun ing o an-
si ions wi h he same obse a ion unde a ack, he p oposed
e i ie cap u es a ack pa hs ha may exploi di e ences in
obse a ion, which classical e i ie s would igno e. No e ha
αcan be ei he N o ep esen he no mal beha io o sys em
wi hou he occu ence o aul om he ini ial s a e o his
one, o F o deno e he occu ence o aul y beha io o
sys em.
Algo i hm 1: Cons uc ion o an a ack e i ie
Inpu : EBRGs Ge= (Xe, E, δ, M0),Ge,n = (Xe,n,
En, δn, M0,n), and a ack s uc u e A
Ou pu : An a ack e i ie Ua= (XU
a, EU
a, δU
a, MU
0)
1Le XU
a={(M0, N;M0)},EU
a=∅, δU
a=∅,
MU
0= (M0, N;M0)be he ini ial s a e ;
2while s a es wi h no ag exis do
3selec a s a e (M1, α;M2) wi h no ag ;
4i (M1, α;M2) is same as a s a e in he pa h
om MU
0 o i hen
5 ag i “duplica e” and go o S ep 2;
6 o all 1∈To∪T and 2∈To,do
7i (M1, 1, M′
1)∈δ, (M2, 2, M′
2)∈
δn, lA( 1)∩lA( 2)=∅ hen
8add a s a e (M′
1, α;M′
2)and a ansi ion
( 1, 2) om (M1, α;M2) o
(M′
1, α;M′
2);
9i 1∈T ,(M1, 1, M′
1)∈δ hen
10 add a s a e (M′
1, F;M2)and a ansi ion
( 1, λ) om (M1, α;M2) o
(M′
1, F;M2);
11 i 1∈To,(M1, 1, M′
1)∈δ, ε ∈lA( 1) hen
12 add a s a e (M′
1, α;M2)and a ansi ion
( 1, λ) om (M1, α;M2) o (M′
1, α;M2);
13 i 2∈To,(M2, 2, M′
2)∈δn, ε ∈lA( 2) hen
14 add a s a e (M1, α;M′
2)and a ansi ion
(λ, 2) om (M1, α;M2) o
(M1, α;M′
2);
15 ag he s a e (M1, α;M2)“old”.
The ollowing de ini ion p esen s he no ion o bad pa h
ha leads o he iola ion o diagnosabili y. P ecisely, he
exis ence o his ype o pa h shows ha , wo a bi a ily
long ansi ion sequences o LPN sys em ha e he same
obse a ion unde a ack and one o hem con ains he aul
ansi ion, such ha he occu ence o he aul canno be
de ec ed in a ini e numbe o s eps. Gi en an au oma on G,
we w i e Mσ
−→
GM′ o deno e ha M′is eached in G om
Mwi h a sequence σ.
De ini ion 4.1: Le S=⟨N, Σ, l, M0⟩be an LPN sys em,
Xebe he se o ex ended basis ma kings, and Uabe a a ack
e i ie cons uc ed by i s wo EBRGs Geand Ge,n. A pa h
eσ= (γi1, γj1)(γi2, γj2)· · · (γik, γjk)in Uais called a bad
pa h i , by le ing σα=γi1· · · γiq, σβ=γiq+1 · · · γik, σ′
α=
γj1· · · γjq, and σ′
β=γjq+1 · · · γjk, he e exis M, M′∈
Xeand an a ack Aico esponding o he modi ied labeling
unc ion laisa is ying:
(1) M0
σα
−−→
Ge
Mσβ
−−→
Ge
M;
(2) M0
σ′
α
−−−→
Ge,n
M′σ′
β
−−−→
Ge,n
M′;
(3) lai(σα) = lai(σ′
α)and lai(σβ) = lai(σ′
β);
(4) ∈σασβ;
(5) no p e ix o eσsa is ies i ems (1)–(4).
P oposi ion 4.2: An LPN sys em ⟨N, Σ, l, M0⟩sa is ying
(A1)–(A2) is diagnosable i and only i i s a ack e i ie Ua
has no bad pa hs.
P oo : Following De ini ion 4.1 and a esul p o ed in
[10], [12] ha he LPN sys em is diagnosable i and only
i i s classic un olded e i ie has no such a pa h, i could
easily ex end in o ou esul .
Using Algo i hm 1, we enume a e all pa hs bu ocus only
on hose ha can be a acked in o a bad pa h ha iola es
he diagnosabili y o he sys em. The ollowing de ini ion
p esen s such an a ack pa h.
De ini ion 4.3: A pa h eσ= (γi1, γj1)(γi2, γj2)· · · (γik,
γjk)in Uais called a ack pa h i σα=γi1· · · γiq, σβ=
γiq+1 · · · γik, σ′
α=γj1· · · γjq, and σ′
β=γjq+1 · · · γjk, he e
exis M, M′∈Xe, such ha (i) he condi ions (1)(2)(4)(5)
in De ini ion 4.1 hold and (ii) an a acked ansi ion ∈Ta
exis s such ha ∈σασβo ∈σ′
ασ′
β.
B. Op imal a ack de e mina ion
Be o e o mally desc ibing he a ack s a egy, we p esen
some necessa y no ions o minimum cos a ack o i-
ola ing he diagnosabili y. We deno e by he ow ec o
c= [c1, . . . , cj, . . . , c|T|] he a ack cos coe icien ec o ,
ha associa es a non-nega i e eal alue cj o each possible
a acked ansi ion j∈To, and assigns cj= 0 o each an-
si ion j∈Tu, whe e cj= 0 means ha ansi ion jcanno
be a acked. Now, gi en an a ack pa h eσk= (σk,1, σk,2),
in o de o selec he possible a acks o iola ing he
diagnosabili y, we de ine a ec o k= [ 1,k, . . . , j,k,...,
|T|,k]T. In pa icula , j,k ∈ {0,1} o j= 1,...,|T|is
a bina y decision a iable and j,k = 1 ( esp., j,k = 0)
means ha he ansi ion label o jhas ( esp., has no ) been
eplaced unde he eplacemen a ack A. Mo eo e , i holds
j,k = 0 o he se o ansi ions T Ta ha canno be
a acked.
Fo he sake o cla i y, we deno e by ejand e′
j he o iginal
label o ansi ion and one eplaced label o ansi ion j,
i.e., ej=l( j)and e′
j∈ΣA( j), espec i ely. Based on
he a o emen ioned no ions, gi en a ansi ion jand i s
co esponding ansi ion label pai (ej, e′
j), he co up ed
obse a ion o ansi ion jcan be exp essed as j,k ·e′
j+
(1 − j,k)·ej. P ecisely, in he case ha j,k = 1 has he
co up ed obse a ion 1·e′
j=e′
j, while j,k = 0 holds i s
o iginal obse a ion wi h (1−0)ej=ej. When he sequence
σis unde an a ack Ai, we can de i e i s comp omised
obse a ion using he ollowing exp ession
lai(σ)=Πj|σ|
j=j1[ j,k ·e′
j+ (1 − j,k)ej].
De ini ion 4.4 (Co up ed op ion): Gi en an LPN sys em
S ulne able o an a ack s uc u e A, a co up ed op ion
Cis de ined as: each ansi ion j∈Tais associa ed wi h
a co up ed label e′
j∈ΣA( j), in which he amoun o
co up ed op ions is equal o Π ∈Ta|ΣA( )|. And he se
o co up ed op ions is deno ed by C(A) = {Ci|i=
1,...,Π ∈Ta|ΣA( )|}.
Gi en an a ack pa h and a co up ed op ion, he ollowing
lemma cha ac e izes he possible a acks Ai o iola ing he
diagnosabili y.
Lemma 4.5: Le us conside he k- h a ack pa h eσk=
(σk,1, σk,2)wi h σk,1=σα,kσβ,k and σk,2=σ′
α,kσ′
β,k.
Gi en an a ack s uc u e Aand a co up ed op ion C,
he a acks Ai o gene a e a bad pa h o iola ing
he diagnosabili y a e de e mined by he ec o s k=
[ 1,k, . . . , j,k, . . . , |T|,k]T ha sa is y he ollowing con-
s ain s:
a) j,k ∈ {0,1} ∀ j∈Ta
b) j,k = 0 ∀ j∈T Ta
c) Πj|σα,k|
j=j1[ j,k ·e′
j+ (1 − j,k)ej]
= Π
j′
|σ′
α,k|
j=j′
1[ j,k ·e′
j+ (1 − j,k)ej]
d) Πj|σβ,k|
j=j1[ j,k ·e′
j+ (1 − j,k)ej]
= Π
j′
|σ′
β,k|
j=j′
1[ j,k ·e′
j+ (1 − j,k)ej]
(1)
P oo : Cons ain s (a) show ha each ansi ion j∈Ta
is associa ed wi h a bina y decision a iable j,k ∈ {0,1}.
Cons ain s (b) impose j,k = 0 o he se o ansi ions
T Ta. By pe o ming an a ack Ai ha is he modi ied
labeling unc ion lai, cons ain s (c)(d) gua an ee ha wo
sequences σk,1=σα,kσβ,k and σk,2=σ′
α,kσ′
β,k gene a e he
same obse a ion, i.e., lai(σα,k) = lai(σ′
α,k)and lai(σβ,k) =
lai(σ′
β,k).
In he ollowing, cons ain s (1.c) and (1.d) a e linea ized
by eplacing hem wi h he cons ain s (2.c) and (2.d):
a) j,k ∈ {0,1} ∀ j∈Ta
b) j,k = 0 ∀ j∈T Ta
c) Pj|σα,k|
j=j1[ j,k ·e′
j+ (1 − j,k)ej]
=Pj′
|σ′
α,k|
j=j′
1[ j,k ·e′
j+ (1 − j,k)ej]
d) Pj|σβ,k|
j=j1[ j,k ·e′
j+ (1 − j,k)ej]
=Pj′
|σ′
β,k|
j=j′
1[ j,k ·e′
j+ (1 − j,k)ej].
(2)
The ollowing lemma es ablishes he ela ionship be ween
ec o s ksa is ying cons ain s (1) and ec o s ksa is ying
cons ain s (2).
Lemma 4.6: I ec o ksa is ies cons ain s (1), hen i
also sa is ies cons ain s (2).
P oo : Cons ain s (2.c) (2.d) ensu e ha wo sequences
σk,1and σk,2gene a e he same amoun o ansi ion labels
(wi hou equi emen on he label o de ), while cons ain s
(1.c) (1.d) gua an ee ha wo sequences gene a e he same
obse a ion (wi h equi emen on he label o de ). Hence, i
can be deduced ha ec o ksa is ies cons ain s (1), hen
i also sa is ies cons ain s (2).
By Lemma 4.6, we can deduce ha he se o easible
solu ions o cons ain s (1) is a subse o he se o easible
solu ions o cons ain s (2). To o malize he new p oblem
we in oduce a se o ec o s Vk, whe e each elemen
k∈Vksa is ies cons ain s (2) bu iola es cons ain s (1).
To ensu e hese in easible solu ions ka e excluded om
he solu ion o ollowing ILP P oblem 2, addi ional linea
cons ain s a e de ined using a ec o yk o each k∈Vk
wi h y j,k ∈ {0,1} o j= 1,...,|T|.
ILP P oblem 1: Conside an a ack s uc u e A, an a ack
cos coe icien ec o cand a se o ec o s Vk ha sa is ies
cons ain s (2) bu does no sa is y cons ain s (1). The
minimum a ack cos zkin e ms o k- h a ack pa h and a
co up ed op ion C, co esponding o a ack Ak o iola ing
he diagnosabili y can be ob ained by sol ing he ollowing
ILP p oblem:
zk= min c· k,
s. . he se o cons ain s (2),
e.1) y j,k ∈ {0,1} ∀ j∈T,
e.2) Pj=|T|
j=1 y j,k ≥1
e.3) y j,k ≤ j,k + j,k ≤2−y j,k ∀ j∈T, ∀ k∈Vk.
Cons ain s (e.2) and (e.3) linea ize k= kby en o cing
ha he e exis s a leas one a iable y j,k ≥1. Indeed, i
k= k, hen each y j,k = 0 and cons ain (e.2) is no
sa is ied.
C. Algo i hm o op imal s eal hy eplacemen a ack
In he ollowing, Algo i hm 2 ou lines he s eps o compu e
his op imal s eal hy eplacemen a ack.
Algo i hm 2: Compu a ion o an op imal s eal hy
eplacemen a ack
Inpu : An a ack e i ie Ua= (XU
a, EU
a, δU
a, MU
0),
an a ack s uc u e A, a se o s eal hy a acks
Asand an a ack cos coe icien ec o c.
1Lis all he a ack pa hs Π = {eσ1,...,eσk,...,eσh}
om Uaby De ini ion 4.3 and ob ain all he
co up ed op ions C(A);
2Ini ialize k= 1, Z =∅, Vk=∅;
3 o all eσk∈Πdo
4 o each co up ed op ion C ∈ C(A)do
5Rese Vk=∅;
6i he ILP P oblem 1 is easible hen
7i he solu ion ksa is ies cons ain s (1)
and he co esponding Ak∈ As hen
8zkis he objec i e alue o solu ion
k;
9i zk= ˆc hen
10 bzk=zk,b
Ak=Ak, go o S ep 17;
11 else
12 Z={zk} ∪ Z, Vk=Vk∪ { k};
13 else
14 k= k;
15 Vk=Vk∪ { k}and go o S ep 6;
16 bz= min
zk
Z;
17 Re u n kand b
Ak;
S ep 1 ob ains all he a ack pa hs in he a ack e i ie
Uaby he condi ions in De ini ion 4.3 and all he co up ed
op ions C(A). S ep 2 ini ializes he index k, he se Z ha
con ains he a ack cos s co esponding o he compu ed
a acks, and he se Vkcon aining he easible solu ions o
ILP p oblem 2 ha sa is y cons ain s (1). The main pa
(s eps 3–15) analyzes each a ack pa h un il he a ack cos
is op imal (i.e., minimum cos ) o all he a ack pa hs ha e
been analyzed.
Theo em 4.7: Gi en an LPN sys em Ssa is ying Assump-
ions (A1)–(A3) ulne able o an a ack s uc u e A, he
a ack A o iola ing he diagnosabili y o he sys em S
ha is compu ed by Algo i hm 2 is op imal.
P oo : Fo each pa h eσk, he algo i hm ob ains all he
possible a acks Akco esponding o he pa h eσkand all he
co up ed op ions C(A). Fo each co up ed op ion C, he se
Vkcon aining he easible solu ions o ILP p oblem 1 and
no sa is ying cons ain s (1) is i s ly ese as emp y se . By
Lemma 4.7, he pa (s eps 6–15) analyzes he minimum cos
a ack co esponding he pa h eσkand his co up ed op ion
by gua an eeing he easibili y o solu ion, sa is ying he
cons ain s (1) and ensu ing he s eal hiness o a ack (s ep
7), i.e., he ob ained a ack should be con ained in he se o
gi en s eal hy a ack As. Pa icula ly, i he o al a ack cos
zkis equal o i s minimum coe icien ˆc, i.e., ˆc= min
{j| j∈To}cj,
i implies ha a minimum cos a ack bzkis ob ained, such ha
he algo i hm e u ns he co esponding a ack b
Ak. O he wise
i s o es he a ack cos zkin he cos se Z. A e analyzing
all pa hs, we ob ain he minimum cos bzk om Zand i s
co esponding a ack b
Ak.
V. A CASE STUDY ON AUTOMATED MANUFACTURING
SYSTEM
In his sec ion, o demons a e he p oposed a ack ap-
p oach, we conside an au oma ed manu ac u ing sys em
(AMS) aken om [13], [14], as shown in Fig. 1. This
sys em consis s o wo en ies (I1 and I2), wo exi s (O1
and O2), i e machines (M1–M5), wo bu e s wi h capaci y
4 (B1 and B2), ou obo s (R1–R4), and wo AGVs (AGV1
and AGV2). I inco po a es wo sepa a e p oduc ion lines
ha manu ac u e di e en p oduc s, as summa ized below.
Du ing ope a ion, Robo s R1 and R2 se e bo h lines: Robo
R1 suppo s Machines M1, M2, and M4, while Robo R2
handles pa s om M3 and M5.
Line 1: R1 loads s ock om I1 in o M1/M2, R3 ou es
he iden ical in e media es h ough B1 o M3, and R2 pu s
he inished pieces on AGV1, which deli e s hem o O1 and
b ings esh ma e ial. Line 2 mi o s his p ocess whe e R1
eeds M4 om I2, R4 mo es in e media es ia B2 o M5,
and R2 places he ou pu on AGV2 o O2 be o e picking
up new s ock.
The Pe i ne model o he conside ed AMS is shown in
Fig. 2. The meaning o each place and each ansi ion is
desc ibed in de ail in [14]. In Fig. 2, he se o unobse able
ansi ions Tu={ 7, 9, 12, 17, 21, 22}wi h wo aul
ansi ions 21( 1)and 22( 2). In de ail, 1 ep esen s a
si ua ion ha a aw ma e ial om en y I1 is di ec ly pu
in o bu e B1 wi hou being p ocessed by M1 o M2 and
Fig. 1. An au oma ed manu ac u ing sys em.
2deno es ano he si ua ion ha an in e media e pa a e
p ocessing by M4 is hen machined by M5, wi hou being
pu in o he bu e B2.
The se o obse able ansi ions To=T Tuwi h
l( 1) = a, l( 2) = l( 3) = l( 13) = b, l( 4) = l( 5) =
c, l( 6) = d, l( 8) = l( 15) = e, l( 10) = l( 19) = , l( 11) =
g, l( 14) = l( 16) = h, l( 18) = l( 20) = k. We now explo e
he e ec i eness o he a ack s a egy p oposed in his pape .
Suppose ha an a acke can hijack he senso s a Robo s
1–4, and has he a ack capabili y by emo ing he label o
ansi ion 2and eplacing he label o ansi ion 4( esp.,
13) om c o d ( esp., om b o c), i.e., he a ack s uc u e
A={( 2(b), 2(ε)),( 4(c), 4(d)),( 13(b), 13(c))}.
By implemen ing Algo i hm 2, i e u ns he ollowing
esul s wi h a compu a ional ime 2.35 mins ha e e s o
he CPU seconds o a lap op wi h In el CPU Co e 2.3
GHz, 8GB memo y and a Ma lab ool. Speci ically, an
a ack pa h eσ1= ( 1, 1)( 21, 2)( 13, 13)( 14, 14)( 15, 15)
( 16, 16)( 17, 17)( 18, 18)( 19, 19)( 20, 20)and he co -
up ed op ion C1={e′
2=ε, e′
4=d, e′
13 =c}, we ge he
solu ion 1=[0100000000000000000000]T
and i s minimum a ack cos z1= 1, which gene a es a bad
pa h wi h la1(σ1,1) = la1(σ1,2) = a(bhek k), such ha he
sys em becomes non-diagnosable.
VI. CONCLUSION
Algo i hms add essing s eal hy eplacemen a acks ha
unde mine diagnosabili y in disc e e e en sys ems ha e been
de eloped. We cons uc ed an a ack e i ie o enume a e
all a ack pa hs leading o he iola ion o diagnosabili y. In
addi ion, we o mula ed he op imal a ack syn hesis as a
se o ILP p oblems, and sol ed hem o ob ain he op imal
a ack. Fu u e wo k will i s ex end he p oposed a ack
s a egy by inco po a ing mo e ad anced scena ios.
REFERENCES
[1] R. Su, “Supe iso syn hesis o hwa cybe a ack wi h bounded
senso eading al e a ions,” Au oma ica, ol. 94, pp. 35–44, 2018.
Fig. 2. An au oma ed manu ac u ing sys em unde a ack modeled by LPN.
[2] R. Mei a-G´
oes, E. Kang, R. H. Kwong, and S. La o une, “Syn hesis
o senso decep ion a acks a he supe iso y laye o cybe –physical
sys ems,” Au oma ica, ol. 121, p. 109172, 2020.
[3] R. Liu, A. M. Mangini, and M. P. Fan i, “Syn hesis o op imal s eal hy
a acks agains diagnosabili y in labeled Pe i ne s,” IEEE/CAA Jou nal
o Au oma ica Sinica, 2025.
[4] R. Liu, Y. Hu, A. M. Mangini, and M. P. Fan i, “K-co up ion
in e mi en a acks o iola ing he codiagnosabili y,” IEEE/CAA
Jou nal o Au oma ica Sinica, ol. 12, no. 1, pp. 159–172, 2025.
[5] M. Sampa h, R. Sengup a, S. La o une, K. Sinnamohideen, and
D. Teneke zis, “Diagnosabili y o disc e e-e en sys ems,” IEEE T ans-
ac ions on Au oma ic Con ol, ol. 40, no. 9, pp. 1555–1575, 1995.
[6] M. P. Cabasino, A. Giua, and C. Sea zu, “Diagnosabili y o disc e e
e en sys ems using labeled Pe i ne s,” IEEE T ansac ions on Au-
oma ion Science and Enginee ing, ol. 11, no. 1, pp. 144–153, 2014.
[7] T. Li, H. Ren, R. Liu, M. P. Fan i, and Z. Li, “Faul diagnosis o
labeled Pe i ne s unde a acks using in ege linea p og amming,”
IEEE T ansac ions on Au oma ion Science and Enginee ing, 2025.
[8] R. Liu, W. Duan, A. M. Mangini, and M. P. Fan i, “A ack syn hesis in
disc e e e en sys ems unde asymme ic obse a ion se ing,” IFAC-
Pape sOnLine, ol. 58, no. 1, pp. 186–191, 2024.
[9] J. Yao, S. Li, and X. Yin, “Senso decep ion a acks agains secu i y in
supe iso y con ol sys ems,” Au oma ica, ol. 159, p. 111330, 2024.
[10] N. Ran, A. Giua, and C. Sea zu, “En o cemen o diagnosabili y in
labeled Pe i ne s ia op imal senso selec ion,” IEEE T ansac ions on
Au oma ic Con ol, ol. 64, no. 7, pp. 2997–3004, 2018.
[11] Y. Hu, R. Liu, M. P. Fan i, and Z. Li, “Robus aul diagnosis o
ne wo ked disc e e e en sys ems using labeled Pe i ne s,” IEEE
T ansac ions on Sys ems, Man, and Cybe ne ics: Sys ems, 2025.
[12] S. Hu, Z. Li, and R. Wisniewski, “Op imal senso selec ion o
diagnosabili y en o cemen in labeled Pe i ne s,” IEEE T ansac ions
on Sys ems, Man, and Cybe ne ics: Sys ems, ol. 54, no. 5, pp. 2965–
2977, 2024.
[13] G. Zhu, Z. Li, N. Wu, and A. Al-Ahma i, “Faul iden i ica ion
o disc e e e en sys ems modeled by Pe i ne s wi h unobse able
ansi ions,” IEEE T ansac ions on Sys ems, Man, and Cybe ne ics:
Sys ems, ol. 49, no. 2, pp. 333–345, 2017.
[14] M. Zhou and F. DiCesa e, Pe i ne syn hesis o disc e e e en con ol
o manu ac u ing sys ems. Sp inge Science & Business Media, 2012,
ol. 204.
