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

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

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

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.