一种基于权值的大规模分布式系统结构脆弱性分析算法

A Structural Vulnerability Analysis Algorithm for Large-Scale Distributed System

结构脆弱性是大规模分布式系统的典型脆弱性类型之一.针对大规模分布式系统实体间复杂的依赖关系和冗余备份机制,构建了实体拓扑模型.该模型采用简单有向图描述实体间依赖关系,采用故障容忍机制刻画节点间的冗余关系,并引入权值刻画节点或边失效对于业务流程的影响.在此基础上,提出了基于权值的大规模分布式系统结构脆弱性分析算法,该算法通过权值计算和基于故障传递的剪枝方法发现并验证结构脆弱性.通过算法分析和实现充分验证了算法的有效性.

As large-scale distributed system plays an increasingly important role in such fields as national security,critical infrastructure and social life,its vulnerability analysis problem has become a growing focus nowadays.Because of wide area deployment,heterogeneity,dynamism,incapable centralized control and other characteristics,structural vulnerability is a typical type of vulnerabilities on large-scale distributed system.Aiming at the complex relation between entities and redundancy mechanism in large-scale distributed system,a new entity topology model is proposed.In the model,the simple digraph is used to describe the relation between entities;the fault tolerance mechanism is put forward to describe the redundancy of entities;and weight is introduced to score the influence of the entity or link failure on system function.Based on the entity topology model,a structural vulnerability analysis algorithm based on weight is put forward,which discovers the structural vulnerabilities by computing weight of every entity and link,and validates them by graph pruning.Experimental results by analyzing,implementation and evaluation,show that the algorithm can effectively discover the structural vulnerability of large-scale distributed system including single point failure node or link and combination failure of nodes and links.