Ramsay Taylor

Mathew Hall

Kirill Bogdanov

John Derrick

Using behaviour inference to optimise regression test sets

Where a software component is updated or replaced regression testing is required. Regression test sets can contain considerable redundancy. This is especially true in the case where no formal regression test set exists and the new component must instead be compared against patterns of behaviour derived from in-use log data from the previous version. Previous work has applied search-based techniques such as Genetic Algorithms to minimise test sets, but these relied on code coverage metrics to select test cases. Recent work has demonstrated the advantage of behaviour inference as a test adequacy metric. This paper presents a multi-objective search-based technique that uses behaviour inference as the fitness metric. The resulting test sets are evaluated using mutation testing and it is demonstrated that a considerably reduced test set can be found that retains all of the fault finding capability of the complete set.

Introduction

Where a software component is updated or replaced regression testing is required. It is often the case that there is no documented specification for the behaviour of the component. In the absence of a specification for the component, regression tests can be used to attempt to determine that a de-facto specification -the behaviour of the previous version -is adhered to.

In the absence of regression test sets, the only available regression test is the replay of trace data from in-service logs of the previous version. This trace data contains sequences of inputs and outputs, or sequences of function calls that are applied to the component. The traces can identify both sequences of behaviour that must be accepted, and sequences that should not occur. When sufficient log data is available this provides an accurate picture of the behaviour that the rest of the system expects from the component, so replay of traces forms a meaningful regression test.

Running regression tests is often expensive, usually due to the large number of tests that comprise a test suite. Often, multiple regression tests will exercise the same behaviour, resulting in time being spent on tests that add no value. This is especially true of test sets derived from in-service data.

