Arjan J. C. van Gemund

ECAI Conference 2014 Conference Paper

Heuristics to Increase Observability in Spectrum-based Fault Localization

• Claudio Landi
• Arjan J. C. van Gemund
• Marina Zanella

The high abstraction level of Spectrum-based Fault Localization (SFL) reasoning, on the one hand, offers the advantage of a model-free approach to diagnosis, while, on the other, reduces the inherently limited testability of many hardware and software systems. Thus, along with substantial complexity gains, SFL exhibits limited diagnostic performance, compared to Model-Based Diagnosis. This paper describes two algorithms (Lion and Tiger) that exploit low cost heuristics to determine the best location to insert additional test oracles (monitors, probes, invariants) so as to increase the observability within the systems. Experiments show that even simple algorithms can considerably improve SFL's diagnostic accuracy.

AAAI Conference 2011 Conference Paper

Spectrum-Based Sequential Diagnosis

• Alberto Gonzalez-Sanchez
• Rui Abreu
• Hans-Gerhard Gross
• Arjan J. C. van Gemund

We present a spectrum-based, sequential software debugging approach coined SEQUOIA, that greedily selects tests out of a suite of tests to narrow down the set of diagnostic candidates with a minimum number of tests. SEQUOIA handles multiple faults, that can be intermittent, at polynomial time and space complexity, due to a novel, approximate diagnostic entropy estimation approach, which considers the subset of diagnoses that cover almost all Bayesian posterior probability mass. Synthetic experiments show that SEQUOIA achieves much better diagnostic uncertainty reduction compared to random test sequencing. Real programs, taken from the Software Infrastructure Repository, confirm SEQUOIA’s better performance, with a test reduction up to 80% compared to random test sequences.

IJCAI Conference 2009 Conference Paper

• Alexander Feldman
• Gregory Provan
• Arjan J. C. van Gemund

Model-Based Diagnosis (MBD) approaches often yield a large number of diagnoses, severely limiting their practical utility. This paper presents a novel active testing approach based on MBD techniques, called FRACTAL (FRamework for ACtive Testing ALgorithms), which, given a system description, computes a sequence of control settings for reducing the number of diagnoses. The approach complements probing, sequential diagnosis, and ATPG, and applies to systems where additional tests are restricted to setting a subset of the existing system inputs while observing the existing outputs. This paper evaluates the optimality of FRACTAL, both theoretically and empirically. FRACTAL generates test vectors using a greedy, next-best strategy and a low-cost approximation of diagnostic information entropy. Further, the approximate sequence computed by FRACTAL’s greedy approach is optimal over all poly-time approximation algorithms, a fact which we confirm empirically. Extensive experimentation with ISCAS85 combinational circuits shows that FRACTAL reduces the number of remaining diagnoses according to a steep geometric decay function, even when only a fraction of inputs are available for active testing.

IJCAI Conference 2009 Conference Paper

• Rui Abreu
• Peter Zoeteweij
• Arjan J. C. van Gemund

Logic reasoning approaches to fault diagnosis account for the fact that a component cj may fail intermittently by introducing a parameter gj that expresses the probability the component exhibits correct behavior. This component parameter gj, in conjunction with a priori fault probability, is used in a Bayesian framework to compute the posterior fault candidate probabilities. Usually, information on gj is not known a priori. While proper estimation of gj can have a great impact on the diagnostic accuracy, at present, only approximations have been proposed. We present a novel framework, BARINEL, that computes exact estimations of gj as integral part of the posterior candidate probability computation. BARINEL’s diagnostic performance is evaluated for both synthetic and real software systems. Our results show that our approach is superior to approaches based on classical persistent fault models as well as previously proposed intermittent fault models.

IJCAI Conference 2009 Conference Paper

• Alexander Feldman
• Gregory Provan
• Arjan J. C. van Gemund