75 research outputs found
Spectrum-based Fault Localization in Embedded Software
No full textLocating software components that are responsible for observed failures is a time-intensive and expensive phase in the software development cycle. Automatic fault localization techniques aid developers/testers in pinpointing the root cause of software failures, as such reducing the debugging effort. Automatic fault localization has been an active area of research in the past years. Current approaches to automatic software fault localization can be classified as either (1) statistics-based approaches, or (2) reasoning approaches. This distinction is based on the required amount of knowledge about the program’s internal component structure and behavior. Statistics-based fault localization techniques such as Spectrum-based Fault Localization (SFL) use abstraction of program traces (also known as program spectra) to find a statistical relationship between source code locations and observed failures. Although SFL’s modeling costs and computational complexity are minimal, its diagnostic accuracy is inherently limited since no reasoning is used. In contrast to SFL, model-based reasoning approaches use prior knowledge of the program, such as component interconnection and statement semantics, to build a model of the correct behavior of the system. On the one hand, model-based reasoning approaches deliver higher diagnostic accuracy, but on the other hand, they suffer from high computation complexity. In this thesis, we thoroughly studied the fundamental limitations of SFL. In particular, we studied its diagnostic accuracy as a function of similarity coefficient, quantity of observations, and quality of the error detectors. As a result of this study, we discovered a new similarity coefficient (Ochiai), known from the molecular biology community. Ochiai consistently outperforms all coefficients investigated, including those used by related approaches. Furthermore, we present a novel, low-cost, Bayesian reasoning approach to spectrum-based multiple fault localization, dubbed Barinel. A central feature of our approach is the use of a generic, intermittent component failure model. The novelty of this model lies in the computation of the component intermittency rate as part of the posterior candidate probability computation using a maximum likelihood estimation procedure, rather than using previous approaches’ approximations. This procedure optimally exploits all information contained in the program spectra. Our synthetic and real software experiments show that Barinel outperforms previous approaches to fault localization. Furthermore, this thesis reports on the following additional studies. First, we studied the capabilities of simple, generic program invariants to replace test oracles, so as to achieve total automation of the fault localization process. We verified that, despite the simplicity of the program invariants (and therefore considerable rates of false positives and/or negatives), the diagnostic performance of SFL is similar to the combination of SFL and test oracles. Second, to scale to large systems, reasoning approaches such as Barinel depends on low-cost algorithms to compute the set of diagnosis candidates. We investigated the possibility of using an SFL-based heuristic to focus the computation of valid diagnosis candidates. We show that the SFL-based heuristic is suitable to derive the set of candidates as the search is focused by visiting candidates in best-first order (aiming to capture the most relevant probability mass in the shortest amount of time). Therefore, our algorithm, Staccato, is order of magnitude faster than, e.g., brute-force approaches, rendering our reasoning approach amenable to large programs. Finally, we studied whether SFL can be integrated with existing model-based software debugging approaches (MBSD) to reduce their high time complexity, while improving their diagnostic quality. We have shown that the combination of SFL with MBSD focus the debugging process to relevant parts of the program. Specially compared to MBSD, we have shown that our algorithm has lower complexity, making it scale to large programs.Software TechnologyElectrical Engineering, Mathematics and Computer Scienc
Approximation Algorithms for Model-Based Diagnosis
No full textModel-based diagnosis is an area of abductive inference that uses a system model, together with observations about system behavior, to isolate sets of faulty components (diagnoses) that explain the observed behavior, according to some minimality criterion. This thesis presents greedy approximation algorithms for three problems closely related to model-based diagnosis: (1) computation of cardinality-minimal diagnoses, (2) computation of max-fault min-cardinality observation vectors, and (3) computation of control assignments that optimally reduce the expected number of remaining cardinality-minimal diagnoses. All three problems are NP-hard or worse (for example, problem (1) is known to be in the second class of the polynomial hierarchy for arbitrary propositional models), thus making deterministic algorithms impractical for solving large models. The three main algorithms of this thesis are SAFARI (StochAstic Fault diagnosis AlgoRIthm) for problem (1), MIRANDA (Max-fault mIn-caRdinAlity observatioN Deduction Algorithm) for problem (2), and FRACTAL-G (FRamework for ACtive Testing ALgorithms - Greedy) for problem (3). These three algorithms, the analysis of their properties, the empirical research about their performance, and the comparison to other approaches are the main theoretical contributions of this thesis. SAFARI, MIRANDA, and FRACTAL-G employ approximation methods such as greedy stochastic search, stochastic sampling (in the case of FRACTAL-G) and, as a result, efficiently solve worst-case NP-hard or worse problems by trading relatively small degradation in the optimality of the diagnostic results for much larger gain in the computational performance (in some cases several orders-of-magnitude improvement in speed). This efficient trade-off is partly due to exploitation of specific properties in the search landscape of the diagnostic problems. All three algorithms achieve good optimality at low computational cost in diagnostic search problems that exhibit certain amount of continuity. We have validated the theoretical claims related to SAFARI, MIRANDA, and FRACTAL-G with extensive experimentation on fault-models of 74XXX/ISCAS85 combinational circuits. These models are of variable size (19 - 3512 components), different weakness (ignorance of abnormal behaviour, stuck-at), and different topology. We show analytically that for a large class of models (weak-fault models), SAFARI can be configured to efficiently compute one subset-minimal diagnosis. In the general case (strong-fault model) and in the case of multiple diagnoses we show topologically-dependent probabilistic properties of SAFARI. For example, in the case of multiple diagnoses, SAFARI computes diagnoses of minimal-cardinality with probability which is negative exponential to the cardinality of the minimal-cardinality diagnosis. SAFARI is computationally very efficient. For example, SAFARI computes a subset-minimal diagnosis in a weak-fault model of a digital circuit having more than 1500 gates in less than 1 s and the memory footprint is less than 24 Mb of RAM. The average degradation in the optimality of the diagnoses computed by SAFARI is 13% only (averaged over all models and observations leading to a single or double-fault). We have compared SAFARI to a range of deterministic and stochastic algorithms for computation of cardinality-minimal diagnoses. State-of-the-art deterministic algorithms such as HA* and CDA* are typically several orders-of-magnitude slower than SAFARI. Furthermore HA* and CDA* often time out with higher cardinality faults (and larger circuits) whereas SAFARI is not sensitive to the cardinality of the cardinality-minimal diagnosis. SAFARI has resemblance to Max-SAT and to further empirically analyze the performance and optimality of SAFARI, we have implemented a method for computing cardinality-minimal diagnoses that uses a deterministic partial Max-SAT solver. In addition to that we have compared SAFARI to a diagnostic algorithm based on SLS Max-SAT. We have established that the performance of the complete Max-SAT and the optimality of the SLS-based Max-SAT degrade when increasing the circuit size or the cardinality of the faults. For example, a diagnosis algorithm based on W-MaxSatz computed diagnoses with only 9.2% of the c880 observation vectors, whereas SAFARI always computes at least one nearly optimal diagnosis. Algorithms based on SLS-based Max-SAT, typically did not compute any diagnoses or computed very suboptimal diagnoses (for example one of the best performing Max-SAT algorithms, SAPS, found a single-fault diagnosis in c7552 after 77264 restarts, while SAFARI computed the same diagnosis with 11 restarts only). In this thesis, we propose an algorithm, MIRANDA, for creating a benchmark of "difficult" observation vectors for testing the performance and optimality of diagnostic algorithms such as SAFARI. MIRANDA computes observation vectors leading to faults of high cardinality. These, so-called MFMC observation vectors, lead to diagnoses of cardinality close to the maximally distinguishable given the fault-model. For small combinational circuits (74XXX) the approximations of MIRANDA coincide with the optimal MFMC observation vectors (in terms of diagnostic cardinality) and these results are computed several orders of magnitude faster than exhaustive algorithms. With large circuits, MIRANDA computes an MFMC observation vector leading to a diagnosis of approximate cardinality of 36 in less than 6 min (c5315). The reason for the good performance of MIRANDA is the fact that it exploits continuity in the space of output assignments in a class of well-formed benchmark circuits. MIRANDA searches the space of all possible observations, and, at each step, uses SAFARI to estimate the cardinality of the cardinality-minimal diagnosis. By varying the number of MIRANDA and SAFARI retries, we have empirically established lower bounds on the approximation error of MIRANDA. The theoretical analysis of the cardinality estimation optimality of SAFARI leads us to believe that the small lower bound on the error of MIRANDA is a good approximation of the overall approximation error and hence, the MFMC values and observation vectors computed by MIRANDA are nearly optimal. FRACTAL-G is an algorithm that, given a model and an observation leading to multiple minimal-cardinality diagnoses, computes a control assignment (a test) that optimally reduces the set of diagnoses. As the problem is computationally hard, we use greedy stochastic search and stochastic sampling. The result is a fast algorithm (computing a whole FRACTAL scenario takes between 1 s for 74182 and 15 min for c7552) that decreases the diagnostic uncertainty according to a near-geometric decay curve. The reason for the efficiency of FRACTAL-G is that it exploits continuity in the space of control assignments. Experimentation shows that this is true even for a small number of control inputs. FRACTAL-G has achieved better exponential decay compared to alternative approaches, except exhaustive control search. The difference in the decay rate between FRACTAL-G and exhaustive search for 74182 is 5.4%. The exhaustive control approach, however, takes minutes to complete even for 74182 and times out with any model having more than 20 controls. We have implemented a tool kit for system modeling called LYDIA (Language for sYstem DIAgnosis). LYDIA is also the framework in which we have developed all the algorithms in this thesis. In addition to the implementations of SAFARI, MIRANDA, and FRACTAL-G, the LYDIA tool kit also contains model translators (e.g., to CNF, DNF, OBDDs, etc), utilities, and all reference algorithms. We have applied LYDIA to, amongst others, (1) a model of the Electrical Power System (EPS) testbed in the ADAPT lab at NASA Ames Research Center, as a participant in the First International Diagnostic Competition (DXC'09), and (2) a Paper Input Module (PIM), part of a heavy-duty printer of Oce Technologies. The ADAPT EPS consists of electrical components only and the PIM model is a combination of electrical, mechanical and pneumatic ones. The results from the applications of LYDIA to models of physical systems such as ADAPT and PIM are consistent with the results from experiments on models of digital circuits. For example, the average running time of SAFARI for diagnosing ADAPT, a system that is modeled with 723 variables and 1567 clauses, was below 6 s which makes SAFARI one of the fastest MBD algorithms today.Software TechnologyElectrical Engineering, Mathematics and Computer Scienc
Cost Optimizations in Runtime Testing and Diagnosis
No full textSoftware testing and diagnosis (debugging) is a time-consuming but rather important task for improving software reliability. It is therefore necessary to devise an appropriate verification strategy that not only achieves this reliability goal, but also does this at a minimum cost. Since exhaustive testing is hardly ever possible, testing typically aims at detecting the presence of faults, by trying to produce a failure (the external manifestation of a fault). Once failures have been detected, the faults that produced them have to be localized. Unfortunately for developers, it has recently been shown that effective fault detection and effective fault localization are contradictory goals. In particular, it has been shown that focusing exclusively on fault detection has a detrimental effect on fault localization, canceling the savings in testing cost by an increase in diagnostic cost. In this thesis we explore the causes for this cost increase, and propose a shift in the goal of testing, focusing on techniques that achieve much better fault localization performance, while maintaining fault detection performance.Software TechnologyElectrical Engineering, Mathematics and Computer Scienc
ANTARES: Automatic Diagnosis of Software/Hardware Systems
No full textWith the market becoming increasingly competitive, there is a pressure to deliver systems with more functionality and at the same cost, which thus leads to more complexity in terms of number of components. Moreover, the society is becoming increasingly dependent on these systems for its critical functions. This coupled with shrinking time-to-market and reducing life-cycle, creates a need to and ways to ensure reliability of these complex systems both effciently and quickly. Due to large size and complexity of modern day systems, fault-finding problem is a non-trivial one. Traditionally, Model-Based Diagnosis (MBD) is used to locate faults in the hardware. A prerequisite for MBD is the accurate model of the components. However, modeling of such complex components requires huge effort, time and expertise. Earlier, a spectrum-based hardware solution named BACINOL was proposed to diagnose the hardware system without the aid of a component model. But BACINOL suffers from low diagnosis quality due to large size of ambiguity sets in the final diagnosis. In this thesis, we introduce a new spectrum-based hardware diagnosis technique ANTARES. It attempts to break these ambiguity sets by providing a better estimate of system's False Negative Rate (FNR) information to the diagnosis method. A series of experiments are performed on the ISCAS benchmark circuits to compare the performance of ANTARES with BACINOL and MBD. Results clearly show that ANTARES has better diagnosis quality as compared to BACINOL but has lower performance than MBD.Computer ScienceElectrical Engineering, Mathematics and Computer Scienc
Analytical cost estimation for embedded systems
No full textIn the today's market of microcontrollers and FPGAs, there are so much different makes and models that making the right choice for a hardware platform for an electronics design is impossible. The spectrum is so wide that an electronics designer is unable to make a good choice for the best microcontroller or FPGA for his/her design based on the information provided by the manufacturers. To fulfill this need, this thesis presents a method of analyzing a range of hardware targets and C code. The models made of the targets and code provide an accurate prediction of the execution time of the code for each target. With this information the performance of the algorithm on a range of hardware targets can be analyzed in a minimum amount of time. Performance is not the only measure, power is just as important. Therefore, with the performance information and the design requirements the minimum clock speed is calculated. Then using the power consumption models made in this thesis, the power consumption of each hardware platform can be calculated. With the methods provided in this thesis, the designer can easily determine the performance and power consumption of a range of hardware platforms and make the right choice in an affordable amount of time.Electrical Engineering, Mathematics and Computer Scienc
Performance Modeling of Stochastic Diagnosis Engines
No full textCritical systems are complex, consisting of thousands of components, which can fail at any time. Diagnosing these systems within a certain time is highly desirable. Traditional diagnosis algorithms are mostly deterministic, able to find single faults extremely fast and double faults reasonably quick as well. However, these algorithms fail to find diagnoses fast enough in cases where there are three or more components failing simultaneously. A stochastic algorithm, like SAFARI, is able to diagnose these problems in reasonable time. However, stochastic algorithms are unable to guarantee optimality and completeness of the returned diagnoses. In this thesis we analyze the behavior of the SAFARI algorithm, introducing a characterization of performance. We provide a performance model for this stochastic algorithm and we propose a termination criterion which guarantees a certain level of completeness of the most important set of diagnoses.Computer ScienceST/SEElectrical Engineering, Mathematics and Computer Scienc
BACINOL: Bayesian Circuit Analysis by Topology
No full textDue to the high availability demands placed on modern hardware systems and the high cost associated with downtime, finding and fixing faults in these systems is an important problem. Unfortunately, the complexity of these systems is very large, making this problem very difficult. While recent innovations in the field of model-based diagnosis have brought increased performance, making it a viable method for diagnosing large systems, constructing a model is still required. This is difficult and time-consuming, therefore this thesis introduces a new method, BACINOL, based on diagnosing software systems using spectra. BACINOL attempts to diagnose multiple faults in hardware systems without the aid of a model. Using the theory behind BACINOL the concept of ambiguity sets is used to calculate a lower bound on the quality of the diagnoses obtained. A series of experiments is performed on the ISCAS85 benchmark, comparing BACINOL with SAFARI, to assess the performance obtained.Software TechnologyElectrical Engineering, Mathematics and Computer Scienc
Performance modeling of parallel systems
No full textElectrical Engineering, Mathematics and Computer Scienc
Statics and Dynamics of a Natural Circulation Cooled Boiling Water Reactor
No full textApplied Science
A Semi-Empirical Three-Dimensional Model of the Pneumatic Tyre Rolling over Arbitrarily Uneven Road Surfaces
No full textNowadays virtual prototyping tools play an important part in the development of vehicles. For studying the dynamics of a vehicle, complex vehicle models are required that are composed of several accurately modelled components. As the tyre constitutes the only contact between the vehicle and the road surface, it is one of the most important components of a vehicle model. For performing ride comfort and durability analyses, there is a need for accurate tyre models that can predict the loads that are transmitted from the tyre to the wheel axle when driving over road irregularities. In this study, such a tyre simulation model is developed that can represent the dynamic response of a tyre when rolling over uneven road surfaces. The approach followed is the combination of the well-known rigid ring dynamic tyre model and a suitable enveloping model that generates a three-dimensional effective road surface, which is used as input for the rigid ring model. The thesis deals with the development of the enveloping models and with the extension of the rigid ring tyre model so that this model is capable of handling the effective road surface. It is shown that the combination of the rigid ring model and the enveloping model can be used successfully to describe the tyre dynamic response to uneven road surfaces. In this research project, numerous experiments have been carried out for model development, parameter identification and model validation. The results of many of these experiments are presented in the thesis.Mechanical Maritime and Materials Engineerin
- …
