Journal of Computer Applications ›› 2016, Vol. 36 ›› Issue (3): 653-656.DOI: 10.11772/j.issn.1001-9081.2016.03.653

Previous Articles     Next Articles

Research on properties of shared resource matrix method based on double cross linked list

YANG Peng, ZHAO Hui, BAO Zhonggui   

  1. Beijing Institute of Tracking and Telecommunications Technology, Beijing 100094, China
  • Received:2015-07-28 Revised:2015-09-29 Online:2016-03-10 Published:2016-03-17

基于双十字链表存储的共享资源矩阵方法特性研究

杨鹏, 赵辉, 鲍忠贵   

  1. 北京跟踪与通信技术研究所, 北京 100094
  • 通讯作者: 杨鹏
  • 作者简介:杨鹏(1991-),男,河北定州人,硕士研究生,主要研究方向:操作系统隐蔽通道检测;赵辉(1957-),女,辽宁沈阳人,研究员,硕士,主要研究方向:航天测控信息系统结构设计;鲍忠贵(1971-),男,安徽合肥人,研究员,硕士,主要研究方向:航天测控软件设计。

Abstract: Concerning the high time-complexity of shared resource matrix method based on array storage in the detection of system covert channel, an improved algorithm based on double cross linked list was proposed. Firstly, traditional array storage was improved by double cross linked list storage in transitive closure operation. Secondly, a probability model for shared resource matrix method was constructed. Finally, the time-complexity of the improved algorithm and features of shared resource matrix were analyzed under the probability model. When the shared resource matrix was a sparse matrix, using the improved algorithm based on double across linker storage could prompt 67% time efficiency of shared resource matrix compared to traditional realization based on array storage. When the scale of shared resource matrix was quite great, the property of transitive closure operation would cause quick filling of elements in shared resource matrix, then the time efficiency advantage of improved algorithm based on double cross linker was declined compared to traditional algorithm based on array storage. This property of transitive closure operation was proven through theoretical deduction under the probability model.

Key words: operating system, covert channel, shared resource matrix, probability model, double cross linked list

摘要: 针对共享资源矩阵法在系统隐蔽通道检测过程中存在的算法时间复杂度高的问题,提出了一种基于双十字链表存储的改进算法。首先,针对共享资源矩阵方法中的核心操作——传递闭包操作,将传统的数组存储改进为双十字链表存储;其次,针对共享资源矩阵方法建立了概率模型;最后,在该概率模型下,分析了改进算法的时间复杂度和共享资源矩阵方法的特性。理论分析和实验仿真表明:当共享资源矩阵为稀疏矩阵时,采用基于双十字链表存储的改进算法能够使共享资源矩阵法的时间效率相比传统的数组存储提高67%;当共享资源矩阵的规模较大时,传递闭包操作会使得共享资源矩阵中的元素快速填充,从而导致基于双十字链表存储改进算法相比传统数组存储的时间效率优势下降,并在概率模型下通过理论推导验证了传递闭包操作的这一特性。

关键词: 操作系统, 隐蔽通道, 共享资源矩阵, 概率模型, 双十字链表

CLC Number: