Материал: + An Orchestrated Survey on Automated Software TestCase Generation

from, though much of the literature has tended to focus on evolutionary algorithms (Harman, 2011).

There are several surveys of these aspects of SBST (Afzal et al., 2009; Ali et al., 2010; Harman et al., 2009; McMinn, 2004, 2011). In these surveys the reader can find more detailed treatments of the work on SBST for non-functional properties (Afzal et al., 2009), Empirical evidence regarding SBST (Ali et al., 2010), as well as overviews of techniques (Harman et al., 2009; McMinn, 2004; McMinn et al., 2012a). Therefore, in this section, we do not seek to provide yet another ‘overview’ of SBST. Rather, we focus on some of the exciting and challenging avenues that lie ahead for future work in this rapidly growing research and practitioner community.

In describing these future directions we seek to consider work which is already underway as well as more ‘blue skies’ directions for open challenges that could yield major breakthroughs. For example, we consider work underway on coevolution and management of oracle cost as well as work on hybridising SBST with other test data generation techniques, such as Dynamic Symbolic Execution (DSE), a topic covered in more detail elsewhere in this paper. The oracle problem is important because the automation of testing requires automation of the checking of outputs as well as the generation of inputs. Co-evolution is interesting and important because it fits so well the way in which the testing process operates, as we shall see.

In all these emerging areas we can expect more work in the immediate future. We also consider open challenges such as the problem of migrating from generation of test cases to genera-

tion of testing strategies using search and optimising the insight that can be gained from SBST.Accepted

7.2. Hybrids of SBST and DSE

The Dynamic Symbolic Execution (DSE) approach (Godefroid et al., 2005) to handling dynamic data structures proved very e ective, leading Lakhotia et al. (2008) to incorporate DSE’s approach into SBST. Conversely, SBST handles floating point computation well, while DSE is limited by the power of the constraint solvers available (which typically cannot solve floating point constraints e ciently). Naturally, therefore, one might expect that the advantage of combining the two techniques, will be that the strengths of one can overcome the shortcomings of the other.

This led several authors to develop approaches to augment DSE with search-based approaches to solving floating point computations. Lakhotia et al. (2010) used a local search to augment the Pex DSE-based testing tool from Microsoft, while Souza et al. (2011) augmented ‘standard’ constraint solving with a Particle Swarm optimiser to improve the performance of Symbolic PathFinder.

The first authors to propose a combination of SBST and DSE to produce a hybrid were Inkumsah and Xie (2007) who introduced the EVACON framework, which composes the two approaches, reporting the first results for a combined DSE/SBST approach. The AUSTIN search-based software testing tool also provides hybrid capabilities, for which results have been reported to compare SBST and DSE for ‘out of the box’ test data generation (Lakhotia et al., 2010).

20

Baars et al. (2011) developed a new approach to SBST, in which symbolic execution is integrated into the search by augmenting the fitness function used to guide SBST. In a way, this work ‘does for SBST, what DSE does for constraint based testing’. However, the di erences between SBST and DSE mean that the modifications to symbolic execution, required to make it scalable, are also di erent. That is, whereas DSE performs a complete symbolic execution using concrete values, Baars et

al. use a purely symbolic execution with no concrete values, butManuscriptapply it only to local regions of code to improve the fitness function.

Harman et al. also combined DSE and SBST to produce the first approach to test data generation for strong (and higher order) mutation testing (Harman et al., 2011). They use DSE to achieve weak mutation adequacy, following a variant of the approach of Liu et al. (2006); Papadakis and Malevris (2010). This approach generates constraints, the satisfaction of which yields weak mutation adequacy. To extend this to strong mutation adequacy Harman et al. search the space of additional conjuncts for constraints to augment those that extend weak to strong. The fitness function seeks maximal control flow disruption in order to increase the likelihood of strong adequacy.

As this recent work demonstrates, there is much activity at the interface between SBST and DSE that is producing a form of ‘crossover and mutation’ of the two approaches. Because of their complementary nature we can expect to see more work on the combination of these two promising test data generation techniques. The proliferation of publicly available tools that support both approaches, and hybrids thereof, creates a rich infrastructure from which future research can draw.

7.3. Handling the Oracle

