research-article

Test Case Prioritization Using Extended Digraphs

Authors:

Seyedeh Sepideh Emam,

James MillerAuthors Info & Claims

ACM Transactions on Software Engineering and Methodology (TOSEM), Volume 25, Issue 1

Article No.: 6, Pages 1 - 41

https://doi.org/10.1145/2789209

Published: 02 December 2015 Publication History

Abstract

Although many test case prioritization techniques exist, their performance is far from perfect. Hence, we propose a new fault-based test case prioritization technique to promote fault-revealing test cases in model-based testing (MBT) procedures. We seek to improve the fault detection rate—a measure of how fast a test suite is able to detect faults during testing—in scenarios such as regression testing. We propose an extended digraph model as the basis of this new technique. The model is realized using a novel reinforcement-learning (RL)- and hidden-Markov-model (HMM)-based technique which is able to prioritize test cases for regression testing objectives. We present a method to initialize and train an HMM based upon RL concepts applied to an application's digraph model. The model prioritizes test cases based upon forward probabilities, a new test case prioritization approach. In addition, we also propose an alternative approach to prioritizing test cases according to the amount of change they cause in applications. To evaluate the effectiveness of the proposed techniques, we perform experiments on graphical user interface (GUI)-based applications and compare the results with state-of-the-art test case prioritization approaches. The experimental results show that the proposed technique is able to detect faults early within test runs.

References

[1]

K. Aas and L. Eikvil. 1996. Text page recognition using grey-level features and hidden Markov models. Patt. Recogn. 29, 6, 977--985.

[2]

