Byzantine Fault Tolerant (BFT) system designs have evolved to withstand increasingly challenging threat scenarios. In particular, network-attack-resilient BFT systems have developed frameworks for distributing replicas among multiple geographical sites to withstand sophisticated network denial of service attacks that can isolate an entire site. To make such systems economically feasible, data centers can be used in addition to on-premises sites to reduce the overall cost. Prior work focuses on developing system designs that tolerate a fixed number of replica failures and site disconnections. However, it has not considered the trade-offs between these designs in terms of their availability and cost. In this paper, we develop a framework to assess network-attack-resilient BFT systems in terms of their cost and availability, while accounting for differences between on-premises and data center sites. We compare five system designs proposed in the literature and identify the most cost-effective designs for a given availability target.

Byzantine Fault Tolerant (BFT) systems are used in applications that need to maintain high availability even in the presence of failures or compromises. BFT systems are typically designed to tolerate a preconfigured threshold number of faulty replicas (f), where the$f$faulty replicas may behave arbitrarily (potentially maliciously). However, as BFT system designs become more complex, it is important to evaluate the impact of such designs on the overall system availability with respect to standard crash faults. In this paper, we analyze three BFT systems that are designed to withstand both system compromises and network attacks: Spire, Confidential Spire, and Decoupled Spire. These network-attack-resilient BFT systems utilize a combination of on-premises and data center replicas to reduce cost and simplify deployment for system operators. We develop an availability model that accounts for differences between the availability of on- premises and data center replicas and analyze Spire, Confidential Spire, and Decoupled Spire under this model. Key system design insights from the analysis are that network-attack-resilient BFT configurations can meet the availability requirements of critical systems, as they provide higher availability than Classical BFT with less available servers. We show also that network-attack- resilient BFT configurations with fewer geographic sites provide higher availability, and that Confidential Spire has the highest availability, followed by Spire and then Decoupled Spire.

Compound threats, in which cyberattacks are targeted in the aftermath of a natural hazard, pose an important emerging threat for critical infrastructure. In this paper, we analyze the system design implications of compound threats for power grid SCADA systems for the first time. We introduce a novel compound threat model and develop a tool for analyzing resilience under this threat model. Using our tool, we compare the resilience of existing fault- and intrusion-tolerant SCADA system architectures in case studies based on two power utilities: Hawaiian Electric (HECO) and Florida Power & Light (FPL). We show that no existing system architecture adequately addresses compound threats, but that it is possible to improve resilience to such threats by explicitly considering natural hazards in the system design and by employing a new out-of-band reconfiguration mechanism for intrusion-tolerant systems. However, an important outcome of our work is that compound threats remain a challenging problem, with no complete solution.

Next generation cellular networks are expected to enable a wide range of new applications, increasing societal dependence on the network infrastructure and requiring a higher level of resilience than current networks. In this paper, we consider the challenges network operators face in providing end-to-end connections across the backhaul part of the cellular network in the face of equipment failures and power outages. In particular, we discuss the impact of the move to commodity hardware, disaggregation of the radio access network, edge computing, densification of the network, and the increased electric power requirements on resilience. Techniques and research directions for overcoming the challenges are presented. This includes thinking beyond methods for a single network operator including cooperative operator techniques and extending resilient overlays to the wireless edge.

Even with the rise of cyberattacks on high-value systems, we still do not see widespread adoption of intrusion-tolerant replication protocols, despite their long history in the research community and potential to support the needed resiliency. A key barrier is that deploying and managing intrusion-tolerant systems in practice requires substantial investment in additional physical infrastructure, as well as specialized technical expertise. In this work, we address this gap by designing a hybrid management model: while the system operator manages their application, a service provider hosts and manages the intrusion-tolerant replication service using cloud infrastructure. We develop the protocols to support this system architecture, without revealing application state, algorithms, or client information to the cloud provider, even when application servers are compromised. We implement and evaluate our approach in the context of an industrial control system and show that it meets the system's performance and resilience requirements.