Testing involves examining the behaviour of a system in order to discover potential faults. Determining the desired correct behaviour for a given input is called the Oracle Problem. Manual testing is expensive and time consuming, particularly because of the manual e ort devoted to solving the oracle problem. This is the Human Oracle Cost. We need to develop SBST algorithms and methods that automatically generate test inputs that reduce Human Oracle Cost, thereby significantly reducing the overall cost of testing. We also need search-based techniques that can help to generate test oracles as well as test cases (Fraser and Zeller, 2010).

Of course, the cost of generating test inputs by hand is high. This has driven the growth of the Search-Based Testing research area. Indeed, over 340 papers have been published in the area according to a recent survey (Harman et al., 2009). However, despite this considerable publication output, there is very little work on either reducing the Oracle Cost (Harman et al., 2010; McMinn et al., 2010) or using SBST to generate oracles (Fraser and Zeller, 2010).

Most previous work concentrates on the problem of searching for good test inputs, but it does not address the equally important problem of reducing the cost of checking the output produced in response to the inputs generated. The current state of the art in SBST thus addresses only the benefit half of the testing problem: that of generating inputs that meet the testing

criterion. It fails to address the other half of the problem: the cost of checking the output produced.

This is simply not realistic for many testing applications; it assumes that all that matters to the tester is the achievement of the highest possible coverage, at any cost. However, a tester might, for example, prefer an approach that achieves 85% coverage with 30 test cases, over an alternative that achieves 90% coverage with 1,000 test cases. Or, the tester may prefer a test suite that lowers the comprehension cost of individual test cases, by minimising test case verbosity (Fraser and Zeller, 2011) and maximising readability (McMinn et al., 2012b).

Fortunately the SBST paradigm naturally generalises to multi-objective optimisation formulations, thereby allowing us to develop techniques that balance the multiple objectives of cost and benefit. If we can measure the oracle cost then we can make it a minimisation objective in our SBST test data generation approach. This will mean that all approaches to test data generation will be naturally multi-objective (Harman et al., 2007), because they will need to balance cost and benefit. This is a natural step forward for SBST, since testing is all about balancing cost and benefit. We know that exhaustive testing is impossible so we wish to achieve maximum benefit (ultimately fault finding, measured through surrogates such as coverage) for minimum cost (ultimately monetary, measured through surrogates such as e ort and time).

7.4. Opportunities for Co-evolution

predator–prey model of evolution, in which both evolving populations are stimulated to evolve to better solutions. In cooperative co-evolution, the idea is to symbiotically co-evolve several populations, each relying on the other to work in concert as part of a larger system that contains them.

With co-evolutionary computation, two or more populations evolve simultaneously, Acceptedusing possibly di erent fitness functions. In competitive co-evolution the idea is to capture a

Adamopoulos et al. (2004) were the first to suggest the application of co-evolution for SBST, arguing that this could be used to evolve sets of mutants and sets of test cases, where the test cases act as predators and the mutants as their prey. For testing, the competitive model has hitherto proved best suited, since test cases make natural predators.

Various forms of testing and bug fixing have been attacked using competitive co-evolution. Arcuri et al. also used coevolution to evolve programs and their test data from specifications (Arcuri, 2008; Arcuri and Yao, 2007) using co-evolution. Arcuri (2008); Arcuri and Yao (2008) also developed a coevolutionary model for bug fixing, in which one population essentially seeks out patches that are able to pass test cases, while test cases can be produced from an oracle in an attempt to find the shortcomings of a current population of proposed patches. In this way the patch is the prey, while the test cases, once again, act as predators.

We can expect to see work in which various software artefacts and their test cases are co-evolved. The test cases will be evolved to find counter examples that demonstrate that the artefacts being evolved are not yet optimal. The artefacts

21

engineering activities with SBST.

FigureManuscript4: Hyper-Heuristic SBSE: using Hyper Heuristics, we may be able to develop tactics an strategies that will unite di erent software

can then be re-evolved to produce new versions for which the counter examples no longer apply. Through iteration of this co-evolutionary cycle we seek to obtain, not only high quality artefacts, but also test cases that can be used to demonstrate their e ectiveness.

