Accelerating System-Level Debug Using Rule Learning and Subgroup Discovery Techniques

$Range\,\,Analysis$ $(\it RA$) [15, 16] is an algorithm resembling $Rule\,\,Learning$ ($\it RL$) [5, 9] and $Subgroup\,\,Discovery$ ($\it SD$) [17, 31, 1]. From the algorithmic perspective, the main distinguishing feature of $\it RA$ is that it heavily employs $Feature\,\,Selection$ ($\it FS$) [10] in two basic building blocks of the algorithm: the ranking and basis procedures. The third basic building block in $\it RA$, the procedure called quality, is the technique borrowed from $\it RL$ and $\it SD$, where the selection of rules or subgroups is done solely based on one or more quality functions. As a consequence, $\it RA$ can directly benefit from advances in $\it SD,\it RL$, and $\it FS$ algorithms. These three procedures will be explained below.

For a numeric feature ${\cal F}$, $\it RA$ defines a single range feature as a pair ${\cal R}\equiv({\cal F},value\_range)$, interpreted as a binary feature ${\cal R}({s})\equiv{\cal F}({s})\in value\_range$, for any sample ${s}$. And for a categorical feature and level $l$, the corresponding single range feature is defined as ${\cal R}({s})\equiv{\cal F}({s})=l$. A range feature is a single range feature or a conjunction of single range features, also referred to as range tuples or simply as ranges. A range ${\cal R}$ covers a sample ${s}$ iff ${\cal R}({s})$ evaluates to true. In the latter case, we will also say that ${s}$ is in ${\cal R}$ or is captured by ${\cal R}$.

The main purpose of $\it RA$ is to identify range features that explain positive samples, or subsets (subgroups) of positive samples with the same root cause. The $\it RA$ algorithm generates range features that are most relevant for explaining the response, where ‘most relevant’ might mean (a) having a strong correlation or high mutual information with the response, based on one or more correlation measures; (b) explaining part of the variability in the response not explained by the strongest correlating features; or (c) maximizing one or more quality functions, which are usually designed to prefer ranges that separate subgroups of positive samples from negate samples; that is, a range is preferred if a majority, or perhaps a great majority, of positive samples are covered by the range and a great majority of negative samples fall outside the range. Important examples of quality functions include the ones defined below.

By treating a range ${\cal R}$ as a classifier that predicts the positive class for samples covered by the range and negative class for samples outside the range, one can apply the well known quality metrics for binary classification to characterize the quality of ranges. Below we list some of the well known and often used quality metrics for binary classification, where $TP({{\cal R}}),FP({{\cal R}}),TN({{\cal R}})$ and $FN({{\cal R}})$ denote true positive, false positive, true negative and false negative, respectively, $n({{\cal R}})$ denotes the samples count within range ${\cal R}$, $Pos$ denotes the positive samples count, and ${\cal N}$ denotes the entire samples count. Thus in this context one can interpret $TP({{\cal R}})$ as the count of positive samples covered by the range ${\cal R}$, $FP({{\cal R}})$ as the count of negative samples covered by the range, $TN({{\cal R}})$ as the count of negative samples not covered by the range, $FN({{\cal R}})$ as the count of positive samples not covered by the range, and $n({{\cal R}})$ as the count of samples predicted by ${\cal R}$ as positive. Then the concepts of quality defined for classification tasks can be defined for ranges ${\cal R}$ as follows:

• •

  True Positive Rate (orsensitivity, recall, or hit rate), $TPR({{\cal R}})=\frac{TP({{\cal R}})}{Pos}$

• •

  Predictive Positive Value (or precision) $PPV({{\cal R}})=\frac{TP({{\cal R}})}{TP({{\cal R}})+FP({{\cal R}})}=\frac{TP({{\cal R}})}{n({{\cal R}})}$

• •

  Lift $Lift({{\cal R}})=\frac{TP({{\cal R}})/n({{\cal R}})}{Pos/{\cal N}}=\frac{PPV({{\cal R}})}{Pos/{\cal N}}$

