Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Empirical Software Engineering
Published in: Empirical Software Engineering 1/2018

05-02-2017

Genetic Algorithm-based Test Generation for Software Product Line with the Integration of Fault Localization Techniques

Authors: Xuelin Li, W. Eric Wong, Ruizhi Gao, Linghuan Hu, Shigeru Hosono

Published in: Empirical Software Engineering | Issue 1/2018

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In response to the highly competitive market and the pressure to cost-effectively release good-quality software, companies have adopted the concept of software product line to reduce development cost. However, testing and debugging of each product, even from the same family, is still done independently. This can be very expensive. To solve this problem, we need to explore how test cases generated for one product can be used for another product. We propose a genetic algorithm-based framework which integrates software fault localization techniques and focuses on reusing test specifications and input values whenever feasible. Case studies using four software product lines and eight fault localization techniques were conducted to demonstrate the effectiveness of our framework. Discussions on factors that may affect the effectiveness of the proposed framework is also presented. Our results indicate that test cases generated in such a way can be easily reused (with appropriate conversion) between different products of the same family and help reduce the overall testing and debugging cost.
next article Experiences and challenges in building a data intensive system for data migration

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
In the rest of this paper, “a structural component is covered” and “a structural component is executed” are equivalent.
 
2
Without loss of generality, program components are considered to be statements for the rest of the paper.
 
3
Several other encoding approaches exist, such as permutation encoding, value encoding, and tree encoding. In this paper, we focus on binary encoding.
 
4
If the absolute values of the upper bound and lower bound differ, we choose the one with greater absolute value to determine the number of bits needed.
 
5
We assume that the upper bound and lower bound of the parameter are 15.00 and −15.00, respectively. Since (15)10 = (1111)2, we only need four bits to represent the integer part of the parameter.
 
6
For the purposes of illustration, we assume this is guaranteed by the input verification module, which is not included in the source code.
 
7
For the purposes of illustration, we assume this is guaranteed by the input verification module, which is not included in the source code.
 
8
(111111)2 = (63)10
 
9
For any general GA-based technique, at least two initial test cases are needed to generate new test cases. As a result, the minimum size of test sets is 2.
 
10
For JFreeChart, we only include statement coverage and condition coverage due to the lack of tools in collecting data regarding all-use coverage.
 
