The rapid adoption of cloud computing has intensified concerns over data privacy, particularly in the context of outsourced datasets. Attribute-Based Keyword Search (ABKS) has emerged as a promising cryptographic solution for enabling secure and efficient search over encrypted data. However, most existing ABKS schemes typically assume that all clients behave honestly, which weakens their applicability in real-world scenarios. In this work, we challenge this assumption by introducing ABKSUT, a new framework that incorporates user accountability and traceable ownership into ABKS. We formalize ABKSUT and present a concrete instantiation, Minos, which properly embeds the user's identity in the trapdoor and the data owner's identity in the ciphertext, enabling secure search, fine-grained access control, and post-hoc accountability. We formally prove the security and correctness of Minos and evaluate its performance using real-world datasets. Results show that Minos achieves strong security guarantees with practical efficiency, making it suitable for real-world deployment.

Federated learning decentralizes the training process across clients, allowing clients that do not trust each other to collaboratively train machine learning models without sharing private local data. However, this decentralized approach makes federated learning vulnerable to Poisoning Attacks. Recently, some studies have proposed a new paradigm called Federated Rank Learning (FRL), which uses ranking updates instead of parameter or gradient updates in federated learning. This change transforms the space of updates from continuous to discrete, making the federated learning framework more robust to poisoning attacks.However, we found that some simple and direct poisoning attack methods can easily cause FRL to fail to converge, contrary to the intuition that reducing the update space should limit attackers. This led us to re-examine the security of FRL. We first analyzed the robustness guarantees of FRL and confirmed its vulnerability to poisoning attacks from both theoretical and experimental perspectives. Next, we revisited the impact of changing the update space from continuous to discrete in the framework and found that the advantage of this change does not lie in directly defending against poisoning attacks, but in greatly limiting the attacker’s ability to implement stealthy poisoning attacks. Based on this, we added appropriate defense strategies to FRL, further shrinking the discrete update space into a secure range, and limiting the effectiveness and stealthiness of attacks. Experiments show that this approach significantly improves the ability of FRL to resist poisoning attacks.

Vehicle cybersecurity has emerged as a critical concern, driven by innovation in the automotive industry, e.g., autonomous, electric, or connected vehicles. Current efforts to address these challenges are constrained by the limited computational resources of vehicles and the reliance on connected infrastructures. This motivated the foundation of Vehicle Security Operations Centers (VSOCs) that extend IT-based Security Operations Centers (SOCs) to cover the entire automotive ecosystem, both the in-vehicle and off-vehicle scopes. Security Orchestration, Automation, and Response (SOAR) tools are considered key for implementing an effective cybersecurity solution. However, existing state-of-the-art solutions depend on infrastructure networks such as 4G, 5G, and WiFi, which often face scalability and congestion issues. To address these limitations, we propose a novel SOAR architecture EVSOAR that leverages the EV charging stations for connectivity and computing to enhance vehicle cybersecurity. Our EV-specific SOAR architecture enables real-time analysis and automated responses to cybersecurity threats closer to the EV, reducing cellular latency, bandwidth, and interference limitations. Our experimental results demonstrate a significant improvement in latency, stability, and scalability through the infrastructure and the capacity to deploy computationally intensive applications that are otherwise infeasible within the resource constraints of individual vehicles.

A notable challenge in Electric Vehicle (EV) charging is the time required to fully charge the battery, which can range from 15 minutes to 2-3 hours. However, this idle period for the EV presents an opportunity to offer time-consuming or data-intensive services such as vehicular software updates. ISO 15118 referred to the concept of Value-Added Services (VASs) in the charging scenario, but it remained underexplored in the literature. Our paper addresses this gap by proposing EVolve, the first EV charger compute architecture that supports secure on-charger universal applications with upstream and downstream communication. The architecture covers the end-to-end hardware/software stack, including standard API for vehicles and IT infrastructure. We demonstrate the feasibility and advantages of EVolve by employing and evaluating three suggested valueadded services: vehicular software updates, security information and event management (SIEM), and secure payments. The results demonstrate significant reductions in bandwidth utilization and latency, as well as high throughput, which supports this novel concept and suggests a promising business model for Electric Vehicle charging station operation.

A long-standing challenge is the design of chips resilient to faults and glitches. Both fine-grained gate diversity and coarse-grained modular redundancy have been used in the past. However, these approaches have not been well-studied under other threat models where some stakeholders in the supply chain are untrusted. Increasing digital sovereignty tensions raise concerns regarding the use of foreign off-the-shelf tools and intellectual property (IP), or off-sourcing fabrication, driving research into the design of resilient chips under this threat model. This article addresses a threat model considering three pertinent attacks to resilience: distribution, zonal, and compound attacks. To mitigate these attacks, we introduce theResiLogicframework that exploitsDiversity by Composability: constructing diverse circuits composed of smaller diverse ones by design. This approach enables designers to develop circuits in the early stages of design without the need for additional redundancy in terms of space or cost. To generate diverse circuits, we propose a technique using E-Graphs with new rewrite definitions for diversity. Using this approach at different levels of granularity is shown to improve the resilience of circuit design inResiLogicup to$\times 5$against the three considered attacks.

Amidst the surge in deep learning-based password guessing models, challenges of generating high-quality passwords and reducing duplicate passwords persist. To address these challenges, we present PagPassGPT, a password guessing model constructed on a Generative Pretrained Transformer (GPT). It can perform pattern guided guessing by incorporating pattern structure information as background knowledge, resulting in a significant increase in the hit rate. Furthermore, we propose D&C-GEN to reduce the repeat rate of generated passwords, which adopts the concept of a divide-and-conquer approach. The primary task of guessing passwords is recursively divided into non-overlapping subtasks. Each subtask inherits the knowledge from the parent task and predicts succeeding tokens. In comparison to the state-of-the-art model, our proposed scheme exhibits the capability to correctly guess 12% more passwords while producing 25% fewer duplicates.

With recent legislation on the right to be forgotten, machine unlearning has emerged as a crucial research area. It facilitates the removal of a user's data from federated trained machine learning models without the necessity for retraining from scratch. However, current machine unlearning algorithms are confronted with challenges of efficiency and validity. To address the above issues, we propose a new framework, named Goldfish. It comprises four modules: basic model, loss function, optimization, and extension. To address the challenge of low validity in existing machine unlearning algorithms, we propose a novel loss function. It takes into account the loss arising from the discrepancy between predictions and actual labels in the remaining dataset. Simultaneously, it takes into consideration the bias of predicted results on the removed dataset. Moreover, it accounts for the confidence level of predicted results. Additionally, to enhance efficiency, we adopt knowledge a distillation technique in the basic model and introduce an optimization module that encompasses the early termination mechanism guided by empirical risk and the data partition mechanism. Furthermore, to bolster the robustness of the aggregated model, we propose an extension module that incorporates a mechanism using adaptive distillation temperature to address the heterogeneity of user local data and a mechanism using adaptive weight to handle the variety in the quality of uploaded models. Finally, we conduct comprehensive experiments to illustrate the effectiveness of proposed approach.

Computational offload to hardware accelerators is gaining traction due to increasing computational demands and efficiency challenges. Programmable hardware, like FPGAs, offers a promising platform in rapidly evolving application areas, with the benefits of hardware acceleration and software programmability. Unfortunately, such systems composed of multiple hardware components must consider integrity in the case of malicious components. In this work, we propose Samsara, the first secure and resilient platform that derives, from Byzantine Fault Tolerance (BFT), protocols to enhance the computing resilience of programmable hardware. Samsara uses a novel lightweight hardware-based BFT protocol for Systems-on-Chip, called H-Quorum, that implements the theoretical-minimum latency between applications and replicated compute nodes. To withstand malicious behaviors, Samsara supports hardware rejuvenation, which is used to replace, relocate, or diversify faulty compute nodes. Samsara's architecture ensures the security of the entire workflow while keeping the latency overhead, of both computation and rejuvenation, close to the non-replicated counterpart.

