Separating passing and failing test executions by clustering anomalies

Program behaviours can be automatically checked against given invariants for violations. Therefore, invariants can be used as test oracles to find out the correct and incorrect output. Invariants are often inserted into the code by the developers, but this again can be a costly exercise and an additional burden at the time of coding. Daikon can be used to learn and infer invariants from program executions dynamically by using a collection of inputs (test cases), monitoring key values (class attributes, method entry and exit points, loop invariants etc.) and then making inferences from this large set of observations (Ernst et al. 2007). Sekar et al. (2001) proposed an approach to learn Finite State Automata (FSA) by using sequences of systems calls. Their approach deals with system security and is aimed at detecting anomalous sequences of system calls which are likely to point to intrusion attempts and malware. Hangal and Lam build up invariants over program variable from the executions of the passed tests and then use any violations of these invariants to identify potential bugs (using the DIDUCE tool) (Hangal and Lam 2002).

Chandola et al. (2009) define anomaly detection as a matter of spotting patterns in data that correspond to abnormal behaviour. This concept is illustrated in Fig. 3—the unfilled circles represent regions of normal behaviour, whereas the filled points represent anomalous data. The aim of the work reported in this paper to investigate whether software bugs generate a non-conformant pattern of behaviour that can be distinguished from the conformant or normal behaviour—in other words, in Fig. 3 do the groups of unfilled points corresponded to passed tests and the filled ones with failures? If this is the case, then the possibility of detecting bugs automatically can be raised.

The main principle of creating test oracles in this context is to hypothesise a formal model of program behaviours from sets of observations. There is a large body of work on using anomaly detection strategies such as clustering and classification techniques to support software testing tasks. However, these typically operate on quite different types of data set (e.g. execution traces), or utilise semi-supervised or supervised learning strategies (such as the presence of a previous version of the program). Consequently, the application of anomaly detection strategies in this context has not been extensively investigated (for a detailed review of anomaly detection techniques and applications see the work of Chandola et al. (2009)). The following subsections discuss some recent work in this area. The work in those subsections will be classified in to three main categories: (1) unsupervised learning techniques; (2) semi-supervised learning techniques; (3) supervised learning techniques.

Unsupervised learning techniques do not require training data and thus are most widely applicable. The techniques in this category make the implicit assumption that normal instances are far more frequent than anomalies in the test data. If this assumption is not true, then such techniques suffer from a high false alarm rate. Examples of such work include that of Dickinson et al. (2001, 2001) who demonstrated the advantage of automated clustering of execution profiles over random selection for finding failures by using function caller/callee feature profiles as the basis for cluster formation. This work is in turn based on that of Podgurski et al. (1999), who used cluster analysis of profiles and stratified random sampling to calculate estimates of software reliability and found that failures were often isolated in small clusters based on unusual execution profiles. Our work is similar to this and explores the same observed hypothesis about the distribution of failures over clusters, but we investigate the use of test case input/output pairs (and input/output pairs combined with execution profiles) from the system under test instead of execution profiles alone.

Semi-supervised learning techniques typically assume that training data has labelled instances for only the normal class (i.e. a subset of passing test cases needs to be identified). A model is built for the class that corresponds to normal behaviour and then used to identify anomalies in the unlabelled test data. Podgurski et al. investigate how bugs could be classified when represented by a failed test that had the same cause (Podgurski et al. 2003). Their approach worked based on the analysis of the execution profile corresponding to reported failures of the test and was built on top of their earlier unsupervised learning system. Bowring and colleagues proposed an automatic classification of program behaviours using execution data which aimed at reverse engineering a more abstract description of system’s behaviour (Bowring et al. 2004).

Supervised learning techniques assume the availability of a training data set which has labelled instances for normal as well as anomaly classes and is therefore the least generally applicable. However, this has been successfully used in regression testing where a reference version of the software exists which makes accurate data labelling possible. For example, Vanmali et al. (2002) trained a multi-layer neural network on the original software application by using randomly generated test data that conformed to the specification. When new versions of the original application are created and regression testing was required, the tested code was executed on the test data to yield outputs that are compared with those of the neural network. Frounchi et al. explored the possibility of using supervised learning as test oracle (Briand 2008) within the image processing domain.

