Intent-based networking (IBN) promises to simplify the network management and automated orchestration of high-level policies in future networking architectures such as software-defined networking (SDN). However, such abstraction and automation creates new network visibility challenges. Existing SDN network forensics and diagnostics tools operate at a lower level of network abstraction, which makes intent-level reasoning difficult. We present PRovINTENT, a framework extension for SDN control plane tools that accounts for intent semantics. PRovINTENT records the provenance and evolution of intents as the network's state and apps' requests change over time and enables reasoning at multiple abstractions. We define an intent provenance model, we implement a proof-of-concept tool, and we evaluate the efficacy of PRovINTENT'S explanatory capabilities by using a representative intent-driven network application.

Many real-world attacks on cyber-physical systems involve physical intrusions that directly cause damage or facilitate cyber attacks. Hence, in this work, we investigate the security risk of organizations with respect to different adversarial models of physical movement behavior. We study the case in which an intrusion detection mechanism is in place to alert the system administrator when users deviate from their normal movement behavior. We then analyze how different user behaviors may present themselves as different levels of threats in terms of their normal movement behavior within a given building topology. To quantify the differences in movement behavior, we define a WeightTopo metric that takes into account the building topology in addition to the movement pattern. We demonstrate our approach on a railway system case study and show how certain user roles, when abused by attackers, are especially vulnerable in terms of the physical intrusion detection probability. We also evaluate quantitatively how the similarity between an attacker’s movement behavior and a user’s movement behavior affects the detection probability of the evaluated intrusion detection system. Certain individual users are found to pose a higher threat, implying the need for customized monitoring.

In this paper, we address the challenges facing the adoption of client puzzles as a means to protect the TCP connection establishment channel from state exhaustion DDoS attacks. We model the problem of selecting the puzzle difficulties as a Stackelberg game with the server as the leader and the clients as the followers and obtain the equilibrium solution for the puzzle difficulty. We then present an implementation of client puzzles inside the TCP stack of the Linux 4.13.0 kernel. We evaluate the performance of our implementation and the obtained solution against a range of attacks through reproducible experiments on the DETER testbed. Our results show that client puzzles are effective at boosting the tolerance of the TCP handshake channel to state exhaustion DDoS attacks by rate limiting malicious attackers while allocating resources for legitimate clients.

The rise of intent-based networking (IBN) allows enterprises to use software-defined networking (SDN) architectures to specify what network requirements are needed rather than specify how such requirements will be implemented. For enterprises that process personal data, those network requirements must necessarily consider data protection by design to comply with new regulations such as the European Union's GDPR. We argue that the centralized data plane view of SDN architectures and the network intent abstractions of IBN can aid in the design of systems that require data protection. We propose a data protection intent framework that leverages SDN and network intents. We use the GDPR as a representative data protection framework and identify the applicable regulatory requirements for system and network design. Based on those requirements, we design an SDN-based architecture for data protection intents that allows data services to request network resources by using data protection abstractions. We implement a proof-of-concept network application for the ONOS SDN controller and explain how our framework can be useful in a representative data breach case study to aid in responding to regulator requests.

Software-defined networking (SDN) continues to grow in popularity because of its programmable and extensible control plane realized through network applications (apps). However, apps introduce significant security challenges that can systemically disrupt network operations, since apps must access or modify data in a shared control plane state. If our understanding of how such data propagate within the control plane is inadequate, apps can co-opt other apps, causing them to poison the control plane's integrity. We present a class of SDN control plane integrity attacks that we call cross-app poisoning (CAP), in which an unprivileged app manipulates the shared control plane state to trick a privileged app into taking actions on its behalf. We demonstrate how role-based access control (RBAC) schemes are insufficient for preventing such attacks because they neither track information flow nor enforce information flow control (IFC). We also present a defense, ProvSDN, that uses data provenance to track information flow and serves as an online reference monitor to prevent CAP attacks. We implement ProvSDN on the ONOS SDN controller and demonstrate that information flow can be tracked with low-latency overheads.

We propose POWERALERT, an efficient external integrity checker for untrusted hosts. Current attestation systems suffer from shortcomings, including requiring a complete checksum of the code segment, from being static, use of timing information sourced from the untrusted machine, or using imprecise timing information such as network round-trip time. We address those shortcomings by (1) using power measurements from the host to ensure that the checking code is executed and (2) checking a subset of the kernel space over an extended period. We compare the power measurement against a learned power model of the execution of the machine and validate that the execution was not tampered. Finally, POWERALERT randomizes the integrity checking program to prevent the attacker from adapting. We model the interaction between POWERALERT and an attacker as a time-continuous game. The Nash equilibrium strategy of the game shows that POWERALERT has two optimal strategy choices: (1) aggressive checking that forces the attacker into hiding, or (2) slow checking that minimizes cost. We implement a prototype of POWERALERT using Raspberry Pi and evaluate the performance of the integrity checking program generation.

As safety-critical systems become increasingly interconnected, a system's operations depend on the reliability and security of the computing components and the interconnections among them. Therefore, a growing body of research seeks to tie safety analysis to security analysis. Specifically, it is important to analyze system safety under different attacker models. In this paper, we develop generic parameterizable state automaton templates to model the effects of an attack. Then, given an attacker model, we generate a state automaton that represents the system operation under the threat of the attacker model. We use a railway signaling system as our case study and consider threats to the communication protocol and the commands issued to physical devices. Our results show that while less skilled attackers are not able to violate system safety, more dedicated and skilled attackers can affect system safety. We also consider several countermeasures and show how well they can deter attacks.

Wireless sensor networks (WSNs) should collect accurate readings to reliably capture an environment's state. However, readings may become erroneous because of sensor hardware failures or degradation. In remote deployments, centrally detecting those reading errors can result in many message transmissions, which in turn dramatically decreases sensor battery life. In this paper, we address this issue through three main contributions. First, we propose REMAX, a peer-to-peer (P2P) error detection protocol that extends the WSN's life by minimizing message transmissions. Second, we propose a low-overhead error detection approach that helps minimize communication complexity. Third, we evaluate our approach via a trace-driven, discrete-event simulator, using two datasets from real WSN deployments that measure indoor air temperature and seismic wave amplitude. Our results show that REMAX can accurately detect errors and extend the WSN's reachability (effective lifetime) compared to the centralized approach.

Software-defined networking (SDN) has recently attracted interest as a way to provide cyber resiliency because of its programmable and logically centralized nature. However, the security of the SDN architecture itself against malicious attacks is not well understood and must be ensured in order to provide cyber resiliency to systems that use SDNs. In this paper, we present ATTAIN, an attack injection framework for OpenFlow-based SDN architectures. First, we define an attack model that relates system components to an attacker's capability to influence control plane behavior. Second, we define an attack language for writing control plane attacks that can be used to evaluate SDN implementations. Third, we describe an attack injector architecture that actuates attacks in networks. Finally, we evaluate our framework with an enterprise network case study by writing and running attacks with popular SDN controllers.

Intrusion resilience is a protection strategy aimed at building systems that can continue to provide service during attacks. One approach to intrusion resilience is to continuously monitor a system's state and change its configuration to maintain service even while attacks are occurring. Intrusion detection, through both anomaly detection (for unknown attacks) and signature detection (for known attacks) is thus a crucial part of that resilience strategy. In this paper, we introduce KOBRA, an online anomaly detection engine that learns behavioral baselines for applications. KOBRA is implemented as a set of cooperative kernel modules that collects time-stamped process events. The process events are converted to a discrete-time signal in the polar space. We learn local patterns that occur in the data and then learn the normal co-occurrence relationships between the patterns. The patterns and the co-occurrence relations model the normal behavioral baseline of an application. We compute an anomaly score for tested traces and compare it against a threshold for anomaly detection. We evaluate the baseline by experimenting with its ability to discriminate between different processes and detect malicious behavior.

Given the growing sophistication of cyber attacks, designing a perfectly secure system is not generally possible. Quantitative security metrics are thus needed to measure and compare the relative security of proposed security designs and policies. Since the investigation of security breaches has shown a strong impact of human errors, ignoring the human user in computing these metrics can lead to misleading results. Despite this, and although security researchers have long observed the impact of human behavior on system security, few improvements have been made in designing systems that are resilient to the uncertainties in how humans interact with a cyber system. In this work, we develop an approach for including models of user behavior, emanating from the fields of social sciences and psychology, in the modeling of systems intended to be secure. We then illustrate how one of these models, namely general deterrence theory, can be used to study the effectiveness of the password security requirements policy and the frequency of security audits in a typical organization. Finally, we discuss the many challenges that arise when adopting such a modeling approach, and then present our recommendations for future work.

The components and systems involved in railway operation are subject to stringent reliability and safety requirements, but up until now the cyber security of those same systems has been largely under-explored. In this work, we examine a widely-used railway technology, track beacons or balises, which provide a train with its position on the track and often assist with accurate stopping at stations. Balises have been identified as one potential weak link in train signalling systems. We evaluate an automatic train stop controller that is used in real deployment and show that attackers who can compromise the availability or integrity of the balises' data can cause the trains to stop dozens of meters away from the right position, disrupting train service. To address this risk, we have developed a novel countermeasure that ensures the correct stopping of the trains in the presence of attacks, with only a small extra stopping delay.