Literature
Abreu R, Zoeteweij P, Golsteijn R, Van Gemund AJC (2009) A practical evaluation of spectrum-based fault localization. J Syst Softw 82(11):1780–1792CrossRef
Andrews JH, Briand LC, Labiche Y (2005) Is mutation an appropriate tool for testing experiments? In: Proceedings of the 27th International Conference on Software Engineering (ICSE ‘05), pp 402–411, St. Louis, USA
Ahmed MA, Hermadi I (2008) GA-based multiple paths test data generator. Comp Operat Res 35(10):3107–3124CrossRef
Ahmed ZH (2010) Genetic algorithm for the traveling salesman problem using sequential constructive crossover operator. J Biom Bioinformat 3(6):96–105
Beohar H, Varshosaz M, Mousavi MR (2016) Basic behavioral models for software product lines: expressivenss and testing pre-orders. Sci Comput Program 123:42–60CrossRef
Bertolino A, Gnesi S (2003) Pluto: a test methodology for product families, 5th Interantional Workshop on Software Product-Family. Engineering 3014:181–197
Burdek J, Lochau M, Bauregger S, Holzer A, von Rhein A, Apel S, Beyer D (2015) Facilitating Reuse in Multi-goal Test-Suite Generation for Software Product Lines, in Proceedings of the 18th International Conference on Fundamental Approaches to Software Engineering (FASE), pp 84–99, April 11–18, 2015
Chen TY, Kuo F, Liu H, Wong WE (2013) Code coverage of adaptive random testing. IEEE Trans Reliab 62(1):226–237CrossRef
Clements P, Northrop L (2001) Software product lines: practices and patterns. Addison-Wesley Longman Publishing Co., Inc., Boston
Do H, Rothermel G (2006) On the use of mutation faults in empirical assessments of test case prioritization techniques. IEEE Trans Softw Eng 32(9):733–752CrossRef
Dustin E, Garrentt T, Gauf (2009) Why automate? Automated software testing ROI explained, Inform IT, April 2009
Engström E, Runeson P (2011) Software product line testing – a systematic mapping study. Informat Softw Technol 53(1):2–13CrossRef
Ensan F, Bagheri E, Gašević D (2012) Evolutionary search-based test generation for software product line feature models. In: Proceedings of the 24th International Conference on Advanced Information Systems Engineering, pp 613–628, June 2012
Everitt BS (1977) The analysis of contingency tables. Chapman & Hall, Ltd., London
Fischer S, Lopez-Herrejon RR, Ramler R, Egyed A (2016) A preliminary empirical assessment of similarity for combinatorial interaction testing of software product lines. In: Proceedings of the 9th International Workshop on Search-Based Software Testing (SBST), pp 15–18, May 16–17, 2016
Forgy EW (1965) Cluster analysis of multivariate data: efficiency versus interpretability of classifications. Biometrics 21:768–769
Freeman D (1987) Applied categorical data analysis. Marcel Dekker, Inc., New York
Gao R, Wong WE, Chen Z, Wang Y (2015) Effective software fault localization using predicated execution results. Softw Qual J. doi:10.​1007/​s11219-015-9295-1, online since November 11, 2015
Goel AL (1985) Software reliability models: assumptions, limitations and applicability. IEEE Trans Softw Eng 11(12):1411–1423CrossRef
Goodman LA, Duncan OD (1984) The analysis of cross-classification data having ordered categories. Harvard University Press, Cambridge
Guo J, White J, Wang G, Li J, Wang Y (2011) a genetic algorithm for optimized feature selection with resource constraints in software product lines. J Syst Softw 84(12):2208–2221
Hall RJ (2015) Fundamental nonmodularity in electronic mail. Automat Softw Eng 12(1):41–79CrossRef
Harman M, Jia Y, Krinke J, Langdon WB, Petke J, Zhang Y (2014) Search based software engineering for software product line engineering: a survey and directions for future work. In: Proceedings of the 18th International Software Product Line Conference, Vol. 1, pp 5–18, September 2014, Florence, Italy
Hartigan JA, Wong MA (1979) Algorithm AS 136: a K-Means clustering algorithm. Appl Stat 28(1):100–108CrossRefMATH
Henard C, Papadakis M, Perrouin G, Klein J, Traon YL (2013) Towards automated testing and fixing of re-engineered feature models. In: Proceedings of the 35th International Conference on Software Engineering, pp 1245–1248
Henard C, Papadakis M, Perrouin G, Klein J, Heymans P, Le Traon Y (2014) Bypassing the combinatorial explosion: using similarity to generate and prioritize t-wise test configurations for software product lines. IEEE Trans Softw Eng 40(7):650–670
Henard C, Papadakis M, Traon YL (2014) Mutation-based generation of software product line test configurations. In: Proceedings of the 6th Symposium on Search Based Software Engineering, pp 92–106, August 2014
Jones JA, Harrold MJ (2005) Empirical evaluation of the tarantula automatic fault-localization technique. In: Proceedings of the 20th IEEE/ACM Conference on Automated Software Engineering, pp 273–282, Long Beach, California, USA, December, 2005
Kakarontzas G, Stamelos I, Katsaros P (2008) Product Line variability with elastic components and test-driven development. In: Proceedings of the 5th IEEE International Conference on Computational Intelligence for Modeling Control and Automation, Vienna, Austria, pp 146–151, December
Lee K, Kang KC, Lee J (2002) Concepts and guidelines of feature modeling for product line software engineering. In: Proceedings of the 7th International Conference on Software Reuse: Methods, Techniques, and Tools. ICSR-7. pp 62–77, London, UK, 2002
Liu C, Fei L, Yan X, Han J, Midkiff SP (2006) Statistical debugging: a hypothesis testing-based approach. IEEE Trans Softw Eng 32(10):831–848CrossRef
Lopez-Herrejon RE, Fischer S, Ramler R, Egyed A (2015) A first systematic mapping study on combinatorial interaction testing for software product lines. In: Companion of the Eighth IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW 2015), pp 1–10, Graz, Austria, April 13–17, 2015
MacQueen J (1967) Some methods for classification and analysis of multivariate observations. In: Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. vol. 1, pp 281–297, June, 1967
Mathur AP (2008) Foundation of software testing. Addison-Wesley Professional, Indianapolis
Mohamed Ali M, Moawad R (2010) An approach for requirements based software product line testing. The 7th International Conference on Informatics and Systems, pp 1–10, March 2010
McGregor JD (2001) Testing a software product line. Technical Report, CMU/SEI-2001-TR-022, December 2001
Michael CC, McGraw G, Schatz MA (2001) Generating software test data by evolution. IEEE Trans Softw Eng 27(12):1085–1110CrossRef
Mitchell M (1998) An introduction to genetic algorithms. MIT Press, Cambridge
Namin AS, Andrews JH, Labiche Y (2006) Using mutation analysis for assessing and comparing testing coverage criteria. IEEE Trans Softw Eng 32(8):608–624CrossRef
Naish L, Lee HJ, Ramamohanarao K (2011) A model for spectra-based software diagnosis. ACM Trans Softw Eng Method 20(3):11:1–11:32
Nebut C, Pickin S, Le Traon Y, Jezequel J (2003) Automated requirements-based generation of test cases for product families. In: Proceedings of 18th IEEE International Conference on Automated Software Engineering, pp 263–266, October 2003
NIST Report (2002) Software errors cost U.S. Economy $59.5 Billion Annually, NIST Planning Report 02-3, May 2002
Offutt AJ, Lee A, Rothermel G, Untch RH, Zapf C (1996) An experimental determination of sufficient mutant operators. ACM Trans Softw Eng Method 5(2):99–118CrossRef
Perrouin G, Oster S, Sen S, Klein J, Baudry B, le Traon Y (2012) Pairwise testing for software product lines: comparison of two approaches. Softw Qual J 22(3–4):605–643CrossRef
Perrouin G, Sen S, Klein J, Baudry B, le Traon Y (2010) Automated and scalable t-wise test case generation strategies for software product lines. In: Proceedings of International Conference on Software Testing, Verification and Validation, pp 459–468, Paris, France, April 2010
Pohl K, Böckle G, Linden FJ (2005) Software product line engineering: foundations, principles, and techniques. Springer, HeidelbergCrossRefMATH
Pohl K, Metzger A (2006) Software product line testing. Commun ACM 49(12):78–81CrossRef
Reis S, Metzger A, Pohl K (2006) A reuse technique for performance testing of software product lines. In: Proceedings of the 11th International Software Product Line Conference, pp 5–10, Baltimore, MD, USA, August 2006
Sinha S, Dasch T, Ruf R (2011) Governance and cost reduction through multi-tier preventive performance tests in a large-scale product line development. In: Proceedings of 15th IEEE International Software Product Line Conference, pp 295–302, Munich, Germany, August 2011
Sivanandam SN, Deepa SN (2008) Introduction to genetic algorithms. Springer, HeidelbergMATH
Tijms H (2004) Understanding probability: chance rules in everyday life. Cambridge University Press, Cambridge
Vessy I (1985) Expertise in debugging computer programs: a process analysis. Int J Man Machine Stud 23(5):459–494CrossRef
Wang S, Ali S, Gotlieb A (2015) Cost-effective test suite minimization in product lines using search techniques. J Syst Softw 103:370–391CrossRef
Wang S, Gotlieb A, Ali S, Liaaen M (2012) Automated selection of test cases using feature model: an industrial case study. Technical Report (2012-20), Simula Research Laboratory, 2012
Wong WE, Debroy V, Choi B (2010) A family of code coverage-based heuristics for effective fault localization. J Syst Softw 83(2):188–208CrossRef
Wong WE, Debroy V, Li Y, Gao R (2012) Software fault localization using DStar (D*). In: Proceedings of The 6th IEEE International Conference on Software Security and Reliability (SERE), pp 21–30, Washington D.C., June, 2012
Wong WE, Debroy V, Li Y, Gao R (2014) The DStar method for effective software fault localization. IEEE Trans Reliab 62(4):290–308CrossRef
Wong WE, Debroy V, Xu D (2012b) Towards better fault localization: a crosstab-based statistical approach. IEEE Trans Syst, Man, Cybernet − Part C 42(3):378–396CrossRef
Wong WE, Mathur AP (1995a) Fault detection effectiveness of mutation and data flow testing. Softw Qual J 4(1):69–83CrossRef
Wong WE, Mathur AP (1995b) Reducing the cost of mutation testing: an empirical study. J Syst Softw 31(3):185–196CrossRef
Wong WE, Qi Y, Zhao L, Cai KY (2007) Effective fault localization using code coverage. In: Proceedings of the 31st Annual International Computer Software and Applications Conference (COMPSAC), pp 449–456, Beijing, China, July, 2007
Xie X, Chen TY, Kuo FC, Xu B (2013) A theoretical analysis of the risk evaluation formulas for spectrum-based fault localization. ACM Trans Softw Eng Method 22(4). doi:10.​1145/​2522920.​2522924
Xie X, Wong WE, Chen TY, Xu B (2013b) Metamorphic slice: an application in spectrum-based fault localization. Informat Softw Technol 55(5):866–879CrossRef
Xu Z, Cohen MB, Motycka W, Rothermel G (2013) Continuous test suite augmentation in software product lines. In: Proceedings of the 17th International Software Product Line Conference, pp 52–61, Tokyo, Japan, August, 2013
Yu Y, Jones JA, Harrold MJ (2008) An empirical study on the effects of test-suite reduction on fault localization. In: Proceedings of the International Conference on Software Engineering (ICSE), pp 201–210, Leipzig, Germany, May, 2008
Metadata
Title
Genetic Algorithm-based Test Generation for Software Product Line with the Integration of Fault Localization Techniques
Authors
Xuelin Li
W. Eric Wong
Ruizhi Gao
Linghuan Hu
Shigeru Hosono
Publication date
05-02-2017
Publisher
Springer US
Published in
Empirical Software Engineering / Issue 1/2018
Print ISSN: 1382-3256
Electronic ISSN: 1573-7616
DOI
https://doi.org/10.1007/s10664-016-9494-9

Other articles of this Issue 1/2018

Empirical Software Engineering 1/2018 Go to the issue

OriginalPaper

Identifying self-admitted technical debt in open source projects using text mining

OriginalPaper

Do developers update their library dependencies?

OriginalPaper

Architecture consistency: State of the practice, challenges and requirements

OriginalPaper

An exploratory qualitative and quantitative analysis of emotions in issue report comments of open source systems

OriginalPaper

Exploring software development at the very large-scale: a revelatory case study and research agenda for agile method adaptation

OriginalPaper

Open innovation using open source tools: a case study at Sony Mobile

Premium Partner

    Image Credits