基于序列验证有界离散事件系统(DES)当前状态不透明性(CSO)的方法

《IEEE Transactions on Automatic Control》:A Sequence-Based Approach for the Verification of Current-State Opacity in Bounded Discrete Event Systems

【字体: 大 中 小 】 时间:2026年07月02日 来源:IEEE Transactions on Automatic Control 7.0

编辑推荐:

  不透明性(opacity)研究系统在向仅能部分观察其动态行为的恶意入侵者隐藏秘密时的能力。在当前状态不透明性(current-state opacity,CSO)框架下,秘密被建模为一组可达状态;若入侵者无法推断系统当前究竟到达了秘密状态还是非秘密状态,则称该

  
不透明性(opacity)研究系统在向仅能部分观察其动态行为的恶意入侵者隐藏秘密时的能力。在当前状态不透明性(current-state opacity,CSO)框架下,秘密被建模为一组可达状态;若入侵者无法推断系统当前究竟到达了秘密状态还是非秘密状态,则称该系统是不透明的。该研究针对由Petri网(Petri nets,PN)建模的离散事件系统(discrete event systems,DES),给出了验证CSO的充分必要条件。该方法仅要求系统有界,而无需文献中常见的诸如不可观测事件导出子网无环(acyclicity of induced subnets)之类的额外假设。研究人员证明,对于有界系统,只需在一个长度受限的有限可观测词集合上检查相应条件即可判定不透明性。这种基于序列的方法避免了观测器(observer)的构建,因而能够加速不透明性验证,并通过与基于观测器的方法进行比较加以说明。此外,所提出的验证算法依赖求解整数线性规划(integer linear programming,ILP)形式的优化问题,并可通过并行化进一步提升效率。全文通过一个示例逐步阐明所提方法。
离散事件系统(DES)是建模、分析与设计复杂分布式人造系统的有力工具,也常被称为信息物理系统(cyber-physical systems,CPS),因其同时包含物理组件与通信、计算等网络组件。CPS由于与网络世界开放互联而容易遭受攻击,其中被动攻击的目标是获取系统秘密,从而引发隐私问题。在此背景下,不透明性(opacity)被广泛用于刻画系统对入侵者隐藏秘密的能力。现有针对Petri网(PN)建模系统的CSO验证方法大多采用基于观测器(observer)的框架,需要计算状态估计图或基本可达图(basis reachability graph,BRG),并通常假设不可观测变迁所导出的子网无环,且非秘密状态集合被取为可达集相对于秘密集合的补集。此类方法面临状态空间指数级爆炸(curse of dimensionality)的困扰,计算代价随状态空间规模急剧增长。因此,研究人员开展这项研究,旨在摆脱上述限制性假设,提出一种基于序列的CSO验证新框架,从而在不构建观测器的前提下实现有界系统不透明性的精确判定。

该研究的核心贡献是证明了:对于由标注Petri网(labeled P/T net)建模的有界系统,CSO的验证只需考察长度不超过某个有限阈值Kmax的可观测词。直观上,任意到达秘密状态的路径均可分解为一条直达秘密状态的直连路径(direct path)与若干使标识回到原点的循环序列(cyclic sequence)。循环序列的发射计数向量(firing count vector,FCV)是最小支持T-不变量(minimal support T-invariant),其任意多次重复可通过一次执行的“解释路径”加以推广。因而,研究人员首先建立了由初始标识到秘密标识的直连路径集合Σ1、到非秘密标识的直连路径集合Σ2,以及包含每个最小支持T-不变量至多一次发射的循环扩展集合Σ3;进而证明Kmax可由Σ1、Σ2中可观测词的最大长度与Σ3中可观测循环次数上界之和确定。在此基础上,给出了CSO的充要条件:一个有界系统是当前状态不透明的,当且仅当对于语言LKmax(𝒢)中每一个长度为Kmax以内的可观测词w,均存在一条从初始标识可达非秘密标识、且产生相同可观测词w的发射序列。

为将上述理论结果转化为可执行算法,研究人员利用PN的状态方程代数表示,将每个长度不超过Kmax的词的生成与验证均转化为ILP可行性问题。具体地,算法依次迭代地构造LKmax(𝒢)中的词,对每一个候选词w求解可行性子问题ΠK,判断是否存在从某初始标识到达秘密标识且可观测投影为w的序列;若存在,则再求解子问题ΠJ,判断是否存在到达非秘密标识且产生相同词w的“解释序列”。只要任一候选词无法被解释,算法即可终止并判定系统不透明性不成立;若所有候选词均可解释,则系统为CSO。由于外层迭代之间彼此独立,该算法易于并行化,进一步提升了计算效率。

研究中所用的关键技术方法可概括为:在非循环假设下,利用直连路径与最小支持T-不变量的结构特性确定最大可观测词长Kmax,并通过ILP优化求解相关路径长度与循环次数上界;随后基于PN代数状态方程,迭代枚举长度不超过Kmax的可观测词,逐一枚举并求解ΠK与ΠJ两个ILP可行性子问题;算法天然支持并行化实现。

研究主体按章节展开如下。

第一章“引言”确立了研究动机:现有基于观测器的方法受限于状态空间爆炸和无环性假设,而有界系统的CSO验证可以转化为有限集合上的序列判定问题。第二章“背景”给出PN、可达语言、T-不变量、标注PN以及CSO的严格定义;同时提出了一个仅涉及不可观测序列的简单充分条件(定理1),并通过ILP可行性问题(定理2)说明如何将序列存在性转化为代数约束,为后续主结果奠定方法基础。

第三章“主要结果”是论文的核心。命题1指出Kmax至少应不小于到达秘密标识的直连路径所对应可观测词的最大长度;命题2说明当不存在循环序列时,该下界即为精确值;命题3则进一步给出含循环序列情形下的上界公式;最终定理3建立了CSO的充分必要条件:若所有长度不超过Kmax的可观测词均可被非秘密路径解释,则系统为CSO,反之则不是。第四章“CSO验证算法”将定理3实现为两个算法:算法1顺序迭代地检查候选词并求解ΠK与ΠJ,算法2则对迭代过程进行并行化。第五章“总结性示例”通过一个具体PN系统,将所提方法与文献中的BRG观测器方法进行对比。结果表明,对于所构造的测试用例,序列方法的Kmax保持为7且只需检查十个词,而基于BRG的观测器方法因状态空间指数增长在较大规模时已无法在5小时内完成;在第二个测试用例中,系统在检查第一个候选词后即可判定为非CSO,体现了序列方法可提前终止的优势。

第六章“结论”总结全文并指出:该文给出了有界DES中由PN建模的CSO验证的充分必要条件,证明了只需检查一个有限语言即可完成CSO判定,其余通往秘密的长序列均可通过循环序列的重复加以“解释”;所提基于序列的算法有效缓解了状态空间爆炸问题,并且可通过并行化进一步提升性能。此外,由于该方法基于PN的代数表示,它对秘密集合与非秘密集合的定义具有高度灵活性,能够方便地处理由广义互斥约束(generalized mutual exclusion constraints,GMECs)描述的秘密集合,并可推广到初始状态不透明性与终结状态不透明性等情形。未来工作可进一步将这一有限语言框架扩展到时序DES,以利用事件上的时间信息提高验证效率。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号