Lateral movement-based attacks are increasingly leading to compromises in large private and government networks, often resulting in information exfiltration or service disruption. Such attacks are often slow and stealthy and usually evade existing security products. To enable effective detection of such attacks, we present a new approach based on graph-based modeling of the security state of the target system and correlation of diverse indicators of anomalous host behavior. We believe that irrespective of the specific attack vectors used, attackers typically establish a command and control channel to operate, and move in the target system to escalate their privileges and reach sensitive areas. Accordingly, we identify important features of command and control and lateral movement activities and extract them from internal and external communication traffic. Driven by the analysis of the features, we propose the use of multiple anomaly detection techniques to identify compromised hosts. These methods include Principal Component Analysis, k-means clustering, and Median Absolute Deviation-based outlier detection. We evaluate the accuracy of identifying compromised hosts by using injected attack traffic in a real enterprise network dataset, for various attack communication models. Our results show that the proposed approach can detect infected hosts with high accuracy and a low false positive rate.

Electricity theft is a major concern for utilities all over the world, and leads to billions of dollars in losses every year. Although improving the communication capabilities between consumer smart meters and utilities can enable many smart grid features, these communications can be compromised in ways that allow an attacker to steal electricity. Such attacks have recently begun to occur, so there is a real and urgent need for a framework to defend against them. In this paper, we make three major contributions. First, we develop what is, to our knowledge, the most comprehensive classification of electricity theft attacks in the literature. These attacks are classified based on whether they can circumvent security measures currently used in industry, and whether they are possible under different electricity pricing schemes. Second, we propose a theft detector based on Kullback-Leibler (KL) divergence to detect cleverly-crafted electricity theft attacks that circumvent detectors proposed in related work. Finally, we evaluate our detector using false data injections based on real smart meter data. For the different attack classes, we show that our detector dramatically mitigates electricity theft in comparison to detectors in prior work.

Intrusion detection and forensic analysis techniques depend upon monitors to collect information about possible attacks. Since monitoring can be expensive, however, monitors must be selectively deployed to maximize their overall utility. This paper introduces a methodology both to evaluate monitor deployments quantitatively in terms of security goals and to deploy monitors optimally based on cost constraints. First, we define a model that describes the system assets, deployable monitors, and the relationship between generated data and intrusions. Then, we define a set of metrics that quantify the utility and richness of monitor data with respect to intrusion detection and the cost associated with deployment. Finally, we formulate a method using our model and metrics to determine the cost-optimal, maximum-utility placement of monitors. We present an enterprise Web service use case and illustrate how our metrics can be used to determine optimal monitor deployments for a set of common attacks on Web servers. Our approach is scalable, being able to compute within minutes optimal monitor deployments for systems with hundreds of monitors and attacks.

Attackers often attempt to move laterally from host to host, infecting them until an overall goal is achieved. One possible defense against this strategy is to detect such coordinated and sequential actions by fusing data from multiple sources. In this paper, we propose a framework for distributed data fusion that specifies the communication architecture and data transformation functions. Then, we use this framework to specify an approach for lateral movement detection that uses host-level process communication graphs to infer network connection causations. The connection causations are then aggregated into system-wide host-communication graphs that expose possible lateral movement in the system. In order to provide a balance between the resource usage and the robustness of the fusion architecture, we propose a multilevel fusion hierarchy that uses different clustering techniques. We evaluate the scalability of the hierarchical fusion scheme in terms of storage overhead, number of message updates sent, fairness of resource sharing among clusters, and quality of local graphs. Finally, we implement a host-level monitor prototype to collect connection causations, and evaluate its overhead. The results show that our approach provides an effective method to detect lateral movement between hosts, and can be implemented with acceptable overhead.

Maintaining the resilience of a large-scale system requires an accurate view of the system's cyber and physical state. The ability to collect, organize, and analyze state central to a system's operation is thus important in today's environment, in which the number and sophistication of security attacks are increasing. Although a variety of "sensors" (e.g., Intrusion Detection Systems, log files, and physical sensors) are available to collect system state information, it's difficult for administrators to maintain and analyze the diversity of information needed to understand a system's security state. Therefore, we have developed the Cyber-Physical Topology Language (CPTL) to represent and reason about system security. CPTL combines ideas from graph theory and formal logics, and provides a framework to capture relationships among the diverse types of sensor information. In this paper, we formally define CPTL as well as operations on CPTL models that can be used to infer a system's security state. We then illustrate the use of CPTL in both the enterprise and electrical power domains and provide experimental results that illustrate the practicality of the approach.

The transformation of traditional power systems to smart grids brings significant benefits, but also exposes the grids to various cyber threats. The recent effort led by US National Electric Sector Cybersecurity Organization Resource (NESCOR) Technical Working Group 1 to compile failure scenarios is an important initiative to document typical cybersecurity threats to smart grids. While these scenarios are an invaluable thought-aid, companies still face challenges in systematically and efficiently applying the failure scenarios to assess security risks for their specific infrastructure. In this work, we develop a model-based process for assessing the security risks from NESCOR failure scenarios. We extend our cybersecurity assessment tool, Cyber-SAGE, to support this process, and use it to analyze 25 failure scenarios. Our results show that CyberSAGE can generate precise and structured security argument graphs to quantitatively reason about the risk of each failure scenario. Further, CyberSAGE can significantly reduce the assessment effort by allowing the reuse of models across different failure scenarios, systems, and attacker profiles to perform "what if?" analysis.

It is critical to monitor IT systems that are part of energy delivery system infrastructure. The problem with intrusion detection systems (IDSes) is that they often produce thousands of alerts daily that must be dealt with by administrators manually. To provide situational awareness, detection systems usually employ (alert, priority) mappings that are either built in the IDS without consideration of the high-level mission objectives of the infrastructure, or manually defined by administrators through a time-consuming task that requires deep system-level expertise. In this paper, we present Seclius, an online security evaluation framework that translates low-level IDS alerts into a high-level system security measure and provides a ranking of past malicious events and affected system assets based on how crucial they are for the organization. Seclius significantly reduces human involvement by automatically learning system characteristics, providing a simple formalism that administrators can use to define security requirements. Experiments on a process control network with real vulnerabilities and a multistep attack show that Seclius can accurately report system security with low performance overhead and support the time-constrained security decision-making process that is necessary for critical infrastructure.

The University of Illinois at Urbana Champaign (Illinois), Pacific Northwest National Labs (PNNL), and the University of Southern California Information Sciences Institute (USC-ISI) consortium is working toward providing tools and expertise to enable collaborative research to improve security and resiliency of cyber physical systems. In this extended abstract we discuss the challenges and the solution space. We demonstrate the feasibility of some of the proposed components through a wide-area situational awareness experiment for the power grid across the three sites.

Graph-based assessment formalisms have proven to be useful in the safety, dependability, and security communities to help stakeholders manage risk and maintain appropriate documentation throughout the system lifecycle. In this paper, we propose a set of methods to automatically construct security argument graphs, a graphical formalism that integrates various security-related information to argue about the security level of a system. Our approach is to generate the graph in a progressive manner by exploiting logical relationships among pieces of diverse input information. Using those emergent argument patterns as a starting point, we define a set of extension templates that can be applied iteratively to grow a security argument graph. Using a scenario from the electric power sector, we demonstrate the graph generation process and highlight its application for system security evaluation in our prototype software tool, Cyber SAGE.

Preserving the availability and integrity of networked computing systems in the face of fast-spreading intrusions requires advances not only in detection algorithms, but also in automated response techniques. In this paper, we propose a new approach to automated response called the response and recovery engine (RRE). Our engine employs a game-theoretic response strategy against adversaries modeled as opponents in a two-player Stackelberg stochastic game. The RRE applies attack-response trees (ART) to analyze undesired system-level security events within host computers and their countermeasures using Boolean logic to combine lower level attack consequences. In addition, the RRE accounts for uncertainties in intrusion detection alert notifications. The RRE then chooses optimal response actions by solving a partially observable competitive Markov decision process that is automatically derived from attack-response trees. To support network-level multiobjective response selection and consider possibly conflicting network security properties, we employ fuzzy logic theory to calculate the network-level security metric values, i.e., security levels of the system's current and potentially future states in each stage of the game. In particular, inputs to the network-level game-theoretic response selection engine, are first fed into the fuzzy system that is in charge of a nonlinear inference and quantitative ranking of the possible actions using its previously defined fuzzy rule set. Consequently, the optimal network-level response actions are chosen through a game-theoretic optimization process. Experimental results show that the RRE, using Snort's alerts, can protect large networks for which attack-response trees have more than 500 nodes.

