基于控制流切片的代码安全缺陷检测方法

周宽久，杨 广，赖晓晨，崔 凯，姚艳双

（大连理工大学 软件学院，辽宁 大连116620）

0 引 言

软件代码中的缺陷是导致软件故障和漏洞问题的主要原因［1］，国家自然科学基金委也设立可信软件重大研究计划专门解决软件可信性问题，通常的软件缺陷如缓冲区溢出、格式字符串、内存泄漏等无法通过安全子集检测出来，而又是影响软件可信性的主要原因，因此文章重点解决上述这些缺陷，从而达到提高软件可信性的目的。

对于软件代码漏洞缺陷检测的研究，国内外成果很多，Koushik Sen最早提出了concolic（一种白盒测试方法）单元测试的概念［2］，通过符号执行来计算程序的执行路径，研究如何赋初值的问题。Gulwani S提出一种基于有限回溯符号执行（symbolic execution）的缺陷自动验证方法，结合路径条件和缺陷触发条件进行缺陷自动验证［3］。Froihofer L等人则通过源码插桩方式得到程序动态运行的输出信息和日志，可以有效分离系统的业务逻辑与检测逻辑，增加程序动态分析的可靠性［4］。针对代码检测误报率过高的问题，肖庆，官云战等人提出了使用多项式时间复杂度的路径敏感算法实现对代码缺陷的静态检测，该方法通过控制流图实现属性状态条件的合并，判断不可达性，降低误报率［1］。近年来模型验证也成为代码诊断领域研究的热点，卞磊，刘超等人使用有穷状态机模型对过程内变量数据流异常进行检测，根据数据项的状态迁移判断过程内的数据流是否异常［5］。周宽久等人提出了一种基于XML中间模型的代码安全规范检测方法，使用GJB安全子集对代码安全进行分析［6］。陈忠湘，詹瑾瑜等人提出一种带控制流的函数分析模型，对函数间调用次序以及逻辑设计复杂度都有描述，辅助程序设计人员进行分析［7］。

针对C/C＋＋的代码检测技术很多，多为通过抽象语法树AST来获取检测信息，因此实现复杂、扩展性差。文章在XML中间模型［6］的基础上，提出控制流提取模型，获取检测信息，简化控制流图的获取，降低路径分析复杂度；将安全子集检测与数据流异常检测相结合，并将数据流分析扩展到过程间、模块间，从而提高代码缺陷的检测能力。

1 控制流提取模型

控制流提取模型将调用关系用ID节点表示，将ID属性attributes中的IDTYPE记录为 “CALL”，LINENUMBER记录为进行函数调用的行号，NAME同级增加FUNLINE，表示被调用函数的定义行号。属性ASSIGNMENT表示为变量的相关赋值语句行号，形如line1：m1，line2：m2…line n：mn，m1…mn代表所赋具体值。控制流提取模型节点表示如图1所示。

图1 控制流提取模型节点表示

部分标识定义为：

（1）访问标号ACCESS：记录类、结构体和联合体成员的访问标号。

（2）所属结构OWNER：成员的所在类、结构体、联合体或命名空间的名称。

（3）虚函数标记VIRTUAL：指示类成员函数是否是虚函数。

（4）运算符重载OPERATE：记录重载操作符。

（5）基类PARENT：记录派生类的继承基类。

（6）模板TEMPLATE：模板定义和声明的模板参数信息。

2 控制流抽取与分析

获取控制流图是进行控制流分析的基础，更是进行数据流跟踪的前提，只有获取控制流，确定程序执行路径，才能跟踪变量数据流。

2.1 控制流提取模型到控制流转化

利用提取模型对过程间、模块间数据流进行记录，用ID节点中的LINENUMBER作为跳转索引，实现控制流图的构建。过程间代码到控制流提取模型的转化，及提取模型到控制流图的转化都是通过对跳转索引进行跟踪实现的。

下文示例代码包含了一些常见的控制流结构和过程间调用，在描述过程间控制流与数据流关系方面，具有一定代表性。

篇幅所致，仅列出与示例代码相应的控制流节点ID，将与控制流无关的ID删除，使用XQuery技术对中间代码进行分析，获得过程内、过程间以及模块间的控制流信息。

