Biblio

In this paper, we study the resilient vector consensus problem in multi-agent networks and improve resilience guarantees of existing algorithms. In resilient vector consensus, agents update their states, which are vectors in ℝd, by locally interacting with other agents some of which might be adversarial. The main objective is to ensure that normal (non-adversarial) agents converge at a common state that lies in the convex hull of their initial states. Currently, resilient vector consensus algorithms, such as approximate distributed robust convergence (ADRC) are based on the idea that to update states in each time step, every normal node needs to compute a point that lies in the convex hull of its normal neighbors' states. To compute such a point, the idea of Tverberg partition is typically used, which is computationally hard. Approximation algorithms for Tverberg partition negatively impact the resilience guarantees of consensus algorithm. To deal with this issue, we propose to use the idea of centerpoint, which is an extension of median in higher dimensions, instead of Tverberg partition. We show that the resilience of such algorithms to adversarial nodes is improved if we use the notion of centerpoint. Furthermore, using centerpoint provides a better characterization of the necessary and sufficient conditions guaranteeing resilient vector consensus. We analyze these conditions in two, three, and higher dimensions separately. We also numerically evaluate the performance of our approach.

Recent disasters have shown that hazards can be unpredictable and can have catastrophic consequences. Emergency plans are key to dealing with these situations and communications play a key role in emergency management. In this paper, we provide a formalism to design resilient emergency plans in terms of communications. We exemplify how to use the formalism using a case study of a Nuclear Emergency Plan.

With the emergence of smart grids as the primary means of distribution across wide areas, the importance of improving its resilience to faults and mishaps is increasing. The reliability of a distribution system depends upon its tolerance to attacks and the efficiency of restoration after an attack occurs. This paper proposes a unique approach to the restoration of smart grids under attack by impostors or due to natural calamities via optimal islanding of the grid with primary generators and distributed generators(DGs) into sub-grids minimizing the amount of load shed which needs to be incurred and at the same time minimizing the number of switching operations via graph theory. The minimum load which needs to be shed is computed in the first stage followed by selecting the nodes whose load needs to be shed to achieve such a configuration and then finally deriving the sequence of switching operations required to achieve the configuration. The proposed method is tested against standard IEEE 37-bus and a 1069-bus grid system and the minimum load shed along with the sequencing steps to optimal configuration and time to achieve such a configuration are presented which demonstrates the effectiveness of the method when compared to the existing methods in the field. Moreover, the proposed algorithm can be easily modified to incorporate any other constraints which might arise due to any operational configuration of the grid.

The growing size of modern datasets necessitates splitting a large scale computation into smaller computations and operate in a distributed manner for improving overall performance. However, adversarial servers in a distributed computing system deliberately send erroneous data in order to affect the computation for their benefit. Computing Boolean functions is the key component of many applications of interest, e.g., classification problem, verification functions in the blockchain and the design of cryptographic algorithm. In this paper, we consider the problem of computing a Boolean function in which the computation is carried out distributively across several workers with particular focus on security against Byzantine workers. We note that any Boolean function can be modeled as a multivariate polynomial which can have high degree in general. Hence, the recently proposed Lagrange Coded Computing (LCC) can be used to simultaneously provide resiliency, security, and privacy. However, the security threshold (i.e., the maximum number of adversarial workers that can be tolerated) provided by LCC can be extremely low if the degree of the polynomial is high. Our goal is to design an efficient coding scheme which achieves the optimal security threshold. We propose two novel schemes called coded Algebraic normal form (ANF) and coded Disjunctive normal form (DNF). Instead of modeling the Boolean function as a general polynomial, the key idea of the proposed schemes is to model it as the concatenation of some linear functions and threshold functions. The proposed coded ANF and coded DNF outperform LCC by providing the security threshold which is independent of the polynomial's degree.

Software-Defined Networks (SDN) are being adopted widely and are also likely to be deployed as the infrastructure of systems with critical real-time properties such as Industrial Control Systems (ICS). This raises the question of what security and performance guarantees can be given for the data plane of such critical systems and whether any control plane actions will adversely affect these guarantees, particularly for quality of service in real-time systems. In this paper we study the existing literature on the analysis of SDN using queueing networks and show ways in which models need to be extended to study attacks that are based on arrival rates and service time distributions of flows in SDN.