An improved test suite can be developed by selecting a subset of the traces with enough traces to exercise each part of the behaviour for the lowest overall cost. Figure 1 illustrates the minimisation process. In the example, a subset of the eight regression tests is selected (1,[START_REF] Chow | Testing Software Design Modeled by Finite-State Machines[END_REF][START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF], and must then be evaluated for its suitability. The naive, exact solution is to repeat this process for all subsets of the test suite, but this is impractical for most test suites, and impossible for test suites generated from log data that can contain billions of lines [START_REF] Xu | Experience mining google's production console logs[END_REF]. It has been shown in [START_REF] Lin | Analysis of test suite reduction with enhanced tiebreaking techniques[END_REF] that finding a suitable regression test subset is NP complete and so heuristic approaches are required. A detailed survey of regression test selection literature can be found in [START_REF] Biswas | Regression Test Selection Techniques: A Survey[END_REF].

The problem has two distinct elements. Firstly, given that considering all candidate sets is infeasible, the selection step must be performed more intelligently. Secondly, once a candidate is selected, difficulty remains in assessing its suitability as a reduced test set.

Genetic Algorithms (GAs) are one solution to the selection problem. They are a class of heuristic approaches that have been used successfully in many software engineering problems [START_REF] Harman | Search-based software engineering[END_REF] and provide efficient selection of possible solutions from large search spaces. In a GA, a pool of good solutions is recombined to locate better solutions. This relies on measurement of the "fitness" of these solutions. Despite its efficiency, a GA will still consider a large number of solutions before it locates a suitable result, making its execution time highly dependent on both the accuracy and the speed of the evaluation mechanism.

Previous work has used code coverage to address the evaluation problem. Genetic Algorithm approaches to the selection of subsets were presented in [START_REF] Mansour | Simulated Annealing and Genetic Algorithms for Optimal Regression Testing[END_REF] and [START_REF] Yoo | Using hybrid algorithm for Pareto efficient multi-objective test suite minimisation[END_REF], and sought to identify the minimum set of traces that achieves complete code coverage. Test sets selected for code coverage have been shown to provide a low "behavioural adequacy" [START_REF] Fraser | Behaviourally Adequate Software Testing[END_REF] -that is, their fault finding ability is lower than test sets selected for behavioural coverage. An alternative measure of a test set is provided by behaviour inference. Using behaviour inference as a measure of test adequacy was first suggested in 1983 [START_REF] Weyuker | Assessing Test Data Adequacy through Program Inference[END_REF], and has been shown to provide a better foundation for selecting test sets [START_REF] Fraser | Behaviourally Adequate Software Testing[END_REF]. While behavioural inference requires some computation time this grows with the number of test cases, regardless of their content. However, the time taken to execute a test set is unbounded as each test may depend on external factors such as communication, which may take an arbitrarily long time.

The contribution of this work is to apply the behaviour inference approach to the problem of regression test set reduction using multi-objective search techniques. The work is directed at the following three Research Questions: RQ1 What reduction in test set size can be obtained using a GA with the behavioural inference fitness metric? RQ2 Is behavioural inference a good selector of high quality test subsets? RQ3 How intelligently does the GA search technique use a constrained budget? This paper makes the following contributions:

-A fitness metric for test subsets based on comparisons of inferred behaviour between the subset and its parent. -A multi-objective search approach based on the NSGA-II algorithm that applies this metric to identify a Pareto front of fast, accurate test sets. -An evaluation of the solutions found by this approach that demonstrates the search efficiency and validates the results by comparing mutation testing outcomes between the subsets and their parent.

The remainder of this paper is organised as follows:

-Section 2 introduces the vending machine example that is used throughout this paper. -Section 3 and Section 4 present the process of evaluating a test set using passive learning algorithms, and the genetic algorithm for efficiently searching the possible test subsets. -The results of the process are evaluated in Section 5.

-Section 6 contains conclusions.

The vending machine example

The example used throughout this paper is a simple vending machine simulation. The case study was implemented in Erlang1 but the techniques developed operate on traces and are independent of the implementation language. The implementation consists of 60 lines of Erlang code. The module presents an interface with a number of functions that represent operations on the machinestart,coin,choc,toffee -some of which take parameters and all of which produce a return value.

The behaviour of the vending machine program can be best understood with reference to the state machine shown in Figure 2, which presents a convenient abstraction. The format for the transition labels is a triple with the name of the function, a list of arguments, and the expected return value. For example, {coin, [START_REF] Armstrong | Concurrent Programming in ERLANG[END_REF],ok} represents a call to the coin function with the parameter 2 and the expected response ok. The machine is initialised with the start function, and can be re-initialised at any point, resetting it to the initial state. The machine accepts 1p and 2p coins and charges 1p for toffee and 2p for choc. Since 2p is the most expensive item, the machine will reject coins that would take its stored value above 2p (this serves to make the machine's state space finite).

In the scenario in this example, a test set was generated randomly according to the following process. Elements of the trace alphabet were randomly selected and conjoined to produce traces. In this example the trace alphabet consists of the interface functions, combined with the valid arguments and valid responses for each function. These were then passed to a program that attempted to execute the generated sequence of function calls and checked that the returned values were consistent with those generated. Where there was an inconsistency -or where there was an exception thrown by the program -the trace was truncated at that point and marked as negative. If all elements of a trace completed successfully then it was marked as a positive trace. This forms a prefix-closed language describing the behaviour of the program.

+ {start,[],ok} {coin, [1],ok} {coin, [START_REF] Armstrong | Concurrent Programming in ERLANG[END_REF],no} {coin, [1] A random test set was constructed by adding random traces to it until the set covered all the behaviour of the state machine inFigure 2. This produced a test set of 190 traces; some example traces are shown in Figure 3. The third trace is listed as negative because it expects the response no to the toffee call after giving the machine a 2p coin, when the implementation will instead respond toffee. This observed behaviour is listed in the fourth trace.

Using behaviour inference to assess the suitability of a test subset

As discussed in Section 1, a technique is needed to select possible test subsets and then evaluates their adequacy. This section defines an evaluation strategy using behaviour inference. This will form the fitness function for the selection technique presented in Section 4. The aim of this fitness function is to assess the behaviour exercised by the test cases, addressing the shortcomings present in previous work that uses code coverage.

In the example in Figure 1, the adequacy of the subset (1,4,5) must be evaluated against the full set (1,2,3,4,5,6,7,8). To do this a model is inferred of the behaviour covered by the full set, and then a model is inferred of the behaviour covered by the subset. These are then compared to assess the extent to which coverage has been maintained. This is particularly pertinent in the regression case where the only specification of correct behaviour is the log data of an existing system, so the model inferred from the complete set is the only available standard against which test set coverage can be measured.

Behaviour inference

Behaviour inference builds finite state machine models from trace data using algorithms inspired by language learning models.

Passive learners aim to learn state machine language representations from partial data, usually a subset of the possible sequences of the language. Evidence driven state merging (EDSM) algorithms such as BlueFringe [START_REF] Lang | Results of the abbadingo one DFA learning competition and a new evidence-driven state merging algorithm[END_REF] operate on a set of positive and negative traces from a system or language and produce a state machine that accepts positive traces and rejects (in the form of a transition to a failure state) negative traces. It was shown to be highly effective in the "Abadingo One" [START_REF] Lang | Results of the abbadingo one DFA learning competition and a new evidence-driven state merging algorithm[END_REF] competition for learning algorithms.

We use the StateChum system [1], which was developed to implement an EDSM algorithm based on BlueFringe with the objective of reverse engineering state machine representations of software behaviour from software trace data [START_REF] Walkinshaw | Reverse engineering state machines by interactive grammar inference[END_REF]. The algorithm operates on prefix closed languages, which are a good model of software execution traces since traces cannot exist with failing prefixes. The supplied traces are merged into a Prefix Tree Automaton (PTA), which represents an accurate but excessively large FSM representation of the behaviour covered by the supplied traces. The algorithm proceeds by merging states to reduce the size of the state machine without altering the accepted language. The choice of states to merge is based on various evidence, such as similar outgoing traces, and the absence of explicit negative traces in the test set that would become accepted after the merge.

State machine comparison

A key component of the evaluation mechanism presented in this section is the comparison of inferred state machines. This paper will use what is called the Balanced Classification Rate (BCR) measure to compare state machines, and thus compare the behaviour coverage of the test sets that produced them.

The BCR metric measures the accuracy of a state machine against a reference machine in terms of the correct classification of traces as either positive (accepted) or negative (rejected). Each of the possible traces of the reference machine are classified by the machine being measured and four sets are produced: true positives (TP), true negatives (TN), false positives (FP), and false negatives (FN). For machines with cycles the set of possible traces is infinite; this paper uses the W-Method [START_REF] Chow | Testing Software Design Modeled by Finite-State Machines[END_REF] to produce a suitable set of traces that cover all of the behaviour in a finite set. For example, in Figure 4 the right hand FSM accepts traces that do not start with {start,[],ok}, whereas the correct model does not, so these form false positives. These figures are used to compute two numbers, C plus and C minus , where C plus = T P/(T P + F N ) and C minus = T N/(T N + F P ). The BCR value is the harmonic mean between C plus and C minus and is defined as: BCR = (2 * C plus * C minus )/(C plus + C minus ). This produces a "score" between 0.0 and 1.0, where 1.0 represents correct classification of all traces, and smaller numbers represent decreasing levels of accuracy.

Subset evaluation metric

With these components in place, each candidate test subset can be compared to a reference model to produce a numeric adequacy value. The behaviour inference process is applied to the complete test suite and the inferred model forms the reference for all subset evaluations. This inference only needs to be conducted once, at the beginning of the process.

Each candidate test subset is compared to the reference set by inferring a model from the subset and then computing the BCR score (as described in Section 3.2) of that model against the reference model. The BCR score gives a numeric metric to the accuracy of the model, and permits the user of the process to allow a trade-off between speed and accuracy. In cases where the optimal, completely accurate regression test still requires many hours to run it may be useful to produce a regression test that can be run in minutes and still find 80% of faults. This could serve as a quick regression test during the development program, that is supplemented by the full regression test at the conclusion of a development phase. By using a numeric metric of accuracy, such as BCR, this process allows quantitative decisions to be made about the appropriate accuracy/speed trade-off that would not be possible using less semantic measures such as code coverage.

Inferring a model from a set of recorded traces is much faster than actually performing tests themselves. Thus using recorded traces, either from in-service log data or a run of the existing regression test set, the time taken to evaluate the behavioural coverage of a regression test subset can be minimised versus running the tests to evaluate it. For example, the inference process on the 146 line trace set takes under 1 second, whereas evaluating the complete set of traces against an implementation takes over 50 seconds. It is shown in Section 5.3 that model inference allows many thousands of candidates to be evaluated in less than an hour. Model inference therefore provides a process by which candidate solutions can be quickly evaluated, allowing many thousands of possible subsets to be evaluated in a reasonable time.

Test subset selection using multi-objective search

Having developed a suitable fitness function, the other component of the technique is the selection of candidate test subsets. This section presents a multiobjective search algorithm using the NSGA-II algorithm.

Genetic Algorithms

This paper uses genetic algorithms to approach the NP complete problem of selecting test subsets from a given test suite. The field of Search-Based Software Engineering [START_REF] Harman | Search-based software engineering[END_REF] includes various techniques that provide general, meta-heuristic approaches to problems for which it is impossible or impractical to find perfect solutions. Genetic Algorithms (GAs) are one such technique that uses an evolutionary metaphor to direct and optimise a limited search of a very large search space. This makes them ideal for a task such as test suite optimisation where the search space is large, and while the best solution is desirable, there is a large space of sub-optimal, but still satisfactory solutions that a GA can discover.

The critical elements of a GA are: a representation of an individual candidate solution as a collection of "genes", and a "fitness function" that produces a numerical measure of the "correctness" of this candidate.

The search consists of the application of operators on a population comprised of a number of chromosomes, each of which containing one or more genes. The minimum operators required are selection, crossover and mutation.

The selection operator uses the fitness values of the chromosomes to determine which are selected in the next generation. Crossover and mutation are concerned with exploring the search space. Crossover models reproduction, where two individuals are mixed together to produce offspring. Crossover operators traditionally consist of a series of swap operations, however more complicated ones exist. The mutation operator serves to prevent the search from remaining in local optima by ensuring diversity in the population. It operates by randomly altering one or more genes in an individual to produce a new individual.

Chromosome Representation and genetic operators

The chromosome representation for a test set subset consists of a set of bits where each bit represents a trace or test from the original test set. Bits set to 1 represent that that trace is included in this subset, 0 represents that the trace is not included. Each bit is considered a gene by the implementation. The chromosome is therefore comprised of T c bits, where T c is the number of traces in the original set. Crossover is enacted by picking some n where n < T c; the new chromosome is formed from bits 1 to n from one parent, and bits n + 1 to T c from the other.

Random mutation of a bit would simply invert it. As the number of bits set to 1 or 0 decreases (i.e. the chromosome is "mostly 1s" or "mostly 0s") this becomes less effective, since inverting a random bit becomes decreasingly likely to further reduce the number of 0s or 1s. This is a significant issue for test set minimisation in cases where a significant optimisation is possible, or very little optimisation is possible, since the ideal solution may have very few traces included (1s) or very few traces excluded (0s).

This implementation uses two mutation operators: one that randomly "turns on" a bit, and one that randomly "turns off" a bit. This ensures that every generation contains some new solutions with more traces and some with fewer traces, even as the population tends towards one extreme or the other.

The binary nature of the individual genes also has a significant impact on the generation of the initial population for the search. If the initial chromosomes are simply generated randomly then they will all have approximately 50% of the bits set and approximately 50% unset. In theory the crossover and mutation will eventually correct for this, but it was found that producing a more even distribution of initial individuals allowed the search to focus more rapidly. Consequently, individuals for the initial population are created by first selecting a random number of bits to be set, and then a random distribution of those bits across the chromosome. This results in an even distribution of individuals from some with 0 bits set to some with T c bits set.

Multi-objective search algorithms

The test set reduction problem involves optimising for both test speed and fault identification. In such instances where there are multiple, independent variables to optimise, this can be achieved by weighting the squares of each variable and using this as the fitness function for a conventional GA, however this has the possibility that a solution with a very high score for one objective will overpower solutions that have a more balanced profile. Consequently, this work uses a specialised multi-objective genetic algorithm, which has a more intricate selection process that seeks to avoid this drawback.

The search heuristic used in this paper is based on the "Non-dominated Sorting Genetic Algorithm II" (NSGA-II) [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF], which has been demonstrated as effective in test set reduction by [START_REF] Yoo | Using hybrid algorithm for Pareto efficient multi-objective test suite minimisation[END_REF]. For each candidate solution the NSGA-II selection mechanism measures the number of other solutions that "dominate" this one, where dominance is defined as being superiour in all objectives. Those that are undominated represent the Pareto front of the currently explored solutions. These are retained as the population for the next generation.

Where there are many Pareto-optimal solutions it becomes necessary to select a subset. The subset is chosen to avoid clustering -that is, the selection mechanism attempts to distribute the chosen solutions evenly over the Pareto front. This distribution creates a much more effective basis for the next generation, since breeding solutions that excel in different objectives should produce offspring which posses both qualities. As an example: breeding a very accurate test set with a very fast one may produce offspring that retain most or all of the accuracy but are considerably quicker.

Fitness Evaluation

The minimisation process has two variables to be optimised: fault identification and cost.

Fault identification is estimated using the BCR score for the learned machine from a candidate individual as described in Section 3.3.

The "cost" of the test set may be defined as the time taken. For the purpose of the case study in this paper, uniform cost is assigned to all tests in a candidate subset, therefore the "cost" is a function of the size of the test set. In a more complex testing scenario it would be important to consider other costs, such as the execution time of each test. This may not be related to trace length, as some tests may include features such as external synchronisation that causes them to take arbitrarily long times. Wherever trace count (T c) is used in the subsequent discussion this could be substituted for trace cost, which would be the sum of individual costs of tests in a test set. The trace improvement of a subset is defined as the number of test cases removed from the total set, (i.e. the number of 0 bits in the chromosome). This is expressed as a fraction of the total chromosome size: T race Improvement = T c-T c individual T c .

Selection

The two values, BCR score and Trace Improvement, measure the solution's fitness in each objective dimension. A solution's dominance is then measured by comparison to the other solutions in the current population. The selector proceeds by choosing undominated solutions. If the number of them exceeds a defined limit then it begins to reduce the set by measuring the "distance" between solutions. The distance is measured as the sum of the absolute difference between the accuracies and the trace improvements. Solutions with identical accuracy and trace improvement have a zero distance and one of the pair will be removed. If the size is still excessive then a threshold distance is established at 0.01 and steadily increased. Any solutions within the threshold distance are pruned and the threshold increased until the population size falls below the limit.

Evaluation

This evaluation seeks to assess the test set improvement that can be obtained using the multi-objective behavioural adequacy approach, as well as to validate the testing capability of the solutions it generates compared to that of the original test set. The research questions this evaluation answers are those defined in Section 1.

The evaluation was conducted on the vending machine example given in Section 2. A test was produced containing 190 randomly generated traces, which covered all behaviour in the program, such that running the EDSM algorithm (Section 3.1) on it will produce the state machine in Figure 2. The random nature of the test set means it is likely to contain duplication -traces that exercise the same behaviour, offering no value. The objective of the evaluation was to determine how much of this duplication the GA removed

RQ1: Reduction in test set size

This research question is answered in terms of the trace improvement (as defined in Section 4.4) the search yields for test sets that exercise the same behaviour as an unoptimised test set.

The test set was optimised using the multiobjective genetic algorithm as detailed in Section 4.3. The individuals were assessed in terms of the constituent variables that make up their fitness (BCR and trace improvement).

The genetic algorithm used a 100% crossover rate, generating one extra individual for every pair of parents, a population size of 10 after each round of selection, and a mutation rate matched to the size of the trace set so that each individual in the population produces one mutant with one gene altered. Crossover and mutation were only applied to the surviving members of the previous fitness evaluation. Fitness values were recorded for all individuals evaluated as the search progressed. The search was repeated 30 times to ensure statistical significance.

The genetic algorithm was limited to 75 generations, which produced an average of 3500 evaluations of distinct individuals. A random set of 3500 individuals was generated and evaluated in the same way. This process was repeated 30 times to produce 30 sets of evaluations, each of a size that is comparable to a run of the GA.

Results

Min

RQ1: Reduction in test size

The individual with the highest trace improvement and a 1.0 BCR was selected from each of the 30 sets of individuals from the minimisation step. This was performed for both the genetic algorithm implementation as well as the random set. Statistics for the trace improvement values of these two samples are shown in Table 1 as well as visually for the GA in Figure 5.

The results demonstrate that a high reduction in test case size is achieved using the approach. Both search algorithms located reduced test sets with a high trace improvement, with the minimum being over 0.7. Consistency is demonstrated by the small standard deviation, which equates to a difference of 4% of the original test set size.

RQ2: Efficacy of the behavioural adequacy metric

The validity of the behavioural adequacy metric as a measure of the fault identification of a test subset is assessed using mutation testing. Mutation testing values of BCR that the mutant killing power is as high as the original test set. In this evaluation BCR is observed to be prone to false negatives, but does not appear to suffer from false positives: of all the test sets with a BCR of 1.0, none killed fewer mutants.

These results suggest that BCR is likely to be too conservative, as smaller test sets with an equal mutant killing power will be discarded if they have a low BCR score. The multiobjective search used in this approach can mitigate this problem; adjacent solutions to test sets with a high trace improvement but low BCR score may still be explored, possibly yielding better adjacent solutions. This also has the implication that individuals on the Pareto front with sub-1.0 BCR scores (but better trace improvement) should not be rejected outright, as they are potentially more suitable minimisations of the test set.

RQ3: How intelligently does the GA search use a constrained budget? The search space for an exhaustive approach for the case study is 2 190 . The results for RQ1 demonstrate the search reliably finds a test set that is significantly smaller than the original regression test set, despite only exploring a small fraction (30, 000 candidates) of the total search space. algorithm, which is beyond the region explored by the random searcher. Along this front are the best individuals found by the search. This front demonstrates the tradeoff between behavioural adequacy (BCR) and trace improvement. As the findings for RQ2 suggest that some solutions with sub 1.0 BCRs may be equally suitable as those with 1.0 BCR scores, the individuals to the right of the plot may actually be better overall.

The random search results exhibit a pattern where a large number of individuals with a widely varied trace improvement have the same BCR score. This is due to the common lack of a critical trace amongst this subset of the population and illustrates the difficulty of the selection problem, as well as demonstrating the benefit of intelligently searching the space, rather than randomly sampling it.

The "p-value" column of Table 1 gives the p-value for a one-sided Wilcoxon test. The p-value gives an indication of the likelihood that the null hypothesis (H 0 ) is true. In this case, H 0 : median(GA) > median(Random). As the p-value is small, the null hypothesis is rejected, indicating the difference in medians is statistically significant, demonstrating that the GA outperforms the random searcher.

Figure 8 shows a visualisation of the BCR scores and trace improvements of the solutions considered by both search algorithms. The higher density towards the higher BCR scores for the random searcher can be explained by the uniform distribution of trace improvement -solutions with more traces (i.e a lower trace improvement) are more likely to have a high BCR score. The genetic algorithm exhibits a more varied distribution of BCR scores, accounted for by the amount of solutions with higher trace improvement it considered; this corresponds to the Pareto front that is illustrated in Figure 7.

Threats to Validity

There are several factors that constitute potential threats to validity.

The performance of the GA may be due to chance It is possible that the results of the genetic algorithm may be entirely due to random chance. This risk is mitigated firstly by the large number of repetitions of the search, reducing the possibility of a non-representative sample being observed. The comparison of the GA against the random set shows that its performance is higher than a purely stochastic search process, meaning that this threat is eliminated. The case study may not be representative of software systems This may impact the amount of improvement observed for other systems. The trace improvement that can be obtained is dependent on the amount of duplication in the test set; the technique presents no benefit if a test set is already minimal. This does not impact the findings shown however, as it demonstrates that, given a means to calculate the BCR score of a candidate test set (and a test set that can be minimised), a reduction is possible using this technique.

Conclusions and Future Work

This work presents an application of a genetic algorithm to the test suite minimisation problem. Although genetic algorithms have been used before, this is the first instance where the behaviour exercised by the tests has been used as a selection criterion. The evaluation demonstrates that the approach is able to locate high-quality minimised test sets using BCR to estimate the behaviour exercised by the tests, identifying a test set that exhibits the same behaviour, despite having 90% of the traces removed from it. This is validated in two aspects, comparison with a random algorithm, as well as the muation testing of the results to compare BCR accuracy. The findings show this is a promising algorithm, however the survey only applies it to a small example. Real world performance is not likely to vary, however, as the learning process occurs separately from the software. GAs can handle large search spaces well, so larger test sets should be reduicible using this technique as well as smaller ones (albeit with a higher fitness evaluation budget). Immediate future work will seek to apply the minimisation process to larger and more varied case studies to test this hypothesis.

Although in this work BCR worked well, it is possible to utilise other comparison techniques [START_REF] Walkinshaw | Automated Comparison of State-Based Software Models in terms of their Language and Structure[END_REF][START_REF] Pradel | A framework for the evaluation of specification miners based on finite state machines[END_REF] that aim to ensure that a less than perfect score corresponds to a small change in an inferred model. Whereas BCR is generally sensitive to transitions close to the initial state, these methods aim to ensure the measure of difference computed is relatively equally sensitive to a missing or added transition anywhere in an automaton. Future work could use these alternatives to improve the accuracy of the test adequacy measure, therefore allowing potentially better trace improvement scores to be reached.

Fig. 1 .

 1 Fig. 1. Problems facing test set selection

Fig. 2 .

 2 Fig. 2. The vending machine state machine

Fig. 3 .

 3 Fig.3. Some example traces from the case study test set.

Fig. 4 .

 4 Fig.[START_REF] Chow | Testing Software Design Modeled by Finite-State Machines[END_REF]. The vending machine behaviour as inferred from the complete random trace set, and a behaviour model with a BCR score of 0.81 inferred from less than 4% of the trace set.

Fig. 5 .

 5 Fig. 5. Histogram of the trace improvement of the best individual with a 1.0 BCR score from each GA search

Fig. 7 .

 7 Fig. 7. Scatter-plot of the individuals evaluated by each search

Figure 7 Fig. 8 .

 78 Figure 7 shows a scatterplot of the trace improvement versus BCR score for each of the individuals selected by both the random and the genetic algorithm searches. Maximised values in both direction represent objectively better solutions. The plot clearly shows a Pareto front has been located by the genetic

Table 1 .

 1 Trace Improvement scores for the best individual with a 1.0 BCR score from each iteration for both search types

	Max Median Mean St. Dev. N p-value
	GA 0.757 0.936 0.921 0.909 Random 0.710 0.873 0.808 0.806	0.037 30 0.028 30	< 0.005

Erlang is a concurrent, functional programming language developed by Ericsson and used extensively in the telecoms industry[START_REF] Armstrong | Concurrent Programming in ERLANG[END_REF].

 [START_REF] Hamlet | Testing programs with the aid of a compiler[END_REF]evaluates test sets by simulating faults in a software system and measuring the test set's ability to identify the faults.

Mutation testing modifies the software's source code to produce a "mutant". The mutant code is recompiled and then tested by the test suite. If the mutant fails the test suite it is referred to as "killed", if not then it is "alive". A large percentage of simple syntactic mutations result in code that does not compile; many of those that do compile have no functional change. Semantic mutation testing (SMT) [START_REF] Clark | Semantic Mutation Testing[END_REF] is intended to improve on this by applying mutation to a parsed form of the program. The muT estErl [START_REF] Guo | Mutation Testing of Erlang Distributed and Concurrent Applications[END_REF] system for Erlang semantic mutation testing was used in this evaluation.

To use mutation testing to evaluate BCR, the complete test set was first run on 4807 mutants. The complete set kills all but 386 of these mutants. These remaining mutants contain modifications that do not alter the observable behaviour of the program -many change the type of the internal representation of the stored coin value from integer to floating point, for example, but the Erlang implementation performs suitable implicit casting at each application of an arithmetic operator to allow all the updates and comparisons to continue to operate.

A selection of 288 randomly generated individuals were then subjected to mutation testing. Each of these individuals was a reduced test set, for which the BCR was calculated. The same set of mutants was then run on each of these reduced test sets, each killing some number of mutants. The result of these runs are shown in a scatterplot in Figure 6. The scatterplot shows that mutant killing power does not correlate highly with BCR (Pearson r = 0.457), however, it also shows that for particularly high


João Santos

Rui Abreu

Lightweight Automatic Error Detection by Monitoring Collar Variables

Keywords: Error detection, program invariants, automatic oracles, dynamic execution

Although proven to be an effective way for detecting errors, generic program invariants (also known as fault screeners) entail a considerable runtime overhead, rendering them not useful in practice. This paper studies the impact of using simple variable patterns to detect the so-called system's collar variables to reduce the number of variables to be monitored (instrumented). Two different patterns were investigated to determine which variables to monitor. The first pattern finds variables whose value increase or decrease at regular intervals and deems them not important to monitor. The other pattern verifies the range of a variable per (successful) execution. If the range is constant across executions, then the variable is not monitored. Experiments were conducted on three different real-world applications to evaluate the reduction achieved on the number of variables monitored and determine the quality of the error detection. Results show a reduction of 52.04% on average in the number of monitored variables, while still maintaining a good detection rate with only 3.21% of executions detecting non-existing errors (false positives) and 5.26% not detecting an existing error (false negatives).

Introduction

An application's development phase is usually restricted by the budget allowed for development and/or time-to-market. These restrictions provide a trade-off with the reliability of the system, which leads to an increase in defects that can lead to catastrophic results. In these cases proper error detection is vital in order to ensure the recognition and recovery from faults during the deployment phase as soon as possible [START_REF] Patterson | Recovery-oriented computing (ROC): Motivation, definition, techniques, and case studies[END_REF]. One possible way of implementing error detection on a system is with the use of generic invariants, also known as fault screeners. They may present a higher rate of false positives (faults detected when none exist) and false negatives (the non detection of an error) when compared to hard coded error detection methods (such as asserts), due to the latter detecting anticipated faults. Despite this, generic invariants have the great benefict of being generated and intrumented automatically into the code. This along with the fact that (1) the invariants can be trained automatically during the testing phase and (2) hard coded solutions are cumbersome and time consuming to implement, might give an edge to generic invariants. Having generated automatically the invariants and trained them during the testing phase, they are ready for being used during the deployment phase, where the invariant detects deviations from the learned behaviour [START_REF] Racunas | Perturbation-based Fault Screening[END_REF]. Generic invariants have been subject of study for many years, spawning various types like range screeners, bitmask screeners, and screeners that leverage Bloom filters [START_REF] Racunas | Perturbation-based Fault Screening[END_REF][START_REF] Hangal | Tracking down software bugs using automatic anomaly detection[END_REF]. They are mostly used for fault localization [START_REF] Abreu | Automatic software fault localization using generic program invariants[END_REF] and error detection [START_REF] Hangal | Tracking down software bugs using automatic anomaly detection[END_REF].

Despite the benefits of generic invariants, their use on real-world, large software applications is currently impeded by the overhead that monitoring all the system's variables requires. However, monitoring every variable may not be required, as only a subset of variables, known as collar variables, truly affect the outcome of a system in a meaningful way [START_REF] Menzies | The strangest thing about software[END_REF]. Applications like TAR3 and TAR4.1 have some algorithms that already experiment on the detection of collar variables [START_REF] Gay | Automatically finding the control variables for complex system behavior[END_REF], but the use of these collar variables has not been applied on the reduction the number of generic invariants needed to monitor a system effectively.

To tackle this, two algorithms were devised to detect exectution patterns of variables both during executions and between them. These algorithms, called variable evolution pattern detectors in this paper, are executed during the training phase of the invariants and collect information from successful executions. During the operational phase, when the impact of the instrumentation overhead needs to be minimized, the data collected from the pattern detectors allows variables deemed unimportant to be ignored.

This paper makes the following contributions:

-Proposes two methods to detect variables that do not require monitoring (in other words, methods to detect the collar variables of the program under analysis).

-Investigates the reduction achieved on the number of used invariants on real world applications. -Evaluates the quality of the error detection when comparing with the results obtained using the test suite of the applications. -Reports the increase in execution time with the use of the invariants.

The paper is organized as follows. Section 2 gives a quick overwiew of how a fault screener works, along with a more detailed explanation of the used screener for the study, the dynamic range screener. In Sect. 3 explains the functioning of the two variable evolution pattern detectors. The experimental setup and results are shown in Sect. 4. Section 5 presents work related to this paper. Finally Sect. 6 gives some final thoughts and some insight on future work.

First used by Ernst et al. [START_REF] Ernst | Dynamically Discovering Likely Program to Support Program Evolution Invariants[END_REF], fault screeners, also known as program invariants, are fault tolerance mechanisms that use historical data recovered from previous executions to determine the expected behaviour from a system's variables, issuing a warning when the expected behaviour is not met [START_REF] Racunas | Perturbation-based Fault Screening[END_REF]. Hence, the use of fault sceeners is a possible way to achieve automatic error detecting by monitoring the system's variables. However, for the detection to be effective, a training phase is required. During this phase the spectrum of valid variable values is determined. This constitutes the expected behaviour for a variable that should raise a warning in case a value that does not fit the spectrum is detected [START_REF] Dimitrov | Anomaly-Based Bug Prediction, Isolation, and Validation: An Automated Approach for Software Debugging[END_REF]. Formally, screeners are not effective at detecting errors that involve the use of random values, or variables that store things like current timestamp.

There are various types of invariants, each with its own algorithms for training and error detecting. In this paper it is focused on the dynamic range invariants [START_REF] Racunas | Perturbation-based Fault Screening[END_REF], due to its simplistic nature, reduced overhead, and known to work in practice [START_REF] Abreu | Automatic software fault localization using generic program invariants[END_REF]. The dynamic range invariant stores the bounds of valid variable values. During the training phase, when a new value is found, the range of values allowed by the screener is extended according to the following equations:

l := min(l, v) (1)
u := max(u, v) (2)
If the new value is lower than the lower bound l, the lower bound is updated. Likewise, if the value is greater than the upper bound u, that bound is updated. Table 1 shows an example of how the training works for the dynamic range screener. At first the invariant does not consider any value valid since no observation was made yet. After the first observation, in this case 5, both bounds need to be updated leading to a valid range of [START_REF] Menzies | The strangest thing about software[END_REF][START_REF] Menzies | The strangest thing about software[END_REF]. The second observation is a 72. This value is greater then the upper bound of the range and not lower then the lower bound, so the upper bound is updated. With an updated range of [START_REF] Menzies | The strangest thing about software[END_REF]72], the new observed value 6 is compared to both bounds. It is between the upper bound and lower bound so no change is made. Lastly, the value 5004 is observed, again greater then the upper bound. This bound is updated leading to a final valid range of [START_REF] Menzies | The strangest thing about software[END_REF]5004]. When on error detection phase, every observed value is checked against the range of values allowed by the invariant. If the value goes outside the range of permitted values, a violation to the expected behaviour is detected:

violation = ¬(l < v < u) (3)
The dynamic range invariant can use a larger number of ranges in order to restrict the allowed spectrum [START_REF] Racunas | Perturbation-based Fault Screening[END_REF]. While the concept is the same, additional ranges require more memory and more execution time. When using more then one range, the objective during the training phase is: when a new value is observed, the updated range is the one that increases the valid spectrum by the least amount of values. Table 2 shows an example of a dynamic range invariant with two ranges. The invariant begins with two empty ranges. Once it observes the value 5, one of the ranges becomes [START_REF] Menzies | The strangest thing about software[END_REF][START_REF] Menzies | The strangest thing about software[END_REF]. On the second observed value, 72, since there is still one range that is empty, that range becomes, [72,72]. Now that both ranges, when new values are observed, the invariant tries to make the ranges as short as possible to learn the least amount of unseen values. When 6 appears, there would be two range choices, [START_REF] Menzies | The strangest thing about software[END_REF][START_REF] Gay | Automatically finding the control variables for complex system behavior[END_REF] and [72,72] or [START_REF] Menzies | The strangest thing about software[END_REF][START_REF] Menzies | The strangest thing about software[END_REF] and [START_REF] Gay | Automatically finding the control variables for complex system behavior[END_REF]72]. Since the first has the smaller ranges, this is the selected option. The last value 5004 provides an interesting twist. At first glance it would seem that this update would lead to [START_REF] Menzies | The strangest thing about software[END_REF][START_REF] Gay | Automatically finding the control variables for complex system behavior[END_REF] and [72, 5004], however that is not the case. The ranges are actually updated to [START_REF] Menzies | The strangest thing about software[END_REF]72] and [5004,5004]. This happens because the amount of values that is learnt is a lot smaller (from 6 to 72 compared to from 72 to 5004) and it still guarantees both the acceptance of the values from the values before the update and the new value observed. In this paper, the only version of the dynamic range invariant used is the single range one. One of the challenges for using generic invariants is the accuracy of the error detection, as the more training the invariants suffer, the number of false positives, errors detected that do not exist, tends to decrease, while the number of false negatives, the non detection of existing errors, increases [START_REF] Abreu | On the performance of fault screeners in software development and deployment[END_REF]. This happens because of the increase of accepted values by the invariant.

