Abstract
Reachability testing is an important approach to testing concurrent programs. It generates and executes all the possible sequences of a concurrent program automatically with a given input while not saving any sequences that have already been executed. However, for a large and complex concurrent program, the number of synchronization sequences that are exercised is too large. It will take too long time to perform reachability testing, which limits its application. In this paper, we propose a parallel reachability testing approach based on Hadoop MapReduce called PRT, aiming to improve its performance. PRT adopts the framework of Hadoop MapReduce with a heuristic strategy to realize dynamic loading balance. We present the algorithms used in PRT, and reports the results of five concurrent Java programs that were conducted to evaluate the speed-up with respect to the sequential execution of reachability testing. Experimental results demonstrate that our PRT is an effective approach to parallelizing reachability testing.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Burns, A., Wellings, A.: Real-Time Systems and Programming Languages, 3rd edn. Addison Wesley Longman, Boston (2001)
Edelstein, O., Farchi, E., et al.: Multithread Java program test generation. J. IBM Syst. 41(1), 111–125 (2002)
Taylor, R.N., Levine, D.L., Kelly, C.D.: Structural testing of concurrent programs. IEEE Trans. Softw. Eng. 18(3), 206–214 (1992)
Lei, Y., Carver, R.H.: Reachability testing of concurrent programs. IEEE Trans. Softw. Eng. 32(6), 382–403 (2006)
Carver, R.H., Lei, Y.: Distributed reachability testing of concurrent programs. Concurrency Comput.: Practice Exp. 22(18), 2445–2466 (2010)
Apache Hadoop. http://hadoop.apache.org/. Accessed 28 June 2018
Li, R., Hu, H., et al.: MapReduce parallel programming model: a state-of-the-art survey. Int. J. Parallel Program. 44(4), 832–866 (2016)
Amazon Elastic Compute Cloud. http://aws.amazon.com/ec2/. Accessed 28 June 2018
Carver, R.H., Lei, Y.: A general model for reachability testing of concurrent programs. In: Davies, J., Schulte, W., Barnett, M. (eds.) ICFEM 2004. LNCS, vol. 3308, pp. 76–98. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30482-1_14
White, T.: Hadoop: The Definitive Guide, 3rd edn. O’Reilly Media, Sebastopol (2012)
Carver, R.H., Tai, K.C.: Modern Multithreading. Wiley, New Jersey (2005)
Edelstein, Y., Havelund, K., et al.: Towards a multi-threaded programs. Concurrency Comput.: Practice Exp. 19(3), 267–279 (2007)
Lei, Y., Carver, R.H., Kacker, R., et al.: A combinatorial testing strategy for concurrent programs. Softw. Test. Verif. Reliab. 17(4), 207–225 (2007)
Qi, X., He, J., et al.: Variable strength combinatorial testing of concurrent programs. Front. Comput. Sci. 10(4), 631–643 (2016)
Souza, S.R.S., Souza, P.S.L., et al.: Using coverage and reachability testing to improve concurrent program testing quality. In: 23rd International Conference on Software Engineering and Knowledge Engineering (SEKE), pp. 207–212. Knowledge Systems Institute, Miami, U.S.A. (2011)
Geronimo, D., Ferrucci, F., Murolo, A., et al.: A parallel genetic algorithm based on hadoop mapreduce for the automatic generation of junit test suites. In: 5th IEEE International Conference on Software Testing, Verification and Validation (ICST), pp. 785–793. IEEE Computer Society, Montreal Canada (2012)
Parveen, T., Tilley, S., Daley, N., et al.: Towards a distributed execution framework for JUnit test cases. In: 25th IEEE International Conference on Software Maintenance (ICSM), pp. 425–428. IEEE Computer Society, Alberta (2009)
Acknowledgements
This work is supported by the National Science Foundation of China under Grant No. 61472076 and No. 61472077.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Qi, X., Li, Y. (2018). Parallel Reachability Testing Based on Hadoop MapReduce. In: Bu, L., Xiong, Y. (eds) Software Analysis, Testing, and Evolution. SATE 2018. Lecture Notes in Computer Science(), vol 11293. Springer, Cham. https://doi.org/10.1007/978-3-030-04272-1_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-04272-1_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-04271-4
Online ISBN: 978-3-030-04272-1
eBook Packages: Computer ScienceComputer Science (R0)