Alexander Feldman

AAAI Conference 2020 Conference Paper

Efficient Model-Based Diagnosis of Sequential Circuits

• Alexander Feldman
• Ingo Pill
• Franza Wotawa
• Ion Matei
• Johan de Kleer

In Model-Based Diagnosis (MBD), we concern ourselves with the health and safety of physical and software systems. Although we often use different knowledge representations and algorithms, some tools like satisfiability (SAT) solvers and temporal logics, are used in both domains. In this paper we introduce Finite Trace Next Logic (FTNL) models of sequential circuits and propose an enhanced algorithm for computing minimal-cardinality diagnoses. Existing state-of-the-art satisfiability algorithms for minimal diagnosis use Sorting Networks (SNs) for constraining the cardinality of the diagnostic candidates. In our approach we exploit Multi-Operand Adders (MOAs). Based on extensive tests with ISCAS-89 circuits, we found that MOAs enable Conjunctive Normal Form (CNF) encodings that are significantly more compact. These encodings lead to 19. 7 to 67. 6 times fewer variables and 18. 4 to 62 times fewer clauses. For converting an FTNL model to CNF, we could achieve a speed-up ranging from 6. 2 to 22. 2. Using SNs fosters 3. 4 to 5. 5 times faster on-line satisfiability checking though. This makes MOAs preferable for applications where RAM and off-line time are more limited than on-line CPU time.

AIJ Journal 2017 Journal Article

How many diagnoses do we need?

• Roni Stern
• Meir Kalech
• Shelly Rogov
• Alexander Feldman

ECAI Conference 2016 Conference Paper

A Framework for Automatic Debugging of Functional and Degradation Failures

• Nuno Cardoso
• Rui Abreu 0001
• Alexander Feldman
• Johan de Kleer

Software diagnosis is a particularly challenging problem for modern systems, which may consist of dozens, if not hundreds, of components computing on concurrent and potentially distributed platforms, and using infrastructure and services built by many organizations. We propose a framework that generalizes state-of-the-art classical reasoning-based fault diagnosis which tolerates observation uncertainty and addresses degradation of quality of service. Empirical evaluation involving 27000 highly realistic synthetic scenarios demonstrates an average accuracy improvement of 20% (with 99% statistical significance) which is considerable in the domain of Software Fault Localization (SFL). We measure the improvement in accuracy on well-established SFL performance metrics.

AAAI Conference 2015 Conference Paper

How Many Diagnoses Do We Need?

• Roni Stern
• Meir Kalech
• Shelly Rogov
• Alexander Feldman

A known limitation of many diagnosis algorithms is that the number of diagnoses they return can be very large. This raises the question of how to use such a large set of diagnoses. For example, presenting hundreds of diagnoses to a human operator (charged with repairing the system) is meaningless. In various settings, including decision support for a human operator and automated troubleshooting processes, it is sufficient to be able to answer a basic diagnostic question: is a given component faulty? We propose a way to aggregate an arbitrarily large set of diagnoses to return an estimate of the likelihood of a given component to be faulty. The resulting mapping of components to their likelihood of being faulty is called the system’s health state. We propose two metrics for evaluating the accuracy of a health state and show that an accurate health state can be found without finding all diagnoses. An empirical study explores the question of how many diagnoses are needed to obtain an accurate enough health state, and a simple online stopping criterion is proposed.

AAAI Conference 2014 Conference Paper

Diagnosing Analogue Linear Systems Using Dynamic Topological Reconfiguration

• Alexander Feldman
• Gregory Provan

Fault diagnosis of analogue linear systems poses many challenges, such as the size of the search space that must be explored and the possibility of simulation instabilities introduced by particular fault classes. We study a novel algorithm that addresses both problems. This algorithm dynamically modifies the simulation model during diagnosis by pruning parametrized components that cause discontinuity in the model. We provide a theoretical framework for predicting the speedups, which depends on the topology of the model. We empirically validate the theoretical predictions through extensive experimentation on a benchmark of circuits.

IJCAI Conference 2013 Conference Paper

Machine-Learning-Based Circuit Synthesis

