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.

Connection admission control (CAC) in broadband, ATM-based telecommunication networks is a problem of recognized importance. Its solution calls for real-time algorithms that can accurately decide whether a connection request may be granted without compromising specified quality of service (QoS) requirements. We consider an algorithm for this purpose that accommodates variable bit rate (VBR) connections and is based on effective bandwidth computations. Arriving VBR traffic streams are assumed to be leaky-bucket regulated and are represented by worst-case, periodic, on-off, fluid sources that are randomly phased. Moreover, certain traffic classes may benefit from statistical multiplexing (S-VBR), while others may not (NS-VBR). We then evaluate the ability of such a CAC algorithm to perform in the presence of fluctuating channel capacity, where the performability variable Y/sub T/ is the fraction of some specified busy period T during which the quality of service requirement is violated. A general base model that supports Y/sub T/ is then formulated and instances of the resulting performability model are constructed and solved using UltraSAN. In particular, the evaluation experiments reveal some interesting differences in how QoS degrades with respect to the control of S-VBR vs. NS-VBR traffic.

Connection admission control (CAC) in broadband, ATM-based telecommunication networks is a problem of recognized importance. We consider algorithms for this purpose that accommodate variable bit rate (VBR) connections and are based on effective bandwidth computations. Arriving VBR traffic streams are assumed to be leaky-bucket regulated and are represented by worst-case, periodic, on-off-fluid sources that are randomly phased. Moreover certain traffic classes may benefit from statistical multiplexing (S-VBR) while others may not (NS-VBR). We then evaluate the ability of such CAC algorithms to perform in the presence of fluctuating channel capacity, where the performability variable Y/sub T/ is the fraction of some specified busy period T during which the quality of service requirement is violated. A general base model that supports Y/sub T/ is then formulated and instances of the resulting performability model are constructed and solved using UltraSAN.

Effects of shared use on the dependability of modular software are evaluated in terms of a generally defined stochastic model. The total system in question consists of a community of n users who share a software system with m modules. The input aspect of the operational environment, reflecting user demands at the module level, is represented by a continuous-time, finite-state Markov process, called the operational profile. The profile's construction is based on the isolated profiles of individual users which, in the case of heterogeneous use, are pairwise-distinct processes. Moreover, in the presence of other users, an individual profile can differ from its isolated version due to "slowdowns" caused by sharing. This multiuser profile is then combined with a failure model which, among other things, captures "stress" due to shared use. A number of basic issues are then addressed and resolved in terms of closed-form dependability solutions obtained for elementary 2-user, 1-module systems. Specifically, three measures are investigated in this manner, providing considerable insight into how dependability, as perceived by a subject user, is affected by the profile of an interfering user.

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.>

A system's ability to recover quickly from transient errors is particularly important for systems that operate in hostile environments where bursts of high-frequency errors are likely. Evaluation of this ability poses a number of problems, including appropriate modeling of both the error-arrival process and the system's workload. These two problems are addressed in the context of a specific evaluation study, where the system in question is a self-exercising, self-checking (SE/SC) memory design. Evaluation is based on a stochastic activity network model of the total system (memory, workload, and error environment) where, for comparison, both the SE/SC memory and a 'standard' memory are modeled in this fashion. The system workload is parameterized and its effect on recovery is evaluated for different choices of parameter values. The central measure of interest is the memory's ability to recover from bursts of transient errors. It is found that coverage is indeed workload dependent, where this dependence is particularly severe in the case of a standard memory. The results also show that, for the SE/SC design, coverage is less sensitive to workload, and in all cases, exceeds that of a standard memory.>

An algorithm is developed for solving a broad class of performability models wherein system performance is identified with "reward." More precisely, for a system S and a utilization period T, the performance variable of the model is the reward derived from using S during T. The state behavior of S is represented by a finite-state stochastic process (the base model); reward is determined by reward rates associated with the states of the base model. Restrictions on the base model assume that the system in question is not repaired during utilization. It is also assumed that the corresponding reward model is a nonrecoverable process in the sense that a future state (reward rate) of the model cannot be greater than the present state. For this model class, we obtain a general method for determining the probability distribution function of the performance (reward) variable and, hence the performability of the corresponding system. Moreover, this is done for bounded utilization periods. The result is an integral expression which can be solved either analytically or numerically.