Figure 1 displays a possible setup for a dynamic range invariant. During the training phase the invariant learnt that the values between -2 and 2 were the valid set of possible values. However the real case is that the values should be valid between -3 and -1, as 1 and 2, as well as between 3 and 4. This leads to some false positives and false negatives. Values observed that withing the ranges [-3, -2[ or ]3, 4] issue a detected error warning, hence they are false positives. Likewise, observations between -1 and 1 do not issue any warnings when they should. In the same scenario, if the invariant had been subject to more training, then more values would be added into the accepted range. On Fig. 2 the number 4 was such a value (even though 4 should not appear during executions if ). This led to the values ranging from 3 to 4 to become valid, eliminating those false positives, but the ones from 2 to 3 also became valid, becoming new false negatives. In other words, there was an increase of false negatives and decrease of false positives. With more training the false positive rate tends to lead to 0 because the entire possibility of values become valid.

On the other side, the number of false negatives increases because since it accepts a lot more values then it should, it does not detect any values outside the huge accepted range. Note that there are other types of invariants, each with their own behaviour regarding accuracy of error detection and performance [START_REF] Abreu | Automatic software fault localization using generic program invariants[END_REF]. Among them are bitmask invariants, which use a bitmask with the bits that were changed during the training when compared with the first observed value. Another one is the Bloom filter, an invariant that saves the entire history of values observed during the training phase. In this paper, the results were obtained by only using the dynamic range invariant. However the approach proposed is easily extensible to other invariant types.

