NİDA GÖKÇE, FEVZİ BELLİ, MÜBARİZ EMİNLİ, BEKİR TANER DİNÇER

Model-based test case prioritization using cluster analysis: a soft-computing approach

Model-based testing is related to the particular relevant features of the software under test (SUT) and its environment. Real-life systems often require a large number of tests, which cannot exhaustively be run due to time and cost constraints. Thus, it is necessary to prioritize the test cases in accordance with their importance as the tester perceives it, usually given by several attributes of relevant events entailed. Based on event-oriented graph models, this paper proposes an approach to ranking test cases in accordance with their preference degrees. For forming preference groups, events are clustered using an unsupervised neural network and fuzzy c-means clustering algorithm. The suggested approach is model-based, so it does not necessitate the availability of the source code of the SUT. It differs from existing approaches also in that it needs no prior information about the tests carried out before. Thus, it can be used to reflect the tester's preferences not only for regression testing as is common in the literature but also for ranking test cases in any stage of software development. For the purpose of experimental evaluation, we compare the suggested prioritization approach with six well-known prioritization methods.

Anahtar Kelimeler:

Test prioritization, model-based testing, event-oriented graphs, event sequence graphs, clustering algorithms, fuzzy c-means, neural networks

Model-based test case prioritization using cluster analysis: a soft-computing approach

Keywords:

Test prioritization, model-based testing, event-oriented graphs, event sequence graphs, clustering algorithms, fuzzy c-means, neural networks,

PDF

___