The agglomerative hierarchical algorithm is an example of a clustering approach that aims to build a hierarchy of objects. The core principle of this type of clustering method is that the objects are more related to nearby objects (as defined by the distance metric) than to objects farther away. A hierarchical clustering method can be either agglomerative or divisive, depending on whether the hierarchical decomposition is formed in a bottom-up (merging) or top-down (splitting) fashion.

In both approaches the user can specify the desired number of clusters as a termination condition.

Density based spatial clustering of application with noise is an example of density based clustering approach, grouping together those objects that are close neighbours which allows it to find arbitrarily shaped clusters. Unlike agglomerative hierarchical clustering, the number of clusters can be determined automatically after specifying two key parameters: the minimum number of points in a cluster and the distance between them. The approach also supports the notion of an outlier—objects not belonging to any cluster. A cluster is defined as containing at least a minimum number of points (MinPts), every pair of points of which either lies within a user specified distance (\(\epsilon\)) of each other or is connected by a series of points that each lie within distance \(\epsilon\) of the next point in the chain. Smaller values of \(\epsilon\) yield denser clusters. Based on the value of \(\epsilon\) and the minimum cluster size, it is possible that some objects will not belong to any cluster (these outliers are considered as noise).

The EM clustering algorithm is an example of probability based clustering approach. In contrast to an approach such as k-means clustering, in which a fixed number of clusters (k) is given at the outset and objects are assigned to those clusters so that the means across clusters (for all objects) are as different from each other as possible, EM works purely from the set of objects without any a priori information to find the most likely set of clusters from a probabilistic perspective. EM operates iteratively to assign data objects to clusters and update the parameters of the probability distributions governing the various clusters until the best model is found.

Versions of three subject programs were used in this study: the NanoXML XML parser system, the scalable internet event notification architecture system (Siena), and the Sed stream editor. All are available from the Software Infrastructure Repository (SIR),⁴ are non-trivial systems, have several versions with well-documented faults embedded within them (these are either real or seeded—typically coming from faults in previous versions of the system), and also come with test suites—an important factor as having sets of good, but independently created, tests is vital for this experiment.

The main components of the experiment were: a set of programs with known failures, a set of test case inputs for each program, a way to determine whether an execution of each test was successful or not (passed or failed), and a mechanism for recording the execution trace taken through the program by each test. The seeded versions of the subject programs were run on the test cases to produce the associated outputs, and Daikon (Ernst et al. 2007) was used to obtain the execution traces. The resulting set of test case input/output pairs was augmented with their associated execution traces, transformed to reduce the volume of data (traces are often very large), and then analysed using several clustering algorithms. Knowing which data objects corresponding to failed test cases enabled us to determine how well the clustering algorithms performed. Each of these steps is described in more detail below.

Test case input/output pair collection The subject programs come with Test Specification Language (TSL) test suites and tools to run these automatically (details are available from the SIR repository and the article by Do et al. (2005)). Test cases which failed to produce any output were discarded (seven out of 214 for NanoXML, and 73 out of 567 for Siena, and seven out of 370 for Sed, giving final test case numbers of 207, 494 and 363).

Data transformation To be acceptable to the various clustering algorithms, the data requires processing before it can be analysed. The processing procedures differ from one data type to another—for instance numeric data sometimes requires normalisation. All systems used in the experiment work with textual input and produce textual output. Very often there is little semantic information in such data and a lot of noise, so to minimise the content (and redundancy) but still retain any uniqueness, the data (test case input/output pairs) were transformed by a simple process of tokenisation. The tokenisation method is widely used in the area of text mining to produce a suitable set of attribute vectors to build a classification model (a problem not dissimilar to the one we are dealing with) and is also suggested by Witten and Frank (2005). Several transformation methods such as hash coding, Huffman coding strategies and others were examined, but tokenisation turned out to be the most suitable one. Table 2 shows an example of this for NanoXML and Siena. Notice that the parameters for Siena commands were all encoded as “1” as they remained unchanged between input and output.

