Assessing Diagnosis Algorithms: Of Sampling, Baselines, Metrics and Oracles

Suppose that we want to design a good metric for single fault diagnosis algorithms. Assume that we have perfect measurements, which is really only possible in digital circuits. Let the components of the system be $X=\{x_1,\mathrm{\dots },x_n\}$. Determining the samples to use to fairly test a diagnostic engine for a competition is a very complex problem that deserves a separate treatment, so let us assume for now that the set of samples is given. Let a simple diagnostic algorithm $A$ return only one fault for a specific diagnosis problem $s$ defined by an exemplar $\mathrm{𝑆𝐷}$ (with a known fault) and some observations $\mathrm{𝑂𝐵𝑆}$. If $A$ returns the actual fault, the score $r(A,s)$ achieved for sample $s$ is $1$ and otherwise it is $0$. An overall score $S(A)$ of algorithm $A$ can, in turn, be defined as:

such that we would sample over a set of diagnosis problems. Intuitively, the overall score estimates the probability of $A$ producing the correct diagnosis for a random sample $s\in \text{samples}$. This simple assessment has numerous shortcomings:

1. 1.

   Probabilities: How to take into account that different components fail at different rates?

2. 2.

   Ambiguity Groups: Sometimes the same symptoms can arise from very different system failures and combinations of faults.

3. 3.

   Multiple Faults: How to take into account that a system can suffer from multiple simultaneous faults?

4. 4.

   False Positives: The sampling approach obviously penalizes false negatives (missed diagnoses), but does not adequately penalize false positives (reporting invalid diagnoses).

It is easy to see that the way we sample for computing $S(A)$ has a great impact on the overall score. A diagnostic algorithm is evaluated against a set of benchmark samples. Imagine a simple system of $4$ components $\{x_1,x_2,x_3,x_4\}$ with priors $p(x_1)=0.001,p(x_2)=0.01,p(x_3)=0.1,p(x_4)=0.889$. If we sampled the fault scenarios representatively in the set of components, i.e., considering an equal distribution, an algorithm $A_1$ that always scored correctly for components $x_1,x_2,x_3$ but not for $x_4$ would achieve a much better overall score $S(A_1)$ than $A_2$ that scored correctly on $x_4$, but not for $x_1,x_2,x_3$. And it does so, even though it is much less useful in practice, i.e., since it scores well, s.t. $r(A_2,s)=1$ for rare samples only. A possible solution to circumvent this would be to draw samples according to the prior distribution, but this requires far too many samples (i.e., expensive simulations) and the score $S(A)$ would not be generalizable for varying priors.

An exponentially more efficient approach is to sample over each of the possible faults and weigh each sample with its prior. This greatly reduces the number of samples needed to obtain a reasonable score $S(A)$:

Due to ${\sum }_{x}p(x)=1$, we see that $S(A)$ will be $1$ iff $r(A,s)$ is always correct and $0$ if it is always wrong. But this is a poor approach, since ambiguity groups introduce considerably more complexity. An ambiguity group is a set of diagnoses among which a diagnoser cannot distinguish given a specific set of observations. For example, consider diagnosing a sequence of $n$ digital buffers where we can observe the input of ${\mathrm{𝑏𝑢𝑓𝑓𝑒𝑟}}_1/x_1$ and the output of ${\mathrm{𝑏𝑢𝑓𝑓𝑒𝑟}}_n/x_n$. If the input is $0/\mathrm{𝑙𝑜𝑤}/\perp$, and the output is $1/\mathrm{ℎ𝑖𝑔ℎ}/\top$, we know that one of the buffers is faulted, but not which one. So all $n$ buffers form an ambiguity group. A similar challenge arises in the analog case where there are $n$ resistors in a row, or the two inverter example from Section 2.4 illustrated in Fig. 1. Let us assume for now that the fault is in $x_1$. Considering the effects that an ambiguity group entails, we need to modify $r(A,s)$. That is, requiring $A$ to return $x_1$ to achieve $r(A,s)=1$ makes no sense. Indeed, a diagnoser should not be penalized because it returns a different element of the ambiguity group. We need to redefine what $r(A,s)$ returns. Let $G(s)=\{x|x\text{ is a diagnosis of}s\}$. If we require $r(A,s)$ to return $x$, it will be right only $\frac{1}{|G(s)|}$ of the time. If we require $r(A,s)$ to return one element of $G(s)$, a diagnoser may always pick the same element of the ambiguity group, making it useless for diagnosing other faults in that ambiguity group. If we require $r(A,s)$ to return the entire $G(s)$, then the diagnoser never gets partial credit. One approach is to give the diagnoser credit for the fraction of the ambiguity group it returns. So, for example, if there are two members in the ambiguity group and the diagnoser returns only one member of the ambiguity group, it would receive a score of $\frac{1}{2}$ for that sample $s$. Rewriting the prior equation to capture this intuition, we obtain

where we assume the diagnoser is sound. This reduces the prior equation in the case there are no interesting ambiguity groups (of size greater than $1$.)

In the multiple fault case, these challenges become only more difficult. Assume that we have a priori probability distribution over the set of diagnoses ${\mathrm{\Delta }}_i\in 2^X$. Following the single fault case, we would like to write (where the ${\mathrm{\Delta }}_i$ can be of any cardinality):

