基于粗糙集理论的离散事件系统不透明性的验证算法

Verification algorithm for opacity of discrete-event systems with rough set theory

中文关键词  离散事件系统，不透明性，粗糙集理论，决策表

英文关键词  Discrete event systems, opacity, rough set theory, decision table

中文摘要

      近年来，离散事件系统的不透明性(opacity)研究引起了国内外众多学者的广泛关注，它在数字签名、保密通信、信息认证、入侵检测、数据加密等信息安全机制中取得了重要应用。本文针对离散事件系统的不透明性，提出了一种将粗糙集理论作为知识提取工具来处理离散事件系统不透明性验证的方法。先对离散事件系统的不透明性进行形式化，再利用粗糙集理论对离散事件系统以信息表以及决策表的形式进行表示，得到一个关于离散事件系统不透明性的充分必要条件，在此基础上给出一个验证离散事件系统不透明性的算法，实现了对系统不透明性。同时，也提出了一个在保证系统不透明性的条件下减少可观事件个数的优化算法。与现有方法相比，本文提出的验证算法既适用于强不透明性的验证，又适用于弱不透明性的验证，并且在时间复杂度上也有明显改进。

英文摘要

      In recent years, the opacity of discrete event systems (DESs) has received considerable attention, which has been successfully applied to many information technology areas such as digital signature, communication security, information authentication, intrusion detection and data encryption. This paper aims to propose an approach for verification of opacity in DESs by means of rough set theory as a knowledge extraction tool. Firstly, the notion of opacity for DESs modeled by finite state automation is formalized. Then DESs are formalized as information tables and decision tables under the framework of rough set theory. A necessary and sufficient condition of verifying opacity is presented and an algorithm is proposed to verify opacity of DESs. Compared with the existing methods, the algorithms proposed in this paper not only can be used to the verification for both strong opacity and weak opacity, but also have lower computational complexity.