Over-the-Air (OTA) software updates are becoming essential for electric/electronic vehicle architectures in order to reduce recalls amid the increasing software bugs and vulnera-bilities. Current OTA update architectures rely heavily on direct cellular repository-to-vehicle links, which makes the repository a communication bottleneck, and increases the cellular bandwidth utilization cost as well as the software download latency. In this paper, we introduce ScalOTA, an end-to-end scalable OTA software update architecture and secure protocol for modern vehicles. For the first time, we propose using a network of update stations, as part of Electric Vehicle charging stations, to boost the download speed through these stations, and reduce the cellular bandwidth overhead significantly. Our formalized OTA update protocol ensures proven end-to-end chain-of-trust including all stakeholders: manufacturer, suppliers, update stations, and all layers of in-vehicle Electric Control Units (ECUs). The empirical evaluation shows that ScalOTA reduces the bandwidth utilization and download latency up to an order of magnitude compared with current OTA update systems.

Current vehicular Intrusion Detection and Prevention Systems either incur high false-positive rates or do not capture zero-day vulnerabilities, leading to safety-critical risks. In addition, prevention is limited to few primitive options like dropping network packets or extreme options, e.g., ECU Bus-off state. To fill this gap, we introduce the concept of vehicular Intrusion Resilience Systems (IRS) that ensures the resilience of critical applications despite assumed faults or zero-day attacks, as long as threat assumptions are met. IRS enables running a vehicular application in a replicated way, i.e., as a Replicated State Machine, over several ECUs, and then requiring the replicated processes to reach a form of Byzantine agreement before changing their local state. Our study rides the mutation of modern vehicular environments, which are closing the gap between simple and resource-constrained "real-time and embedded systems", and complex and powerful "information technology" ones. It shows that current vehicle (e.g., Zonal) architectures and networks are becoming plausible for such modular fault and intrusion tolerance solutions—deemed too heavy in the past. Our evaluation on a simulated Automotive Ethernet network running two state-of-the-art agreement protocols (Damysus and Hotstuff) shows that the achieved latency and throughout are feasible for many Automotive applications.

Today, leveraging the enormous modular power, diversity and flexibility of manycore systems-on-a-chip (SoCs) requires careful orchestration of complex and heterogeneous resources, a task left to low-level software, e.g., hypervisors. In current architectures, this software forms a single point of failure and worthwhile target for attacks: once compromised, adversaries can gain access to all information and full control over the platform and the environment it controls. This article proposes Midir, an enhanced manycore architecture, effecting a paradigm shift from SoCs to distributed SoCs. Midir changes the way platform resources are controlled, by retrofitting tile-based fault containment through well known mechanisms, while securing low-overhead quorum-based consensus on all critical operations, in particular privilege management and, thus, management of containment domains. Allowing versatile redundancy management, Midir promotes resilience for all software levels, including at low level. We explain this architecture, its associated algorithms and hardware mechanisms and show, for the example of a Byzantine fault tolerant microhypervisor, that it outperforms the highly efficient MinBFT by one order of magnitude.

While previous works have discussed the network delay upper bound that guarantees the consistency of Nakamoto consensus, measuring the actual network latencies and evaluating their impact on miners/pools in Bitcoin remain open questions. This paper fills this gap by: (1) defining metrics that quantify the impact of network latency on the mining network; (2) developing a tool, named miner entanglement (ME), to experimentally evaluate these metrics with a focus on the network latency of the top mining pools; and (3) quantifying the impact of the current network delays on Bitcoin's mining network. For example, we evaluated that Poolin, a Bitcoin mining pool, was able to gain between 0.5% and 1.9% of blocks in addition (i.e., from 36.27 BTC to 137.83 BTC) per week thanks to its low network latency. Moreover, as pools are rational in Bitcoin, we model the strategy a pool would follow to improve its network latency (e.g., by leveraging our ME tool) as a two party game. We show that a Bitcoin mining pool could improve its effective hash rate by up to 4.5%. For a multi-party game, we use a state-of-the-art Bitcoin mining simulator to study the situation where all pools attempt to improve their network latency and show that the largest mining pools would improve their revenue and reach a Nash equilibrium while the smaller mining pools would suffer from a decreased access to the network, and therefore a decreased revenue. These conclusions further incentivize the centralisation of the mining network in Bitcoin, and provide an empirical explanation for the observed tendency of pools to design and rely on low latency private networks.

Critical infrastructures have to withstand advanced and persistent threats, which can be addressed using Byzantine fault tolerant state-machine replication (BFT-SMR). In practice, unattended cyberdefense systems rely on threat level detectors that synchronously inform them of changing threat levels. However, to have a BFT-SMR protocol operate unattended, the state-of-the-art is still to configure them to withstand the highest possible number of faulty replicas$f$they might encounter, which limits their performance, or to make the strong assumption that a trusted external reconfiguration service is available, which introduces a single point of failure. In this work, we present ThreatAdaptive the first BFT-SMR protocol that is automatically strengthened or optimized by its replicas in reaction to threat level changes. We first determine under which conditions replicas can safely reconfigure a BFT-SMR system, i.e., adapt the number of replicas$n$and the fault threshold$f$so as to outpace an adversary. Since replicas typically communicate with each other using an asynchronous network they cannot rely on consensus to decide how the system should be reconfigured. ThreatAdaptive avoids this pitfall by proactively preparing the reconfiguration that may be triggered by an increasing threat when it optimizes its performance. Our evaluation shows that ThreatAdaptive can meet the latency and throughput of BFT baselines configured statically for a particular level of threat, and adapt 30% faster than previous methods, which make stronger assumptions to provide safety.

Abstract Genome-Wide Association Studies (GWAS) identify the genomic variations that are statistically associated with a particular phenotype (e.g., a disease). The confidence in GWAS results increases with the number of genomes analyzed, which encourages federated computations where biocenters would periodically share the genomes they have sequenced. However, for economical and legal reasons, this collaboration will only happen if biocenters cannot learn each others’ data. In addition, GWAS releases should not jeopardize the privacy of the individuals whose genomes are used. We introduce DyPS, a novel framework to conduct dynamic privacy-preserving federated GWAS. DyPS leverages a Trusted Execution Environment to secure dynamic GWAS computations. Moreover, DyPS uses a scaling mechanism to speed up the releases of GWAS results according to the evolving number of genomes used in the study, even if individuals retract their participation consent. Lastly, DyPS also tolerates up to all-but-one colluding biocenters without privacy leaks. We implemented and extensively evaluated DyPS through several scenarios involving more than 6 million simulated genomes and up to 35,000 real genomes. Our evaluation shows that DyPS updates test statistics with a reasonable additional request processing delay (11% longer) compared to an approach that would update them with minimal delay but would lead to 8% of the genomes not being protected. In addition, DyPS can result in the same amount of aggregate statistics as a static release (i.e., at the end of the study), but can produce up to 2.6 times more statistics information during earlier dynamic releases. Besides, we show that DyPS can support a larger number of genomes and SNP positions without any significant performance penalty.

The accelerated digitalisation of society along with technological evolution have extended the geographical span of cyber-physical systems. Two main threats have made the reliable and real-time control of these systems challenging: (i) uncertainty in the communication infrastructure induced by scale, and heterogeneity of the environment and devices; and (ii) targeted attacks maliciously worsening the impact of the above-mentioned communication uncertainties, disrupting the correctness of real-time applications. This article addresses those challenges by showing how to build distributed protocols that provide both real-time with practical performance, and scalability in the presence of network faults and attacks, in probabilistic synchronous environments. We provide a suite of real-time Byzantine protocols, which we prove correct, starting from a reliable broadcast protocol, called PISTIS, up to atomic broadcast and consensus. This suite simplifies the construction of powerful distributed and decentralized monitoring and control applications, including state-machine replication. Extensive empirical simulations showcase PISTIS's robustness, latency, and scalability. For example, PISTIS can withstand message loss (and delay) rates up to 50 percent in systems with 49 nodes and provides bounded delivery latencies in the order of a few milliseconds.