But this has the same kinds of problems with ambiguity groups as discussed earlier. Consider the $n=10$ buffer example. It has a large number of multiple faults in the ambiguity group as well: $\left(\genfrac{}{}{0pt}{}{10}{3}\right)+\left(\genfrac{}{}{0pt}{}{10}{5}\right)+..$. A worse challenge arises in the analog case where there are $n$ resistors in a row where the ambiguity group can be of size $2^n-1$ because any subset of the resistors can be a diagnosis.

Contributing to this confusion is the fact that we have been mixing together two distinct ideas: (1) the construction of a fair benchmark and (2) the fair evaluation of a diagnostic algorithm on a benchmark. There are two important questions: (1) how to construct a benchmark that truely reflects actual occurring faults, and (2) given a set of samples, how do we fairly evaluate a diagnostic algorithm on this benchmark. Designers of a benchmark must concern themselves with the first question. This paper is primarily focused on the second question. So what we start with is the benchmark which is simply a set of samples (input-output pairs). Let $G(s)=\{{\mathrm{\Delta }}_i|{\mathrm{\Delta }}_i\text{ is a diagnosis of }s\}$. This defines the ambiguity group of a sample. The prior $p(G(s))={\sum }_{{\mathrm{\Delta }}_i\in G(s)}p(s)$. The prior single fault equation remains unchanged with the updated definition of $G(s)$

Some diagnostic algorithms return a posterior probability $V(\mathrm{\Delta })$ with each diagnosis. This requires a new approach, which we will discuss later.

So far we have penalized a diagnoser for false negatives, but not directly for false positives. But what should happen if the diagnoser returns a false positive, i.e., a diagnoser returns a non-diagnosis. An approach for this has been well studied in machine learning. One can construct a confusion matrix with the diagnoser’s results on the vertical axis and the actual faults on the horizontal. (This applies for both single faults and multiple faults.) Then accuracy, true positive rate, false positive rate, and precision can be defined in the usual way as in ML. This also needs to be adapted for ambiguity groups. In ML techniques like Top-k-accuracy can be used.

An approach which avoids the problems we have seen thus far is to base a metric on the difference between the true distribution of faults and the one determined by the diagnostic algorithm.

Let $Q(x)$ be the gold standard – the probability distribution which best approximates the state of affairs the single fault diagnoser encounters. Let $P(x)$ be the distribution the diagnoser reports. The most familiar metric is cross-entropy – which is used widely in ML to compare the predicted probability distributions. In our case, we want to compare how close the calculated probability distribution $P(x)$ is to the perfect one $Q(x)$. For this case, KL-divergence is a better metric:

If $P(x)$ and $Q(x)$ are identical, KL-divergence is $0$, unlike cross-entropy. One problem is that if the diagnoser assigns non-zero probability to a possibility which never occurs, then KL-divergence is indeterminate. So this is problematic as well.

We hope we have convinced you that all the sampling based metrics described in this section are problematic measures of a diagnoser’s capabilities. Although these metrics are often used because they appear to make sense on the surface, none of them is a decent scoring mechanism for a diagnostic algorithm. Instead, we argue diagnostic algorithms need to be scored based on the costs they incur in use.

Complementing an understanding of the problems associated with the metrics, we hope that we have convinced you also that the sampling strategy can have a strong impact on how we perceive some algorithms’ performances. When designing benchmarks, we thus also need to anticipate the issues discussed in this section and define a set of samples that keeps those issues within certain and well-understood limits. In this respect, we would like to point out also that there are diagnosis algorithms that consider multiple samples in one diagnostic process [24], such that $\mathrm{𝑆𝐷}$ would stay the same for all $s$ but $\mathrm{𝑂𝐵𝑆}$ would change. As Pill and Wotawa mused in [23], supposedly representative concepts for generating test suites like combinatorial testing could help with defining representative sample sets for such algorithms. Ideally, their employment would allow us in turn to explain not only some occurred faults, but to isolate all the faults present in a system via an integrated approach at constructing representative I/O scenarios and diagnosing the corresponding observations. Such related work could help us not only in exploring options to assess multi-scenario diagnosis algorithms, but also when facing the challenge of designing benchmarks for diagnosis algorithms in general.

As we concluded in Sec. 2.1, sampling has a major impact on how an algorithm performs. But there are also a variety of concepts for assessing the quality of a diagnostic process, and our choice can significantly influence how we perceive an algorithm to perform for a specific sample $s$ (and in general). In this subsection, our focus is on exploring the effects that a diagnosis algorithm’s results have on the repair process.

Let us start with single fault diagnosis scenarios, and this time, the algorithm returns a probability distribution $p(x_1),\mathrm{\dots },p(x_n)$ over the system’s components $x_i\in X$. These are the posterior probabilities given some specific observations. For example, a system of three components $\{x_1,x_2,x_3\}$ might have posterior probabilities $p(x_1)=0.1,p(x_2)=0.6,p(x_3)=0.3$. Assume for the moment that these posterior probabilities are the true ones. A simple repair approach might now replace $x_i$ in decreasing posterior probability order. We first replace $x_2$ (due to the highest posterior probability), and if the symptoms are not gone, we consider $x_3$, and lastly $x_1$. Assuming the cost of a replacement $rep(x_i)$ was unity, the estimated repair costs $C$ for these posterior probabilities are $rep(x_2)+rep(x_3)\ast (1-p(x_2))+rep(x_1)\ast (1-p(x_2)-p(x_3))=1+0.4+0.1$. More formally, we can express $C$ via the following equation for a given list $L$ of diagnoses ${\mathrm{\Delta }}_i$ that were sorted with decreasing probability.

This simple repair process takes advantage of the fact that repairing a single component and making all repairs suggested by a diagnosis ${\mathrm{\Delta }}_i$ is the same in a single-fault scenario. Obviously, we need to distinguish between the two for multi-fault scenarios though, which, in turn, requires us to adapt the repair strategy. Before we reason about such an update, let us first explore a sometimes hidden assumption though. That is, the assumption of whether we have Perfect Fault Understanding (PFU) when inspecting a component, or not.

In particular, similar to perfect bug understanding from the software engineering community (as it is relevant in a diagnostic context when assessing spectrum-based fault localization metrics), we have to decide whether or not we can assume the ability to recognize faults with complete certainty when inspecting some component. A simple illustrating scenario would be that of when we would inspect a software program by looking at a part of the code (the component), recognize the faulty code in it, and then fix the component’s code accordingly.
In the single fault case, we can observe whether the problematic behavior is gone when executing the system after the repair of some component $x_j$ (as suggested by a single-fault diagnosis $\mathrm{\Delta }$). So, without requiring PFU, we could just replace $x_j$ and avoid a detailed inspection and fault-oriented repair of $x_j$.
PFU would be an important assumption in multi-fault scenarios insofar, since we would need to replace all $x_j$ in a diagnosis $\mathrm{\Delta }$ to supposedly make the observed symptoms disappear. So, when checking the quality of the individual repairs via observing the system’s behavior, we would first have to repair all $x_i\in \mathrm{\Delta }$, and then we would observe executions of the supposedly fault-free system. Consequently, judging the situation after inspecting/repairing a single component $x_i$ from $\mathrm{\Delta }$ would require PFU of $x_i$.

A repair strategy for multi-fault scenarios could exploit PFU as follows. Choose a component $x_i$ that appears in many diagnoses and then investigate and, if needed, repair $x_i$. If $x_i$ was found to be correct in the inspection (due to PFU), all diagnoses ${\mathrm{\Delta }}_j$ containing $x_i$ can be discarded s.t. they get a probability of $0$, and the probabilities $P(\mathrm{\Theta })$ for all diagnoses that are still possible (with search space $\mathrm{\Theta }=2^X$) should be updated accordingly. We repeat this until the symptoms have gone, there is no diagnosis left, or until there is no component left to repair. Obviously, estimating the costs $C$ of this repair process is a bit more complicated than for a single fault scenario. That is, we need to constantly update $P(2^X)$ after investigating some $x_i$, and we have to statistically approximate the costs incurred when estimating $C$.

If we do not have PFU (like when we just swap components without inspection), we could simply walk through the list of diagnoses ${\mathrm{\Delta }}_i$ according to their probabilities and repair for each investigated ${\mathrm{\Delta }}_i$ all components $x_j\in {\mathrm{\Delta }}_i$. Extending our Eq. 6, we can approximate the average repair costs in this case as

with $rep(x_k)$ referring to the repair costs of component $x_k$. When following this process, one specific downside is that a certain component $x_k$ might get repaired more than once. That is, if it is contained in more than one ${\mathrm{\Delta }}_i$ that we had to investigate before arriving at the actual diagnosis (so that the system is finally repaired).

A supposedly better repair process would keep track of whether individual components have been repaired before, so as to avoid unnecessary repairs. However, this requires that a repaired component is not destroyed again during the repair process. That is, before all $x_i$ in the actual diagnosis have been repaired. In practice, this can easily happen, when the interaction of faults leads to the immediate destruction of a repaired component $x_j$ by some $x_k$ that has not yet been repaired. A simple example would be that of a fuse. The fuse could be immediately destroyed again if the problem that triggered it has not yet been taken care of. Considering such dependencies, the more naive and also supposedly more costly process could even be better suited (and cheaper) in practice for many applications.

Please note that the metrics we considered in this subsection are simplistic variants of the economic metric discussed in Section 4.

When researchers present a new algorithm, they often evaluate it in the context of a family of relevant algorithms and use specific metrics that allow them to show the validity and effectiveness of the proposed improvements over the state-of-the-art. This approach enables a clear and focused presentation of these improvements and allows the authors to adhere to the page limits of a conference at the same time. However, it comes with certain limitations.

Let us illustrate them with the example of RC-Tree [19]. RC-Tree is a diagnosis algorithm that implements a conflict-driven computation as first proposed by Reiter [25] as well as de Kleer and Williams [4] in their seminal papers. The computational concept behind RC-Tree is close to that of HS-DAG [10], but due to some additional reasoning in terms of a divide-and-conquer exploration of the search space, RC-Tree can avoid all redundancy in the search. Intuitively, any diagnosis candidate gets generated only via one tree-based exploration sequence (in contrast to HS-DAG that allows permutations), which results in a narrower search without losing important properties like completeness, soundness, being an anytime algorithm, or supporting an on-the-fly calculation of the conflicts. When evaluating RC-Tree, the authors proved (1) that it returns diagnoses adhering to Reiter’s theory in a sound and complete manner (see Defs. 4 and 5 in Section 3.1), and they conducted (2) an empirical evaluation that isolated the performance advantages over HS-DAG as encountered in practice. The algorithm’s run-time and the number of evaluated diagnosis candidates (which relate to tree nodes and thus memory consumption) served as metrics in those experiments. The resulting evaluation certainly meets one’s expectations in terms of elucidating the authors’ contributions. But it does not provide us with a holistic picture on how this algorithm compares to the entire algorithmic landscape. That is, in comparison to completely orthogonal concepts – like subsymbolic algorithms that would approximate probability distributions (see Section 2.1).