As large-scale linear equation systems are pervasive in many scientific fields, great efforts have been done over the last decade in realizing efficient techniques to solve such systems, possibly relying on High Performance Computing (HPC) infrastructures to boost the performance. In this framework, the ever-growing scale of supercomputers inevitably increases the frequency of faults, making it a crucial issue of HPC application development.A previous study [1] investigated the possibility to enhance the Inhibition Method (IMe) -a linear systems solver for dense unstructured matrices-with fault tolerance to single hard errors, i.e. failures causing one computing processor to stop.This article extends [1] by proposing an efficient technique to obtain fault tolerance to multiple hard errors, which may occur concurrently on different processors belonging to the same or different machines. An improved parallel implementation is also proposed, which is particularly suitable for HPC environments and moves towards the direction of a complete decentralization. The theoretical analysis suggests that the technique (which does not require check pointing, nor rollback) is able to provide fault tolerance to multiple faults at the price of a small overhead and a limited number of additional processors to store the checksums. Experimental results on a HPC architecture validate the theoretical study, showing promising performance improvements w.r.t. a popular fault-tolerant solving technique.

Traditionally, vulnerability is the level of degradation caused by failures or disturbances, and resilience is the ability to recover after a high-impact event. This paper presents a topological procedure based on graph theory to evaluate the vulnerability and resilience of power grids. A cascading failures model is developed by eliminating lines both deliberately and randomly, and four restoration strategies inspired by the network approach are proposed. In the two cases, the degradation and recovery of the electrical infrastructure are quantified through four centrality measures. Here, an index called flow-capacity is proposed to measure the level of network overload during the iterative processes. The developed sequential framework was tested on a graph of 600 nodes and 1196 edges built from the 400 kV high-voltage power system in Spain. The conclusions obtained show that the statistical graph indices measure different topological aspects of the network, so it is essential to combine the results to obtain a broader view of the structural behaviour of the infrastructure.

We propose a new approach to creating a subject-oriented distributed computing environment. Such an environment is used to support decision-making in solving relevant problems of ensuring energy systems resilience. The proposed approach is based on the idea of advancing and integrating the following important capabilities in supercomputer engineering: continuous integration, delivery, and deployment of the system and applied software, high-performance computing in heterogeneous environments, multi-agent intelligent computation planning and resource allocation, big data processing and geo-information servicing for subject information, including weakly structured data, and decision-making support. This combination of capabilities and their advancing are unique to the subject domain under consideration, which is related to combinatorial studying critical objects of energy systems. Evaluation of decision-making alternatives is carrying out through applying combinatorial modeling and multi-criteria selection rules. The Orlando Tools framework is used as the basis for an integrated software environment. It implements a flexible modular approach to the development of scientific applications (distributed applied software packages).

We focus on resilience towards covert attacks on Cyber-Physical Systems (CPS). We define the new k-steerability and l-monitorability control-theoretic concepts. k-steerability reflects the ability to act on every individual plant state variable with at least k different groups of functionally diverse input signals. l-monitorability indicates the ability to monitor every individual plant state variable with £ different groups of functionally diverse output signals. A CPS with k-steerability and l-monitorability is said to be (k, l)-resilient. k and l, when both greater than one, provide the capability to mitigate the impact of covert attacks when some signals, but not all, are compromised. We analyze the influence of k and l on the resilience of a system and the ability to recover its state when attacks are perpetrated. We argue that the values of k and l can be augmented by combining redundancy and diversity in hardware and software techniques that apply the moving target paradigm.

Developing mission-centric impact assessment techniques to address cyber resiliency in the cyber-physical systems (CPSs) requires integrating system inter-dependencies to the risk and resilience analysis process. Generally, network administrators utilize attack graphs to estimate possible consequences in a networked environment. Attack graphs lack to incorporate the operations-specific dependencies. Localizing the dependencies among operational missions, tasks, and the hosting devices in a large-scale CPS is also challenging. In this work, we offer a graphical modeling technique to integrate the mission-centric impact assessment of cyberattacks by relating the effect to the operational resiliency by utilizing a combination of the logical attack graph and mission impact propagation graph. We propose formal techniques to compute cyberattacks’ impact on the operational mission and offer an optimization process to minimize the same, having budgetary restrictions. We also relate the effect to the system functional operability. We illustrate our modeling techniques using a SCADA (supervisory control and data acquisition) case study for the cyber-physical power systems. We believe our proposed method would help evaluate and minimize the impact of cyber attacks on CPS’s operational missions and, thus, enhance cyber resiliency.