The ADversary VIew Security Evaluation (ADVISE) model formalism provides a system security model from the perspective of an adversary. An ADVISE atomic model consists of an attack execution graph (AEG) composed of attack steps, system state variables, and attack goals, as well as an adversary profile that defines the abilities and interests of a particular adversary. The ADVISE formalism has been implemented as a Möbius atomic model formalism in order to leverage the existing set of mature modeling formalisms and solution techniques offered by Möbius. This tool paper explains the ADVISE implementation in Möbius and provides technical details for Möbius users who want to use ADVISE either alone or in combination with other modeling formalisms provided by Möbius.

Organizations of all sizes are shifting their IT infrastructures to the cloud because of its cost efficiency and convenience. Because of the on-demand nature of the Infrastructure as a Service (IaaS) clouds, hundreds of thousands of virtual machines (VMs) may be deployed and terminated in a single large cloud data center each day. In this paper, we propose a content-based scheduling algorithm for the placement of VMs in data centers. We take advantage of the fact that it is possible to find identical disk blocks in different VM disk images with similar operating systems by scheduling VMs with high content similarity on the same hosts. That allows us to reduce the amount of data transferred when deploying a VM on a destination host. In this paper, we first present our study of content similarity between different VMs, based on a large set of VMs with different operating systems that represent the majority of popular operating systems in use today. Our analysis shows that content similarity between VMs with the same operating system and close version numbers (e.g., Ubuntu 12.04 vs. Ubuntu 11.10) can be as high as 60%. We also show that there is close to zero content similarity between VMs with different operating systems. Second, based on the above results, we designed a content-based scheduling algorithm that lowers the network traffic associated with transfer of VM disk images inside data centers. Our experimental results show that the amount of data transfer associated with deployment of VMs and transfer of virtual disk images can be lowered by more than 70%, resulting in significant savings in data center network utilization and congestion.

In this paper we advocate the use of workflow---describing how a system provides its intended functionality---as a pillar of cybersecurity analysis and propose a holistic workflow-oriented assessment framework. While workflow models are currently used in the area of performance and reliability assessment, these approaches are designed neither to assess a system in the presence of an active attacker, nor to assess security aspects such as confidentiality. On the other hand, existing security assessment methods typically focus on modeling the active attacker (e.g., attack graphs), but many rely on restrictive models that are not readily applicable to complex (e.g., cyber-physical or cyber-human) systems.

In this paper we present a framework for analyzing the fault tolerance of deduplicated storage systems. We discuss methods for building models of deduplicated storage systems by analyzing empirical data on a file category basis. We provide an algorithm for generating component-based models from this information and a specification of the storage system architecture. Given the complex nature of detailed models of deduplicated storage systems, finding a solution using traditional discrete event simulation or numerical solvers can be difficult. We introduce an algorithm which allows for a more efficient solution by exploiting the underlying structure of dependencies to decompose the model of the storage system. We present a case study of our framework for a real system.We analyze a production deduplicated storage system and propose extensions which improve fault tolerance while maintaining high storage efficiency.

Whether it happens through malware or through phishing, loss of one's online identity is a real and present danger. While many attackers seek credentials to realize financial gain, an analysis of the compromised accounts at our own institutions reveals that perpetrators often steal university credentials to gain free and unfettered access to information. This nontraditional motivation for credential theft puts a special burden on the academic institutions that provide these accounts. In this paper, we describe the design, implementation, and evaluation of a system for safeguarding academic accounts and resources called the University Credential Abuse Auditing System (UCAAS). We evaluate UCAAS at two major research universities with tens of thousands of user accounts and millions of login events during a two-week period. We show the UCAAS to be useful in reducing this burden, having helped the university security teams identify a total of 125 compromised accounts with zero false positives during the trail.

Summary form only given, as follows. The vision for a modernized "Smart Grid" involves the use of an advanced computing, communication and control cyber infrastructure for enhancing current grid operations by enabling timely interactions among a range of entities. The coupling between the power grid and its cyber infrastructure is inherent, and the extent to which the Smart Grid vision can be achieved depends upon the trustworthiness of its cyber infrastructure. This talk describes challenges in assuring the trustworthiness (performance, dependability, and security) of the emerging smart grid, using example of research underway at the DOEand HHS-funded Trustworthy Cyber Infrastructure for the Power Grid (TCIPG) Center. The goal of TCIPG is to provide trustworthiness in the nation's electric grid cyber infrastructure such that it continues to deliver electricity and maintain critical operations even in the presence of cyber attacks. Achieving this goal will involve the extension, integration, design, and development of IT technologies imbibed with key properties of realtime availability and security. This research area provides many opportunities for dependability analysts and engineers to apply and extend their work.

The vision for a modernized "Smart Grid" involves the use of an advanced computing, communication and control cyber infrastructure for enhancing current grid operations by enabling timely interactions among a range of entities. The coupling between the power grid and its cyber infrastructure is inherent, and the extent to which the Smart Grid vision can be achieved depends upon the trustworthiness of its cyber infrastructure.

It is critical to develop an effective way to monitor advanced metering infrastructures (AMI). To ensure the security and reliability of a modernized power grid, the current deployment of millions of smart meters requires the development of innovative situational awareness solutions to prevent compromised devices from impacting the stability of the grid and the reliability of the energy distribution infrastructure. To address this issue, we introduce a specification-based intrusion detection sensor that can be deployed in the field to identify security threats in real time. This sensor monitors the traffic among meters and access points at the network, transport, and application layers to ensure that devices are running in a secure state and their operations respect a specified security policy. It does this by implementing a set of constraints on transmissions made using the C12.22 standard protocol that ensure that all violations of the specified security policy will be detected. The soundness of these constraints was verified using a formal framework, and a prototype implementation of the sensor was evaluated with realistic AMI network traffic.

Modern storage systems are employing data deduplication with increasing frequency. Often the storage systems on which these techniques are deployed contain important data, and utilize fault-tolerant hardware and software to improve the reliability of the system and reduce data loss. We suggest that data deduplication introduces inter-file relationships that may have a negative impact on the fault tolerance of such systems by creating dependencies that can increase the severity of data loss events. We present a framework composed of data analysis methods and a model of data deduplication that is useful in studying the reliability impact of data deduplication. The framework is useful for determining a deduplication strategy that is estimated to satisfy a set of reliability constraints supplied by a user.

Automatic system monitoring and recovery has the potential to provide effective, low-cost ways to improve dependability in distributed software systems. However, automating recovery is challenging in practice because accurate fault diagnosis is hampered by monitoring tools and techniques that often have low fault coverage, poor fault localization, detection delays, and false positives. In this paper, we present a holistic model-based approach that overcomes these challenges and enables automatic recovery in distributed systems. To do so, it uses theoretically sound techniques including Bayesian estimation and Markov decision theory to provide controllers that choose good, if not optimal, recovery actions according to a user-defined optimization criteria. By combining monitoring and recovery, the approach realizes benefits that could not have been obtained by using them in isolation. We experimentally validate our framework by fault injection on realistic e-commerce systems.

Managing geographically dispersed deployments of complex multitier applications involves dealing with the substantial effects of network latency. However, the effects of network latency on an application's end-to-end performance can be far from obvious, thus making it difficult to predict the true impact of infrastructure changes such as network upgrades or server relocation on the users of an application. In this paper, we propose a new metric to quantify this impact called the link gradient. We develop a novel noise-resistant, nonintrusive technique to measure the link gradients in running systems without requiring knowledge of the system structure by using a combination of run-time delay injection and spectral analysis. We evaluate the intrusiveness and accuracy of our approach using micro-benchmarks and a deployment of two benchmark multitier Web applications on PlanetLab. Using these results, we show that link gradients can be used to accurately predict the impact of network latency changes on the end-to-end responsiveness of individual application transactions, even in new application configurations and without requiring a dedicated test environment.

An important approach for software dependability is the use of diversity to detect and/or tolerate errors. We develop and evaluate an approach for automated program diversity called Diverse Partial Memory Replication (DPMR), aimed at detecting memory safety errors. DPMR is an automatic compiler transformation that replicates some subset of an executable's data memory and applies one or more diversity transformations to the replica. DPMR can detect any kind of memory safety errors in any part of a program's data memory. Moreover, DPMR is novel because it uses partial replication within a single address space, replicating (and comparing) only a subset of a program's memory. We also perform a detailed study of the diversity mechanisms and state comparison policies in DPMR (a first of its kind for such diversity approaches), which is valuable for exploiting the high flexibility of DPMR.

Swarm systems, which typically comprise a large number of lightweight mobile components, must be capable of self-healing. In this paper, we propose a self-organizing, self-healing framework called “superimposed” clustering for such systems. The framework makes a significant departure from traditional clustering algorithms that apply a single policy to form clusters through iterations. Specifically, our superimposed clustering protocol (SCP) selects a pair of diversified clustering polices to simultaneously build two sets of clusters, which we view as two cluster layers with one on top of the other. Via redundancy shadowing, SCP is able to extract and combine the complementary portions of the two layers to form a clustered network such that the vast majority of nodes can be organized through a single round. Moreover, SCP exploits shadow redundancy to enable gracefully degradable clustering coverage to mitigate cluster damage caused by node failure, death, or migration. We present the notion of superimposed clustering by devising a protocol and conducting a performability evaluation.