The Sed test data (input/output pairs) consists of a command line which contains 2 main parts: the parameters identifying the operations to be performed and a text file that needs to be modified which therefore forms both part of the input and output. Therefore, the data were transformed in a slightly different way compared to NanoXML and Siena: all input components remained unchanged except the filename (e.g. “../inputs/default.in”) which was encoded as the token “<1>” as the file itself contains only the text to be modified. Trying to tokenise the file to be modified (and its modified version) failed to reduce the size of the output sufficiently and so for output part the diff utility (a data comparison tool) was used to calculate the differences between the input text file and its modified form (this process reports how to change the first file to make it match the second file with specific operation that needs to be performed such as “a” for add and “c” for change). The magnitude of the compression achieved by this method is hard to quantify, depending as it does on the file and the modifications, but it typically yielded a much smaller representation of the output data. Table 2 shows an example of this coding strategy.

As explained earlier, each test input/output pair was augmented with its associated execution trace. Such traces are often very long (hundreds, and in some cases thousands of entries), and each entry in a sequence is often a full Java method signature including package name, class name, method name, and parameters (along with their respective long signatures). This required more compression than could be provided by simple tokenisation so the trace compression algorithm developed by Nguyen et al. (2013) was used. The algorithm replaces the collections of method sequence entry and exit values with their hash keys, consisting usually of just 1 or 2 characters. It takes into account the occurrence frequency to assign shorter hash keys for entries that are most frequent. Table 3 shows a sample of sequences for one of collected traces and their hash key values (for space reasons, just 3 sequences are included rather than all sequences of that trace) which are then concatenated to produce one single string. The obtained trace from the example in this table is 0LA37...

Finally all the data items can be combined into vectors that forms the input to the clustering algorithm. These vectors are built from two components for the first experiment (test input and output) and three for the second experiment (test input, output and execution trace). So if the NanoXML example from Table 2 above generated the trace fragment shown in Table 3, then the vectors would take the form of <FCRSSNRSS, F> for experiment 1 and <FCRSSNRSS, F, 0LA37...> for experiment 2. This structure is repeated for all the input/output [trace] combinations for each test case.

Perform clustering Agglomerative hierarchical clustering was used in experiment 1. The second experiment extended this to include also DBSCAN and EM clustering. Agglomerative hierarchical clustering has been used by other researchers for some similar types of problem and shown to perform reasonably well [e.g. Dickinson et al. (2001), Dickinson et al. (2001), Yan et al. (2010), Yoo et al. (2009)] and is also recommended by Witten and Frank (2005) as the most suitable solution for nominal and string data (which the coding systems produce for two subject programs). In contrast, DBSCAN and EM were chosen because of their ability to determine the number of clusters automatically rather than have to specify them at the outset (one of the limitations observed in the first experiment).

A range of distance measures were initially explored such as Euclidean distance, Minkowski distance, Manhattan distance and edit distance in order to establish the most suitable measure for the experiments proper. The first three were similar in terms of the performance and principle. However, edit distance did not perform well and agglomerative hierarchical clustering consistently assigned all input/output pairs into one cluster even when the clusters count was increased. After exploring these various alternatives, Euclidean distance was settled on as the measure of (dis)similarity between two objects. The WEKA toolkit⁵ used in this study computes this by converting all nominal attributes into binary numeric attributes. So, an attribute with k values is transformed into k binary attributes (using the one-attribute-per-value approach) (Witten and Frank 2005). Thus, all attributes values are binary: being either a numeric attribute or a synthetic binary attribute that is treated as numeric. The squared Euclidean distance sums the squared differences between these attributes: a zero sum indicates agreement (similarity), but a non-zero sum suggests a dissimilarity.

The consequence of choosing Euclidean distance is that nominal or categorical data (such as the inputs, outputs and traces used in these experiments) are only considered equal if they are identical. Any form of difference, no matter how small or large, causes them to be considered unequal. This means that two traces may differ in just one method call out of thousands but are considered as different as two that had no method calls in common. This might seem an odd decision but the rationale behind this is that even a slight difference in an execution trace may be indicative of an error. Using other measures would mean such a difference was hardly perceptible and could easily be missed. The impact of this decision, along with other distance measures, is something that needs to be explored further in the future.

In addition to a similarity metric, agglomerative hierarchical clustering requires a linkage metric which is used to determine when clusters should be merged or split. There are three approaches: Single Linkage calculates the minimum distance between an object in one cluster and an object in another, Average Linkage computes the mean distance between objects in the two clusters, and Complete Linkage is based on the maximum distance between objects. All three are explored in this study.

