No description available.

This technical report complements the paper entitled “Scalable error isolation for distributed systems” published at USENIX NSDI 15.

Fault tolerant and secure distributed data storage systems typically require that only up to a threshold of storage nodes can ever be compromised or fail. In proactively-secure systems, this requirement is modified to hold only in a time interval (also called epoch), resulting in increased security. An attacker or adversary could compromise distinct sets of nodes in any two time intervals. This attack model is also called the mobile adversary model. Proactively-secure systems require all nodes to "refresh" themselves periodically to a clean state to maintain the availability, integrity, and confidentiality properties of the data storage service. This dissertation investigates the design of a proactively-secure distributed data storage system. Data can be stored at storage servers using encoding schemes called secret sharing, or encryption-with-replication. The primary challenge is that the protocols that the servers run periodically to maintain integrity and confidentiality must scale with large amounts of stored data. Determining how much data can be proactively-secured in practical settings is an important objective of this dissertation. The protocol for maintain the confidentiality of stored data is developed in the context of data storage using secret sharing. We propose a new technique called the GridSharing framework that uses a combination of XOR secret sharing and replication for storing data efficiently. We experimentally show that the algorithm can secure several hundred GBs of data. We give distributed protocols run periodically by the servers for maintaining the integrity of replicated data under the mobile adversary model. This protocol is integrated into a document repository to make it proactively-secure. The proactively-secure document repository is implemented and evaluated on the Emulab cluster (http://www.emulab.net). The experimental evaluation shows that several 100 GBs of data can be proactively-secured. This dissertation also includes work on fault and intrusion detection - a necessary component in any secure system. We give a novel Byzantine-fault detection algorithm for quorum systems, and experimentally evaluate its performance using simulations and by deploying it in the AgileFS distributed file system.

Au cours de la dernière décennie, l'informatique en nuage (Cloud Computing) suscita un important changement de paradigme dans de nombreux systèmes d'information. Ce nouveau paradigme s'illustre principalement par la délocalisation de l'infrastructure informatique hors du parc des entreprises, permettant ainsi une utilisation des ressources à la demande. La prise en charge de serveurs locaux s'est donc vue peu à peu remplacée par la location de serveurs distants, auprès de fournisseurs spécialisés tels que Google, Amazon, Microsoft. Afin d'assurer la pérennité d'un tel modèle économique, il apparaît nécessaire de fournir aux utilisateurs diverses garanties relatives à la sécurité, la disponibilité, ou encore la fiabilité des ressources mises à disposition. Ces facteurs de qualité de service (QoS pour Quality of Service) permettent aux fournisseurs et aux utilisateurs de s'accorder sur le niveau de prestation escompté. En pratique, les serveurs mis à disposition des utilisateurs doivent épisodiquement faire face à des fautes arbitraires (ou byzantines). Il s'agit par exemple de ruptures temporaires du réseau, du traitement de messages corrompus, ou encore d’arrêts inopinés. Le contexte d'informatique en nuage s'est vu néanmoins propice à l'émergence de technologies telles que la virtualisation ou la réplication de machines à états. De telles technologies permettent de pallier efficacement à l’occurrence de pannes via l'implémentation de protocoles de tolérance aux pannes.La tolérance aux fautes byzantines (BFT pour Byzantine Fault Tolerance) est un domaine de recherche implémentant les concepts de réplication de machines à états, qui vise à assurer la continuité et la fiabilité des services en présence de comportements arbitraires. Afin de répondre à cette problématique, de nombreux protocoles furent proposés. Ceux-ci se doivent d'être efficaces afin de masquer le surcoût lié à la réplication, mais également robustes afin de maintenir un niveau de performance élevé en présence de fautes. Nous constatons d'abord qu'il est délicat de relever ces deux défis à la fois: les protocoles actuels sont soit conçus pour être efficaces au détriment de leur robustesse, soit pour être robustes au détriment de leur efficacité. Cette thèse se focalise autour de cette problématique, l'objectif étant de fournir les instruments nécessaires à la conception de protocoles à la fois robustes et efficaces.Notre intérêt se porte principalement vers deux types de dénis de service liés à la gestion des requêtes. Le premier de ces dénis de service est causé par la corruption partielle d'une requête lors de son émission par un client. Le deuxième est causé par l'abandon intentionnel d'une requête lors de sa réception par un réplica. Afin de faire face efficacement à ces deux comportements byzantins, plusieurs mécanismes dédiés furent implémentés dans les protocoles de BFT robustes. En pratique, ces mécanismes engendrent d'importants surcoûts, ce qui nous permet d'introduire notre première contribution: la définition de plusieurs principes de conception génériques destinés à réduire ces surcoûts tout en assurant un niveau de robustesse équivalent.La seconde contribution de cette thèse illustre ER-PBFT, un nouveau protocole implémentant ces principes de conception sur PBFT, la référence en matière de tolérance aux fautes byzantines. Nous démontrons l'efficacité de notre nouvelle politique de robustesse, à la fois en présence de comportements byzantins mais également lors de scénarios sans faute.La troisième contribution illustre ER-COP, un nouveau protocole orienté à la fois vers l’efficacité et la robustesse, implémentant nos principes de conception sur COP, le protocole de BFT fournissant les meilleures performances à l'heure actuelle dans un environnement sans faute. Nous évaluons le surcoût engendré par l'intégration de notre politique de robustesse, et nous démontrons la capacité de ER-COP à tolérer l'occurrence de comportements byzantins. / Over the last decade, Cloud computing instigated an important switch of paradigm in numerous information systems. This new paradigm is mainly illustrated by the re-location of the whole IT infrastructures out of companies’ warehouses. The use of local servers has thus being replaced by remote ones, rented from dedicated providers such as Google, Amazon, Microsoft.In order to ensure the sustainability of this economic model, it appears necessary to provide several guarantees to users, related to the security, availability, or even reliability of the proposed resources. Such quality of service (QoS) factors allow providers and users to reach an agreement on the expected level of dependability. Practically, the proposed servers must episodically cope with arbitrary faults (also called byzantine faults), such as incorrect/corrupted messages, servers crashes, or even network failures. Nevertheless, the Cloud computing environment encouraged the emergence of technologies such as virtualization or state machine replication. These technologies allow cloud providers to efficiently face the occurrences of faults through the implementation of fault tolerance protocols.Byzantine Fault Tolerance (BFT) is a research area involving state machine replication concepts, and aiming at ensuring continuity and reliability of hosted services in presence of any kind of arbitrary behaviors. In order to handle such threat, numerous protocols were proposed. These protocols must be efficient in order to counterbalance the extra cost of replication, and robust in order to lower the impact of byzantine behaviors on the system performance. We first noticed that tackling both these concerns at the same time is difficult: current protocols are either designed to be efficient at the expense of their robustness, or robust at the expense of their efficiency. We tackle this specific problem in this thesis, our goal being to provide the required tools to design both efficient and robust BFT protocols.Our focus is mainly dedicated to two types of denial-of-service attacks involving requests management. The first one is caused by the partial corruption of a request transmitted by a client. The second one is caused by the intentional drop of a request upon receipt. In order to face efficiently both these byzantine behaviors, several mechanisms were integrated in robust BFT protocols. In practice, these mecanisms involve high overheads, and thus lead to the significant performance drop of robust protocols compared to efficien ones. This assessment allows us to introduce our first contribution: the definition of several generic design principles, applicable to numerous existing BFT protocols, and aiming at reducing these overheads while maintaining the same level of robustness.The second contribution introduces ER-PBFT, a new protocol implementing these design principles on PBFT, the reference in terms of byzantine fault tolerance. We demonstrate the efficiency of our new robustness policy, both in fault-free scenarios and in presence of byzantine behaviors.The third contribution highlights ER-COP, a new BFT protocol dedicated to both efficiency and robustness, implementing our design principles on COP, the BFT protocol providing for now the best performances in a fault-free environment. We evaluate the additional cost introduced by our robustness policy, and we demonstrate ER-COP's ability to handle byzantine behaviors.

In distributed systems, if a hardware fault corrupts the state of a process, this error might propagate as a corrupt message and contaminate other processes in the system, causing severe outages. Recently, state corruptions of this nature have been observed surprisingly often in large computer populations, e.g., in large-scale data centers. Moreover, since the resilience of processors is expected to decline in the near future, the likelihood of state corruptions will increase even further. In this work, we argue that preventing the propagation of state corruption should be a first-class requirement for large-scale fault-tolerant distributed systems. In particular, we propose developers to target error isolation, the property in which each correct process ignores any corrupt message it receives. Typically, a process cannot decide whether a received message is corrupt or not. Therefore, we introduce hardening as a class of principled approaches to implement error isolation in distributed systems. Hardening techniques are (semi-)automatic transformations that enforce that each process appends an evidence of good behavior in the form of error codes to all messages it sends. The techniques “virtualize” state corruptions into more benign failures such as crashes and message omissions: if a faulty process fails to detect its state corruption and abort, then hardening guarantees that any corrupt message the process sends has invalid error codes. Correct processes can then inspect received messages and drop them in case they are corrupt. With this dissertation, we contribute theoretically and practically to the state of the art in fault-tolerant distributed systems. To show that hardening is possible, we design, formalize, and prove correct different hardening techniques that enable existing crash-tolerant designs to handle state corruption with minimal developer intervention. To show that hardening is practical, we implement and evaluate these techniques, analyzing their effect on the system performance and their ability to detect state corruptions in practice.

This technical report complements the paper entitled “Scalable error isolation for distributed systems” published at USENIX NSDI 15.

BFT consensus algorithms can ensure the consistency of distributed systems where nodes may behave arbitrarily due to faults or intentional malicious actions. However, most of the practical BFT consensus algorithms are leader-based. In an adversarial network, leader-based BFT consensus algorithms exhibit vulnerabilities and lack resilience. Byzantine leaders can pose a potential threat to the system; firstly, malicious leaders can actively downgrade the processing speed of handling proposals, thereby diminishing the system’s overall performance. Secondly, they can determine the submission order of received requests, which can be fatal in specific decentralized financial systems. Additionally, external attackers can compromise the system’s stability by conducting DDoS attacks on leader nodes, frequently triggering view changes and potentially causing the system to lose liveness altogether. We present BFT Baxos, a more robust and resilient BFT consensus protocol that equips a BFT random exponential backoff mechanism to ensure each node has the egalitarian right to propose. Employing random exponential backoff as a replacement for leader election eliminates the potential malicious actions of Byzantine leaders and prevents external attackers from conducting targeted DDoS attacks on the leader node within systems. We implemented and evaluated our BFT Baxos prototype. Our results indicate that BFT Baxos exhibits good performance and scalability in low-concurrency scenarios. Additionally, we illustrated the functioning of BFT Baxos even in extremely adverse network conditions by subjecting it to random DDoS attacks. / BFT-konsensusalgoritmer är utformade för att säkerställa konsistensen i distribuerade system där noder kan agera godtyckligt, antingen på grund av fel eller avsiktliga skadliga handlingar. Dock är de flesta praktiska BFT-konsensusalgoritmerna baserade på ledare. I en fientlig nätverksmiljö uppvisar ledar-baserade BFT-konsensusalgoritmer sårbarheter och brist på motståndskraft. Bysantinska ledare kan utgöra en potentiell hot mot systemet; för det första kan skadliga ledare aktivt sänka behandlingshastigheten för hantering av förslag och därigenom minska systemets totala prestanda. För det andra kan de bestämma ordningen för inskickning av mottagna begäranden, vilket kan vara ödesdigert i vissa decentraliserade finansiella system. Dessutom kan externa angripare kompromettera systemets stabilitet genom att genomföra DDoS-attacker mot ledarnoder, vilket ofta utlöser vynändringar och potentiellt orsakar att systemet förlorar livskraft helt och hållet. Vi presenterar BFT Baxos, en mer robust och motståndskraftig BFT-konsensusprotokoll som utrustar en BFT slumpmässig exponentiell backoff-mekanism för att säkerställa att varje nod har rätten att föreslå på ett egalitärt sätt. Genom att använda slumpmässig exponentiell backoff som ett alternativ till ledarval eliminerar det inte bara möjliga skadliga handlingar från bysantinska ledare utan förhindrar även externa angripare från att genomföra riktade DDoS-attacker mot ledarnoden inom system. Vi implementerade och utvärderade vår BFT Baxos-prototyp. Våra resultat visar att BFT Baxos uppvisar god prestanda och skalbarhet i scenarier med låg samtidighet. Dessutom illustrerade vi funktionen av BFT Baxos även under extremt ogynnsamma nätverksförhållanden genom att utsätta den för slumpmässiga DDoS-attacker.

Information technology systems are essential for most businesses as they facilitate the handling and sharing of data and the execution of tasks. Due to connectivity to the internet and other internal networks, these systems are susceptible to cyberattacks. Computer worms are one of the most significant threats to computer systems because of their fast self-propagation to multiple systems and malicious payloads. Modern worms employ obfuscation techniques to avoid detection using patterns from previous attacks. Although the best defense is to eliminate (patch) the software vulnerabilities being exploited by computer worms, this requires a substantial amount of time to create, test, and deploy the patches. Worm containment techniques are used to reduce or stop the spread of worm infections to allow time for software patches to be developed and deployed. In this dissertation, a novel blockchain-based collaborative intrusion prevention system model is introduced. This model is designed to proactively contain zero-day and obfuscated computer worms. In this model, containment is achieved by creating and distributing signatures for the exploited vulnerabilities. Blockchain technology is employed to provide liveness, maintain an immutable record of vulnerability-based signatures to update peers, accomplish trust in confirming the occurrence of a malicious event and the corresponding signature, and allow a decentralized defensive environment. A consensus algorithm based on the Practical Byzantine Fault Tolerance (PBFT) algorithm is employed in the model. The TLA+ formal method is utilized to check the correctness, liveness, and safety properties of the model as well as to assert that it has no behavioral errors. A blockchain-based automatic worm containment system is implemented. A synthetic worm is created to exploit a network-deployed vulnerable program. This is used to evaluate the effectiveness of the containment system. It is shown that the system can contain the worm and has good performance. The system can contain 100 worm attacks a second by generating and distributing the corresponding vulnerability-based signatures. The system latency to contain these attacks is less than 10 ms. In addition, the system has low resource requirements with respect to memory, CPU, and network traffic. / Graduate

<p>The advent of advanced communication technologies has given rise to large-scale networks comprised of numerous interconnected agents, which need to cooperate to accomplish various tasks, such as distributed message routing, formation control, robust statistical inference, and spectrum access coordination. These tasks can be formulated as distributed optimization problems, which require agents to agree on a parameter minimizing the average of their local cost functions by communicating only with their neighbors. However, distributed optimization algorithms are typically susceptible to malicious (or "Byzantine") agents that do not follow the algorithm. This thesis offers analysis and algorithms for such scenarios. As the malicious agent's function can be modeled as an unknown function with some fundamental properties, we begin in the first two parts by analyzing the region containing the potential minimizers of a sum of functions. Specifically, we explicitly characterize the boundary of this region for the sum of two unknown functions with certain properties. In the third part, we develop resilient algorithms that allow correctly functioning agents to converge to a region containing the true minimizer under the assumption of convex functions of each regular agent. Finally, we present a general algorithmic framework that includes most state-of-the-art resilient algorithms. Under the strongly convex assumption, we derive a geometric rate of convergence of all regular agents to a ball around the optimal solution (whose size we characterize) for some algorithms within the framework.</p>

La Tolérance aux pannes Byzantines (BFT) est de plus en plus cruciale avec l'évolution d'applications et en raison de la croissance de l'innovation technologique en informatique. Bien que des dizaines de protocoles BFT aient été introduites dans les années précédentes, leur mise en œuvre ne semble pas satisfaisant. Pour faire face à cette complexité, due à la dépendance d'un protocole d'une situation, nous tentons une approche qui permettra de sélectionner un protocole en fonction d'une situation. Ceci nous paraît, en s'inspirant de tout système d'encrage, comme une démarche nécessaire pour aborder la problématique de la BFT. Dans cette thèse, nous introduisons un modèle de sélection ainsi que l'algorithme qui permet de simplifier et d'automatiser le processus d'élection d'un protocole. Ce mécanisme est conçu pour fonctionner selon 3 modes : statique, dynamique et heuristique. Les deux derniers modes, nécessitent l'introduction d'un système réactif, nous ont conduits à présenter un nouveau modèle BFT: Adapt. Il réagit à tout changement et effectue, d'une manière adaptée, la commutation entre les protocoles d'une façon dynamique. Le mode statique permet aux utilisateurs de BFT de choisir un protocole BFT en une seule fois. Ceci est très utile dans les services Web et les " Clouds " où le BFT peut être fournit comme un service inclut dans le contrat (SLA). Ce mode est essentiellement conçu pour les systèmes qui n'ont pas trop d'états fluctuants. Pour ce faire, un processus d'évaluation est en charge de faire correspondre, à priori, les préférences de l'utilisateur aux profils du protocole BFT nommé, en fonction des critères de fiabilité et de performance. Le protocole choisi est celui qui réalise le meilleur score d'évaluation. Le mécanisme est bien automatisé à travers des matrices mathématiques, et produit des sélections qui sont raisonnables. D'autres systèmes peuvent cependant avoir des conditions flottantes, il s'agit de la variation des charges ou de la taille de message qui n'est pas fixe. Dans ce cas, le mode statique ne peut continuer à être efficace et risque de ne pas pouvoir s'adapter aux nouvelles conditions. D'où la nécessité de trouver un moyen permettant de répondre aux nouvelles exigences d'une façon dynamique. Adapt combine un ensemble de protocoles BFT ainsi que leurs mécanismes de commutation pour assurer l'adaptation à l'évolution de l'état du système. Par conséquent, le "Meilleur" protocole est toujours sélectionné selon l'état du système. On obtient ainsi une qualité optimisée de service, i.e., la fiabilité et la performance. Adapt contrôle l'état du système grâce à ses mécanismes d'événements, et utilise une méthode de "Support Vector Regrssion" pour conduire aux prédictions en temps réel pour l'exécution des protocoles (par exemple, débit, latence, etc.). Ceci nous conduit aussi à un mode heuristique. En utilisant des heuristiques prédéfinies, on optimise les préférences de l'utilisateur afin d'améliorer le processus de sélection. L'évaluation de notre approche montre que le choix du "meilleur" protocole est automatisé et proche de la réalité de la même façon que dans le mode statique. En mode dynamique, Adapt permet toujours d'obtenir la performance optimale des protocoles disponibles. L'évaluation démontre, en plus, que la performance globale du système peut être améliorée de manière significative. Explorer d'autres cas qui ne conduisent pas de basculer entre les protocoles. Ceci est rendu possible grâce à la réalisation des prévisions d'une grande précision qui peuvent atteindre plus de 98%dans de nombreux cas. La thèse montre que cette adaptabilité est rendue possible grâce à l'utilisation des heuristiques dans un mode dynamique.