離散事件系統(tǒng)不透明性監(jiān)督控制研究綜述

區(qū)嘉穎 劉富春

摘要：離散事件系統(tǒng)不透明性是指外部觀(guān)察者無(wú)法分辨系統(tǒng)的一系列行為是否為系統(tǒng)所發(fā)生的。而離散事件不透明性監(jiān)督控制則是構(gòu)建監(jiān)督器控制系統(tǒng)行為，使系統(tǒng)滿(mǎn)足不透明性的一種方法。離散事件系統(tǒng)不透明性與信息安全有著緊密的聯(lián)系，并得到了廣泛的應(yīng)用。首先對(duì)離散事件系統(tǒng)做了簡(jiǎn)要的概述，然后介紹了不透明性監(jiān)督控制算法的研究現(xiàn)狀，最后進(jìn)行了總結(jié)和展望。

關(guān)鍵詞：離散事件系統(tǒng);不透明性;監(jiān)督控制

中圖分類(lèi)號(hào)：TP301.1 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）12-0232-03

1背景

近年來(lái)，隨著互聯(lián)網(wǎng)高速發(fā)展，個(gè)人隱私和數(shù)據(jù)安全受到嚴(yán)峻的挑戰(zhàn)，信息安全成為一個(gè)熱門(mén)領(lǐng)域。信息安全要求信息流，也即在用戶(hù)之間的數(shù)據(jù)傳輸能夠保證安全和隱私。而安全和隱私在離散事件系統(tǒng)領(lǐng)域中被定義為匿名性和秘密性，也即不透明性中兩個(gè)特殊的屬性來(lái)研究。不透明性在離散事件系統(tǒng)中還包含其余三個(gè)重要屬性——可觀(guān)性、可診斷性和可偵測(cè)性。對(duì)這五個(gè)特性的確認(rèn)均可以簡(jiǎn)化為對(duì)不透明性的確認(rèn)。因此，離散事件系統(tǒng)與信息安全結(jié)合有非常重要的現(xiàn)實(shí)意義。多年來(lái)，許多研究者在離散事件系統(tǒng)不透明性領(lǐng)域做出了重要的研究成果，在通信協(xié)議和計(jì)算機(jī)系統(tǒng)領(lǐng)域中已有廣泛應(yīng)用。

2離散事件系統(tǒng)

離散事件系統(tǒng)是指由一系列離散的狀態(tài)組成，并由事件驅(qū)動(dòng)的人造系統(tǒng)。對(duì)離散事件系統(tǒng)領(lǐng)域的研究始于20世紀(jì)50年代中期，具體有三條不連貫但互補(bǔ)的主線(xiàn)——邏輯控制（Logic Controller）、離散事件仿真（Discrete Event Simulation）和實(shí)施估計(jì)與控制（Performance Evaluation and Control），共同特點(diǎn)是都圍繞著人造系統(tǒng)的建模、分析和綜合展開(kāi)。經(jīng)過(guò)多年的發(fā)展，離散事件系統(tǒng)理論日趨完善，成為一個(gè)跨學(xué)科寬廣的領(lǐng)域。作為一個(gè)正式的系統(tǒng)理論，離散事件系統(tǒng)基于數(shù)學(xué)和邏輯，綜合了自動(dòng)控制（Automatic Control）、運(yùn)籌學(xué)（Operations Research）等多個(gè)學(xué)科的知識(shí)。目前，離散事件系統(tǒng)領(lǐng)域關(guān)鍵問(wèn)題集中在建模、邏輯與行為分析、設(shè)計(jì)優(yōu)化、強(qiáng)制邏輯要求（如互斥和死鎖解除等）、計(jì)劃和運(yùn)籌（如生產(chǎn)時(shí)間周期的最小化）以及故障診斷和定位，在工業(yè)制造、工作流管理、軟硬件設(shè)計(jì)、交通和通信中有廣泛的應(yīng)用。同時(shí)，離散事件系統(tǒng)也被應(yīng)用到其他領(lǐng)域中，如動(dòng)力系統(tǒng)、流行病學(xué)和生物化學(xué)。

3不透明性