Variable Evolution Pattern Detectors

In this section, the two methods created to detect patterns on the variable values are presented. These patterns were designed to be as simple as possible, while still detecting constants and other variables, like counters. It is important to note that a variable is never classified as not important to monitor if it was only used on one execution of the system.

Delta Oriented Pattern Detector

The Delta Oriented Pattern Detector is the first of two algorithms created to detect collar variables. With this detector, the main objective is to discover variables that throughout its life cycle evolve in a constant fashion. These variables are then deemed not essencial since during every execution its value increases or decreases in the same manner, no matter what the input is, in other words variables with such detected pattern do not need to be monitored. This is accomplished by using a delta value (∆), that is the difference between the last value observed and the current one:

∆ := current value -last value if last value = ∅ (4)
∆ := 0 if last value = ∅ (5)
Algorithm 1 demonstrates how this detector can determine which variables are important to monitor. Every variable in the system has a ∆ associated to it. During the training phase, when the first value is observed, ∆ is given the value 0 and the last value is updated to the observed one. On the next observation, ∆ will be updated accordingly, using the current value and the last value, as seen in Line 8. After this, the pattern detection begins. With each observation, an updated ∆ is generated (∆ 2 ) and is compared to the current ∆. If the new ∆ is equal to the current one, the pattern detection continues as the evolution of the variable remains the same. In case the ∆ is different, since the pattern is broken, a flag is stored indicating that this pattern does not exist for the variable being evaluated. There is, however, an exception to this. When the new ∆ is 0, then it is not compared to the previous ∆ (Line 12). This is done because variables can be accessed without their values being changed. for all Observation pattern do 4:

