International audience

In distributed systems and in particular in industrial SCADA environments, alert correlation systems are necessary to identify complex multi-step attacks within the huge amount of alerts and events. In this paper we describe an automata-based correlation engine developed in the context of a European project where the main stakeholder was an energy distribution company. The behavior of the engine is extended to fit new requirements. In the proposed solution, a fully automated process generates thousands of correlation rules. Despite this major scalability challenge, the designed correlation engine exhibits good performances. Expected rates of incoming low level alerts approaching several hundreds of elements per second are tolerated. Moreover, the used data structures allow to quickly handle dynamic changes of the set of correlation rules. As some attack steps are not observed, the correlation engine can be tuned to raise an alert when all the attack steps except k of them have been detected. To be able to react to an ongoing attack by taking countermeasures, alerts must also be raised as soon as a significant prefix of an attack scenario is recognized. Fulfilling these additional requirements leads to increase the memory consumption. Therefore purge mechanisms are also proposed and analyzed. An evaluation of the tool is conducted in the context of a SCADA environment.

We consider the approximate consensus problem in a partially connected network of n nodes where at most f nodes may suffer from Byzantine faults. We study under which conditions this problem can be solved using an iterative algorithm. A Byzantine node can equivocate: it may provide different values to its neighbors. To restrict the possibilities of equivocation, the 3-partial multicast primitive is considered. When a (correct or faulty) node uses this communication primitive, it provides necessarily the same value to the two identified receivers. Based on this communication primitive, a novel condition called f-resilient is proposed and proved to be necessary and sufficient to solve the approximate Byzantine consensus problem in a synchronous network. This condition takes into account two different communication primitives: unicast and 3-partial multicast. It expresses a trade-off between the two known approaches that make the problem solvable (increasing the number of neighbors or/and increasing the power of the communication primitives). The condition f-resilient does not require to eliminate all the possibilities of equivocation. Furthermore, it can be satisfied when there is just a majority of correct nodes. The relationships between the condition f-resilient and the condition h-disjoint (proposed by Alexander Jaffe et al. in 2012 to solve another problem, namely exact Byzantine consensus) are investigated. Two preliminary conclusions are obtained. When a network does not satisfy h-disjoint, it also does not satisfy f-resilient. But when a network satisfies h-disjoint, f-resilient is not necessarily satisfied. Finally, the condition is extended to cope with asynchronous networks.

In large distributed information systems, alert correlation systems are necessary to handle the huge amount of elementary security alerts and to identify complex multi-step attacks within the flow of low level events and alerts. In this paper, we show that, once a human expert has provided an action tree derived from an attack tree, a fully automated transformation process can generate exhaustive correlation rules that would be tedious and error prone to enumerate by hand. The transformation relies on a detailed description of various aspects of the real execution environment (topology of the system, deployed services, etc.). Consequently, the generated correlation rules are tightly linked to the characteristics of the monitored information system. The proposed transformation process has been implemented in a prototype that generates correlation rules expressed in an attack description language.

We consider the clock synchronization problem in wireless mobile ad hoc networks in the presence of Byzantine nodes. The communication topology is dynamic: nodes move randomly within a geographical area. We propose a clock synchronization protocol which is based on the linear approximate consensus method. Periodically each correct node broadcasts its current timestamp and gathers the timestamps provided by its current neighbors. To cope with the malicious nodes (and to improve the performance when the node density is low), each node keeps the collected timestamps in a local log. As a log may contain values received more or less recently, a transformation technique is introduced to refresh the outdated values. The accuracy of the synchronisation depends on the connectivity among the moving nodes. We use a matrix and vector based representation to model the behavior of the synchronization process and to analyze its accuracy. We show that the deviation between the different clock values can converge towards zero when a particular condition is satisfied infinitely often. The frequency at which the condition is satisfied also impacts the synchronization accuracy. Based on a particular mobility scenario, performance simulations are conducted.

We present a protocol designed to solve several consecutive consensus instances in an asynchronous distributed system prone to crash failures and message omissions. The protocol follows the Paxos approach and integrates two different optimizations to reduce the latency of learning a decision value. This protocol is adaptive as it tries to obtain the best performance gain depending on the current context. Moreover, it guarantees the persistence of all decision values. Our experimentation results focus on the impact of collisions.