• •

  Normalized Positive Likelihood Ratio $NPLR({{\cal R}})=\frac{TPR({{\cal R}})}{TPR({{\cal R}})+FPR({{\cal R}})}$, where $FPR({{\cal R}})=\frac{FP({{\cal R}})}{FP({{\cal R}})+TN({{\cal R}})}$

• •

  Weighted Relative Accuracy $WRAcc({{\cal R}})=\frac{n({{\cal R}})}{{\cal N}}\cdot(\frac{TP({{\cal R}})}{n({{\cal R}})}-\frac{Pos}{{\cal N}})=\frac{n({{\cal R}})}{{\cal N}}\cdot(PPV({{\cal R}})-\frac{Pos}{{\cal N}})$

• •

  ROC Accuracy associated with Receiver Operating Characteristic (ROC)
  $ROCAcc({{\cal R}})=TPR({{\cal R}})-FPR({{\cal R}})$

• •

  $F_{1}$-score $F1Score({{\cal R}})=\frac{2\cdot PPV({{\cal R}})\cdot TPR({{\cal R}})}{PPV({{\cal R}})+TPR({{\cal R}})}$

• •

  Accuracy $Acc({{\cal R}})=\frac{TP({{\cal R}})+TN({{\cal R}})}{N}$

The RA algorithm works as follows:

1. 1.

   The $\it RA$ algorithm first ranks features highly correlated to the response; this can be done using an ensemble Feature Selection [10] procedure, we refer to it as ranking procedure and denote the number of features it selects by $nRanking$ (this number is controlled by user). In addition, $\it RA$ uses the $mRMRe$ [6] algorithm to select a subset of features which both strongly correlate to the response and provide a good coverage of the entire variability in the response; this algorithm selects a subset of features according to the principle of Maximum Relevance and Minimum Redundancy (MRMR) [7], we refer to this procedure as basis and denote the number of features it selects by $nBasis$ (this number too is controlled by user).

2. 2.

   For non-binary categorical features selected using the ranking and basis procedures described above, or optionally, for all non-binary categorical features, for each level a binary range feature is generated through the one-hot encoding. In a similar way, a fresh binary feature is generated for each selected numeric feature and each range constructed through a discretization procedure. These features are called single-range features. Unlike $\it RL$ and $\it SD$, in $\it RA$ the candidate ranges can be overlapping, which helps to significantly improve the quality of selected ranges. The $\it RA$ algorithm then applies ranking and basis procedures to select $nRanking$ and $nBasis$ most relevant single ranges, respectively; in addition, $\it RA$ selects single range features that maximize one or more quality functions – $nRanking$ single rage features per quality function used. We refer to the quality-function based selection of ranges as quality.

3. 3.

   For each pair (or optionally, for a subset of pairs) of selected single range features associated with different original features, $\it RA$ generates range-pair features which have value $1$ on each sample where both the component single-range features have value $1$ and have value $0$ on the remaining samples. $\it RA$ then applies ranking, basis and quality procedures to select respectively $nRanking$ and $nBasis$ most relevant range pairs.

4. 4.

   Similarly, from the selected single ranges and selected range pairs, the $\it RA$ algorithm builds range triplets, and applies ranking, basis and quality procedures to select most relevant ones. Ranges with higher dimensions can be generated and selected in a similar way.

$\it RA$ is implemented in Intel’s auto-ML tool EVA [15, 16]. It has been used for root-causing and design space exploration also in other areas of microprocessor design [23, 24].

For our root-causing application, the first priority is to find range tuples with high precision – preferably with the maximal precision $1$, since such a range tuple provides a clear explanation for the subset of positive samples covered by it (this explanation might or might not be the ’true’ explanation). The second priority is to find high precision ranges with high sensitivity (that is, high coverage of positive samples), since that way one can identify root-causing hints valid for many failures thus these failures might be solvable with the same fix – as a subgroup of failures with the same root cause. In addition, in general, range tuples with smaller dimension might be preferable among ranges with the same precision and coverage, as they give simpler explanation for the covered positive samples. Therefore, given a dataset with a binary label, that is, given ${\cal N}$ and $Pos$, it is convenient to view that the precision $PPV({{\cal R}})$ and coverage $n({{\cal R}})$ uniquely determine $TP({{\cal R}}),FP({{\cal R}}),TN({{\cal R}})$ and $FN({{\cal R}})$, thus all the quality functions above are expressible through precision and coverage.

In this work, in addition to quality function based selection, we suggest to use quality orders for prioritizing ranges for selection. In particular, we define Coverage Weighted Precision (CWP), or Weighted Precision for short, as a lexicographic order on pairs $(precision,coverage)$. That is, $CW\!P({{\cal R}_{1}})>CW\!P({{\cal R}_{2}})$ if and only if $PPV({{\cal R}_{1}})>PPV({{\cal R}_{2}})$ or $PPV({{\cal R}_{1}})=PPV({{\cal R}_{2}})\wedge n({{\cal R}_{1}})>n({{\cal R}_{2}})$. For binary responses, which is the focus of this work, CWP induces the same ordering as Positive Coverage Weighted Precision (PCWP) defined as a lexicographic order on pairs $(precision,positive\_coverage)$, where $positive\_coverage$ is the count of positive samples covered by the range feature. For numeric responses, there might be multiple suitable ways to define positive samples (see Section 6.2 in [16]), thus there will be multiple useful ways to define PCWP orderings. While $WRAcc$ prefers selection of ranges with high precision and high coverage, the ordering induced by $WRAcc$ is not equivalent to weighted precision. For example, consider dataset with ${\cal N}=80$ samples containing $Pos=20$ positive ones, and consider two range tuples ${\cal R}_{1}$ and ${\cal R}_{2}$, covering $TP({{\cal R}_{1}})=10$ positive and $FP({{\cal R}_{1}})=0$ negative samples, and $TP({{\cal R}_{2}})=13$ positive and $FP({{\cal R}_{2}})=7$ negative samples, respectively. Then $PPV({{\cal R}_{1}})=1$ is significantly higher than $PPV({{\cal R}_{2}})=0.65$, thus $CW\!P({{\cal R}_{1}})>CW\!P({{\cal R}_{2}})$, while $WRAcc({{\cal R}_{1}})=0.09375$ is smaller than $WRAcc({{\cal R}_{2}})=0.1$.

Coverage Weighted Lift and Positive Coverage Weighted Lift are defined similarly, and they define the same orderings as CWP and PCWP, respectively. Among two range tuples with the same $WRAcc$, one with smaller coverage has higher precision, therefore Coverage weighted WRAcc is defined as the lexicographic order on pairs $(WRAcc,coverage)$, while Precision weighted WRAcc is defined as as the lexicographic order on pairs $(WRAcc,1/coverage)$, or equivalently, on pairs $(WRAcc,precision)$. One can refine the remaining quality functions in the same way. The dimension of the range tuples can be added to these lexicographic orders as the third component in order to ensure that range tuples with smaller dimensions are selected first among tuples with the same precision and coverage.

We explain the main idea of how $\it RA$ helps root-causing on an example of Figure 2(a), which displays a binary feature $CLK\_OFF$, associated to event $Clk=0$, ranked highly by $\it RA$ and plotted for validator’s inspection. The dots in the plot, known as a Violin plot, correspond to rows in the input dataset, thus each dot represents a passing or failing instance of $PkgC8$ flow. Value $1$ on the $Y$ axis (the upper half of the plot) represents the failing tests and value $0$ (the lower half) represents the passing ones. The plot shows that when $CLK\_OFF=0$, that is, when signal $Clk$ was never set to $0$ along the execution of the flow instance, all tests fail! This is a valuable information that the validator can use as an atomic step for root-causing. The legend at the top of the plot specifies that there are actually $115$ failing tests and $0$ passing tests with $CLK\_OFF=0$, and there are $85$ failing tests and $247$ passing ones with $CLK\_OFF=1$.

