基于雙向觀測器的隨機離散事件系統(tǒng)的不透明性

亓國照，劉富春，崔洪剛

（廣東工業(yè)大學(xué) 計算機學(xué)院，廣東 廣州 510006）

離散事件系統(tǒng)是由離散事件按照一定的運行規(guī)則相互作用而導(dǎo)致狀態(tài)演化的一類動態(tài)系統(tǒng)，在軍事國防、交通控制、計算機集成制造系統(tǒng)、電子通訊網(wǎng)絡(luò)、機器人技術(shù)等領(lǐng)域都有成功應(yīng)用[1-5]。近年來，離散事件系統(tǒng)的不透明性(opacity)研究引起了國內(nèi)外眾多學(xué)者的廣泛關(guān)注。離散事件系統(tǒng)的不透明性在數(shù)字簽名、信息認證、數(shù)據(jù)加密等信息安全機制中有著重要應(yīng)用[6-9]。

文獻[10-12]研究系統(tǒng)的不透明性驗證，并提出了多種不同類型的不透明性。文獻[10]使用監(jiān)督控制的方法確保系統(tǒng)不透明性。文獻[13]中K步不透明性首先被提出。K步不透明性用來驗證入侵者能否確定系統(tǒng)在特定時刻之后的K個狀態(tài)是否存在秘密狀態(tài)。文獻[14]提出，當(dāng)K趨于無窮時，K步不透明度變?yōu)闊o窮步不透明度。文獻[14]提出了一種改進的方法，使用了一種稱為雙向觀測器的結(jié)構(gòu)。文獻[15]在隨機離散事件系統(tǒng)中研究無窮步不透明性和K步不透明性，并提出隨機無窮步不透明性和隨機K步不透明性。

本文繼續(xù)文獻[14-15]的工作，將文獻[14]提出的雙向觀測器引入至隨機離散事件系統(tǒng)，提出一種基于雙向觀測器的隨機無窮步不透明性和隨機K步不透明性驗證方法。首先對隨機無窮步不透明性和隨機K步不透明性進行形式化定義。然后運用文獻[15]中的方法，構(gòu)造 (G,p) 的反向自動機GR，進而得到(G,p)的 雙向觀測器。通過(G,p)的雙向觀測器得到含有秘密狀態(tài)的映射集，再以 (G,p)含有秘密狀態(tài)的映射集構(gòu)建驗證器，得到一個基于雙向觀測器驗證系統(tǒng)隨機無窮步不透明性和隨機K步不透明性的充分必要條件。最后提出一個基于雙向觀測器的隨機無窮步不透明性和隨機K步不透明性驗證算法。

1 系統(tǒng)模型

經(jīng)典離散事件系統(tǒng)表示為式（1）的不確定自動機[1]

式中：X為狀態(tài)集，Σ 為事件集，δ ：X×Σ →2X是狀態(tài)轉(zhuǎn)移函數(shù)，X0?X為初始狀態(tài)集。用Σ?表 示Σ 中元素的所有有限長度字符串的集合，包括空串 ?。語句L?Σ?是有限長度字符串Σ?的 子集。通常，Σ可劃分為兩個集合：可觀測事件集合Σobs和不可觀測事件集合Σuo。并且Σobs∩Σuo=?∧Σobs∪Σuo=Σ。自然映射P:Σ?→Σo?bs可以遞歸定義為：P(ts)=P(t)P(s),t∈Σ,s∈Σ?。當(dāng)t∈Σobs時，P(t)=t；當(dāng)t∈Σuo∪{?} 時，P(t)=?。

而隨機離散事件系統(tǒng)[2]是在經(jīng)典離散事件系統(tǒng)的基礎(chǔ)上附加一個概率結(jié)構(gòu)，通常用一個隨機有窮自動機 (G,p)表 示，其中G=(X,Σ,δ,X0)是一個經(jīng)典離散事件系統(tǒng)，p:X×Σ →[0,1]是概率轉(zhuǎn)移函數(shù)。特別地，用p(σ|x) 來表示事件σ 在狀態(tài)x發(fā)生的概率，它滿足：(1) ?x∈X:Σσ∈Σp(σ|x)=1 ；(2)?x∈X,?σ ∈Σ:p(σ|x)>0 ?δ(x,σ)!。

給定狀態(tài)集q∈2X，用U R(q) 來表示可從q中的某個狀態(tài)不可觀測地到達的狀態(tài)集，即

用N ext(q,σ)表 示當(dāng)可觀測事件σ ∈Σobs發(fā)生時可以立即達到的狀態(tài)集，即

