Evolutionary Generation Approach of Test Data for Multiple Paths Coverage of Message-passing Parallel Programs

TIAN Tian; GONG Dunwei

Article Contents

Article Navigation > Chinese Journal of Electronics > 2014 > 23(2): 291-296

TIAN Tian and GONG Dunwei, “Evolutionary Generation Approach of Test Data for Multiple Paths Coverage of Message-passing Parallel Programs,” Chinese Journal of Electronics, vol. 23, no. 2, pp. 291-296, 2014,

Citation:

TIAN Tian and GONG Dunwei, “Evolutionary Generation Approach of Test Data for Multiple Paths Coverage of Message-passing Parallel Programs,” Chinese Journal of Electronics, vol. 23, no. 2, pp. 291-296, 2014,

Citation:

PDF( 267 KB)

Evolutionary Generation Approach of Test Data for Multiple Paths Coverage of Message-passing Parallel Programs

School of Information and Electrical Engineering, China University of Mining and Technology, Xuzhou, Jiangsu 221116, China

Funds: This work is supported by the National Natural Science Foundation of China (No.61375067, No.61075061, No.61203304), the Natural Science Foundation of Jiangsu Province (No.BK2012566, No.BK2010187), Graduate Student Research Innovation Program of Jiangsu Province College (No.CXZZ11 0292) and the Fundamental Research Funds for the Central Universities(No.2013XK09).

Received Date: 2013-07-01
Rev Recd Date: 2013-11-01
Publish Date: 2014-04-05

Abstract

Abstract

Test data generation, the premise of software testing, has attracted scholars in the software engineering community in recent years. Influenced by task partitioning, process scheduling, and network delays, parallel programs are executed in a non-deterministic way, which makes test data generation of parallel programs different from that of serial programs in essence. This paper investigated the problem of generating test data for multiple paths coverage of message-passing parallel programs. A mathematical model of the above problem was built based on each given path and its equivalent ones. It was solved by using a genetic algorithm to generate all desired data in one run. The proposed method was applied to five benchmark programs, and compared with the existing methods. The experimental results show that the proposed method greatly shortens the number of iterations and time consumption without reducing the coverage rate.
- Software testing,
- Parallel program,
- Multiple paths,
- Test data,
- Genetic algorithm

FullText(HTML)

References(25)

References

M. Snir, S. Otto, H. Steven, D. Walker, J. Dongarra, MPI: The Complete Reference, MIT Press, Cambridge, USA. 1996.

G.L. Chen, H. An, L. Chen, Q.L. Zheng, J.L. Shan, Parallel Algorithms, Higher Education Press, Beijing, China, 2004.

J.H. Shan, Y. Jiang, P. Sun, "Survey on path-wise automatic generation of test data", Acta Electronica Sinica, Vol.32, No.1, pp.134-145, 2004.

B. Krammer, M. Resch, "Correctness checking of MPI onesided communication using Marmot", Proc. of 13th European PVM/MPI Users' Group Meeting on Recent Advances in Parallel Virtual Machine and Message Passing Inte cxrface, Bonn, Germany, Lecture Notes in Computer Science, Vol.4192, pp.105-114, 2006.

J.S. Vetter, B.R. Supinski, "Dynamic software testing of MPI applications with umpire", Proc. of Supercomputing ACM/ IEEE Conference, Dallas, USA, pp.79, 2000.

J. Lei, R. Carver, "Reachability testing of concurrent programs", IEEE Transactions on Software Engineering, Vol.32, No.6, pp.382-403, 2006.

S.R.S. Souza, P.S.L. Souza, M.C.C. Machado, "Using coverage and reachability testing to improve concurrent program testing quality", Proc. of 23rd International Conference on Software Engineering and Knowledge Engineering, Miami Beach, USA, pp.207-212, 2011.

P. Godefroid, "Model checking for programming languages using verisoft", Proc. of 24th Symposium on Principles of Programming Languages, Paris, France, pp.174-186, 1997.

C. Flanagan, P. Godefroid, "Dynamic partial-order reduction for model checking software", Proc. of 32nd Symposium on Principles of Programming Languages, New Orleans, USA, pp.110-121, 2005.

S. Koushik, "Effective random testing of concurrent programs", Proc. of 22nd International Conference on Automated Software Engineering, Atlanta, Georgia, pp.323-333, 2007.

S. Vakkalanka, M. DeLisi, G. Gopalakrishnan, R.M. Kirby, R. Thakur, W. Gropp, "Implementing efficient dynamic formal verification methods for MPI programs", Proc. of 15th European PVM/MPI Users' Group Meeting on Recent Advances in Parallel Virtual Machine and Message Passing Interface, Dublin, Ireland, Lecture Notes in Computer Science, Vol.5205, pp.248-256, 2008.

C.Y. Sun, L.P. Lori, "All-uses testing of shared memory parallel programs", Software Testing, Verification and Reliability, Vol.13, No.1, pp.3-24, 2003.

C.S.D. Yang, A.L. Souter, L.L. Pollock, "All-du-path coverage for parallel programs", Proc. Of ACM International Symposium on Software Testing and Analysis, Clearwater Beach, USA, pp.153-162, 1998.

S.R.S. Souza, S.R. Vergilio, P.S.L. Souza, "Structural testing criteria for message-passing parallel programs", Concurrency and Computation: Practice and Experience, Vol.20, No.16, pp.1893-1916, 2008.

P.S.L. Souza, S.R.S. Souza, E. Zaluska, "Structural testing for message-passing concurrent programs an extended test model", Concurrency and Computation: Practice and Experience, Vol.25, No.18, pp.149-158, 2013.

S. Xanthakis, C. Ellis, C. Skourlas, "Application of genetic algorithms to software testing", Proc. of 5th International Conference on Software Engineering and Applications, Toulouse, France, pp.625-636, 1992.

M.A. Ahmed, I. Hermadi, "GA-based multiple paths test data generator", Computer & Operations Research, Vol.35, No.10, pp.3107-3127, 2008.

P. Bueno, M. Jino, "Automatic test data generation for program path using genetic algorithms", International Journal of Software Engineering and Knowledge Engineering, Vol.12, No.6, pp.691-709, 2002.

A. Watkins, "The automatic generation of test data using genetic algorithms", Proc. of 4th Software Quality Conference, Austin, USA, pp.300-309, 1995.

J.C. Lin, P.L. Yeh, "Using genetic algorithms for test case generation in path testing", Proc. of 9th Asian Test Symposium, Taipei, China, pp.241-246, 2000.

X.Y. Xie, B.W. Xu, Shi L., C.H. Nie, "Genetic test case generation for path-oriented testing", Journal of Software, Vol.20, No.12, pp.3117-3136, 2009.

P. McMinn, M. Harman, D. Binkley, P. Tonella, "The species per path approach to search-based test data generation", Proc. of International Symposium on Software Testing and Analysis, Portland, USA, pp.13-24, 2006.

D.W. Gong, W. Q. Zhang, Y. Zhang, "Evolutionary generation of test data for multiple paths coverage", Chinese Journal of Electronics, Vol.19, No.2, pp.233-237, 2011.

D.W. Gong, T. Tian, X.J. Yao, "Grouping target paths for evolutionary generation of test data in parallel", Journal of Systems and Software, Vol.85, No.13, pp.2531-2540, 2012.

T. Tian, D.W. Gong, "Evolutionary generation of test data for path coverage of message-passing parallel programs", China journal of computers, Vol.36, No.11, pp.2212-2223, 2013.

Relative Articles

Supplements(0)

Cited By

Proportional views