Trading resiliency for security: model and algorithms

• Main Authors: Tian Bu, Norden, S., Woo, T.
• Format: Conference Proceeding
• Language: English
• Subjects: Applied sciences; Approximation algorithms; Computer crime; Exact sciences and technology; Filtering; Heuristic algorithms; Internet; Multiprocessor interconnection networks; Network servers; Operation, maintenance, reliability of teleprocessing networks; Resists; Routing protocols; Secret; Security; Systems, networks and services of telecommunications; Telecommunications; Telecommunications and information theory; Teleprocessing networks. Isdn
• ISSN: 1092-1648; 2643-3303
• DOI: 10.1109/ICNP.2004.1348112

An attack-resistant network is a purpose-built network to survive attacks; by construction, it should be both resilient and secure. Resiliency is the ability to provide alternative communication paths should one path become disrupted due to failures or attacks; while security is the ability to contain and limit the impact of compromises. Interestingly, these two can present conflicting demands. We provide a first formulation of a new class of problems focusing on the engineering of attack-resistant networks. Our model considers both resiliency and security, and uses a notion of blocking probability as a rigorous measure for evaluating different network constructions. We propose several efficient approximation algorithms for computing blocking probability and provide bounds for their errors. Based on these algorithms, we introduce a family of heuristics to guide the construction of optimal attack-resistant networks with minimum blocking probabilities. We also present extensive results to evaluate and demonstrate the near-optimal performance of our heuristics and approximation algorithms.