If computing system performance is degradable, then as recognized in a number of recent studies, system evaluation must deal simultaneously with aspects of both performance and reliability. One approach is the evaluation of a system's "performability," which relative to a specified performance variable Y, generally requires solution of the probability distribution function of Y. In this paper we examine the feasibility of closed-form solutions of performability when Y is continuous. In particular, we consider the modeling of a degradable buffer/multiprocessor system whose performance Y is the (normalized) average throughput rate realized during a bounded interval of time. Employing an approximate decomposition of the model, we show that a closed-form solution can indeed be obtained.

If the performance of a computing system is "degradable," performance and reliability issues must be dealt with simultaneously in the process of evaluating system effectiveness. For this purpose, a unified measure, called "performability," is introduced and the foundations of performability modeling and evaluation are established. A critical step in the modeling process is the introduction of a "capability function" which relates low-level system behavior to user-oriented performance levels. A hierarchical modeling scheme is used to formulate the capability function and capability is used, in turn, to evaluate performability. These techniques are then illustrated for a specific application: the performability evaluation of an aircraft computer in the environment of an air transport mission.

Performability modeling and evaluation methods are applied to the SIFT computer in the computational environment of an air transport mission. User-visible performance of the "total system" (SIFT plus its environment) is modeled as a random variable taking values in a set of "accomplishment levels." These levels are defined in terms of four attributes of total system behavior: safety, no change in mission profile, no operational penalties, and no economic penalties. The "base model" of the total system is a stochastic process whose states describe the internal structure of SIFT as well as relevant conditions of its environment. Base model state trajectories are related to accomplishment levels via a "capability function" which is formulated in terms of a three-level model hierarchy. Solution methods are then applied to determine the performability of the total system for various choices of computer and environment parameter values.

When a specific type of network is required, the function to be realized limits the amount of fault tolerance that can be achieved. Parameters of functions that affect the maximum obtainable fault tolerance and the maximum obtainable diagnosability are investigated for several types of combinational memoryless) networks.

A reliability analysis method for computing systems is considered in which the underlying criteria for "success" are based on the computations the system must perform in the use environment. Beginning with a general model of a "computer with faults," intermediate concepts of a "tolerance relation" and an "environment space" are introduced which account for the computational needs of the user and the probabilistic nature of the use environment. These concepts are then incorporated to obtain a precisely defined class of computation-based reliability measures. Formulation of a particular measure is illustrated and results, applying this measure, are compared with those of a typical structure-based analysis.

A formal model for the study of on-line diagnosis is introduced and used to investigate the diagnosis of unrestricted faults. Within this model a fault of a system S is considered to be a transformation of S into another system S' at some time r. The resulting faulty system is taken to be the system which looks like S up to time r and like S' thereafter. Notions of fault tolerance and error are defined in terms of the resulting system being able to mimic some desired behavior as specified by a system S. A notion of on-line diagnosis is formulated which involves an external detector and a maximum time delay within which every error caused by a fault in a prescribed set must be detected.

A formal model for the study of reliable combinational networks is introduced and used to determine network properties conducive to the location of faults. The usual concept of fault location is generalized to be an interval on the partially ordered set of subsets of network nodes that classifies nodes into three disjoint sets: a faulty set, a fault-free set, and an indeterminate set. After developing basic properties of locatable faults, necessary and sufficient conditions for a fault to be locatable in an arbitrary network are stated and proven.

A machine representation of permanent memory faults is introduced where, if M is a sequential machine representing some fault free system, a memory fault is represented by a function μ on the states of M, and the result of the fault by an appropriately determined machine Mμ. Given this representation, the investigation is primarily concerned with faults that are tolerated (masked) in the sense that resulting behavior relates in some specified way to original behavior. Several types of fault masking are thus considered and conditions for their existence investigated. The restriction to a special class of stable faults is also studied, this class being of interest since it includes all faults which correspond to "stuck-at" failures in the memory cells of a sequential switching network.