Hadi Hemmati
Skip Abstract Section
Abstract
The increase in size and complexity of modern software systems requires scalable, systematic, and automated testing approaches. Model-based testing (MBT), as a systematic and automated test case generation technique, is being successfully applied to verify industrial-scale systems and is supported by commercial tools. However, scalability is still an open issue for large systems, as in practice there are limits to the amount of testing that can be performed in industrial contexts. Even with standard coverage criteria, the resulting test suites generated by MBT techniques can be very large and expensive to execute, especially for system level testing on real deployment platforms and network facilities. Therefore, a scalable MBT technique should be flexible regarding the size of the generated test suites and should be easily accommodated to fit resource and time constraints. Our approach is to select a subset of the generated test suite in such a way that it can be realistically executed and analyzed within the time and resource constraints, while preserving the fault revealing power of the original test suite to a maximum extent. In this article, to address this problem, we introduce a family of similarity-based test case selection techniques for test suites generated from state machines. We evaluate 320 different similarity-based selection techniques and then compare the effectiveness of the best similarity-based selection technique with other common selection techniques in the literature. The results based on two industrial case studies, in the domain of embedded systems, show significant benefits and a large improvement in performance when using a similarity-based approach. We complement these analyses with further studies on the scalability of the technique and the effects of failure rate on its effectiveness. We also propose a method to identify optimal tradeoffs between the number of test cases to run and fault detection.
- Aarts, E. H. L. and Lenstra, J. K. 2003. Local Search in Combinatorial Optimization. Princeton University Press. Google Scholar
Digital Library
- Ali, S., Briand, L. C., Hemmati, H., and Panesar-Walawege, R. K. 2010a. A systematic review of the application and empirical investigation of search-based test-case generation. IEEE Trans. Software Eng. 36, 742--762. Google ScholarDigital Library
- Ali, S., Hemmati, H., Holt, N. E., Arisholm, E., and Briand, L. 2010b. Model transformations as a strategy to automate model-based testing: A tool and industrial case studies Simula Research Laboratory, Tech. Rep. 2010-01.Google Scholar
- Arcuri, A. 2010. Longer is better: On the role of test sequence length in software testing. In Proceedings of the IEEE International Conference on Software Testing, Verification and Validation. 469--478 Google ScholarDigital Library
- Arcuri, A. and Briand, L. 2011. A practical guide for using statistical tests to assess randomized algorithms in software engineering. In Proceedings of the ACM/IEEE International Conference on Software Engineering. Google ScholarDigital Library
- Arcuri, A. and Yao, X. 2008. Search based software testing of object-oriented containers. Inf. Sci. 178, 3075--3095. Google ScholarDigital Library
- Binder, R. V. 1999. Testing Object-Oriented Systems: Models, Patterns, and Tools. Addison-Wesley Professional. Google ScholarDigital Library
- Cartaxo, E. G., Machado, P. D. L., and Neto, F. G. O. 2011. On the use of a similarity function for test case selection in the context of model-based testing. Software Test. Verif. Reliab. 21, 2, 75--110. Google ScholarDigital Library
- Chen, T. Y., Kuoa, F. C., Merkela, R. G., and Tseb, T. H. 2010. Adaptive Random Testing: The ART of test case diversity. J. Syst. Software 83, 60--66. Google ScholarDigital Library
- Chen, Y., Probert, R. L., and Ural, H. 2009. Regression test suite reduction based on SDL models of system requirements. J. Software Maintenance Evol. Res. Pract. 21, 379--405. Google ScholarDigital Library
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. 2001. Introduction to Algorithms. MIT Press. Google ScholarDigital Library
- Dalal, S., Jain, A., and Poore, J. 2005. Workshop on advances in model-based software testing. In Proceedings of the 27th International Conference on Software Engineering. 680. Google ScholarDigital Library
- Dong, G. and Pei, J. 2007. Sequence Data Mining. Springer. Google ScholarDigital Library
- Droste, S., Jansen, T., and Wegener, I. 2002. On the analysis of the (1+1) evolutionary algorithm. Theor. Comput. Sci. 276, 51--81. Google ScholarDigital Library
- Durbin, R., Eddy, S. R., Krogh, A., and Mitchison, G. 1999. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press.Google Scholar
- Elbaum, S. G., Malishevsky, A. G., and Rothermel, G. 2002. Test case prioritization: A family of empirical studies. IEEE Trans. Software Eng. 28, 159--182. Google ScholarDigital Library
- Feldt, R., Torkar, R., Gorschek, T., and Afzal, W. 2008. Searching for cognitively diverse tests: Towards universal test diversity metrics. In Proceedings of the 1st Workshop on Search-Based Software Testing. 178--186. Google ScholarDigital Library
- Feller, W. 1968. An Introduction to Probability Theory and Its Applications. Wiley.Google Scholar
- Gamma, E., Helm, R., Johnson, R., and Vlissides, J. 1995. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley. Google ScholarDigital Library
- Goldberg, D. E. 2001. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Professional.Google Scholar
- Gusfield, D. 1997. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press. Google ScholarDigital Library
- Hamlet, R. 1994. Random testing. In Encyclopedia of Software Engineering. Wiley, 970--978.Google Scholar
- Harman, M. 2007. The current state and future of search based software engineering. In Proceedings of the Conference on the Future of Software Engineering. IEEE Computer Society, 342--357. Google ScholarDigital Library
- Harman, M. and Jones, B. F. 2001. Search-based software engineering. Inf. Software Tech. 43, 833--839.Google ScholarCross Ref
- Harman, M. and McMinn, P. 2010. A theoretical and empirical study of search based testing: Local, global and hybrid search. IEEE Trans. Software Eng. 36, 226--247. Google ScholarDigital Library
- Haupt, R. L. and Haupt, S. E. 1998. Practical Genetic Algorithms. Wiley-Interscience. Google ScholarDigital Library
- Hemmati, H., Arcuri, A., and Briand, L. 2010b. Reducing the cost of model-based testing through test case diversity. In Proceedings of the 22nd IFIP International Conference on Testing Software and Systems. Lecture Notes in Computer Science, vol. 6435. 63--78. Google ScholarDigital Library
- Hemmati, H., Arcuri, A., and Briand, L. 2011. Empirical investigation of the effects of test suite properties on similarity-based test case selection. In Proceedings of the 4th International Conference on Software Testing, Verification and Validation. Google ScholarDigital Library
- Hemmati, H. and Briand, L. 2010. An industrial investigation of similarity measures for model-based test case selection. In Proceedings of the 21st IEEE International Symposium on Software Reliability Engineering. 141--150. Google ScholarDigital Library
- Hemmati, H., Briand, L., Arcuri, A., and Ali, S. 2010a. An enhanced test case selection approach for model-based testing: An industrial case study. In Proceedings of the 18th ACM International Symposium on Foundations of Software Engineering. 267--276. Google ScholarDigital Library
- Jain, A. K. 2010. Data clustering: 50 years beyond K-means. Pattern Recognit. Lett. 31, 8, 651--666. Google ScholarDigital Library
- Jiang, B., Zhang, Z., Chan, W. K., and Tse, T. H. 2009. Adaptive random test case prioritization. In Proceedings of the 25th IEEE/ACM International Conference on Automated Software Engineering. 233--244. Google ScholarDigital Library
- Jones, J. A. and Harrold, M. J. 2003. Test-suite reduction and prioritization for modified condition/decision coverage. IEEE Trans. Software Eng. 29, 195--209. Google ScholarDigital Library
- Jourdan, G. V., Ritthiruangdech, P., and Ural, H. 2006. Test suite reduction based on dependence analysis. In Proceedings of the 21th International Symposium on Computer and Information Sciences. Springer, 1021--1030. Google ScholarDigital Library
- Korel, B., Koutsogiannakis, G., and Tahat, L. H. 2007. Model-based test prioritization heuristic methods and their evaluation. In Proceedings of the 3rd Workshop on Advances in Model Based Testing. 34--43. Google ScholarDigital Library
- Lakhotia, K., Harman, M., and McMinn, P. 2007. A multi-objective approach to search-based test data generation. In Proceedings of the Genetic and Evolutionary Computation Conference. 1098--1105. Google ScholarDigital Library
- Ledru, Y., Petrenko, A., and Boroday, S. 2009. Using string distances for test case prioritisation. In Proceedings of the 24th IEEE/ACM International Conference on Automated Software Engineering. 510--514. Google ScholarDigital Library
- Leon, D. and Podgurski, A. 2003. A comparison of coverage-based and distribution-based techniques for filtering and prioritizing test cases. In Proceedings of the 14th IEEE International Symposium on Software Reliability Engineering. 442--456. Google ScholarDigital Library
- Li, Z., Harman, M., and Hierons, R. M. 2007. Search algorithms for regression test case prioritization. IEEE Trans. Software Eng. 33, 225--237. Google ScholarDigital Library
- Ma, X. Y., Sheng, B. K. and Ye, C. Q. 2005. Test-Suite Reduction Using Genetic Algorithm. In Advanced Parallel Processing Technologies. Springer, 253--262. Google ScholarDigital Library
- Manning, C. D., Raghavan, P., and Schütze, H. 2008. Introduction to Information Retrieval. Cambridge University Press. Google ScholarDigital Library
- Masri, W., Podgurski, A., and Leon, D. 2007. An empirical study of test case filtering techniques based on exercising information flows. IEEE Trans. Software Eng. 33, 454--477. Google ScholarDigital Library
- Mathur, A. P. 2008. Foundations of Software Testing. Addison-Wesley Professional. Google ScholarDigital Library
- McMaster, S. and Memon, A. 2008. Call-stack coverage for GUI test suite reduction. IEEE Trans. Software Eng. 34, 99--115. Google ScholarDigital Library
- Michalewicz, Z. and Schoenauer, M. 1996. Evolutionary Algorithms for Constrained Parameter Optimization Problems. Evol. Comput. 4, 1--32. Google ScholarDigital Library
- Moscato, P. and Cotta, C. 2010. A modern introduction to memetic algorithms. In Handbook of Metaheuristics. Springer, 141--183.Google Scholar
- Orso, A., Do, H., Rothermel, G., Harrold, M. J., and Rosenblum, D. S. 2007. Using component metadata to regression test component-based software. Software Test. Verif. Reliab. 17, 61--94. Google ScholarDigital Library
- Pender, T. 2003. UML Bible. Wiley. Google ScholarDigital Library
- Ramanathan, M. K., Koyutürk, M., Grama, A., and Jagannathan, S. 2008. PHALANX: A graph-theoretic framework for test case prioritization. In Proceedings of the 23rd Annual ACM Symposium on Applied Computing. 667--673. Google ScholarDigital Library
- Rothermel, G., Harrold, M. J., Ronne, J. V., and Hong, C. 2002. Empirical studies of test-suite reduction. Software Test. Verif. Reliab. 12, 219--249.Google ScholarCross Ref
- Simão, A. D. S., Mello, R. F. D., and Senger, L. J. 2006. A technique to reduce the test case suites for regression testing based on a self-organizing neural network architecture. In Proceedings of the 30th Annual International Computer Software and Applications Conference. 93--96. Google ScholarDigital Library
- Tan, P. N., Steinbach, M., and Kumar, V. 2006. Introduction to Data Mining. Addison-Wesley. Google ScholarDigital Library
- Utting, M. and Legeard, B. 2006. Practical Model-Based Testing: A Tools Approach. Morgan-Kaufmann. Google ScholarDigital Library
- Vaandrager, F. W. 2006. Does it pay off? Model-based verification and validation of embedded systems. Tech.Rep. ICIS-R06019, ICIS Radboud University Nijmegen, 43--66.Google Scholar
- Vargha, A. and Delaney, H. D. 2000. A critique and improvement of the CL common language effect size statistics of McGraw and Wong. J. Educ. Behav. Stat. 25, 101--132.Google Scholar
- Vega, D., Schieferdecker, I., and Din, G. 2007. Test data variance as a test quality measure: Exemplified for TTCN-3. In Proceedings of the 19th IFIP International Conference on Testing of Communicating Systems and 7th International Workshop on Formal Approaches to Testing of Software. 351--364. Google ScholarDigital Library
- White, L. J. and Cohen, E. I. 1980. A domain strategy for computer program testing. IEEE Trans. Software Eng. 6, 247--257. Google ScholarDigital Library
- Whitley, D. 1989. The GENITOR algorithm and selection pressure: Why rank-based allocation of reproductive trials is best. In Proceedings of the 3rd International Conference on Genetic Algorithms. 116--121. Google ScholarDigital Library
- Wohlin, C., Runeson, P., Host, M., Ohlsson, M. C., Regnell, B., and Wesslen, A. 2000. Experimentation in Software Engineering: An Introduction. Kluwer Academic Publishers. Google ScholarDigital Library
- Wolpert, D. and Macready, W. G. 1997. No free lunch theorems for optimization. IEEE Trans. Evol. Comput. 1, 67--82. Google ScholarDigital Library
- Xiao, M., El-Attar, M., Reformat, M., and Miller, J. 2007. Empirical evaluation of optimization algorithms when used in goal-oriented automated test data generation techniques. Empirical Soft. Eng. 12, 183--239. Google ScholarDigital Library
- Xu, R. and Wunsch, D. 2005. Survey of clustering algorithms. IEEE Trans. Neural Networks 16, 645--678. Google ScholarDigital Library
- Yoo, S., Harman, M., Tonella, P., and Susi, A. 2009. Clustering test cases to achieve effective and scalable prioritisation incorporating expert knowledge. In Proceedings of the 18th ACM International Symposium on Software Testing and Analysis. 201--212. Google ScholarDigital Library
Index Terms
- Achieving scalable model-based testing through test case diversity
Recommendations
An enhanced test case selection approach for model-based testing: an industrial case study
FSE '10: Proceedings of the eighteenth ACM SIGSOFT international symposium on Foundations of software engineeringIn recent years, Model-Based Testing (MBT) has attracted an increasingly wide interest from industry and academia. MBT allows automatic generation of a large and comprehensive set of test cases from system models (e.g., state machines), which leads to ...
Reducing the cost of model-based testing through test case diversity
ICTSS'10: Proceedings of the 22nd IFIP WG 6.1 international conference on Testing software and systemsModel-based testing (MBT) suffers from two main problems which in many real world systems make MBT impractical: scalability and automatic oracle generation. When no automated oracle is available, or when testing must be performed on actual hardware or a ...
On the use of a similarity function for test case selection in the context of model-based testing
Test case selection in model-based testing is discussed focusing on the use of a similarity function. Automatically generated test suites usually have redundant test cases. The reason is that test generation algorithms are usually based on structural ...
Comments