The spread of an epidemic is often modeled by an SIR random process on a social network graph. The MinInfEdge problem for optimal social distancing involves minimizing the expected number of infections, when we are allowed to break at most B edges; similarly the MinInfNode problem involves removing at most B vertices. These are fundamental problems in epidemiology and network science. While a number of heuristics have been considered, the complexity of this problem remains generally open. In this paper, we present two bicriteria approximation algorithms for the MinInfEdge problem, which give the first non-trivial approximations for this problem. The first is based on the cut sparsification result technique of Karger, which works for any graph, when the transmission probabilities are not too small. The second is a Sample Average Approximation (SAA) based algorithm, which we analyze for the Chung-Lu random graph model. We also extend some of our results for the MinInfNode problem.

Recent work on intrusion-tolerance has shown that resilience to sophisticated network attacks requires system replicas to be deployed across at least three geographically distributed sites. While commodity data centers offer an attractive solution for hosting these sites due to low cost and management overhead, their use raises significant confidentiality concerns: system operators may not want private data or proprietary algorithms exposed to servers outside their direct control. We present a new model for Byzantine Fault Tolerant replicated systems that moves toward “intrusion tolerance as a service”. Under this model, application logic and data are only exposed to servers hosted on the system operator's premises. Additional offsite servers hosted in data centers can support the needed resilience without executing application logic or accessing unencrypted state. We have implemented this approach in the open-source Spire system, and our evaluation shows that the performance overhead of providing confidentiality can be less than 4% in terms of latency.

While there has been considerable research on making power grid Supervisory Control and Data Acquisition (SCADA) systems resilient to attacks, the problem of transitioning these technologies into deployed SCADA systems remains largely unaddressed. We describe our experience and lessons learned in deploying an intrusion-tolerant SCADA system in two realistic environments: a red team experiment in 2017 and a power plant test deployment in 2018. These experiences resulted in technical lessons related to developing an intrusion-tolerant system with a real deployable application, preparing a system for deployment in a hostile environment, and supporting protocol assumptions in that hostile environment. We also discuss some meta-lessons regarding the cultural aspects of transitioning academic research into practice in the power industry.

As key components of the power grid infrastructure, Supervisory Control and Data Acquisition (SCADA) systems are likely to be targeted by nation-state-level attackers willing to invest considerable resources to disrupt the power grid. We present Spire, the first intrusion-tolerant SCADA system that is resilient to both system-level compromises and sophisticated network-level attacks and compromises. We develop a novel architecture that distributes the SCADA system management across three or more active sites to ensure continuous availability in the presence of simultaneous intrusions and network attacks. A wide-area deployment of Spire, using two control centers and two data centers spanning 250 miles, delivered nearly 99.999% of all SCADA updates initiated over a 30-hour period within 100ms. This demonstrates that Spire can meet the latency requirements of SCADA for the power grid.

We consider the Shallow-Light Steiner Network problem from a fixed-parameter perspective. Given a graph $G$, a distance bound $L$, and $p$ pairs of vertices $(s_1,t_1),\cdots,(s_p,t_p)$, the objective is to find a minimum-cost subgraph $G'$ such that $s_i$ and $t_i$ have distance at most $L$ in $G'$ (for every $i \in [p]$). Our main result is on the fixed-parameter tractability of this problem with parameter $p$. We exactly characterize the demand structures that make the problem "easy", and give FPT algorithms for those cases. In all other cases, we show that the problem is W$[1]$-hard. We also extend our results to handle general edge lengths and costs, precisely characterizing which demands allow for good FPT approximation algorithms and which demands remain W$[1]$-hard even to approximate.

We consider the Shallow-Light Steiner Network problem from a fixed-parameter perspective. Given a graph G, a distance bound L, and p pairs of vertices {(s_i,t_i)}_{i in [p]}, the objective is to find a minimum-cost subgraph G' such that s_i and t_i have distance at most L in G' (for every i in [p]). Our main result is on the fixed-parameter tractability of this problem for parameter p. We exactly characterize the demand structures that make the problem "easy", and give FPT algorithms for those cases. In all other cases, we show that the problem is W[1]-hard. We also extend our results to handle general edge lengths and costs, precisely characterizing which demands allow for good FPT approximation algorithms and which demands remain W[1]-hard even to approximate.

