Trapping Malicious Crawlers in Social Networks
Trapping Malicious Crawlers in Social Networks
复制标题
DOI：
10.1145/3340531.3412004
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Shiju Li;Chul-Ho Lee;Do Young Eun
中科院分区：
文献类型：
--
作者：
Shiju Li;Chul-Ho Lee;Do Young Eun
本文研究了在社交网络中捕获恶意网络爬虫的问题，以最大限度地减少恶意爬虫窃取个人/隐私信息的攻击。问题是要找到在哪里放置一个给定的一组陷阱在一个图，以尽量减少预期数量的用户谁可能成为牺牲品（可能是随机的）一组恶意爬虫，其中每个遍历图中的随机行走的方式为一个随机的有限时间。我们首先证明了这个问题是NP-困难的，也是一个单调的子模极大化问题。然后，我们提出了一个贪婪算法，实现了（1 -1/e$）-近似。我们还开发了一个$（ε，δ）$-近似蒙特卡罗估计，以减轻计算的贪婪算法，从而使算法可扩展的大型图。最后，我们提出了广泛的模拟结果表明，我们的算法显着优于其他基线算法的基础上，各种中心性措施。
In this paper, we study a problem of trapping malicious web crawlers in social networks to minimize the attacks from crawlers with malicious intents to steal personal/private information. The problem is to find where to place a given set of traps over a graph so as to minimize the expected number of users who possibly fall prey to a (possibly random) set of malicious crawlers, each of which traverses the graph in a random-walk fashion for a random finite time. We first show that this problem is NP-hard and also a monotone submodular maximization problem. We then present a greedy algorithm that achieves a ($1-1/e$)-approximation. We also develop an $(ε,δ)$-approximation Monte Carlo estimator to ease the computation of the greedy algorithm and thus make the algorithm scalable for large graphs. We finally present extensive simulation results to show that our algorithm significantly outperforms other baseline algorithms based on various centrality measures.