Halo: High-Assurance Searches in Peer-to-Peer Networks

by Apu Kapadia

Massachusetts Institute of Technology

Date

Wednesday, March 11, 2009

Time

2:00 p.m. (special time) — 3:00 p.m.

Place

Informatics East (I2), Room 130

Abstract:  We study the problem of reliably searching for resources in untrusted peer-to-peer networks, where a significant portion of the participating network odes may act maliciously to subvert the search process. We present a new method called Halo for performing redundant searches over a distributed hash table (DHT) structure to achieve high integrity and availability levels without affecting the storage and communication complexities of the underlying DHT. Other schemes for redundant searches have proposed new or modified DHTs with increased storage requirements at nodes, requiring modifications at all nodes in the network. In contrast, Halo aims to serve as a middleware component, making "black-box" calls of the underlying primitive search operation to eventually provide a new composite search operation of higher assurance. We apply this concept to the popular and well-studied DHT Chord, and demonstrate the efficiency and security of our approach though analytical modeling and simulation-based analysis. For example, we show that for 12% malicious nodes in a network of 100,000 nodes, a regular Chord search fails more than 60% of the time. In contrast, Halo reduces this failure rate to 1%. We show how our scheme lends itself to a recursive version that can tolerate 22% malicious nodes with the same level of success, while regular Chord searches fail more than 80% of the time.

Biography:  Apu Kapadia received his Ph.D. in Computer Science from the University of Illinois at Urbana-Champaign. For his dissertation research on trustworthy communication, Apu received a four-year High-Performance Computer Science Fellowship from the Department of Energy. Following his doctorate, Apu joined Dartmouth College as a Post-Doctoral Research Fellow with the Institute for Security Technology Studies (ISTS), working with Profs. David Kotz and Sean Smith. He is now a researcher at MIT Lincoln Laboratory, a federally funded Department of Defense Laboratory at the Massachusetts Institute of Technology. Apu is interested in topics related to systems' security and privacy. He is particularly interested in privacy-enhancing technologies; usable models and policy languages for privacy; security in peer-to-peer networks, pervasive systems, and mobile computing; and applied  cryptography.  http://www.cs.dartmouth.edu/~akapadia/

Colloquium Provided By:

the School of Informatics