In this talk, we discuss how control theory can contribute to the analysis and design of secure cyber-physical systems. We start by reviewing conditions for undetectable false-data injection attacks on feedback control systems. In particular, we highlight how a physical understanding of the controlled process can guide us in the allocation of protective measures. We show that protecting only a few carefully selected actuators or sensors can give indirect protection to many more components. We then illustrate how such analysis is exploited in the design of a resilient control scheme for a microgrid energy management system.

This paper proposes a simple topological characterization of a large class of fair adversarial models via affine tasks: sub-complexes of the second iteration of the standard chromatic subdivision. We show that the task computability of a model in the class is precisely captured by iterations of the corresponding affine task. Fair adversaries include, but are not restricted to, the models of wait-freedom, t-resilience, and k-concurrency. Our results generalize and improve all previously derived topological characterizations of the ability of a model to solve distributed tasks.

We study a game theoretic model where a coalition of processors might collude to bias the outcome of the protocol, where we assume that the processors always prefer any legitimate outcome over a non-legitimate one. We show that the problems of Fair Leader Election and Fair Coin Toss are equivalent, and focus on Fair Leader Election. Our main focus is on a directed asynchronous ring of n processors, where we investigate the protocol proposed by Abraham et al. [4] and studied in Afek et al. [5]. We show that in general the protocol is resilient only to sub-linear size coalitions. Specifically, we show that Ω( p n logn) randomly located processors or Ω( 3 √ n) adversarially located processors can force any outcome. We complement this by showing that the protocol is resilient to any adversarial coalition of size O( 4 √ n). We propose a modification to the protocol, and show that it is resilient to every coalition of size ?( √ n), by exhibiting both an attack and a resilience result. For every k ≥ 1, we define a family of graphs Gk that can be simulated by trees where each node in the tree simulates at most k processors. We show that for every graph in Gk , there is no fair leader election protocol that is resilient to coalitions of size k. Our result generalizes a previous result of Abraham et al. [4] that states that for every graph, there is no fair leader election protocol which is resilient to coalitions of size ?n/2 ?.

The problem of Byzantine Agreement (BA) is of interest to both distributed computing and cryptography community. Following well-known results from the distributed computing literature, BA problem in the asynchronous network setting encounters inevitable non-termination issues. The impasse is overcome via randomization that allows construction of BA protocols in two flavours of termination guarantee - with overwhelming probability and with probability one. The latter type termed as almost-surely terminating BAs are the focus of this paper. An eluding problem in the domain of almost-surely terminating BAs is achieving a constant expected running time. Our work makes progress in this direction. In a setting with n parties and an adversary with unbounded computing power controlling at most t parties in Byzantine fashion, we present two asynchronous almost-surely terminating BA protocols: With the optimal resilience of t \textbackslashtextless n3 , our first protocol runs for expected O(n) time. The existing protocols in the same setting either runs for expected O(n2) time (Abraham et al, PODC 2008) or requires exponential computing power from the honest parties (Wang, CoRR 2015). In terms of communication complexity, our construction outperforms all the known constructions that offer almost-surely terminating feature. With the resilience of t \textbackslashtextless n/3+ε for any ε \textbackslashtextgreater 0, our second protocol runs for expected O( 1 ε ) time. The expected running time of our protocol turns constant when ε is a constant fraction. The known constructions with constant expected running time either require ε to be at least 1 (Feldman-Micali, STOC 1988), implying t \textbackslashtextless n/4, or calls for exponential computing power from the honest parties (Wang, CoRR 2015). We follow the traditional route of building BA via common coin protocol that in turn reduces to asynchronous verifiable secretsharing (AVSS). Our constructions are built on a variant of AVSS that is termed as shunning. A shunning AVSS fails to offer the properties of AVSS when the corrupt parties strike, but allows the honest parties to locally detect and shun a set of corrupt parties for any future communication. Our shunning AVSS with t \textbackslashtextless n/3 and t \textbackslashtextless n 3+ε guarantee Ω(n) and respectively Ω(εt 2) conflicts to be revealed when failure occurs. Turning this shunning AVSS to a common coin protocol constitutes another contribution of our paper.

