SRI Logo
About Us|R and D Divisions|Careers|Newsroom|Contact Us|SRI Home
  SRI Logo

Bonsai: Balanced Lineage Authentication
 by Dr. Ashish Gehani & Dr. Ulf Lindqvist.

In Proceedings of the 23rd Annual Computer Security Applications Conference (ACSAC 2007), Miami Beach, Florida, Dec. 10-14, 2007, pp. 363-373, ISBN 978-0-7695-3060-4.

The provenance of a piece of data is of utility to a wide range of applications. Its availability can be drastically increased by automatically collecting lineage information during filesystem operations. However, when data is processed by multiple users in independent administrative domains, the resulting filesystem metadata can only be trusted if it has been cryptographically certified. This has three ramifications: it slows down filesystem operations, it requires more storage for metadata, and verification depends on attestations from remote nodes.
We show that current schemes do not scale in a distributed environment. In particular, as data is processed, the latency of filesystem operations will degrade exponentially. Further, the amount of storage needed for the lineage metadata will grow at a similar rate. Next, we examine a completely decentralized scheme which has fast filesystem operations with minimal storage overhead. We demonstrate that its verification operation will fail with an exponentially increasing likelihood as more nodes are unreachable (due to being powered off or disconnected from the network). Finally, we present a new scheme, Bonsai, where the verification failure is significantly reduced by tolerating a small increase in filesystem latency and storage overhead for certification compared to filesystems without lineage certification.
Available as PDF here.


About Us  |  R&D Divisions  |  Careers  |  Newsroom  |  Contact Us
© 2024 SRI International 333 Ravenswood Avenue, Menlo Park, CA 94025-3493
SRI International is an independent, nonprofit corporation. Privacy policy