Mobile devices are now equipped with multiple sensors and networking capabilities. They can gather information about their surrounding environment and interact both with nearby nodes, using a dynamic and self-configurable ad-hoc network, and with distant nodes via the Internet. While the concept of mobile agent is appropriate to explore the ad-hoc network and autonomously discover service providers, it is not suitable for the implementation of strong distributed synchronization mechanisms. Moreover, the termination of a task assigned to an agent may be compromised if the persistence of the agent itself is not ensured. In the case of a transactional mobile agent, we identify two services, Availability of the Source and Atomic Commit, that have to be supplied by more powerful entities located outside the ad-hoc network, in a remote network, called the support network. We propose a solution where the two services are successively provided by an active entity called the leader. In the support network, crash failures may also occur. To guarantee reliability, the main actions performed by the leader are the subject of a consensus with all the other potential leaders. The proposed solution relies on a single agreement protocol that orders continuously all the new actions.

Consensus services have been recognized as fundamental building blocks for fault-tolerant distributed systems. Many different protocols to implement such a service have been proposed, however, not a lot of effort has been placed in evaluating their performance. In particular, in the context of round-based consensus protocols for asynchronous systems augmented with failure detectors, there has been some work on evaluating how the QoS of the failure detector impacts the performance of the protocols, as well as on the trade-off between having faster decentralized decision at the expenses of generating more network load. These studies, however, focus on protocols that have no mechanism to deal with an eventual bad QoS provided by the failure detector, and have a decision pattern that is either completely centralized - only one process being able to autonomously decide - or completely decentralized - all processes being able to autonomously decide. This paper reports a thorough evaluation of the performance of a consensus protocol that has two unique features. Firstly, it mitigates the problems due to bad QoS delivered by the failure detector by allowing processes to simultaneously participate in multiple rounds. Secondly, it allows its decision pattern to be configured to have different numbers of processors allowed to autonomously decide. We have measured the decision latency of the protocol to conduct the performance analysis. The results, obtained by means of simulation, highlight the advantages and limitations of the two mechanisms and allow one to understand in a comprehensive framework how the protocol's parameters should be set, such that the best performance is achieved depending on the application's requirements.

This paper addresses the problem of trajectory tracking that deals with gathering coherent information on the past behavior of a mobile target. When a target enters and moves within a region covered by a sensor network, information about this target is generated by any active sensor that detects the target in its monitoring area. These gathered data have to be received by some registered nodes that are in charged of identifying the trajectory of the target to perform latter complex computations at the application level (e.g., trajectory forecasting, pursuer/evader, optimization of the management of natural disasters, etc,), Our first contribution consists informally specifying the problem: the proposed formal specification is the first one to the best of our knowledge. We also propose an original architecture combining three distinct abstractions which allows describing various solutions. Some algorithmic solutions that is necessary far the self-stabilizing-implementation of the trajectory tracking specification is outlined. The overall solution blends together in the context of tracking applications, three research areas: temporal correlated data, causal correlated (content related) data, and self-stabilizing overlays

This paper presents the design of OPEN EDEN, an imple-mentation of the Fault Tolerant CORBA specification based on the use of a group communication system, called EDEN. The design of OPEN EDEN has been driven by the desire to use only portable techniques (mainly portable intercep-tors) to implement the interaction between the EDEN group communication system and CORBA. The EDEN system it-self is built by configuring, assembling and deploying com-ponents connected to a generic agreement component that implements a consensus algorithm. The resulted platform is particularly portable, since it can be easily migrated to d-ifferent architectures, and transparent for applications pro-grammers, since requests to a replicated service are trans-parently intercepted and redirected to the EDEN system. We discuss the main difficulties we encountered and we draw some conclusions about the adequacy of our choices.

This paper is on consensus protocols for asynchronous distributed systems prone to process crashes, but equipped with Chandra-Toueg's (1996) unreliable failure detectors. It presents a unifying approach based on two orthogonal versatility dimensions. The first concerns the class of the underlying failure detector. An instantiation can consider any failure detector of the class S (provided that at least one process does not crash), or oS (provided that a majority of processes do not crash). The second versatility dimension concerns the message exchange pattern used during each round of the protocol. This pattern (and, consequently, the round message cost) can be defined for each round separately, varying from O(n) (centralized pattern) to O(n/sup 2/) (fully distributed pattern), n being the number of processes. The resulting versatile protocol has nice features and actually gives rise to a large and well-identified family of failure detector-based consensus protocols. Interestingly, this family includes at once new protocols and some well-known protocols (e.g., Chandra-Toueg's oS-based protocol). The approach is also interesting from a methodological point of view. It provides a precise characterization of the two sets of processes that, during a round, have to receive messages for a decision to be taken (liveness) and for a single value to be decided (safety), respectively. Interestingly, the versatility of the protocol is not restricted to failure detectors: a simple timer-based instance provides a consensus protocol suited to partially synchronous systems.

