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.