A. Arcuri and L. Briand. 2011. A practical guide for using statistical tests to assess randomized algorithms in software engineering. In Proceedings of the 33^rd International Conference on Software Engineering (ICSE'11). IEEE, 1--10.

Digital Library

[3]

I. Arel, C. Liu, T. Urbanik, and A. G. Kohls. 2010. Reinforcement learning-based multi-agent system for network traffic signal control. IET Intell. Transport Syst. 4, 2, 128--135.

[4]

D. Ariu, R. Tronci, and G. Giacinto. 2011. HMMPayl: An intrusion detection system based on hidden Markov models. Comput. Secur. 30, 4, 221--241.

Digital Library

[5]

S. Arlt, S. Pahl, C. Berolini, and M. Schaf. 2012. Trends in model-based GUI testing. Adv. Comput. 86, 183--222.

[6]

A. Avritzer and E. R. Weyuker. 1995. The automatic generation of load test suites and the assessment of the resulting software. IEEE Trans. Softw. Engin. 21, 9, 705--716.

Digital Library

[7]

C. G. Bai, Q. P. Hu, M. Xie, and S. H. Ng. 2005. Software failure prediction based on a Markov Bayesian network model. J. Syst. Softw. 74, 3, 275--282.

Digital Library

[8]

L. Baum, T. Petrie, G. Soules, and N. Weiss. 1970. A maximization technique occuring in the statistical analysis of probabilistic functions of Markov chains. The Ann. Math. Statist. 41, 1, 164--171.

[9]

G. Becce, L. Mariani, O. Riganelli, and M. Santoro. 2012. Extracting widget descriptions from GUIs. In Proceedings of the 15^th International Conference on Fundamental Approaches to Software Engineering (FASE'12). 347--361.

Digital Library

[10]

P. Blunsom. 2004. Hidden Markov models. http://digital.cs.usu.edu/&sim;cyan/CS7960/hmm-tutorial.pdf.

[11]

K.-Y. Cai, Y.-C. Li, and W.-Y. Ning. 2005. Optimal software testing in the setting of controlled Markov chains. Euro. J. Oper. Res. 162, 2, 552--579.

[12]

H. S. Chang. 2006. Reinforcement learning with supervision by combining multiple learnings and expert advices. In Proceedings of the American Control Conference (ACC'06). 159--161.

[13]

W. Ching. 2006. Markov Chains: Model, Algorithms and Applications. Springer Science.

Digital Library

[14]

J. Cohen. 1988. Statistical Power Analysis for the Behavioral Sciences. Lawrence Erlbaum Associate Publishers.

[15]

H. Cua and N. Dethlefs. 2011. Hierarchical reinforcement learning and hidden Markov models for task-oriented natural language generation. In Proceedings of the 49^th Annual Meeting of the Association for Computational Linguistics: Short Papers (ACL'11). 654--659.

Digital Library

[16]

R. Davoodi and B. J. Andrews. 1998. Computer simulation of FES standing up in paraplegia: A self-adaptive fuzzy controller with reinforcement learning. IEEE Trans. Rehabil. Engin. 6, 2, 151--161.

[17]

P. Dayan and C. J. Watkin. 1992. Technical note Q-learning. Mach. Learn. 8, 279--292.

Digital Library

[18]

R. Dev, A. Jaaskelainen, and M. Katara. 2012. Model-based GUI testing: Case smartphone camera and messaging development. Adv. Comput. 85, 65--122.

[19]

H. Do, S. Mirarab, L. Tahvildari, and G. Rothermel. 2010. The effect of time constraints in test case prioritization: A series of controlled experiments. IEEE Trans. Softw. Engin. 36, 5, 592--617.

Digital Library

[20]

I. K. El-Far and J. A. Whittaker. 2002. Model-based software testing. In Encyclopedia of Software Engineering. Wiley, 1--22.

[21]

S. Elbaum, G. Rothermel, A. G. Malishevsky, and S. Member. 2002. Test case prioritization: A family of empirical studies test case prioritization. IEEE Trans. Softw. Engin. 27, 10, 929--948.

[22]

D. P. Ellis. 2010. The Essential Guide to Effect Sizes; Statistical Power, Meta-Analysis and the Interpretation of Research Results. Cambridge University Press.

[23]

A. T. Endo and A. Simao. 2011. Model-based testing of service-oriented applications via state models. In Proceedings of the IEEE International Conference on Services Computing (SCC'11). 432--439.

Digital Library

[24]

U. Farooq. 2011. Model based test suite minimization using metaheuristics. http://ro.ecu.edu.au/cgi/viewcontent.cgi?articlen=1409&context==theses.

[25]

A. Feliachi and H. L. Guen. 2010. Generating transition probabilities for automatic model-based test generation. In Proceedings of the 3^rd International Conference on Software Testing, Verification, and Validation (ICST'10). 99--102.

Digital Library

[26]

P. G. Frankl, G. Rothermel, K. Sayre, and F. I. Vokolos. 2003. An empirical comparison of two safe regression test selection techniques. In Proceedings of the International Symposium on Empirical Software Engineering (ISESE'03). IEEE Computer Society, 195--204.

Digital Library

[27]

F. Galon. 1889. Natural Inheritance. MacMillan.

[28]

K. Hamamoto, K. Morooka, and H. Nagahashi. 2004. Motion recognition by combining HMM and reinforcement learning. In Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics (ICSMC'04). 259--264.

[29]

J. Hao and E. Mendes. 2006. Usage-based statistical testing of Web applications. In Proceedings of the 6^th International Conference on Web Engineering (ICWE'06). ACM Press, New York, 17--24.

Digital Library

[30]

H. Hemmati. 2011. Similarity-based test case selection: Toward scalable and practical model-based testing. https://www.simula.no/publications/similarity-based-test-case-selection-toward-scalable-and-practical-model-based-testing.

[31]

H. Hemmati, A. Arcuri, and L. Briand. 2013. Achieving scalable model-based testing through test case diversity. ACM Trans. Softw. Engin. Methodol. 22, 1, 1--42.

Digital Library

[32]

M. A. T. Ho, Y. Yamada, and Y. Umetani. 2002. An HMM-based temporal difference learning with model-updating capability for visual tracking of human communicational behaviors. In Proceedings of the 5^th IEEE International Conference on Automatic Face Gesture Recognition (FGR'02). 170--175.

Digital Library

[33]

H. Hsu and P. A. Lachenbruch. 2008. Paired t-test. In Encyclopedia of Clinical Trials. Wiley, 1--3.

[34]

C.-Y. Huang, J.-R. Chang, and Y.-H. Chang. 2010. Design and analysis of GUI test-case prioritization using weight-based methods. J. Syst. Softw. 83, 4, 646--659.

Digital Library

[35]

R. Ihaka and R. Gentleman. 1996. R: A language for data analysis and graphics. J. Comput. Graph. Statist. 5, 3, 299--314.

[36]

T. P. Jaakkola, S. P. Singh, and M. I. Jordan. 1995. Reinforcement learning algorithm for partially observable Markov decision problems. http://papers.nips.cc/paper/951-reinforcement-learning-algorithm-for-partially-observable-markov-decision-problems.pdf.

[37]

D. Jeffrey and N. Gupta. 2007. Improving fault detection capability by selectively retaining test cases during test suite reduction. IEEE Trans. Softw. Engin. 33, 2, 108-123.

Digital Library

[38]

J. Kabudian, M. R. Meybodi, and M. M. Homayounpour. 2004. Applying continuous action reinforcement learning automata (CARLA) to global training of hidden Markov models. In Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC'04). 638-642.

Digital Library

[39]

K. Lee, H. Hon, M. Hwang, and X. Huang. 1990. Speech recognition using hidden Markov model: A CMU perspective. Speech Comm. 9, 5--6, 497--508.

Digital Library

[40]

B. Legeard and M. Utting. 2006. Practical Model-Based Testing: A Tools Approach. Morgan Kaufmann, San Fransisco.

Digital Library

[41]

L. J. Lin. 1992. Self-improving reactive agents based on reinforcement learning, planning and teaching. Mach. Learn. 8, 3--4, 293--321.

Digital Library

[42]

F. Lindlar, A. Windisch, and J. Wegener. 2010. Integrating model-based testing with evolutionary functional testing. In Proceedings of the 3^rd International Conference on Software Testing, Verification, and Validation Workshops (ICSTW'10). 163--172.

Digital Library

[43]

L. Mariani, M. Pezz, O. Riganelli, and M. Santoro. 2011. AutoBlackTest: A tool for automatic black-box testing. In Proceedings of the 33^rd International Conference on Software Engineering (ICSE'11). 1013--1015.

Digital Library

[44]

L. Mariani, M. Pezz, O. Riganelli, and M. Santoro. 2012. AutoBlackTest: Automatic black-box testing of interactive applications. In Proceedings of the IEEE International Conference on Software Testing, Verification and Validation (ICST'12). 81--90.

Digital Library

[45]

A. K. McCallum. 1995. Reinforcement learning with selective percemption and hidden state. Doctoral dissertation, University of Rochester, NY. http://web.media.mit.edu/&sim;tristan/Classes/MAS.945/Papers/Contextual/McCallum_Thesis.pdf.

Digital Library

[46]

M. McPartland and M. Gallagher. 2011. Reinforcement learning in first person shooter games. IEEE Trans. Comput. Intell. AI Games 3, 1, 43--56.

[47]

H. Mei, D. Hao, L. Zhang, J. Zhou, and G. Rothermel. 2012. A static approach to prioritizing J-unit test cases. IEEE Trans. Softw. Engin. 38, 6, 1258--1275.

Digital Library

[48]

A. M. Memon. 2007. An event-flow model of GUI-based applications for testing. Softw. Test. Verif. Reliab. 17, 3, 137--157.

Digital Library

[49]

A. M. Memon and D. R. Hackner. 2008. Test case generator for GUITAR. In Proceedings of the Companion to the International Conference of Software Engineering (ICSE'08). 959--960.

Digital Library

[50]

S. Mirarab and L. Tahvildari. 2007. A prioritization approach for software. In Proceedings of the 10^th International Conference on Fundamental Approaches to Software Engineering (FASE'07). 276--290.

Digital Library

[51]

S. Mirarab and L. Tahvildari. 2008. An empirical study on Bayesian network-based approach for test case prioritization. In Proceedings of the 1^st International Conference on Software Testing, Verification, and Validation (ICST'08). 278--287.

Digital Library

[52]

D. Nardo, N. Alshahwan, and L. Briand. 2013. Coverage-based test case prioritisation: An industrial case study. In Proceeding of the 6^th International Conference on Software Testing, Verification, and Validation (ICST'13). 302--311.

Digital Library

[53]

S. Parsa and A. Khalilian. 2010. On the optimization approach towards test suite minimization approach. Int. J. Softw. Engin. Appl. 4, 1, 15--28.

[54]

L. R. Rabiner and B. H. Juang. 1986. An introduction to hidden Markov models. IEEE ASSP Mag. 3, 1, 4--16.

[55]

H. Reza, S. Endapally, and E. Grant. 2007. A model-based approach for testing GUI using hierarchical predicate transition nets. In Proceedings of the 4^th International Conference on Information Technology (ITNG'07). 366--370.

Digital Library

[56]

J. A. Rice. 1994. Mathematical Statistics and Data Analysis. Duxbury Press.

[57]

M. Robinson and P. A. Vorobiev. 1999. Swing: A Fast-Paced Guide with Production-Quality Code Examples. Manning.

Digital Library

[58]

G. Rothermel and D. Hall. 1997. A safe, efficient regression test selection technique. ACM Trans. Softw. Engin. Methodol. 6, 2, 173--210.

Digital Library

[59]

G. Rothermel and M. J. Harrold. 1998. Empirical studies of a safe regression test selection technique. IEEE Trans. Softw. Engin. 24, 6, 108--123.

Digital Library

[60]

G. Rothermel, M. J. Harrold, J. Ostrin, and C. Hong. 1998. An empirical study of the effects of minimization on the fault detection capabilities of test suites. In Proceedings of the International Conference on Software Maintenance (ICSM'98). 34--43.

Digital Library

[61]

G. Rothermel, R. Untch, and M. J. Harrold. 2001. Prioritizing test cases for regression testing. IEEE Trans. Softw. Engin. 27, 10, 929--948.

Digital Library

[62]

G. S. Semmel and D. G. Linton. 1998. Determining optimal testing times for Markov chain usage models. In Proceedings of the IEEE SECON Conference (Southeastcon'98). 1--4.

[63]

R. S. Sutton and A. G. Barto. 1998. Reinforcement Learning: An Introduction. The MIT Press, Cambridge, Massachusetts.

Digital Library

[64]

C. Szepesvári. 2010. Algorithms for Reinforcement Learning. Morgan and Claypool.

Digital Library

[65]

S. W. Thomas, H. Hemmati, A. E. Hassan, and D. Blostein. 2012. Static test case prioritization using topic models. Empir. Softw. Engin. 19, 1, 182--212.

Digital Library

[66]

O. Tramasco and S. Bauer. 2013. Package ‘RHmm’. http://www2.uaem.mx/r-mirror/web/packages/RHmm/RHmm.pdf.

[67]

M. A. Walker. 2000. An application of reinforcement learning to dialogue strategy selection in a spoken dialogue system for email. J. Artif. Intell. Res. 12, 387--416.

[68]

C. J. Watkin. 1989. Learning from delayed rewards. 1--14. https://www.cs.rhul.ac.uk/home/chrisw/new_thesis.pdf.

[69]

A. L. White and J. A. Sjorgen. 1988. Markov chains for testing redundant software. In Proceedings of the Reliability and Maintainability Symposium (RAMS'88). 426--433.

[70]

J. A. Whittaker and M. G. Thomason. 1994. A Markov chain model for statistical software testing. IEEE Trans. Softw. Engin. 20, 10, 812--824.

Digital Library

[71]

M. Wiering and M. Van Otterlo. 2012. Reinforcement Learning (State of the Art). Springer.

Digital Library

[72]

J. D. Williams and S. Young. 2007. Partially observable Markov decision processes for spoken dialog systems. Comput. Speech Lang. 21, 2, 393--422.

Digital Library

[73]

W. E. Wong, J. R. Horgan, S. London, and H. Agrawal. 1997. A study of effective regression testing in practice. In Proceedings of the 8^th IEEE International Symposium on Software Reliability Engineering (ISSRE'97). 264--274.

Digital Library

[74]

M. M. Yin and J. T. L. Wang. 2001. Effective hidden Markov models for detecting splicing junction sites in DNA sequences. Inf. Sci. 139, 1--2, 139--163.

Digital Library

[75]

S. Yoo and M. Harman. 2007. Regression testing minimisation, selection and prioritisation: A survey. Softw. Test. Verif. Reliab. 7, 1--60.

Digital Library

[76]

Y. T. Yu and M. F. Lau. 2012. Fault-based test suite prioritization for specification-based testing. Inf. Softw. Technol. 54, 2, 179--202.

Digital Library

[77]

L. Zhang, S.-S. Hou, C. Guo, T. Xie, and H. Mei. 2009a. Time-aware test-case prioritization using integer linear programming. In Proceedings of the 18^th International Symposium on Software Testing and Analysis (ISSTA'09). ACM Press, New York, 401--419.

Digital Library

[78]

Z. Zhang, W. K. Chan, and T. H. Tse. 2009b. Adaptive random test case prioritization. In Proceedings of the 24^th IEEE/ACM International Conference on Automated Software Engineering (ASE'09).

Digital Library

[79]

F. Zhen And P. Chenglian. 2004. A system test methodology based on the Markov chain usage model. In Proceedings of the 8^th International Conference on Computer Supported Cooperative Work in Design (CACWD'04). 160--165.

Cited By

Wang SHuang LGao AGe JZhang TFeng HSatyarth ILi MZhang HNg V(2023)Machine/Deep Learning for Software Engineering: A Systematic Literature ReviewIEEE Transactions on Software Engineering10.1109/TSE.2022.317334649:3(1188-1231)Online publication date: 1-Mar-2023
https://doi.org/10.1109/TSE.2022.3173346
Ufuktepe ETuglular T(2023)Application of the Law of Minimum and Dissimilarity Analysis to Regression Test Case PrioritizationIEEE Access10.1109/ACCESS.2023.328321211(57137-57157)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3283212
Singh ASinghrova ABhatia RRattan D(2023)A Systematic Literature Review on Test Case Prioritization TechniquesAgile Software Development10.1002/9781119896838.ch7(101-159)Online publication date: 8-Feb-2023
https://doi.org/10.1002/9781119896838.ch7
Show More Cited By

Index Terms

Test Case Prioritization Using Extended Digraphs
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Formal software verification
      2. Software defect analysis
        Software testing and debugging

Recommendations

Adaptive random prioritization for interaction test suites
SAC '14: Proceedings of the 29th Annual ACM Symposium on Applied Computing

Combinatorial interaction testing (CIT), a black-box testing method, has been well studied in recent years. It aims at constructing an effective interaction test suites, so as to identify the faults that are caused by interactions among parameters. ...
Multi-objective test case prioritization for GUI applications
SAC '13: Proceedings of the 28th Annual ACM Symposium on Applied Computing

Test case prioritization techniques are proposed to schedule execution of test cases in order to improve testing effectiveness. Various coverage criteria are used as surrogates for test case prioritization. They are expected to improve testing ...
Static test case prioritization using topic models

Software development teams use test suites to test changes to their source code. In many situations, the test suites are so large that executing every test for every source code change is infeasible, due to time and resource constraints. Development ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Software Engineering and Methodology

ACM Transactions on Software Engineering and Methodology Volume 25, Issue 1

December 2015

339 pages

ISSN:1049-331X

EISSN:1557-7392

DOI:10.1145/2852270

Editor:
David S. Rosenblum
National University of Singapore, Singapore

Issue’s Table of Contents

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 December 2015

Accepted: 01 June 2015

Revised: 01 November 2014

Received: 01 May 2014

Published in TOSEM Volume 25, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
702
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)1

Reflects downloads up to 05 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang SHuang LGao AGe JZhang TFeng HSatyarth ILi MZhang HNg V(2023)Machine/Deep Learning for Software Engineering: A Systematic Literature ReviewIEEE Transactions on Software Engineering10.1109/TSE.2022.317334649:3(1188-1231)Online publication date: 1-Mar-2023
https://doi.org/10.1109/TSE.2022.3173346
Ufuktepe ETuglular T(2023)Application of the Law of Minimum and Dissimilarity Analysis to Regression Test Case PrioritizationIEEE Access10.1109/ACCESS.2023.328321211(57137-57157)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3283212
Singh ASinghrova ABhatia RRattan D(2023)A Systematic Literature Review on Test Case Prioritization TechniquesAgile Software Development10.1002/9781119896838.ch7(101-159)Online publication date: 8-Feb-2023
https://doi.org/10.1002/9781119896838.ch7
Ghaemmaghami SEmam SMiller J(2022)Automatically inferring user behavior models in large-scale web applicationsInformation and Software Technology10.1016/j.infsof.2021.106704141:COnline publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1016/j.infsof.2021.106704
Nayak SKumar CTripathi S(2022)Analytic hierarchy process-based regression test case prioritization technique enhancing the fault detection rateSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-022-07174-w26:15(6953-6968)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s00500-022-07174-w
Khatibsyarbini MIsa MJawawi DShafie MWan-Kadir WHamed HSuffian M(2021)Trend Application of Machine Learning in Test Case Prioritization: A Review on TechniquesIEEE Access10.1109/ACCESS.2021.31355089(166262-166282)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3135508
Khalilian ABaraani-Dastjerdi AZamani B(2021)CGenProg: Adaptation of cartesian genetic programming with migration and opposite guesses for automatic repair of software regression faultsExpert Systems with Applications10.1016/j.eswa.2020.114503169(114503)Online publication date: May-2021
https://doi.org/10.1016/j.eswa.2020.114503
Mohd-Shafie MKadir WLichter HKhatibsyarbini MIsa M(2021)Model-based test case generation and prioritization: a systematic literature reviewSoftware and Systems Modeling (SoSyM)10.1007/s10270-021-00924-821:2(717-753)Online publication date: 7-Sep-2021
https://dl.acm.org/doi/10.1007/s10270-021-00924-8
Gal GSnoeck MLaurier W(2021)Ontology-Driven Audit Using the REA-OntologyAdvanced Information Systems Engineering Workshops10.1007/978-3-030-79022-6_10(109-120)Online publication date: 9-Jun-2021
https://doi.org/10.1007/978-3-030-79022-6_10
Wei DSun QWang XZhang TChen B(2020)A Model-Based Test Case Prioritization Approach Based on Fault Urgency and SeverityInternational Journal of Software Engineering and Knowledge Engineering10.1142/S021819402050012630:02(263-290)Online publication date: 23-Mar-2020
https://doi.org/10.1142/S0218194020500126
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents