[PAST EVENT] On Graphs as Side-Channels

October 16, 2015
3pm - 4pm
McGlothlin-Street Hall, Room 020
251 Jamestown Rd
Williamsburg, VA 23185Map this location

Location-based services, which employ data from smartphones, vehicles, etc., are growing in popularity. To reduce the threat that shared location data poses to a user's privacy, some services anonymize or obfuscate this data. In this paper, we show these methods can be effectively defeated: a set of location traces can be deanonymized given an easily obtained social network graph. The key idea of our approach is that a user may be identified by those she meets: a contact graph identifying meetings between anonymized users in a set of traces can be structurally correlated with a social network graph, thereby identifying anonymized users. We demonstrate the effectiveness of our approach using three real world datasets: University of St Andrews mobility trace and social network (27 nodes each), SmallBlue contact trace and Facebook social network (125 nodes), and Infocom 2006 bluetooth contact traces and conference attendees DBLP social network (78 nodes). Our experiments show that 80% of users are identified precisely, while only 8% are identified incorrectly, with the remainder mapped to a small set of users.

Key References:

1. Shouling Ji, Mudhakar Srivatsa and Raheem Beyah. Structural Data De-anonymization: Quantification, Practice and Implications. In ACM Conference on Computer and Communications Security (CCS), Nov 2014.

2. Mudhakar Srivatsa and Mike Hicks. Deanonymizing Mobility Traces: Using Social Network as a Side-Channel. In ACM Conference on Computer and Communication Security (CCS), Oct 2012.

3. Mudhakar Srivatsa. Breaking Mix-Zones using Road Network Graphs as a Side-Channel. Work in progress.

Bio: Dr. Srivatsa is a research scientist and manager of network analytics team at IBM Thomas J. Watson Research Center. His research interests primarily include network analytics and secure information flow. He serves as a technical area leader for Secure Hybrid Network research in US/UK International Technology Alliance in Network and Information Sciences and as a principal investigator for Information Network Research in Network Science Collaborative Technology Alliance where he is working on adversarial analysis of co-evolving networks (social, information, and communication).