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.