7.5. Hyper-Heuristic Software Engineering

One key question for the SBSE/SBST research agenda is

“Can we radically increase automation by integrating SBST with other forms of SBSE?”

Consider the two connected trees depicted in Figure 4. The lower tree is a sub-tree of software engineering defined by the ACM classification system. Existing work on SBSE is currently applied at the leaves of this tree. More work can and will surely be done, across the community, within each of the leaves to better address instances of each software engineering problem. However, such approaches, on their own, can only o er optimisation of a narrow set of very similar engineering activities. That is we will have optimised test input generation and (separately) optimised requirements prioritisation. What we will still need is to find ways to unite the two so that we can have optimised tests generated from requirements, with requirements prioritised in a manner that takes account of testability.

To solve this larger software engineering challenge, SBST needs to make a transition from solving instances to automatically finding tactics that solve instances. This will increase the abstraction level at which we apply SBSE, as indicated in the upper tree in Figure 4, drawing together sets of related software engineering activities. For instance, we shall be able to combine di erent kinds of test data generation, searching for improved tactics that deploy each to maximise their e ectiveness and minimise cost, automatically tailoring the methodology to suit the particular test problem in hand.

In this way, we would be making a leap from tactics that solve classes of problems to strategies that cross the existing

software engineering boundaries, as illustrated by the top node of the upper tree in Figure 4. Ultimately, the goal would be to unify previously poorly connected areas of software engineering activity within a single computational search process. This would be a kind of ‘Hyper-Heuristic Software Engineering’.

As an example of the possibilities for Hyper-Heuristic Software Engineering, suppose we succeed in combining requirements optimisation (Zhang et al., 2008) with SBST. We shall now be able to optimise the selection of requirements based, not only on traditional aspects of SBSE for requirements (customer satisfaction, cost etc.), but also on the implications for regression testing (coverage achievable, test execution time). We would reach the pinnacle (the root) of the upper tree in Figure 4 with Hyper-Heuristic Requirements and Testing. However, we could go further still in our quest for a unified Hyper-Heuristic Software Engineering.

Suppose we now also manage to draw SBSE for project planning (Antoniol et al., 2011; Chicano and Alba, 2005) into our Hyper-Heuristic Software Engineering framework. We will then have a combined approach to optimised, requirements, project planning and testing. Instead of merely discussing requirements choices devoid of their technical and managerial consequences, we can use our combined automated approach to check the implications of requirement choices on the project plan used to sta the project and implement the requirements. We can also explore implications for regression testing and seek multi-objective solutions that balance the competing objectives of requirement choices, e ective implementation plans and ef-

ficient and e ective regression testing.

spond in real time to changing requirement choices with analysis and results on the implications for the cost and duration of the project and its testing. This would not be merely ‘better requirements engineering’ or ‘better testing’; it would be a fundamentally di erent approach to software development in which optimisation would be at the heart; a lingua franca within which decisions could be made about requirements, design and testing with detailed investigation of their consequences. Gradually, as hyper heuristic software engineering strategies draw in more of the process, the information available would be further enriched, bringing together aspects of marketing, negotiation, customer relations, project management, design and testing.

Armed with a hyper heuristicAcceptedsoftware engineering tool, decision makers could then enter negotiations armed able to re-

7.6. Optimising and Understanding Failures

Some failures are caused by exceptionally long and complex sequences of actions and events. This makes it theoretically hard (and sometimes practically impossible) to find the fault or faults that cause the failure. Therefore, a natural yet challenging and important question to ask is:

“Can we simplify the failure to make it easier to debug?”

In some ways, this problem is related to the oracle cost problem, described in Section 7.3. That is, if we can reduce the cost of understanding the output of a test, then we reduce the oracle

cost to the human. On the other hand, there is also a human cost in understanding the input to a test. If a long sequence (and/or a complex sequence) of actions is required to replicate a failure at the developers’ site, the engineers may find it too complicated to understand the causes of the failure, and therefore to di cult to find the fault(s) that cause failure.

Suppose we can capture the failing behaviour with an assertion (or some such similar mechanism). Now we can have a

fitness function that measures how close a test case comes to causingManuscripta failure to manifest itself. This would be one potential fitness function. If we can additionally measure the complexity

