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

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

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.