EPCN: Strong Diagnoses from Weak Signals: Leveraging Network Effects for Epidemic Detection

互联互通是现代基础设施功能的核心，可以传播思想、技术和信息。未来的关键基础设施，从自动驾驶汽车到云计算承诺启用、利用和依赖于这种互联和传播能力。但最近的历史表明，从拒绝服务攻击到国家驱动的网络战，如果漏洞允许，它们也会遭受攻击。恶意软件潜在的广泛破坏性影响是显而易见的，尤其是在移动设备的重要性正在上升的情况下。随着越来越多的关键基础设施与终端用户（消费者）控制的设备相关联，而不仅仅是一个硬件和软件被集中管理和控制的计算机骨干，维护我们设备的网络健康的重要性将变得越来越重要，也变得更加困难。这一提议的中心主题是它的座右铭，如果传播，它就无法隐藏。其动机是建立一个理论和相应的算法，不依赖于网络或设备的具体情况，也不依赖于传播的具体情况。如果我们的防御依赖于探测特定的特征，根据定义，他们会错过任何不具有这些特征的威胁。更确切地说，如果某种东西通过网络传播，传播本身就会留下一个独立于恶意软件设计或被感染设备的签名。此外，这个提议是建立在这样一个想法之上的，即这是可以做到的，即使它在局部没有留下任何痕迹——也就是说，即使随着时间的推移观察单个设备，它的行为在统计上与正常行为没有区别。这项工作建议通过开发网络逆问题的新范式来做到这一点：使用大量但极其微弱或嘈杂的信号作为网络取证工具，以揭示在网络上传播的隐藏结构、属性和现象。这需要使用和开发来自高维统计和集中，马尔可夫链耦合，图动力学和图理论的新工具，以获得一种统计理论，该理论描述了何时全球现象在统计上可检测到，从局部信号与噪声无法区分。我们所提出的工作的另一部分是开发高效、可扩展的算法来进行检测。在此基础上，该提案解决了两个基本挑战：开发具有不随网络规模扩展的信息需求的高效并行和分布式算法，其次，使用通过噪声信号提取的聚合网络反馈概念，以实现网络学习。

Interconnection is at the core of the functionality of our modern infrastructure, spreading ideas, technology and information. Future critical infrastructure, from self-driving cars to everything cloud computing promises to enable, exploit and depend on this interconnection and spreading capability. But as recent history shows, from denial of service attacks to state-driven cyberwarfare they will also suffer from it if vulnerabilities allow. The potential for broad destructive impact of malware is clear, particularly as the importance of mobile devices is on the rise. As more of our critical infrastructure becomes linked to devices end-users (consumers) control, and not merely a computer backbone whose hardware and software are centrally managed and controlled, the importance of maintaining the cyber-health of our devices will become increasingly critical, and much more difficult. The central theme of this proposal is its motto, if it spreads, it cannot hide. The motivation is to build a theory and accompanying algorithms that do not depend on the specifics of the network or devices, or on the specifics of what is spreading. If our defenses depend on detecting specific characteristics, by definition they miss any threat that does not share those. Rather, the high level idea is that if something spreads through a network, the spread itself will leave a signature independent of the design of the malware, or of the devices it is infecting. Moreover, the proposal is built on the idea that this can be done, even if locally it leaves no trace -- that is, even if looking at a single device over time, its behavior is statistically indistinguishable from normal behavior. This work proposes to do this by developing a new paradigm for network inverse problems: use plentiful but extremely weak or noisy signals as network forensics tools, to uncover hidden structure, properties, and phenomena spreading on the network. This requires using and developing new tools from high dimensional statistics and concentration, Markov chain coupling, graph dynamics and graph theory, to obtain a statistical theory that delineates the landscape of when global phenomena are statistically detectable, from local signals indistinguishable from noise. An equal part of the proposed work is then to develop efficient, scalable algorithms to do the detection. Building on this, the proposal tackles two fundamental challenges: developing efficient parallelizable and distributed algorithms with information requirements that do not scale in the size of the network, and second, using a notion of aggregate network feedback extracted through noisy signals, to enable network learning.