Constraint Search based Test Data Generation to cover Prime Paths in Structural Testing

Subject Areas : Multimedia Processing, Communications Systems, Intelligent Systems

Ebrahim Fazli ¹ , Mojtaba Aajami ²

1 - Assistant professor, Faculty of Electrical and Computer Engineering, Zanjan Branch, Islamic Azad University, Zanjan
2 - Assistant professor, Faculty of Electrical and Computer Engineering, Zanjan Branch, Islamic Azad University, Zanjan

Received: 2022-12-06 Accepted : 2023-06-20 Published : 2023-03-21

Keywords: coverage criterion, test data, prime path, structural testing,

Abstract :

This paper presents a novel scalable Constraint Search Based method forTest Data Generation, called CSBTDG, used in structural testing. CSBTDG outperforms existing methods for test data generation in several orders of magnitude, both in time and constraint efficiency. Search-based software testing is a powerful automated method to generate test inputs for software under test. Its goal is to reach a branch or a statement in a program. One major limitation of this approach is an insufficiently informed fitness function to start and guide search toward a test target within nested predicates (constraints). Another important limitation of this approach about equality constraints. To address these problems we propose a new search method based on integrating constraint programming using choco constraint solver and the Gray Wolf heuristic search algorithm. Preliminary experiments promise efficiency and effectiveness for the new constraint search based test data generation approach using multiple fitness functions.Test data generation is done by solving constraints related to test paths extracted from the program under test [3][2]. In general, the constraint solving problem of the test paths is a sub problem of a wider set of problems called constraint satisfaction problem (CSP) [4]. Formally, a constraint satisfaction problem is defined as a triple (X, D, C). X represents a set of variables, D is a set of range of values for variables and C is a set of constraints. Constraint satisfaction is the process of finding solutions for a set of constraints that satisfy the conditions imposed on the variables. Evaluation of variables is a function of a subset of variables to a specific set of values in the corresponding domains. The proposed solution is called consistent evaluation if none of the constraints are violated. An evaluation is a complete evaluation if it includes all variables. If the assessment is consistent and complete, it is a solution. It is said that such evaluation is a solution to the constraint satisfaction problem. Therefore, a solution is a set of values for the variables that satisfy all the constraints, that is, a point in the feasible region. The main innovation of this article is to present a cooperation model to exchange information between the solver and the searcher. In this model of data generation, the test solver is an initial setup to assign values to some variables to start searching for the meta-heuristic algorithm.

References:

• [1] Fazli and M. Afsharchi, "A Time and Space-Efficient Compositional Method for Prime and Test Paths Generation," in IEEE Access, vol. 7, pp. 134399-134410, 2019, doi: 10.1109/ACCESS.2019.2941429.


• [2] M. S. Bueno and M. Jino. Automatic test data generation for program paths using genetic algorithms. International Journal of Software Engineering and Knowledge Engineering, 12(06):691–

709, 2002.

• [3] Jussien, N., Rochart, G., & Lorca, X. (2008). Choco: an open source java constraint programming library. In CPAIOR'08 Workshop on Open-Source Software for Integer and Contraint Programming (OSSICP'08) (pp. 1-10).


• [4] Dwarakanath and A. Jankiti. Minimum number of test paths forprime path and other structural coverage criteria. In IFIP International Conference on Testing Software and Systems, pages 63–79. Springer, 2014.


• [5] C. Ntafos and S. L. Hakimi. On path cover problems in digraphs
  and applications to program testing. IEEE Transactions on Software
  Engineering, (5):520–529, 1979.


• [6] A. Nejmeh. Npath: a measure of execution path complexity and its applications. Communications of the ACM, 31(2):188–200, 1988.