张华强1，喻胜2，王继刚1，阎波3

　　（1. 中兴通讯成都研究所，四川 成都 610041； 2. 四川精艺防伪科技有限公司，四川 成都 610041；3. 电子科技大学 通信与信息工程学院，四川 成都 611731）

　　摘要：内存相关程序错误的自动检测技术能够帮助程序员尽早发现程序中的内存相关错误，从而提高软件开发效率，增强软件运行的可靠性。探讨了采用前沿的动态二进制分析技术检测软件中与内存相关错误，为程序员定位错误位置、查找错误、消除错误原因提供准确的信息的方法，为致力于内存程序错误检测技术的研究人员提供参考。在C/C++软件中的内存错误检测实例验证了本文方法的有效性。

　　关键词：内存自检；影子内存；静态源码分析；动态二进制分析

0引言

　　软件开发过程中，与内存相关的程序错误(BUG)造成程序不能正常工作的情况非常多。通常都采用程序员手工检查方式消除这类错误。然而，程序员手工检查方式既低效又不完备，而且与程序员的业务能力相关。因此，与内存相关的BUG在软件开发过程中对项目开发的影响非常大。

　　近年来，内存相关BUG的自动检测技术有了很大的发展，可以帮助程序员尽早发现程序中的内存相关BUG，从而提高软件开发效率，增强软件运行的可靠性［12］。这类工具主要检测软件中与内存相关BUG，为程序员定位BUG位置、查找BUG、消除BUG原因提供准确的信息。

　　当前在内存自动检测的所有方法中，根据分析的时机可以分类为静态分析和动态分析方法。这一分类方法的分界点为程序执行，在程序执行前分析称为静态分析，在程序执行中分析为动态分析［34］。另一方面，根据分析操作的对象又可分为源代码分析和二进制目标代码分析［5］。其中，静态分析方法更复杂，由于要分析所有的执行路径而更完备。静态分析的最大问题是误报太多；而动态分析方法简单一些，通常只分析单一的执行路径。由于动态分析方法在分析时各个变量采用的是程序的真实运行值，因此，检查精度更高一些，误报相对少得多。同时，源代码分析与二进制分析方法也是互补的，源代码分析依赖于目标程序的编程语言而与平台（处理器体系结构、操作系统）独立，在分析过程中可以得到程序的高级信息，例如可以定位错误到具体的源代码行。二进制分析方法刚好相反，是依赖于目标程序的平台而独立于编程语言，在分析过程中可以操纵程序的低级信息，例如控制寄存器的分配等。二进制分析的最大好处是分析第三方库时，可以不需要第三方库的源代码就能分析，而源代码分析对此就无能为力了。

　　本文重点讨论通过动态二进制分析技术实现内存自动检测的相关技术和具体实现，研究了如何利用动态插入内存检测技术的二进制级别的内存自动检测方法，使程序员能够更方便地实现内存相关BUG的自动检测实现。

1主要内存相关软件错误

　　本文讨论的软件开发过程中主要的内存相关的软件错误包括以下9种：

　　(1)空指针：程序访问变量的内存地址为0。

　　(2)内存释放：包括释放已释放存储（Free Freed Memory, FFM）、释放未分配存储（Freeing unallocated memory, FUM）、释放地址不匹配（Freeing Mismatched Memory，FMM）、已释放存储区访问(Freed Memory Access, FMA)，指程序读、写的存储空间已在以前释放了，该问题也称为指针悬挂（dangling pointer）或者野指针。

　　(3)越界访问：如果指向某个存储区的指针在进行指针算术、类型转换、赋值操作时，该指针指向另外的存储区，造成操作的操作数发生错误。

　　(4)未初始化存储：没有进行初始化操作，其他的内容是随机的。因此，读未初始化存储区中的数据是无意义的，常常引起程序的异常行为。

　　(5)内存泄漏:如果程序不停地向系统申请存储空间，最终将耗尽进程的虚拟地址空间，内存泄漏通常都是分配了动态存储区，而程序没有释放所致。

　　(6)存储区重叠操作：两个不同的指针指向的内存区出现了部分或者全部重叠,在多线程访问操作时会出现数据不一致的错误。

　　(7)系统调用参数错误：操作系统内部需要做参数检测，防止应用程序提供错误的参数，从而引起系统的崩溃。