假設(shè) α ∈P(L(G))是 一個可觀測映射。用X︿G(α)表示映射α 發(fā)生時的當(dāng)前狀態(tài)估計，其定義為

當(dāng)執(zhí)行 β ≤α (即β 為α的前綴集合) 時，定義在已知可觀映射α 的條件下β 的延遲狀態(tài)估計為

給定r1,r2∈2X×X為兩個狀態(tài)對集合。操作?:2X×X×2X×X→2X×X,其定義為

2 隨機K步不透明性和隨機無窮步不透明性

在實際應(yīng)用中違反無窮步(或K步)不透明性的概率極其微小則可以忽略不計。定量評價無窮步(或K步)不透明性，還需考慮系統(tǒng)轉(zhuǎn)移的概率。因此提出隨機無窮步(或K步)不透明性定義。

定義1 給定一個隨機離散事件系統(tǒng)(G,p)和秘密狀態(tài)集為Xs及 閾值θ <1。記

如果Σs∈LPIFpr(s)<θ，則稱(G,p)具有隨機無窮步不透明性。

定義2 給定一個隨機離散事件系統(tǒng)(G,p)和秘密狀態(tài)集為Xs及 閾值θ <1。記

如果Σs∈LPKS pr(s)<θ ，則稱(G,p)具有隨機K步不透明性。

3 驗證隨機無窮步不透明性

基于雙向觀測器 O bstw(G)[14]驗證隨機無窮步不透明性。

定理1 給定一個隨機離散事件系統(tǒng) (G,p)，可觀事件集為Σo，秘密狀態(tài)集為Xs。給定Obstw(G)=(Qtw,Σtw,ftw,qtw,0)為 (G,p)的雙向觀測器，記

隨機離散事件系統(tǒng) (G,p)具有無窮步不透明性，當(dāng)且僅當(dāng)LIFS=?。

證明 (充分性)設(shè) ? (q1,q2)∈qtw,使q1∩q2≠?并且q1∩q2?Xs。設(shè)s∈L(G) ，則?t∈L(Obstw(G))使 得P(s)=τ1(t)(τ2(t))R[14]。已 知q1=fobs(x0,τ1(t))和q2=fobs,R(X,τ2(t))，那么

從而

通過LIFS構(gòu)建驗證器VG[15]。記

對于任何ρ ∈2X×X，定義

作為 ρ的第一個分量中的狀態(tài)集。對于任何R∈22X×X，定義

確定是否?s∈LIF，就要確定QIF={(x,R)∈Q:?ρ ∈Rs.t.l1(ρ)?Xs}是否為空。記