The use of metrics that focus, e.g., on repair costs (see Sec. 2.2) could provide a clearer picture, but those metrics are not suited for highlighting RC-Tree’s algorithmic improvements over the state-of-the-art. Experts can draw on their expertise to maintain their own educated picture of the algorithmic landscape. For example, since RC-Tree returns the same diagnoses as HS-DAG (which has been around for about four decades), we can infer that the repair costs and other aspects can be considered to be the same and that there is only a difference in the computational costs. Consequently, this allows an expert to put RC-Tree into perspective. A non-expert would hardly have the knowledge to make such deductions. Metrics and evaluations that are more informative from a global perspective could thus help them in establishing a holistic picture as quickly as possible. Only such a holistic picture would allow a diagnostician or engineer to make an educated decision when faced with the challenge of having to select the most suitable diagnosis algorithm for a specific diagnosis problem.

When we assess the performance of a diagnosis algorithm, we need to think not only about sampling and metrics, but we also need to know how the ideal results should look like. In this subsection, we focus on the latter, and we hope to convince you that this supposedly simple task is not as straightforward to address as it seems.

In order to illustrate some of the issues, let us have a look at a simple example in the form of the circuit illustrated in Fig. 1. It is a simplified variant of the $n$-buffer example from Sec. 2.1 and contains. two inverters. Assume that we can observe the input $i{n}_1$ and the output $ou{t}_2$ and let us consider three scenarios for an input value of $i{n}_1=\top /1/\mathrm{ℎ𝑖𝑔ℎ}$.

It is easy to see that the nominal output (such that both inverters work correctly) is $ou{t}_2=\top$. If we observe this expected output in practice, we must recall though that this would be the case also for some fault scenarios. That is, observability limitations (like that can’t observe $ou{t}_1$) might prohibit us to distinguish the nominal case from some fault scenarios. For our example, this would be the case for Fault Scenario 1 where Inverter 1 suffers from a stuck-at-zero fault so that $ou{t}_1$ is always $\perp$. The same is true for for Fault Scenario 2 where Inverter 2 suffers from a stuck-at-one fault. In both cases, the fault does not manifest in the observations, but this would require the input to be$i{n}_1=\perp /0/\mathrm{𝑙𝑜𝑤}$. Consequently, the nominal case, Fault Scenario 1 and Fault Scenario 2 form an ambiguity group (see Sec. 2.1).

A consistency-based diagnosis algorithm like RC-Tree [19], HS-DAG [10], or GDE [4] would report from this ambiguity group only the empty diagnosis which represents nominal behavior. In fact, the underlying computation concept of those algorithms entails that when using a weak fault model, any superset of a diagnosis $\mathrm{\Delta }$ is also an explanation. Thus they form sort of an ambiguity group with $\mathrm{\Delta }$ by default and are, in turn, not explicitly reported. From this example, we can easily see that we need to know how to interpret a specific algorithm’s results in terms of aspects like implicit ambiguity groups, and we need to decide how we would formalize this in the baseline.

Let us now consider Fault Scenario 3 which illustrates a special case of an ambiguity group. In this fault scenario, both inverters malfunction so that they act as buffers and pass their input values along instead of inverting them. For this double fault, we can easily observe that there is no input that can reveal it. That is, unless we would improve the observability. Either via monitoring the intermediate signal $ou{t}_1(=i{n}_2)$, or by adding a connection from $ou{t}_1$ to some circuit part that is connected to a different observable output.
In fact, we can observe that the system behaves exactly as intended on its observable interfaces not only for Fault Scenario 3, but for all I/O scenarios. In particular, the two faults cancel each other’s negative effects on the system’s output so that there cannot be any evidence of this double fault on the observable signals. Since the mutated system is I/O-conformant, we can refer to it as equivalent mutant [7].
From a designer’s perspective, such an equivalent mutant is among equivalent design choices for implementing the desired I/O behavior. This presents us with quite interesting challenges from a diagnostic perspective. That is,we need to explore the question of whether a diagnosis algorithm is supposed to report equivalent mutants as diagnoses or not, and, potentially, we need to identify the set of equivalent mutants.

For elucidating further issues, let us consider two general concepts for defining a baseline, i.e., (1) using the ground truth, and (2) defining/computing a golden set of diagnoses.

For the first option, we would use ground truth knowledge about the faults that are present in a system and would expect an algorithm to report it. Assume that we, e.g., have a simulation-based setup like we discussed it in the Introduction. Since we know which faults we injected and when, we could simply consider this ground truth as gold standard for the diagnosis algorithm’s results. This choice would be certainly intuitive and natural, but it comes with several problems, as we can illustrate using the above fault scenarios.
Consider Fault Scenario 3, where, no matter the input, a diagnosis algorithm is likely to completely fail if we do not consider implicit ambiguity groups. That is, since it will most probably report the empty diagnosis instead of the double fault.
But there are more issues. So, what if the faults have not manifested yet and there is potential subsequent behavior for nominal and faulty cases? That is, despite the fault being present we could have (a) for a stateless system that we might not yet have seen an input combination that manifests the fault(s) and (b) for a stateful system that we did not yet experience the delay that is necessary for the manifestation. While the baseline would indeed require the faults’ detection, the question is on which basis an algorithm would justify that it reports a related diagnosis? Would we consider the algorithm then to be (a) clairvoyant (see Sec. 3), does it simply report (b) a statistic assessment with corresponding probabilities for all the possible continuations and their fault combinations/diagnoses, or (c) should the diagnosis actually be considered spurious – despite being defined in the baseline?