　　(8)存储操作匹配:在C++中，如果用malloc、calloc、realloc、valloc和memalign函数进行动态存储分配，则必须用free函数释放分配的存储。如果存储分配用new［］，则必须用delete［］释放，分配用函数new，释放操作必须用delete函数。这些操作在Linux下可以混用，但是在其他一些操作系统下可能出现问题，例如Windows与Solaris。

　　(9)废代码：完全不能执行到代码路径上的代码。

　　针对以上常见内存错误，评价一种内存自动检测技术的检测目标指标主要包括：

　　(1)误报（false positives）：在无错的情况下分析过程报错，这是静态分析的最大问题。

　　(2)漏报（false negatives）：发生错误没报，这是所有分析过程的关键问题，怎样找出程序中的所有问题是分析过程的目标。

　　(3)路径敏感（pathsenitive）：程序中的某些变量在一定值的范围内有些执行路径不可能进入，在分析过程中，排除这些不可能执行路径的分析称为路径敏感分析，这是一种分析优化技术，减少分析过程中的误报。

　　(4)上下文敏感（context-senitive）：某个函数中的变量值和其调用者相关，在分析时能综合考虑这些因素称为上下文敏感。

　　(5)过程间分析（Interprocedual）：几个函数都操作同一变量，分析过程能处理这种情况的，称为过程间分析。与之相对应的过程内分析（Intraprocedual）只在单个函数内分析变量的访问。

2动态二进制分析方法

　　内存检测的动态分析方法是在源代码中插入分析代码、状态检测代码，在运行时，这些代码检测存储区的状态，并且分析程序的行为，从而发现程序中的BUG。目前，内存动态分析技术的实现主要是在动态堆管理库中添加检测代码来实现。库替换可以在编译时替换，也可以在目标程序动态链接时替换，还有其他一些特殊的检测代码插入方法。动态二进制分析和动态源代码分析的主要区别在于，动态二进制分析是在指令级插入检测代码，动态源代码分析是在库级、函数级插入代码。

　　本文动态二进制分析采用的主要技术如下。

　　2.1影子内存

　　在目标代码的指令中动态插入检测代码，检测代码跟踪存储区中每个字节（可以有字级、字节级）的可寻址性或存储区的每个字节（可以有字级、字节级、位级）或寄存器的有效性，这些存储区的存储状态信息保存在影子存储中。当目标程序有数据移动、数据操纵等操作时，检测代码检查影子存储中该字节的状态，从而检测存储相关问题。

　　影子内存具体有多种实现方式，下面是两种最简单的方式。

　　(1)将用户态的地址空间分为2个部分，一部分程序使用，另一部分作为影子内存。存储空间的开销大，地址映射关系简单，查找效率高。

　　(2)采用动态分配的存储作为影子内存，未分配存储空间就不需要影子内存从而优化对存储空间的需求。

　　影子内存的状态位表示对应存储的使用状态。

　　(1)A位：每一个内存字节都有一个A 位（Addressability），用来表示客户程序对其访问的合法性。A＝0 表示不可寻址的字节， A＝1表示可以寻址的字节，分配存储空间时置位，释放时清0；可以检测堆缓冲溢出、指针越界等。

　　(2)V位：寄存器或者内存的每一个字节的每个位（bit）都有一个V位（Validity），用来标明该位的值是已经定义了的。V＝0 表示已经定义位，V=1表示未定义位。可以检测未初始化存储错。

　　图1是本文实现的检测工具影子内存的具体实现情况。

　　图1中，采用二级表实现影子内存管理。表目PM［1］和PM［2］对应已被写入的64 KB内存区，这些已被写入的内存区有自己的影子内存。剩余的PM条目仍指向NoAccess DSM区。

　　2.2状态管理

　　在采用影子内存的检测技术中，通常采用图2所示状态图管理存储区的状态。

　　图2中，系统内存中的每个字节（如果采用位级的影子内存，则是每个位）存在4个状态。

　　(1)程序启动时，所有可用存储区都是unallocated和uninitialized，即在影子内存中对应存储区的A位和V位都置为无效，本文将此类存储区记为为红色状态，访问红色存储区发出未分配存储访问错。

　　(2)存储区分配函数作用于红色存储区、蓝色存储区时，存储区进入图2“Allocated But UnInitialized”状态，即黄色状态存储区。访问黄色存储区发出未初始化存储访问错。

　　(3)当释放函数作用于黄色存储区时，存储区回到红色存储区状态。