The number of clusters for EM is determined automatically by cross validation, a technique often used in classification (Witten and Frank 2005). A given data set is firstly divided into m parts. Next, \(m-1\) parts are used to build a clustering model, and the remaining part used to test the quality of the clustering. This process is repeated m times to derive clusterings of k clusters by using each part in turn as the test set. The average of the quality measure is taken as the overall quality measure. Then, the overall quality measure with respect to different values of k is compared to find the best number of clusters that fits the data.

The DBSCAN algorithm uses two specified parameters (\(\epsilon\): the radius parameter, and MinPts: the neighbourhood density threshold—see Sect. 4.2) to determine the number of clusters automatically. For our experiments, we found that the parameters which gave the best results were \(\epsilon\) = 1.5 and MinPts = 1.

The performance of the clustering algorithms can be assessed by looking at the way that failures are distributed over the small clusters (the definition of “small” is flexible so what follows is a general definition). To capture more accurately for this experiment, we used the F-measure—a combination measure of Precision and Recall (widely used measures in information science domain). These measures in turn rely on the concepts of true positives (TP), false positives (FP) and false negatives (FN) which are defined in this context as follows:

Precision is defined as the ratio of “correctly clustered” failures (i.e. failures that appear in small clusters) to the sum of all the entries in the small clusters:Recall is the ratio of “correctly clustered” failures to the total number of true failures (failures appearing in both small and large clusters):The F-measure—the harmonic mean of precision and recall—combines these two as follows:In this study, we have defined small clusters as those being of average size or less (i.e. the total number of passing and failing outputs divided by the number of clusters). Further work in this area will explore other values of small.

To illustrate the process of the evaluation, we introduce a small example which shows how the small cluster size, precision, recall and F-measure are computed. Assume that a system under test generates 21 data points during execution of its set of test cases. The system contains three faults (referred to as F1, F2 and F3) which cause failures which appear in the output 4, 4 and two times respectively. The remaining 11 test outputs were all passes (we do not need to distinguish amongst these). Again assume that after applying clustering, six clusters were created which grouped the outputs as follows: (f1, f2, f3, p, p, p), (p, p, p, p, p), (f1, f2, p, p), (f1, f2, p), (f2, f3), (f1), where fn corresponds to a failure associated with fault n and p corresponds to pass execution. This can be illustrated graphically as shown in Fig. 4 (where the clusters are sorted in increasing order of size on the y-axis and the “cluster count” legend is just an arbitrary value allocated to a cluster). This representation allows us to see the distribution of failures over the clusters.

The key values are computed as follows:

The first question to explore is whether failures are distributed in a random pattern or whether they tend to congregate in the smaller clusters as hypothesised. Figures 5, 6, 7, 8, 9 and 10 show bar charts representing the cluster size and composition for all versions of NanoXML, Siena (faulty version 2), and Sed using agglomerative hierarchical clustering with average linkage. The results are interesting and in several cases (NanoXML versions 2 and 3 and Siena version 2) it can be seen from these that failures in the test input/output pair population tend to cluster together and these clusters tend to be the smaller ones. This effect is less pronounced in NanoXML versions 1 and 5 where the smallest clusters also tend to contain more of the passing cases. The pattern for Sed is quite different—there are a very large number of small clusters rather than a gradually increasing distribution as in the other cases, and these contains a mixture of both passing and failing cases. Overall there is some support for the main hypothesis behind this work, that failure tends to gravitate towards the smaller clusters but it is by no means universal. The following sections examine this in more detail.

To investigate this observation further, we examined the population of input/output pairs that were in small clusters (defined as being of average size or less) and corresponded to failures. Tables 4 and 5 show, for varying numbers and sizes of clusters over all systems and for the three different linkage metrics that may be used with agglomerative hierarchical clustering (Average, Single and Complete), the percentage of all data points corresponding to failures. The first column (Cluster Count %) defines the number of clusters the algorithm is charged with creating expressed as a percentage of the number of test cases. So, for NanoXML a value of 10 in the Cluster Count % corresponds to 21 as it has 207 tests, for Siena this would be 50 as it has 494 test cases, and for Sed which has 370 tests it would be 37. The second column (Cluster Size %) is the average size of the clusters that are created by the algorithms, again expressed in terms of the number of tests. So as the values in Cluster Count % column increase, so do the number of clusters created which leads to a corresponding decrease in the average size of the clusters. The subsequent columns refer to the version number of the program. Note that the faults in Siena changed the same output data in all versions, even though they are distinct faults, so only the results from one version are considered since there is nothing to be gained from examining the other versions.

