Description

Abstract:

Quantifying and querying network reachability is important for security monitoring and auditing as well as many aspects of network management such as troubleshooting, maintenance, and design. Although attempts to model network reachability have been made, feasible solutions to computing network reachability have remained unknown. In this paper, we present Quarnet, a tool that comprises a suite of concrete algorithms for quantifying and querying network reachability. For quantification, Quarnet takes a network topology and the ACLs deployed on middleboxes as its input, and outputs reachabilitymatrices that represent the lower-bound reachability (i.e., the minimal set of packets that can traverse from a source to a destination at any time), instantaneous reachability (i.e., the set of packets that can traverse from a source to a destination at a particular time), and upper-bound reachability (i.e., the maximal set of packets that can traverse from a source to a destination at some time) for every pair of source and destination subnets.