Design And Implementation Of Symbolic Execution Engine For C Programing Language

With the continuous development in China's aerospace,railway,and chips industry,the number and scale of software systems in the high-security area is increasing.Because of the requirements in strong stability,real-timing and compatibility of software systems in these fields,most systems are written in C.The high security requirements of these systems also makes it necessary for companies that to perform full unit testing on the system and ensure adequate security with high test coverage.To achieve high test coverage,testers need to spend a lot of time writing unit test cases.But there was still inefficiency in test case producing and the quality of these manual test cases varies tremendously.In order to solve the above problems,this paper proposed a method that applies symbolic execution techniques to test cases automatic generation for unit testing of C programs,and implemented a tool which automatically generates unit test cases with high test coverage.The main contributions of this paper are as follows:Symbolic execution engine for C programming language: The symbolic execution engine in this paper uses static code analysis and control flow analysis techniques to analyze and preprocess the C source code,then generated an abstract syntax tree and a control flow graph model based on the processed source code.With the control flow graph,the searcher and executor performed symbolic execution and gathered information of test input for the given program path,which was used to generate test case.The symbolic execution engine implemented the core functionality of the unit test automatic generation tool.Efficient search algorithm that support MC/DC coverage: This paper proposed a method for generating unit test cases that satisfies MC/DC coverage criteria in the symbolic execution engine,which also improved the efficiency in program path searching.In addition,we designed a new search algorithm called flood search algotithm,which makes the symbolic execution engine able to simulates symbolic execution and generates unit test cases based on statement,branch,and MC/DC coverage criteria.Unit test automatic generation tool: This paper implemented a cloud-based,industrial-level unit test automatic generation tool based on the symbolic execution engine,which also provided support for some mainstream third-party unit test platform.Therefore,automatic unit test could be performed bearly without manual work,with high effectiveness and quality.This paper designed and implemented a unit test automatic generation tool for C programming language,whose kernel is a new C symbolic execution engine.The tool has been applied to realworld industrial applications as aerospace and railway signaling.