Considering the results for NanoXML (Table 4), the data shows that when the cluster counts are between 15 and 25 % of the number of test cases (corresponding to cluster sizes of around 3 % of the number of test cases—i.e. around six data points for NanoXML), well over 55 % of the data points are failures irrespective of which linkage metric is used, and over 60 % when the average linkage metric is employed. For Siena (Table 5) a similar pattern emerges but the best results are at the higher cluster count levels (20–25 %, possibly due to the larger number of test cases which gives an average cluster size of around 4) and tend to be over 70 %. The results for Sed (Table 5) are less dramatic and although a similar trend is displayed the failure density never reaches 50 %, peaking at just over 40 % when the complete linkage metric is used with an average cluster size of about 3. From the graphs shown earlier (Fig. 10), it was observed that Sed contained a very large number of small clusters and only one large cluster, rather than a steadily increasing cluster size which suggests that the data is very fragmented and the algorithm is clearly struggling to form larger groups of data items.

Even with the results from Sed, the findings lend support to the main hypothesis of this paper: As the number of clusters increases and their average size decreases, so the failure density of the small (less than average) sized clusters tends to increase. One case where this is not quite true is version 3 of NanoXML where the largest clusters contained the most failures: the input-output pairs corresponding to failures are so distinct from the rest that they were all grouped into one cluster (an impressive but probably unusual case!).

Tables 6 and  7 show the results of clustering test inputs and outputs using the Expectation Maximisation and DBSCAN algorithms, respectively. Unlike agglomerative hierarchical clustering, neither of these algorithms require the number of clusters to be specified in advance. The results show that EM performs well with all versions of NanoXML but less so with Siena and very poorly with Sed. Interestingly, for NanoXML the number of clusters created is close to the best number when specified for agglomerative hierarchical clustering. The results for DBSCAN are weaker for NanoXML and very poor for Siena but extremely encouraging for Sed, generating both a very high failure density in the smallest clusters and a reasonable F score. In the case of Sed DBSCAN has generated a very large number of small clusters (matching the pattern observed earlier in Fig. 10)—almost twice the number that was explored using agglomerative hierarchical clustering, which confirms our earlier observations about the data being very fragmented.

Although general pattern is for failure intensity to increase as the cluster size decreases, a trend which can also be observed in Figs. 11, 12 and 13 which present the percentage of failures found in the small clusters with different cluster counts in the subject programs (essentially a graphical summary of the data that appears in Tables 4 and 5), there are cases where the failure intensity peaks and then begins to drop (although not substantially) as the clusters are forced to fragment. An important lesson from this study is that the cluster size is crucial: too few and the technique may be ineffective but too many may cause the failure intensity to diminish as the clusters are forced to fragment. Identifying the ideal number of clusters (or similarly, the best parameters for algorithms such as DBSCAN) is something which needs further empirical investigation to establish.

From the perspective of supporting the practising software engineer in their work and also in the construction of a test oracle, the interesting question concerns the return on investment: how many outputs need to be examined before a reasonable number of failures are observed? To answer this we examined in more detail the proportion of failing outputs appearing in the smallest sized clusters. The absence of a fault matrix for Siena makes this very time consuming to compute; therefore, only the results for the highest failure density clusters for NanoXML and Sed have been calculated so far. The results of this are summarised in Tables 8 and  9 and show the cluster size (the three values correspond to the absolute size of the cluster, the number of clusters of that size, and the size of the cluster and proportional to the test set size) and details of the failures found (the proportion, the actual failures indicated by ‘Fn’, and the number of occurrences of each failure). Failures associated with a new fault (i.e. not previously encountered) are indicated in bold font. The final column shows the cumulative count of unique faults observed (via their associated failures) over the total number of faults in the system. So, for instance, the first entry of Table 8 shows that for Version 1 using 25 % of the number of test cases to define the number of clusters, there were 13 clusters each of size 1 corresponding to 0.48 % of the number of test cases, containing failures 1 (three times), 2 and 6 (once each), giving a cumulative count of 3 out of a total of 7.