The costs of data loss and unavailability can be large, so businesses use many data protection techniques such as remote mirroring, snapshots, and backups to guard against failures. Choosing an appropriate combination of techniques is difficult because there are numerous approaches for protecting data and allocating resources. Storage system architects typically use ad hoc techniques, often resulting in overengineered expensive solutions or underprovisioned inadequate ones. In contrast, this paper presents a principled automated approach for designing dependable storage solutions for multiple applications in shared environments. Our contributions include search heuristics for intelligent exploration of the large design space and modeling techniques for capturing interactions between applications during recovery. Using realistic storage system requirements, we show that our design tool produces designs that cost up to two times less in initial outlays and expected data penalties than the designs produced by an emulated human design process. Additionally, we compare our design tool to a random search heuristic and a genetic algorithm metaheuristic, and show that our approach consistently produces better designs for the cases we have studied. Finally, we study the sensitivity of our design tool to several input parameters.

Mobius 2.3 is an extensible dependability, security, and performance modeling environment for large-scale discrete-event systems. It provides multiple model formalisms and solution techniques, facilitating the representation of each part of a system in the formalism that is most appropriate for it, and the application of the solution method or methods best-suited to estimating the system's behavior. Since its initial release in 2001, many advances have been made in Moumlbius's design and implementation that have strengthened its place in the modeling and analysis community. With almost a decade of widespread academic and industrial use, Moumlbius has proven itself to be useful in a wide variety of modeling situations. This paper documents the current feature set of Mobius 2.3, emphasizing recent significant enhancements.

Preserving the availability and integrity of networked computing systems in the face of fast-spreading intrusions requires advances not only in detection algorithms, but also in automated response techniques. In this paper, we propose a new approach to automated response called the Response and Recovery Engine (RRE). Our engine employs a game-theoretic response strategy against adversaries modeled as opponents in a two-player Stackelberg stochastic game. RRE applies attack-response trees to analyze undesired security events and their countermeasures using Boolean logic to combine lower-level attack consequences. In addition, RRE accounts for uncertainties in intrusion detection alert notifications. RRE then chooses optimal response actions by solving a partially observable competitive Markov decision process that is automatically derived from attack-response trees. Experimental results show that RRE, using Snort's alerts, can protect large networks for which attack-response trees have more than 900 nodes.

Geographically dispersed deployments of large and complex multitier enterprise applications introduce many challenges, including those involved in predicting the impact of network latency on end-to-end transaction response times. Here, a measurement-based approach to quantifying this impact using a new metric called the link gradient is presented. A non-intrusive technique for measuring the link gradient in running systems using delay injection and spectral analysis is presented, along with experimental results on PlanetLab that demonstrate that the link gradient can be used to predict end-to-end responsiveness, even in new and untested application configurations.

Petascale computing requires I/O subsystems that can keep up with the dramatic computing power demanded by such systems. TOP500.org ranks top computers based on their peak compute performance, but there has not been adequate investigation of the current state-of-the-art and future requirements of storage area networks that support petascale computers. Dependable scaling of an I/O subsystem to support petascale computing is not as simple as adding more storage servers. In this paper, we present a stochastic activity network model that uses failure rates computed from real logs to predict the reliability and availability of the storage architecture of the Abe cluster at the National Center for Supercomputing Applications (NCSA). We then use the model to evaluate the challenges encountered as one scales the number of storage servers to support petascale computing. The results present new insights regarding the dependability challenges that will be encountered when building next-generation petabyte storage. Furthermore, we provide insight into a new design approach that will enable system designers to integrate the trace-based analysis of parameter values from real system data into their stochastic models to allow informed design choices.

Embedded systems for closed-loop applications often behave as discrete-time semi-Markov processes (DTSMPs). Performability measures most meaningful to iterative embedded systems, such as accumulated reward, are thus difficult to solve analytically in general. In this paper, we propose a recurrence-relation-based (RRB) reward model to evaluate such measures. A critical element in RRB reward models is the notion of state-entry probability. This notion enables us to utilize the embedded Markov chain in a DTSMP in a novel way. More specifically, we formulate state-entry probabilities, state-occupancy probabilities, and expressions concerning accumulated reward solely in terms of state-entry probability and its companion term, namely the expected accumulated reward at the point of state entry. As a result, recurrence relations abstract away all the intermediate points that lack the memoryless property, enabling a solvable model to be directly built upon the embedded Markov chain. To show the usefulness of RRB reward models, we evaluate an embedded system for which we leverage the proposed notion and methods to solve a variety of probabilistic measures analytically.

Abstract There are many group communication systems (GCSs) that provide consistent group membership and reliable, ordered multicast properties in the presence of crash faults. However, relatively few GCS implementations are able to provide these properties in the presence of malicious faults resulting from intrusions. We describe the systematic transformation of a crash‐tolerant GCS, namely C‐Ensemble, into an intrusion‐tolerant GCS, the ITUA GCS. To perform the transformation, we devised intrusion‐tolerant versions of key group communication protocols. We then inserted implementations of the protocols into C‐Ensemble and made significant changes to the rest of the C‐Ensemble protocol stack to make the stack intrusion tolerant. We quantify the cost of providing intrusion‐tolerant group communication in two ways. First, we quantify the implementation effort by presenting a detailed analysis of the amount of change required to the original C‐Ensemble system. In doing so, we provide insight into the choice of building an intrusion‐tolerant GCS from scratch versus building one by leveraging a crash‐tolerant implementation. Second, we quantify the run‐time performance cost of tolerating intrusions by presenting results from an experimental evaluation of the main intrusion‐tolerant microprotocols. The results are analyzed to identify the parts that contribute the most overhead while providing intrusion tolerance during both normal operation and recovery from intrusions. Copyright © 2007 John Wiley & Sons, Ltd.

Viruses that infect smartphones are emerging as a new front in the fight against computer viruses. In this paper, we model the propagation of mobile phone viruses in order to study their impact on the dependability of mobile phones. We propose response mechanisms and use the models to obtain insight on the effectiveness of these virus mitigation techniques. In particular, we consider the effects of multimedia messaging system (MMS) viruses that spread by sending infected messages to other phones. The virus model is implemented using the Mobius software tool and is highly parameterized, enabling representation of a wide range of potential MMS virus behavior. Using the model, we present the results of four illustrative MMS virus scenarios simulated with and without response mechanisms. By measuring the propagation rate and the extent of virus penetration in the simulation phone population, we quantitatively compare the effectiveness of mobile phone virus response mechanisms.

No abstract available.

UNLABELLED: Möbius has found numerous applications in computational biology to build and solve stochastic models of biological processes. It provides the user with a modeling workflow and several sophisticated features that are not available in the simulation tools commonly used by computational biologists. AVAILABILITY: Möbius is free for academic users. It can be downloaded from www.mobius.uiuc.edu

We propose a resource-efficient way to execute requests in Byzantine-fault-tolerant replication that is particularly well-suited for services in which request processing is resource-intensive. Previous efforts took a failure masking all-active approach of using all execution replicas to execute all requests; at least 2t + 1 execution replicas are needed to mask t Byzantine-faulty ones. We describe an asynchronous protocol that provides resource-efficient execution by combining failure masking with imperfect failure detection and checkpointing. Our protocol is parsimonious since it uses only t + 1 execution replicas, called the primary committee or PC, to execute the requests under normal conditions characterized by a stable network and no misbehavior by PC replicas; thus, a trustworthy reply can be obtained with the same latency, but with only about half of the overall resource use of the all-active approach. However, a request that exposes faults among the PC replicas causes the protocol to switch to a recovery mode, in which all 2t + 1 replicas execute the request and send their replies; then, after selecting a new PC, the protocol switches back to parsimonious execution. Such a request incurs a higher latency using our approach than the all-active approach, mainly because of fault detection latency. Practical observations point to the fact that failures and instability are the exception rather than the norm. That motivated our decision to optimize resource efficiency for the common case, even if it means paying a slightly higher performance cost during periods of instability

Dependable systems are usually designed with multiple instances of components or logical processes, and often possess symmetries that may be exploited in model-based evaluation. The problem of how best to exploit symmetry in models has received much attention from the modeling community, but no solution has garnered widespread support, primarily because each solution is limited in terms of either the types of symmetry that can be exploited, or the difficulty of translating from the system description to the model formalism. We propose a new method for detecting and exploiting model symmetry in which 1) models retain the structure of the system, and 2) all symmetry inherent in the structure of the model can be detected and exploited for the purposes of state-space reduction. Composed models are constructed from models through specification of connections between models that correspond to shared state fragments. The composed model is interpreted as an undirected graph, and results from group theory, and graph theory are used to develop procedures for automatically detecting, and exploiting all symmetries in the composed model. We discuss the necessary algorithms to detect and exploit model symmetry, and provide a proof that the theory generates an equivalent model. After a thorough analysis of the added complexity, a state-space generator which implements these algorithms within Mobius is then presented.