The success and growing popularity of blockchain technology has lead to a significant increase in load on popular permissionless blockchains such as Ethereum. With the current design, these blockchain systems do not scale with additional nodes since every node executes every transaction. Further efforts are therefore necessary to develop scalable permissionless blockchain systems. In this paper, we provide an aggregated overview of the current research on the Ethereum blockchain towards solving the scalability challenge. We focus on the concept of sharding, which aims to break the restriction of every participant being required to execute every transaction and store the entire state. This concept however introduces new complexities in the form of stateless clients, which leads to a new challenge: how to guarantee that critical data is published and stays available for as long as it is relevant. We present an approach towards solving the data availability problem (DAP) that leverages synergy effects by reusing the validators from Casper. We then propose two distinct approaches for reliable collation proposal, state transition, and state verification in shard chains. One approach is based on verification by committees of Casper validators that execute transactions in proposed blocks using witness data provided by executors. The other approach relies on a proof of execution provided by the executor proposing the block and a challenge game, where other executors verify the proof. Both concepts rely on executors for long-term storage of shard chain state.

The interaction design community increasingly addresses how digital technologies may contribute to societal transformations. This paper aims at understanding transformation ignited by a particular constructive design research project. This transformation will be discussed and analysed using resilience thinking, an established approach within sustainability science. By creating a common language between these two disciplines, we start to identify what kind of transformation took place, what factors played a role in the transformation, and which transformative qualities played a role in creating these factors. Our intention is to set out how the notion of resilience might provide a new perspective to understand how constructive design research may produce results that have a sustainable social impact. The findings point towards ways in which these two different perspectives on transformation the analytical perspective of resilience thinking and the generative perspective of constructive design research - may become complementary in both igniting and understanding transformations.

Byte addressable persistent memory eliminates the need for serialization and deserialization of data, to and from persistent storage, allowing applications to interact with it through common store and load instructions. In the event of a process or system failure, applications rely on persistent techniques to provide consistent storage of data in non-volatile memory (NVM). For most of these techniques, consistency is ensured through logging of updates, with consequent intensive cache line flushing and persistent fences necessary to guarantee correctness. Undo log based approaches require store interposition and persistence fences before each in-place modification. Redo log based techniques can execute transactions using just two persistence fences, although they require store and load interposition which may incur a performance penalty for large transactions. So far, these techniques have been difficult to integrate with known memory allocators, requiring allocators or garbage collectors specifically designed for NVM. We present Romulus, a user-level library persistent transactional memory (PTM) which provides durable transactions through the usage of twin copies of the data. A transaction in Romulus requires at most four persistence fences, regardless of the transaction size. Romulus uses only store interposition. Any sequential implementation of a memory allocator can be adapted to work with Romulus. Thanks to its lightweight design and low synchronization overhead, Romulus achieves twice the throughput of current state of the art PTMs in update-only workloads, and more than one order of magnitude in read-mostly scenarios.

Leakage resilience (LR) and misuse resistance (MR) are two important properties for the deployment of authenticated encryption (AE) schemes. They aim at mitigating the impact of implementation flaws due to side-channel leakages and misused randomness. In this paper, we discuss the interactions and incompatibilities between these two properties. We start from the usual definition of MR for AE schemes from Rogaway and Shrimpton, and argue that it may be overly demanding in the presence of leakages. As a result, we turn back to the basic security requirements for AE: ciphertext integrity (INT-CTXT) and CPA security, and propose to focus on a new notion of CIML security, which is an extension of INT-CTXT in the presence of misuse and leakages. We discuss the extent to which CIML security is offered by previous proposals of MR AE schemes, conclude by the negative, and propose two new efficient CIML-secure AE schemes: the DTE scheme offers security in the standard model, while the DCE scheme offers security in the random oracle model, but comes with some efficiency benefits. On our way, we observe that these constructions are not trivial, and show for instance that the composition of a LR MAC and a LR encryption scheme, while providing a (traditional) MR AE scheme, can surprisingly lose the MR property in the presence of leakages and does not achieve CIML security. Eventually, we show the LR CPA security of DTE and DCE.