The advent of next-generation sequencing (NGS) machines made DNA sequencing cheaper, but also put pressure on the genomic life-cycle, which includes aligning millions of short DNA sequences, called reads, to a reference genome. On the performance side, efficient algorithms have been developed, and parallelized on public clouds. On the privacy side, since genomic data are utterly sensitive, several cryptographic mechanisms have been proposed to align reads more securely than the former, but with a lower performance. This paper presents DNA-SeAl a novel contribution to improving the privacy × performance product in current genomic workflows. First, building on recent works that argue that genomic data needs to be treated according to a threat-risk analysis, we introduce a multi-level sensitivity classification of genomic variations designed to prevent the amplification of possible privacy attacks. We show that the usage of sensitivity levels reduces future re-identification risks, and that their partitioning helps prevent linkage attacks. Second, after extending this classification to reads, we show how to align and store reads using different security levels. To do so, DNA-SeAl extends a recent reads filter to classify unaligned reads into sensitivity levels, and adapts existing alignment algorithms to the reads sensitivity. We show that using DNA-SeAl allows high performance gains whilst enforcing high privacy levels in hybrid cloud environments.

We develop new foundations on transaction untraceability for CryptoNote-style blockchain systems. In particular, we observe new attacks; develop theoretical foundations to model transaction untraceability; provide the least upper bound of transaction untraceability guarantee; provide ways to efficiently and automatically verify whether a given ledger achieves optimal transaction untraceability; and provide a general solution that achieves provably optimal transaction untraceability. Unlike previous cascade effect attacks (ESORICS' 17 and PETS' 18) on CryptoNote-style transaction untraceability, we consider not only a passive attacker but also an active adaptive attacker. Our observed attacks allow both types of attacker to trace blockchain transactions that cannot be traced by using the existing attacks. We develop a series of new games, which we call "The Sun-Tzu Survival Problem", to model CryptoNote-style blockchain transaction untraceability and our identified attacks. In addition, we obtain seven novel results, where three of them are negative and the rest are positive. In particular, thanks to our abstract game, we are able to build bipartite graphs to model transaction untraceability, and provide reductions to formally relate the hardness of calculating untraceability to the hardness of calculating the number of perfect matchings in all possible bipartite graphs. We prove that calculating transaction untraceability is a #P-complete problem, which is believed to be even more difficult to solve than NP problems. In addition, we provide the first result on the least upper bound of transaction untraceability. Moreover, through our theoretical results, we are able to provide ways to efficiently and automatically verify whether a given ledger achieves optimal transaction untraceability. Furthermore, we propose a simple strategy for CryptoNote-style blockchain systems to achieve optimal untraceability. We take Monero as a concrete example to demonstrate how to apply this strategy to optimise the untraceability guarantee provided by Monero.

Video consumption is one of the most popular Internet activities worldwide. The emergence of sharing videos directly recorded with smartphones raises important privacy concerns. In this paper we propose P3LS, the first practical privacy-preserving peer-to-peer live streaming system. To protect the privacy of its users, P3LS relies on k-anonymity when users subscribe to streams, and on plausible deniability for the dissemination of video streams. Specifically, plausible deniability during the dissemination phase ensures that an adversary is never able to distinguish a user's stream of interest from the fake streams from a statistical analysis (i.e., using an analysis of variance). We exhaustively evaluate P3LS and show that adversaries are not able to identify the real stream of a user with very high confidence. Moreover, P3LS consumes 30% less bandwidth than the standard k-anonymity approach where nodes fully contribute to the dissemination of k streams.

Wireless sensor networks (WSNs), often adhering to a single gateway architecture, constitute the communication backbone for many modern cyber-physical systems (CPSs). Consequently, fault-tolerance in CPS becomes a challenging task, especially when accounting for failures (potentially malicious) that incapacitate the gateway or disrupt the nodes-gateway communication, not to mention the energy, timeliness, and security constraints demanded by CPS domains. This paper aims at ameliorating the fault-tolerance of WSN-based CPS to increase system and data availability. To this end, we propose a replicated gateway architecture augmented with energy-efficient real-time Byzantine-resilient data communication protocols. At the sensors level, we introduce fault-tolerant trustful space-time protocol, a geographic routing protocol capable of delivering messages in an energy-efficient and timely manner to multiple gateways, even in the presence of voids caused by faulty and malicious sensor nodes. At the gateway level, we propose a multigateway synchronization protocol, which we call ByzCast, that delivers timely correct data to CPS applications, despite the failure or maliciousness of a number of gateways. We show, through extensive simulations, that our protocols provide better system robustness yielding an increased system and data availability while meeting CPS energy, timeliness, and security demands.

Byzantine fault-tolerant state-machine replication (BFT-SMR) is a technique for hardening systems to tolerate arbitrary faults. Although robust, BFT-SMR protocols are very costly in terms of the number of required replicas (3f+1 to tolerate f faults) and of exchanged messages. However, with "hybrid" architectures, where "normal" components trust some "special" components to provide properties in a trustworthy manner, the cost of using BFT can be dramatically reduced. Unfortunately, even though such hybridization techniques decrease the message/time/space complexity of BFT protocols, they also increase their structural complexity. Therefore, we introduce Asphalion, the first theorem prover-based framework for verifying implementations of hybrid systems and protocols. It relies on three novel languages: (1) HyLoE: a Hybrid Logic of Events to reason about hybrid fault models; (2) MoC: a Monadic Component language to implement systems as collections of interacting hybrid components; and (3) LoCK: a sound Logic of events-based Calculus of Knowledge to reason about both homogeneous and hybrid systems at a high-level of abstraction (thereby allowing reusing proofs, and capturing the high-level logic of distributed systems). In addition, Asphalion supports compositional reasoning, e.g., through mechanisms to lift properties about trusted-trustworthy components, to the level of the distributed systems they are integrated in. As a case study, we have verified crucial safety properties (e.g., agreement) of several implementations of hybrid protocols.

Today's cyber-physical systems face various impediments to achieving their intended goals, namely, communication uncertainties and faults, relative to the increased integration of networked and wireless devices, hinder the synchronism needed to meet real-time deadlines. Moreover, being critical, these systems are also exposed to significant security threats. This threat combination increases the risk of physical damage. This paper addresses these problems by studying how to build the first real-time Byzantine reliable broadcast protocol (RTBRB) tolerating network uncertainties, faults, and attacks. Previous literature describes either real-time reliable broadcast protocols, or asynchronous (non real-time) Byzantine ones. We first prove that it is impossible to implement RTBRB using traditional distributed computing paradigms, e.g., where the error/failure detection mechanisms of processes are decoupled from the broadcast algorithm itself, even with the help of the most powerful failure detectors. We circumvent this impossibility by proposing RT-ByzCast, an algorithm based on aggregating digital signatures in a sliding time-window and on empowering processes with self-crashing capabilities to mask and bound losses. We show that RT-ByzCast (i) operates in real-time by proving that messages broadcast by correct processes are delivered within a known bounded delay, and (ii) is reliable by demonstrating that correct processes using our algorithm crash themselves with a negligible probability, even with message loss rates as high as 60 percent.

Existing proof-of-work cryptocurrencies cannot tolerate attackers controlling more than 50 percent of the network's computing power at any time, but assume that such a condition happening is “unlikely”. However, recent attack sophistication, e.g., where attackers can rent mining capacity to obtain a majority of computing power temporarily, render this assumption unrealistic. This paper proposes RepuCoin, the first system to provide guarantees even when more than 50 percent of the system's computing power is temporarily dominated by an attacker. RepuCoin physically limits the rate of voting power growth of the entire system. In particular, RepuCoin defines a miner's power by its `reputation', as a function of its work integrated over the time of the entire blockchain, rather than through instantaneous computing power, which can be obtained relatively quickly and/or temporarily. As an example, after a single year of operation, RepuCoin can tolerate attacks compromising 51 percent of the network's computing resources, even if such power stays maliciously seized for almost a whole year. Moreover, RepuCoin provides better resilience to known attacks, compared to existing proof-of-work systems, while achieving a high throughput of 10000 transactions per second (TPS).

Software-defined networking (SDN) decouples the control and data planes of traditional networks, logically centralizing the functional properties of the network in the SDN controller. While this centralization brought advantages such as a faster pace of innovation, it also disrupted some of the natural defenses of traditional architectures against different threats. The literature on SDN has mostly been concerned with the functional side, despite some specific works concerning non-functional properties such as security or dependability. Though addressing the latter in an ad-hoc, piecemeal way may work, it will most likely lead to efficiency and effectiveness problems. We claim that the enforcement of non-functional properties as a pillar of SDN robustness calls for a systemic approach. We further advocate, for its materialization, the reiteration of the successful formula behind SDN: ‘logical centralization’. As a general concept, we propose anchor , a subsystem architecture that promotes the logical centralization of non-functional properties. To show the effectiveness of the concept, we focus on security in this article: we identify the current security gaps in SDNs and we populate the architecture middleware with the appropriate security mechanisms in a global and consistent manner. Essential security mechanisms provided by anchor include reliable entropy and resilient pseudo-random generators, and protocols for secure registration and association of SDN devices. We claim and justify in the article that centralizing such mechanisms is key for their effectiveness by allowing us to define and enforce global policies for those properties; reduce the complexity of controllers and forwarding devices; ensure higher levels of robustness for critical services; foster interoperability of the non-functional property enforcement mechanisms; and promote the security and resilience of the architecture itself. We discuss design and implementation aspects, and we prove and evaluate our algorithms and mechanisms, including the formalisation of the main protocols and the verification of their core security properties using the T amarin prover.

Our increasing dependence on complex and critical information infrastructures and the emerging threat of sophisticated attacks, ask for extended efforts to ensure the correctness and security of these systems. Byzantine fault-tolerant state-machine replication (BFT-SMR) provides a way to harden such systems. It ensures that they maintain correctness and availability in an application-agnostic way, provided that the replication protocol is correct and at least $$n-f$$ out of n replicas survive arbitrary faults. This paper presents Velisarios, a logic-of-events based framework implemented in Coq, which we developed to implement and reason about BFT-SMR protocols. As a case study, we present the first machine-checked proof of a crucial safety property of an implementation of the area’s reference protocol: PBFT.

Fully autonomous driving is one if not the killer application for the upcoming decade of real-time systems. However, in the presence of increasingly sophisticated attacks by highly skilled and well equipped adversarial teams, autonomous driving must not only guarantee timeliness and hence safety. It must also consider the dependability of the software concerning these properties while the system is facing attacks. For distributed systems, fault-and-intrusion tolerance toolboxes already offer a few solutions to tolerate partial compromise of the system behind a majority of healthy components operating in consensus. In this paper, we present a concept of an intrusion-tolerant architecture for autonomous driving. In such a scenario, predictability and recovery challenges arise from the inclusion of increasingly more complex software on increasingly less predictable hardware. We highlight how an intrusion tolerant design can help solve these issues by allowing timeliness to emerge from a majority of complex components being fast enough, often enough while preserving safety under attack through pre-computed fail safes.

Time-triggered real-time systems achieve deterministic behaviour, making them suitable for safety-critical environments. However, this determinism also allows attackers to finetune attacks after studying the system behaviour through side channels, targeting safety-critical victim tasks. Assuming fault independence, replication tolerates both random and malicious faults of up to f replicas. Yet, directed attacks violate the fault independence assumption. This violation possibly gives attackers the edge to compromise more than f replicas simultaneously, in particular if they can mount the attack from already compromised components. In this paper, we sketch mitigation strategies for time-triggered systems with task replication to withstand directed timing attacks and show preliminary results on their effectiveness and practicality.

The recent introduction of new DNA sequencing techniques caused the amount of processed and stored biological data to skyrocket. In order to process these vast amounts of data, bio-centers have been tempted to use low-cost public clouds. However, genomes are privacy sensitive, since they store personal information about their donors, such as their identity, disease risks, heredity and ethnic origin. The first critical DNA processing step that can be executed in a cloud, i.e., read alignment, consists in finding the location of the DNA sequences produced by a sequencing machine in the human genome. While recent developments aim at increasing performance, only few approaches address the need for fast and privacy preserving read alignment methods. This paper introduces MaskAl, a novel approach for read alignment. MaskAl combines a fast preprocessing step on raw genomic data - filtering and masking - with established algorithms to align sanitized reads, from which sensitive parts have been masked out, and refines the alignment score using the masked out information with Intel's software guard extensions (SGX). MaskAl is a highly competitive privacy-preserving read alignment software that can be massively parallelized with public clouds and emerging enclave clouds. Finally, MaskAl is nearly as accurate as plain-text approaches (more than 96% of aligned reads with MaskAl compared to 98% with BWA) and can process alignment workloads 87% faster than current privacy-preserving approaches while using less memory and network bandwidth.

Technologies such as Industry 4.0 or assisted/autonomous driving are relying on highly customized cyber-physical realtime systems. Those systems are designed to match functional safety regulations and requirements such as EN ISO 13849, EN IEC 62061 or ISO 26262. However, as systems – especially vehicles – are becoming more connected and autonomous, they become more likely to suffer from new attack vectors. New features may meet the corresponding safety requirements but they do not consider adversaries intruding through security holes with the purpose of bringing vehicles into unsafe states. As research goal, we want to bridge the gap between security and safety in cyber-physical real-time systems by investigating real-time-aware intrusion-tolerant architectures for automotive use-cases.

Sequencing thousands of human genomes has enabled breakthroughs in many areas, among them precision medicine, the study of rare diseases, and forensics. However, mass collection of such sensitive data entails enormous risks if not protected to the highest standards. In this article, we follow the position and argue that post-alignment privacy is not enough and that data should be automatically protected as early as possible in the genomics workflow, ideally immediately after the data is produced. We show that a previous approach for filtering short reads cannot extend to long reads and present a novel filtering approach that classifies raw genomic data (i.e., whose location and content is not yet determined) into privacy-sensitive (i.e., more affected by a successful privacy attack) and non-privacy-sensitive information. Such a classification allows the fine-grained and automated adjustment of protective measures to mitigate the possible consequences of exposure, in particular when relying on public clouds. We present the first filter that can be indistinctly applied to reads of any length, i.e., making it usable with any recent or future sequencing technologies. The filter is accurate, in the sense that it detects all known sensitive nucleotides except those located in highly variable regions (less than 10 nucleotides remain undetected per genome instead of 100,000 in previous works). It has far less false positives than previously known methods (10% instead of 60%) and can detect sensitive nucleotides despite sequencing errors (86% detected instead of 56% with 2% of mutations). Finally, practical experiments demonstrate high performance, both in terms of throughput and memory consumption.

The world is becoming an immense critical information infrastructure, with the fast and increasing entanglement of utilities, telecommunications, Internet, cloud, and the emerging IoT tissue. This may create enormous opportunities, but also brings about similarly extreme security and dependability risks. We predict an increase in very sophisticated targeted attacks, or advanced persistent threats (APT), and claim that this calls for expanding the frontier of security and dependability methods and techniques used in our current CII. Extreme threats require extreme defenses: we propose resilience as a unifying paradigm to endow systems with the capability of dynamically and automatically handling extreme adversary power, and sustaining perpetual and unattended operation. In this position paper, we present this vision and describe our methodology, as well as the assurance arguments we make for the ultra-resilient components and protocols they enable, illustrated with case studies in progress.