Let’s note that the range feature $(CLK\_OFF,0)$ has precision $1$, as defined in Subsection 5.1, since it only covers positive samples (which correspond to failing tests). To encourage selection of range features with precision $1$ in root-causing runs, in $\it RA$ we use weighted precision along with WRAcc and Lift, which also encourage selection of range features with precision $1$.

During different stages of product development, the nature of validation activities might vary significantly. When there are many failing tests, the root cause for failures might be different for subgroups of all failed tests. In this case it is important to be able to discover these subgroups of failing tests so that failures in each subgroup can be debugged together to save validation effort. On the other hand, it is important to be able to efficiently debug individual failures. In our approach, the strategies of identifying subgroups of failing tests with similar root cause and putting focus on root-causing individual failures correspond to breadth-first and depth-first search strategies in the Root-Causing Tree ($\it RCT$) that we define next.

Our proposed procedure for root-causing regression failures is an iterative process and requires a guidance from the validator – or inputs from an oracle, to make the formulation of $\it RCT$ procedure formal – in order to decide whether the ranked root-causing hints are sufficient to conclude the root cause or further root-causing effort is required, including upgrading the initial dataset with more features according to what has been learned from the root-causing procedure that far. Generation of the ranked list of root-causing hints in each iteration of building $\it RCT$ (splitting a node in the current tree) is fully automated by using the $\it RA$ algorithm, but unlike the $\it RL$ and $\it SD$ algorithms, the input data to the $\it RCT$ procedure can change from one iteration of $\it RA$ algorithm to a next iteration. As a result, in $\it RCT$ procedure user guidance is explicit while data preparation and inspection of results are outside of the scope of $\it RL$ and $\it SD$ algorithms (thus $\it RL$ and $\it SD$ are deemed as fully automated even if the results are not satisfactory and rerun is required with a more appropriate dataset and/or different parameter values of $\it RL$ and $\it SD$ algorithms).

The iterative root-causing procedure is illustrated using Figure 2(b). More specifically, Figure 2(b) presents an $\it RCT$ of regression failures of $PkgC8$ with random wakeup-timer, which will issue an interrupt to trigger a wake-up out of $PkgC8$ flow. Using the procedure described next, after a few iterations, at the leaves of the tree we get subgroups of failures characterized by the length of the wakeup-timer and which actions were achieved. Initially, in the regression we see $200$ failing tests as one group of failing tests, and there are $247$ passing tests.

• (a)

  [Initialization] Initialize the root-causing tree $\it RCT$ to a node $n$, mark it as open, set the input dataset $D$ passed to the iterative root-causing procedure to the dataset engineered from traces as described in Section 4, and set the number of iterations $i=0$. Go to step $(c)$.

• (b)

  [Iterations] In this step, the procedure receives a four-tuple $(\it RCT,n,S,D_{S})$ where $\it RCT$ is the current tree, $n$ is a node in it selected for splitting, $S$ is the subgroup of failing tests associated to node $n$, and $D_{S}$ is the dataset to be used for splitting the subgroup $S$, with the aim to arrive to smaller high quality subgroups with different root cause or root causes each. $\it RA$ is performed on $D_{S}$ and the oracle chooses the best range feature to split the tree at node $n$. (Any range feature not identical to the response implies a split at $n$.) We add two sons to $\it RCT$: one will be associated with the subgroup of failing tests covered by the selected range feature, and the other one with the subgroup containing the rest of failing tests from $S$; both sons are marked as open. Increment $i$ and go to step $(c)$.