Reflecting on these issues, we might thus rather choose to define the baseline via computing a well-founded set of diagnoses that takes into account limitations in terms of observability and diagnosability. Although this approach would allow us to address some of the issues mentioned above, it comes with increased computational costs and causes its own problems.
Let us consider first the diagnosis of a stateless system like the two-inverter circuit. If a system is stateless, its behavior depends only on the current input which means in a diagnostic context that we can diagnose each time step individually. The same holds then also for the computation of the baseline for which we can either use a proven algorithm or manual analysis. The split into independent computations allows us to address a potential scalability issue that could otherwise arise with larger systems and long computation sequences and their traces. With the focus on individual time steps, the sizes of $\mathrm{𝑆𝐷}$ and $\mathrm{𝑂𝐵𝑆}$ are minimized for each individual computation. Still, we need either an algorithm that can compute the baseline, or we need to manually inspect the diagnosis problem(s).
For a stateful system, the computational demands might be even higher. That is, we have to consider the entire history of observations and can’t split the execution into smaller problems for each time step. The simple reason is that this history is reflected in an internal (potentially unobservable) state [18] that is relevant for the system’s I/O relation. Like the authors did for [18, 9], we can still use one health state variable for the entire execution. And this allows us to constrain the exponential diagnosis search space to $2^X$ instead of $2^{X\times T}$ (for a weak fault model and a temporal horizon of length $T$). We might also not loose timing information when a fault manifests since this information might be present in the underlying computation (like in the conflicts when using RC-Tree).But the models for $\mathrm{𝑆𝐷}$ and $\mathrm{𝑂𝐵𝑆}$ will still grow linearly with $T$.
It is important to note that these scalability issues are further exacerbated when we evaluate diagnosis algorithms that consider not only one but a set of executions [24] – like when a diagnostic algorithm examines all failed tests after executing a test suite [23].

For our final argument, assume that we are investigating a live scenario and that we managed to compute the gold standard of diagnoses for all the individual prefixes. As we suggested in the introduction, we now have to decide how to penalize the various types of deviation from the baseline. We have, for instance, that the diagnoses reported could be over- or under-approximations of diagnoses in the baseline. Or there could be a delay in detecting a diagnosis, which would require us to compare the diagnoses reported for time step $t_i$ with the baseline for time step $t_j\ne t_i$. Accommodating these and a variety of other deviations entails another increase in the computational costs and it illustrates that we must not consider metrics and baselines in isolation. In Section 3.1, we will define the notions of near-soundness and near-completeness that will allow us to discuss this in more detail and to support automated reasoning in this context.

Note that the notation for some of our definitions deviates from what the reader might be familiar with from the literature and papers like [4, 25, 19]. The purpose of these deviations is to accommodate the results from as many diagnosis algorithms/approaches as possible, including results like diagnosis probability distributions that were computed under the consideration of strong fault models.

Assume that a system $\mathrm{𝑆𝐷}$ consists of components $x_i\in X$, and that we have some observations $\mathrm{𝑂𝐵𝑆}$ about the behavior of $\mathrm{𝑆𝐷}$¹¹1As usual, we will also formally refer to a system model with $\mathrm{𝑆𝐷}$ and it will be clear from the context whether we refer to the system in general or a model. As indicated in Section 2.1 and following the literature [4, 25], we can define from $\mathrm{𝑆𝐷}$, $X$ and $\mathrm{𝑂𝐵𝑆}$ a diagnosis problem $(\mathrm{𝑆𝐷},X,\mathrm{𝑂𝐵𝑆})$ where we, e.g., sampled over such diagnosis problems in Eq. 1. A diagnosis $\mathrm{\Delta }\subseteq X$ for a diagnosis problem points us to a subset of faulty components that can explain $\mathrm{𝑂𝐵𝑆}$. To this end, a diagnosis assigns each component $x_i\in X$ a mode $m_j\in M_i$, where $M_i$ is the finite set of modes in which a component $x_i$ can be.
$M_i$ must contain the nominal mode $m_{nom}$ and at least one fault mode. This can be the general fault mode $m_{gen}$, but also one or more concrete fault modes $m_k$. The general fault mode $m_{gen}$ implements a weak fault model [4, 25] that does not place any restrictions on the behavior of $x_i$ in the faulty case. In contrast, concrete fault modes pose concrete constraints on the behavior of $x_i$ also in the faulty case. Technically, there is no requirement to describe the exact behavior of a strong fault model but only some constraint. In practice, though, we tend to do so and define concrete faulty behavior – like a stuck-at-0 fault for a logic gate. As the respective authors outlined in [5, 25], exact strong fault models have advantages and disadvantages. For example, they indicate to a user what exactly happened. This information is certainly welcome during the inspection and repair of the system. When diagnosing specifications or design ideas, using a strong fault model allows us to even suggest repairs [18], which we can exploit in generative model-based diagnosis for design purposes as suggested in [17]. But the advantages are secured at the cost of an increased search space, since we now have not only two modes per component, but multiple ones. On an algorithmic level, we are then also limited by the chosen fault modes in our diagnostic search.
We consider nominal mode assignments in a diagnosis $\mathrm{\Delta }$ to be optional, so that we require only those tuples $(x_i,m_j)$ to be specified in $\mathrm{\Delta }$ that assign a non-nominal mode $m_j\in M_i\setminus \{m_{nom}\}$ to some component $x_i$. All components $x_i\in X$ for which $\mathrm{\Delta }$ does not contain an assignment tuple are assumed to be in nominal node. If we state that a diagnosis $\mathrm{\Delta }$ is a subset of $X$, like the definitions in [4, 25] suggest, we refer to the observation that $\mathrm{\Delta }$ defines a subset of components that are faulty.