The Internet has led to the creation of a digital society, where (almost) everything is connected and is accessible from anywhere. However, despite their widespread adoption, traditional IP networks are complex and very hard to manage. It is both difficult to configure the network according to predefined policies, and to reconfigure it to respond to faults, load, and changes. To make matters even more difficult, current networks are also vertically integrated: the control and data planes are bundled together. Software-defined networking (SDN) is an emerging paradigm that promises to change this state of affairs, by breaking vertical integration, separating the network's control logic from the underlying routers and switches, promoting (logical) centralization of network control, and introducing the ability to program the network. The separation of concerns, introduced between the definition of network policies, their implementation in switching hardware, and the forwarding of traffic, is key to the desired flexibility: by breaking the network control problem into tractable pieces, SDN makes it easier to create and introduce new abstractions in networking, simplifying network management and facilitating network evolution. In this paper, we present a comprehensive survey on SDN. We start by introducing the motivation for SDN, explain its main concepts and how it differs from traditional networking, its roots, and the standardization activities regarding this novel paradigm. Next, we present the key building blocks of an SDN infrastructure using a bottom-up, layered approach. We provide an in-depth analysis of the hardware infrastructure, southbound and northbound application programming interfaces (APIs), network virtualization layers, network operating systems (SDN controllers), network programming languages, and network applications. We also look at cross-layer problems such as debugging and troubleshooting. In an effort to anticipate the future evolution of this new paradigm, we discuss the main ongoing research efforts and challenges of SDN. In particular, we address the design of switches and control platforms - with a focus on aspects such as resiliency, scalability, performance, security, and dependability - as well as new opportunities for carrier transport networks and cloud providers. Last but not least, we analyze the position of SDN as a key enabler of a software-defined environment.

The Third International Workshop on Dependability of Clouds, Data Centers, and Virtual Machine Technology (DCDV 2013) features papers covering various aspects of dependability and security in Clouds and Data Centers. Four sessions covering Cloud and Data Center Networking, Dependability Evaluation, Mobile and Cloud Computing, and Virtualization and Cloud include eleven papers.

State machine replication (SMR) is a generic technique for implementing fault-tolerant distributed services by replicating them in sets of servers. There have been several proposals for using SMR to tolerate arbitrary or Byzantine faults, including intrusions. However, most of these systems can tolerate at most f faulty servers out of a total of 3f+1. We show that it is possible to implement a Byzantine SMR algorithm with only 2f+1 replicas by extending the system with a simple trusted distributed component. Several performance metrics show that our algorithm, BFT-TO, fares well in comparison with others in the literature. Furthermore, BFT-TO is not vulnerable to some recently presented performance attacks that affect alternative approaches.

We present two asynchronous Byzantine fault-tolerant state machine replication (BFT) algorithms, which improve previous algorithms in terms of several metrics. First, they require only 2f+1 replicas, instead of the usual 3f+1. Second, the trusted service in which this reduction of replicas is based is quite simple, making a verified implementation straightforward (and even feasible using commercial trusted hardware). Third, in nice executions the two algorithms run in the minimum number of communication steps for nonspeculative and speculative algorithms, respectively, four and three steps. Besides the obvious benefits in terms of cost, resilience and management complexity-fewer replicas to tolerate a certain number of faults-our algorithms are simpler than previous ones, being closer to crash fault-tolerant replication algorithms. The performance evaluation shows that, even with the trusted component access overhead, they can have better throughput than Castro and Liskov's PBFT, and better latency in networks with nonnegligible communication delays.

MapReduce is a framework for processing large data sets largely used in cloud computing. MapReduce implementations like Hadoop can tolerate crashes and file corruptions, but there is evidence that general arbitrary faults do occur and can affect the correctness of job executions. Furthermore, many individual cloud outages have been reported, raising concerns about depending on a single cloud. We present a MapReduce runtime that tolerates arbitrary faults and runs in a set of clouds at a reasonable cost in terms of computation and execution time. The main challenge is to avoid sending through the internet the huge amount of data that would normally be exchanged between map and reduce tasks.

Distributed protocols executing in uncertain environments, like the Internet or ambient computing systems, should dynamically adapt to environment changes in order to preserve Quality of Service (QoS). In earlier work, it was shown that QoS adaptation should be dependable, if correctness of protocol properties is to be maintained. More recently, some ideas concerning specific strategies and methodologies for improving QoS adaptation have been proposed. In this article we describe Adaptare , a complete framework for dependable QoS adaptation. We assume that during its lifetime, a system alternates periods where its temporal behavior is well characterized, with transition periods during which a variation of the environment conditions occurs. Our method is based on the following: if the environment is generically characterized in analytical terms, and we can detect the alternation of these stable and transient phases, we can improve the effectiveness and dependability of QoS adaptation. To prove our point we provide detailed evaluation results of the proposed solutions. Our evaluation is based on synthetic data flows generated from probabilistic distributions, as well as on real data traces collected in various Internet-based environments. We compare our solution with other approaches and we show that Adaptare, albeit more complex, is very effective, allowing protocols to adapt to the available resources in a dependable way.

Randomized agreement protocols have been around for more than two decades. Often assumed to be inefficient due to their high expected communication and computation complexities, they have remained overlooked by the community-at-large as a valid solution for the deployment of fault-tolerant distributed systems. This paper aims to demonstrate that randomization can be a very competitive approach even in hostile environments where arbitrary faults can occur. A stack of randomized intrusion-tolerant protocols is described and its performance evaluated under several settings in both local-area-network (LAN) and wide-area-network environments. The stack provides a set of relevant services ranging from basic communication primitives up to atomic broadcast. The experimental evaluation shows that the protocols are efficient, especially in LAN environments where no performance reduction is observed under certain Byzantine faults.

In the past, some research has been done on how to use proactive recovery to build intrusion-tolerant replicated systems that are resilient to any number of faults, as long as recoveries are faster than an upper bound on fault production assumed at system deployment time. In this paper, we propose a complementary approach that enhances proactive recovery with additional reactive mechanisms giving correct replicas the capability of recovering other replicas that are detected or suspected of being compromised. One key feature of our proactive-reactive recovery approach is that, despite recoveries, it guarantees the availability of a minimum number of system replicas necessary to sustain correct operation of the system. We design a proactive-reactive recovery service based on a hybrid distributed system model and show, as a case study, how this service can effectively be used to increase the resilience of an intrusion-tolerant firewall adequate for the protection of critical infrastructures.

The increasing reliance put on networked computer systems demands higher levels of dependability. This is even more relevant as new threats and forms of attack are constantly being revealed, compromising the security of systems. This paper addresses this problem by presenting an attack injection methodology for the automatic discovery of vulnerabilities in software components. The proposed methodology, implemented in AJECT, follows an approach similar to hackers and security analysts to discover vulnerabilities in network-connected servers. AJECT uses a specification of the server's communication protocol and predefined test case generation algorithms to automatically create a large number of attacks. Then, while it injects these attacks through the network, it monitors the execution of the server in the target system and the responses returned to the clients. The observation of an unexpected behavior suggests the presence of a vulnerability that was triggered by some particular attack (or group of attacks). This attack can then be used to reproduce the anomaly and to assist the removal of the error. To assess the usefulness of this approach, several attack injection campaigns were performed with 16 publicly available POP and IMAP servers. The results show that AJECT could effectively be used to locate vulnerabilities, even on well-known servers tested throughout the years.

Systems connected to the Internet are highly susceptible to denial-of-service attacks that can compromise service availability, causing damage to customers and providers. Due to errors in the design or coding phases, particular client-server interactions can be made to consume much more resources than necessary easing the success of this kind of attack.To address this issue we propose a new methodology for the detection and identification of local resource-exhaustion vulnerabilities. The methodology also gives a prediction on the necessary effort to exploit a specific vulnerability, useful to support decisions regarding the configuration of a system, in order to sustain a certain attack magnitude.The methodology was implemented in a tool called PREDATOR that is able to automatically generate malicious traffic and to perform post-processing analysis to build accurate resource usage projections on a given target server.The validity of the approach was demonstrated with several synthetic programs and well-known DNS servers.

In environments like the Internet, faults follow unusual patterns, dictated by the combination of malicious attacks with accidental faults such as long communication delays caused by temporary network partitions. In this scenario, attackers can force buffer overflows in order to leave the system in an inconsistent state or to prevent it from doing progress, causing a denial of service. This paper is about the effects that finite memory has on intrusion-tolerant protocols and systems. We present the problem and propose a generic mitigation technique based on repair nodes that reduces the buffer space requirements. An experimental evaluation of the buffer usage with and without this technique is presented, allowing to assess in practice the effects of finite memory in a real, albeit simple, intrusion-tolerant system.