• (c)

  [Decisions]

  1. 1.

     If all leaves of $\it RCT$ are marked as closed, exit. Otherwise go to $(c).2$:

  2. 2.

     Choose a leaf node $n$ not marked as closed – this is the leaf targeted for splitting in order to refine the associated subgroup $S$ of failing tests. if the oracle decides there is no need to split $S$, that is, all failing tests in $S$ can be associated to a single root cause or $S$ is empty, then mark the leaf $n$ as closed and go to $(d)$. Otherwise go to $(c).3$:

  3. 3.

     Define $D_{S}$ as follows: if $i>1$, from the input dataset $D$ subset rows that correspond to failing tests in this subgroup and rows corresponding to the passing tests, to obtain dataset $D_{S}$. Drop from $D_{S}$ all features that were used for splitting at the parent nodes; in addition, drop the features that are identical to the dropped features, as well as features that are identical to the response (the class label), in $D_{S}$. Otherwise (case $i=0$), set $D_{S}=D$. Go to $(c).4$.

  4. 4.

     If there are no features in $D_{S}$ and no new features can be added, mark the leaf node $n$ as closed and go to step $(c)$. Otherwise, if $D_{S}$ contains all features relevant to $S$ (subject to the oracle’s decision), or no additional features are available, go to step $(b)$ with four-tuple $(\it RCT,n,S,D_{S})$. Otherwise go to step $(e)$ with four-tuple $(\it RCT,n,S,D_{S})$.

• (d)

  [Knowledge Mining] This step performs mining of knowledge learned along a closed branch of the root-causing tree, and it will be discussed further in Subsection 5.7. Then go to step $(c)$.

• (e)

  [Data Refinement] This step corresponds to the situation when the oracle wants to add more features that can potentially help to split subgroup $S$ further, and it will be discussed further in Subsection 5.6. Then go to step $(b)$ (with an updated dataset $D_{S}$).

Let’s note that in the root-causing tree of Figure 2(b), event $C8\_ACTIONS$ is not a flow-event – it does not occur in $PkgC8$ flow description. It helps to explain why some of the flow instances that successfully go through the $CLK\_OFF$ stage of the $PkgC8$ flow fail to complete the flow. Also, the events of the $PkgC8$ that should occur between $CLK\_OFF$ and $CORE\_WAKE\_TO\_C0$ do not occur in the root-causing tree. The root-causing tree therefore provides pretty neat and succinct explanations and grouping of the failures, and gives deeper insights compered to just identifying where in the flow the flow instance starts to deviate from the expected execution. As discussed in Section 4, the information that event $C8\_ACTIONS$ should occur before events notifying exit stages of $PkgC8$ flow can be mined as out-of-order features, optionally. During building the tree in Figure 2(b), this information was not coded as a feature in the input dataset $D$.

In each splitting iteration, the range feature selected for splitting can be multi-dimensional, such as pairs or triplets of feature-range pairs. That is, in general splitting is performed based on a set of events, not necessarily based on just one event. This will be discussed in more detail in Subsection 5.5. Each iteration is zooming into a lower-level detail of the flow execution and smaller set of modules of the system.

We note that the features identical to the response in dataset $D_{S}$ that are dropped from analysis in step $(c)$ are very interesting features for root-causing as they fully separate the current subgroup $S$ and the passing tests.

Our iterative root-causing procedure assumes that there are passing tests. This is a reasonable assumption but does not need to hold at the beginning of a design project. In such cases, unsupervised rule based or clustering algorithms can be used.

Finally, let’s note that at every iteration in the proposed root-causing procedure, we select only one range feature to perform a split. However, multiple range features can be selected and splitting can be performed in parallel (and then the root-causing tree will not be binary) or in any order (then the root-causing tree will stay binary and in each iteration we add more than one generation of children to the tree). This reduces the number of required iterations.

Consider the feature $signal\_y\_4$ in Figure 3(a), associated to event $signal\_y=4$, and feature $timer\_22159\_22714$ in Figure 3(b), associated to event $timer\in[22159,22714]$. While for a big majority of tests ($67$ out of $70$, in this case) the value $0$ of feature $signal\_y\_4$ implies test failure, there are a few tests ($3$ out of $70$, in this case) that are passing. So, the single range feature ${\cal R}_{1}=(signal\_y\_4,0)$ cannot fully isolate the failing tests from passing ones. As can be seen from Figure 3(b), the second single range feature ${\cal R}_{2}=(timer\_22159\_22714,0)$ cannot isolate failing tests from the passing tests either – along with $67$ failing tests, there are $106$ passing tests when timer does not occur at time range $[22159,22714]$. However, the range pair feature ${\cal P}={\cal R}_{1}\wedge{\cal R}_{2}$ (the conjunction of two binary features ${\cal R}_{1}$ and ${\cal R}_{2}$, as defined in Subsection 5.1) fully isolates the $67$ failing tests from the passing tests, because the $3$ negative samples covered by ${\cal R}_{1}$ and $106$ negative sample covered by ${\cal R}_{2}$ are disjoint. The range pair feature ${\cal P}$ is depicted in Figure 3(c), where the color encodes the ratio of positive and negative samples within the colored squares: the red color encodes positive samples and green encodes negative samples.

