Intrusion tolerance in large scale networks

Tese de doutoramento, Informática (Engenharia Informática), Universidade de Lisboa, Faculdade de Ciências, 2010The growing reliance on wide-area services demands highly available systems that provide a correct and uninterrupted service. Therefore, Byzantine Fault-Tolerant (BFT) algorithms have received considerable attention in the last years. A service is replicated over several servers and can survive even in the presence of a bounded number of Byzantine failures. The main motivation for this thesis is that for a replicated service to be fault-tolerant, common mode failures have to be avoided. More specifically, the thesis is concerned with common mode failures caused by natural disasters, power outages and physical attacks, which have to be prevented by scattering replicas geographically. This requires the sites where the replicas reside to be connected by a wide-area network (WAN) like the Internet. Unfortunately, when the replicas are distributed geographically the performance of current BFT algorithms is affected by the lower bandwidths, and the higher and more heterogeneous network latencies. In order to deal with these limitations this thesis introduces novel BFT algorithms that are simultaneously efficient and secure. Some algorithms of this thesis are based on a hybrid fault model, i.e., considering that a part of the system is secure by construction. A notable contribution of this thesis is the definition and implementation of a minimal trusted service: the Unique Sequential Identifier Generator (USIG). The thesis describes how to implement a 2 f +1 Byzantine consensus algorithm using a 2 f +1 reliable multicast algorithm that requires a trusted service, that is an abstract version of the USIG. Then, the USIG service and the reliable multicast primitive are applied as a core component to implement two novel BFT algorithms introduced in this thesis: MinBFT and MinZyzzyva. These BFT algorithms are minimal in terms of number of replicas, complexity of the trusted service used, and number of communication steps. In order to mitigate performance degradation attacks, this thesis proposes the use of a rotating primary defining a novel BFT algorithm, Spinning, that is less vulnerable to attacks caused by a faulty primary and attains a throughput similar to the baseline algorithm in the area. Finally, the mechanisms and techniques developed in this thesis are combined in order to define EBAWA, a novel BFT algorithm that is suitable for supporting the execution of wide-area replicated services.O crescimento da dependência na utilização de serviços informáticos em redes de larga escala demanda sistemas que forneçam um serviço correcto e ininterrupto. Por este motivo, algoritmos tolerantes a faltas bizantinas (BFT) têm recebido considerável atenção nos últimos anos. A ideia fundamental destes algoritmos é replicar um determinado serviço num conjunto de servidores, assegurando a sua operação contínua mesmo na presença de um número limitado de servidores faltosos. Cada servidor é uma réplica, uma máquina de estados determinística que executa operações em resposta a requisições realizadas por clientes. Para que serviços replicados sejam tolerantes a faltas, modos comuns de falhas devem ser evitados, essa ´e a principal motivação desta tese. Mais especificamente, a tese trata de falhas causadas por desastres naturais, falta de energia e ataques físicos. Para que a ocorrência destas falhas afecte um número limitado de servidores é necessário distribuir as réplicas geograficamente. Esta distribuição, requer que os locais onde se situam as réplicas sejam conectados por uma rede de larga-escala (WAN), como a Internet. Infelizmente, quando as réplicas estão distribuídas geograficamente o desempenho dos algoritmos BFT actuais é afectado pelas limitações de largura de banda e latências heterogéneas, típicas em redes de larga-escala. A fim de tratar destas limitações esta tese introduz novos algoritmos BFT que são simultaneamente eficientes e seguros. Alguns destes algoritmos são baseados em um modelo de faltas híbrido, por exemplo, parte do sistema ´e considerado seguro pela sua construção. Uma importante contribuição desta tese é a definição e concretização de um serviço confiável mínimo: o gerador de identificador único e sequencial (USIG). A tese descreve como concretizar algoritmos de consenso bizantinos com 2 f +1 processos, usando um algoritmo de reliable multicast que requer um componente confiável, uma abstração do USIG. O serviço USIG e a primitiva de reliable multicast são aplicados como componentes nucleares na concretização de dois novos algoritmos BFT introduzidos nesta tese: MinBFT e MinZyzzyva. Estes algoritmos são mínimos em termos de número de réplicas, complexidade do componente confiável e número de passos de comunicação. A fim de mitigar os ataques de degradação de desempenho esta tese propõe o uso de um primário rotativo, definindo assim um novo algoritmo BFT, o Spinning. Al´em de ser menos vulnerável a ataques causados por primários faltosos, o Spinning atinge um débito similar ao algoritmo base. Finalmente, os mecanismos e técnicas desenvolvidos ao longo desta tese são combinados com o objectivo de definir o EBAWA, um novo algoritmo BFT que é adequado para suportar a execução de serviços replicados em redes de larga-escala.Programme ALBAN; Fundação para a Ciência e a Tecnologia - Portuga