Context: Search-based software testing promises to provide users with the ability to generate high-quality test cases, and hence increase product quality, with a minimal increase in the time and effort required. One result that emerged out of a previous study to investigate the application of search-based software testing (SBST) in an industrial setting was the development of the Interactive Search-Based Software Testing (ISBST) system. ISBST allows users to interact with the underlying SBST system, guiding the search and assessing the results. An industrial evaluation indicated that the ISBST system could find test cases that are not created by testers employing manual techniques. The validity of the evaluation was threatened, however, by the low number of participants. Objective: This paper presents a follow-up study, to provide a more rigorous evaluation of the ISBST system. Method: To assess the ISBST system a two-way crossover controlled experiment was conducted with 58 students taking a Verification and Validation course. The NASA Task Load Index (NASA-TLX) is used to assess the workload experienced by the participants in the experiment. Results: The experimental results validated the hypothesis that the ISBST system generates test cases that are not found by the same participants employing manual testing techniques. A follow-up laboratory experiment also investigates the importance of interaction in obtaining the results. In addition to this main result, the subjective workload was assessed for each participant by means of the NASA-TLX tool. The evaluation showed that, while the ISBST system required more effort from the participants, they achieved the same performance. Conclusions: The paper provides evidence that the ISBST system develops test cases that are not found by manual techniques, and that interaction plays an important role in achieving that result.
Alternatively, a system may require the human user to only replace the fitness functions at certain times, e.g. to serve as a tie-breaker, when the existing fitness functions cannot rank certain candidates @cite_27 .
@cite_27
2099020927 2043811931 2148192607 2151083897
We describe two approaches to reducing human fatigue in interactive evolutionary computation (IEC). A predictor function is used to estimate the human user's score, thus reducing the amount of effort required by the human user during the evolution process. The fuzzy system and four machine learning classifier algorithms are presented. Their performance in a real-world application, the IEC-based design of a micromachine resonating mass, is evaluated. The fuzzy system was composed of four simple rules, but was able to accurately predict the user's score 77 of the time on average. This is equivalent to a 51 reduction of human effort compared to using IEC without the predictor. The four machine learning approaches tested were k-nearest neighbors, decision tree, AdaBoosted decision tree, and support vector machines. These approaches achieved good accuracy on validation tests, but because of the great diversity in user scoring behavior, were unable to achieve equivalent results on the user test data. A major obstacle to finding program errors in a real system is knowing what correctness rules the system must obey. These rules are often undocumented or specified in an ad hoc manner. This paper demonstrates techniques that automatically extract such checking information from the source code itself, rather than the programmer, thereby avoiding the need for a priori knowledge of system rules.The cornerstone of our approach is inferring programmer "beliefs" that we then cross-check for contradictions. Beliefs are facts implied by code: a dereference of a pointer, p, implies a belief that p is non-null, a call to "unlock(1)" implies that 1 was locked, etc. For beliefs we know the programmer must hold, such as the pointer dereference above, we immediately flag contradictions as errors. For beliefs that the programmer may hold, we can assume these beliefs hold and use a statistical analysis to rank the resulting errors from most to least likely. For example, a call to "spin_lock" followed once by a call to "spin_unlock" implies that the programmer may have paired these calls by coincidence. If the pairing happens 999 out of 1000 times, though, then it is probably a valid belief and the sole deviation a probable error. The key feature of this approach is that it requires no a priori knowledge of truth: if two beliefs contradict, we know that one is an error without knowing what the correct belief is.Conceptually, our checkers extract beliefs by tailoring rule "templates" to a system --- for example, finding all functions that fit the rule template "a must be paired with b." We have developed six checkers that follow this conceptual framework. They find hundreds of bugs in real systems such as Linux and OpenBSD. From our experience, they give a dramatic reduction in the manual effort needed to check a large system. Compared to our previous work [9], these template checkers find ten to one hundred times more rule instances and derive properties we found impractical to specify manually. In basic genetic algorithm (GA) applications, the fitness of a solution takes a value that is certain and unchanging. This formulation does not work for ongoing searches for better solutions in a nonstationary environment in which expected solution fitness changes with time in unpredictable ways, or for fitness evaluations corrupted by noise. In such cases, the estimated fitness has an associated uncertainty. The uncertainties due to environmental changes (process noise) and to noisy evaluations (observation noise) can be reduced, at least temporarily, by re-evaluating existing solutions. The Kalman formulation provides a formal mechanism for treating uncertainty in GA. It provides the mechanics for determining the estimated fitness and uncertainty when a new solution is generated and evaluated for the first time. It also provides the mechanics for updating the estimated fitness and uncertainty after an existing solution is re-evaluated and for increasing the uncertainty with the passage of time. A Kalman-extended GA (KGA) is developed to determine when to generate a new individual, and when to re-evaluate an existing one and which to re-evaluate. This KGA is applied to the problem of maintaining a network configuration with minimized message loss, with mobile nodes and stochastic transmission. As the nodes move, the optimal network changes, but information contained within the population of solutions allows efficient discovery of better-adapted solutions. The sensitivity of the KGA to several control parameters is explored. In evolutionary computation, the fitness function normally measures progress toward an objective in the search space, effectively acting as an objective function. Through deception, such objective functions may actually prevent the objective from being reached. While methods exist to mitigate deception, they leave the underlying pathology untreated: Objective functions themselves may actively misdirect search toward dead ends. This paper proposes an approach to circumventing deception that also yields a new perspective on open-ended evolution. Instead of either explicitly seeking an objective or modeling natural evolution to capture open-endedness, the idea is to simply search for behavioral novelty. Even in an objective-based problem, such novelty search ignores the objective. Because many points in the search space collapse to a single behavior, the search for novelty is often feasible. Furthermore, because there are only so many simple behaviors, the search for novelty leads to increasing complexity. By decoupling open-ended search from artificial life worlds, the search for novelty is applicable to real world problems. Counterintuitively, in the maze navigation and biped walking tasks in this paper, novelty search significantly outperforms objective-based search, suggesting the strange conclusion that some problems are best solved by methods that ignore the objective. The main lesson is the inherent limitation of the objective-based paradigm and the unexploited opportunity to guide search through other means.