不透明性是一種重要的信息安全性質(zhì)，它描述了系統(tǒng)秘密行為不被外界入侵者所獲知的特性。假設(shè)入侵者完全了解系統(tǒng)結(jié)構(gòu)，但只觀(guān)察到系統(tǒng)的部分行為，并根據(jù)觀(guān)察結(jié)果構(gòu)建系統(tǒng)軌跡的估計(jì)。當(dāng)入侵者的估計(jì)沒(méi)有揭示系統(tǒng)的秘密，無(wú)法分辨一系列行為是否為系統(tǒng)真正發(fā)生的，則這個(gè)系統(tǒng)是不透明的。也就是說(shuō)，對(duì)于任何秘密行為，系統(tǒng)中至少存在一個(gè)與入侵者看起來(lái)相同的秘密行為。

不透明性的定義在許多文獻(xiàn)中有介紹。2004年，Mazare在研究信息流的安全和隱私、分析秘密協(xié)議的文獻(xiàn)[2]中首次介紹了不透明性。后來(lái)，計(jì)算機(jī)安全領(lǐng)域不透明性的概念擴(kuò)展到離散事件系統(tǒng)框架下，Mazare介紹了使用Petri Net建模的不透明性，而B(niǎo)ryans J則探討了在動(dòng)態(tài)離散事件系統(tǒng)中確?！安l(fā)秘密”的概念。這些工作激發(fā)了離散事件系統(tǒng)領(lǐng)域?qū)Σ煌该餍缘难芯?。隨后，基于狀態(tài)的不透明性和基于語(yǔ)言的不透明性先后被提出。

3.1基于狀態(tài)的不透明性

根據(jù)秘密集的性質(zhì)，基于狀態(tài)的不透明性可分為當(dāng)前狀態(tài)不透明性、初始狀態(tài)不透明性、最初和最終狀態(tài)的不透明性、K步不透明性以及無(wú)窮步不透明性。

Saboori A提出了使用狀態(tài)估計(jì)的方法定義的不透明性，當(dāng)前狀態(tài)不透明性是指入侵者或外部觀(guān)察者不能確定當(dāng)前系統(tǒng)所處的狀態(tài)是否為秘密狀態(tài)。在文獻(xiàn)[6]中，Saboori A介紹初始狀態(tài)不透明性，也即如果觀(guān)察者不能確定系統(tǒng)的初始狀態(tài)是否是秘密狀態(tài)，則系統(tǒng)是初始狀態(tài)不透明的。與此同時(shí)，Wu介紹初始和最終狀態(tài)不透明性，它是當(dāng)前不透明性與初始不透明性的擴(kuò)展，它們之間的唯一區(qū)別是初始和最終狀態(tài)不透明性的秘密狀態(tài)是成對(duì)定義的。另外，初始不透明性與當(dāng)前不透明性是初始和最終不透明性的特殊例子。

除初始狀態(tài)不透明以外，先前定義的不透明性不會(huì)考慮系統(tǒng)在退出秘密狀態(tài)后的行為。因此，一個(gè)更普遍的問(wèn)題是：系統(tǒng)在狀態(tài)轉(zhuǎn)移的過(guò)程中，在多少步之前是處于秘密狀態(tài)的。K步不透明性和無(wú)限步不透明性基于此問(wèn)題提出。

在文獻(xiàn)[8]中K步不透明性是當(dāng)前狀態(tài)不透明性的直接推廣，對(duì)系統(tǒng)運(yùn)行中的任一狀態(tài)向前K步所形成的事件序列，入侵者即使觀(guān)察到，也無(wú)法判定系統(tǒng)是否在秘密狀態(tài)中。當(dāng)前不透明性是K步不透明性的特殊情況，等價(jià)于0步不透明性。K步不透明性的進(jìn)一步推廣便是無(wú)限步不透明性。對(duì)于系統(tǒng)的每次執(zhí)行，在觀(guān)察到任意長(zhǎng)的事件序列之后，入侵者無(wú)法推斷系統(tǒng)在某個(gè)時(shí)刻處于秘密狀態(tài)（在執(zhí)行的任何后退步驟），則系統(tǒng)是無(wú)限步不透明的。

3.2基于語(yǔ)言的不透明性

基于語(yǔ)言的不透明性定義與可診斷性有緊密的聯(lián)系。可診斷性是有分辨確定的事情的能力，如故障有無(wú)出現(xiàn);而不透明性是沒(méi)有能力分辨確定的事情，如系統(tǒng)是否處于秘密狀態(tài)。