Considers the priority inversion problem in an actively replicated system. Priority inversion was originally defined in the context of nonreplicated systems. Therefore, we first introduce the concept of group priority inversion, which extends the concept of (local) priority inversion to the context of a group of processors that perform an actively replicated processing. We then present the properties of a request scheduling protocol to enforce a total ordering for the processing of requests while avoiding group priority inversions. These properties have been implemented in a protocol that relies on a timed asynchronous system model equipped with a failure detector of the class /spl diams/S. The proposed solution allows us to replicate a critical server while ensuring that the processing of all the incoming requests is consistent (mechanisms for solving the atomic broadcast problem) and predictable (mechanisms for solving the group priority inversion problem). Thus, the described request scheduling protocol is a key component which can be used to develop fault-tolerant real-time applications in a timed asynchronous system.

We consider the priority inversion problem in an actively replicated system. Priority inversion was originally defined in the context of non-replicated systems. Therefore we first introduce the concept of group priority inversion, which extends the concept of (local) priority inversion to the context of a group of processors that perform an actively replicated processing. We then present the properties of a request scheduling protocol to enforce a total ordering for the processing of requests while avoiding group priority inversions. These properties have been implemented in a protocol that relies on a timed asynchronous system model equipped with a failure detector of the class /spl square/S. The proposed solution allows one to replicate a critical server while ensuring that the processing of all the incoming requests is consistent (mechanisms for solving the atomic broadcast problem) and predictable (mechanisms for solving the group priority inversion problem). Thus, the described request scheduling protocol is a key component which can be used to develop fault tolerant real time applications in a timed asynchronous system.

Group-based computing is becoming more and more popular when one has to design middleware able to support reliable distributed applications. This paradigm is made of two basic services, namely, a group membership service and a group communication service. More generally, a group is a set of processes cooperating to carry out a common task (e.g., copies of a replicated server, participants in a transaction or users in a CSCW-based application). Due to the desire of new processes to join the group, to the desire of a group member to leave it, or to process crashes, the composition of a group can evolve dynamically. The set of processes that currently implements the group is called the current view of the group. This paper addresses the specification and the implementation of a primary component group membership service. Primary component means that the specification imposes to have a single view at any time. The paper first proposes a specification for the problem. Then it presents a protocol that implements that specification in asynchronous distributed systems equipped with failure detectors. This primary component group membership protocol is obtained as an appropriate instantiation of a general agreement framework.

Presents a framework for the development of higher level communication protocols that provides extra functionalities not supplied by standard off-the-shelf lower level communication protocols. The framework is based on the event channel abstraction which allows circumventing the main drawbacks of the layered-based approach traditionally used to develop such protocols, whilst at the same time providing a flexible, simple and well structured way to implement them. The event channel service provided by EVA establishes how entities that share the same address space interact. Then, the application designer has the opportunity to define the most appropriate lower level communication protocols that control the way entities that execute within different processes will interact. The framework specifies a way to accommodate these protocols and provides several standard protocol implementations. Further a development methodology is described for constructing applications on top of the framework. In designing the framework, we have followed the approach of using, whenever possible, well established concepts, thus the paper also discusses the utilisation of such concepts in improving both the efficiency and the structuring of the framework and of the applications to be built on top of it.

The paper revisits the "sliding window" notion commonly encountered in communication protocols and applies it to the round numbers of round-based asynchronous protocols. This approach is novel. To illustrate its benefits, the paper presents an original weak failure detector-based consensus protocol that allows each process to be simultaneously involved in several rounds. The rounds in which a process is simultaneously involved defines "sliding round window". The proposed approach has several advantages. It fits better to the uncertainty created by the asynchrony and failures, and consequently permits one to design efficient round-based asynchronous protocols. Maybe more important, it also provides a better understanding of the global synchronization that manages the protocol progress from round to round. This appears clearly in the proposed failure detector-based consensus protocol, where the "sliding round window" allows one to dynamically define the message exchange pattern for each round separately.