of a test case then we can seek to minimize this, while maximising similarity to the failure of interest; another multi-objective formulation of test data generation.

A natural starting point for failures, would be ‘wrong values in variables’, since this would be easy to capture within existing SBST frameworks: fitness computation would be no di erent to that for branch coverage. One could use a simple testability transformation (Harman, 2008; McMinn et al., 2009) to insert a branch that captures the failing behaviour and seek to cover the branch. A starting point for test complexity would be simply the length of the input sequence required to reveal the fault. The challenge will be in finding supporting fitness functions and ways to smooth an otherwise rather ‘spiky’ landscape in order to provide guidance to shorter test inputs that manifest the desired failure.

7.7. Conclusion on Search-Based Testing

Search Based Software Testing (SBST) is a branch of Search Based Software Engineering (SBSE) which (re)formulates test objectives as fitness functions to guide automated search procedures. This provides a way to automate test generation for many di erent forms of testing. The approach is supremely general and astonishingly widely applicable because any test objective that can be measured is a candidate for this transformation into a fitness function. There surely remain many exciting, important and productive test objectives that have yet to be attacked using this SBSE reformulation, thereby providing many fruitful avenues for future work.

8. Conclusion and Acknowledgement

This paper presents a survey of some most prominent techniques of automated test data generation, including symbolic execution, model-based, combinatorial, adaptive random and search-based testing.

The survey has been carried out following the novel approach of orchestrated surveys. We believe that, by coordinating renowned specialists of carefully selected topics, the approach has the merit of balancing breadth with depth of the survey to produce one article of reasonable size.

Editing this paper is new to the editors. The editors would like to thank the authors of the sections for their participation and excellent work carried out in the project. The editors would also like to express their appreciation to the reviewers of the sections. Their constructive and critical comments are invaluable to the success of the project. The editors are most grateful

to Prof. Hans van Vliet, the Editor-in-Chief of the Journal of Systems and Software, for his support to this project and valuable advices and direction given to the editors of the paper, as well as for his patience during the long process of the project.

References

Aarts, F., Vaandrager, F. W., 2010. Learning I/O automata. In: Gastin, P., Laroussinie, F. (Eds.), CONCUR, Springer. pp. 71–85.

Abrial, J. R., 1996. The B-Book: Assigning Programs to Meanings. Cambridge University Press, New York, NY, USA.

Adamopoulos, K., Harman,M. and Hierons, R. M., 2004. How to overcome the equivalent mutant problem and achieve tailored selective mutation using co-evolution. In: Proc. of the 2004 Conference on Genetic and Evolutionary Computation (GECCO ’04), pp. 1338–1349. LNCS 3103/2004, Springer.

Afzal, W., Torkar, R. and Feldt, R. , 2009. A systematic review of searchbased testing for non-functional system properties. Information and Software Technology 51(6), 957–976.

Aho, A., Dahbura, A., Lee, D., Uyar, M., 1988. An optimization technique for protocol conformance test generation based on UIO sequences and rural Chinese postman tours. In: Aggarwal, S., Sabnani, K. (Eds.), Protocol Specification, Testing, and Verification VIII, North-Holland. pp. 75–86.

de Alfaro, L., Henzinger, T. A., 2001. Interface automata. In: ESEC / SIGSOFT FSE, pp. 109–120.

Ali, S., Briand, L. C., Hemmati, H. and Panesar-Walawege, R. K., 2010. A systematic review of the application and empirical investigation of searchbased test-case generation. IEEE Transactions on Software Engineering. 36(6), 742–762.

Alshahwan, N. and Harman, M., 2011. Automated web application testing using search based software engineering. In: Proc. of the 26th IEEE/ACM International Conference on Automated Software Engineering (ASE’11), pp. 3 – 12.

Alur, R., Henzinger, T. A., Kupferman, O., Vardi, M. Y., 1998. Alternating

Anand, S., Godefroid, P., Tillmann, N., 2008. Demand-driven compositional symbolic execution. In: Proc. of the 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pp. 367–381. Springer.

Anand, S., Harrold, M. J., 2011. Heap cloning: Enabling dynamic symbolic execution of Java programs. In: Proc. of the 26th IEEE/ACM International Conference on Automated Software Engineering (ASE’11), pp. 33–42.

