Research On Automated Software Testing Techniques Based On Hierarchical Reinforcement Learning

Software testing is gaining increasing attention from academia with industry as the primary ways to ensure functional delivery and identify software project problems in advance,and automated software testing is one of the hot areas.Coverage-guided fuzzing and dynamic symbolic execution as two mainstream automated software testing techniques have been widely studied and applied in academia and industry,these two techniques have obvious characteristics: Fuzzy testing generates new test cases by mutating the used test cases,which is efficient but the reliability of the test cases is unsatisfactory.Dynamic symbolic execution generates reliable test cases based on inverse path constraint taking,but it faces the limitations of path explosion and constraint solvers,and the cost of generating test cases is high.The design of search heuristics mitigates path explosion to some extent,but most search policies are designed by hand and are immutable during testing.Some scholars have also combined dynamic symbolic execution with fuzzy testing,called hybrid testing,to break through their inherent limitations.However,the current hybrid tests are mainly executed by both methods in turn,which lacks flexibility.Reinforcement learning scenario in which agent continuously adjusts their policy based on reward from the environment can be used for the design of dynamic symbolic execution search heuristics.The hierarchical reinforcement learning framework is able to solve the control transfer problem excellently and can be used for the design of hybrid testing algorithms.Inspired by the reinforcement learning algorithm,this paper proposes a hybrid testing algorithm LCCT(Learnable Cooperative Concolic Testing)based on hierarchical reinforcement learning.The main work of this paper is as follows.(1)Abstract the dynamic symbolic execution process as a Markov decision process,define a dynamic symbolic execution executor and learn the search heuristics using a reinforcement learning algorithm.For the executor,the state is the program execution tree consisting of all covered branches,and the action space is all conditional branches that can be inverted in the current state.The actuator takes the embedded conditional path as a partial representation of the current state,predicts the value of all desirable inverse actions on the path based on the DDQN algorithm,and finally generates a test case for the current moment based on an improved (?)-greedy strategy for selecting actions.The environment feeds back rewards based on the number of new branches covered and the generation time after executing the test cases,and the executor optimizes the state action value prediction function based on the rewards.(2)In order to break through the inherent limitations of dynamic symbolic execution,a fuzzy test executor is introduced as a supplement to the dynamic symbolic execution actuator,and a coordinator is introduced using a hierarchical reinforcement learning framework to effectively combine the two algorithms,and LCCT is proposed.LCCT consists of a top-level coordinator and a bottom-level executor,with the state of the coordinator being the statistics of the covered branches composing the program execution tree,and the action space being the fuzzy test executor as well as the dynamic symbolic execution executor.The coordinator uses the DQN algorithm for value prediction and selects executors to generate test cases according to the (?)-greedy strategy,and finally optimizes the prediction function based on the performance of the test cases.LCCT avoids dynamic symbolic actuators from falling into local optima and reduces the impact of path explosion by introducing fuzzy test executor.The design of the coordinator allows for more flexible switching between actuators,and the executors improve their respective effectiveness through data transfer.(3)The dynamic symbolic execution actuator and the LCCT algorithm are experimentally tested with the current mainstream dynamic symbolic execution strategy Chameleon and others on a series of open source programs such as expat.The experimental results show that the dynamic symbolic execution executor outperforms most of the current strategies and that LCCT outperforms the dynamic symbolic execution executor and covers the most branches on some programs.