实际程序中转移分支语句数目多、结构复杂，对一些不可达路径进行删减显得尤为重要。因此提出控制流切片及剪枝方法删减代码控制流图数组信息。

2.1.1 控制流切片

程序切片是一种分析和理解程序的技术，通过从源程序中去除零条或多条语句来构造，最早由Weiser于1979年提出，通过计算每个兴趣点的切片来进行程序的分析与理解［8］。文章提出的控制流切片与程序切片的定义接近，为源程序控制流零条或多条分支组成的代码单元，同时也是一个控制流分析单元。

定义1 代码控制流图定义为六元组G＝＜E，P，Estart，Eend，Eentry，Eexit＞ ，其中，E代表节点集，由LINENUMBER［6］标识，P为路径集合，由控制流图数组记录；Estart与Eend为控制流切片起、终点集合，Eentry与Eexit为转移路径起、终点集合。

定义2 控制流切片定义为由主函数路径（i＝0）起始，并交于主函数的控制流图子图，表示为控制流切片起、终点为estart，eend，控制流切片内分支结构的起、终点为einstart，einend。

定义3 控制流切片的函数调用为转移路径，起、终点为eentry，eexit。（Pf表示产生的新增路径集合。主函数路径中转移路径情况例外，表示为定义2中控制流切片

定义4 并接符号Λ表示将两个路径集合并接，P1ΛP2：｛＜p1，p2＞｜p1∈P1，p2∈P2｝，即路径集合P1中的每条路径均可能成为P2中所有路径的前段路径，路径｛p1，p2｝构成完整路径。实现为将两个数组并接，在并接过程的同时，若超过存储范围，则停止检测。

情况3 如果控制流切片中分支结束，即转移到einend，则图2中（Pexit＝（Pstart，因为函数调用与内嵌分支间没有其他结构，因此路径集合不变。其中（Pin为嵌套分支路径集合，（Pstart为进入分支嵌套结构前的路径集合。

根据程序控制流切片的定义及性质，针对主程序的分支情况进行处理，对可能路径进行合并，考虑到嵌套的有限性，对控制流切片内部条件分支以及转移进行同样处理，以控制流切片为单位获取代码的可能执行路径，伪代码描述如下：

可能执行路径获取算法伪代码：

图2 控制流切片

使用上文阐述的可能路径获取算法，获得示例代码的可能执行路径，包括 ｛17，20，26｝，｛17，20，22，1，7，10，13，7，22，23，26｝， ｛17，20，22，1，7，10，13，14，7，22，23，26｝， ｛17，20，22，1，7，10，13，7，22，23，24，26｝， ｛17，20，22，1，7，10，13，14，7，22，23，24，26｝等。图3描述示例代码的控制流图，基于提取模型，通过可能路径获取算法获得代码的可能执行路径信息，并保存在控制流图数组中，利用数组信息对模型中CODELINE的属性节点LINENUMBER进行追踪，并记录所跟踪变量的状态变化。

图3 过程间代码控制流程

可能路径获取算法并未描述break与switch语句的处理方式，switch语句处理需要解析表达式，获取正确路径，处理方法与下文控制流剪枝处理方法相似；break语句处理方式与分支语句结束标签处理方式相同。

2.1.2 控制流剪枝

上文中，控制流图数组信息包含的路径数目巨大，因此根据分支条件，合理对控制流进行剪枝具有重大意义。剪枝可用于包括if、while、for等的分支结构中，主要分两种情况：第一种情况，在条件语句中即可判断真伪，如for（int i＝0；i＜＝10；i＋＋）。第二种情况，需要解析表达式，追踪未知变量，如for（i＝p＊j；i＜＝10；i＋＋）中需追踪p和j的赋值来判断条件语句的真伪。处理方式如下：

情况1 可直接从提取模型中获取变量值，＜ASSIGNMENT＞23：0＜/ASSIGNMENT＞表示在第23行，局部变量赋值为0。由于0＜＝10，因此必定进入for模块中，对该分支节点剪去一枝。