The costs of data loss and unavailability can be large, so businesses use many data protection techniques, such as remote mirroring, snapshots and backups, to guard against failures. Choosing an appropriate combination of techniques is difficult because there are numerous approaches for protecting data and allocating resources. Storage system designers typically use ad hoc techniques, often resulting in over-engineered, expensive solutions or under-provisioned, inadequate ones. In contrast, this paper presents a principled, automated approach for designing dependable storage solutions for multiple applications in shared environments. Our contributions include search heuristics for intelligently exploring the large design space and modeling techniques for capturing interactions between applications during recovery. Using realistic storage system requirements, we show that our design tool can produce designs that cost up to 3X less in initial outlays and expected data penalties than the designs produced by an emulated human design process

This paper presents our experience validating the flood tol- erance of two network interface card (NIC)-based embedded firewall solutions, the Embedded Firewall (EFW) and the Au- tonomic Distributed Firewall (ADF). Experiments were per- formed for both embedded firewall devices to determine their flood tolerance and performance characteristics. The results show that both are vulnerable to packet flood attacks on a 100 Mbps network. In certain configurations, we found that both embedded firewall devices can have a significant, negative impact on bandwidth and application performance. These re- sults imply first that, firewall rule-sets should be optimized for performance-sensitive applications, and second, that proper consideration must be given to attack risks and mitigations before either the EFW or ADF is deployed. Finally, we be- lieve that future embedded firewall implementations should be vetted in a manner similar to that presented in this paper. Our experience shows that when their limitations are properly considered, both the EFW and ADF can be safely deployed to enhance network security without undue risk.

This paper provides a technique, based on partially observable Markov decision processes (POMDPs), for building automatic recovery controllers to guide distributed system recovery in a way that provides provable assurances on the quality of the generated recovery actions even when the diagnostic information may be imprecise. Lower bounds on the cost of recovery are introduced and proved, and it is shown how the characteristics of the recovery process can be used to ensure that the lower bounds converge even on undiscounted models. The bounds used in an appropriate online controller provide it with provable termination properties. Simulation-based experimental results on a realistic e-commerce system demonstrate that the proposed bounds can be improved iteratively, and the resulting controller convincingly outperforms a controller that uses heuristics instead of bounds

Path-based techniques make the analysis of very large Markov models feasible by trading off high computational complexity for low space complexity. Often, a drawback in these techniques is that they have to evaluate many paths in order to compute reasonably tight bounds on the exact solutions of the models. In this paper, we present a path composition algorithm to speed up path evaluation significantly. It works by quickly composing subpaths that are precomputed locally at the component level. The algorithm is computationally efficient since individual subpaths are precomputed only once, and the results are reused many times in the computation of all composed paths. To the best of our knowledge, this work is the first to propose the idea of path composition for the analysis of Markov models. A practical implementation of the algorithm makes it feasible to solve even larger models, since it helps not only in evaluating more paths faster but also in computing long paths efficiently by composing them from short ones. In addition to presenting the algorithm, we demonstrate its application and evaluate its performance in computing the reliability and availability of a large distributed information service system in the presence of fault propagation and in computing the probabilities of buffer overflow and buffer flushing in a media multicast system with varying system configurations

Dependable systems are usually designed with multiple instances of components or logical processes, and often possess symmetries that may be exploited in model-based evaluation. The problem of how best to exploit symmetry in models has received much attention from the modeling community, but no solution has garnered widespread support, primarily because each solution is limited in terms of either the types of symmetry that can be exploited or the difficulty of translating from the system description to the model formalism. We propose a new method for detecting and exploiting model symmetry in which 1) models retain the structure of the system, and 2) all symmetry inherent in the structure of the model can be detected and exploited for the purposes of state-space reduction. Composed models are constructed from models through specification of connections between models that correspond to shared state fragments. The composed model is interpreted as an undirected graph, and results from group and graph theory are used to develop procedures for automatically detecting and exploiting all symmetries in the composed model. A state-space generator which implements these algorithms within Mobius is then presented

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

MOTIVATION: The stochastic kinetics of a well-mixed chemical system, governed by the chemical Master equation, can be simulated using the exact methods of Gillespie. However, these methods do not scale well as systems become more complex and larger models are built to include reactions with widely varying rates, since the computational burden of simulation increases with the number of reaction events. Continuous models may provide an approximate solution and are computationally less costly, but they fail to capture the stochastic behavior of small populations of macromolecules. RESULTS: In this article we present a hybrid simulation algorithm that dynamically partitions the system into subsets of continuous and discrete reactions, approximates the continuous reactions deterministically as a system of ordinary differential equations (ODE) and uses a Monte Carlo method for generating discrete reaction events according to a time-dependent propensity. Our approach to partitioning is improved such that we dynamically partition the system of reactions, based on a threshold relative to the distribution of propensities in the discrete subset. We have implemented the hybrid algorithm in an extensible framework, utilizing two rigorous ODE solvers to approximate the continuous reactions, and use an example model to illustrate the accuracy and potential speedup of the algorithm when compared with exact stochastic simulation. AVAILABILITY: Software and benchmark models used for this publication can be made available upon request from the authors.

Abstract Applications that are part of a mission‐critical information system need to maintain a usable level of key services through ongoing cyber‐attacks. In addition to the well‐publicized denial of service (DoS) attacks, these networked and distributed applications are increasingly threatened by sophisticated attacks that attempt to corrupt system components and violate service integrity. While various approaches have been explored to deal with DoS attacks, corruption‐inducing attacks remain largely unaddressed. We have developed a collection of mechanisms based on redundancy, Byzantine fault tolerance, and adaptive middleware that help distributed, object‐based applications tolerate corruption‐inducing attacks. In this paper, we present the ITUA architecture, which integrates these mechanisms in a framework for auto‐adaptive intrusion‐tolerant systems, and we describe our experience in using the technology to defend a critical application that is part of a larger avionics system as an example. We also motivate the adaptive responses that are key to intrusion tolerance, and explain the use of the ITUA architecture to support them in an architectural framework. Copyright © 2006 John Wiley & Sons, Ltd.

Continuous-time Markov chains (CTMCs) have been used successfully to model the dependability and performability of many systems. Matrix diagrams (MDs) are known to be a space-efficient, symbolic representation of large CTMCs. In this paper, we identify local conditions for exact and ordinary lumpings that allow us to lump MD representations of Markov models in a compositional manner. We propose a lumping algorithm for CTMCs that are represented as MDs that is based on partition refinement, is applied to each level of an MD directly, and results in an MD representation of the lumped CTMC. Our compositional lumping approach is complementary to other known model-level lumping approaches for matrix diagrams. The approach has been implemented, and we demonstrate its efficiency and benefits by evaluating an example model of a tandem multi-processor system with load balancing and failure and repair operations.

While inherent resource redundancies in distributed applications facilitate gracefully degradable services, methods to enhance their dependability may have subtle, yet significant, performance implications, especially when such applications are stateful in nature. In this paper, we present a performability-oriented framework that enables the realization of software rejuvenation in stateful distributed applications. The framework is constructed based on three building blocks, namely, a rejuvenation algorithm, a set of performability metrics, and a performability model. We demonstrate via model-based evaluation that this framework enables error-accumulation-prone distributed applications to deliver services at the best possible performance level, even in environments in which a system is highly vulnerable to failures.

Distributed checkpointing is an important concept in providing fault tolerance in distributed systems. In today's applications, e.g., grid and massively parallel applications, the imposed overhead of taking a distributed checkpoint using the known approaches can often outweigh its benefits due to coordination and other overhead from the processes. This paper presents an innovative approach for distributed checkpointing. In this approach, the checkpoints are obtained using offline analysis based on the application level. During execution, no coordination is required. After presenting the approach, the authors proved its safety and present a performance analysis of it using stochastic models

Simulation to obtain reliability and availability estimates has been widely used by system designers to evaluate and compare alternative choices before making design decisions. However, traditionally that approach worked only if significant computer resources were available or designers accepted a significant time delay between design iterations. In this paper, we present an alternative approach to compute measures of interest for a family of models that represent alternative design choices that is significantly more efficient than the traditional approach. The new approach combines the existing single-clock multiple-system simulation with adaptive uniformization. We achieve the speedup by simulating all the alternative configurations of the discrete-event model simultaneously while amortizing the cost of enabled event set management. That allows us to explore and evaluate multiple configuration settings of a discrete-event model at the same time, significantly increasing the number of alternative versions of the model that are explored in a given amount of time.

Automatic system monitoring and recovery has the potential to provide a low-cost solution for high availability. However, automating recovery is difficult in practice because of the challenge of accurate fault diagnosis in the presence of low coverage, poor localization ability, and false positives that are inherent in many widely used monitoring techniques. In this paper, we present a holistic model-based approach that overcomes these challenges and enables automatic recovery in distributed systems. To do so, it uses theoretically sound techniques including Bayesian estimation and Markov decision theory to provide controllers that choose good, if not optimal, recovery actions according to a user-defined optimization criteria. By combining monitoring and recovery, the approach realizes benefits that could not have been obtained by using them in isolation. In this paper, we present two recovery algorithms with complementary properties and trade-offs, and validate our algorithms (through simulation) by fault injection on a realistic e-commerce system.

