11532584
Sequentially t-Diagnosable Systems: A Characterization and Its Applications
In the system level fault diagnosis area, the fundamental problem of characterizing sequentially t-diagnosable systems in the PMC model has remained open for more than two decades. We resolve this problem by providing a complete characterization of such systems. Our solution to the characterization problem leads to the correct identification of optimal sequentially t-diagnosable D/sub /spl delta/,k/ systems. Given a set of n units where n=2t+1, an optimal D/sub /spl delta/,k/ system can be constructed with just n([(t+2)/3]) tests, rather than n([t/2]+1) tests-a previously misjudged bound. An efficient algorithm for identifying the set of faulty units in a sequentially t-diagnosable D/sub /spl delta/,k/ system is given along the line of the proposed characterization, which is linear with respect to the number of tests in the system. >
11432676
Building Embedded Fault-Tolerant Systems for Critical Applications: An Experimental Study
An increasing range of industries have a growing dependence on embedded software systems, many of which are safety-critical, real-time applications that require extremely high dependability. Two fundamental approaches — fault avoidance and fault tolerance — have been proposed to increase the overall dependability of such systems. However, the increased cost of using the fault tolerance approach may mean that this increase in dependability is not worth the extra expense involved. We describe an experiment undertaken in order to establish whether or not software redundancy (or the multi-version design method) can offer increased dependability over the traditional single-version development approach when given the same level of resources. The results of this and a subsequent follow-up study are then given. The analytic results from these experiments show that despite the poor quality of individual versions, the multi-version method results in a safer system than the single-version solution. It is evident that regarding the single-version method as a “seem-to-be” safer design decision for critical applications is not generally justifiable.
5963621
Concurrent Exception Handling and Resolution in Distributed Object Systems
We address the problem of how to handle exceptions in distributed object systems. In a distributed computing environment, exceptions may be raised simultaneously in different processing nodes and thus need to be treated in a coordinated manner. Mishandling concurrent exceptions can lead to catastrophic consequences. We take two kinds of concurrency into account: 1) Several objects are designed collectively and invoked concurrently to achieve a global goal and 2) multiple objects (or object groups) that are designed independently compete for the same system resources. We propose a new distributed algorithm for resolving concurrent exceptions and show that the algorithm works correctly even in complex nested situations, and is an improvement over previous proposals in that it requires only O(n/sub max/N/sup 2/) messages, thereby permitting quicker response to exceptions.
2775894
Rigorous development of a safety-critical system based on coordinated atomic actions
This paper describes our experience using coordinated atomic (CA) actions as a system structuring tool to design and validate a sophisticated control system for a complex industrial application that has high reliability and safety requirements. Our study is based on the "Fault-Tolerant Production Cell", which represents a manufacturing process involving redundant mechanical devices (provided in order to enable continued production in the presence of machine faults). The challenge posed by the model specification is to design a control system that maintains specified safety and liveness properties even in the presence of a large number and variety of device and sensor failures. We discuss in this paper: i) a design for a control program that uses CA actions to deal with both safety-related and fault tolerance concerns, and ii) the formal verification of this design based on the use of model-checking. We found that CA action structuring facilitated both the design and verification tasks by enabling the various safety problems (e.g. clashes of moving machinery) to be treated independently. The formal verification activity was performed in parallel with the design activity the interaction between them resulted in a combined exercise in "design for validation".
16148439
Solving the brachytherapy seed localization problem using geometric and linear programming techniques
We propose a technique to solve the Brachytherapy Seed Localization problem in prostate brachytherapy. Our algorithm is based on novel geometric approaches to exploit the special structure of the problem combined with a number of key observations which help us formulate it as an Integer Program. We solve the equivalent linear program and present a variant of randomized rounding to yield an integral solution to our problem. The algorithm is efficient and performs extremely well in practice. We discuss in detail the underlying theory and performance evaluations based on our implementation.
10511708
Automatic diagnosis and response to memory corruption vulnerabilities
Cyber attacks against networked computers have become relentless in recent years. The most common attack method is to exploit memory corruption vulnerabilities such as buffer overflow and format string bugs. This paper presents a technique to automatically identify both known and unknown memory corruption vulnerabilities. Based on the observation that a randomized program usually crashes upon a memory corruption attack, this technique uses the crash as a trigger to initiate an automatic diagnosis algorithm. The output of the diagnosis includes the instruction that is tricked to corrupt data, the call stack at the time of corruption, and the propagation history of corrupted data. These results provide useful information in fixing the vulnerabilities. Moreover, the diagnosis process also generates a signature of the attack using data/address values embedded in the malicious input message, and is used to block future attacks. Such a signature is further associated with the program execution state to reduce false positives without decreasing the detection rate. The proposed techniques enable the development of a decentralized self-diagnosing and self-protecting defense mechanism for networked computers. We report the implementation experience and experimental evaluation of a prototype system on Linux.
17909513
Determining an optimal penetration among weighted regions in two and three dimensions
We present efficient algorithms for solving the problem of computing an optimal penetration (a ray or a semi-ray) among weighted regions in 2-D and 3-D spaces. This problem finds applications in several areas, such as radiation therapy, geological exploration, and environmental engineering. Our algorithms are based on a combination of geometric techniques and optimization methods. Our geometric analysis shows that the d-D (d = 2, 3) optimal penetration problem can be reduced to solving O(n2(d−1)) instances of certain special types of non-linear optimization problems, where n is the total number of vertices of the regions. We also give implementation results of our 2-D algorithms.
17405074
Extracting Meaningful Entities from Police Narrative Reports
Valuable criminal-justice data in free texts such as police narrative reports are currently difficult to be accessed and used by intelligence investigators in crime analyses. It would be desirable to automatically identify from text reports meaningful entities, such as person names, addresses, narcotic drugs, or vehicle names to facilitate crime investigation. In this paper, we report our work on a neural network-based entity extractor, which applies named-entity extraction techniques to identify useful entities from police narrative reports. Preliminary evaluation results demonstrated that our approach is feasible and has some potential values for real-life applications. Our system achieved encouraging precision and recall rates for person names and narcotic drugs, but did not perform well for addresses and personal properties. Our future work includes conducting larger-scale evaluation studies and enhancing the system to capture human knowledge interactively.
30370540
On (d, 2)-dominating numbers of binary undirected de Bruijn graphs
Abstract In this paper, we show that: (i) For n-dimensional undirected binary de Bruijn graphs, UB(n), n⩾4, there is a vertex x=x 1 x 1 x 1 ⋯ x 1 x 1 (x1=1 or 0) such that for any other vertex t there exist at least two internally disjoint paths of length at most n−1 between x and t in UB(n), i.e., the (n−1,2)-dominating number of UB(n) is equal to one. (ii) For n⩾5, let S={100⋯01,011⋯10}. For any other vertex t there exist at least two internally disjoint paths of length at most n−2 between t and S in UB(n), i.e., the (n−2,2)-dominating number of UB(n) is no more than 2.