Using Software-defined Networks in wide area (SDN-WAN) has been strongly emerging in the past years. Due to scalability and economical reasons, SDN-WAN mostly uses an in-band control mechanism, which implies that control and data sharing the same critical physical links. However, the in-band control and centralized control architecture can be exploited by attackers to launch distributed denial of service (DDoS) on SDN control plane by flooding the shared links and/or the Open flow agents. Therefore, constructing a resilient software designed network requires dynamic isolation and distribution of the control flow to minimize damage and significantly increase attack cost. Existing solutions fall short to address this challenge because they require expensive extra dedicated resources or changes in OpenFlow protocol. In this paper, we propose a moving target technique called REsilient COntrol Network architecture (ReCON) that uses the same SDN network resources to defend SDN control plane dynamically against the DDoS attacks. ReCON essentially, (1) minimizes the sharing of critical resources among data and control traffic, and (2) elastically increases the limited capacity of the software control agents on-demand by dynamically using the under-utilized resources from within the same SDN network. To implement a practical solution, we formalize ReCON as a constraints satisfaction problem using Satisfiability Modulo Theory (SMT) to guarantee a correct-by-construction control plan placement that can handle dynamic network conditions.

Android applications are usually obfuscated before release, making it difficult to analyze them for malware presence or intellectual property violations. Obfuscators might hide the true intent of code by renaming variables and/or modifying program structures. It is challenging to search for executables relevant to an obfuscated application for developers to analyze efficiently. Prior approaches toward obfuscation resilient search have relied on certain structural parts of apps remaining as landmarks, un-touched by obfuscation. For instance, some prior approaches have assumed that the structural relationships between identifiers are not broken by obfuscators; others have assumed that control flow graphs maintain their structures. Both approaches can be easily defeated by a motivated obfuscator. We present a new approach, MACNETO, to search for programs relevant to obfuscated executables leveraging deep learning and principal components on instructions. MACNETO makes few assumptions about the kinds of modifications that an obfuscator might perform. We show that it has high search precision for executables obfuscated by a state-of-the-art obfuscator that changes control flow. Further, we also demonstrate the potential of MACNETO to help developers understand executables, where MACNETO infers keywords (which are from relevant un-obfuscated programs) for obfuscated executables.

We study coding schemes for multiparty interactive communication over synchronous networks that suffer from stochastic noise, where each bit is independently flipped with probability ε. We analyze the minimal overhead that must be added by the coding scheme in order to succeed in performing the computation despite the noise. Our main result is a lower bound on the communication of any noise-resilient protocol over a synchronous star network with n-parties (where all parties communicate in every round). Specifically, we show a task that can be solved by communicating T bits over the noise-free network, but for which any protocol with success probability of 1-o(1) must communicate at least Ω(T log n / log log n) bits when the channels are noisy. By a 1994 result of Rajagopalan and Schulman, the slowdown we prove is the highest one can obtain on any topology, up to a log log n factor. We complete our lower bound with a matching coding scheme that achieves the same overhead; thus, the capacity of (synchronous) star networks is Θ(log log n / log n). Our bounds prove that, despite several previous coding schemes with rate Ω(1) for certain topologies, no coding scheme with constant rate Ω(1) exists for arbitrary n-party noisy networks.

Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography. These are seeded non-malleable extractors, introduced by Dodis and Wichs; seedless non-malleable extractors, introduced by Cheraghchi and Guruswami; and non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs. Besides being interesting on their own, they also have important applications in cryptography, e.g, privacy amplification with an active adversary, explicit non-malleable codes etc, and often have unexpected connections to their non-tampered analogues. However, the known constructions are far behind their non-tampered counterparts. Indeed, the best known seeded non-malleable extractor requires min-entropy rate at least 0.49; while explicit constructions of non-malleable two-source extractors were not known even if both sources have full min-entropy, and was left as an open problem by Cheraghchi and Guruswami. In this paper we make progress towards solving the above problems and other related generalizations. Our contributions are as follows. (1) We construct an explicit seeded non-malleable extractor for polylogarithmic min-entropy. This dramatically improves all previous results and gives a simpler 2-round privacy amplification protocol with optimal entropy loss, matching the best known result. In fact, we construct more general seeded non-malleable extractors (that can handle multiple adversaries) which were used in the recent construction of explicit two-source extractors for polylogarithmic min-entropy. (2) We construct the first explicit non-malleable two-source extractor for almost full min-entropy thus resolving the open question posed by Cheraghchi and Guruswami. (3) We motivate and initiate the study of two natural generalizations of seedless non-malleable extractors and non-malleable codes, where the sources or the codeword may be tampered many times. By using the connection found by Cheraghchi and Guruswami and providing efficient sampling algorithms, we obtain the first explicit non-malleable codes with tampering degree t, with near optimal rate and error. We call these stronger notions one-many and many-manynon-malleable codes. This provides a stronger information theoretic analogue of a primitive known as continuous non-malleable codes. Our basic technique used in all of our constructions can be seen as inspired, in part, by the techniques previously used to construct cryptographic non-malleable commitments.