　　(4)在黄色存储区进行写操作时，存储区进入图2的“Allocated And Initialized”状态，即绿色存储区状态，访问该存储区是合法的。

　　(5)当释放函数作用于绿色存储区时，存储区进入图2的“Freed But Still Uninitialized”状态，即蓝色存储区状态，访问蓝色存储区状态发出为分配存储访问错。

　　2.3类型检测

　　类型检测方法解释编译后的二进制文件，跟踪所有存储器变量和寄存器的类型值，当存储访问发生类型不匹配错误时，发出警告信息。本文类型检测工具可以检测存储访问错和类型错等两种错误方式。存储访问错指存储访问操作访问无效的存储区（无效的存储区包括读写未分配存储区，访问未初始化存储区等）。类型错指存储访问操作的操作数和操作本身不一致（例如：指针变量和实数相加、调用函数的参数数量或类型错误、将一个整型变量作为一个指针等）。

　　3利用动态二进制方法实现自动内存检测

　　Valgrind是一个动态二进制指令插入（Dynamic Binary Instrumentation，DBI）框架，能够实现运行时（动态）在目标程序中添加检测代码［6］。因此，可以在动态二进制指令插入框架上建立动态二进制分析器，在目标程序运行时从机器指令级上分析目标程序。

　　Valgrind采用模块化的设计方式，系统体系结构基本上可以看成由“Valgrind核心＋工具插件”组成，核心提供一个动态二进制指令插入的基础设施，而各个工具插件提供具体功能的实现。Valgrind核心采用即时编译技术（JustInTime，JIT）（二进制变换）的虚拟机技术，目标程序不直接从实际处理器上运行，而是运行在Valgrind的JIT虚拟机上。

　　以此工具为基础，本文采用影子存储保存存储区的分配状态和存储的类型信息，在目标程序运行时检查这些信息，以检测它支持的存储相关错误。实现的内存自动检测实验结果如图3所示。

　　图3的例程中，先向union写入一个指针值，然后从中读一个整型值。当程序在x.p上存储&i的值时，类型检测器标识union中存储的是指针值（union的类型信息由机器指令lea指令(计算&i)中推导出来）。当程序在取x.k的值进行乘法运算时，类型检测器检测出操作类型不匹配，从而发出警告消息。该例子同时也表明，在不需要编译器和调试器支持的情况下，能进行类型检查。

　　图4内存自动检测的数组越界错误检测实验又如，在图4所示的程序代码中，存在数组越界错误，采用传统内存分析方法不容易检测出来。y.a［10］赋值操作语句中数组已经越界，通过本文类型检测可以发现该类越界访问错误。

4结论

　　静态程序分析误报率、漏报率非常高，在当前的所有自动检测方法中，实用性不强，目前还没有静态分析工具能保证程序的健壮性，通常都作为一种调试手段在使用。动态检测方法可以在程序运行时检测，因此，可以在发布的产品中附带动态检测工具，当在软件实现运行过程中出现问题时，方便开发人员快速定位BUG的位置，从而消除BUG。因此，动态检测方法可以有效地降低程序BUG所造成的损失。本文在动态二进制内存自动检测框架的基础上，通过状态管理和类型检测等方法实现了常见软件内存错误的自动检测。研究结果表明，该自动检测方法能够在不需要编译器和调试器支持的情况下实现高效的内存错误自动检测，为更好地研究自动内存管理提供了帮助。

参考文献

　　［1］ 肖如良. 虚拟计算环境的运行时资源监控与内存泄漏检测技术［M］. 北京：电子工业出版社，2015.

　　［2］ JONES R, HOSKINGntony. 垃圾回收算法手册:自动内存管理的艺术［M］. 王雅光，译.北京：机械工业出版社，2016.

　　［3］ 杨宇,张健. 程序静态分析技术与工具［J］. 计算机科学, 2004,31(2): 171174.

　　［4］ 吴民,涂奉生. 内存泄漏的动态跟踪分析［J］. 计算机工程与应用, 2005,45(14): 1820.

　　［5］ 夏超,邱卫东.二进制环境下的缓冲区溢出漏洞动态检测［J］. 计算机工程, 2008,34(22): 187191.

　　［6］ 潘竹生，童维勤， 周正. 基于Valgrind的嵌入式应用程序调试技术［J］.微计算机信息， 2009, 25(22):5860.