Toward Robust Monitoring of Malicious Outbreaks
研究在社交网络中部署监控器以检测恶意扩散（如计算机蠕虫传播）的博弈问题，提出α-监控博弈模型，考虑噪声扩散下的稳健策略，为安全防御提供理论支撑。
Recently, diffusion processes in social networks have attracted increasing attention within computer science, marketing science, social sciences, and political science. Although the majority of existing works focus on maximizing the reach of desirable diffusion processes, we are interested in deploying a group of monitors to detect malicious diffusion processes such as the spread of computer worms. In this work, we introduce and study the [Formula: see text]-Monitoring Game} on networks. Our game is composed of two parties an attacker and a defender. The attacker can launch an attack by distributing a limited number of seeds (i.e., virus) to the network. Under our [Formula: see text]-Monitoring Game, we say an attack is successful if and only if the following two conditions are satisfied: (1) the outbreak/propagation reaches at least α individuals without intervention, and (2) it has not been detected before reaching β individuals. Typically, we require that β is no larger than α in order to compensate the reaction delays after the outbreak has been detected. On the other end, the defender’s ultimate goal is to deploy a set of monitors in the network that can minimize attacker’s success ratio in the worst-case. (We also extend the basic model by considering a noisy diffusion model, where the propagation probabilities on each edge could vary within an interval.) Our work is built upon recent work in security games, our adversarial setting provides robust solutions in practice. Summary of Contribution: Although the diffusion processes in social networks have been extensively studied, most existing works aim at maximizing the reach of desirable diffusion processes. We are interested in deploying a group of monitors to detect malicious diffusion processes, such as the spread of computer worms. To capture the impact of model uncertainty, we consider a noisy diffusion model in which the propagation probabilities on each edge could vary within an interval. Our work is built upon recent work in security games; our adversarial setting leads to robust solutions in practice.