FRACTAL: Efficient fault isolation using active testing

Model-Based Diagnosis (MBD) approaches often yield a large number of diagnoses, severely lim-iting their practical utility. This paper presents a novel active testing approach based on MBD tech-niques, called FRACTAL (FRamework for ACtive Testing ALgorithms), which, given a system de-scription, computes a sequence of control settings for reducing the number of diagnoses. The ap-proach 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 gen-erates test vectors using a greedy, next-best strategy and a low-cost approximation of diagnostic infor-mation entropy. Further, the approximate sequence computed by FRACTAL’s greedy approach is opti-mal over all poly-time approximation algorithms, a fact which we confirm empirically. Extensive experimentation with ISCAS85 combinational cir-cuits 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.