Like in Section 2.1, we assume that the results of a diagnosis algorithm are given as a probability distribution $P(\mathrm{\Theta })$ over the diagnosis space $\mathrm{\Theta }$. The gold standard in terms of the expected results of an algorithm will be referred to as $Q(\mathrm{\Theta })$, where we discuss in Section 2.4 several concepts to define this baseline. If an algorithm algorithm does not report probabilities but only a set of solutions, a naive concept to create a distribution is to assign all diagnoses the same probability and non-diagnoses a probability of zero. More elaborate approaches would consider the components’ priors and a diagnosis $\mathrm{\Delta }$’s cardinality when computing $p(\mathrm{\Delta })$, but let us continue this discussion later in this section.
Based on the individual $M_i$ from Def. 1, the search space for diagnoses $\mathrm{\Theta }$ varies in its size and structure. Let us first consider the cases where $\forall x_i\in X:M_i=\{m_{nom},m_{gen}\}$, so that we implement a weak fault model. In this case, $P(\mathrm{\Theta })$ and $Q(\mathrm{\Theta })$ are distributions over the diagnosis space $\mathrm{\Theta }=2^X$. This space grows to $M^X$ if we implement strong fault models such that $M$ is a general set of modes for all $x\in X$. If the fault sets vary between individual components (which is likely to be the case in practice), we can use individual mode sets $M_i$ and $\mathrm{\Theta }={\mathrm{\Pi }}_{x_i\in X}{M}_i$ for a more precise characterization.

Soundness and completeness are important properties of any diagnosis algorithm $A$, since they capture whether (1) the diagnoses reported by $A$ are indeed diagnoses (in that they follow a formal definition like our Def. 1), and whether (2) the algorithm will return all diagnoses if it runs long enough. There’s an abundance of reasons why algorithms could be incomplete or unsound. Obvious examples are approximating concepts like subsymbolic approaches, but there are also well-founded analytic concepts. For example, if a diagnosis algorithm is tasked to derive one minimum-cardinality diagnosis, we usually employ optimizations that result in an incomplete search but where we can still guarantee that at least one minimum-cardinality diagnosis survives and that $A$ reports sound results [2, 6]. Another example would be that of computing all minimal conflicts between $\mathrm{𝑆𝐷}$ and $\mathrm{𝑂𝐵𝑆}$ (see [4, 25] for the underlying theory), and where we subsequently employ an approximating algorithm like Staccato [1] for computing diagnoses as the minimal hitting sets of the conflicts.

Assessing traits like completeness and soundness should thus be an integral part of any approach that assesses the quality of a diagnosis algorithm and its results, especially if we do not have detailed knowledge of the algorithm (or its implementation) but have to evaluate it anyway. Having white-box access to an algorithm and its implementation provides us with a powerful and intuitive approach to do so, i.e., by deriving formal proofs. In some contexts, such as competitions, we may have only limited knowledge about the diagnosis engine rather than detailed information about its implementation. But even if we would know the algorithm’s details, we need to be aware that a proof would most likely target the algorithm’s computational concept and seldomly its implementation. In this paper, we are thus interested in assessing soundness and completeness in the context of a diagnosis algorithm’s results, rather than proving these traits for the algorithm’s computational concept.
In the context of $P(\mathrm{\Theta })$ and $Q(\mathrm{\Theta })$, intuitively, soundness refers to the question whether a diagnosis $\mathrm{\Delta }$ reported in $P(\mathrm{\Theta })$ (s.t. $p(\mathrm{\Delta })>0$) is also a diagnosis in $Q(\mathrm{\Theta })$. When evaluating completeness, we need to verify that all diagnoses in $Q(\mathrm{\Theta })$ are also diagnoses in $P(\mathrm{\Theta })$.

It is easy to see that the two definitions support any diagnosis search space, but they do not take into account how the algorithms encode their results. In particular, as we observed in Sec. 2.4, some algorithms mention some ambiguity groups implicitly. That is, when using a weak fault model, algorithms like [25, 4, 19] report only ${\mathrm{\Delta }}_i$ for an ambiguity group defined by a subset-minimal diagnosis ${\mathrm{\Delta }}_i$ and all its supersets. That is, since all of ${\mathrm{\Delta }}_i$’s supersets would qualify as diagnosis according to our Def. 1 by default.
Continuing our discussion on how to generate $P(\mathrm{\Theta })$, we thus might have to enrich the reported set of diagnoses, like we suggested in Section 2.4. In the current case, we would derive all the missing probabilities for diagnoses that are entailed by the reported ones. All non-diagnoses are then finally assigned a probability of $0$. Please note that other algorithms might call for a much more elaborate post-processing.

It is intuitive that Definitions 5 and 4 leave no room for deviations between $P(\mathrm{\Theta })$ and $Q(\mathrm{\Theta })$ when we look at the respective sets of diagnoses. When considering our discussion in Section 2.4, the choices we make for defining the gold standard $Q(\mathrm{\Theta })$ could, however, result in the situation that even the most precise algorithm could not achieve completeness and soundness. Potential delays in diagnosability could be one of these reasons, i.e., when we consider the known ground truth about injected faults to define $Q(\mathrm{\Theta })$ and thus do not consider observability-related issues that would cause the faults to manifest on the observable signals (and thus in $\mathrm{𝑂𝐵𝑆}$) only after some delay (see Sec. 2.4).