While cyberattacks pose a relatively new challenge for power grid control systems, commercial cloud systems have needed to address similar threats for many years. However, technology and approaches developed for cloud systems do not necessarily transfer directly to the power grid, due to important differences between the two domains. We discuss our experience adapting intrusion-tolerant cloud technologies to the power domain and describe the challenges we have encountered and potential directions for overcoming those obstacles.

The dramatic success and scaling of the Internet was made possible by the core principle of keeping it simple in the middle and smart at the edge (or the end-to-end principle). However, new applications bring new demands, and for many emerging applications, the Internet paradigm presents limitations. For applications in this new generation of Internet services, structured overlay networks offer a powerful framework for deploying specialized protocols that can provide new capabilities beyond what the Internet natively supports by leveraging global state and in-network processing. The structured overlay concept includes three principles: A resilient network architecture, a flexible overlay node software architecture that exploits global state and unlimited programmability, and flow-based processing. We demonstrate the effectiveness of structured overlay networks in supporting today's demanding applications and propose forward-looking ideas for leveraging the framework to develop protocols that push the boundaries of what is possible in terms of performance and resilience.

Emerging applications such as remote manipulation and remote robotic surgery require communication that is both timely and reliable, but the Internet natively supports only communication that is either completely reliable with no timeliness guarantees (e.g. TCP) or timely with best-effort reliability (e.g. UDP). We present an overlay transport service that can provide highly reliable communication while meeting stringent timeliness guarantees (e.g. 130ms round-trip latency across the US) over the Internet. To enable routing schemes that can support the necessary timeliness and reliability, we introduce dissemination graphs, providing a unified framework for specifying routing schemes ranging from a single path, to multiple disjoint paths, to arbitrary graphs. We conduct an extensive analysis of real-world network data, finding that a routing approach using two disjoint paths performs well in most cases, and that cases where two disjoint paths do not perform well typically involve problems around a source or destination. Based on this analysis, we develop a timely dissemination-graph-based routing method that can add targeted redundancy in problematic areas of the network. This approach can cover over 99% of the performance gap between a traditional single-path approach and an optimal (but prohibitively expensive) scheme, while two dynamic disjoint paths cover about 70% of this gap, and two static disjoint paths cover about 45%. This performance improvement is obtained at a cost increase of about 2% over two disjoint paths.

The performance profile of local area networks has changed over the last decade, but many practical group communication and ordered messaging tools rely on core ideas invented over a decade ago. We present the Accelerated Ring protocol, a novel ordering protocol that improves on the performance of standard token-based protocols by allowing processes to pass the token before they have finished multicasting. This performance improvement is obtained while maintaining the correctness and other beneficial properties of token-based protocols. On 1-gigabit networks, a single-threaded daemon-based implementation of the protocol reaches network saturation, and can reduce latency by 45% compared to a standard token-based protocol while simultaneously increasing throughput by 30%. On 10-gigabit networks, the implementation reaches throughputs of 6 Gbps, and can reduce latency by 30-35% while simultaneously increasing throughput by 25-40%. A production implementation of the Accelerated Ring protocol has been adopted as the default ordering protocol for data center environments in Spread, a widely-used open-source group communication system.

As the Internet becomes an important part of the infrastructure our society depends on, it is crucial to construct networks that are able to work even when part of the network is compromised. This paper presents the first practical intrusion-tolerant network service, targeting high-value applications such as monitoring and control of global clouds and management of critical infrastructure for the power grid. We use an overlay approach to leverage the existing IP infrastructure while providing the required resiliency and timeliness. Our solution overcomes malicious attacks and compromises in both the underlying network infrastructure and in the overlay itself. We deploy and evaluate the intrusion-tolerant overlay implementation on a global cloud spanning East Asia, North America, and Europe, and make it publicly available.

Data center applications rely on messaging services that guarantee reliable, ordered message delivery for a wide range of distributed coordination tasks. Totally ordered multicast, which (informally) guarantees that all processes receive messages in exactly the same order, is particularly useful for maintaining consistent distributed state in systems as diverse as financial systems, distributed storage systems, cloud management, and big data analytics platforms.