Research On The Algorithm For Automated Test Case Generation Based On Path Coverage

Test case generation is the prerequisite for software testing.Automated test case generation based on path coverage(ATCG-PC),as one kind of intelligent software testing technique,is the key improving the efficiency of testing.Furthermore,ATCG-PC is a large-scale black-box optimization problem.The efficient and effective algorithm for ATCG-PC is important for both software engineering and optimization algorithms.This thesis aims to address the following problems,including test case generation based on simpler branch coverage or other criteria,the inefficiency of the optimization algorithm,the lack of explanation of the algorithm,and demanding for manual assistance.This thesis proposed the optimization models for ATCG-PC,which extend the ATCG from simple branch coverage to more difficult path coverage.Three classical automated test case generation model based on path coverage is proposed based on a variety of software application scenarios.Three effective strategies are proposed for ATCG-PC and detecting the defects based on above three models.In the following research,we proposed a general method for ATCG-PC based on the space-time tradeoff and other algorithm design criteria,which significantly improve the explanation of the algorithm.The framework of the automated tool for ATCG is also the research topic in this thesis.Differing from prior research,this thesis divides the encoding space of the test case into the effective decision space and the other search space.The effective decision space is a much smaller subspace of the whole search space,which contains the test cases of the target paths.The path can be covered by adaptively searching in the found effective decision space and the other search space.The main research includes the following aspects.1)The optimization model of ATCG-PC is one of the most emerging topic.As a result,this thesis will first study how to build the optimization model.In this research,ATCG is extended to more complex path coverage while the heuristic strategy is used to design a self-adaptive fitness function to achieve the automatic generation of path coverage test cases.2)The black-box feature between test case and path is the main difficulty of ATCG-PC.How to mine the relationship between test case and path,and how to avoid the repetition search consumption of algorithms are the key scientific problems of this thesis.Three classical mathematical models are proposed based on the different application scenarios.The testcase-path relationship matrix strategy,scatter search strategy and vulnerability detection method based on ATCG-PC are applied to emerging software applications such as fog computing,natural language processing,and blockchain intelligent contract,respectively.The effectiveness and efficiency of the algorithm are further improved,thereby assist with the detection of the potential program vulnerabilities.3)Based on the above-mentioned work,an general method for large-scale black-box optimization problems such as ATCG-PC is proposed to enhance the effectiveness of the algorithm.Inspired by the law of manifold distribution hypothesis,this thesis defined some related concepts such as effective decision space.A manifold-inspired search-based algorithm is proposed based on the proposed framework.ATCG-PC can be effectively solved by finding the effective decision subspace of the target paths and dynamically allocate the test case consumption.This work can ensure the efficiency and explanation of the algorithm.The corresponding results show that the proposed algorithm based on the framework significantly outperforms the compared state-of-the-art algorithms.4)How to achieve the automatic unit testing framework without manual analysis is an important research topic of this thesis.To relieve the demanding for manual analysis in ATCG-PC,this thesis designs a toolkit to automatically analyze the unit program and generated corresponding path coverage test cases.The flowchart and branch nodes of the unit program under test can be obtained by analyzing the inserted byte-code.The fitness function can also automatically generated.The path coverage test cases can be generated based on the fitness function and our search algorithm.This work greatly improves the automation of solving ATCG-PC.