At present, the proposed 13 attributes have equal weights. One of the future works is to use multivariate
data analysis techniques in order to get better weighting schemes, such as principal component analysis and
factor analysis. Another study planned includes application of the proposed approaches to a broader class of
testing problems, e.g., to multiple-metrics-based testing where a family of software measures is used to generate
tests. As mentioned in Section 2, some recent work applied event-oriented prioritization criteria indirectly to
the model, e.g., parameter-value interaction or measuring the coverage of windows/actions/call frequency [9].
As our approach is also event-oriented [8], we see some chances that in our future work we can attempt to
extend, and maybe uniformly structure, our attributes’ catalogue, taking this aspect into account.
B. Beizer, Software Testing Techniques, 2nd ed., New York, Van Nostrand Reinhold, 1990.
R.V. Binder, Testing Object-Oriented Systems: Models, Patterns and Tools, Boston, Addison-Wesley, 2000.
A.P. Mathur, Foundations of Software Testing, New Delhi, Addison-Wesley Professional, 2008.
J.B. Goodenough, S.L. Gerhart, “Toward a theory of test data selection”, IEEE Transactions on Software Engi
neering, Vol. 1, pp. 156–173, 1975.
M.P.E. Heimdahl, D. George, R. Weber, “Specification test coverage adequacy criteria = specification test generation
inadequacy criteria”, in: Proceedings of HASE’04, Tampa, FL, USA, pp. 178–186, 2004.
F. Belli, “Finite-state testing and analysis of graphical user interfaces”, in: Proceedings of ISSRE’01, Hong Kong, pp. 34–43, 2001.
F. Belli, C.J. Budnik, L. White, “Event-based modeling, analysis and testing of user interactions – approach and
case study”, Software Testing, Verification & Reliability, Vol. 16, pp. 3–32, 2006.
F. Belli, M. Beyazit, A. Memon, “Testing is an event-centric activity”, Proceedings of the 6th IEEE International
Conference on Software Security and Reliability, SERE-C, pp. 198–206, 2012.
C. Bryce, S. Sampath, A.M. Memon, “Developing a single model and test prioritization strategies for event-driven
software”, IEEE Transactions on Software Engineering, Vol. 37, pp. 48–64, 2011.
A.M. Memon, M.E. Pollack, M.L. Soffa, “Hierarchical GUI test case generation using automated planning”, IEEE
Transactions on Software Engineering, Vol. 27, pp. 144–155, 2001.
J. Edmonds, E.L. Johnson, “Matching, Euler tours and the Chinese Postman”, Mathematical Programming, Vol.
5, pp. 88–124, 1973.
S.A. Cook, “The complexity of theorem-proving procedures”, in: Proceedings of STOC’71, New York, pp. 151–158, 1971.
F. Belli, N. G¨ok¸ce, “Test prioritization at different modeling levels”, Communications in Computer and Information
Science, Vol. 117, pp. 130–140, 2010. [14] J.M. Kim, A. Porter, “A history-based test prioritization technique for regression testing in resource constrained
environments”, in: Proceedings of ICSE 2002, Orlando, FL, USA, pp. 119–129, 2002. [15] S. Elbaum, A. Malishevsky, G. Rothermel, “Test case prioritization: a family of empirical studies”, IEEE Transac
tions on Software Engineering, Vol. 28, pp. 182–191, 2002. [16] Y.F. Chen, D.S. Rosenblum, K.P. Vo, “Test Tube: a system for selective regression testing”, in: Proceedings of
ICSE’94, Sorrento, Italy, pp. 211–222, 1994. [17] G. Rothermel, M.J. Harrold, “A safe, efficient algorithm for regression test selection”, in: Proceedings of ICSM’93,
Montreal, pp. 358–367, 1993. [18]N. G¨ok¸ce, M. Eminov, F. Belli, “Coverage-based, prioritized testing using neural network clustering”, Lecture Notes
in Computer Science, Vol. 4263, pp. 1060–1071, 2006. [19] F. Belli, M. Eminov, N. G¨ok¸ce, “Prioritizing coverage-oriented testing process-an adaptive-learning-based approach and case study”, 31st Annual International Computer Software and Applications Conference, COMPSAC 2007,
Vol. pp. 197–203, 2007. [20]F. Belli, M. Eminov, N. G¨ok¸ce, “Coverage-oriented, prioritized testing – a fuzzy clustering approach and case
study”, Lecture Notes in Computer Science, Vol. 4746, pp. 95–110, 2007. [21] F. Belli, M. Eminov, N. G¨okce, “Model-based test prioritizing - a comparative soft computing approach and case
studies”, Lecture Notes in Artificial Intelligence, Vol. 5803, pp. 427–434, 2009. [22] F. Belli, M. Eminov, N. G¨ok¸ce, W.E. Wong, “Prioritizing coverage-oriented testing process - an adaptive-learning
based approach and case study”, Series on Software Engineering and Knowledge Engineering, Vol. 20, pp. 1–22, 2011. [23] N. G¨ok¸ce, Determination of Model Based Test Priorities By Clustering Approach”, PhD, Mu˘gla Sıtkı Ko¸cman
University, Mu˘gla, Turkey, 2012 (in Turkish). [24]A. Jain, M. Murty, P. Flynn, “Data clustering: a review”, ACM Computing Surveys, Vol. 31, pp. 264–323, 1999. [25] Angewandte Datentechnik, Test Suite Designer Tool, Paderborn, Germany, University of Paderborn. [26] W.E. Wong, J.R. Horgan, S. London, A.P. Mathur, “Effect of test set minimization on fault detection effectiveness”,
in: Proceedings of ICSE’95, Seattle, pp. 41–50, 1995. [27] G. Rothermel, M.J. Harrold, J.V. Ronne, C. Hong, “Empirical studies of test-suite reduction”, Software Testing,
Verification & Reliability, Vol. 12, pp. 219–249, 2002. [28]G. Rothermel, R.H. Untch, C. Chu, M.J. Harrold, “Prioritizing test cases for regression testing”, IEEE Transactions on Software Engineering, Vol. 27, pp. 929–948, 2001. [29] P.R. Srivastava, “Test case prioritization”, Journal of Theoretical and Applied Information Technology, Vol. 2005,
pp. 178–181, 2005. [30] J.M. Kim, A. Porter, “A history-based test prioritization technique for regression testing in resource constrained
environments”, in: Proceedings of ICSE’02, Orlando, FL, USA, pp. 119–129, 2002. [31] H. Srikanth, L. Williams, J. Osborne, “System test case prioritization of new and regression tests”, in: Proceedings
of ISESE 2005, Noosa Heads, Australia, pp. 1–10, 2005.
R. Krishnamoorthi, S.A. Sahaaya Arul Mary, “Requirement based system test case prioritization of new and
regression test cases”, International Journal of Software Engineering and Knowledge Engineering, Vol. 19, pp. 453–475, 2009. [33] A. Srivastava, J. Thiagrajan, “Effectively prioritizing test in development environment”, in: Proceedings of IS
STA2002, Rome, pp. 97–106, 2002. [34] D. Jeffrey, N. Gupta, “Test case prioritization using relevant slices”, in: Proceedings of COMPSAC’06, Chicago,
Vol. 1, pp. 411–420, 2006. [35] C. Bryce, A.M. Memon, “Test suite prioritization by interacting coverage”, in: Proceedings of DoSTA2007,
Dubrovnik, Croatia, pp. 1–7, 2007. [36] A. Ensan, E. Bagheri, M. Asadi, D. Gasevic, Y. Biletskiy, “Goal-oriented test case selection and prioritization for
product line feature models”, in: Proceedings of INTG’11, Las Vegas, pp. 291–298, 2011. [37] S. Elbaum, A. Malishevsky, G. Rothermel, “Incorporating varying test costs and fault severities into test case
prioritization”, in: Proceedings of ICSE-01, Toronto, pp. 329–338, 2001. [38] W. Wong, J. Horgan, S. London, H. Agrawal, “A study of effective regression testing in practice”, in: Proceedings
of ISSRE 1997, Albuquerque, NM, USA, pp. 230–238, 1997. [39] D. Leon, A. Podgurski, “A comparison of coverage-based and distribution-based techniques for filtering and
Proceedings of ICSTW’09, Denver, CO, USA, pp. 77–84, 2009. [46] K. Cheng, A. Krishnakumar, “Automatic functional test generation using the extended finite state machine model”,
in: Proceedings of DAC’93, Dallas, TX, USA, pp. 86–91, 1993. [47]R. Dssouli, K. Saleh, E. Aboulhamid, A. En-Nouaary, C. Bourhfir, “Test development for communication protocols: towards automation”, Computer Networks, Vol. 31, pp. 1835–1872, 1999. [48] A.M. Memon, “An event-flow model of GUI-based applications for testing”, Software Testing, Verification &
D.E. Rummelhart, D. Zipser, “Feature discovery by competitive learning”, Journal of Cognitive Science, Vol. 9, pp. 75–112, 1985. [56] F. Hoppner, F. Klawonn, R. Kruse, T. Runkler, Fuzzy Cluster Analysis, New York, John Wiley, 1999. [57] D.J. Kim, Y.W. Park, D.J. Park, “A novel validity index for determination of the optimal number of clusters”,
IEICE Transactions on Information and Systems, Vol. D-E84, pp. 281–285, 2001.
R.A. DeMillo, R. J. Lipton, F.G. Sayward, “Hints on test data selection: help for the practicing programmer”,
Computer, Vol. 11, pp. 34–41, 1978. [59]M. Friedman, “The use of ranks to avoid the assumption of normality implicit in the analysis of variance”, Journal of the American Statistical Association, Vol. 32, pp. 675–701, 1939. [60] H. Scheff´e, The Analysis of Variance, New York, Wiley, 1959. [61] Y. Hochberg, A.C. Tamhane, Multiple Comparison Procedures, Hoboken, NJ, USA, John Wiley & Sons, 1987.