Anand, S., Orso, A., Harrold, M. J., 2007. Type-dependence analysis and program transformation for symbolic execution. In: Proc. of the the 13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pp. 117–133.

Anand, S., Pasareanu, C. S., Visser, W., 2009. Symbolic execution with abstraction. International Journal on Software Tools for Technology Transfer 11, 53–67.

Antoniol, G., Di Penta, M. and Harman, M., 2011. The use of search-based optimization techniques to schedule and sta software projects: An approach and an empirical study. Software — Practice and Experience 41(5), 495519.

Arcuri, A., 2008. On the automation of fixing software bugs. In: Proc. of the Doctoral Symposium of the IEEE International Conference on Software Engineering (ICSE ’08), pp. 1003–1006. ACM.

refinement relations. In: Sangiorgi,AcceptedD., de Simone, R. (Eds.), CONCUR, Springer. pp. 163–178.

Arcuri, A. and Briand, L., 2011. Adaptive random testing: An illusion of e ectiveness? In: Proc. of the 20th International Symposium on Software Testing and Analysis, pp. 265–275.

Arcuri, A. and Yao, X., 2007. Coevolving programs and unit tests from their specification. In: Proc. of the 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE’07), pp. 397–400. ACM.

Arcuri, A. and Yao, X., 2008. A novel co-evolutionary approach to automatic software bug fixing. In: Proc. of the IEEE Congress on Evolutionary Computation (CEC ’08), pp. 162–168. IEEE Computer Society.

Baars, A., Harman, M., Hassoun, M., Lakhotia, Y. K., McMinn, P., Tonella, P. and Vos, T., 2011. Symbolic search-based testing. In:Proc. of the 26th IEEE/ACM International Conference on Automated Software Engineering (ASE’11), pp. 53 - 62.

Bertolino, A., 2007. Software testing research: achievements, challenges, dreams. In: Proc. of the 1st Workshop on Future of Software Engineering (FOSE ’07) at ICSE 2007, pp. 85 - 103.

Binder, B., 2012. Open source tools for model-based testing. http://www.robertvbinder.com/robertvbinder.com/ open-source-tools-for-model-based-testing.

Bjørner, N., Tillmann, N., Voronkov, A., 2009. Path feasibility analysis for string-manipulating programs. In: Proc. of the International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pp. 307–321.

Boonstoppel, P., Cadar, C., Engler, D. R., 2008. RWset: Attacking path ex- Manuscriptplosion in constraint-based test generation. In: Proc. of the International Conference on Tools and Algorithms for the Construction and Analysis of

Systems, pp. 351–366.

Borges, M., d’Amorim, M., Anand, S., Bushnell, D., Pasareanu, C., 2012. Symbolic execution with interval constraint solving and meta-heuristic search. In: Proc. of the International Conference on Software Testing, Verification and Validation, pp. 111–120.

Bouge,´ L., Choquet, N., Fribourg, L., Gaudel, M. C., 1986. Test sets generation from algebraic specifications using logic programming. Journal of Systems and Software 6, 343–360.

Bouquet, F., Grandpierre, C., Legeard, B., Peureux, F., Vacelet, N., Utting, M., 2007. A subset of precise UML for model-based testing, in: A-MOST, ACM. pp. 95–104.

Briand,L. C., Feng, J. and Labiche, Y., 2002. Using genetic algorithms and coupling measures to devise optimal integration test orders. In: Proce. of International Conference on Software Engineering and Knowledge Engineering (SEKE’02), pp. 43–50.

Brinksma, E., Grieskamp, W., Tretmans, J., 2005. 04371 summary – perspectives of model-based testing. In: Brinksma, E., Grieskamp, W., Tretmans, J. (Eds.), Perspectives of Model-Based Testing, Internationales Begegnungsund Forschungszentrum fur¨ Informatik (IBFI), Schloss Dagstuhl, Germany, Dagstuhl, Germany. URL http://drops.dagstuhl.de/opus/ volltexte/2005/364.