情况2 根据for节点ID行号LINENUMBER［6］标识23（假设23行定义for）以及i的ID节点中＜ASSIGNMENT＞23：p＊j＜/ASSIGNMENT＞，发现相应赋值为p＊j，经过表达式解析分别查找p的ID节点以及j的ID节点，并在其ID节点的ASSIGNMENT内寻找小于并最接近23的行号，发现p＝2，j＝k＋1，同理寻找k的ID节点，发现小于并最接近j＝k＋1行号的赋值记录为k＝5；通过层层递归即可实现条件剪枝，图4通过递归及简单表达式解析求得12大于10，因此不执行for循环，对该分支节点剪去一枝。情况2剪枝原理如图4所示。

图4 控制流剪枝情况2

将剪枝方法应用到控制流抽取中，可以解决常见控制流抽取方法中路径众多的问题，在控制流切片起始点estart进行控制流剪枝，解决了控制流图数组元素过多的问题。

剪枝算法伪代码描述：

算法中FUNCTION2函数为变量追踪函数，追踪变量的最近赋值记录。使用剪枝算法对上文示例代码的可能执行路径进行剪枝，main函数中for（int i＝2；i＜＝3；i＋＋）的条件表达式i＜＝3为真，函数f2中for（int i＝1；i＜＝q；i＋＋）的条件表达式i＜＝q无法判断，因为引入函数参数变量，main函数的if分支的条件无法判断。剪枝算法处理后的可能执行路径为 ｛17，20，22，1，7，10，13，7，22，23，26｝， ｛17，20，22，1，7，10，13，14，7，22，23，26｝， ｛17，20，22，1，7，10，13，7，22，23，24，26｝， ｛17，20，22，1，7，10，13，14，7，22，23，24，26｝等。

2.2 安全规则子集

控制流异常与数据流异常是软件运行异常的两个主要原因，控制流异常主要是由控制结构的使用不当带来的，GJB安全子集中包含了大量描述代码控制流安全的规则，文献［6］中指出在 《GJB 5369－2005航天型号软件C语言安全子集》中代码控制流相关规则（程序风格类，宏指令类以及过程类）所占比例已超过61%，还有一部分描述变量定义与数据操作的安全规则，因此文章使用GJB安全子集对代码控制流进行安全性检测。安全子集中对代码安全隐患描述详尽，但无法检测出变量的状态变化，更无法对变量数据流进行跟踪，挖掘数据流错误，安全子集中关于数据变量的安全缺陷描述仅限于数据变量的定义和操作，因此将变量数据流跟踪与GJB安全子集检测相结合，从安全缺陷检测及数据流异常检测两个角度挖掘代码的安全隐患，增强代码缺陷的挖掘能力。

此外，采用的控制流提取模型还增添了对 《MIRA C＋＋：2008》的支持，将代码安全缺陷检测扩展到过程间、模块间。

3 数据流异常分析

通过控制流提取模型获取控制流图，从而得到代码的可能执行路径，实现对数据变量的跟踪，检测数据流异常。

3.1 数据流异常检测状态机

数据流异常可分为过程内、过程间以及模块间数据流异常。与控制流异常相比，数据流异常更为常见，由数据流异常导致的错误要占到错误总数的15%以上［5］。文献［9］指出使用数据流分析方法可以精确地分析程序，检测程序信息流安全，并且宽容性更大。文献 ［5］使用有穷自动机对过程内的一般变量进行数据流检测，在一定程度上提高了过程内数据流异常审查效率。文章提出控制流提取模型，基于该模型获取代码可能执行路径，并使用有穷状态机对变量数据流进行跟踪。

指针变量具有特殊性，可定义为空指针，同时与有效指针状态所能进行的转化不同，不能进行正常的引用及删除。当引用指向空地址单元的指针时，会产生严重的空指针引用故障［10］。同时，数组访问越界、悬空指针访问等安全隐患通常也是黑客利用的手段［11］。文章在文献 ［5］状态机的基础上，将指针单独划出，将变量类型C分为指针型变量P以及一般型变量G，解决空指针状态跟踪问题。

