In dieser Arbeit stellen wir verteilte Informations- und Speichersysteme vor, die gegen Angriffe eines Insiders beweisbar robust sind. Ein Insider ist dabei ein Gegner, der Wissen über das gesamte System hat. Unsere Systeme erlauben signifikant mehr als polylogarithmisch viele durch einen Insider angegriffene Server und garantieren gleichzeitig polylogarithmische Schranken für die Effizienz (in Anzahl der Server) und eine höchstens logarithmische Redundanz. Zuerst stellen wir Basic IRIS vor, ein verteiltes Informationssystem, das trotz der Existenz eines Insiders, der bis zu O(n^(1/loglog(n))) Server abstürzen lassen kann, beweisbar korrekt arbeitet (wobei n die Anzahl der Server im System bezeichnet). Genauer gesagt beantwortet Basic IRIS jede Menge von Suchanfragen (mit höchstens O(1) Anfragen pro nicht abgestürzten Server) in polylogarithmischer Zeit und mit polylogarithmischem Aufwand pro Server bei konstanter Redundanz. Durch Erweiterung von Basic IRIS erhalten wir Enhanced IRIS, ein verteiltes Informationssystem mit logarithmischer Redundanz, das gegen einen Insider robust ist, der einen konstanten Anteil aller Server zum Absturz bringen kann.Aufbauend auf IRIS stellen wir mit RoBuSt ein verteiltes Speichersystem vor, das zusätzlich Schreibanfragen effizient beantwortet und logarithmische Redundanz besitzt. Abschließend verstärken wir den betrachteten Gegner noch weiter, indem wir diesem das Korrumpieren des Speichers der Server erlauben. Das heißt, der Gegner darf den permanenten Speicher der Server korrumpieren, jedoch nicht deren Arbeitsspeicher oder Protokolle. Mit OSIRIS stellen wir ein verteiltes Speichersystem mit asymptotisch gleicher Effizienz und Redundanz wie RoBuSt vor, das jede Menge von Such- und Schreibanfragen trotz der Präsenz eines Insiders, der den Speicher von O(n^(1/loglog(n))) Servern korrumpieren darf, beweisbar korrekt beantwortet.
Bibliographic Metadata
- TitleInsider-resistant distributed storage systems / Martina Eikel ; [Reviewers: Prof. Dr. Christian Scheideler, University of Paderborn, Prof. Dr. Friedhelm Meyer auf der Heide, University of Paderborn]
- Author
- Participants
- Corporate name
- Published
- EditionElektronische Ressource
- Description1 Online-Ressource (viii, 145 Seiten) : Illustrationen
- Institutional NoteFaculty of Computer Science, Electrical Engineering and Mathematics, Department of Computer Science, Univ., Dissertation, 2015
- AnnotationTag der Verteidigung: 16.02.2016
- Defended on2016-02-16
- LanguageEnglish
- Document TypesDissertation (PhD)
- URN
- Social MediaShare
- Reference
- IIIF
In this work we present distributed information and storage systems that are provably robust against attacks by an insider adversary, i.e., an adversary with complete knowledge of the system. Our systems break the barrier between allowing significantly more than a polylogarithmic number of servers to be attacked by an insider adversary on the one hand, but still adhering to polylogarithmic efficiency bounds (in the number of servers) and at most logarithmic redundancy on the other hand. First, we present Basic IRIS, a distributed information system that works provably correctly despite the existence of an insider adversary that may crash up to O(n^(1/loglog(n))) servers (with n being the number of servers in the system). To be more precise, Basic IRIS provably correctly serves any set of lookup requests (with at most O(1) requests per server not crashed) with polylogarithmic time and work and a constant redundancy. By extending Basic IRIS, we end up with Enhanced IRIS, a distributed information system that tolerates even up to a constant fraction of all servers to be crashed by an insider adversary with a logarithmic redundancy. Building on IRIS, we present RoBuSt, a distributed storage system that additionally answers write requests with polylogarithmic time and work and a logarithmic redundancy. Finally, we strengthened the adversary even further by allowing it to corrupt the servers storage. To be more precise, the adversary may corrupt the permanent storage of the servers, but it is not allowed to corrupt the servers' main memory or the protocol itself. With OSIRIS we present a distributed storage system that provably correctly serves any set of lookup and write requests (with at most O(1) requests per server) despite the existence of an insider adversary that may corrupt the storage of up to O(n^(1/loglog(n))) servers while asymptotically adhering to the same efficiency and redundancy bounds as RoBuSt.
- The PDF-Document has been downloaded 43 times.