Visible to the public Adaptive Reconnaissance Attacks with Near-Optimal Parallel Batching

TitleAdaptive Reconnaissance Attacks with Near-Optimal Parallel Batching
Publication TypeConference Paper
Year of Publication2017
AuthorsLi, X., Smith, J. D., Thai, M. T.
Conference Name2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS)
Date Publishedjun
ISBN Number978-1-5386-1792-2
KeywordsAdaptive Approximation Algorithms, adaptive monotonic submodular properties, adaptive reconnaissance attacks, Adaptive Stochastic Optimization, Algorithm design and analysis, approximation ratio, data privacy, graph theory, Max-Crawling, near-optimal parallel batching, Network reconnaissance, Network topology, online social networks, Optimization, optimization problem, privacy, pubcrawl, Reconnaissance, Resiliency, social graph, Social network services, social networking (online), social networks analysis, stochastic programming, Target Reconnaissance Attacks, Topology, two-stage stochastic programming approach

In assessing privacy on online social networks, it is important to investigate their vulnerability to reconnaissance strategies, in which attackers lure targets into being their friends by exploiting the social graph in order to extract victims' sensitive information. As the network topology is only partially revealed after each successful friend request, attackers need to employ an adaptive strategy. Existing work only considered a simple strategy in which attackers sequentially acquire one friend at a time, which causes tremendous delay in waiting for responses before sending the next request, and which lack the ability to retry failed requests after the network has changed. In contrast, we investigate an adaptive and parallel strategy, of which attackers can simultaneously send multiple friend requests in batch and recover from failed requests by retrying after topology changes, thereby significantly reducing the time to reach the targets and greatly improving robustness. We cast this approach as an optimization problem, Max-Crawling, and show it inapproximable within (1 - 1/e + $e$). We first design our core algorithm PM-AReST which has an approximation ratio of (1 - e-(1-1/e)) using adaptive monotonic submodular properties. We next tighten our algorithm to provide a nearoptimal solution, i.e. having a ratio of (1 - 1/e), via a two-stage stochastic programming approach. We further establish the gap bound of (1 - e-(1-1/e)2) between batch strategies versus the optimal sequential one. We experimentally validate our theoretical results, finding that our algorithm performs nearoptimally in practice and that this is robust under a variety of problem settings.

Citation Keyli_adaptive_2017