Table 8 shows that on average over all four versions a fair proportion of the failures—45 % (13/29)—are contained within the very smallest clusters (formed from just one or two items). This is encouraging from a test oracle perspective: out of 43 outputs, 23 correspond to failures giving a failure density of 53 %. This initially good rate tails off until the cluster size reaches 4 and additional failures appear in the outputs (except for version 5). By this point an average of 66 % (19/29) of the failures have appeared in the clusters, albeit at the expense of having to examine more non-failing outputs and encountering duplicate failing outputs (but still giving a failure density of around 59 %). This failure density figure, combined with the fact that clusters tend to contain outputs associated with the same failure, means that in practice less than half of the outputs from a small cluster need to be checked before a failing output is encountered.

The results for Sed (Table 9) are less impressive but nevertheless encouraging. Even though the failure density is lower than for NanoXML, the failures are well represented in the smallest clusters: by examining these 3 out of the 4 failures would be encountered. On the downside the outputs of 62 small clusters (all of size 1) need to be checked, but this is still far less work than examining all 370 test outputs.

Of course, there are still additional failing outputs embedded in the larger clusters which cannot be ignored. This is clearly a weakness of the approach and one of the main topics of future work is to explore how these can be teased out into smaller clusters. A further feature of the clustering is that there is often number of independent clusters associated with the same failure (separated typically because the input/output pairs have different attribute values). This is also a challenge since finding the same failure appearing in several clusters can be quite frustrating for the individual charged with the task of checking outputs. Merging them together is not the answer as this will typically result in a larger cluster which may escape scrutiny, so some way of indicating similarity between them needs to be explored.

Again, the first major question to explore is whether failures are distributed in a random pattern over the clusters or whether they gravitate towards the small clusters as hypothesised. To examine this a sample of the results are shown visually—space prohibits the inclusion of all the results, but the full set is available online.⁶ Figures 14, 15, 16, 17, 18 and 19 show bar charts of the cluster composition for NanoXML (all faulty versions), Siena (just faulty version 2 as 4 and 6 produce an identical pattern as mentioned before) and Sed, where failing outputs are coloured blue and passing ones yellow. In these cases the cluster count for NanoXML is set at 15 % of the number of test cases (producing approximately 30 clusters), 20 % for Siena (producing just under 100 clusters) and 25 % for Sed (producing just over 90 clusters). In all cases the results are using agglomerative hierarchical clustering (DBSCAN and EM clustering algorithms were also used but tended to perform relatively poorly—something which is explored in more detail later).

It can be seen from these results that as in experiment 1 the failure data do tend to cluster together and these clusters are the smaller ones in most cases. There are some exceptions to this: for example for NanoXML version 5 the very smallest clusters are dominated by non-failing outputs, whereas the converse is true for the other versions, and in all cases of NanoXML some failures creep into the largest clusters. The results for Siena are more consistent with a clear tendency for failures to gravitate towards the small clusters and away from the larger ones. The results for Sed are similar to experiment 1—many small clusters and one large cluster but this time with a few intermediate-sized ones. It must be stressed that these are selected, and very high-level, results (although others reflect a similar pattern) but it would seem that a substantial number of failures congregate in small clusters. The detailed composition of these small clusters is examined in more detail in the next section.

This apparent observed tendency for failures to gravitate towards the smaller clusters need to be explored in more detail: the precise degree to which it occurs; the impact of the different clustering algorithms and parameters (especially the number of clusters); and particularly the way that multiple failures are distributed (for example, in the case of several failures do they all appear in the small clusters or is one failure dominant?). To explore this principle further, we examined the population of the small clusters (defined as being of average size or less) for each of the algorithms, identified the percentage of these clusters that correspond to failures, and also used the F-measure to answer the point about the way that multiple failures are clustered.