定义5 文章引用Mealy状态机的形式定义［5］M＝（Q，Σ，Δ，δ，λ，qs），其中，Mealy机的状态集合Q＝｛＜q，c＞｜q∈S，c∈C｝，S＝｛qs，qn，qd，qr，qk，E｝，C＝｛P，G｝。其中，qs为被跟踪变量的首次出现，qn表示将指针变量赋值为空，qd为定义或赋值后的状态，qr为引用或解引用后的状态，qk表示释放变量空间后的状态，E为数据流异常状态。输入字母表Σ＝｛d，r，k，n｝，d代表变量定义，r变量引用，k清除变量，n设置空指针。状态转移函数δ：（Q，Σ）→Q。输出函数λ：（Q，Σ）→Δ，输出字母表Δ＝｛E，R｝，R表示在某一检测点非E的任何状态，即暂时正确状态。错误状态集ES＝｛＜q，c＞｜q∈S－｛R｝，c∈C｝，错误状态为稳定状态，即产生错误后不能进入其他状态。

定义6 基于上文定义5中的Mealy状态机，定义数据流异常，定义检测主体集合M＝｛a1，a2，…，an｝，a∈Q，a为检测主体，检测变量。客体集合N＝｛n1，n2，…，nn｝，n∈Σ。因此变量的生存序列（状态输出布尔值序列）为L＝｛λ｛a，n1｝，λ｛a，n2｝，…λ｛a，nn｝｝。将数据流异常定义为L∩｛E｝≠Φ。即在变量的生存序列中出现不合法行为，正是对数据流检测的重点。

3.2 数据流异常检测状态机

状态迁移表示变量当前状态与类型的笛卡尔乘积到下一状态的转化，依据文献［5］中对状态变迁的描述，将变量分为一般变量及指针变量，具体如下：

根据变量的状态集合及变迁条件可得Mealy机的状态迁移图如图5和图6所示。

4 构建系统框架原型

系统通过对源代码文件进行词法、语法分析获得控制流提取模型，基于该模型，设立两个主线程，分别用来对代码进行安全子集检测和数据流异常检测，并将检测结果以异常报表的形式输出，系统设计原型如图7所示。

图7 系统结构框架模型

5 相关实验

为验证所提方法，修改文献 ［6］中静态检测工具，自行设计面向对象语言的检测系统CPP－CSV。引入控制流切片模型，同时结合数据流异常检测算法对linux－0.11内核kernel目录下的3个常用文件signal.c，panic.c，printk.c进行检测，其中，signal.c主要负责对信号进行判断，在系统调用等方面作用巨大。panic.c中包含一些处理系统运行故障的函数，如Panic（）等。printk.c包含一些内核态输出函数，广泛用于嵌入式开发中。

表1 实验结果数据

实验结果分析：通过实验得出如下分析结果，对3个Linux内核文件进行检测，共检测出缺陷总数为38类161处，其中控制流相关缺陷为23类66处，数据定义类相关缺陷为12类84处，变量数据流异常为3类11处。

从图8中的统计结果可以看出，程序中控制流缺陷种类较多，情况复杂，并不集中的表现为几类缺陷。数据定义类缺陷具有类型集中，出现频率高的特点，例如，在signal.c文件中仅6类数据定义类缺陷就出现了高达54次，给程序带来了严重的安全隐患。图8中可看出，数据流异常缺陷出现频率和种类均比前两类缺陷低，但部分数据流异常检测在不进行跟踪的前提下难以实现，如空指针引用等。这3个文件的数据流异常多表现为变量定义后未使用，并直接结束（kill）。此外，未定义便引用的情况，虽然少见但危险性极高、难以检测。

控制流相关缺陷及数据定义类相关缺陷均为违反安全子集的情况，为不可忽略的安全隐患。变量数据流异常为Mealy机检测出来的安全隐患，如signal.c文件中有7处对变量定义，但未使用就退出了，导致资源的浪费，使得程序晦涩难懂。由于系统仍处于开发阶段，部分算法需要完善，难免带来一些检测的误报漏报，通过人工分析对系统的误报漏报进行修正，共发现系统漏报误报总数为3类5处。如表1所示，3个文件的检测准确率分别为97.4%、90.0%、97.3%；实验结果分析见表2。

图8 实验结果

表2 实验结果分析

实验结果的分析表明提出的方法具有可行性，保留了原有安全子集的检测能力，同时提供变量的跟踪能力。所提方法可有效解决变量跟踪问题，检测代码中隐含的安全缺陷，在提高代码安全性、可靠性等方面有着重要作用。

6 结束语