The growing interest in ad hoc wireless network applications that are made of large and dense populations of lightweight system resources, calls for scalable approaches to fault tolerance. Moreover, the nature of these systems creates significant challenges for the development of failure detection services (FDSs), because their quality often depends heavily on reliable communication. In particular, ad hoc wireless networks are notoriously vulnerable to message loss, which precludes deterministic guarantees for the completeness and accuracy properties of FDSs. To meet the challenges, we propose an FDS based on the notion of clustering. Specifically, we use a cluster-based communication architecture to permit the FDS to be implemented in a distributed manner via intra-cluster heartbeat diffusion and to allow a failure report to be forwarded across clusters through the upper layer of the communication hierarchy. In doing so, we extensively exploit the message redundancy that is inherent in ad hoc wireless settings to mitigate the effects of message loss on the accuracy and completeness properties of failure detection. As shown by our mathematical analysis, the resulting FDS is able to provide satisfactory probabilistic guarantees for the desired properties.

Accomplishing the distributed snapshots problem in mobile systems is an important issue as well as in distributed systems. This work presents a distributed snapshots protocol for mobile computing systems. In addition, this protocol can be used for achieving an efficient checkpointing protocol in the mobile environment. Specifically, it is a robust adaptation of the classical distributed snapshots protocol, where the mobile hosts can still roam among the different cells within the mobile system. The main benefit of this work is to provide distributed snapshots for a mobile system without adding any restriction to the system, such as FIFO ordering among the application messages as required for a traditional distributed system.

Evaluation of computing system security requires knowledge of the vulnerabilities present in the system and of potential attacks against the system. Vulnerabilities can be classified based on their location as application vulnerabilities, network vulnerabilities, or host vulnerabilities. We describe Ferret, a new software tool for checking host vulnerabilities. Ferret helps system administrators by quickly finding vulnerabilities that are present on a host. It is designed and implemented in a modular way: a different plug-in module is used for each vulnerability checked, and each possible output format is specified by a plug-in module. As a result, Ferret is extensible, and can easily be kept up-to-date through addition of checks for new vulnerabilities as they are discovered; the modular approach also makes it easy to provide specific configurations of Ferret tailored to specific operating systems or use environments. Ferret is a freely available open-source software implemented in Perl.

An increasing number of computer systems are designed to be distributed across both local and wide-area networks, performing a multitude of critical information-sharing and computational tasks. Malicious attacks on such systems are a growing concern, where attackers typically seek to degrade quality of service by intrusions that exploit vulnerabilities in networks, operating systems, and application software. Accordingly, designers are seeking improved techniques for validating such systems with respect to specified survivability requirements. In this regard, we describe a model-based validation effort that was undertaken as part of a unified approach to validating a networked intrusion-tolerant information system. Model-based results were used to guide the system's design as well as to determine whether a given survivability requirement was satisfied.

The development of techniques for quantitative, model-based evaluation of computer system dependability has a long and rich history. A wide array of model-based evaluation techniques is now available, ranging from combinatorial methods, which are useful for quick, rough-cut analyses, to state-based methods, such as Markov reward models, and detailed, discrete-event simulation. The use of quantitative techniques for security evaluation is much less common, and has typically taken the form of formal analysis of small parts of an overall design, or experimental red team-based approaches. Alone, neither of these approaches is fully satisfactory, and we argue that there is much to be gained through the development of a sound model-based methodology for quantifying the security one can expect from a particular design. In this work, we survey existing model-based techniques for evaluating system dependability, and summarize how they are now being extended to evaluate system security. We find that many techniques from dependability evaluation can be applied in the security domain, but that significant challenges remain, largely due to fundamental differences between the accidental nature of the faults commonly assumed in dependability evaluation, and the intentional, human nature of cyber attacks.

Validation of the dependability of distributed systems via fault injection is gaining importance because distributed systems are being increasingly used in environments with high dependability requirements. The fact that distributed systems can fail in subtle ways that depend on the state of multiple parts of the system suggests that a global-state-based fault injection mechanism should be used to validate them. However, global-state-based fault injection is challenging since it is very difficult in practice to maintain the global state of a distributed system at runtime with minimal intrusion into the system execution. We present Loki, a global-state-based fault injector, which has been designed with the goals of low intrusion, high precision, and high flexibility. Loki achieves these goals by utilizing the ideas of partial view of global state, optimistic synchronization, and offline analysis. In Loki, faults are injected based on a partial, view of the global state of the system, and a post-runtime analysis is performed to place events and injections into a single global timeline and to discard experiments with incorrect fault injections. Finally, the experiments with correct fault injections are used to estimate user-specified performance and dependability measures. A flexible measure language has been designed that facilitates the specification of a wide range of measures.

We present in this paper an extension of the message-driven confidence-driven framework that we developed for onboard guarded software upgrading. The purpose of this work is to provide the framework with the capability of protecting distributed software upgrades that involve message-passing interface changes. To achieve this goal, we propose an approach to clustering the components involved in software upgrades and those involved in message-passing interface changes, such that from outside the cluster all those components can be perceived collectively as one virtual low-confidence component. Moreover, we develop a confidence-driven mechanism that enables combined use of sender- and receiver-side message logging for efficient, fine-grained error containment and recovery. The paper provides a detailed algorithm description.

Functional Interface (AFI). Models and solution techniques interact with one another through the use of the standard interface, allowing them to interact with M OBIUS framework components, not formalism components. This permits novel combinations of modeling techniques. The AFI uses abstract classes to implement the framework components. The most basic model in the M OBIUS framework is an atomic model, and is made up of state variables that hold information about the state of a model and actions that are used for changing model state. Stochastic activity networks (SANs) and the stochastic process algebra PEPA are example atomic models that have been successfully implemented in the M OBIUS tool.

As computer systems become more complex and more widely distributed, it is becoming increasingly difficult to remove all vulnerabilities that can potentially be exploited by intruders. Intrusion tolerance is an emerging approach that aims to enable systems to continue functioning in spite of successful intrusions. Before intrusion tolerance is accepted as an approach to security, there must be quantitative techniques to measure its efficacy. However, there have been very few attempts at quantitative validation of intrusion-tolerant systems or, for that matter, of security in general. In this paper, we show that probabilistic validation through stochastic modeling is an attractive mechanism for evaluating intrusion tolerance. We demonstrate our approach by using stochastic activity networks to quantitatively validate an intrusion-tolerant replication management system. We characterize the intrusion tolerance provided by the system through several measures defined on the model, and study variations in these measures in response to changes in system parameters to evaluate the relative merits of various design choices.

Systems that are formed by massively distributed mobile resources, such as satellite constellations, often provide mission-critical functions. However, many existing fault tolerance schemes and quality-of-service (QoS) management concepts cannot be applied to those systems in a traditional way, due to the dynamically and continuously changing readiness-to-serve of their mobile resources. In this paper, we describe a case study that investigates a method called opportunity-adaptive QoS enhancement (QAQ).

Experimental evaluation is an important way to assess distributed systems, and fault injection is the dominant technique in this area for the evaluation of a system's dependability. For distributed systems, network failure is an important fault model. Physical network failures often have far-reaching effects, giving rise to multiple correlated failures as seen by higher-level protocols. This paper presents an experimental evaluation, using the Loki fault injector, which provides insight into the impact that correlated network partitions have on the Coda distributed file system. In this evaluation, Loki created a network partition between two Coda file servers, during which updates were made at each server to the same replicated data volume. Upon repair of the partition, a client requested directory resolution to converge the diverging replicas. At various stages of the resolution, Loki invoked a second correlated network partition, thus allowing us to evaluate its impact on the system's correctness, performance, and availability.

Building dependable distributed systems from commercial off-the-shelf components is of growing practical importance. For both cost and production reasons, there is interest in approaches and architectures that facilitate building such systems. The AQuA architecture is one such approach; its goal is to provide adaptive fault tolerance to CORBA applications by replicating objects. The AQuA architecture allows application programmers to request desired levels of dependability during applications' runtimes. It provides fault tolerance mechanisms to ensure that a CORBA client can always obtain reliable services, even if the CORBA server object that provides the desired services suffers from crash failures and value faults. AQuA includes a replicated dependability manager that provides dependability management by configuring the system in response to applications' requests and changes in system resources due to faults. It uses Maestro/Ensemble to provide group communication services. It contains a gateway to intercept standard CORBA IIOP messages to allow any standard CORBA application to use AQuA. It provides different types of replication schemes to forward messages reliably to the remote replicated objects. All of the replication schemes ensure strong, data consistency among replicas. This paper describes the AQuA architecture and presents, in detail, the active replication pass-first scheme. In addition, the interface to the dependability manager and the design of the dependability manager replication are also described. Finally, we describe performance measurements that were conducted for the active replication pass-first scheme, and we present results from our study of fault detection, recovery, and blocking times.