• Lior Rokach
• Meir Kalech
• Gregory Provan
• Alexander Feldman

Multi-level logic synthesis is a problem of immense practical significance, and is a key to developing circuits that optimize a number of parameters, such as depth, energy dissipation, reliability, etc. The problem can be defined as the task of taking a collection of components from which one wants to synthesize a circuit that optimizes a particular objective function. This problem is computationally hard, and there are very few automated approaches for its solution. To solve this problem we propose an algorithm, called Circuit-Decomposition Engine (CDE), that is based on learning decision trees, and uses a greedy approach for function learning. We empirically demonstrate that CDE, when given a library of different component types, can learn the function of Disjunctive Normal Form (DNF) Boolean representations and synthesize circuit structure using the input library. We compare the structure of the synthesized circuits with that of well-known circuits using a range of circuit similarity metrics.

AAAI Conference 2012 Conference Paper

Exploring the Duality in Conflict-Directed Model-Based Diagnosis

• Roni Stern
• Meir Kalech
• Alexander Feldman
• Gregory Provan

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

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

AAAI Conference 2008 Conference Paper

Computing Minimal Diagnoses by Greedy Stochastic Search

• Alexander Feldman

Most algorithms for computing diagnoses within a modelbased diagnosis framework are deterministic. Such algorithms guarantee soundness and completeness, but are ΣP 2 hard. To overcome this complexity problem, which prohibits the computation of high-cardinality diagnoses for large systems, we propose a novel approximation approach for multiple-fault diagnosis, based on a greedy stochastic algorithm called SAFARI (StochAstic Fault diagnosis Algo- RIthm). We prove that SAFARI can be configured to compute diagnoses which are of guaranteed minimality under subsumption. We analytically model SAFARI search as a Markov chain, and show a probabilistic bound on the minimality of its minimal diagnosis approximations. We have applied this algorithm to the 74XXX and ISCAS85 suites of benchmark combinatorial circuits, demonstrating order-ofmagnitude speedups over two state-of-the-art deterministic algorithms, CDA∗ and HA∗, for multiple-fault diagnoses.

AAAI Conference 2008 Conference Paper

Computing Observation Vectors for Max-Fault Min-Cardinality Diagnoses

• Alexander Feldman

Model-Based Diagnosis (MBD) typically focuses on diagnoses, minimal under some minimality criterion, e. g. , the minimal-cardinality set of faulty components that explain an observation α. However, for different α there may be minimal-cardinality diagnoses of differing cardinalities, and several applications (such as test pattern generation and benchmark model analysis) need to identify the α leading to the max-cardinality diagnosis amongst them. We denote this problem as a Max-Fault Min-Cardinality (MFMC) problem. This paper considers the generation of observations that lead to MFMC diagnoses. We present a near-optimal, stochastic algorithm, called MIRANDA (Max-fault mIn-caRdinAlity observatioN Deduction Algorithm), that computes MFMC observations. Compared to optimal, deterministic approaches such as ATPG, the algorithm has very low cost, allowing us to generate observations corresponding to high-cardinality faults. Experiments show that MIRANDA delivers optimal results on the 74XXX circuits, as well as good MFMC cardinality estimates on the larger ISCAS85 circuits.

AAAI Conference 2006 Conference Paper

A Two-Step Hierarchical Algorithm for Model-Based Diagnosis

• Alexander Feldman

For many large systems the computational complexity of complete model-based diagnosis is prohibitive. In this paper we investigate the speedup of the diagnosis process by exploiting the hierarchy/locality as is typically present in wellengineered systems. The approach comprises a compile-time and a run-time step. In the first step, a hierarchical CNF representation of the system is compiled to hierarchical DNF of adjustable hierarchical depth. In the second step, the diagnoses are computed from the hierarchical DNF and the actual observations. Our hierarchical algorithm, while sound and complete, allows large models to be diagnosed, where compiletime investment directly translates to run-time speedup. The benefits of our approach are illustrated by using weak-fault models of real-world systems, including the ISCAS-85 combinatorial circuits. Even for these non-optimally partitioned problems the speedup compared to traditional approaches ranges in the hundreds.