Research On Solving Complex Path Constraints By Polynomial Approximation

Software testing is an important way to ensure software quality and reliability.Automatic test case generation can effectively reduce test overhead and improve test efficiency,and thus becomes a hot research topic in the field of software engineering in recent years.Path-oriented coverage is widely used in error detection and defect location.Effectively generating test cases for covering paths corresponds to solving their path constraints.For complex path constraints,the difficulty in solving them arises from non-linear and floating-pointing computation.Heuristic search based and dynamic symbolic ex-ecution based method are both prevailing technologies to solve non-linear constraints at present.However,the solving performance of heuristic search heavily relies on the setting of key parameters,so that inappropriate parameter setting will cause repeated search resulting in too much iteration.Replacing symbol variables with concrete val-ues during symbolic execution makes the constraints easier to treat but at the cost of restricting the search space to some extent,since such a replacement is usually aim-lessness which are prone to losing feasible solutions.A powerful solver should be developed to settle the problem of complex path constraints solving from the root.It is theoretically proved that there is no single al-gorithm that can effectively solve arbitrary constraints.Therefore,it is necessary to design solvers targeting constraints of different types based on their characteristics.The solver VerifyRealRoots is able to find real solutions of polynomial systems by symbolic-numeric computation method aiming at solving higher-degree polynomials,especially for the polynomial system composed of complex equations.In numerical calculation program and control program,there are usually many non-linear path con?straints consisting of several equations which beyond the ability of mainstream con-straints solving technologies.In this paper,we try to solve the non-linear complex constraint system by polynomial approximation.An equivalent representation algo-rithm is proposed to represent complex functions as high degree polynomials.For con-straints which can not be equivalently converted,an iterative framework is designed which first uses polynomials to approximate complex constraints,and then adopts the VerifyRealRoots to find solutions to the derived polynomials,and finally verifies the solutions by putting them back to the original constraints.The main contributions are as follows:1.Propose an equivalent representation method of polynomial constraints.First define many basic mapping rules from elementary functions to variables accord-ing to the functionality of basic elementary functions,which cover most com-mon elementary functions.On the basis of these mapping rules,an equivalent transformation algorithm of transferring the constraints consisting of complex functions to the polynomial constraints is proposed.Based on different function relations and variable relations,different path constraints are treated by respec-tive equivalent rules in the process.For the equivalent representation algorithm,the solution of the transformed polynomial constraint system is the solution of the original constraint system.Using the algorithm proposed,the generality of solvable constraints has been dramatically improved,that is the input type of this system is extended from the purely polynomial system to the system with complex functions.2.Propose an iterative framework,which,for those constraints unable be handled by equivalent transformation,approximates the original constraints by building a set of polynomial constraints through continuously fitting.Based on it,we pro-pose an automatic test data generation method for path-oriented coverage that is based on polynomial approximation,which adopts the equivalent transforma-tion method or the approximate fitting method to build polynomial constraints.The solutions are successively resolved in terms of the mapping between vari-ables and the transformation rules from the solutions returned by the polynomial solver and are verified.If the unsolved solution cannot satisfy the original con-straints,the iteration repeats until the correct solution is found or the threshold is reached.3.Based on the above methods,we design and implement an automated test case generation tool SPF-PLV,a plug-in of the Eclipse tool,which can automatically generate test data for Java program.Using benchmark programs,the effective-ness evaluation and contrast experiments were designed.The effectiveness eval-uation shows that the method can effectively treat complex constraints involving non-linear and floating-point computation.The contrast experiment against the strong solver SPF-CORAL shows that our method is more power when facing with constraint systems including several equality constraints.