Usage of range pairs and range tuples of high dimensions can accelerate debugging as they allow to arrive to a root cause in fewer debugging iterations. On the other hand, the splittings of subgroups of failures associated to high dimensional range tuples might not match the intuition of the validator (the oracle’s decision) controlling the iterations in the root-causing tree. Thus the time spent by $\it RA$ algorithm (or other $\it RL$ or $\it SD$ algorithms which can be used instead of $\it RA$ at each splitting iteration) will be wasted. One useful heuristic of choosing ranges for next splitting iterations is to choose the range features with precision $1$ that originate from the flow-events as a default, without intervention of the validator, if such range features are selected by $\it RA$ as candidates for splitting.

To aid the validator in choosing the range features that are associated to well understood events, to every ranked candidate range features we associate a list of very highly correlated or identical features, with respect to $D_{S}$. Thus, instead of a highly ranked feature the validator can chose another representative with a clear interpretation. These strongly correlated or identical features are computed by $\it RA$ anyway, as a means to reduce the redundancy in the identified subgroups and to speed-up the algorithm [15, 16]. In $\it RA$, the usage of the $MRMR$ procedure helps to not miss interesting range features for splitting, when there are many features in the analysis. Finding diverse, non-redundant and concise sets of subgroups is an important direction in the $\it SD$ research [20, 30], and is very relevant in the context of minimizing the validator’s involvement as the decision maker in controlling the root-causing iterations.

For large systems with many modules, it might not be wise or feasible to generate upfront all features that can be engineered from traces, and include them into the initial dataset $D$ used in the first root-causing iteration. The root-causing iterations can also be performed in a hierarchical manner, and this is actually a preferred option which we adopted in our experiments.

In the hierarchical approach, during the initial iterations, one can choose to only consider features associated with some of the important modules as well as with observable signals on module interfaces, in order to include in analysis the features associated to all the flow-events in the flow of interest. And if root-causing hints collected so far indicate that the bug could be in a particular module or modules, features originating from these modules can be added to analysis (and optionally, features from some other modules can be dropped). This flexibility of refining the input data during root-causing iterations helps to keep the datasets analyzed by ML algorithms smaller and focused, and speeds up the root-causing iterations. In particular, when the iterative procedure arrives at step $(e)$, one could consider adding features originating from relevant modules if they were not present, or consider engineering more features associated to additional variables from the relevant modules, when possible, and then continue with step $(b)$, with tuple $(\it RCT,n,S,D_{S})$ received at step (e), but with the updated $D_{S}$. As an example, in the root-causing tree of Figure 2(b), the rightmost branch was closed with label $Reached\_last\_stage\_before\_C8$, because data from the respective module was not available at the time of initial experiments. Interestingly, when the relevant data became available and was added to analysis, further root-causing revealed that the corresponding regression test failures were not caused by a bug, instead, the self-checks in these tests were incorrect, and were fixed as a result of the gained insights during the root-causing iterations.

We note that there might be other useful ways to revise a current dataset, not covered by our algorithm, and it is not our goal to be exhaustive in that respect. For example, as mentioned in Section 4, feature engineering depends on the definition of the trace fragment associated to a flow instance, and our choice in this work was to define the relevant trace fragment upfront as part of data preprocessing step prior to $\it RCT$ construction, while we could make the definition of relevant trace fragment as part of the $\it RCT$ procedure, since identification of the most relevant fragments of trace to engineer features from it is also affected by the learning acquired as part of root-causing iteration performed so far.

