指针是C语言最重要的特征之一,是C语言的核心和灵魂。指针缺陷是指由于对指针的错误或不规范使用导致的缺陷。C程序要求开发人员自行维护指针,进行动态的内存管理。这种机制保证了C语言的灵活性和高效性,但同时会导致C程序中存在大量的指针缺陷。C语言应用于很多安全攸关的领域,比如操作系统、服务器软件、航空航天相关软件等,由C程序指针缺陷引起的安全事故往往具有严重的后果。因此,对C程序指针缺陷的检测技术进行研究,对于提升软件的可靠性与安全性,具有十分重要的意义。针对现有技术存在的问题,本文从程序内存模型的构建、指针缺陷的规模化检测、指针缺陷检测工具的实现三个层次开展研究,主要成果包括:针对现有指针缺陷检测技术内存模型精度不足的问题,本文提出了基于约束敏感的指针分析和轻量级求解技术建立程序精确内存模型的算法。本文首次提出了约束敏感的指针分析算法,通过路径约束对指针的指向关系进行限制,提升分析精度。本文提出了轻量级求解技术,用于对路径约束进行快速求解,过滤不可达路径及不可满足的指向关系。利用得到的指针分析结果,可以建立程序的精确内存模型。针对现有指针缺陷检测技术规模化能力不足的问题,本文提出了基于多入口策略的指针缺陷规模化检测技术。本文利用基于状态约减的检测方法对程序进行过程内的分析。对于不同的缺陷类型,可以设计多个分析模块对程序进行分析,每个分析模块均可设计为正向或反向。本文提出了组合式函数摘要的策略,通过组合式函数摘要模拟程序的多种行为。通过过程内分析结合函数摘要,本文实现了程序的过程间分析,保证了分析的精度。为了保证分析效率,本文提出了多入口的规模化检测技术。针对每个入口,本文提出了利用组合测试技术对可能执行路径进行剪枝的策略。本文实现了针对C程序的指针缺陷检测工具Tsmart-GPChecker。本文的内存建模算法和多入口策略均实现于Tsmart-GPChecker中。Tsmart-GPChecker实现了多类分析模块和函数摘要,能对多类CWE缺陷进行检测。本文将Tsmart-GPChecker在测试集、开源项目和实际场景上进行了应用,应用结果表明了工具的精确性和高效性。
Pointer is one of the most important characteristics of C language, which is the core and soul of C language. Pointer defect refers to the defect caused by the wrong or irregular use of a pointer. C program requires the developer to maintain the pointer and manage the memory dynamically. This mechanism ensures the flexibility and efficiency of C language, but at the same time, it leads to a large number of pointer defects in C programs. C language is used in many security related fields, such as operating system, server software, aerospace related software, etc. The security accidents caused by pointer defects often have serious consequences. Therefore, it is very important to study the detection technology of pointer defects for improving the reliability and security of software. In view of the problems existing in current technologies, this paper studies from three levels: how to build the memory model of a program, how to make the detection of pointer defects scalable, and how to implement the pointer defect detection tool.To solve the problem that the accuracy of memory models used in existing pointer defect detection technologies are insufficient, this paper proposes an algorithm for building accurate memory models based on constraint-sensitive pointer analysis and light weight constraint solving technology. In this paper, a constraint-sensitive pointer analysis is proposed for the first time. The points-to relationships are gated by path constraints. This paper presents a light weight constraint solving technology, which can solve the path constraints quickly. It is used to filter the unreachable paths and unsatisfied points-to relationships. Using the results of pointer analysis, the accurate memory model of the analyzed program can be established.To solve the problem of insufficient scalability of existing pointer defect detection technologies, this paper proposes a scalable pointer defect detection technology based on multi-entry strategy. In this paper, the detection method based on state reduction is used to implement an intra-procedural analysis. For different types of defects, we can design a variety of analysis modules to analyze the program. Each analysis module can be designed as forward or backward. In this paper, a strategy named combined function summary is proposed to simulate various behaviors of a program. Through the combination of an intra-procedural analysis and function summary, this paper implements an inter-procedural analysis, which ensures the accuracy of the analysis. To ensure the algorithm's efficiency, this paper proposes a multi-entry mechanism. For each entry, a strategy of pruning possible execution paths by combinatorial testing technology is presented.This paper implements a pointer defect detection tool for C programs, Tsmart-GPChecker. The memory modeling algorithm and multi-entry strategy proposed in this paper are implemented in Tsmart-GPChecker. Tsmart-GPChecker implements many analysis modules and function summaries. It is able to detect many types of CWE defects. In this paper, Tsmart-GPChecker is applied on benchmarks, open source projects and actual scenes. The results show that the tool is quite accurate and efficient.