Model-Based Test Case Generation from Graph Transformation Specifications using Beam Search Algorithm

Authors

Faculty of Engineering, Arak University, Arak, Iran

Abstract

Software testing is one of the key activities in software development life cycle that plays an important role in software quality. More than half of the software development costs and time are often spent on the test. Obviously, the automation of software testing, especially in generating test cases that is a key activity of this process, will dramatically reduce the costs. Among the prosperous testing techniques is model-based testing that utilizes model checker tools to automatically extract test cases. However, as these tools basically designed for model verification, not for test generation, the researches in the testing context are encountered with some major challenges such as state space explosion problem and duplication of the vast majority of test cases. In this paper, we propose a novel method using Beam-search algorithm for generating tests from systems specified through graph transformation specification. The popopsed approach not only improvs the mentioned challenges, but also generates the test suites with high coverage and low size in a desired time budget. We implemented it in the model checker tool GROOVE. To assess the efficiency of our approach, we compared it with model checker-assisted testing, search-based testing strategies and random testing. The empirical results over some case studies in the domain of service-oriented systems confirm it's superiority in terms of coverage size, test suit size and speed.

Keywords

References

[1] P. Ammann and J. Offutt, Introduction to software testing, 1 ed. United States of America, New York, Cambridge University Press, April 2008.
[2] L. Zhao and W. Luo, "An algorithm for reducing test suite based on interface parameters," International Conference on Computational Intelligence and Software Engineering, pp. 1-4, Wuhan, China, December 2010.
[3] سجاد اسفندیاری و وحید رافع، «راهکاری نوین جهت تولید دنباله آزمون کمینه در فرآیند آزمون نرم‌افزار با ترکیب الگوریتم‌های جستجوی تپه‌نوردی و جستجوی خفاش»، مجله مهندسی برق دانشگاه تبریز، جلد 46، شماره 3 صفحه 25-35، پاییز 1395.
[4] M. Utting, B. Legeard, F. Bouquet, E. Fourneret, F. Peureux, and A. Vernotte, "Recent advances in model-based testing," Advances in Computers. vol. 101, pp. 53-120, Elsevier, January 2016.
[5] C. Baier and J.-P. Katoen, Principles of model checking, Massachusetts,MIT Press, January 2008.
[6] M. P. E. Heimdahl, S. Rayadurgam, W. Visser, G. Devaraj, and J. Gao, "Auto-generating test sequences using model checkers: a case study," Third International Workshop on Formal Approaches to Testing of Software, pp. 42-59 Berlin, Heidelberg: Springer, 2004.
[7] V. Rafe, M. Rahmani, and K. Rashidi, "A Survey on coping with the state space explosion problem in model checking," International Research Journal of Applied and Basic Sciences, vol. 4, no.3, pp. 1379-1384, 2013.
[8] G. Fraser, F. Wotawa, and P. Ammann, "Issues in using model checkers for test case generation," Journal of Systems and Software, vol. 82, no.9, pp. 1403-1418, September 2009.
[9] V. Rafe, M. Moradi, R. Yousefian, and A. Nikanjam, "A Meta-heuristic solution for automated refutation of complex software systems specified through graph transformations," Applied Soft Computing, vol. 33, no. c, pp. 136-149, August 2015.
[10] R. Yousefian, S. Aboutorabi, and V. Rafe, "A Greedy algorithm versus metaheuristic solutions to deadlock detection in graph transformation systems," Journal of Intelligent and Fuzzy Systems, vol. 31, no. 1, pp. 137-149, June 2016.
[11] X.-S. Yang, "Metaheuristic optimization: algorithm analysis and open problems," Proceedings of the 10th International Conference on Experimental Algorithms, vol. 6630 pp. 21-32, Crete, Greece, May 2011.
[12] D. Furcy and S. Koenig, "Limited discrepancy beam search," In Proceedings of the 19th International Joint Conference on Artificial Intelligence, pp. 125-131, Edinburgh, Scotland, August 2005.
[13] A. Rensink, "The GROOVE simulator: a tool for state space generation," Applications of Graph Transformations with Industrial Relevance, vol. 3062 pp. 479-485 Berlin, Heidelberg, Springer, 2004.
[14] M. A. Bokhari, T. Bormer, and M. Wagner, "An Improved beam-search for the test case generation for formal verification systems," Proceedings of the 7th International Symposium on Search Based Software Engineering, vol. 9275 pp. 77-92, Cham, 2015.
[15] B. Jiang and W. K. Chan, "Input-based adaptive randomized test case prioritization: A local beam search approach," Journal of Systems and Software, vol. 105, no. c, pp. 91-106, July 2015.
[16] اکرم کلائی، تولید بهینه مورد آزمون مبتنی بر مدل برای توصیفات تبدیل گراف با استفاده از الگوریتم‌های فرامکاشفه‌ای، درجه عالی، دانشگاه اراک، اراک، صفحه 1-120، زمستان 1394.
[17] R. Heckel, T. Khan, and R. Machado, "Towards test coverage criteria for visual contracts," Proceedings of the Tenth International Workshop on Graph Transformation and Visual Modeling Techniques GTVMT - Electronic Communications of the EASST, vol. 41, pp. 1-15 Berlin, January 2011.
[18] C. Nebut, F. Fleurey, Y. L. Traon, and J.-M. Jezequel, "Automatic test generation: A use case driven approach," IEEE Transactions on Software Engineering, vol. 32, no. 3, pp. 140-155, March 2006.
[19] M. A. Saadtjoo and S. M. Babamir, "Optimizing cost Function in Imperialist competition algorithm for path coverage problem in software testing," Journal of AI and Data Mining, vol. 5, September 2017.
[20] S. Z. Waheed and U. Qamar, "Data flow based test case generation algorithm for object oriented integration testing," 6th IEEE International Conference on Software Engineering and Service Science (ICSESS), pp. 423–427, Beijing, China, September 2015.
[21] N. Nayak and D. P. Mohapatra, "Automatic test data generation for data flow testing using particle swarm optimization," Communications in Computer and Information Science, vol. 95, pp. 1-12, Berlin, Heidelberg, January 2010.
[22] R. Grzegorz, Handbook of graph grammars and computing by graph transformation, vol. 1, World Scientific, 1997.
[23] مریم مردادی، رزا یوسفیان و وحید رافع، « ارائه راهکاری جهت مقابله با مشکل انفجار فضای حالت در سیستم‌های تبدیل گراف با استفاده از الگوریتم‌های پرندگان و جستجوی گرانشی»، مجله مهندسی برق دانشگاه تبریز، جلد 45، شماره 4 صفحه 163-177، زمستان 1394.
[24] R. Heckel, "Graph transformation in a nutshell," Electronic Notes in Theoretical Computer Science, vol. 148, no.1, pp. 187-198, February 2006.
[25] P. M. Herman, "A Data flow analysis approach to program testing," The Australian Computer Journal, vol. 8, no. 3, pp. 92-96, November 1976.
[26] A. Groce and W. Visser, "Heuristics for model checking java programs," International Journal on Software Tools for Technology Transfer (STTT), vol. 6, no. 4, pp. 260-276, August 2004.
[27] T. Su, Z. Fu, G. Pu, J. He, and Z. Su, "Combining symbolic execution and model checking for data flow testing," Proceedings of the 37th International Conference on Software Engineering, vol. 1, pp. 654-665, Florence, Italy, May 2015.
[28] P. McMinn, "Search-based software testing: past, present and future," Proceedings of the 2011 IEEE Fourth International Conference on Software Testing, Verification and Validation Workshops, pp. 153-163, April 2011.
[29] O. Runge, T. A. Khan, and R. Heckel, "Test Case Generation Using Visual Contracts," Proceedings of the 12th International Workshop on Graph Transformation and Visual Modeling Techniques GTVMT- Electronic Communications of the EASST, vol. 58, Italy, 2013.
[30] V. Rafe, "Scenario-driven analysis of systems specified through graph transformations," Journal of Visual Languages & Computing, vol. 24, no. 2, pp. 136-145, April 2013.
[31] G. Engels, B. Güldali , and M. Lohmann, "Towards model-driven unit testing," Proceedings of the 2006 International Conference on Models in Software Engineering, vol. 4364, pp. 182-192, Italy, October 2006.
[32] A. Arcuri and L. Briand, "A practical guide for using statistical tests to assess randomized algorithms in software engineering," Proceedings of the 33rd International Conference on Software Engineering, pp. 1-10, Waikiki, Honolulu, HI, USA, May 2011.

Files

Share

How to cite

Statistics