关键词: 符号执行, 路径调度, 约束求解, 软件测试

Abstract: Symbol execution and constraint solving with path scheduling algorithm based on Depth First Searching（DFS），which is used in common，is prone to path clustering problem.In practice，the problem of path exploding，which makes it impossible to test all the paths，always exits in software.Path clustering，path exploding and finite test time cause a low level of code coverage.A new path scheduling algorithm called PSHC（Path Scheduling Algorithm with High Code Coverage） is introduced.In this algorithm，a path composes of two parts，prefix and postfix.Test is trying to execute on the path that has the shortest prefix，which has the same nodes with the paths that have been executed，and is doing the best to including the nodes not executed ever in the postfix.The experiments with PBFT（Phoenix-oriented Bug Finding Tool） imply that the PSHC algorithm can increase quickly the code coverage rate to 100% and solve the low coverage of code problem caused by path clustering which is the result of using the path scheduling algorithm oriented on DFS.The amount of paths created by PSHC don’t relate to the depth of loops.The larger the software is，the better the PSHC’s outstanding is.

Key words: symbolic execution, path scheduling, constraints solving, software testing