Tables 10, 11 and 12 show, for NanoXML, Siena and Sed respectively, the results of applying agglomerative hierarchical clustering for different linkage metrics with varying numbers of clusters. The tables show the percentage of all data points in small (less than average sized) clusters that correspond to failures, and the F-measure for the small clusters. The percentage figure gives an indication of the failure density and the F-measure adds to this by considering the range of faults that are revealed by failures that appear in the small clusters (for NanoXML there are seven faults in versions 1–3 and eight in version 5). The first column (Count) defines the number of clusters the algorithm is charged with creating expressed as a percentage of the number of test cases. The second column (Size) is the average size of the clusters again in terms of the number of test cases. The cluster count figure has to be supplied as a parameter, whereas the size figure is a consequence of the number of clusters and is not controllable. The subsequent columns refer to the version number of the programs and % and F refer to the percentage of failures and the F-measure. The figures in bold italics indicate the high values.

The data for NanoXML shows an interesting bi-modal response: the best results occur when there is either the smallest number of clusters (1 % which corresponds to two clusters) or when the cluster counts range between 10 and 25 % of the number of test cases (yielding between 20 and approximately 50 clusters). When the cluster count is very small, the algorithm will generate two large clusters (these will be of similar size but the smaller one is always treated as the small cluster) and in some cases one of these is composed entirely of failures and the other of passing outputs (those where the F-measure has a value of 1)—in other words the algorithm has managed to perfectly separate the passing and failing executions. These impressive clusterings were investigated in more detail and found that in version 2, 3 and 5 of NanoXML, all failing outputs follow exactly the same path through the program (despite being different faults generating distinct outputs) and the algorithms were perfectly separating the results based upon the execution trace. Even though this is probably a rare occurrence, it clearly demonstrates the power that execution traces can bring to this process.

As the cluster count increases so the results tend to drop quite dramatically until they pick up at around the 15 % level (\(+/-\)5 %) before tailing off again. In this range, the average small cluster sizes are between 2.73 and 6.39 % of the number of test cases—around 5 to 13 elements and it is worth noting that well over 60 % – sometimes far more—of the data points are failures. This again lends support to the experimental hypothesis behind this work that failures tend to congregate in small clusters. Another notable point is the fact that the F-measure tends to vary in line with the percentage of failures (and in all but one case the highest F-measure is also the highest percentage of failures), indicating that the failures associated with the numerous faults are evenly distributed across the small clusters. This is important as it could have been the case that the small clusters were dominated by a small and unrepresentative number of failures. The exact composition of these clusters will be explored in more detail later. It is also notable that both the linkage metrics and the versions of the program have an impact on the results, but the best overall and most stable results are produced by using the single linkage metric with a cluster count set at 15 % of the number of test cases.

The results for Siena (Table 11) tend to follow a similar pattern: in some cases the smallest number of clusters (5) tend to perform well and again manage to perfectly separate the data (once again this result is down to the passing and failing outputs being completely separable by their traces), but in other cases (with the single linkage metrics) they perform very poorly. The data for Siena also support the key hypothesis behind this paper with the cluster counts between 5 and 25 % of the number of test cases consisting of over 70 % failures. In contrast to NanoXML there is less of an impact of version (probably due to each having just a single failure) but like NanoXML the linkage metrics influence the findings, with the single linkage producing the least consistent results and the complete linkage the best. The reasons behind this are unclear and need further investigation.

The picture for Sed is similar to that for experiment 1—a gradual increase in failure density and F-measure as the cluster size drops but a much lower overall failure density value than was observed in the other two projects. Including the trace information has not produced any dramatic results as with NanoXML and Siena as there is no dominant pattern of traces arising from failing executions.

The results of using EM and DBSCAN to perform the clustering are shown in Tables 13 and 14. The first column (systems) defines the subject programs with their version number. The second and third columns identify, as in the previous tables, the number of clusters and the average small cluster size again in terms of the percentage of test cases. The key difference in this case is that the cluster count is determined automatically by the algorithm. The final column shows the percentage of failures in the small clusters and the F-measure for each algorithm. With the exception of version 1, DBSCAN performed well on NanoXML: for version 2 the result was equal to the best found using agglomerative hierarchical clustering, and versions 3 and 5 were close to the best. It is also notable that the cluster count chosen was 15 %—identified as the best compromise for agglomerative hierarchical clustering. The trace information in version 1 is far more diverse which may explain the less impressive performance in this case. The results for Siena are consistent but far inferior to those produced by most of the different cluster size parameters using agglomerative hierarchical clustering. Sed produced the most disappointing results for this algorithm—far worse than when it was operating on test input and outputs alone which suggests that the clustering seems to be fragmenting the data further and is something that needs to be explored in future work. The findings for EM are very disappointing, with the odd exception of NanoXML Version 1. In the majority of cases, the algorithm failed to apportion any of the failures into the smallest clusters and also elected to use a very small number of clusters.