LIPF={s∈LIFS:[f(q0,s)∈QIF]∧[?t

計算Σs∈LLPFp(s) ，首先定義VG=(Q,Σ,f,q0)[15]。然后定義馬爾可夫鏈(MC)M=(Q,pM,π0)，其中M狀態(tài)空間與VG狀態(tài)空間相同，轉(zhuǎn)移概率函數(shù)pM:Q×Q→[0,1] 其定義為：對于任意q=(x,R),q′=(x′,R′)∈Q,

4 驗證隨機K步不透明性

基于雙向觀測器 Obstw(G)[14]驗證隨機K步不透明性。

如果隨機離散事件系統(tǒng)(G,p)具有隨機K步不透明性，當(dāng)且僅當(dāng)LKS S=?。

證明 (充分性)設(shè) (G,p)具有K步不透明性，則?(q1,q2)∈qtw，使q1∩q2≠?且q1∩q2?Xs。

另有

則 (G,p) 具有無窮步不透明性當(dāng)且僅當(dāng)q1∩q2≠?∧q1∩q2?Xs,|τ2(t)|>K[14]。即(G,p)具有K步不透明性時，LKS S=?。

( 必 要 性) 設(shè)LKS S≠? ，則X︿|s1|(s1s2)?Xs。?t∈L(Obstw(G)) 使 得q1∩q2≠? ，并 且P(s)=τ1(t)(τ2(t))R,|τ2(t)|≤K[14]。則有

為了確定是否s∈，記

記：

5 系統(tǒng)不透明性算法

在給定閾值θ 的情況下，檢查 (G,p)是否具有隨機無窮步不透明性和隨機K步不透明性?；谏衔牡难芯拷Y(jié)果，提出以下算法。

算法1 輸入：(G,p)=(Q,Σ,f,q0) ，可觀事件集為Σo，秘密狀態(tài)集為Xs，隨機無窮步不透明性閾值θIF，正整數(shù)K，隨機K步不透明性閾值θKS

例1 在訪問服務(wù)器時，用戶權(quán)限存在兩種：超級用戶權(quán)限和普通用戶權(quán)限。用戶在登入服務(wù)器后，首先要獲取相應(yīng)的權(quán)限。擁有超級用戶權(quán)限或者普通賬戶權(quán)限的賬號都可以訪問服務(wù)器。服務(wù)器的賬戶系統(tǒng)非常嚴格，普通用戶在做系統(tǒng)級別的更改時會受到用戶權(quán)限的限制。用戶登錄服務(wù)器默認擁有普通用戶權(quán)限。擁有超級用戶權(quán)限的用戶可以以普通用戶的身份訪問服務(wù)器，還可以執(zhí)行普通用戶無法進行的系統(tǒng)操作。同時，擁有超級用戶權(quán)限的用戶還可以授權(quán)其他用戶為超級用戶。超級用戶權(quán)限為系統(tǒng)最高權(quán)限，不受安全系統(tǒng)限制。為防止入侵者獲得超級用戶權(quán)限，將“超級用戶權(quán)限登入”看作是一個秘密狀態(tài)。對于一個已設(shè)計的服務(wù)器系統(tǒng)，能否通過比較隨機離散事件系統(tǒng)具有隨機K步不透明性的閾值θ 與系統(tǒng)安全期望值，提前得到系統(tǒng)是否安全以便采取相應(yīng)預(yù)防措施。

給定事件a為用戶獲取訪問系統(tǒng)權(quán)限，事件b為超級用戶權(quán)限轉(zhuǎn)換成普通用戶權(quán)限，事件c為訪問系統(tǒng)?？紤]如圖1(a)所示用戶訪問服務(wù)器系統(tǒng)，其中狀態(tài)1表示未登錄用戶，狀態(tài)2表示用戶以普通用戶權(quán)限登入，狀態(tài)3表示用戶以超級用戶權(quán)限登入，狀態(tài)4為用戶訪問服務(wù)器系統(tǒng)。其中狀態(tài)3被表示為秘密狀態(tài)。當(dāng)入侵者在入侵系統(tǒng)后可以確定用戶是以超級用戶權(quán)限登入(秘密狀態(tài))時，表明系統(tǒng)不具備隨機K步不透明性。用字母A、B、C、D、E、F、H標(biāo)識不同的狀態(tài)集。將用戶訪問系統(tǒng)的事件看作隨機離散事件系統(tǒng)的事件轉(zhuǎn)移，投影為P:Σ?→Σo?，其中Σo={a,b,c}，Xs={3}為秘密狀態(tài)。

圖1 系統(tǒng)G 其中的可觀事件Σ obs={a,b,c} 和 秘密狀態(tài)Xs={3}Fig.1 System G with Σ obs={a,b,c} 、Xs={3}

步驟1：求(G,p)的 O bstw(G)，如圖2所示。

圖2 Obstw(G)Fig.2 Obstw(G)

步驟2：求得 (G,p)中含有秘密狀態(tài)且滿足K步不透明性的語言LKS S={ac,abc}。

圖3 一個隨機K 步不透明性的例子，其中K=1Fig.3 An example of almost K-step opacity, where K =1

由于P(M2)和P(M4)是一個自由項，所以上述方程的解不唯一。設(shè)P(M2)=P(M4)=0 ，而P(M5)=1，則P=[0.090 0.101] 。因 此π0(M1)×P(M1)=0.09。當(dāng)系統(tǒng)安全期望值大于0.09時，此系統(tǒng)為隨機1步不透明性。即入侵者無法在用戶訪問系統(tǒng)時確定用戶是否是以超級用戶權(quán)限登入。在設(shè)計這樣的服務(wù)器時，可以通過算法1來判斷所設(shè)計的系統(tǒng)是否安全。一旦所設(shè)計的系統(tǒng)不安全，則可以為保障擁有超級用戶權(quán)限的用戶不被發(fā)現(xiàn)而采取相應(yīng)的控制手段(如提高普通用戶權(quán)限使用頻率、降低超級用戶權(quán)限使用頻率等)，以規(guī)避超級用戶權(quán)限被盜用的發(fā)生。

6 結(jié)論

本文研究了基于狀態(tài)的可觀映射下隨機離散事件系統(tǒng)是否具有隨機無窮步不透明性和隨機K步不透明性問題。將雙向觀測器引入隨機離散事件系統(tǒng)不透明性研究，構(gòu)造隨機無窮步不透明性和隨機K步不透明性的驗證器，提出算法以驗證系統(tǒng)是否具有隨機無窮步不透明性和隨機K步不透明性。