離散事件系統不透明性監督控制研究綜述

區嘉穎 劉富春

摘要：離散事件系統不透明性是指外部觀察者無法分辨系統的一系列行為是否為系統所發生的。而離散事件不透明性監督控制則是構建監督器控制系統行為，使系統滿足不透明性的一種方法。離散事件系統不透明性與信息安全有著緊密的聯系，并得到了廣泛的應用。首先對離散事件系統做了簡要的概述，然后介紹了不透明性監督控制算法的研究現狀，最后進行了總結和展望。

關鍵詞：離散事件系統;不透明性;監督控制

中圖分類號：TP301.1 文獻標識碼：A

文章編號：1009-3044（2020）12-0232-03

1背景

近年來，隨著互聯網高速發展，個人隱私和數據安全受到嚴峻的挑戰，信息安全成為一個熱門領域。信息安全要求信息流，也即在用戶之間的數據傳輸能夠保證安全和隱私。而安全和隱私在離散事件系統領域中被定義為匿名性和秘密性，也即不透明性中兩個特殊的屬性來研究。不透明性在離散事件系統中還包含其余三個重要屬性——可觀性、可診斷性和可偵測性。對這五個特性的確認均可以簡化為對不透明性的確認。因此，離散事件系統與信息安全結合有非常重要的現實意義。多年來，許多研究者在離散事件系統不透明性領域做出了重要的研究成果，在通信協議和計算機系統領域中已有廣泛應用。

2離散事件系統

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

3不透明性

不透明性是一種重要的信息安全性質，它描述了系統秘密行為不被外界入侵者所獲知的特性。假設入侵者完全了解系統結構，但只觀察到系統的部分行為，并根據觀察結果構建系統軌跡的估計。當入侵者的估計沒有揭示系統的秘密，無法分辨一系列行為是否為系統真正發生的，則這個系統是不透明的。也就是說，對于任何秘密行為，系統中至少存在一個與入侵者看起來相同的秘密行為。

不透明性的定義在許多文獻中有介紹。2004年，Mazare在研究信息流的安全和隱私、分析秘密協議的文獻[2]中首次介紹了不透明性。后來，計算機安全領域不透明性的概念擴展到離散事件系統框架下，Mazare介紹了使用Petri Net建模的不透明性，而Bryans J則探討了在動態離散事件系統中確保“并發秘密”的概念。這些工作激發了離散事件系統領域對不透明性的研究。隨后，基于狀態的不透明性和基于語言的不透明性先后被提出。

3.1基于狀態的不透明性

根據秘密集的性質，基于狀態的不透明性可分為當前狀態不透明性、初始狀態不透明性、最初和最終狀態的不透明性、K步不透明性以及無窮步不透明性。

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

除初始狀態不透明以外，先前定義的不透明性不會考慮系統在退出秘密狀態后的行為。因此，一個更普遍的問題是：系統在狀態轉移的過程中，在多少步之前是處于秘密狀態的。K步不透明性和無限步不透明性基于此問題提出。

在文獻[8]中K步不透明性是當前狀態不透明性的直接推廣，對系統運行中的任一狀態向前K步所形成的事件序列，入侵者即使觀察到，也無法判定系統是否在秘密狀態中。當前不透明性是K步不透明性的特殊情況，等價于0步不透明性。K步不透明性的進一步推廣便是無限步不透明性。對于系統的每次執行，在觀察到任意長的事件序列之后，入侵者無法推斷系統在某個時刻處于秘密狀態（在執行的任何后退步驟），則系統是無限步不透明的。

3.2基于語言的不透明性

基于語言的不透明性定義與可診斷性有緊密的聯系。可診斷性是有分辨確定的事情的能力，如故障有無出現;而不透明性是沒有能力分辨確定的事情，如系統是否處于秘密狀態。

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

上述基于語言或狀態的不透明性均屬于邏輯不透明性，并沒有提供系統不透明性的度量，定義只是考慮了非秘密行為與給定的觀察串的能否匹配。為了更好地描述一個系統不透明性的程度，研究者使用了隨機有限自動機、馬爾可夫過程和隱藏的馬爾可夫模型來定量地（或定性地）描述不透明性。

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

4監督控制

監督控制作為離散事件系統領域的一個重要研究內容，在20世紀80年代萌芽。監督控制的出現與系統建模優化問題相關。它提供了系統優化控制的方式，以及劃定了控制器和不受控制的機器之間的界限，使得不受控制的機器在控制器（監督器）的監督下能夠達到預期的規范。監督控制基于系統反饋控制，結合可控制性理論和可控可觀理論，可劃分為部分可觀監督控制、非阻塞控制和部分可控控制;根據系統的架構，劃分為模塊化控制和去中心化控制等。監督控制在國內外有廣泛應用，常見于電網、柔性系統等工業制造領域中。

4.1經典離散事件系統不透明性監督控制

Saboori A等在文獻[11]中介紹了基于初始狀態不透明性的監督控制，采取了將初始狀態不透明性從基于狀態的定義擴展到語言方法，通過確定的可控可觀不透明性語言的上確界（supremal）元素來達到構造最小約束不透明性監督器。同時得出上確界元素存在的條件以及展示初始狀態估計器。在先前工作基礎上，SabooriA等繼續考慮系統由部分可觀非確定性有限自動機建模，利用狀態估計方法構建一個最小約束不透明性的監督器，使得系統滿足初始狀態不透明性和無限步不透明性的要求。

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

4.2其他類型系統不透明性監督控制

離散事件系統監督控制除了應用在經典離散事件系統中，還應用到去中心化、分布式離散事件系統、并發系統等類型系統中。

Lin F等將經典離散事件系統不透明性監督控制算法推廣到去中心化離散事件系統中，指出了三種基于語言不透明性的監督控制問題。在文獻中，Lin F對外部觀察者之間有無協調者的兩種情況，給出了對應的不透明性監督控制算法。Yin Tong等則基于狀態的不透明性，討論使用模塊化方法構建監督控制。在將離散事件系統不透明性應用到其他系統時，研究者也有研究魯棒性等相關性質，使得監督控制保持安全和健壯。

5總結與展望

離散事件系統不透明性在信息安全領域具有重要而廣泛的應用，本文對離散事件系統不透明性以及監督控制方法進行了介紹。當前的離散事件系統監督控制方法多集中于經典離散事件系統中，對其他類型的系統如隨機離散事件系統等的研究較少，且算法復雜度較高。隨著離散事件系統領域進一步發展，對不透明性監督控制的進一步研究，會在更多的場景中得到應用。