Test Input Data Generation for Choiceless Program Nets
Article Sidebar
Main Article Content
Abstract
Software testing is an important problem in designing a large software system and this problem is difficult to be solved due to its computational complexity. We try to use program nets to approach this problem and have proposed algorithms to divide a whole program net into subnets that can structurally cover the original one based on divide-and-conquer method. This paper aims to solve the remaining task of our approach, that is how to find test input data for each subnet to be called choiceless program net. Firstly, definitions of program nets are extended and the properties of choiceless program nets are analysed. Secondly, polynomial algorithms are proposed to get all constraint conditions of any given choiceless program nets. Finally, a method to generate test input data under the obtained constraint conditions is proposed by adopting an SMT (Satisfiability Modulo Theories) solver, $Z3$ prover, and also an example is given to show the usefulness of our method.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
References
B. Hetzel, The Complete Guide to Software Testing, John Wiley & Sons, Inc., 1993.
B.T. Abreu, E. Martins, and F.L. Sousa, "Automatic test data generation for path testing using a new stochastic algorithm", Proc. of the 19th Brazilian Symp. on Software Engineering, vol.19, pp.247-262, 2005.
M. Alzabidi, A. Kumar, and A.D. Shaligram, "Automatic software structural testing by using evolutionary algorithms for test data generations", IJCSNS International Journal of Computer Science and Network Security, vol.9, no.4, 2009.
S. Anand, E.K. Burke, T.Y. Chen, J. Clark, M.B. Cohen, W. Grieskamp, M.Harman, M.J. Harrold, P. McMinn, A. Bertolino, J.J. Li, and H. Zhu, "An orchestrated survey of methodologies for automated software test case generation", Journal of Systems and Software, vol.86, no.8, pp.1978-2001, 2013.
Q.W. Ge, T. Watanabe, and K. Onaga, "Execution termination and computation determinacy of data-flow program nets", J. Franklin Institute, vol.328, no.1, pp.123-141, 1991.
Q.W. Ge, T. Watanabe, and K. Onaga, "Topological analysis of firing activities of data-flow program nets", IEICE Trans. Fundamentals, vol.E73, no.7, pp.1215-1224, 1990.
B. Wu, X. Bao, N. Zhang, H. Morita, M. Nakata, and Q.W. Ge, "Subnets generation of program nets and its application to software testing", IEICE Trans. Fundamentals, vol.E102, no.9, pp.1303-1311, 2019.
J. Mei, S.Y. Wang, "An improved genetic algorithm for test cases generation oriented paths", Chinese journal of electronics, vol.23, no.3, pp.494-498, 2014.
Q.W Ge, T. Watanabe, and K. Onaga, "Computation of minimum firing time for general self-cleaning SWITCH-less program nets", IEICE Trans. Fundamentals, vol.E81, no.6, pp.1072-1078, 1998.
S. Yamaguchi, T. Takai, T. Watanabe, Q.W. Ge, and M. Tanaka, "Complexity and a heuristic algorithm of computing parallel degree for program nets with SWITCH-nodes", IEICE Trans. Fundamentals, vol.E89, no.11, pp.3207-3215, 2006.
Q.W. Ge, and K. Onaga, "On verification of token self-cleanness of data-flow program nets", IEICE Trans. Fundamentals, vol.E79, no.6, pp.812-817, 1996.
Q.W. Ge, C. Li, and M. Nakata, "Performance evaluation of a two-processor scheduling method for acyclic SWITCH-less program nets", IEICE Trans. Fundamentals, vol.E88, no.6, pp.1502-1506, 2005.
H. Wang, J. Xing, Q. Yang, W. Song, and X.W. Zhang, "Generating effective test cases based on satisfiability modulo theory solvers for service-oriented workflow applications", Software Testing, Verification and Reliability, vol.26, no.2, pp.149-169, 2016.
B. Dutertre and L.D. Moura, "A fast linear-arithmetic solver for DPLL(T)", Proc. of the 16th International Conference on Computer Aided Verification, vol. 4144, pp.81-94, 2006.
L.D Moura and N. Bjϕrner, "Z3: An efficient SMT solver", International conference on Tools and Algorithms for the Construction and Analysis of Systems. Springer, Berlin, Heidelberg, pp.337-340, 2008.