A dependable middleware should be able to adaptively share the distributed resources it manages in order to meet diverse application requirements, even when the quality of service (QoS) is degraded due to uncertain variations in load and unanticipated failures. We have addressed this issue in the context of a dependable middleware that adaptively manages replicated servers to deliver a timely and consistent response to time-sensitive client applications. These applications have specific temporal and consistency requirements, and can tolerate a certain degree of relaxed consistency in exchange for better response time. We propose a flexible QoS model that allows clients to specify their timeliness and consistency constraints. We also propose an adaptive framework that dynamically selects replicas to service a client's request based on the prediction made by probabilistic models. These models use the feedback from online performance monitoring of the replicas to provide probabilistic guarantees for meeting a client's QoS specification. The experimental results we have obtained demonstrate the role of feedback and the efficacy of simple analytical models for adaptively sharing the available replicas among the users under different workload scenarios.

One well-known challenge in using replication to service multiple clients concurrently is that of delivering a timely and consistent response to the clients. In this paper, we address this problem in the context of client applications that have specific temporal and consistency requirements. These applications can tolerate a certain degree of relaxed consistency, in exchange for better response time. We propose a flexible QoS model that allows these clients to specify their temporal and consistency constraints. In order to select replicas to serve these clients, we need to control of the inconsistency of the replicas, so that we have a large enough pool of replicas with the appropriate state to meet a client's timeliness, consistency, and dependability requirements. We describe an adaptive framework that uses lazy update propagation to control the replica inconsistency and employs a probabilistic approach to select replicas dynamically to service a client, based on its QoS specification. The probabilistic approach predicts the ability of a replica to meet a client's QoS specification by using the performance history collected by monitoring the replicas at runtime. We conclude with experimental results based on our implementation.

Group communication systems that provide consistent group membership and reliable, ordered multicast properties in the presence of faults resulting from malicious intrusions have not been analyzed extensively to quantify the cost of tolerating these intrusions. This paper attempts to quantify this cost by presenting results from an experimental evaluation of three new intrusion-tolerant microprotocols that have been added to an existing crash-fault-tolerant group communication system. The results are analyzed to identify the parts that contribute the most overhead during provision of intrusion tolerance at the group communication system level.

When making an engineering design decision, it is often necessary to consider its implications on both system performance and dependability. We present a performability study that analyzes the guarded operation duration for onboard software upgrading. In particular, we define a "performability index" Y that quantifies the extent to which the guarded operation with a duration /spl phi/ reduces the expected total performance degradation. In order to solve for Y, we progressively translate its formulation until it becomes an aggregate of constituent measures conducive to efficient reward model solutions. Based on the reward-mapping-enabled intermediate model, we specify reward structures in the composite base model which is built on three stochastic activity network reward models. We describe the model-translation approach and show its feasibility for design-oriented performability modeling.

We describe a group membership protocol that is part of an intrusion-tolerant group communication system, and present an effort to use formal tools to model and validate our protocol. We describe in detail the most difficult part of the validation exercise, which was the determination of the right level of abstraction of the protocol for formally specifying the protocol. The validation exercise not only formally showed that the protocol satisfies its correctness claims, but also provided information that will help us make the protocol more efficient without violating correctness.

Building large-scale distributed object-oriented systems that provide multidimensional quality of service (QoS) in terms of fault tolerance, scalability, and performance is challenging. In order to meet this challenge, we need an architecture that can ensure that applications' requirements can be met while providing reusable technologies and software solutions. This paper describes techniques, based on the AQuA architecture, that enhance the applications' dependability and scalability by introducing two types of group members and a novel passive replication scheme. In addition, we describe how to make the management structure itself dependable by using the passive replication scheme. Finally, we provide performance measurements for the passive replication scheme.

Message-driven confidence-driven (MDCD) error containment and recovery, a low-cost approach to mitigating the effect of software design faults in distributed embedded systems, is developed for onboard guarded software upgrading for deep-space missions. In this paper, we first describe and verify the MDCD algorithms in which we introduce the notion of "confidence-driven" to complement the "communication-induced" approach employed by a number of existing checkpointing protocols to achieve error containment and recovery efficiency. We then conduct a model-based analysis to show that the algorithms ensure low performance overhead. Finally, we discuss the advantages of the MDCD approach and its potential utility as a general-purpose, low-cost software fault tolerance technique for distributed embedded computing.

The Mobius framework is an environment for supporting multiple modeling formalisms and solution techniques. Models expressed in formalisms that are compatible with the framework are translated into equivalent models using Mobius framework components. This translation preserves the structure of the models, allowing efficient solutions. The framework is implemented in the tool by a well-defined abstract functional interface. Models and solution techniques interact with one another through the use of the standard interface, allowing them to interact with Mobius framework components, not formalism components. This permits novel combinations of modeling techniques, and will be a catalyst for new research in modeling techniques. This paper describes our approach, focusing on the "atomic model". We describe the formal description of the Mobius components as well as their implementations in our software tool.

Server replication is commonly used to improve the fault tolerance and response time of distributed services. An important problem when executing time-critical applications in a replicated environment is that of preventing timing failures by dynamically selecting the replicas that can satisfy a client's timing requirement, even when the quality of service is degraded due to replica failures and excess load on the server. We describe the approach we have used to solve this problem in AQuA, a CORBA-based middleware that transparently replicates objects across a local area network. The approach we use estimates a replica's response time distribution based on performance measurements regularly broadcast by the replica. An online model uses these measurements to predict the probability with which a replica can prevent a timing failure for a client. A selection algorithm then uses this prediction to choose a subset of replicas that can together meet the client's timing constraints with at least the probability requested by the client. We conclude with experimental results based on our implementation.

Describes an approach for enabling the synergistic coordination between two fault-tolerance protocols to simultaneously tolerate software and hardware faults in a distributed computing environment. Specifically, our approach is based on a message-driven confidence-driven (MDCD) protocol that we have devised for tolerating software design faults, and a time-based (TB) checkpointing protocol that was developed by N. Neves and W.K. Fuchs (1996) for tolerating hardware faults. By carrying out algorithm modifications that are conducive to synergistic coordination between volatile-storage and stable-storage checkpoint establishments, we are able to circumvent the potential interference between the MDCD and TB protocols, and to allow them to effectively complement each other to extend a system's fault tolerance capability. Moreover, the protocol coordination approach preserves and enhances the features and advantages of the individual protocols that participate in the coordination, keeping the performance cost low.

The authors revisit the problem of software fault tolerance in distributed systems. In particular, we propose an extension of a message-driven confidence-driven (MDCD) protocol we have developed for error containment and recovery in a particular type of distributed embedded system. More specifically, we augment the original MDCD protocol by introducing the method of "fine-grained confidence adjustment," which enables us to remove the architectural restrictions. The dynamic nature of the MDCD approach gives it a number of desirable characteristics. First, this approach does not impose any restrictions on interactions among application software components or require costly message-exchange based process coordination/synchronization. Second, the algorithms allow redundancies to be applied only to low-confidence or critical interacting software components in a distributed system, permitting flexible realization of software fault tolerance. Finally, the dynamic error containment and recovery mechanisms are transparent to the application and ready to be implemented by generic middleware.

The AQuA architecture provides adaptive fault tolerance to CORBA applications by replicating objects and providing a high-level method that an application can use to specify its desired level of dependability. This paper presents the algorithms that AQUA uses, when an application's dependability requirements can change at runtime, to tolerate both value faults in applications and crash failures simultaneously. In particular, we provide an active replication communication scheme that maintains data consistency among replicas, detects crash failures, collates the messages generated by replicated objects, and delivers the result of each vote. We also present an adaptive majority voting algorithm that enables the correct ongoing vote while both the number of replicas and the majority size dynamically change. Together, these two algorithms form the basis of the mechanism for tolerating and recovering from value faults and crash failures in AQuA.

Distributed applications can fail in subtle ways that depend on the state of multiple parts of a system. This complicates the validation of such systems via fault injection, since it suggests that faults should be injected based on the global state of the system. In Loki, fault injection is performed based on a partial view of the global state of a distributed system, i.e. faults injected in one node of the system can depend on the state of other nodes. Once faults are injected, a post-runtime analysis, using off-line clock synchronization, is used to place events and injections on a single global timeline and to determine whether the intended faults were properly injected. Finally, experiments containing successful fault injections are used to estimate the specified measures. In addition to briefly reviewing the concepts behind Loki and its organization, we detail Loki's user interface. In particular, we describe the graphical user interfaces for specifying state machines and faults, for executing a campaign and for verifying whether the faults were properly injected.

To assure dependable onboard evolution, we have developed a methodology called guarded software upgrading (GSU). We focus on a low-cost approach to error containment and recovery for GSU. To ensure low development cost, we exploit inherent system resource redundancies as the fault tolerance means. In order to mitigate the effect of residual software faults at low performance cost, we take a crucial step in devising error containment and recovery methods by introducing the confidence-driven notion. This notion complements the message-driven (or communication-induced) approach employed by a number of existing checkpointing protocols for tolerating hardware faults. In particular, we discriminate between the individual software components with respect to our confidence in their reliability and keep track of changes of our confidence (due to knowledge about potential process state contamination) in particular processes. This, in turn, enables the individual processes in the spaceborne distributed system to make decisions locally at run-time, on whether to establish a checkpoint upon message passing and whether to roll back or roll forward during error recovery. The resulting message-driven confidence-driven approach enables cost-effective checkpointing and cascading-rollback free recovery.

