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

EPCN：弱信号强诊断：利用网络效应进行流行病检测

• 批准号: 1609279
• 负责人: Constantine Caramanis
• 金额: $ 36万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1609279&HistoricalAwards=false
• 关键词: EPCN; Strong; Diagnoses; Weak; Signals

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.

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

项目成果

Detecting Cascades from Weak Signatures

从弱签名中检测级联

• DOI: 10.1109/tnse.2017.2764444
• 发表时间: 2018
• 期刊: IEEE Transactions on Network Science and Engineering
• 影响因子: 6.6
• 作者: Meirom, Eli A.;Caramanis, Constantine;Mannor, Shie;Orda, Ariel;Shakkottai, Sanjay
• 通讯作者: Shakkottai, Sanjay