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

doi:10.11772/j.issn.1001-9081.2016.03.653

Abstract

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:

TP309.5

YANG Peng, ZHAO Hui, BAO Zhonggui. Research on properties of shared resource matrix method based on double cross linked list[J]. Journal of Computer Applications, 2016, 36(3): 653-656.

杨鹏, 赵辉, 鲍忠贵. 基于双十字链表存储的共享资源矩阵方法特性研究[J]. 计算机应用, 2016, 36(3): 653-656.

References

[1] LAMPSON B W. A note on the confinement problem [J]. Communications of the ACM, 1973, 16(10): 613-615.
[2] TSAI C R, GLIGOR V D, CHANDERSEKARAN C S. On the identification of covert storage channels in secure systems [J]. IEEE Transactions on Software Engineering, 1990, 16(6): 569-580.
[3] ZANDER S, ARMITAGE G, BRANCH P. A survey of covert channels and countermeasures in computer network protocols [J]. IEEE Communication Surveys and Tutorials, 2007, 9(3): 44-57.
[4] WU Z, XU Z, WANG H. Whispers in the hyper-space: high-speed covert channel attacks in the cloud [C]//Security'12: Proceedings of the 21st USENIX Conference on Security Symposium. Berkeley, CA: USENIX Association, 2012:159-173.
[5] RISTENPART T, TROMER E, SHACHAM H, et al. Hey, you, get off of my cloud: exploring information leakage in third-party compute clouds [C]//CCS'09: Proceedings of the 16th ACM Conference on Computer and Communications Security. New York: ACM, 2009: 199-212.
[6] KEMMERER R A. Shared resource matrix methodology: an approach to identifying storage and timing channels [J]. ACM Transactions on Computer Systems, 1983, 1(3): 256-277.
[7] DENNING D E. A lattice model of secure information flow [J]. Communications of the ACM, 1976, 19(5): 236-243.
[8] TSAI C R, GLIGOR V D, CHANDERSEKARAN C S. A formal method for the identification of covert storage channels in source code [C]//Proceedings of the 1987 IEEE Symposium on Security and Privacy. Washington, DC: IEEE Computer Society, 1987: 74.
[9] GOGUEN J A, MESEGUER J. Security policies and security models [C]//Proceedings of the 1982 IEEE Symposium on Security and Privacy. Washington, DC: IEEE Computer Society, 1982: 11.
[10] 姚立红,訾小超,李建华.隐蔽通道的信息传递模型[J].电子学报,2008,36(11):2216-2219. (YAO L H, ZI X C, LI J H. An information transmission model for covert channel [J]. Acta Electronica Sinica, 2008, 36(11): 2216-2219.)
[11] 卿斯汉,朱继锋.安胜安全操作系统的隐蔽通道分析[J].软件学报,2004,15(9):1385-1392. (QING S H, ZHU J F. Covert channel analysis on ANSHENG secure operating system [J]. Journal of Software, 2004, 15(9): 1385-1392.)
[12] 陈喆,刘文清,王亚弟,等.基于信息流分析的隐蔽通道分类与标志[J].计算机应用研究,2010,27(7):2631-2635. (CHEN Z, LIU W Q, WANG Y D, et al. Categorying and identifying with covert channel based on information flow analysis [J]. Application Research of Computers, 2010, 27(7): 2631-2635.)
[13] 宋香梅,周密,鞠时光,等.一种基于信息流脉络网的隐蔽通道搜索方法 [J].计算机应用研究,2013,30(8):2506-2509. (SONG X M, ZHOU M, JU S G, et al. Method for covert channels identification based on information flow veined net [J]. Application Research of Computers, 2013, 30(8): 2506-2509.)
[14] 支雷磊,王佳,曾庆凯.针对源代码的隐蔽通道标识关键技术及其改进方法[J].上海交通大学学报,2009,43(1):101-105. (ZHI L L, WANG J, ZENG Q K. Key technologies and improvement of identifying covert channels in source code [J]. Journal of Shanghai Jiaotong University, 2009, 43(1): 101-105.)
[15] 郭云川,周渊,丁丽,等.基于概率干扰的概率隐蔽通道仿真研究[J].通信学报,2009,30(2):59-64. (GUO Y C, ZHOU Y, DING L, et al. Simulation analysis of probabilistic covert channels based on probabilistic interference [J]. Journal on Communications, 2009 30(2): 59-64.)
[16] 王昌达,鞠时光,周从华,等.一种隐通道威胁审计的度量方法[J].计算机学报,2009,32(4):751-762. (WANG C D, JU S G, ZHOU C H, et al. A measurement of covert channels threat [J]. Chinese Journal of Computers, 2009, 32(4): 751-762.)
[17] HAIGH J T, KEMMERER R A, MCHUGH J, et al. An experience using two covert channel analysis techniques on a real system design [J]. IEEE Transactions on Software Engineering, 1987,13(2): 157-168.
[18] 王永吉,吴敬征,曾海涛,等.隐蔽信道研究[J].软件学报,2010,21(9):2262-2288. (WANG Y J, WU J Z, ZENG H T, et al. Covert channel research [J]. Journal of Software, 2010, 21(9): 2262-2288.)
[19] 刘承玉.基于源代码的隐蔽通道分析方法若干关键问题的研究[D].北京:北京交通大学, 2010:51-60.(LIU C Y. Study on key issues of covert channels analysis based on source codes [D]. Beijing: Beijing Jiaotong University, 2010:51-60.)