Ressourceneffiziente Fehler- und Einbruchstoleranz

More and more network-based services are considered essential by their operators: either because their unavailability might directly lead to economic losses, as with e-commerce applications or online auction services, for example, or because their well-functioning is crucial for the well-functioning of other services, which is, for example, the case for distributed file systems or coordination services. Byzantine fault-tolerant replication allows systems to be built that are able to ensure the availability and reliability of network-based services, even if a subset of replicas fail arbitrarily. As a consequence, such systems not only tolerate fault scenarios in which replicas crash, but also cases in which replicas have been taken over by an adversary as the result of a successful intrusion. Despite the fact that several major outages of network-based services in the past have been caused by non-crash failures, industry is still reluctant to broadly exploit the available research results on Byzantine fault tolerance. One of the main reasons for the decision to retain crash-tolerant systems is the high resource demand associated with Byzantine fault-tolerant systems: Besides the need to execute more costly protocols, the more complex fault model also requires Byzantine fault-tolerant systems to comprise more replicas than their crash-tolerant counterparts. In this thesis, we propose and evaluate different protocols and techniques to increase the resource efficiency of Byzantine fault-tolerant systems. The key insights that serve as a basis for all of these approaches are that during normal-case operation it is sufficient for a system to detect (or at least suspect) faults, while during fault handling a system must be able to actually tolerate faults, and that the former usually requires less resources than the latter. Utilizing these insights, we investigate different ways to improve resource efficiency by implementing a clear separation between normal-case operation and fault handling based on two modes of operation: During normal-case operation, a system reduces its resource usage to a level at which it is only able to ensure progress as long as all replicas behave according to specification. In contrast, in case of suspected or detected faults, the system switches to an operation mode in which it may use additional resources in order to tolerate faults. An important outcome of this thesis is that passive replication can be an effective building block for the implementation of a resource-efficient operation mode for normal-case operation in Byzantine fault-tolerant systems. Furthermore, experimental results show that improving the resource efficiency of a system can also lead to an increase in performance.Netzwerkbasierte Dienste werden von ihren Betreibern zunehmend als unentbehrlich angesehen: entweder weil ihr Ausfall direkt zu ökonomischen Verlusten führen könnte, wie etwa bei elektronischen Handelssystemen oder internetgestützten Auktionsdiensten, oder weil die Verfügbarkeit anderer Dienste von ihnen abhängt, wie es beispielsweise bei Netzwerkdateisystemen oder Koordinierungsdiensten der Fall sein kann. Das Prinzip der byzantinisch fehlertoleranten Replikation erlaubt es Systemen die Verfügbarkeit und Zuverlässigkeit von netzwerkbasierten Diensten sogar dann zu gewährleisten, wenn ein Teil der Replikate willkürliches Fehlverhalten zeigt. Solche Systeme können daher nicht nur Replikatausfälle tolerieren, sondern auch Szenarien, in denen Replikate als Folge von Einbrüchen von einem Angreifer übernommen wurden. Trotz der Tatsache, dass willkürliches Fehlverhalten von Systemkomponenten in der Vergangenheit zu mehreren schwerwiegenden Ausfällen von netzwerkbasierten Diensten geführt hat, werden existierende Forschungsergebnisse aus dem Bereich der byzantinischen Fehlertoleranz weiterhin kaum für den Produktiveinsatz genutzt. Einer der Hauptgründe dafür sich wie bisher auf ausfalltolerante Systeme zu beschränken ist der mit byzantinisch fehlertoleranten Systemen verbundene hohe Ressourcenbedarf: Neben der Notwendigkeit des Einsatzes aufwendigerer Protokolle macht es das komplexere Fehlermodell außerdem erforderlich, dass byzantinisch fehlertolerante Systeme mehr Replikate als vergleichbare ausfalltolerante Systeme bereitstellen. Diese Dissertation schlägt mehrere Protokolle und Techniken zur Steigerung der Ressourceneffizienz von byzantinisch fehlertoleranten Systemen vor und evaluiert sie. Allen hier präsentierten Ansätzen liegen dabei die zentralen Erkenntnisse zugrunde, dass es für den Normalbetrieb ausreicht Fehler erkennen (oder sie zumindest vermuten) zu können, wogegen sie im Zuge einer Fehlerbehandlung tatsächlich toleriert werden müssen, und dass ersteres weniger Ressourcen benötigt als letzteres. Aufbauend darauf, werden verschiedene Vorgehensweisen untersucht, wie sich die Ressourceneffizienz eines Systems durch eine klare Trennung des Normalbetriebs von der Fehlerbehandlung und die damit verbundene Einführung zweier Betriebsmodi steigern lässt: Im Normalfall befindet sich das System in einem Modus, in dem es seinen Ressourcenverbrauch so weit senkt, dass Fortschritt nur noch gewährleistet ist, solange sich alle Replikate korrekt verhalten. Im Unterschied dazu stehen im Fehlerbehandlungsmodus zusätzliche Ressourcen zur Verfügung, um Fehler tolerieren zu können; in ihn wird umgeschaltet, sobald das Auftreten von Fehlern entweder vermutet oder erkannt wird. Ein zentrales Resultat dieser Arbeit ist die Erkenntnis, dass passive Replikation ein effektives Mittel zur Implementierung eines ressourceneffizienten Normalbetriebsmodus darstellt. Darüber hinaus belegen Evaluationsergebnisse, dass eine verbesserte Ressourceneffizienz auch zu einer gesteigerten Leistungsfähigkeit eines Systems führen kann