In order to make root-causing easier for validators and to enable leveraging the knowledge accumulated during root-causing activities, we propose to mine validation knowledge as follows:

• •

  Maintain and improve a table associating their meaning with well understood events. This table is used to display the meaning of the events and event combinations associated to range features ranked highly by $\it RA$ algorithm when the latter are presented to the validator to choose the best root-causing hints and decide on next root-causing iteration.

• •

  Construct and improve a database or rules as follows: At step $(d)$ of the root-causing procedure, before returning to step $(c)$, the validator can assign a label to the respective subgroup of failures, and add a rule to the database of rules associated to the branch of the tree leading to that subgroup. The antecedent of this rule is the conjunction of conditions associated with the ranges along this branch and the consequent is the label of the subgroup $S$ at the leaf of this branch. As an example, the rule associated to the branch ending at node $Clk\_Off\_without\_C8\_Actions$ is written as:

  $$CLK\_OFF=1\wedge C8\_ACTIONS=0\longrightarrow Clk\_Off\_without\_C8\_Actions$$

The learned rules in the rule database can be used to predict root cause of test failures in future regressions by building predictive models from rules, using the algorithms developed under $\it RL$ or related algorithms such as [20] that combine $\it RL$ and $\it SD$ techniques for building predictive models from rules. An alternative approach is to train a model predicting the learned failure labels (failure labels learned during $\it RCT$ construction) once a rich set of failure labels and dataset $D$ engineered from passing tests and failing tests with these failure types are available, like this is done in previous work [22, 11] for predefined failure labels. In addition to the features in $D$, the range features corresponding to the left-hand sides of the mined learned rules can be used as derived features when training the model, since this can improve the quality of the trained model as was demonstrated in [16].

It is important to point out that the learned failure labels and rules added to the database are based on the intended behavior of the system and not on its current implementation. Thus, when the design is updated (say due to bug fixes), the design intent usually stays the same. Therefore, the failure labels and rules stay relevant as the design evolves, as long as the design intent is not changed. That is, the rules are more like the reference models or other types of assertions, but have the opposite meaning in that they capture cases of incorrect behavior rather than the intended behavior.

In our root-causing procedure, we did not discuss backtracking during the $\it RCT$ construction. When backtracking is not used, each subgroup of failing tests is split at most once, which can be done in a finite number of ways (in binary $\it RCT$ construction procedure, a subgroup is split in two subgroups or not split at all). Furthermore, steps $(a),(b),(d)$ transition to step $(c)$ which starts with a termination check, and step $(e)$ transitions to $(b)$ which then transitions to $(c)$. Therefore, assuming backtracking is not used and assuming step (b) succeeds by selecting a range that is used for splitting, it is straightforward to conclude that the $\it RCT$ construction will terminate (there will be no infinite loops).

In general, it can be the case that step (b) does not generate valuable root-causing hints and the validator cannot refine the subgroup at hand further. The most likely reason for this is that the used dataset does not contain relevant features. If that is the case, it is useful to backtrack to the same subgroup $S$ but upgrade the dataset $D_{S}$ by adding potentially relevant features, by going through step $(e)$. Otherwise, the problem might be due to incorrect splitting decisions taken earlier during $\it RCT$ constriction or poor quality of top ranked range features returned by $\it RA$, and in such cases too backtracking to an already visited subgroup might be useful. Assuming the number of features available for root-causing is limited and only a limited number of backtracking to an already visited subgroup is allowed, $\it RCT$ construction will always terminate.