文章提出一种控制流提取模型，基于该模型可以方便构造程序控制流图，获取程序可能执行路径，解决了常见的基于抽象语法树获取控制流图难度大、扩展性差的缺点；在该模型的基础上获取控制流切片，同时增添对面向对象语言及过程间调用的支持，在利用安全子集对代码进行控制流规范检测的同时，使对代码数据流跟踪成为可能，从而弥补了安全子集不能分析变量数据流的缺陷，解决了过程间、模块间数据流异常难以分析的问题；此外，还提出了一种控制流化简方法，采用控制流切片与剪枝手段减少控制流信息数组中元素数量，并使用Mealy机的方式对数据流进行分类跟踪，解决了空指针跟踪问题，提高异常检测能力。利用该方法对实际Linux内核文件进行检测，取得了良好的效果，检测准确率达94.9%。

［1］XIAO Qing，GONG Yunzhan，YANG Zhaohong，et al.Path sensitive static defect detecting method ［J］.Journal of Software，2010，21（2）：210－217.［肖庆，官云战，杨朝红，等.一种路径敏感的静态缺陷检测方法 ［J］.软件学报，2010，21（2）：210－217.］

［2］SEN K，Agha G.CUTE：A concolic unit testing engine for C［C］.Proceedings of the 13th ACM SIGSOFT Symposium on Foundations of Software Engineering Held Jointly With 10th European Software Engineering Conference.Lisbon：ACM Press，2005：263－272.

［3］Gulwani S，Srivastava S，Venkatesan R.Program analysis constraint solving ［C］.Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation.Tucson，Arizona，2008：281－292.

［4］Froihofer L，Glos G，Osrael J，et al.Overview and evaluation of constraint validation approaches in Java ［C］.Minneapolis，MN，USA：Proceedings of the 29th International Conference on Software Engineering，2007：313－322.

［5］BIAN Lei，LIU Chao，JIN Maozhong.A method for intra—procedural data flow anomaly auto－detection facing to inspection［J］.Journal of Nanjing University（Natural Sciences），2010，46（1）：71－76.［卞磊，刘超，金茂忠.一种面向审查的过程内数据流异常自动检测方法 ［J］.南京大学学报，2010，46（1）：71－76.］

［6］ZHOU Kuanjiu，ZHENG Hongbo，LAI Xiaochen，et al.Research on static analysis method for software security based on XML ［J］.Computer Engineering and Applications，2010，46（28）：64－69.［周宽久，郑红波，赖晓晨，等.基于XML的软件安全静态检测方法研究 ［J］.计算机工程与应用，2009，46（28）：64－69.］

［7］CHEN Zhongxiang，ZHAN Jinyu，HAO Zongbo.Method for static function call analysis with control flow ［J］.Computer Engineering，2011，37（9）：47－50. ［陈忠湘，詹瑾瑜，郝宗波.带控制流的静态函数调用分析方法 ［J］.计算机工程，2011，37（9）：47－50.］

［8］ZHAO Yunshan，GONG Yunzhan，LIU Li，et al.Improving the efficiency and accuracy of path－sensitive defect detecting ［J］.Chinese Journal of Computers，2011，34（6）：1110－1111. ［赵云山，官云战，刘莉，等.提高路径敏感缺陷检测方法的效率及精度研究 ［J］.计算机学报，2011，34（6）：1100－1111.］

［9］HUANG Haijun，CHEN Yiyun.Data flow analysis for checking information flow security of programs ［J］.Journal of Chinese Computer Systems，2007，28（1）：102－106.［黄海军，陈意云.用数据流分析方法检查程序信息流安全 ［J］.小型微型计算机系统，2007，28（1）：102－106.］

［10］ZHANG Wei，LU Qingling，WAN Lin，et al.Research on faults model and testing method of null pointer dereference ［J］.Computer Engineering and Applications，2006，42（4）：71－73.［张威，卢庆龄，万琳，等.空指针引用故障模型与测试方法研究 ［J］.计算机工程与应用，2006，42（4）：71－73.］

［11］CHEN Yiyun，HUA Baojian，GE Lin，et al.A pointer logic for safety verification of pointer programs ［J］.Chinese Journal of Computers，2008，31（3）：372－380. ［陈意云，华保健，葛琳，等.一种用于指针程序安全性证明的指针逻辑［J］.计算机学报，2008，31（3）：372－380.］