This paper presents a study on the performance of intrusion-tolerant protocols in wireless LANs. The protocols are evaluated in several different environmental settings, and also within the context of a car platooning application for distributed cruise control. The experimental evaluation reveals how performance is affected by the various environmental parameters such as the wireless standard, group size, and network topology. The distributed cruise control application demonstrates the practicability of such protocols, even when subjected to malicious faults.

Previous works have studied how to use proactive recovery to build intrusion-tolerant replicated systems that are resilient to any number of faults, as long as recoveries are faster than an upper-bound on fault production assumed at system deployment time. In this paper, we propose a complementary approach that combines proactive recovery with services that allow correct replicas to react and recover replicas that they detect or suspect to be compromised. One key feature of our proactive-reactive recovery approach is that, despite recoveries, it guarantees the availability of the minimum amount of system replicas necessary to sustain system's correct operation. We design a proactive-reactive recovery service based on a hybrid distributed system model and show, as a case study, how this service can effectively be used to augment the resilience of an intrusion-tolerant firewall adequate for the protection of critical infrastructures.

Intrusion tolerance has been proposed as a new paradigm for computer systems security. The idea is to apply the fault tolerance paradigm in the domain of systems security accepting that malicious faults (attacks, intrusions) can never be entirely prevented, and that highly resilient systems have to tolerate these faults. Research in this area has produced a set of clever intrusion-tolerant protocols and systems (I/T protocols and I/T systems for short). However, we believe that an issue has been overlooked: that servers have, finite memory, so the number of messages that can be stored in their buffers is limited. Intuitively, this can be a problem in systems in which there are many messages being exchanged. Moreover, all of these systems assume that the environment is essentially asynchronous, i.e., that there are no bounds on communication and processing delays. Assuming this kind of model is very important in order to prevent the success of attacks against time.

In today's world where distributed systems form many of our critical infrastructures, dependability outagesare becoming increasingly common. In many situations, it is necessary to not just detect a failure, but alsoto diagnose the failure, i.e., to identify the source of the failure. Diagnosis is challenging since highthroughput applications with frequent interactions between the different components allow fast errorpropagation. It is desirable to consider applications as black-boxes for the diagnostic process. In thispaper, we propose a Monitor architecture for diagnosing failures in large-scale network protocols. TheMonitor only observes the message exchanges between the protocol entities (PEs) remotely and doesnot access internal protocol state. At runtime, it builds a causal graph between the PEs based on theircommunication and uses this together with a rule base of allowed state transition paths to diagnose thefailure. The tests used for the diagnosis are based on the rule base and are assumed to have imperfectcoverage. The hierarchical Monitor framework allows distributed diagnosis handling failures at individualMonitors. The framework is implemented and applied to a reliable multicast protocol executing on ourcampus-wide network. Fault injection experiments are carried out to evaluate the accuracy and latency ofthe diagnosis.

Randomized agreement protocols, often assumed to be inefficient due to their high expected communication and time complexities, they have remained largely overlooked by the community-at-large as a valid solution for the deployment of fault-tolerant distributed systems. This paper aims to demonstrate that randomization can be a very competitive approach even in hostile environments where arbitrary faults can occur. A stack of randomized intrusion-tolerant protocols is described and its performance evaluated under different faultloads. The stack provides a set of relevant services ranging from basic communication primitives up to atomic broadcast. The experimental evaluation shows that the protocols are efficient and no performance reduction is observed under certain Byzantine faults

Due to our increasing reliance on computer systems, security incidents and their causes are important problems that need to be addressed. To contribute to this objective, the paper describes a new tool for the discovery of security vulnerabilities on network connected servers. The AJECT tool uses a specification of the server's communication protocol to automatically generate a large number of attacks accordingly to some predefined test classes. Then, while it performs these attacks through the network, it monitors the behavior of the server both from a client perspective and inside the target machine. The observation of an incorrect behavior indicates a successful attack and the potential existence of a vulnerability. To demonstrate the usefulness of this approach, a considerable number of experiments were carried out with several IMAP servers. The results show that AJECT can discover several kinds of vulnerabilities, including a previously unknown vulnerability

The CAN Enhanced Layer (CANELy) is a CAN-based infrastructure capable of extremely reliable communication. This paper describes the mechanisms and the techniques used in CANELy to enforce system correctness in the time-domain despite the occurrence of network errors (inaccessibility). The paper discusses how to integrate in the existing CANELy machinery, the control of inaccessibility and the management of timers, at several levels of the system. In particular, application and low-level protocol layers are addressed. In addition, a relevant set of parameters are available for system monitoring, allowing the validation/enforcement of the system model.

The paper presents a comparative performance study of the two main classes of randomized binary consensus protocols: a local coin protocol, with an expected high communication complexity and cheap symmetric cryptography, and a shared coin protocol, with an expected low communication complexity and expensive asymmetric cryptography. The experimental evaluation was conducted on a LAN environment, by varying several system parameters, such as the fault types and number of processes. The analysis shows that there is a significant gap between the theoretical and the practical performance results of these protocols, and provides an important insight into what actually happens during their execution

In a recent paper, we presented proactive resilience as a new approach to proactive recovery, based on architectural hybridization. We showed that, with appropriate assumptions about fault rate, proactive resilience makes it possible to build distributed intrusion-tolerant systems guaranteed not to suffer more than the assumed number of faults during their lifetime. In this paper, we explore the impact of these assumptions in asynchronous systems, and derive conditions that should be met by practical systems in order to guarantee long-lived, i.e., available, intrusion-tolerant operation. Our conclusions are based on analytical and simulation results as implemented in Mobius, and we use the same modeling environment to show that our approach offers higher resilience in comparison with other proactive intrusion-tolerant system models

This paper proposes a stack of three Byzantine-resistant protocols aimed to be used in practical distributed systems: multi-valued consensus, vector consensus and atomic broadcast. These protocols are designed as successive transformations from one to another. The first protocol, multi-valued consensus, is implemented on top of a randomized binary consensus and a reliable broadcast protocol. The protocols share a set of important structural properties. First, they do not use digital signatures constructed with public-key cryptography, a well-known performance bottleneck in this kind of protocols. Second, they are time-free, i.e. they make no synchrony assumptions, since these assumptions are often vulnerable to subtle but effective attacks. Third, they are completely decentralized, thus avoiding the cost of detecting corrupt leaders. Fourth, they have optimal resilience, i.e. they tolerate the failure of f = ⌊(n−1)/3⌋ out of a total of n processes. In terms of time complexity, the multi-valued consensus protocol terminates in a constant expected number of rounds, while the vector consensus and atomic broadcast protocols have O(f) complexity. The paper also proves the equivalence between multi-valued consensus and atomic broadcast in the Byzantine failure model without signatures. A similar proof is given for the equivalence between multi-valued consensus and vector consensus. These two results have theoretical relevance since they show once more that consensus is a fundamental problem in distributed systems.

No abstract available.

Fault-tolerant protocols, asynchronous and synchronous alike, make stationary fault assumptions: only a fraction f of the total n nodes may fail. Whilst a synchronous protocol is expected to have a bounded execution time, an asynchronous one may execute for an arbitrary amount of time, possibly sufficient for f+1 nodes to fail. This can compromise the safety of the protocol and ultimately the safety of the system. Recent papers propose asynchronous protocols that can tolerate any number of faults over the lifetime of the system, provided that at most f nodes become faulty during a given interval. This is achieved through the so-called proactive recovery, which consists of periodically rejuvenating the system. Proactive recovery in asynchronous systems, though a major breakthrough, has some limitations which had not been identified before. In this paper, we introduce a system model expressive enough to represent these problems which remained in oblivion with the classical models. We introduce the predicate exhaustion-safe, meaning freedom from exhaustion-failures. Based on it, we predict the extent to which fault/intrusion-tolerant distributed systems (synchronous and asynchronous) can be made to work correctly. Namely, our model predicts the impossibility of guaranteeing correct behavior of asynchronous proactive recovery systems as exist today. To prove our point, we give an example of how these problems impact an existing fault/intrusion-tolerant distributed system, the CODEX system, and having identified the problem, we suggest one (certainly not the only) way to tackle it.