Global data is a vector with one entry per process. Each entry must be filled with an appropriate value provided by the corresponding process. Several distributed computing problems amount to compute a function on global data. This paper proposes a protocol to solve such problems in the context of asynchronous distributed systems where processes may fail by crashing. The main problem that has to be solved lies in computing the global data and in providing each non-crashed process with a copy of it, despite the possible crash of some processes. To be consistent, the global data must contain (at least) all the values provided by the processes that do not crash. This defines the global data computation (GDC) problem. To solve this problem, processes execute a sequence of asynchronous rounds during which they construct (in a decentralized way) the value of the global data, and eventually each process gets a copy of it. To cope with process crashes, the protocol uses a perfect failure detector. The proposed protocol has been designed to be time-efficient. It allows early decisions. Let t be the maximum number of processes that may crash (t

The class of strong failure detectors (denoted S) includes all failure detectors that suspect all crashed processes and that do not suspect some (a priori unknown) process that never crashes. So, a failure detector that belongs to S is intrinsically unreliable as it can arbitrarily suspect correct processes.

A Global Data is a vector with one entry per process. Each entry must be filled with an appropriate value provided by the corresponding process. Several distributed computing problems amount to compute a function on a global data. This paper proposes a protocol to solve such problems in the context of asynchronous distributed systems where processes may fail by crashing. The main problem that has to be solved lies in computing the global data and in providing each noncrashed process with a copy of it, despite the possible crash of some processes. To be consistent, the global data must contain, at least, all the values provided by the processes that do not crash. This defines the Global Data Computation (GDC) problem. To solve this problem, processes execute a sequence of asynchronous rounds during which they construct, in a decentralized way, the value of the global data and eventually each process gets a copy of it. To cope with process crashes, the protocol uses a perfect failure detector. The proposed protocol has been designed to be time efficient: it allows early decision. Let t be the maximum number of processes that may crash, t

Atomic broadcast or non-blocking atomic commitment are classic agreement problems encountered when designing fault-tolerant distributed systems. Specific protocols that solve such agreement problems can be designed based on a common building block, namely the consensus service. Unfortunately, the consensus problem has no deterministic solution in an asynchronous distributed system that is subject to even a single process crash failure. Among the solutions proposed to circumvent this impossibility result, the concept of unreliable failure detectors proposed by Chandra and Toueg is particularly attractive. They have defined a protocol that solves the consensus problem when the assumption that the underlying failure detector belongs to the class /spl square/S holds true. This paper presents an extension of their protocol that allows to solve this fundamental problem in a mobile environment. In such an environment, the problem is more challenging: based on their initial states, a set of mobile hosts must agree on a common decision, despite disconnections, changes of location and failures of mobile/fixed hosts.

Agreement problems are among the most important problems designers of distributed systems have to cope with. A way to solve them is to first provide a solution to the Consensus problem and then to reduce each agreement problem to Consensus. This "run-time customizing" approach is particularly relevant when upper layer applications have to solve several distinct agreement problems. We investigate a "compile-time customizing" approach to automatically generate ad hoc agreement protocols. A general agreement framework, characterized by six "versatility" parameters, is defined. Appropriate instantiations of these parameters provide particular agreement protocols. This approach is particularly suited to generate efficient agreement protocols.

This paper investigates the use of asynchronous protocols to design and build middleware whose aim is to provide run-time support for soft real-time applications. A simple and general framework is described. This framework allows to take into account timeliness constraints of upper layer applications, while using an asynchronous protocol at the underlying level. When a timeliness constraint is about to be violated, the application layer is informed and can take appropriate measures. The deadline period can then be extended if the constraint is soft enough; in the other case, a default value can be used as a result. This framework can be seen as a bridge from asynchronous systems to synchronous ones. The proposed approach is illustrated with the consensus problem. This approach is investigated in the ARGO system we are implementing. The target applications of the ARGO middleware are telecommunication applications.

The consensus problem is now well identified as being one of the most important problems encountered in the design and the construction of fault-tolerant distributed systems. This problem is defined as follows: processes have to reach a common decision, which depends on their inputs, despite failures. We consider the consensus problem in asynchronous distributed systems augmented with unreliable failure detectors. Several protocols have been proposed for these systems, when process crashes are assumed to be definitive. This paper addresses the consensus problem in a more practical asynchronous system model, namely in a context where processes can crash and recover. As a process crash entails the loss of its volatile memory, each process is equipped with a stable storage. So, to be efficient a consensus protocol has to log as few critical data as possible. The proposed protocol uses a new class of failure detectors suited to the crash/recovery model. It is particularly efficient when, whether there are crashes or not, the underlying failure detector makes few mistakes. Additionally, the proposed protocol tolerates message duplication and copes with some message losses.

Global predicate detection is a fundamental problem in distributed systems and finds applications in many domains such as testing and debugging distributed programs. This paper presents an efficient distributed algorithm to detect conjunctive-form global predicates in distributed systems. The algorithm detects the first consistent global state that satisfies the predicate even if the predicate is unstable. Unlike previously proposed run-time predicate detection algorithms, our algorithm does not require the exchange of control messages during the normal computation. All the necessary information to detect predicates is piggybacked on computation messages of application programs. The algorithm is distributed because the predicate detection efforts as well as the necessary information are equally distributed among the processes. We prove the correctness of the algorithm and compare its performance with respect to message, storage and computational complexities with that of the previously proposed run-time predicate detection algorithms.