C分析工具中程序切片和变换的设计与实现

发布时间：2018-06-09 02:44

本文选题：缺陷检测 + 程序切片　；参考：《中国科学技术大学》2017年硕士论文

【摘要】：当今计算机技术的发展日新月异,软件在我们的生活中扮演着水和电的重要角色。C语言作为一门广泛应用的语言,已有40多年的历史,它在系统软件如操作系统、编译器、数据库等领域中仍然具着强劲的优势,在保持底层运行效率的同时,它也给程序员带来一些负担,程序员需要关注内存泄露、空指针和悬空指针解引用、缓冲区溢出等问题。目前提高软件可靠性和安全性的方法主要有程序验证、动态测试和静态分析。程序验证目前还未实现完全的自动化证明,动态测试的精确性和覆盖率受到测试集的很大影响,且运行时的检查成本和风险相对较高,静态分析则是比较精确和经济的手段。在静态分析领域中,符号执行被广泛用于测试例的自动生成,它的主要思想是对代码中变量的取值进行符号化,模拟执行程序中所有可能的路径,因此随着程序中的控制结构变得越来越复杂,所需执行的状态数目将急剧增加,严重影响分析工具的伸缩性。针对状态爆炸问题,本文提出了两种在符号执行的不同阶段的优化方法来缓解。第一,使用针对缺陷的程序切片技术对被测程序的中间表示做预处理。首先根据用户关心的缺陷生成源程序的切片准则,然后分析源代码生成数据依赖图和控制依赖图,由两者共同构成程序依赖图,再根据切片准则做程序切片,将源程序规模缩小,最后将切片后的程序交给程序分析工具分析。第二,在符号执行引擎执行过程中对无副作用的控制结构做程序变换。在静态分析工具执行到某个函数时,先分析该函数的所有控制结构,如果某控制结构对程序的后续执行没有影响,则将该控制结构简化,为了不影响分析精度,将工具要检测的缺陷语句提出,这样减少了路径数目,提高了工具的分析性能。笔者所在的课题组目前已实现了一个基于符号执行的C程序静态分析工具,应用本文提出的优化方法,该静态分析工具的分析性能获得了较为明显的改善。
[Abstract]:Nowadays, with the rapid development of computer technology, software plays an important role in water and electricity in our life. As a widely used language, it has been used for more than 40 years. It has been used in system software such as operating system, compiler, etc. Database and other fields still have strong advantages, while maintaining the underlying efficiency, it also brings some burden to programmers, programmers need to pay attention to memory leaks, null pointer and suspended pointer dereference, buffer overflow and so on. At present, the main methods to improve software reliability and security are program verification, dynamic testing and static analysis. At present, program verification has not been fully automated. The accuracy and coverage of dynamic testing are greatly affected by the test set, and the cost and risk of running inspection are relatively high. Static analysis is a more accurate and economical method. In the field of static analysis, symbolic execution is widely used in automatic generation of test cases. Its main idea is to symbolize the values of variables in the code and simulate all possible paths in the execution program. Therefore, as the control structure in the program becomes more and more complex, the number of states that need to be executed will increase dramatically, which will seriously affect the scalability of the analysis tools. For the problem of state explosion, this paper proposes two optimization methods in different stages of symbolic execution to alleviate the problem. First, the defect-specific program slicing technique is used to preprocess the intermediate representation of the program under test. Firstly, according to the defects concerned by the user, the slicing criteria of the source program are generated, then the source code generation data dependency graph and the control dependency graph are analyzed. The program dependency graph is composed of both of them, and then the program slice is made according to the slicing rule. Reduce the size of the source program, and finally the program after slicing to the program analysis tool analysis. Secondly, the program transformation of the control structure without side effect is made during the execution of the symbol execution engine. When a static analysis tool is executed to a function, all control structures of the function are analyzed first. If a control structure has no effect on the subsequent execution of the program, the control structure is simplified so as not to affect the analysis accuracy. The defect statement to be detected by the tool is proposed, which reduces the number of paths and improves the analysis performance of the tool. The author's research group has implemented a static analysis tool of C program based on symbolic execution. By using the optimization method proposed in this paper, the analysis performance of the static analysis tool has been improved obviously.
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.1

【参考文献】