To this end, let us introduce temporal and cardinality-oriented error bounds. Via those bounds, we can then define some maximum deviations in terms of temporal deviations or over- and under-approximations of a diagnosis. Within those bounds, we will consider the results to be near-complete and near-sound.

Near-completeness allows us to reason within a temporal scope for situations where we compute diagnoses for each individual time step $t_i$ of a stateful system’s computation (see our discussion in Sec. 2.4). For every diagnosis in $Q(\mathrm{\Theta })$ for time step $t_i$, we then search for matching diagnoses in $P(\mathrm{\Theta })$ for any time step $t_{j-{ϵ}_T}\le t_l\le t_{j+{ϵ}_T}$. This allows us to deal with delayed observability as well as with the potential clairvoyance (see Def. 14) of, e.g., subsymbolic algorithms. If we do not want to consider temporal deviations, or for the usual case of diagnosing the entire computation after it finished, we just have to set ${ϵ}_T$ to $0$. Via parameter ${ϵ}_C$, we can control the acceptance of over- or under-approximations of diagnoses ${\mathrm{\Delta }}_i$ from $Q$, such that $P$ would contain only super- or subsets of ${\mathrm{\Delta }}_i$. ${ϵ}_C$ allows us to define a limit on the difference in cardinality.

Similar to considering completeness within temporal and cardinality-oriented bounds, let us consider also soundness within such well-defined bounds.

When we discussed near-completeness as of Def. 6, we briefly mentioned that an algorithm might be clairvoyant. Let us briefly formalize such clairvoyance and let us connect it to strictly near-sound algorithms.

It is easy to see that a clairvoyant diagnosis means that the algorithm is by definition unsound, i.e., since there was no matching diagnosis for the same time step.

It is evident that the notions of near-completeness and near-soundness allow us to classify and compare some algorithms’ performance for a diagnosis problem via inspecting ${ϵ}_T$ and ${ϵ}_C$. That is, via their respective minimum parameters ${ϵ}_T$ and ${ϵ}_C$ that are required for achieving near-soundness and/or near-completeness. The lower the minimum values for the parameters, the better the algorithm. Via ${ϵ}_T$ and ${ϵ}_C$ we can thus establish partial orders in the sense that when we fix one of these parameters, the minimum values for the other parameter defines a natural order regarding their performance. For obtaining a total order, we would need a weighted metric considering ${ϵ}_{T_{min}}$ and ${ϵ}_{C_{min}}$, or we could take into account the entire set of all (minimal) combinations. For a representative verdict, some (weighted) average over a set of samples might need to be computed, implementing the discussion offered in Section 2.1.

Please note that the values for parameters ${ϵ}_T$ and ${ϵ}_C$ depend on each other, as can be seen from Corollaries 9 and 13. A consequence that we can easily observe is that we might need values for ${ϵ}_T$ that are higher than ${ϵ}_{T_{min}}$ for enabling near-completeness and/or near-soundness for some specific ${ϵ}_C$ (and vice versa).

We motivated our work in the Introduction with the complexity of finding correct and informative answers to the natural question of whether a specific diagnosis algorithm returned the correct result for some diagnosis problem, and if not, how good the results are. As we hope to have convinced you with our discussion in Section 2, providing the right answers is a complex task that requires us to take into account a wide variety of aspects.

Let us now discuss potential solutions to the problem at hand. In principle, we can observe that any solution needs to tackle two distinct problems:

• $\mathrm{■}$

  Task 1: We need to implement an oracle that judges whether the results are OK or not.

• $\mathrm{■}$

  Task 2: We need to quantify the quality of the results with a corresponding measure.

T1 and T2 can be addressed and answered independently, but we can also exploit synergies and tackle both tasks together. So we could use a quantitative metric for T2 and implement the oracle $O$ for T1 by a qualitative interpretation of the value obtained by the metric.

An intuitive and straightforward solution for the latter would be to consider $P(\mathrm{\Theta })$ and $Q(\mathrm{\Theta })$ and to sum up the absolute value of the differences between $p({\mathrm{\Delta }}_i)$ and $q({\mathrm{\Delta }}_i)$ when iterating through the diagnosis space $\mathrm{\Theta }$. We could adopt KL-convergence as of Eq. 5 in Section 2.1, we could sum up the squared absolute value such as to penalize larger differences, and we could adopt a large a variety of similar ideas with individual twists. That is, as long as we ensure that the final value is $0$ iff there is no deviation at all, we have a solution with the desired property. Obviously, this concept is not very robust against the influence of noisy computations. If we add some error bound $ϵ\in {ℝ}^{+}$ to mitigate some of the effects (see Eq. 8 for such an oracle $O$), we would still not be able to address the disadvantage that the metric (the sum in Eq. 8) does not distinguish between problems with different severity levels.

