信息流图的分割算法

Divide Algorithm Based on Information-flow Chart Build Forest

一个多级安全系统的信息传递关系是搜索隐通道的重要依据。由于一个大型多安全级软件系统的信息传递关系非常复杂,对其直接进行信息流分析并搜索隐通道的工作量非常大,因此为进一步提高搜索和分析隐通道的效率,提出了一种将信息流图分割成信息流森林的算法。该算法首先选定一棵父树,然后通过边割集中的弧置换父树中的树枝得到新树,并能从理论上保证分割后得到的信息流森林正确继承原图的信息,即原图中信息流既未被割裂也未丢失。通过对每棵信息流树表示的信息流进行分析就可取代对整个信息流图的分析,从而有效降低了分析问题的规模。

Information-flows of mains and objects in a Multi-level security system could be used to describe an information-flow chart. This information-flow chart is the important basis of covert-channel search. But the information-flow charts in big system are intricately. Therefore, we proposed a new segmentation algorithm based on information-flow chart to build forest. Segmentation algorithm needs to ensure that information-flow forest could inherit correct information from information-flow chart. First, arbitrary full path in information-flow chart is not fragmented. Second, arbitrary full path in information-flow could not miss. Last, algorithm is able to handle the cycle flow of information. Analyzing the information flow, we can replace the entire information-flow chart. So it could effectively lower the analysis of the complexity of the problem. The new model could be used in the field of covert-channel search analysis, and improve the efficiency.