CIF: Small: Adversarial Network Tomography: Inferring Network State from Manipulated End-to-End Measurements

An accurate and timely view of a network's internal state (e.g., distributions of link delays/jitters/losses or various statistics of these distributions) is at the heart of many network management functions, such as traffic engineering, service placement, and fault detection/localization. Obtaining such a view has, however, become more challenging than ever in modern computer communication networks such as the Internet, hybrid optical/copper networks, future cellular networks, and distributed cloud networks, due to their increased complexity and heterogeneity. The traditional network monitoring approach that is based on pervasively deployed monitoring agents (e.g., SNMP) or pervasively supported network protocols (e.g., traceroute) faces severe limitations in such complex and heterogeneous environments. Network tomography, which aims at inferring the network internal state from end-to-end measurements taken from the peripheral of the network, provides a powerful alternative approach that can construct a view of the internal state without directly monitoring the internal links/nodes. Existing network tomography solutions, however, assume that all the internal nodes behave consistently in traffic forwarding, which makes them vulnerable in an adversarial setting, where certain nodes can manipulate the traffic traversing them to alter the end-to-end measurements. This project will investigate the vulnerability of existing network tomography solutions in an adversarial setting and develop guidelines for defense mechanisms.

The primary objective of the project is to quantify the vulnerability of existing network tomography algorithms through rigorous vulnerability analysis, which involves actually developing the optimal attack strategy for each representative tomography algorithm and analyzing its impact in terms of the maximum performance degradation that an adversary can cause without being detected/localized. Concrete optimization problems will be formulated and solved for network tomography algorithms designed for different types of network states, including additive metrics that represent link delay/loss statistics, min metrics that represent available link capacities, and Boolean metrics that represent link congestion/failure states. Based on the vulnerability analysis, insights will be drawn on the reliability of tomography-based network monitoring in adversarial environments, and guidelines will be developed for future network tomography algorithms. The proposed research is grounded on latest advances on network tomography in the benign setting, including state estimation algorithms, measurement design algorithms, and theory about their limitations and performance. The research will be performed at the intersection of optimization and algorithm design, involving linear/non-linear optimization, combinatorial optimization, parameter estimation, and empirical validations. The project will provide training experience for students, some from underrepresented groups, through participation in the theoretical study, implementation of algorithms, and conduct of empirical validations based on real datasets from the Internet.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.