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

准确和及时地查看网络的内部状态(例如，链路延迟/抖动/损耗的分布或这些分布的各种统计数据)是许多网络管理功能的核心，例如流量工程、服务布置和故障检测/定位。然而，由于复杂性和异构性的增加，在诸如因特网、混合光/铜网络、未来蜂窝网络和分布式云网络等现代计算机通信网络中，获得这样的观点已经变得比以往任何时候都更具挑战性。传统的网络监控方法基于普遍部署的监控代理(如SNMP)或普遍支持的网络协议(如Traceroute)，在这种复杂和异构的环境中面临着严重的限制。网络断层扫描旨在从从网络外围获得的端到端测量推断网络内部状态，它提供了一种强大的替代方法，该方法可以构建内部状态的视图，而无需直接监视内部链路/节点。然而，现有的网络层析成像解决方案假设所有内部节点在业务转发中的行为一致，这使得它们在对抗性环境中很容易受到攻击，其中某些节点可以操纵通过它们的业务来改变端到端的测量。该项目将调查现有网络断层扫描解决方案在对抗性环境中的脆弱性，并制定防御机制的指导方针。该项目的主要目标是通过严格的漏洞分析来量化现有网络断层扫描算法的漏洞，这涉及到实际为每个有代表性的断层扫描算法开发最佳攻击策略，并根据对手在不被检测/本地化的情况下可能导致的最大性能降级来分析其影响。将为为不同类型的网络状态设计的网络层析成像算法制定和解决具体的优化问题，包括表示链路延迟/丢失统计的附加度量、表示可用链路容量的最小度量以及表示链路拥塞/故障状态的布尔度量。在脆弱性分析的基础上，将对基于断层扫描的网络监测在对抗环境中的可靠性进行深入研究，并将为未来的网络断层扫描算法制定指导方针。提出的研究是基于良性环境下网络层析成像的最新进展，包括状态估计算法、测量设计算法以及它们的局限性和性能的理论。研究将在优化和算法设计的交叉点上进行，涉及线性/非线性优化、组合优化、参数估计和经验验证。该项目将通过参与理论研究、算法实施和基于来自互联网的真实数据集进行经验验证，为学生提供培训经验，其中一些学生来自代表性不足的群体。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.