if first observation then 5:

∆ := 0 6:

LastV alue := ObservedV alue 7:

else if second observation nRuns = 0 then 8:

∆ := ObservedV alue -LastV alue 9: else 10:

∆2 := ObservedV alue -LastV alue 11:

LastV alue := ObservedV alue 12:

if ∆ = ∆2 ∆2 = 0 then 13:

pattern := f alse 14:

end if 15:

end if 16:

end for 17:

nRuns + + 18: end for After each execution, the value of ∆ is saved along with a flag indicating whether the pattern was broken or not. Subsequent executions use the ∆ from the first execution and starts the pattern detection after the first two values, instead of after the third like the first run.

With this detector it is possible to detect constant values (∆ = 0), as well as counters and loop variables that always increment/decrement with the same pace. A good example of this is the Java code presented on Fig. 3. Of all the variables from this small code sample, j is the one that has the least impact on the outcome. It only serves as an auxiliary variable for the loop.

The delta oriented pattern detector can be used to mark this variable as not essencial. It does not matter what the input of this function is, because j will always increment in the same manner. ∆ will always be 1 (j always starts with the value 0 and increments by one on every access), so the pattern is never broken. Since this pattern is never broken, the variable will not be monitored during the error detection phase.

Range Oriented Pattern Detector

One of the main differences between this pattern and the previous one is that the range oriented pattern detector requires one full execution before it can determine a broken pattern. The basis of this detector is that if the range of values that a variable has between every run is the same, then it is not important to monitor. This is the reason why one full execution is required. The detector only has the range of the full execution at the end of it.