Brinksma, E., Tretmans, J., 2000. Testing transition systems: An annotated bibliography. In: Cassez, F., Jard, C., Rozoy, B., Ryan, M.D. (Eds.), MOVEP, Springer. pp. 187–195.

Brownlie, R., Prowse, J., Phadke, M. S., 1992. Robust testing of AT&T

PMX/StarMAIL using OATS, AT& T Technical Journal 71 (3), 41–47. Brucker, A., Wol , B., 2012. On theorem prover-based testing. Formal Aspects

of Computing, 1–3910.1007/s00165-012-0222-y.

Brumley, D., Poosankam, P., Song, D. X., 0002, J. Z., 2008. Automatic patchbased exploit generation is possible: Techniques and implications. In: Proc. of the IEEE Symposium on Security and Privacy, pp. 143–157.

Bryce, R., Colbourn, C., 2006. Prioritized interaction testing for pair-wise coverage with seeding and constraints, Journal of Information and Software Technology 48 (10), 960–970.

Bryce, R. C., Colbourn, C. J., 2007. One-test-at-a-time heuristic search for interaction test suites. In: Proc. of the Conference on Genetic and Evolutionary Computation (GECCO’07), Search Based Software Engineering Track, pp. 258–269.

Burroughs, K., Jain, A., Erickson, R. L., 1994. Improved quality of protocol testing through techniques of experimental design. In: Supercomm/IC: Proc. of IEEE International Conference on Communications, pp. 745 – 752.

Cadar, C., Dunbar, D., Engler, D. R., 2008. KLEE: Unassisted and automatic generation of high-coverage tests for complex systems programs. In: Proc. of the Symposium on Operating Systems Design and Implementation, pp. 209–224.

Cadar, C., Godefroid, P., Khurshid, S., Pasareanu, C. S., Sen, K., Tillmann, N., Visser, W., 2011. Symbolic execution for software testing in practice: preliminary assessment. In: Proc. of the International Conference on Software Engineering (ICSE’11, pp. 1066–1071.

Cai, K.-Y., 2002. Optimal software testing and adaptive software testing in the context of software cybernetics. Information and Software Technology, 44(14), 841–855.

Calvagna, A. and Gargantini, A., 2009. Combining satisfiability solving and heuristics to constrained combinatorial interaction testing. In: Proc. of the 3rd International Conference on Tests and Proofs (TAP’09), pp. 27–42.

Calvagna, A. and Gargantini, A., 2010. A formal logic approach to constrained combinatorial testing, Journal of Automated Reasoning 45, 331–358.

Campbell, C., Grieskamp, W., Nachmanson, L., Schulte, W., Tillmann, N.,

Veanes, M., 2005. Testing concurrent object-oriented systems with spec explorer. In: Fitzgerald, J., Hayes, I.J., Tarlecki, A. (Eds.), FM, Springer. pp. 542–547.

Castro, M., Costa, M., Martin, J. P., 2008. Better bug reporting with better privacy. In: Proc. of the International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS’08), pp. 319– 328.

Chan, K. P., Chen, T. Y. and Towey, D., 2006. Forgetting test cases. In:Proc. of the 30th Annual International Computer Software and Application Conference (COMPSAC’06), pp. 485–492.

Chan, K. P., Chen, T. Y. and Towey, D., 2006. Restricted random testing: Adaptive random testing by exclusion. International Journal of Software Engineering and Knowledge Engineering 16(4), 553–584.

