Privacy-preserving quantification of cross-domain network reachability

Network reachability is an important characteristic for understanding end-to-end network behavior and helps in detecting violations of security policies across the network. While quantifying network reachability within one administrative domain is a difficult problem in itself, performing the same computation across a network spanning multiple administrative domains presents a novel challenge. The problem of quantifying network reachability across multiple administrative domains is more difficult because the privacy of security policies of individual domains is a serious concern and needs to be protected through this process. In this paper, we propose the first cross-domain privacy-preserving protocol for quantifying network reachability. Our protocol constructs equivalent representations of the Access Control List (ACL) rules and determines network reachability while preserving the privacy of the individual ACLs. This protocol can accurately determine the network reachability along a network path through different administrative domains. We have implemented and evaluated our protocol on both real and synthetic ACLs. The experimental results show that the online processing time of an ACL containing thousands of rules is less than 25 s. Given two ACLs, each containing thousands of rules, the comparison time is less than 6 s, and the total communication cost is less than 2100 kB.