Validation of distributed systems using fault injection is difficult because of their inherent complexity, lack of a global clock, and lack of an easily accessible notion of a global state. To address these challenges, the Loki fault injector injects faults based on a partial view of the global state of a distributed system, and performs a post-runtime analysis using an off-line clock synchronization algorithm to determine whether the faults were properly injected. In this paper, we first describe an enhanced runtime architecture for the Loki fault injector and then present a new method for obtaining measures in Loki. The enhanced runtime allows dynamic entry and exit of nodes in the system. It also offers more efficient multicast of notification messages and more efficient communication between state machines on the same host, and is more scalable than the previous runtime. We then detail a new and flexible method for obtaining a wide range of performance and dependability measures in Loki.

This paper describes the basis for and preliminary implementation of a new fault injector, called Loki, developed specifically for distributed systems. Loki addresses issues related to injecting correlated faults in distributed systems. In Loki, fault injection is performed based on a partial view of the global state of an application. In particular, facilities are provided to pass user-specified state information between nodes to provide a partial view of the global state in order to try to inject complex faults successfully. A post-runtime analysis, using an off-line clock synchronization and a bounding technique, is used to place events and injections on a single global time-line and determine whether the intended faults were properly injected. Finally, observations containing successful fault injections are used to estimate specified dependability measures. In addition to describing the details of our new approach, we present experimental results obtained from a preliminary implementation in order to illustrate Loki's ability to inject complex faults predictably.

Dependable distributed systems are difficult to build. This is particularly true if they have dependability requirements that change during the execution of an application, and are built with commercial off-the-shelf hardware. In that case, fault tolerance must be achieved using middleware software, and mechanisms must be provided to communicate the dependability requirements of a distributed application to the system and to adapt the system's configuration to try to achieve the desired dependability. The AQuA architecture allows distributed applications to request a desired level of availability using the Quality Objects (QuO) framework and includes a dependability manager that attempts to meet requested availability levels by configuring the system in response to outside requests and changes in system resources due to faults. The AQuA architecture uses the QuO runtime to process and invoke availability requests, the Proteus dependability manager to configure the system in response to faults and availability requests, and the Ensemble protocol stack to provide group communication services. Furthermore, a CORBA interface is provided to application objects using the AQuA gateway. The gateway provides a mechanism to translate between process-level communication, as supported by Ensemble, and IIOP messages, understood by Object Request Brokers. Both active and passive replication are supported, and the replication type to use is chosen based on the performance and dependability requirements of particular distributed applications.

High level modeling representations, such as stochastic Petri nets, frequently generate very large state spaces and corresponding state transition rate matrices. We propose a new steady state solution approach that avoids explicit storing of the matrix in memory. This method does not impose any structural restrictions on the model, uses Gauss Seidel and variants as the numerical solver, and uses less memory than current state of the art solvers. An implementation of these ideas shows that one can realistically solve very large, general models in relatively little memory.

Consensus protocols are used in a variety of reliable distributed systems, including both safety-critical and business-critical applications. The correctness of a consensus protocol is usually shown, by making assumptions about the environment in which it executes, and then proving properties about the protocol. But proofs about a protocol's behavior are only as good as the assumptions which were made to obtain them, and violation of these assumptions can lead to unpredicted and serious consequences. We present a new approach for the probabilistic verification of synchronous round based consensus protocols. In doing so, we make stochastic assumptions about the environment in which a protocol operates, and derive probabilities of proper and non proper behavior. We thus can account for the violation of assumptions made in traditional proof techniques. To obtain the desired probabilities, the approach enumerates possible states that can be reached during an execution of the protocol, and computes the probability of achieving the desired properties for a given fault and network environment. We illustrate the use of this approach via the evaluation of a simple consensus protocol operating under a realistic environment which includes performance, omission, and crash failures.

Stochastic Petri nets (SPNs) and extensions are a popular method for evaluating a wide variety of systems. In most cases, their numerical solution requires generating a state-level stochastic process, which captures the behavior of the SPN with respect to a set of specified performance measures. These measures are commonly defined at the net level by means of a reward variable. In this paper, we discuss issues regarding the generation of state-level reward models for systems specified as stochastic activity networks (SANs) with "step-based reward structures". Step-based reward structures are a generalization of previously proposed reward structures for SPNs and can represent all reward variables that can be defined on the marking behavior of a net. While discussing issues related to the generation of the underlying state-level reward model, we provide an algorithm to determine whether a given SAN is "well-specified" A SAN is well-specified if choices about which instantaneous activity completes among multiple simultaneously-enabled instantaneous activities do not matter, with respect to the probability of reaching next possible stable markings and the distribution of reward obtained upon completion of a timed activity. The fact that a SAN is well specified is both a necessary and sufficient condition for its behavior to be completely probabilistically specified, and hence is an important property to determine.

The proposed use of asynchronous transfer mode (ATM) in B-ISDN necessitates fast packet switches (FPS) capable of providing adequate quality of service (QoS). The knockout switch is an FPS with low delay and cell loss at the switch level. However, the performance perceived by a specific input is not simple to determine, since the often computed cell loss probability (CLP) is a time averaged value obtained with respect to the switch. An analysis of the distribution of consecutive cell losses seen at a tagged port would be more useful. In this paper, we examine this distribution under a wide range of traffic burstiness for the knockout switch using Markov processes generated automatically from a stochastic activity network (SAN) representation. The results provide useful information on the performance at a specific input, as well as illustrate the usefulness of SANs in modeling and analyzing telecommunication switch designs.

Model-based evaluation of reliable distributed and parallel systems is difficult due to the complexity of these systems and the nature of the dependability measures of interest. The complexity creates problems for analytical model solution techniques, and the fact that reliability and availability measures are based on rare events makes traditional simulation methods inefficient. Importance sampling is a well-known technique for improving the efficiency of rare event simulations. However, finding an importance sampling strategy that works well in general is a difficult problem. The best strategy for importance sampling depends on the characteristics of the system and the dependability measure of interest. This fact motivated the development of an environment for importance sampling that would support the wide variety of model characteristics and interesting measures. The environment is based on stochastic activity networks, and importance sampling strategies are specified using the new concept of the importance sampling governor. The governor supports dynamic importance sampling strategies by allowing the stochastic elements of the model to be redefined based on the evolution of the simulation. The utility of the new environment is demonstrated by evaluating the unreliability of a highly dependable fault-tolerant unit used in the well-known MARS architecture. The model is non-Markovian, with Weibull distributed failure times and uniformly distributed repair times.>

A fiber-optic star-based picture archiving and communication system (PACS) network that is based on a multiplexed passive star local area network with wavelength-division multiplexing (WDM) to provide separate logical channels for transfer of control and image data is discussed. The system consists of an image network (INET), for image transfer at a rate of 140 Mb/s, and a control network (CNET), operating at 10 Mb/s, for mediating the flow of image transfers. INET is a circuit switched network devoted solely to image transfer, while CNET employs the CSMA/CD protocol for bus arbitration. Stochastic activity networks were used to develop a detailed model of the command and image channels. The performance of the system was then evaluated under realistic workload conditions. In particular, a number of important performance variables, including the image response time, command channel delay, and queue length at each type of node and the network supervisor, are estimated. The results (1) show that stochastic activity networks are an appropriate model type for evaluating picture archiving and communication systems, (2) delineate the workload conditions under which PACS may effectively operate, and (3) show that even when these conditions are exceeded, the command channel load remains extremely light.

The authors investigate the use of stochastic activity networks (SANs) and reduced base model construction techniques in evaluating picture archiving and communication systems (PACSs). Construction and solution of the models is done using UltraSAN, a graphically oriented software tool for model specification, analysis, and simulation. The method is illustrated via the evaluation of a realistically sized PACS for a typical US hospital of 300-400 beds, and the derivation of system response times and component utilizations. The approach is modular, in the sense that SAN models of individual PACS components can be reused when investigating alternative system configurations.>

The authors present the results of an evaluation for the CSMA/CD (carrier sense multiple access with collision detection) protocol and a deterministic protocol under workloads anticipated in an industrial environment. Stochastic activity networks are used as the model type, and simulation is used as the solution method. The results show that the preferred resolution scheme depends on the level of workload anticipated and whether transient faults occur. It is seen that stochastic activity networks permit the representation of a relatively complex fault model as well as normal protocol operations. It is shown that, when transient faults are considered, the deterministic collision resolution scheme performs better than the nondeterministic scheme.>

Reduced base model construction methods for stochastic activity networks are discussed. The basic definitions concerning stochastic networks are reviewed and the types of variables used in the construction process are defined. These variables can be used to estimate both transient and steady-state system characteristics. The construction operations used and theorems stating the validity of the method are presented. A procedure for generating the reduced base model stochastic process for a given stochastic activity network and performance variable is presented. Some examples which illustrate the method and demonstrate its effectiveness in reducing the size of a state space are presented.>