Chen, T. Y., Eddy, G. R., Merkel, G. and Wong, P. K., 2004. Adaptive random testing through dynamic partitioning. In:Proc. of the 4th International Conference on Quality Software (QSIC’04, pp. 79–86.

Chen, T. Y., Kuo, F.-C. and Liu, H., 2009. Adaptive random testing based on distribution metrics. Journal of Systems and Software 82(9), 1419–1433.

Chen, T. Y., Kuo, F.-C. and Merkel, R. G., 2006. On the statistical properties of testing e ectiveness measures. Journal of Systems and Software 79(5), 591–601.

Chen, T. Y., Kuo, F.-C., Merkel, R. G. and Ng, S. P., 2004. Mirror adaptive random testing. Information and Software Technology 46(15), 1001–1010.

Chen, T. Y., Kuo, F.-C., Merkel, R. G. and Tse, T. H., 2010. Adaptive random testing: the ART of test case diversity. Journal of Systems and Software 83(1), 60–66.

Chen, T. Y., Kuo, F.-C. and Zhou, Z. Q., 2007. On favourable conditions for adaptive random testing. International Journal of Software Engineering and Knowledge Engineering 17(6), 805–825.

Chen, T. Y., Leung, H. and Mak, I. K., 2004. Adaptive random testing. In:Proc. of the 9th Asian Computing Science Conference, LNCS 3321, pp. 320–329.

Chen, T. Y. and Merkel, R. 2008. An upper bound on software testing e ectiveness. ACM Transactions on Software Engineering and Methodology 17(3), 16:1–16:27.

Chen, T. Y., Tse, T. H. and Yu, Y. T. 2001. Proportional sampling strategy: A compendium and some insights. Journal of Systems and Software 58(1),

Chicano, F. and Alba, E., 2005. Management of software projects with GAs. In: Proc. of the 6th Metaheuristics International Conference (MIC’05).

Chipounov, V., Kuznetsov, V., Candea, G., 2011. S2e: a platform for in-vivo multi-path analysis of software systems. In: Proc. of the 16th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS’11), pp. 265–278.

Chow, T., 1978. Testing software design modeled by finite-state machines. IEEE Transactions on Software Engineering 4, 178–187.

Ciupa, I., Leitner, A. Oriol, M. and Meyer, B., 2008. ARTOO: Adaptive random testing for object-oriented software. In: Proc. of the 30th International Conference on Software Engineering (ICSE’08), pp. 71–80.

Claessen, K., Hughes, J., 2000. QuickCheck: a lightweight tool for random testing of haskell programs. In: Odersky, M., Wadler, P. (Eds.), Proc. of the 5th ACM SIGPLAN International Conference on Functional Programming (ICFP’00), ACM. pp. 268–279.

Clements, P., Northrop, L. M., 2001. Software Product Lines: Practices and Patterns, Addison Wesley.

Cochran, W. G., Cox, G. M., 1957. Experimental Designs, 2nd Edition, J. Wiley & Sons, Inc., New York.

Cohen, D. M., Dalal, S. R., Parelius, J., Patton, G. C., 1996. The combinatorial design approach to automatic test generation. IEEE Software 13 (5), 83–88.

Cohen, D. M., Dalal, S. R., Fredman, M. L., Patton, G. C., 1997. The AETG system: an approach to testing based on combinatorial design. IEEE Transactions on Software Engineering 23 (7), 437–444.

Cohen, M. B., Colbourn, C. J., Gibbons, P. B., Mugridge, W. B., 2003. Constructing test suites for interaction testing. In: Proc. of the 25th International Conference on Software Engineering (ICSE’03), pp. 38–48.

Cohen, M. B., Colbourn, C. J., Collofello, J., Gibbons, P. B., Mugridge, W. B., 2003. Variable strength interaction testing of components. In: Proc. of the 27th IEEE International Computer Software and Applications Conference (COMPSAC’03), pp. 413–418.

Cohen, M. B., Colbourn, C. J., Ling, A. C. H., 2003. Augmenting simulated annealing to build interaction test suites. In: Proc. of the 14th IEEE International Symposium on Software Reliability Engineering (ISSRE’03), pp.

394–405.

Cohen, M. B., Dwyer, M. B., Shi, J., 2006. Coverage and adequacy in software product line testing. In: Proc. of the ISSTA 2006 Workshop on the Role of Architecture for Testing and Analysis (ROSATEA ’06), pp. 53–63.

Cohen, M. B., Dwyer, M. B. Shi, J. ,2008. Constructing interaction test suites for highly-configurable systems in the presence of constraints: A greedy approach. IEEE Transactions on Software Engineering 34 (5), 633–650.

Cohen, M. B., Gibbons, P. B., Mugridge, W. B. and Colbourn, C. J., 2003. Constructing test suites for interaction testing. In:Proc. of the 25th International Conference on Software Engineering (ICSE’03), pp. 38–48. IEEE Computer Society.