Let us elucidate the issue by considering the two following cases. For Case 1, assume that there is a very small deviation ${\delta }_i=|p({\mathrm{\Delta }}_i)-q({\mathrm{\Delta }}_i)|$ in the probabilities for some ${\mathrm{\Delta }}_i:(p({\mathrm{\Delta }}_i)>0\wedge q({\mathrm{\Delta }}_i)>0$. Case 1 refers thus to a scenario in which ${\mathrm{\Delta }}_i$ is a diagnosis in both $P(\mathrm{\Theta })$ and $Q(\mathrm{\Theta })$, but in which we observe a slight deviation between $p({\mathrm{\Delta }}_i)$ and $q({\mathrm{\Delta }}_i)$. In the context of a repair procedure, this difference might cause a change in the rank of ${\mathrm{\Delta }}_i$, which could in turn affect repair cost estimates (see Section 2.2). But we can easily see that $A$ neither missed to report diagnosis ${\mathrm{\Delta }}_i$ in $Q(\mathrm{\Theta })$, nor is ${\mathrm{\Delta }}_i$ a spurious diagnosis. Mathematically, we thus observe that the completeness and soundness of the results is not negatively affected by the difference in probabilities. Now let us look at Case 2, in which the probability for the same ${\mathrm{\Delta }}_i$ is $0$ for either $P(\mathrm{\Theta })$ or $Q(\mathrm{\Theta })$ and is ${\delta }_i$ for the other. In Case 2, while the difference is indeed the same as in Case 1, we can easily observe that the results $P(\mathrm{\Theta })$ are either incomplete or unsound, i.e., since $A$ either failed to report a diagnosis (if $p({\mathrm{\Delta }}_i)=0$), or it reported a spurious and thus unsound diagnosis (if $q({\mathrm{\Delta }}_i=0)$). The metric can, however, not distinguish Case 2 from Case 1 so that ${\mathrm{\Delta }}_i$ contributes in either case with the same ${\delta }_i$ to the computation.

An intuitive way to address the issue would be to employ a combination of such a simple quantitative metric and a formal assessment of completeness and soundness. Following up on our discussions in Sections 2.4 and 3.1, this might also call for inspecting near-soundness and near-completeness as of Definitions 10 and 6 instead, since this would allow us, e.g., to accommodate delays in the diagnosability of some faults.

In combination with this formal assessment, we could replace the metric in Eq. 8 with a much simpler one. First, we rank the diagnoses for $P(\mathrm{\Theta })$ and $Q(\mathrm{\Theta })$ respectively, and then subsequently count the ${\mathrm{\Delta }}_i$s for which there is a difference in ranking (taking into account ambiguity groups). This simplification would make the quantitative measure more robust to noise and slight deviations in the probabilities that do not change the ranking, while it already takes the effects on a repair process into account. There is an abundance of similar metrics, and in Section 4 we discuss with the economic metric a much more elaborate approach to quantify effects on the repair costs, and thus a metric that is closer in line with our repair-cost estimate discussion from Section 2.2.

It is easy to see that the combination of a formal assessment with some quantitative ranking could be realized in a combined metric that allows us to tackle T1 and T2 together, but also in individual solutions for T1 and T2. We could use the assessment of soundness and completeness for addressing T1, and employ a quantitative metric for T2. Approaches for T1 following the concept described above require us to know $Q(\mathrm{\Theta })$. In reality, this assumption is indeed a strong one and we may not be able to fulfill it in practice. Let us thus explore whether we might be able to assess completeness and soundness without knowing $Q(\mathrm{\Theta })$.

So, we can verify the soundness of a single diagnosis ${\mathrm{\Delta }}_k$, for example, by checking if the symptoms disappear after repairing all (necessary) $x_i$ as suggested by ${\mathrm{\Delta }}_k$. Connecting to our discussions around PFU in Sec. 2.2), such a ${\mathrm{\Delta }}_k$ is indeed sound. Furthermore, considering Def. 1, we do not need to verify whether $\mathrm{\Delta }$ is subset-minimal, since it is not required by our definition. For these two reasons, in general, ${\mathrm{\Delta }}_k$ should also be part of $Q(\mathrm{\Theta })$). That is, unless we break the hidden assumption that we consider the ambiguity groups of diagnoses and their supersets in a sensible way such that $Q(\mathrm{\Theta })$ would miss to contain also the relevant supersets of some diagnosis as diagnoses.
Please note that if we would desire subset-minimality in the diagnoses for a weak fault model computation, it would not suffice to simply check whether $P(\mathrm{\Theta })$ contains another diagnosis ${\mathrm{\Delta }}_l:{\mathrm{\Delta }}_l\subset {\mathrm{\Delta }}_k$ – like some diagnosis algorithms do. That is, this check works out for algorithms like RC-Tree [18] since they are sound and complete. But while completeness is ensured in those algorithm’s construction, it is not necessarily the case in our context.

Verifying completeness is also sometimes possible without knowing the expected results. For example, in cases where we have access to a precise system model that is suitable for working with a SAT, SMT or constraint solver. Assuming that we have, e.g., a behavioral model in some temporal language [18, 9] or a simple combinational circuit [4], we first compile $\mathrm{𝑆𝐷}$ and $\mathrm{𝑂𝐵𝑆}$ into a SAT problem as suggested in those papers (see also [13]), or into an SMT problem/constraint problem [16]. We then add blocking clauses for all diagnoses from $P(\mathrm{\Theta })$ and finally ask the solver to search exhaustively for a new diagnosis [13, 15]. If one is found, the results $P(\mathrm{\Theta })$ are incomplete, and otherwise they are complete.

We hope that we could convince you that there are many ways to tackle the problem at hand, despite all the challenges that we have to face. To illustrate this, we, indeed, discussed several options to implement the desired oracle (T1), as well as to quantify the quality of the results reported by a diagnosis algorithm (T2).