在基于語(yǔ)言的可診斷性中，使用了兩種語(yǔ)言，與先前基于狀態(tài)的不透明性只使用一種語(yǔ)言是互補(bǔ)的。兩種語(yǔ)言定義的不透明性在應(yīng)用中更加靈活，具體可分為強(qiáng)不透明性、弱不透明性和不具有不透明性。給定一般的觀(guān)察映射，若一個(gè)語(yǔ)言的所有串能和另一個(gè)語(yǔ)言的部分串混淆，則這個(gè)語(yǔ)言具有強(qiáng)不透明性;若一個(gè)語(yǔ)言的部分串能和另一個(gè)語(yǔ)言的部分串混淆，則這個(gè)語(yǔ)言具有弱不透明性。由于在強(qiáng)不透明性概念中涉及信息安全性質(zhì)，也即匿名性和秘密性，強(qiáng)不透明性很常用。弱不透明性可以自然地?cái)U(kuò)展到強(qiáng)不透明性。強(qiáng)不透明性和弱不透明性的區(qū)別與可觀(guān)察性和可偵測(cè)性在線(xiàn)性系統(tǒng)理論中的區(qū)別相似。同時(shí)考慮到某些情況下觀(guān)察器或代理出于安全或其他目的，需要透明地監(jiān)控系統(tǒng)行為，介紹了不具有不透明性的概念。另外，在文獻(xiàn)[1]中，Lin Feng等將可觀(guān)性、可診斷性和可偵測(cè)性重新形式化為不透明性的特例。

上述基于語(yǔ)言或狀態(tài)的不透明性均屬于邏輯不透明性，并沒(méi)有提供系統(tǒng)不透明性的度量，定義只是考慮了非秘密行為與給定的觀(guān)察串的能否匹配。為了更好地描述一個(gè)系統(tǒng)不透明性的程度，研究者使用了隨機(jī)有限自動(dòng)機(jī)、馬爾可夫過(guò)程和隱藏的馬爾可夫模型來(lái)定量地（或定性地）描述不透明性。

在完成對(duì)不透明性形式化定義的基礎(chǔ)上，需要考慮：1）如何判定的系統(tǒng)是否具有不透明性;2）使不具有不透明性的系統(tǒng)滿(mǎn)足不透明性。針對(duì)上述問(wèn)題，解決方案主要包括：驗(yàn)證、監(jiān)督控制和強(qiáng)制執(zhí)行。其中，驗(yàn)證是指通過(guò)建模來(lái)對(duì)系統(tǒng)進(jìn)行不透明性檢查，涉及離散事件系統(tǒng)驗(yàn)證的一般問(wèn)題。監(jiān)督控制是通過(guò)構(gòu)造監(jiān)督器約束系統(tǒng)行為，使其滿(mǎn)足不透明性要求。強(qiáng)制執(zhí)行是指系統(tǒng)輸入一系列可觀(guān)事件，并輸出可能修改后的信息，來(lái)確保系統(tǒng)的不透明性。這三種機(jī)制在不同系統(tǒng)模型或類(lèi)系統(tǒng)模型（經(jīng)典系統(tǒng)、定時(shí)系統(tǒng)、下推系統(tǒng)）得到廣泛的研究，也結(jié)合了其他諸如動(dòng)態(tài)觀(guān)察者、插入編輯功能等技術(shù)。

4監(jiān)督控制

監(jiān)督控制作為離散事件系統(tǒng)領(lǐng)域的一個(gè)重要研究?jī)?nèi)容，在20世紀(jì)80年代萌芽。監(jiān)督控制的出現(xiàn)與系統(tǒng)建模優(yōu)化問(wèn)題相關(guān)。它提供了系統(tǒng)優(yōu)化控制的方式，以及劃定了控制器和不受控制的機(jī)器之間的界限，使得不受控制的機(jī)器在控制器（監(jiān)督器）的監(jiān)督下能夠達(dá)到預(yù)期的規(guī)范。監(jiān)督控制基于系統(tǒng)反饋控制，結(jié)合可控制性理論和可控可觀(guān)理論，可劃分為部分可觀(guān)監(jiān)督控制、非阻塞控制和部分可控控制;根據(jù)系統(tǒng)的架構(gòu)，劃分為模塊化控制和去中心化控制等。監(jiān)督控制在國(guó)內(nèi)外有廣泛應(yīng)用，常見(jiàn)于電網(wǎng)、柔性系統(tǒng)等工業(yè)制造領(lǐng)域中。

4.1經(jīng)典離散事件系統(tǒng)不透明性監(jiān)督控制