Nowadays, one of the major concerns about the services provided over the Internet is related to their availability. Replication is a well known way to increase the availability of a service. However, replication has some associated costs, namely it is necessary to guarantee a correct coordination among the replicas. Moreover, being the Internet such an unpredictable and insecure environment, coordination correctness should be tolerant to Byzantine faults and immune to timing failures. Several past works address agreement and replication techniques that tolerate Byzantine faults under the asynchronous model, but they all make the assumption that the number of faulty replicas is bounded and known. Assuming a maximum number of f faulty replicas under the asynchronous model is dangerous - there is no way of guaranteeing that no more than f faults will occur during the execution of the system. In this paper, we describe a resilient f fault/intrusion-tolerant state machine replication system, which guarantees that no more than f faults ever occur. The system is asynchronous in its most part and it resorts to a synchronous oracle to periodically remove the effects of faults/attacks from the replicas.

The design of embedded real-time systems requires skills from multiple specific disciplines, including, but not limited to, control, computer science, and electronics. This often involves experts from differing backgrounds, who do not recognize that they address similar, if not identical, issues from complementary angles. Design methodologies are lacking in rigor and discipline so that demonstrating correctness of an embedded design, if at all possible, is a very expensive proposition that may delay significantly the introduction of a critical product. While the economic importance of embedded systems is widely acknowledged, academia has not paid enough attention to the education of a community of high-quality embedded system designers, an obvious difficulty being the need of interdisciplinarity in a period where specialization has been the target of most education systems. This paper presents the reflections that took place in the European Network of Excellence Artist leading us to propose principles and structured contents for building curricula on embedded software and systems.

This paper presents a solution to the vector consensus problem for Byzantine asynchronous systems augmented with wormholes. Wormholes prefigure a hybrid distributed system model, embodying the notion of an enhanced part of the system with "good" properties otherwise not guaranteed by the "normal" weak environment. A protocol built for this type of system runs in the asynchronous part, where f out of n/spl ges/3f+1 processes might be corrupted by malicious adversaries. However, sporadically, processes can rely on the services provided by the wormhole for the correct execution of simple operations. One of the nice features of this setting is that it is possible to keep the protocol completely time-free and, in addition, to circumvent the FLP impossibility result by hiding all time-related assumptions in the wormhole. Furthermore, from a performance perspective, it leads to the design of a protocol with a good time complexity.

This paper describes and discusses the work carried on in the context of the CORTEX project, for the development of adaptive real-time applications in wormhole based systems. The architecture of CORTEX relies on the existence of a timeliness wormhole, called timely computing base (TCB), which we have described in previous papers. Here we focus on the practical demonstration of the wormhole concept, through a demo with two complementary facets. The objective is to illustrate the effectiveness of the concept from a practical, yet rigorous, perspective, which is done with the help of an emulation framework that we present in the paper. Furthermore, the paper also describes two different ways of implementing timeliness wormholes on top of both wired and wireless infrastructures.

The application of dependability concepts and techniques to the design of secure distributed systems is raising a considerable amount of interest in both communities under the designation of intrusion tolerance. However, practical intrusion-tolerant replicated systems based on the state machine approach (SMA) can handle at most f Byzantine components out of a total of n = 3f + 1, which is the maximum resilience in asynchronous systems. This paper extends the normal asynchronous system with a special distributed oracle called TTCB. Using this extended system we manage to implement an intrusion-tolerant service based on the SMA with only 2f + 1 replicas. Albeit a few other papers in the literature present intrusion-tolerant services with this approach, this is the first time the number of replicas is reduced from 3f + 1 to 2f + 1. Another interesting characteristic of the described service is a low time complexity.

Fault-tolerant distributed systems based on fieldbuses may benefit to a great extent from the availability of semantically rich communication services, such as those provided by group communication, clock synchronization, membership and failure detection. This is specially true of distributed critical control applications. However, the migration of those services to the realm of simple fieldbuses, such as the native Controller Area Network (CAN) protocol family, presents non-negligible problems, since it lacks most of the functionality required of a fault-tolerant distributed system, such as reliable message broadcast guarantees, distributed node failure detection, and site membership services. As part of our endeavor to design a CAN-based infrastructure support for extremely reliable distributed computer control, dubbed CAN Enhanced Layer (CANELy), we have been addressing the problem of fault-tolerant communications on fieldbuses in a comprehensive way. In this paper, we show that node failure detection and site membership services can be efficiently supported by a simple software layer built on top of an exposed CAN controller interface.

Designing applications with timeliness requirements in environments of uncertain synchrony is known to be a difficult problem. In this paper we follow the perspective of timing fault tolerance: tinting errors occur and they are processed using redundancy, e.g., component replication, to recover and deliver timely service. We introduce a paradigm for generic tinting fault tolerance with replicated state machines. The paradigm is based on the existence of Timing Failure Detection with tinted completeness and accuracy properties. Generic timing fault tolerance implies the ability to dependably observe the system and to timely notify timing failures, which we discuss in the paper On the other hand, it ensures replica determinism with respect to time (temporal consistency), and safety in case of spare exhaustion. We show that the paradigm can be addressed and realized in the framework of the timely computing base (TCB) model and architecture. Furthermore, we illustrate the generality, of our approach by reviewing previous existing solutions and by showing that in contrast with ours, they, only secure a restricted semantics, or simply provide ad-hoc solutions.

The paper presents a new reliable multicast protocol that tolerates arbitrary faults, including Byzantine faults. This protocol is developed using a novel way of designing secure protocols which is based on a well-founded hybrid failure model. Despite our claim of arbitrary failure resilience, the protocol need not necessarily incur the cost of "Byzantine agreement", in number of participants and round/message complexity. It can rely on the existence of a simple distributed security kernel-the TTCB-where the participants only execute crucial parts of the protocol operation, under the protection of a crash failure model. Otherwise, participants follow an arbitrary failure model. The TTCB provides only a few basic services, which allow our protocol to have an efficiency similar to that of accidental fault-tolerant protocols: for f faults, our protocol requires f+2 processes, instead of 3f+1 in Byzantine systems. Besides, the TTCB (which is synchronous) allows secure operation of timed protocols, despite the unpredictable time behavior of the environment (possibly due to attacks on timing assumptions).

Current systems are very often based on large-scale, unpredictable and unreliable infrastructures. However, users of these systems increasingly require services with timeliness properties. This creates a difficult-to-solve contradiction with regard to the adequate time model: should it be synchronous, or asynchronous? In this paper, we propose an architectural construct and programming model which address this problem. We assume the existence of a component that is capable of executing timely functions, however asynchronous the rest of the system may be. We call this component the "timely computing base", and it can be used by the other components to execute a set of simple but crucial time-related services. We also show how to use it to build dependable and timely applications exhibiting varying degrees of timeliness assurance, under several synchrony models.

The round-trip duration measurement technique is fundamental in solving many problems in asynchronous distributed systems. In essence, this technique provides the means for reading remote clocks with a known and bounded error. Therefore, it is used as a fundamental building block in several clock synchronization algorithms. In general, the technique can be used to implement duration measurement services, such as that of the timely computing base model. In this paper we propose a new technique for measuring distributed durations that minimizes the measurement error and is able to keep this error almost stable. The new technique can be used to improve the precision of remote clock reading in certain situations. We provide a protocol that implements this new technique and present some evaluation results. The results clearly show that our solution is better than existing ones.

In open and heterogeneous environments, where an unpredictable number of applications compete for a limited amount of resources, executions can be affected by also unpredictable delays, which may not even be bounded. Since many of these applications have timeliness requirements, they can only be implemented if they are able to adapt to the existing conditions. We present a novel approach, called dependable QoS adaptation, which can only be achieved if the environment is accurately and reliably observed. Dependable QoS adaptation is based on the timely computing base (TCB) model. The TCB model is a partial quality of service synchrony model that adequately characterizes environments of uncertain synchrony and allows, at the same time, the specification and verification of timeliness requirements. We introduce the coverage stability property and show that adaptive applications can use the TCB to dependably adapt and enjoy this property. We describe the characteristics and the interface of a QoS coverage service and discuss its implementation details.

