（计算机应用技术专业论文）嵌入式软件的c语言代码静态检查技术研究.pdf

浙江大学硕士学位论文 摘要 摘要 嵌入式系统是一种集软件和硬件于一身的特殊计算机系统。随着其在国防、 航天、工业控制等若干重要领域的应用越来越广泛，嵌入式软件系统本身的安全 性也变得越发重要。c 语言是嵌入式软件开发中应用最广的编程语言，因此，对 c 语言程序的安全性验证成为了保证嵌入式系统安全的关键。 c 语言程序的检测方法分为动态和静态两大类。动态检查又称为运行时检查， 是实际运行时检测程序的方案，在c 程序运行过程中，通过选择适当的测试用例， 并对程序的运行状态进行监控以发现程序中的错误。静态检测是指不在计算机上 实际执行所检测的程序，而是采用分析代码文本、人工模拟或类似动态分析的方 法，借助相关的静态分析工具完成程序源代码的分析与检测。由于嵌入式软件特 殊的开发模式，静态检测相对于动态检测具有过程简单，检测代价小的优点，是 检测嵌入式软件的理想方法。本文通过对国内外该领域相关研究的学习，总结了 c 语言中常见的安全隐患，介绍了每种隐患产生的原因。在此基础上，主要介绍 了两种检测方法，一种是基于标注的检测模型，用来检测指针和内存引用错误。 另一种是通过对c 语言编译过程中间结果的分析来检测堆栈溢出错误。其中第二 种方法是本文的主要工作和创新点。 指针和内存错误是c 语言安全隐患中最常见同时也是最难检测的错误，本文 介绍了一种基于源代码中附加标注的静态检测模型，通过标注每个对象的状态来 检测内存和指针访问错误。嵌入式系统有限的硬件资源使得堆栈的溢出检测成为 了安全保障的一个重要的环节。本文通过c 语言的内存模型和函数调用过程，详 细介绍了堆栈溢出错误的产生原因，提出了一种基于编译过程中间结果的静态检 测方法，并对所涉及的关键技术进行了详细介绍。最后，给出了整个堆栈静态检 查器的系统设计和实现，并通过测试证明了该方法的正确性和可用性。 关键词嵌入式系统，标注模型，堆栈溢出，静态检测 浙江人学硕1 ：学位论文 a b s t r a c t a b s t r a c t e m b e d d e ds y s t e mi sak i n do fs p e c i a lc o m p u t e rs y s t e mt h a tc o m b i n e st h es o f t w a r e a n dh a r d w a r et i g h t l ya saw h o l e a si ti su s e dm o r ea n dm o r ew i d e l yi ns o m eh i g h l y s e c u r ea r e a ss u c ha sn a t i o n a ld e f e n s e ，s p a c e ，i n d u s t r i a lc o n t r o l ，t h es e c u r i t yo f e m b e d d e ds y s t e mi t s e l fh a sb e c o m em o r ei m p o r t a n tt h a te v e hci st h em o s tc o m m o n l y u s e dc o m p u t e rl a n g u a g ei ne m b e d d e ds o f t w a r ed e v e l o p m e n t ，s ot h ec o r r e c t n e s s c h e c k i n gf o rcp r o g r a mh a sb e c o m eak e yp o i n ti ng u a r a n t e et h es e c u r i t y f o r e m b e d d e ds o f t w a r e t h e r ea r et w om a i nt y p e si ncp r o g r a mc h e c k i n g ：d y n a m i cc h e c k i n ga n ds t a t i c c h e c k i n g d y n a m i cc h e c k i n g ，k n o w na sr u n - t i m ec h e c k i n g ，i sa k i n do fc h e c k i n gt h a t d ot h ev e r i f i c a t i o nw h e nt h ep r o g r a mi sa c t u a l l yr u n n i n g i tc h o o s ep r o p e rt e s tc a s e ， r u nt h ep r o g r a ma g a i n s tt h e s ec a s ea n dm o n i t o rt h er u n n i n gp r o c e s so ft h ep r o g r a mt o s e ei ft h e r ei ss o m e t h i n ga b n o r m a lh a p p e n e d i fe r r o rh a p p e n e d ，t h em o n i t o rc a nt r a c e t h et r a c ko ft h ep r o b l e mt od e t e c tt h eb u gi no r i g i n a lc o d e t h es t a t i cc h e c k i n g ，o nt h e o t h e rw a y , d o e sn o tr u nt h ep r o g r a mo nt h ec o m p u t e r i n s t e a d ，i tt r yt oa n a l y z et h e s o u r c ec o d e ，s i m u l a t et h er u nt i m eb e h a v i o ro ft h ep r o g r a mi no r d e rt od e t e c tt h e p o t e n t i a lb u ga n d f l a wi nt h es o u r c ec o d ew i t ht h eh e l po fs o m es t a t i cc h e c kt 0 0 1 d u e t ot h es p e c i a ld e v e l o pp r o c e s so fe m b e d d e ds o f t w a r e ，c o m p a r et od y n a m i cc h e c k i n g , s t a t i cc h e c k i n gi ss i m p l e ra n da s kf o rf e w e rr e s o u r c e s s o ，s t a t i cc h e c k i n gi sm o r e s u i t a b l ef o re m b e d d e ds o f t w a r ed e v e l o p m e n t i nt h i st h e s i s ，w et r yt os u m m a r i z et h e m a i ns e c u r i t yc h a l l e n g e sf o rcp r o g r a mb a s e do nt h er e l a t e dr e s e a r c hw o r k si n t h i s a r e aa n da n a l y z et h er e a s o nf o rt h e s es e c u r i t yp r o b l e m s b a s eo na l lo ft h e s ew o r k s ，w e i n t r o d u c et w om a i nm e t h o d sf o rs t a t i cc h e c k i n go fcl a n g u a g e t h ef i r s to n ei sa n a n n o t a t i o nb a s e dm e t h o du s e dt od e t e c tt h em e m o r ya n dp o i n t e re r r o ra n dt h es e c o n d o n ei sas t a c ko v e r f l o wd e t e c t i o nm e t h o db a s eo nf u n c t i o nc a l l i n ga n a l y z i n g t h e s e c o n do n ei st h em a i nc o n t r i b u t i o no ft h i st h e s i s m e m o r y a n dp o i n t e re r r o ra r et h em o s tc o m m o na n dh a r d e s td e t e c t i n ge r r o r si nc p r o g r a m i nt h i st h e s i s ，w ep r e s e n tas t a t i cc h e c k i n gm o d e lu s i n ga n n o t a t i o ni ns o u r c e 浙江人学硕 ：学位论文 a b s t r a c t c o d et os o l v et h e s et w op r o b l e m s t h em o d e lm a r k sa l lo ft h eo b j e c t si np r o g r a mw i t h d i f f e r e n ta n n o t a t i o n s ，b yc h e c k i n gt h ec o n s i s t e n c ya m o n gs t a t e sa n da n n o t a t i o n s ， m e m o r ya n dp o i n t e re r r o r s c a nb ed e t e c t e d b e c a u s eo ft h el i m i t e dr e s o u r c ei n e m b e d d e ds y s t e m ，d e t e c t i n gf o rs t a c ko v e r f l o wh a sb e c a m ea ni m p o r t a n ta s p e c ti n s t a t i cc h e c k i n g i nt h i st h e s i s ，w ei n t r o d u c et h em e m o r ym o d e la n df u n c t i o nc a l l i n g p r o c e s si ncp r o g r a m e x p l a i nt h ec a u s eo fs t a c ko v e r f l o w b e y o n dt h a t ，w ep r o p o s ea s t a t i cc h e c k i n gm e t h o df o rt h es t a c ko v e r f l o wp r o b l e m d e s c r i b et h ek e yt e c h n o l o g i e s i nd e t a i l a l s o ，w ed e s i g na n di m p l e m e n t e dt h ew h o l es t a c ko v e r f l o wc h e c k e r , t e s t i n g i t sc o r r e c t n e s sa n du s a b i l i t yt op r o v et h a ti t sw o r k si nt h er e a ls y s t e m k e y w o r d s ：e m b e d d e ds y s t e m ，a n n o t a t i o nm o d e l ，s t a c ko v e r f l o w , s t a t i cc h e c k 浙江人学硕十学位论文 幽目录 图目录 图1 1 嵌入式应用环境1 图2 1s t a c k a n a i y z e r 示意图1 1 图3 1 示例代码2 0 图3 2 示例代码控制流图2 1 图4 1c 语言内存结构2 5 图4 2 函数堆栈示意图2 7 图4 3 栈帧结构示意图2 8 图4 4 函数调用堆栈变化图3 0 图4 5 函数序言示例3 4 图4 6c 程序调用关系图3 6 图4 7r t l 代码示例3 8 图4 8 平儿的遍历算法3 9 图4 9 堆栈溢出分析算法。4 1 图4 1 0 堆栈检查器系统结构图4 2 图4 11 堆栈检查器u m l 图4 3 图4 1 2 调用关系子模块流程图4 5 图4 1 3 堆栈分析子模块流程图4 7 图4 1 4 调用图分析子模块流程图4 9 图4 1 5 单件模式示意图5 0 图4 1 6 配置管理子模块流程图5 1 图5 1 递归调用测试结果。5 5 图5 2 堆栈溢出测试结果5 5 图5 3 f 常运行状态5 6 图5 4 参数错误提示5 7 图5 5 程序运行时间随代码量增长趋势图5 8 i i i 浙江人学硕上学位论文 表目录 表目录 表5 1j a v a 自带的时间测试工具测试结果5 8 i v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝姿盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名： 潘超 签字日期： 衫年乡月日 学位论文版权使用授权书 本学位论文作者完全了解逝姿盘堂 有权保留并向国家有关部门或机构 送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝姿盘鲎可 以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 庙超 导师签名1 签字日期：够年月 蜘 签字日期： u 矿年( ) q 月b 日 浙江人学帧l 学位论文第1 帝绪论 1 1 课题的背景和意义 第1 章绪论 1 1 1 嵌入式系统的广泛应用 嵌入式系纠l 】一般指非p c 系统，有计算机功能但又不称之为计算机的设备 或器材。它是以应用为中心，软硬件可裁减的，适应应用系统对功能、可靠性、 成本、体积、功耗等综合性严格要求的专用计算机系统。简单地说，嵌入式系统 集应用软件与硬件于一体，类似于p c 中b i o s 2 】的工作方式，具有软件代码小、 高度自动化、响应速度快等特点1 3 j ，特别适合于要求实时和多任务的体系。嵌入 式系统主要由嵌入式处理器、相关支撑硬件、嵌入式操作系统及应用软件系统等 组成，它是可独立工作的“器件”。 嵌入式系统几乎包括了生活中的所有电器设备，如图1 1 所示。掌上p d a 、 移动计算设备、电视机顶盒、手机上网、数字电视、多媒体、汽车、微波炉、数 字相机、家庭自动化系统、电梯、空调、安全系统、自动售货机、蜂窝式电话、 消费电子设备、工业自动化仪表与医疗仪器等都含有嵌入式系统。 图1 1 嵌入式应用环境 盛啊翟 浙江人学顾十学位论文第1 章绪论 嵌入式系统的硬件部分，包括处理器微处理器、存储器及外设器件和i o 端口、图形控制器等。嵌入式系统有别于一般的计算机处理系统，它一般不具备 像硬盘那样大容量的存储介质，而大多使用e p r o m 、e e p r o m 或闪存( f l a s h m e m o r y ) 作为存储介质。软件部分包括操作系统软件( 要求实时和多任务操作) 和应用程序。应用程序控制着系统的运作和行为；而操作系统控制着应用程序与 硬件的交互。 1 1 2 嵌入式软件的开发环境 不同于一般形式的软件编程，嵌入式系统建立在特定的硬件平台上，势必要 求编程语言具备较强的硬件直接操作能力，同时，当嵌入式系统应用在一些控制 敏感的领域时，有很强的实时性要求，所以，编程语言的效率必须很高。无疑， 汇编语言具备这样的特质。但是，归因于汇编语言开发过程的复杂性，它并不是 嵌入式系统开发的一般选择。而与之相比，c 语言一种”高级的低级”语言， 则成为嵌入式系统软件开发的最佳选择1 3 j 。 嵌入式软件开发与传统的桌面软件系统开发相比有一些显著的特点，它一般 需要一个交叉编译和调试环境1 4 1 ，即编辑和编译软件在主机上进行( ，比如主机使用 w i n d o w s 操作系统1 ，编译好的软件模块需要下载到目标机上运行1 3 j 。 目标机的 硬件环境一般都比较有限，通过在目标机上调试代码的方法发现错误往往代价很 高，效率很低。因此，引入代码的静态验证技术，在代码运行之前就在开发端的 主机上对代码进行检测就显得很必要。 1 1 3 嵌入式c 代码静态验证的意义 c 语言是一个开放的语言，语法形式自由，不同的人可以编写出实现同一功 能而源代码形式多样的程序。使用c 能编写高性能程序，包括系统程序和应用程 序，但是，c 语言与它的支持库本质上是不安全的【5 1 ，无意中的失误可能导致非 常严重的安全漏洞。 本课题的提出，来源于一个嵌入式系统在航天上的应用。由于航天系统对软 件的质量要求极高，且采用在目标版上运行代码进行调试的方法代价高，效率低。 2 浙江人学硕- 学位论文 第1 章绪论 所以，需要在运行之前通过静态验证技术尽可能多地发现代码中的缺陷。 1 2 课题的研究目标 本文的研究目标是：通过对国内外c 代码静态检查技术的研究，总结出嵌入 式c 代码可能面临的主要安全隐患以及在静态检测阶段发现这些隐患的主要方 法。分析当前能够使用的一些静态检查工具的特点和主要功能。同时，结合航天 项目的要求，详细研究堆栈溢出问题在嵌入式系统中的产生原因、危害和解决方 案，设计和实现一个能够在函数级别检测堆栈溢出和嵌套调用的堆栈检测工具。 1 3 拟解决的关键问题 传统的c 代码静态检测技术的研究，多集中在内存访问错误，指针引用错误， 缓冲区溢出错误等内存管理相关的内容。而本文除了对这些错误的检测方法进行 研究之外，还针对航天系统的特殊需求，重点研究了嵌入式c 程序中的堆栈溢出 错误，以及如何在静态分析阶段对其进行检测并最终实现一个堆栈溢出的静态检 测工具。 1 4 论文组织 整个论文分为6 章。 第一章绪论。本章介绍了整个论文的选题背景和意义，主要的研究目标和将 要解决的关键问题。 第二章c 代码静态检测研究综述。本章总结了c 代码面临的主要安全隐患， 介绍了c 代码静态检测面临的主要问题，国内外对于这一问题的主要研究方向、 研究成果和目前能够使用的静态检测工具。 第三章内存管理错误的检测。 本章介绍了内存管理相关的一系列错误产生 的原因和如何使用一种基于代码中添加标注的方法来对这些错误进行静态检测。 第四章堆栈溢出检查。本章介绍了本文的主要工作静态堆栈溢出检测。 详细分析了堆栈溢出产生的原因、解决方案设计、系统设计和具体的算法实现。 第五章实验与测试。本章介绍了对于堆栈溢出检查器的测试框架、测试策略 浙江大学硕 ：学位论文第1 章绪论 设计以及最终的测试结果和分析。 第六章总结与展望。本章总结了本文的主要工作，并提出了将来的改进方向。 4 浙江大学硕_ 上学位论文 第2 章c 代码静态检查研究综述 第2 章c 代码静态检查研究综述 2 1 嵌入式c 代码主要的安全隐患 一般认为，普通c 代码中主要的安全隐患集中在内存访问、指针引用、缓冲 区溢出、异常控制等几个方面【6 1 。在嵌入式代码中，因为内存大小受限，使得堆 栈内存空间的溢出也成为了一个需要特别重视的安全问题。下面简要介绍几类安 全隐患。 2 2 1 内存访问错误 c 语言程序中引发的安全问题绝大多数属于内存访问错误，内存访问错误可 能由数组、指针或内存管理过程造成。对指针和数组缺乏边界检查是造成内存访 问错误的根源。据统计，超过5 0 。6 0 的软件故障是由指针和数组访问造成的1 7 1 。内 存错误主要有以下几种类型【8 1 1 1 内存分配未成功，却使用了它。典型的情况就是从堆中动态申请内存； 2 ) 内存分配虽然成功，但是尚未初始化就引用它。在c 语言中，内存的 缺省初值没有统一的标准【9 1 ，如果引用了末被初始化的变量，可能会 导致程序错误； 3 ) 内存访问越界，典型的情况是数组下标超过了数组的大小； 4 ) 内存泄漏，在使用完后忘记释放内存，程序运行一段时间后内存耗尽； 5 、) 引用已经释放了的内存。 内存访问错误由于在语法上完全符合c 语言的规范，因而不能被编译器发现， 而且在动态调试时也常常难以再现出错的异常情况，所以是检测中的难点。 2 2 2 缓冲区溢出错误 缓冲区溢出【1 0 1 即是越过数组边界读写内存。标准c 库中提供有许多诸如 g e t s ( ) 、s t r c p y o 、s t r c m p 0 、s p r i n f o 等字符串函数，它们在被编译时会分配连续的 存储空间。但由于程序员不能预先确定缓冲区大小，如果读入的字符串长度超出 给定的存储区的长度，则超出的部分字符会覆盖给定区域的后续相邻空间，由此 5 浙江人学硕十学位论文 第2 章c 代码静态检查研究综述 会引起【1 1 1 ：被覆盖区域的内容非常关键从而产生严重的安全隐患；通过覆盖运行 栈中函数的返回地址，可引诱程序执行任意代码。 2 2 3 指针引用错误 空指针即没有指向任何合法存储的指针，由于c 语言中指针指向的内容在程 序运行之前是不确定的，所以在编译阶段认为正确的代码很可能在运行时指向了 一个无意义的地址。为此程序在使用指针时，不仅要关心指针本身足否定义，还 要关心指针是否已经指向了合法的内存空间【1 2 】。应该检查从指针定义到其引用的 每条可能路径，以确定指针是否指向了合法的内存空问。 2 2 4 异常控制 c 语言没有异常处理机制，所有的异常检测和处理都必须由程序员手动来完 成【1 3 】，如果程序员没有明确处理异常情况，那么异常发生时系统将出现不可预测 的错误。比如在执行打开文件操作时，代码总是假设系统中一定存在某个文件， 并且打开总能成功。如果这个文件被恶意地删除，或者程序运行的权限不够致使 打开不成功，那么，后续的读操作将发生核心错( c o r e d u m p ) 。因此c 程序员有义 务增加异常检测和处理代码，进行主动防错设计。 2 2 5 堆栈溢出 c 语言使用堆栈来存储局部变量和传递函数的参数，所以，如果函数的调用 层数过多或者出现了递归调用，就非常容易使得堆栈上的内存需求超过了最大能 够使用的空间限制，产生堆栈溢出。在普通的p c 系统中，堆栈溢出并不是一个 很明显的问题，一是因为很多系统中含有存储器管理单元( m m u ) ，可以提供对 堆栈内存空间的保护【1 4 】。二是因为普通p c 系统存取器容量较大，可以分配给堆 栈足够的内存空间，但是在内存容量受限制且大多不具备内存保护机制的嵌入式 设备上，堆栈溢出经常会出现，而且一旦出现，往往意味着整个系统崩溃。所以 在对嵌入式的c 代码进行检查的时候，堆栈溢出检查是一个很重要的方面i z o j 。 6 浙江人学硕十学位论文第2 章c 代码静态榆查研究综述 2 2 静态检测和动态检测的对比 目前对c 代码的检查，主要分为动态分析和静态分析两种【1 5 】： 动态检查又称为运行时检查，是实际运行时检测程序的方案，在c 程序运行 过程中，通过选择适当的测试用例，并对程序的运行状态进行监控以发现程序中 的错误。该技术依靠系统编译程序和动态检查工具实现检测，优点是检测的结果 比较接近于程序的真实运行状态，对于内存使用情况，空指针引用等错误的检测 比较准确。但缺点是检测的全面性严重依赖于测试用例对代码的覆盖情况，运行 时间较长，而且对于程序中的递归调用等过程，动态检测很难覆盖全部的情况。 静态检测是指不在计算机上实际执行所检测的程序，而是采用分析代码文本、 人工模拟或类似动态分析的方法，借助相关的静态分析工具完成程序源代码的分 析与检测。通过扫描源程序正文，对程序中的数据流和控制流进行分析，来发现 编译阶段没有发现、定位运行阶段难于定位的错误。在嵌入式系统中，很多时候 无法在最终的开发板上大量地运行测试用例来做动态分析1 1 酬，所以，静态分析的 工具和方法在嵌入式系统中有着更大的价值。 2 3 静态分析的主要困难 尽管静态分析相对于动态分析在嵌入式c 代码的分析上有很多优势，但由于 静态分析不是真正地执行代码，往往需要通过对程序运行过程建立模型、分析模 型来得出结论，所以，在实现上也有着很大的困难，主要表现在【1 5 】： 1 ) c 语言自由的风格致使其不太适合静态分析。c 语言大量地使用指针，而 指针具有动态性和别名特点，很难进行静态跟踪。 2 ) c 语言缺乏异常处理机制的支持，使得程序设计时只关注系统功能的实现， 较少考虑异常情况的检查与处理。 3 ) 如果在程序中函数调用关系非常复杂并伴有中断处理程序，那么，要精确 地模拟程序的运行状态就需要非常大的搜索空间1 1 7 j ，在时间上是不可行的。所以， 需要在精确度和速度上进行取舍。 7 浙江大学硕士学位论文第2 章c 代码静态检查研究综述 2 4 国内外相关研究 目前在静态检查方面比较通用的方法有两类，一类是针对空指针、非法内存 访问、类型不检查和缓冲区溢出等错误，以及编码风格上的一些缺陷，通过规则 检查来发现代码中的缺陷。另一类是通过对程序的数据流和控制流进行分析，采 用建立特定模型的方法来检测诸如未初始化数据，未释放指针等的错误。以下是 一些主要的研究成果介绍。 t h o m a sr e p s 提出了一种如何通过分析数据流和控制流的方法来对c 代码进 行检测的思想【1 8 】。这种方法对整个程序的运行状态建模，构造数据流和控制流的 转换图，通过图论的方法对图进行分析，得到关于程序运行状态的信息。但t h o m a s 的工作更多地是进行了数学上的证明，提出了一些通用的准则，并没有太多地针 对具体问题提出解决方案。这种对图的分析思想，被后续的很多研究所借鉴。本 文的主要工作堆栈溢出检查，也借鉴了这种思想。 d a v i de v a n s 和他的研究小组提出了一种在代码中使用标注来检测空指针引 用，未初始化内存和内存泄漏等错误的轻量级静态检测框架【1 9 1 。他和j o h ng u t t a g 等人一起，将这种方法应用在他们开发的原型系统中，催生出了著名的代码检测 工具l c l i n t 2 。这个静态检查工具能够检测出未初始化变量、空指针引用、缓冲 区溢出、非法内存访问等很多编译器无能为力的错误【2 射，至今仍然被广泛地应用 在许多使用c 作为开发语言的工程中。 t o d dm a u s t i n 介绍了一种s a f ep o i n t e r 的数据结构【1 2 1 ，通过为每一个指针附加 一个这样的结构，来记录该指针变量类型、基地址和地址范围，在访问该指针时 根据这些值进行访问合法性检测，从而避免了非法的内存访问。这种方法需要对 c 语言源程序进行改写，而且只能用于由指针非法访问引起的运行时错误，可推 广性不强。 h a oc h e n 和他在u cb e r k e l y 的同事提出了一种使用m o d e lc h e c k i n g 的方法来 发现c 代码安全漏洞的技术【2 3 】，他们介绍了c 代码可能出现的5 种安全隐患及相 应的检测技术，同时也给出了使用他们开发的原型系统m o p s 进行检测的结果。 严格来说，他们的研究偏重于对u n i x 系统中安全漏洞进行攻击的检测，属于计 8 浙江大学硕i ：学位论文第2 章c 代码静态检查研究综述 算机安全技术的范畴。 j o h nr e g e h r 提出了一种通过对通用寄存器和中断控制寄存器的状态进行建模 来检测堆栈溢出的方法。这种方法将程序的运行过程表示为一个状态迁移流程 图，通过对这个图的分析来判断是否存在堆栈溢出的情况。本文借鉴了这样的思 想，但对建立图和分析的方法进行了较大的改进。 2 5 常用工具分析 目前能够使用的c 代码检查工具很多，在功能上也是各有侧重，下面简要介 绍几个比较常用的工具。 2 5 1p c - 1 i n t p c 1 i n t 2 4 】是u n i x 的时代的产物，价格相对较低，功能上也比较强大，是应用 最广泛的c 代码静态检查工具之一。它是基于d a v i de v a n s 和他的小组开发的原 型系统l c l i n t 进行实现的，其主要功能包括了： 1 1 强类型检查：解决自定义类型的匹配问题的问题。 2 ) 初始化跟踪：对没有初始化的变量进行警告 3 ) 赋值跟踪：可以对自动的变量的值进行跟踪，在错误的使用的时候进 行报警 4 ) 参数检查：对于一些函数进行参数检查( 可进行配置) ；对参数进行 非空性检查，对某个函数进行怎样的检查时完全可以配置的。 5 1 求值顺序：对于语法上的歧义性进行警告 6 ) 格式检查：对p r i n t f 和s c a n f 中的格式字符串进行检查 7 ) 缩进检查：代码缩进的检查 8 1 对c o n s t 和v o l a t i l e 变量的检查 2 5 2l o g i s c o p e l o g i s c o p e l 2 5 l 有三项主要功能，以三个独立工具的形式出现，分别是：软件质 量分析工具a l l d i t ；代码规范性检测工具r u l e c h e c k e r ；测试覆盖率统计工 9 浙江大学硕f ：学位论文第2 章c 代码静态检查研究综述 具一e s t c h e c k e r 。a u d i t 和r u l e c h e c k e r 提供了对软件进行静态分析的功能， t e s t c h e c k e r 提供了测试覆盖率统计的功能。 l o g i s c o p e 可以对多种语言实现的代码进行分析，比如c 、c + + 、j a v a 、a d a ， 等等。该软件更多地是对编程风格和软件工程质量的检查。 2 5 3q a c c + + q a c c + + 2 6 】的特点是支持软件工程、软件认证、软件过程认证和各种质量认 证标准，也集中了代码编写规范和注释规范性上的检查，可以和多种开发工具， 如v c 6 0 ，t o r n a d o 等集成，可以定制检查规则，检查结果以可视化的方式呈现， 使用比较方便。其主要特点有： 1 ) 代码规则检查自动化 可以自动识别c 语言源代码中出现的问题。这些问题主要是语言使用过程不 安全，过于复杂，无法移植，难以维护或与该行业的代码标准偏离造成的。能够 对许多编译器或其他工具开发软件无法说明的问题提出警告。极大的缩减代码检 测的时间并能同时加强程序设计人员对c 语言中不完全为人理解的某些特点的 认知。能够在开发软件早期阶段对存在的问题加以注意，提高代码质量，缩短测 试周期。 2 ) 提供深层次的静态分析 可迅速而有效地检测出语言运用中的错误、己过时用法、程序标准一致性问 题，从而防止在软件开发的后期以更昂贵的代价去解决问题。而且还将工业分析 度量标准和通俗易懂的报告结合在一起。能够使用4 4 种被工业界认可的衡量标 准，其中包括圈复杂度量图，静态路径计算和m y e r s 间隔度量。 3 ) 规则可以定制 对于工具的数据库中已有的规则，可以由测试人员决定使用哪项规则或不使 用哪项规则，或者是某一个错误等级的规则。 4 ) 可以和开发工具集成 可以和v i s u a ls t u d i ov 6 0 、v i s u a ls t u d i o n e t 、t o r n a d o 集成，在开发环境中 1 0 浙江大学硕士学位论文第2 章c 代码静态检查研究综述 来使用q a c ，提高测试效率。 2 5 4p o l y s p a c ecv e r i f i e r p o l y s p a c e 【明软件是由p o l y s p a c e 公司开发的一个程序运行时错误的静态检查 工具。该软件采用基于源代码静态建模的方法来检查程序在运行时可能出现的错 误，可以大幅度的提高软件的可靠性，降低测试成本，缩短软件的开发周期。 p o l y s p a c c 主要优势 1 ) 在模型层次上查找b u g 和引起功能错误的原因，加速了调试效率； 2 ) 缩短了代码阶段才检查运行时错误的工作量； 3 ) 快速检查手写代码编写的函数、客户模块和状态流中的错误； 可以用来确认最终发布的软件是没有错误的，具有高可靠性； 5 ) 帮助模型设计者生成可重用的模型； 2 5 5s t a c k a n a l y z e r 目前，在堆栈分析方面，还没有太多成熟的工具可用，唯一可以使用的是商 用分析工具s t a c k a n a l y z e r 【2 8 l 。这款软件，如图2 1 所示，可以自动分析出应用 程序中最差情况下的堆栈使用情况：分析结果以标注的形式在调用关系图和控制 流图中显示。 “。”*一1” j 一。7i ，。 ，i ；一雾4 - 4 | ：一一一一， i ，垦兰戛雨 ：l 弘= ! ? = ? 。 ； 。 ， + i j 兰；z 蠹：量二 一 f ；：? ：一。_ ，。， 一l 。 图2 1s t a c k a n a l y z e r 示意图 浙江人学硕十学位论文第2 章c 代码静态柃查研究综述 它可以计算出任何一个函数的堆栈使用情况，并且起始点可以任意选取，也可以 预报可能出现的堆栈溢出，以及优化对堆栈的使用。但是，这款软件是一个需要 付费的商用产品，且价格较高。同时，由于没有源代码，无法对其本身的安全性 进行评估，因此不能在航天软件开发上进行应用。 上述所有的静态检查工具除了p c l i n t 现在有开源的版本s p l i n t 可以使用以 外，全部都是商用软件。应用在航天软件的开发过程中是不适合的，因为无法对 这些工具本身的可靠性和安全性进行验证。在堆栈检测方面的工具，更是没有开 源的项目可供选择，所以，开发一个自主知识产权的堆栈检测工具，是尤为必要 的。 2 6 本章小结 本章介绍了嵌入式c 代码检查的主要研究方向，对比了静态和动态检测，分 析了静态代码检测所面临的主要困难以及国内外的相关研究的成果。最后，列举 了一些应用比较广泛的代码静态检测软件，对各自的特点进行了介绍。 1 2 浙江大学硕上学位论文 第3 章内存和指针错误检查 第3 章内存访问和指针错误检查 3 1 内存和指针错误种类 指针引用和内存访问错误是c 语言中两类最常见又最难以检查的运行时错 误。在本文中，内存访问错误主要是指：由于m a l l o c 和f r e e 函数的不当使用造成 的内存泄漏和对已经释放内存的再次访问：而指针引用错误主要是指：对未定义 的内存进行使用和对已经定义但却没有初始化的内存进行引用两种。可以看出， 引起指针引用错误的主要原因也是由于对于相应的内存区域没有能够正确使用 造成的，所以，在静态检测中可以采取类似的方法对这两种错误进行检测。 3 2 基于标注的静态检测模型分析 指针是c 语言中最灵活的语法，通过它可以对内存进行直接的读写，由于没 有类型检查，边界检查等安全手段的介入，使得指针和内存错误很难在静态编译 阶段被检查出来，因为所有的指针引用和内存访问语句从语法上看都是没有任何 问题的。因此，对这些错误进行静态检查需要引入额外的关于内存区域的信息， 这些信息，称为代码中的标注【2 9 】( a n n o t a t a i o n ) ，这种方法，称为基于标注的代码 静态检测模型。 c 语言中每个变量都代表了一块内存区域，在基于标注的方法中，每块内存 区域都被称为一个对象( o b j e c t ) ，这些对象有一系列的属性和运行时状态，比如 是否可以为空( n u l l ) ，是否已经定义，是否可以共享等。这些属性和状态是由软 件开发者来定义的，定义的方式就是在程序中添加额外的标注。比如 * n o n n u l l 搴就是一个标注，由注释标识和标注文字组成。由于将所有的标注文 字部分都包含在了注释符中，所以不会影响程序的正常编译。标注文字决定了标 注的性质，例如，上面的标注就说明一个变量的值不能为n u l l 。 每个对象都有一系列标注来指定了它的性质和状态，随着程序控制流的迁 移，这些状念会不断改变，通过在每次程序的控制流发生迁移的时候检查程序中 所有对象状态和属性的一直性，就可以静态地发现程序中可能存在的内存访问和 1 3 浙江大学硕i j 学位论文第3 章内存和指针错误榆查 指针引用错误。同时，为了不增加开发时的难度，所有的对象都有默认的状态标 注，从而不需要程序员自己在代码中逐个声明，这些默认标注在没有其他显式的 标注的时候起作用。 3 2 1 存储模型分析 3 2 1 1 对象和对象的定义状态 对象每个对象是一块有类型的内存区域。某些对象是自动分配和回收的， 而某些是在堆上分配和回收的，需要程序员自己管理。 一个内存区域的定义状态有3 种，分别是： u n d e f i n e d ：这个内存区域没有被定义； d e f i n e d ：这个内存区域已经被定义； c o m p l e t e l yd e f i n e d ：一般用于结构体类型的对象，如果该对象中能够到达的所 有域的定义状态都是d e f i n e d ，则称这个对象被完全定义了。 3 2 1 2 左值和右值 当一个变量在等号( 赋值语句) 左边被引用时，就称为左值，在等号右边被引用， 就称为右值。一个未定义的内存可以被用做左值，但是不能被用作右值。 3 2 1 3 指针类型和指针状态 指针的状态可以是有效或者是过期。一个有效的指针可以为n u l l 或者是指 向一个已经分配了的内存区域。一个指向对象的指针称为对象指针，而一个指向 对象内部的指针称为偏移指针。一个指向已经分配的但没有初始化赋值的内存区 域的指针称为已分配指针。一个没有分配内存空间的指针称为过期指针。过期指 针和己分配指针都不能用作右值。 3 2 1 4 对象的外部引用集合 每个对象有一个属于自己的所有者集合，即所有能够在外部引用这个对象的 引用集合。一个外部的引用是指在调用这个函数的上下文中对该内存的引用。如 果经过一个函数调用后使得某个对象的所有者集合是空的，那么这个函数就是有 1 4 浙江大学硕： ：学位论义第3 章内存和指针错误榆查 问题的。因为这意味着在函数外部，没有能够引用这个对象的指针，那么，就不 能通过一个引用来释放它，发生了内存泄漏。 3 2 2 标注分类和语义分析 主要的代码标注有三类：指针标注、定义状态标注和内存分配状态标注。 3 2 2 1 指针标注 指针标注的作用对象是所有的指针变量，其作用是指出该变量在整个生存周 期中是否可能为n u l l 。指针标注分以下三种： n u l l 表示一个指针可能为n u l l n o 姗u l l 表示一个指针不能为n u l l r e l n u l 卜一在被使用时，假设不为n u l l ，但是可以被赋值为n u l l ，是一种 放松了的n u l l 检查。 对于没有明确标注的指针变量，默认的标注值是n o n n u l l 。 3 2 2 2 定义状态标注 此类标注表明一个对象的定义状态，一般用于定义函数参数和返回值的状态， 所有对函数的检查都基于一个假设：即在函数的入口处，所有的实际变量和全局 变量都已经被定义并且赋值了，处于已定义状态。 o u 卜- 当一个函数的参数被标为o u t 时，将假设这个参数已经被分配了内存 空间了，但可能还没有初始化赋值。在函数调用完成后，一个o u t 参数必须 已经是完全定义( c o m p l e t e l yd e f i n e d ) 的，否则，就会引发一个静态检查错误。 如果一个从o u t 参数中导出的引用在没有被定义之前就被作为右值引用了， 被认为是一个错误。一个o u t 参数中所有的域如果在函数返回前没有被完全 定义，也将被认为是一个错误。 p a r t