Colanzi,ManuscriptT. E., Assunc¸ao,˜ W. K. G., Vergilio, S. R. and Pozo, A. T. R., 2011. Integration test of classes and aspects with a multi-evolutionary and coupling-

based approach. In: Proc. of the 3rd International Symposium on Search

Based Software Engineering (SSBSE ’11). Springer.

Colbourn, C. J., 2004. Combinatorial aspects of covering arrays. Le Matem-

atiche (Catania) 58, 121–167.

Colbourn, C. J., 2012. Covering array tables. Available at http://www.

public.asu.edu/~ccolbou/src/tabby/catable.html.

Colbourn, C. J., Cohen, M. B., Turban, R. C. , 2004. A deterministic density algorithm for pairwise interaction coverage. In: Proc. of the IASTED

International Conference on Software Engineering, pp. 345–352.

Colbourn, C., McClary, D., 2008. Locating and detecting arrays for interaction

faults. Journal of Combinatorial Optimization 15 (1), 17–48.

Czerwonka, J., 2006. Pairwise testing in real world. In: Proc. of the Pacific

Northwest Software Quality Conference, pp. 419–430.

Dalal, S. R., Jain, A., Patton, G., Rathi, M., Seymour, P., 1998. AETGS M web: a Web based service for automatic e cient test generation from functional requirements. In: Proc. of the 2nd IEEE Workshop on Industrial Strength

Formal Specification Techniques (WIFT’98), pp. 84–85.

Dan, H., Hierons, R.M., 2011. Conformance testing from message sequence charts, in: Proc. of the 4th IEEE International Conference on Software Testing, Verification and Validation (ICST’11), pp. 279–288. IEEE Computer Society.

Derderian, K., Hierons, R., Harman, M. and Guo, Q., 2006. Automated Unique Input Output sequence generation for conformance testing of FSMs. The computer Journal 49(3), 331–344.

Dick, J., Faivre, A., 1993. Automating the generation and sequencing of

test cases from model-based specifications. In: Woodcock, J., Larsen, P.G. (Eds.), FME ’93: Industrial-Strength Formal Methods, LNCS 670, pp. 268– 284. Springer.

Dumlu, E., Yilmaz, C., Cohen, M. B., Porter, A., 2011. Feedback driven adaptive combinatorial testing. In: Proc. of the 2011 International Symposium on Software Testing and Analysis (ISSTA’11), pp. 243–253.

Dunietz, I. S., Ehrlich, W. K., Szablak, B. D., Mallows, C. L., Iannino, A., 1997. Applying design of experiments to software testing. In: Proc. of the 19th International Conference on Software Engineering, (ICSE’97), pp. 205–215.

Dutertre, B., de Moura, L., 2006. A Fast Linear-Arithmetic Solver for DPLL(T). In: Proc. of the 18th International Conference on Computer Aided Verification (CAV’06), pp. 81–94.

Ehrig, H., Mahr, B., 1985. Fundamentals of Algebraic Specification 1: Equations and Initial Semantics. volume 6 of Monographs in Theoretical Computer Science. An EATCS Series. Springer.

Ernits, J. P., Kull, A., Raiend, K., Vain, J., 2006. Generating tests from efsm models using guided model checking and iterated search refinement. In: (Havelund et al., 2006). pp. 85–99. pp. 85–99.

ETSI, 2011b. Requirements for Modelling Notations. Technical Report ES 202 951. ETSI.

Fisher, R. A., 1971. The Design of Experiments, 8th Edition. Hafner Publishing Company, New York.

Fouche,´ S., Cohen, M. B., Porter, A., 2009. Incremental covering array failure characterization in large configuration spaces. In: Proc. of the 18th International Symposium on Software Testing and Analysis (ISSTA’09), pp. 177–187.

Feijs, L. M. G., Goga, N., Mauw, S., Tretmans, J., 2002. Test selection, trace distance and heuristics. In: Schieferdecker, I., Konig,¨ H., Wolisz, A. (Eds.), Testing of Communicating Systems XIV, Applications to Internet Technologies and Services, Proceedings of the IFIP 14th International Conference on Testing Communicating Systems (TestCom 2002), pp. 267–282. Kluwer.

Frantzen, L., Tretmans, J., Willemse, T. A. C., 2004. Test generation based on