Real-time behavior is specified in compliance with timeliness requirements, which in essence calls for synchronous system models. However systems often rely on unpredictable and unreliable infrastructures, that suggest the use of asynchronous models. Several models have been proposed to address this issue. We propose an architectural construct that takes a generic approach to the problem of programming in the presence of uncertain timeliness. We assume the existence of a component, capable of executing timing functions, which helps applications with varying degrees of synchrony to behave reliably despite the occurrence of timing failures. We call this component the Timely Computing Base, TCB. This paper describes the TCB architecture and model, and discusses the application programming interface for accessing the TCB services. The implementation of the TCB services uses fail-awareness techniques to increase the coverage of TCB properties.

Object oriented techniques have been along the last decade one of the most useful programming paradigms. However, for distributed embedded systems, the semantic gap between the object orientation layer and the underlying infrastructure is extremely large. This gap can be narrowed, should the embedded system platform provide semantically rich communication and management services. The paper outlines our research effort in the provision of such services by CAN based (Controller Area Network) systems.

In a quasi-synchronous environment worst-case times associated with a given activity are usually much higher than the average time needed for that activity. Using always those worst-case times can make a system useless. However not using them may lend to timing failures. On the other hand, fully synchronous behavior is usually restricted to small parts of the global system. In a previously defined architecture we use this small synchronous part to control and validate the other parts of the system. In this paper we present a light-weight group protocol that together with the previously defined architecture makes it possible to efficiently handle timing failures in a quasi-synchronous system. This is specially interesting when active replication is used. It provides application support for a fail-safe behavior or controlled (timely and safe) switching between different qualities of service.

This paper presents a new communication service. The novelty of the work resides in the distributed architecture adopted which is based on communication agents in every tool and in every host of the design environment. The importance of the work is demonstrated by the results achieved: improved performance, reduced network traffic and fault-tolerance to host and network failures.

Totally ordered multicast protocols have proved to be extremely useful in supporting fault-tolerant distributed applications. This paper compares the performance of the two main classes of protocols providing total order in large-scale systems (token-site and symmetric protocols) and proposes a new dynamic hybrid protocol that, when applied to systems where the topology/traffic patterns are not known a priori, offers a much lower latency than any of the previous classes of protocols in isolation.

The virtual synchrony model for group communication has proven to be a powerful paradigm for building distributed applications. Implementations of virtual synchrony usually require the use of failure detectors and failure recovery protocols. In applications that require the use of a large number of groups, significant performance gains can be attained if these groups share the resources required to provide virtual synchrony. A service that maps user groups onto instances of a virtually synchronous implementation is called a light-weight group service. This paper proposes a new design for the light-weight group protocols that enables the usage of this service in a transparent manner as a test case, the new design was implemented in the Horus system, although the underlying principles can be applied to other architectures as well. The paper also presents performance results from this implementation.

In recent years there has been a growing interest in developing communication systems that are able to deliver messages respecting potential causality. Unfortunately, causal delivery cannot be provided without costs: extra delays may be induced on message delivery or processes may be required to maintain and exchange records of causal relations. In this paper we present an extension to previous work on compression of causal information using knowledge about the topology of the communication structure. In order to make practical use of this result, we present a methodology to model the communication system. The technique exploits the physical structure of existing networks, in particular its hierarchical nature, to create a communication graph where causal separators match the underlying physical and administrative organization. We show that this approach can be applied to existing large-scale systems, providing the means for using topological timestamping with negligible overhead.

Although many algorithms and implementations of replicated services have been developed, most have embedded aspects of the replication management in the invocation protocol. This makes it extremely difficult to modify the replication protocol without changing the protocol used by the clients, and causes an undesirable violation of both transparency and modularity. The GRIP protocol supports the fault-tolerant remote invocation of replicated services, providing not only the usual location transparency but also transparency of replication semantics. Our approach is independent of the details of the replica control protocol used to maintain the consistency of server replicas. We use a lightweight remote invocation protocol in order to minimize the impact on the client of issues such as scale and replication consistency maintenance. Furthermore, unlike most previous systems we provide explicit support for weakly consistent replication protocols. GRIP is designed as a collection of modular services, which can be configured according to the needs of the application.>

Presents a processor group membership protocol designed to run on top of a local area network. The protocol maintains information about a selected group of stations that explicitly join the protocol by keeping a replica of a global membership table at every member. Additionally, the protocol guarantees that a given station always occupies the same entry in the table. As a result, table indexes uniquely and universally identify a station and can thus be used as short identifiers. The interest of a processor group membership is twofold: it is a powerful auxiliary for process group membership management and it provides support for efficient message addressing.>

A clock synchronization algorithm was given by P. Verissimo et al. (1989), dubbed a posteriori agreement, a variant of the convergence nonaveraging technique. By exploiting the characteristics of broadcast networks, the effect of message delivery delay variance is largely reduced. In consequence, the precision achieved by the algorithm is drastically improved. Accuracy preservation is near to optimal. A particular materialization of this algorithm, implemented as a time service of the xAMp group communications system, is given here. The algorithm was implemented using some of the primitives offered by xAMp, which simplified the work and stressed its advantages. Performance results for this implementation obtained on two different infrastructures are presented. Timings validate the design choices and clearly show that the algorithm is able to provide improved precision without compromising accuracy and reliability.>

Continuity of service and bounded and known message delivery latency are requirements of a number of applications, which are imperfectly fulfilled by standard LANs. Most previous studies have addressed this issue by computing worst-case access/transmission delays only for normal LAN operation. However, LANs are subject to failures, namely partitions. Since most applications can live with temporary glitches in LAN operation, an alternative approach is to quantify all these glitches or temporary partitions, called inaccessibilities, and to derive a worst-case figure, to be added to the worst-case transmission delay in the absence of faults. In these conditions, reliable real-time operation is possible on nonreplicated LANs. An exhaustive study of the inaccessibility characteristics of the ISO 8802/4 token-bus LAN is described.>

The xAMp is a highly versatile group communications service aimed at supporting the development of distributed applications with different dependability, functionality, and performance requirements. These range from unreliable and nonordered to atomic multicast, and are enhanced by efficient group addressing and management support. The basic protocols are synchronous, clockless and designed to be used over broadcast local area networks (LANs), and are portable to a number of them. The functionality provided yields a reasonably complete solution to the problem of reliable group communication. While other protocols offer similar services, the authors follow a novel engineering approach by deriving all qualities of services from a single basic procedure. Thus, their implementation shares data structures, procedures, failure-recovery algorithms, and group monitor services, resulting in a highly integrated package.>

The authors discuss the definition and design of a generic reliable communication architecture on a widely used host-independent platform, such as a local area network (LAN). Two relevant aspects are the use of nonreplicated LANs and self-checking components. The protocol is innovative, in the sense that, although clockless and running on a nonreplicated network, it displays bounded execution times. Thus the architecture is capable of reliably addressing realtime. Support of high-performance real-time applications with this architecture is being seriously considered in the present phase of project Delta-4, a CED Esprit II consortium designing an open, dependable distributed architecture. The authors' considerations regarding synchronism properties of clockless protocols are being applied in this context.>

This paper deals with the problem of reliable group communication for distributed applications, in the context of the Reliable Broadcast class of protocols. An atomic multicast protocol for token passing Lans is presented. The actual implementation is on an 8802/4 Token-bus, although it is applicable to 8802/5 Token-rings and the FDDI Fibre-Optic network.

The author presents a study of a redundant media implementation for an ISO 8802/4 token-bus local area network (LAN), consistent with the standard recommendations. The redundant media IEEE-802.4G-compatible interface is intended to provide high availability of network access in the presence of medium omission and stopping faults. A set of management rules and fault treatment operations is defined, together with lookahead medium failure detection, to limit overall omission degree to that of a single medium, and avoid unavailability because of medium failure. It is concluded that the proposed mechanism is completely general, and may be applied to plain 8802/4 LANs, i.e. Manufacturing Automation Protocol networks.>