As in experiment 1, the practical utility of the approach and the return on investment was explored: how many outputs need to be examined before a reasonable number of failures and associated faults are observed? To answer this we examined in more detail the precise composition of failing data appearing in the smallest sized clusters—in other words which failing outputs appeared in which clusters.

The results of this analysis for NanoXML (with a clustering size of 15 % using agglomerative hierarchical clustering⁷) are shown in Table 15 (which takes the same form as Table 8 in Sect. 6.3). The three figures in the leftmost column show the absolute size of the cluster, the number of clusters of that size, and the size of the cluster proportional to the test set size (note that the table is presented in increasing order of cluster size and includes only clusters which are of less than average size). The second column identifies the failures found (indicated by ’Fn’) and the number of occurrences of this failure. Failures associated with new faults (i.e. those not previously encountered) are indicated by a bold font. The final column is a cumulative count of the number of faults observed after examining the cluster over the total number of faults in the system. For example, the first entry of Table 15 shows that for Nanoxml Version 1 using 15 % of the number of test cases to define the number of clusters, there were ten clusters each of size 1 corresponding to 0.67 % of the number of test cases, containing failures 1 and 2 (2 times each) and 6 (once), giving a cumulative count of 3.

The NanoXML results show a number of failures appearing in the smallest clusters with additional ones appearing after examining just a few more clusters (with the exception of version 5). This is an important finding as it suggests that those failures which are going to be observed tend to appear relatively early in the ordering of clusters. This has important practical implications: collectively these smallest clusters correspond to between 25 and 30 % of the total output of the system, and the observed failures appear in an even smaller grouping, which means that the majority of failures in a system can be identified by looking at between one-fifth and one-quarter of the output—a substantial saving in effort for the developer.

The results for Siena are included in Table 16 although since Siena contains just the one fault the impact is less pronounced (and just one version is included since the results for other two are similar). However, it does show that the observed failures also tend to be concentrated early on in the small clusters and have the same implications as the NanoXML results.

The findings for Sed are shown in Table 17. The pattern is similar to the first experiment but the number of clusters to be examined has dropped very slightly. Again there are clear practical benefits: 75 % of the program’s failures are concentrated in about 16 % of its results.

One key factor in this study is the failure density. As mentioned in Sect. 5.1, this is between 31 and 39 % for NanoXML and 17 % for Siena. This failure rate is a factor of the combination of test cases supplied for the two systems and the nature of the faults embedded within the systems. However, in practical terms, this may be too high. The expectation is that this approach would be applied to a relatively mature system which may not have many obvious faults, and consequently a much smaller failure rate. Furthermore, an assumption behind anomaly detection is that anomalous events are relatively rare, whereas in these experiments the failure rate has been fairly high, so may represent a difficult case for the successful application of clustering techniques. To explore the impact of this, we took two versions of two of the systems—NanoXML V3 and Siena V4 (Sed was ignored as it demonstrated a similar failure rate to Siena)—and randomly pruned out fault revealing test cases to systematically reduce the failure rates to 10, 5 and 1 % for each system.

The results for this part of the investigation are shown in Tables 18 and 19 which, for each system, shows the cluster size, again in terms of the percentage of test cases (but note that the actual number of clusters will decrease as the failure rate decreases as test cases are being pruned from the suite), and the percentage of failures found and F-measure over the small clusters for failure rates of 10, 5 and 1 %. Both systems exhibit a similar distinctive pattern: as the failure rate decreases the recall (percentage of failures found) tends to remain high but the F-measure drops as the cluster count increases. The reason behind this is that with an increase in the number of clusters the false positive rate also increases as more passing tests become classified into the small clusters. This also has an important practical implication for this technique suggesting that if the system under investigation is expected to have a low failure rate, then the cluster count (if specified as a parameter) should be very small, but as the expected failure rate increases then so should the number of clusters. Further experimentation is required in order to validate this observation.