The functions of updating the bounds of the range are the same as the dynamic range invariant:

public i n t funcExample ( i n t i ) { i n
u := max(u, v) (6)
The main difference between the dynamic range invariant and the range oriented pattern detector is that the bounds of the detector are only updated on the first execution that a variable appears in. On the following executions, every time a new value is observed, it is determined if it is within the range of the first execution:

broken = ¬(l < v < u) (8)
Algorithm 2 shows how the detector works. During the first execution (Lines 4 and 5) the range is constantly updated with every observation of a given variable. Once the first execution is over, the pattern detector is ready to discover a pattern. Hence, on the following executions, each observed value is compared to the pattern detector range, as seen in Line 7. If the new value is not within the range determined by the first execution, then the pattern was broken. If this never happens then it is determined that there is a pattern in the execution and the variable will not be monitored during the error detection phase.

With this detector it is possible to detect variables that although do not evolve in a linear way that can be detected by the delta oriented pattern detector, are restricted in some way during the execution. This is the case of loop variables that are affected within the cycle. This can be seen in the example shown on the example shown on Fig. 4. In this case, variable j is not a very important variable to be monitored. Taking into account the previous, detector, it is easy to understand that it would not be marked as not essencial (as ∆ can be both 1 or 2). However the range oriented detector can find a pattern. On every execution, despite what input is received, the range of values j takes is always [0, 5]. During the first execution, this range would be given to the pattern detector and the following runs would follow the pattern, so the variable would not be monitored. nRuns + + 13: end for public i n t funcExample ( i n t i ) { i n t a c c u m u l a t o r = i ; f o r ( i n t j = 0 ; j < 5 ; j ++) { i f ( a c c u m u l a t o r == 1 && j < 3 ) j=j +2; a c c u m u l a t o r * = a c c u m u l a t o r ; } i n t r e s u l t = a c c u m u l a t o r * 3 ; return r e s u l t ; }

Algorithm 2 Range Oriented Pattern Detector

Empirical Results

In this section the experimental setup is presented, along with the workflow of the experiments themselves. After that the experimental results are discussed.

Experimental Setup

Application Set. During the experimentation, three real world applications were used:

-NanoXML 1 -a XML parser.

org.jacoco.report 2 -a report generator for the JaCoCo library.

-XML-Security -a XML signature and encryption library from the Apache Santuario 3 project.

1 NanoXMLhttp://devkix.com/nanoxml.php 2 JaCoCohttp://www.eclemma.org/jacoco/index.html 3 Apache Santuariohttp://santuario.apache.org/

In Table 3 some details of the applications used are shown. These details include the number of lines of code and the number of test cases. NanoXML is a free, easy to use and non-GUI based and non-validating XML parser for Java. It has three different components:

-NanoXML/Java, the main standard parser.

-NanoXML/SAX, an SAX adapter for the standard parser.

-NanoXML/Lite, an extremely small version of the parser with limited funcionality.

NanoXML is available under the zlib/libpng license, which is Open Source compliant.

JaCoCo is an open source code coverage library for Java, being developed by EclEmma. The current goal of JaCoCo is to provide a code coverage library that is able to provide coverage reports. To do this there is a bundle called org.jacoco.report. This bundle is able to provide reports in three formats:

-HTML, for end users.

-XML, to be processed by external tools.

-CSV, suitable for graph creation.

XML-Security is one of the libraries available on the Apache Santuario project, a project that aims at providing security standards for XML. It is distributed under the Apache Licence Version 2.0 which is compatible with other open source licenses. The XMLSecurity data format provides encryption and decryption XML payloads at different levels, namely Document, Element and Element Content. XPath can be used for multi-node encryption/decryption. There exist two versions of XML-Security: a Java one and a C++ one. The Java version is used for the experiments.

Workflow of Experiments.

In order to determine if the pattern detectors were effective at reducing the number of instrumented points and if the error detection maintained a good quality, the system's variables is subject to training first. Each application is instrumented in order to train the fault screeners. This training is achieved by executing a random number of test case (roughly 50% of the tests in the original suite) of the target program. We did not use the complete suite in order not to influence the results positively.

Once the training of the fault screeners is complete, the error detection phase begins. To evaluate the quality of the error detection, each application is executed five times. On each execution a different bug is inserted into the code and the number of false positives and false negatives are collected. An additional execution is performed without any inserted bug to determine the execution time in a regular scenario.

Each application's test suite was executed without any instrumentation as well to determine the increase of time the instrumentation brings.

Figure 5 shows the different phases of the experiments. First, during the training phase, the test are executed with the instrumented code. Everytime a variable is used, the update function of the screener is called in order to update the accepted values. In addition, the screener uses the pattern detectors to detect broken patterns. At the end of the execution, both the invariant and the data collected from the detector are saved. On the operational phase the test cases are executed with the instrumented code once again. However, this time instead of monitoring every variable, only the variables that did not have a detected pattern are observed. On each observation the value is then validated by the screener using information gathered during the training. With this setup the expected results are:

-Value of the reduction obtained in the number of used invariants.

-Comparison of execution times between executions with and without instrumentation. -Accuracy of the error detection with the use of pattern detectors.

Results

Table 4 shows the number of variables that were trained and the number of variables that are considered collar variables by the pattern detectors. It is important to note that only numerical variables are subjected to training, in other words, only variables of the types int, long, double and float. On average, a reduction of 52.04% is achieved with the use of the two pattern detectors. However the execution time of the program with instrumentation is also important to take into consideration. Table 5 presents the execution times of the test suites both with and without instrumentation. This instrumentation uses only collar variables. The average increase in the execution time is 135.8%. Although this seems like a high value, it is greatly impacted by the increase noticed on NanoXML that is only a few miliseconds.

Having the data on the reduction of variables monitored and execution time increase, the quality of the error detection is what remains. To test the quality of the detection using these collar variabes, the number of false positives (N f p ) and false negatives (N f n ) was determined. A false positive is considered when the fault screener detects an error in the execution that does not exist. Likewise, a false negative is counted when a faulty execution has no objections raised from any fault screener.

The results shown on Table 6 were obtained by comparing the total number of false positives (N f p ) and false negatives (N f n ) with the number of tests on the test suite of the target program (N t ):

f p := N f p N t (9)
f n := N f n N t (10)
With an average of 3.21% rate of false positives and 5.26% rate of false negatives, the rate of these false results is considerably low, especially on the smaller applications. On the largest application, XML-Security, although having a higher rate of false results, the worst case scenario detected was a 13.64% f p and 7.14% f n .

In conclusion, with only the use of two pattern detectors, the decrease of used invariants is quite significant and the error detection quality remains very high, appart from some special cases. In terms of execution time, it may still not be enough to allow their use on real world markets, but perhaps the creation of even more detectors could be a solution.

Threats to Validity

The main threat to the validity of these results is the fact that only three test subjects were used during the experimentation. Despite these subjects being real world applications being diverse in both the size of the application (lines of code) and size of the test suite, the limited number of subjects implies that not all types of system's are tested. This means that a system with characteristics that are completly different might present different results.

Another threat is that the number of injected bugs is not enough to lead to accurate results, as these bugs might simply be "lucky bugs" that intercept a collar variable.

Naturally, there are also threats that are based on the implementation of the invariants, the instrumentation or the pattern detector algorithms themselves. The reduce these threats, additional testing was made prior to the experimentation to guarantee the quality of the experimental results in this regard.

Related Work

Since being introduced, generic invariants have been subject of study along the years with very different goals in mind. These goals range from study of program evolution [START_REF] Ernst | Dynamically Discovering Likely Program to Support Program Evolution Invariants[END_REF][START_REF] Ernst | The Daikon system for dynamic detection of likely invariants[END_REF], fault detection [START_REF] Racunas | Perturbation-based Fault Screening[END_REF] and fault localization [START_REF] Hangal | Tracking down software bugs using automatic anomaly detection[END_REF][START_REF] Pytlik | Automated Fault Localization Using Potential Invariants[END_REF]. Invariants have also been used as an alternative way of error detection on a fault localization technique known as SFL [START_REF] Abreu | Automatic software fault localization using generic program invariants[END_REF][START_REF] Abreu | On the performance of fault screeners in software development and deployment[END_REF].

Daikon [START_REF] Ernst | The Daikon system for dynamic detection of likely invariants[END_REF] is a tool that reports likely invariants. It runs a program and then reports the properties observed during the executions. Besides storing predefined invariants like constants, range or linear relationships, it can be extended by the user with new invariant types. It is compatible with various programming languages, including C, C++, Java and Pearl.

Carrot [START_REF] Pytlik | Automated Fault Localization Using Potential Invariants[END_REF] is a tool created with the purpose of using generic invariants for fault localization. It uses a smaller set of invariants than Daikon. The results obtained were negative which lead to the belief that invariants alone are insuficient as a means of debugging. However, in [START_REF] Abreu | On the performance of fault screeners in software development and deployment[END_REF] the use of invariants for fault localization was successful when used as the input for the fault localization technique SFL.

DIDUCE [START_REF] Hangal | Tracking down software bugs using automatic anomaly detection[END_REF] is yet another tool that uses dynamic bitmask invariants. Although the results appear to be good on four real world applications, the error that is detected is on a variable that is constant during the training phase and changed when it was on error detection mode (an error that is easily detected by a bitmask invariant, an invariant that detects differences on the allowed active bits of a variable value).

IODINE [START_REF] Hangal | IODINE : A Tool to Automatically Infer Dynamic Invariants for Hardware Designs[END_REF] is a framework for extracting dynamic invariants for hardware designs. It has been shown that accurate properties can be obtained from using dynamic invariants.

Zoltar [START_REF] Janssen | Zoltar: A Toolset for Automatic Fault Localization[END_REF] is a tool that applies a fault screener on every occurrence of a variable and tries to detect errors by finding perturbations on their behavior. In addition to detecting errors, Zoltar uses the errors detected to help debugging using SFL.

Another tool that works with fault screeners is PRECIS [START_REF] Sagdeo | PRECIS: Inferring invariants using program path guided clustering[END_REF]. PRECIS introduces a different type of invariant based on pre-and post-conditions. The results obtained suggest the existance of some advantages over Daikon.

iSWAT [START_REF] Sahoo | Using likely program invariants to detect hardware errors[END_REF] is a framework that uses invariants for error detection of a hardware level. It uses LLVM to instrument the source code to monitor the store values.

In [START_REF] Racunas | Perturbation-based Fault Screening[END_REF] various invariants were subjected to performance evaluations. Among the tested invariants were dynamic range, bitmask, Bloom filters and TBL. Although the results show that bitmask outperforms Bloom filters and dynamic range, the errors used on the experimentation consisted of random bit switching, which is better suited for bitmask invariants and are not very common.

On the topic of collar variables, this term was used by Tim Menzies to describe the subset of variables that affect the output of an application in a meaninful way [START_REF] Menzies | The strangest thing about software[END_REF].

In [START_REF] Gay | Automatically finding the control variables for complex system behavior[END_REF] the algorithms of TAR3 and TAR4.1 are explained. These algorithms allow to obtain a ranking of "usefulness" of the different components of an application. TAR3 uses the concepts of lift, the change that a decision makes on a set of examples, and support. TAR4.1 uses Naive Bayes classifiers for the scor-ing heuristic in order to obtain an overall better performance in comparison to TAR3.1.

KEYS [START_REF] Jalali | Optimizing Requirements Decisions with KEYS[END_REF] is yet another algorithm that tries to discover the collar variables, called keys by the author. It is used to optimize requirement decisions and is faster then the TAR3 algorithm. In [START_REF] Gay | Real-time Optimization of Requirements Models[END_REF], an improved KEYS algorithm is shown called KEYS2. It outperforms the original version by four orders of magnitude in terms of speed.

In [START_REF] Williams | Backdoors To Typical Case Complexity[END_REF], the concept of collar variable is once again used, this time by the name of back doors. They were using these back doors to solve CSP/SAT search problems and suggest by formal analisys the potencial improvement of some hard problems from an exponential to polynomial time.

Conclusions & Future Work

In this paper two simple detectors were used to evaluate what were the collar variables in each of the systems. Experimenting on real world applications led to a more accurate take on the impact of the use of invariants for error detection. By only using two detectors, the reduction of number of invariants used was above 50% while still maintaining good quality detection. Still the increase in execution time might still be too severe for use and the inability of the detectors to view patterns on non numeric values is still an obstacle.

In this regard, for future work in order to reduce the overhead, a further decrease in the number of invariants used is necessary. The study of additional detectors that would filter even more variables would be a possibility to achieve such a decrease. Another option is the use of an algorithm similar to the one used on TAR4.1 [START_REF] Gay | Automatically finding the control variables for complex system behavior[END_REF] to make the decision of what variables to monitor. There are also plans to combine this method with static analysis in orther to try to achieve better results.

Futher work will also be invested in tackling one of the main issues of the current approach, the ability to only evaluate numeric variables. Efforts will be made to use invariants and create detectors that would evaluate patterns for other variable types like String or char. These variables may prove invaluable to increasing the effectiveness of this method.

Fig. 1 .

 1 Fig. 1. False positive and false negative example

Fig. 2 .

 2 Fig. 2. False positive and false negative example with increased training

Algorithm 1

 1 Delta Oriented Pattern Detector 1: pattern := true 2: for all Execution pattern do 3:

Fig. 3 .

 3 Fig. 3. Delta Detector code example

Fig. 4 .

 4 Fig. 4. Range Detector code example

Fig. 5 .

 5 Fig. 5. Workflow of experiments

Table 1 .

 1 Dynamic Range Screener training

	New Result Value Range Point
	5	∅
	72	[5, 5]
	6	[5, 72]
	5004	[5, 72]
		[5, 5004]

Table 2 .

 2 Dynamic Range Screener training with two segments

	New Result Value Range Point 1 Range Point 2
	5	∅	∅
	72	[5, 5]	∅
	6	[5, 5]	[72, 72]
	5004	[5, 6]	[72, 72]
		[5, 72]	[5004, 5004]

Table 3 .

 3 Application details

	Subject	LOC Test Cases
	NanoXML	5393	9
	org.jacoco.report 5979	235
	XML-Security	60946	462

Table 4 .

 4 Variable reduction

	Subject	Variables trained Collar Variables Reduction
	NanoXML	40	17	57.5%
	org.jacoco.report	55	28	49.09%
	XML-Security	325	164	49.54%

Table 5 .

 5 Execution time increase

	Subject	Execution time with Execution time without Increase instrumentation (ms) instrumentation (ms)
	NanoXML	270	827	206.3%
	org.jacoco.report	3469	5162	48.8%
	XML-Security	25005	63088	152.3%

Table 6 .

 6 False positive (fp) and false negative rate (fn) fn % fp % fn % fp % fn % fp % fn % fp % fn %

	Bug 1 fp % NanoXML Subject 0 0	Bug 2 0 0	Bug 3 0 0	Bug 4 0 66.67 0 Bug 5 0
	org.jacoco.report 0	0	3.4 2.13 3.4	0	3.83 2.13 5.96	0
	XML-Security	2.81 0.21 13.64 7.14 1.95 0.22 12.99 0.22 0.22 0.22

Acknowledgements

This work is financed by the ERDF -European Regional Development Fund through the COMPETE Programme (operational programme for competitiveness) and by National Funds through the FCT -Fundação para a Ciência e a Tecnologia (Portuguese Foundation for Science and Technology) within project PTDC/EIA-CCO/116796/2010.