Saboori A等在文獻(xiàn)[11]中介紹了基于初始狀態(tài)不透明性的監(jiān)督控制，采取了將初始狀態(tài)不透明性從基于狀態(tài)的定義擴(kuò)展到語(yǔ)言方法，通過(guò)確定的可控可觀(guān)不透明性語(yǔ)言的上確界（supremal）元素來(lái)達(dá)到構(gòu)造最小約束不透明性監(jiān)督器。同時(shí)得出上確界元素存在的條件以及展示初始狀態(tài)估計(jì)器。在先前工作基礎(chǔ)上，SabooriA等繼續(xù)考慮系統(tǒng)由部分可觀(guān)非確定性有限自動(dòng)機(jī)建模，利用狀態(tài)估計(jì)方法構(gòu)建一個(gè)最小約束不透明性的監(jiān)督器，使得系統(tǒng)滿(mǎn)足初始狀態(tài)不透明性和無(wú)限步不透明性的要求。

Benkalefa M等在文獻(xiàn)[13]中證明了不透明性在并集下是封閉的，但在交集下可能不封閉。另外也展示了如何修改語(yǔ)言使其滿(mǎn)足強(qiáng)不透明性。若一個(gè)語(yǔ)言不滿(mǎn)足強(qiáng)不透明性、弱不透明性和透明性，則可以尋找它的最大子語(yǔ)言或最小超語(yǔ)言來(lái)分別滿(mǎn)足強(qiáng)不透明性、弱不透明性和透明性。利用上確界的（supremal）、最大的（maximal）、下確界（infimal）和最小的（minimal）及其屬性，可以以更好的方式修改語(yǔ)言。文獻(xiàn)[14]延續(xù)了[13]的工作，使用監(jiān)督控制方法達(dá)到不透明性，也即若系統(tǒng)不能滿(mǎn)足不透明性，則尋找一個(gè)可以約束系統(tǒng)行為來(lái)滿(mǎn)足不透明性的監(jiān)督器。假設(shè)監(jiān)督器在系統(tǒng)內(nèi)部，但是可以觀(guān)察到一些不能被外部觀(guān)察者所觀(guān)察到的事件;假設(shè)監(jiān)督器能禁止某些可控事件的發(fā)生來(lái)約束系統(tǒng)行為。該文獻(xiàn)討論三個(gè)監(jiān)督控制問(wèn)題，強(qiáng)不透明性監(jiān)督控制問(wèn)題、弱不透明性監(jiān)督控制問(wèn)題和不具有不透明性控制問(wèn)題，對(duì)各個(gè)問(wèn)題分別提出了解決方案。

4.2其他類(lèi)型系統(tǒng)不透明性監(jiān)督控制

離散事件系統(tǒng)監(jiān)督控制除了應(yīng)用在經(jīng)典離散事件系統(tǒng)中，還應(yīng)用到去中心化、分布式離散事件系統(tǒng)、并發(fā)系統(tǒng)等類(lèi)型系統(tǒng)中。

Lin F等將經(jīng)典離散事件系統(tǒng)不透明性監(jiān)督控制算法推廣到去中心化離散事件系統(tǒng)中，指出了三種基于語(yǔ)言不透明性的監(jiān)督控制問(wèn)題。在文獻(xiàn)中，Lin F對(duì)外部觀(guān)察者之間有無(wú)協(xié)調(diào)者的兩種情況，給出了對(duì)應(yīng)的不透明性監(jiān)督控制算法。Yin Tong等則基于狀態(tài)的不透明性，討論使用模塊化方法構(gòu)建監(jiān)督控制。在將離散事件系統(tǒng)不透明性應(yīng)用到其他系統(tǒng)時(shí)，研究者也有研究魯棒性等相關(guān)性質(zhì)，使得監(jiān)督控制保持安全和健壯。

5總結(jié)與展望

離散事件系統(tǒng)不透明性在信息安全領(lǐng)域具有重要而廣泛的應(yīng)用，本文對(duì)離散事件系統(tǒng)不透明性以及監(jiān)督控制方法進(jìn)行了介紹。當(dāng)前的離散事件系統(tǒng)監(jiān)督控制方法多集中于經(jīng)典離散事件系統(tǒng)中，對(duì)其他類(lèi)型的系統(tǒng)如隨機(jī)離散事件系統(tǒng)等的研究較少，且算法復(fù)雜度較高。隨著離散事件系統(tǒng)領(lǐng)域進(jìn)一步發(fā)展，對(duì)不透明性監(jiān)督控制的進(jìn)一步研究，會(huì)在更多的場(chǎng)景中得到應(yīng)用。