Table 2 reports $\it RA$ results in the original root-causing activity after the first $\it RCT$ iteration on the dataset $Data8$ with $944$ features and $2826$ rows. Each row in the table corresponds to a selected range feature (the names of features and the selected ranges are not shown), and the first column $Dim$ shows the dimension of the range features – range features up to triplets were generated. Two heuristics for generating diverse set of ranked range features were used: (1) the number of ranges selected per feature was limited to $2$ (this is a default value and was used in all experiments); and (2) among the identical range features per dimension (range features that define the same subgroups but have different descriptions and might be associated to same or different original features in the data), only a single representative was used in further construction of rages of higher dimensions. Therefore the top ranked range features – the selected subgroup descriptions – are diverse, though the subgroups of samples that they define have overlaps. The remaining columns in Table 2 report the confusion matrix statistics and quality metrics defined in Section 5.1. The selected ranges were sorted according to weighted precision defined in Section 5.1. One can see that many ranges with precision $1$ have been selected, which include single ranges and range triplets. Actually, all the selected ranges were of high quality. The validator chose the highest ranked range for splitting, in order to further root-cause the seven false negatives (value $7$ occurs in column $FN$ in the first row of Table 2). The second iteration was $\it RA$ run on the dataset obtained by dropping all positive samples except the seven false negatives. With the ranges reported by the second $\it RA$ run, it was possible to split the seven test failures into subgroups of four, two and one failures, respectively, which resulted in full root-causing of all seven failures.

In Table 3 we present positive samples coverage information on all eight datasets in our benchmark suite. Table $\ref{pos_coverage_ppv_all_one}.a$ reports coverage information on positive samples (i.e., test failures) with single range features only, with $\it RA$. The first column lists the datasets, the columns $positives$ and $negatives$ report the count of positive and negative samples in the dataset, receptively, and they are included here for convenience. Columns $ppv\_min$ and $ppv\_max$ report the min and max values of the precisions (PPV) of the selected single ranges. To achieve a high level of diversity among the selected range tuples, in addition to the heuristics mentioned above, a heuristic method from [20, 30] was used to generate a diverse set of single ranges that penalizes selection of range features that cover samples already covered by earlier selected range features. In particular, in experiments reported in Table 3, the weight $w$ that controls the degree of penalizing coverage of a sample by $i$-th rule is computed as $w=\gamma^{i}$, where $0\leq\gamma\leq 1$ was set to $0.4$, and then (weighted) coverage for a candidate rule is computed based on the weights [20, 30]. Note that when $\gamma=1$ the heuristic has no effect, while $\gamma=0$ corresponds to ignoring the previously covered samples (or dropping them from the dataset). Columns $cov\_min$ and $cov\_max$ report the min and max coverage of positives samples by the selected single ranges (not all samples need to be covered with the same number of rules). The number of samples not covered by any of the selected single ranges are reported in column $not\_cov$, and for convenience in column $all\_cov$ we report number of all covered samples by single ranges. Each of the coverage columns $cov\_min,cov\_max,not\_cov$ and $all\_cov$ actually report two numbers separated by $``/^{\prime\prime}$: on the left to $``/^{\prime\prime}$ we report the respective coverage information for all the selected single ranges while to the right we present coverage information for selected single ranges with precision $1$. Range features with precision $1$ clearly separate a subset of positive samples from the negative samples thus they can be considered as high quality root-causing hints. From the data reported in columns $cov\_min$ and $cov\_max$ we see that for a single positive sample there are multiple selected single ranges with precision $1$, which means that there are multiple root-causing hints for these samples and each one of them can potentially point to the real root cause.

Table 3.b reports the same information as Table 3.a, except now it covers selected single ranges and range pairs, and Table 3.c reports the same information for all range features – single ranges, pairs and triplets. Table 3.d reports the same information obtained using pysubgroup $\it SD$, where the $depth$ parameter was set to $3$, to generate range tuples up to triplets, and the $result\_set\_size$ parameter for each dataset was set to the number of generated triplets in Table 3.c for $\gamma=1$. The latter choice is justified by the fact that pysubgroup $\it SD$ does not support the $\gamma$-based heuristic and with $\gamma=1$ this heuristic has no effect (in $\it SD$ and in $\it RA$). As it can be seen from Table 3.c, for datasets $1-3,7,8$ only very few samples remain not-covered by selected ranges with precision $1$, and they require an additional iteration of the $\it RCT$ procedure.