key: cord-0047459-vvv4xcb5 authors: S, Saju Sankar; S S, Vinod Chandra title: An Ant Colony Optimization Algorithm Based Automated Generation of Software Test Cases date: 2020-06-22 journal: Advances in Swarm Intelligence DOI: 10.1007/978-3-030-53956-6_21 sha: 6ec1588e6cacdefe88abe8ce71418056415c2734 doc_id: 47459 cord_uid: vvv4xcb5 Software testing is an important process of detecting bugs in the software product thereby a quality software product is developed. Verification and Validation (V & V) activities are the effective methods employed to achieve quality. Static and dynamic testing activities are performed during V & V. During static testing, the program code is not executed while in dynamic testing (Black Box and White Box), the execution of the program code is performed. Effective test cases are designed by both these methods. Tables are employed to represent test case documentation. The most beneficial representation - State table based testing, for generating test inputs is explained with the help of state graphs and state tables. This technique is mainly employed in embedded system software testing, real time applications and web application based software product testing where time constraints are a major criteria. Automatic generation of test cases will help to reduce time overhead in testing activities. Our study is to develop optimum test cases by a modified Ant Colony Optimization (ACO) technique in an automated method and it ensures maximum coverage. The prediction model used in this paper ensures better accuracy of the design of test inputs. A comparison of the similar optimization techniques was also discussed that is used in automated test case generation. A case study of the various states during the execution of a task in an operating system has been presented to illustrate our approach. A software product should be reliable and measurable. These qualities are evaluated by way of effective testing activities. Hence testing is an important stage of Software Development Life Cycle (SDLC). Like SDLC, Software Testing Life Cycle (STLC) is also a process which detects bugs or faults so as to rectify them before delivery of the software product to the customer. The testing of the various phases of STLC by way of manual testing is difficult due to the overhead of time, cost and schedule slippage. Hence automated testing is complemented for majority of the testing activities [1] . This automated generation of test cases is necessary when a set of tests are to be done repeatedly, compatibility testing, regression testing etc. For this purpose, artificial intelligence techniques are adopted with a Meta heuristic approach. The problem of generating sets of test cases for functional testing, structural testing etc. are achieved by automated test case generation techniques [2] . In this paper, we propose an optimal algorithm for the automated generation of test cases based on Ant Colony Optimization (ACO). State table based testing -a black box testing technique is employed, which assures a higher level of functional testing of the individual modules. Here the process is categorized as -software environment modeling, test case selection, test case execution, test metrics and automated test suite reduction techniques [3] . A software product can be optimized by various algorithms such as genetic algorithms, ACO, Particle Swarm Optimization (PSO), Artificial Bee Colony (ABC) etc. The ACO algorithm is a metaheuristic intelligent optimization method. The algorithm is used for finding the optimal path in a graph. ACO is also employed for the optimization of test case generation techniques namely functional testing, Structural testing, Regression testing etc. [4] . Praveen et al. proposed an ACO based automated software testing technique which shows the generation of optimal test cases in an automated environment [5] . This paper proposes an automated method of generating test cases in functional testing technique mainly state table based testing, optimized by an ACO algorithm. The results are compared with other optimization models for effectiveness [6] . State table based testing is defined as the black box testing technique in which changes in input conditions cause state changes in the application under test [7] . It is a convenient method for testing software systems where states and transitions are specified. Tables are used for representing information relating to the design of test cases. We have represented them using state transition diagrams and state tables. A state table representation has a) Finite State Machine (FSM), a model whose output is dependent on both previous and present inputs. An FSM model represents the software behavior and serves as a guide to design functional test cases. b) State transition diagram or state graph, is a software system which has different states depending on its input and time. The nodes in a state graph represent states. The nodes are connected by links denoted as transitions. With the help of nodes and transitions, a state graph is prepared. The pictorial representation of an FSM is depicted by a state graph and it represents the states that the system can assume. The state graph is converted to a tabular form known as state tables. They specify states, input events, transitions and outputs. The information contained in the state graph and the state table is converted into test cases. The state table contains cells of valid and invalid inputs. Valid inputs causes a change of state and invalid inputs do not cause any change in transition in the state of a task. Due to the tremendous overhead of time and cost exhaustive testing is not possible. The solution is to formulate a strategy for test case reduction without affecting the functional coverage of the system under test. The genetic algorithms employed currently have to be modified for the above [8] . The method of state table based testing is depicted with a case study, showing the different states of a task in an operating system. A task or job assigned to an operating system has the states -New, Ready, Running, Waiting, Terminated. The state graph is drawn as the first step. The state graph can be represented as a directed graph G = (N, E), where N denotes the states (nodes) of the system under test and E denotes the edges or transition between the states. As shown in Fig. 1 , there are two paths which satisfy rule b. ACO is a probabilistic technique which searches for optimal path in a graph. Ant behavior is looking a shortest path between their colony and location of food source. The path is discovered by pheromone deposits when the ants move at random. More pheromone deposits on a path increases the probability of the path being followed. The path is selected based on the maximum pheromone deposit from start node and the path is analyzed for optimality [9] . The behavior of ants can be used for solving the problem. Selection of paths depends upon the theory of probability. Ants generate pheromone and deposits on the paths for further remembrance and it is a heuristic technique. The path visibility is accomplished by the level of pheromone intensity and heuristic information. The feasible path is selected based on highest pheromone level and heuristic information. The algorithm needs four parameters for selecting the valid transitions of the state graph -Probability, Heuristic information, Pheromone intensity and Visibility of the path [10] . Required (PTR) metric [6] . The metrics was evaluated by the case studies for triangle problem, quadratic equation problem etc. (Table 3) . The comparison shows that m-ACO algorithm shows better coverage than the other optimization algorithms. In order to classify or to select the valid test cases, we used the modified algorithm 'Comprehensive Improved Ant Colony Optimization (ACIACO) for finding the effective optimization path and this path model is used to achieve highest coverage and reduce the number of iterations [11] . The establishment of transformation relationship makes effective use of ant colony algorithm for iterative optimization of test cases. In this paper, generating the test cases from the state table is achieved by the modified ACO algorithm. The algorithm is for the effective traversing through the different states. Also the feasible test cases are generated so as to cover all transitions at least once. The procedure is given, 1. Initialize parameters. Initialize heuristic value of each transition in the state graph Ƞ =2. Initialize pheromone value for each transition in the state graph (Ʈ=1). Initialize V s = 0 (the condition in which ant not visited any state). Initialize P = 0. 1.5 Initialize α =1, β =1, the parameters which controls the desirability and visibility. 1.6 Set count = maximum number of possible transitions. The probability has values between 0 and 1. 3. Move to the next node. 3.1 Select the destination node. Ant will follow the rules. We have discussed how the test cases are minimized while maximizing coverage of testing. If there are 'n' states in a state graph, then there will be a maximum of 'n*n' test cases both feasible and infeasible generated thereby increasing the testing time overhead. For the automated generation of test cases, we used an open source testing tool multidimensional modified condition/decision coverage which supports state graph based testing and generates test cases by traversing through the state transition graph [12] . The test cases given in Table 2 , twenty four test cases both valid and invalid, which cause or do not cause change in transition from one state to another during the execution of a task has to be minimized. Wang's algorithm [13] was used for the effective reduction of test cases. After completely extracting all the transitions, the next step is to generate the test cases from TC1 to TC24. The last step is to reduce the set of generated test cases by calculating the node coverage for each test case and determining which test cases are covered by other test cases. i.e. from NC(TC1) to NC(TC24). The test cases are valid if the node coverage is empty. All other test cases are invalid and can be ignored. Hence the six valid test cases which causes state transitions in the execution of a task in an operating system are Test Suite, TS = {TC1, TC8, TC15, TC16, TC18, TC23} as shown in Table 4 . This reduction in test suite helps saving of time in resource constrained software projects. The ACIACO algorithm effectively covered the criteria such as reduced test suite size, improved fault detection capability, reduced time, cost and highest coverage criteria. A comparison of the three kinds of coverage -statement coverage, branch coverage and modified condition/decision coverage shows that the modified ACIACO algorithm obtained better values as shown in Table 5 . It is evident that the ACO optimization algorithm will effectively improve the quality of the test cases generated. We have proposed a modified ACO based approach for the automated and effective generation of valid test cases for the state transition based software testing. An FSM model is prepared. From the model, a state graph followed a state table and a test case table was generated. Also a test suite reduction algorithm is implemented thereby the optimization is achieved. ACO is a promising methodology for test case generation, selection and prioritization problem. ACO algorithm fully satisfies software coverage without having any redundancy. The power of nature inspired models in software engineering area is emerging because of its optimization outcome. The swarm based optimization is evolving in many of the software optimization fields. It is highly recommended, agent and swarm fused optimization algorithms can be used to generate efficient automated test environments. Literature review on test case generation approach Automated software test data generation: direction of research Generation and optimization of test cases for object oriented software using state chart diagram Evaluation of test cases using ACO with a new heuristic function: a proposed approach Structured testing using ant colony optimization A Comparative evaluation of 'm-ACO' technique for test suite prioritization An ant colony optimization approach to test sequence generation for state based software testing A survey on test case selection using optimization techniques in software testing Smell detection agent based optimization algorithm Baby: automatic test sequence generation for state transition testing via ACO Improved Ant algorithm for software testing cases generation Generation of test case using automation in software systems -a review Generating test cases from UML activity diagram based on graybox method