Suppose that you have n truly random bits x=(x1,…,xn) and you wish to use them to generate m≫ n pseudorandom bits y=(y1,…, ym) using a local mapping, i.e., each yi should depend on at most d=O(1) bits of x. In the polynomial regime of m=ns, stextgreater1, the only known solution, originates from (Goldreich, ECCC 2000), is based on Random Local Functions: Compute yi by applying some fixed (public) d-ary predicate P to a random (public) tuple of distinct inputs (xi1,…,xid). Our goal in this paper is to understand, for any value of s, how the pseudorandomness of the resulting sequence depends on the choice of the underlying predicate. We derive the following results: (1) We show that pseudorandomness against F2-linear adversaries (i.e., the distribution y has low-bias) is achieved if the predicate is (a) k=Ω(s)-resilience, i.e., uncorrelated with any k-subset of its inputs, and (b) has algebraic degree of Ω(s) even after fixing Ω(s) of its inputs. We also show that these requirements are necessary, and so they form a tight characterization (up to constants) of security against linear attacks. Our positive result shows that a d-local low-bias generator can have output length of nΩ(d), answering an open question of Mossel, Shpilka and Trevisan (FOCS, 2003). Our negative result shows that a candidate for pseudorandom generator proposed by the first author (computational complexity, 2015) and by O’Donnell and Witmer (CCC 2014) is insecure. We use similar techniques to refute a conjecture of Feldman, Perkins and Vempala (STOC 2015) regarding the hardness of planted constraint satisfaction problems. (2) Motivated by the cryptanalysis literature, we consider security against algebraic attacks. We provide the first theoretical treatment of such attacks by formalizing a general notion of algebraic inversion and distinguishing attacks based on the Polynomial Calculus proof system. We show that algebraic attacks succeed if and only if there exist a degree e=O(s) non-zero polynomial Q whose roots cover the roots of P or cover the roots of P’s complement. As a corollary, we obtain the first example of a predicate P for which the generated sequence y passes all linear tests but fails to pass some polynomial-time computable test, answering an open question posed by the first author (Question 4.9, computational complexity 2015).

We present a task-based domain-decomposition preconditioner for partial differential equations (PDEs) resilient to silent data corruption (SDC) and hard faults. The algorithm exploits a reformulation of the PDE as a sampling problem, followed by a regression-based solution update that is resilient to SDC. We adopt a server-client model implemented using the User Level Fault Mitigation MPI (MPI-ULFM). All state information is held by the servers, while clients only serve as computational units. The task-based nature of the algorithm and the capabilities of ULFM are complemented at the algorithm level to support missing tasks, making the application resilient to hard faults affecting the clients. Weak and strong scaling tests up to \textasciitilde115k cores show an excellent performance of the application with efficiencies above 90%, demonstrating the suitability to run at large scale. We demonstrate the resilience of the application for a 2D elliptic PDE by injecting SDC using a random single bit-flip model, and hard faults in the form of clients crashing. We show that in all cases, the application converges to the right solution. We analyze the overhead caused by the faults, and show that, for the test problem considered, the overhead incurred due to SDC is minimal compared to that from the hard faults.