应用程序切片技术的静态缺陷检测方法

摘要

本发明公开一种应用程序切片技术的静态缺陷检测方法，包括：A、获取待检测缺陷模式的缺陷特征；B、根据所述的缺陷特征，计算所有分支节点的路径条件，并生成切片准则；C、按照所述的切片准则，遍历控制流图进行程序切片，对控制流图进行重构，得到已重构的控制流图；D、利用所述已重构的控制流图，应用缺陷状态迭代算法，进行缺陷模式状态机计算；E、若当前控制流图节点为非汇合节点，则将所有缺陷状态中的状态条件进行汇聚及更新操作；F、如果当前控制流图节点为汇合节点，则按照当前缺陷状态的状态条件进行状态合并。采用该方法能够在一定程度上提高缺陷检测的效率，并减少基于路径合并策略的路径敏感检测方法的误报。

说明书

技术领域

本发明涉及软件测试技术，尤其涉及一种应用程序切片技术的静态缺陷检测方法，属于路径敏感方法在静态缺陷检测中的应用。 

背景技术

软件测试是提高软件质量的重要手段，根据是否运行被测试程序，软件测试可以分为动态测试和静态测试。基于软件缺陷的静态分析方法可以针对小概率缺陷实施有效测试，受到了学术界和工业界的广泛关注。静态分析的效率是影响其能否应用于大型软件缺陷检测的关键，它与分析过程中的计算复杂度密切相关。由于静态分析需要抽象出完整的程序语义信息，该抽象语义信息往往是精确程序语义的“保守”近似，从而导致其计算量要远大于程序精确语义所表示的计算量，因此减少保守性分析时的计算量可以提高分析效率。根据Rice定理，静态分析针对程序的任何非平凡属性(例如：是否存在运行时错误)，不可能做到既是可靠的(sound)又是完备的(complete)，导致其计算结果可能会出现误报(false positive)和漏报(false negative)。大量的误报会使人对分析工具失去信心，而漏报会造成程序具有较高质量的假象，因此提高精度是完善静态分析功能的又一挑战。 

路径敏感的缺陷检测方法从控制流图头节点依次进行状态迭代，每个缺陷状态都会关联当前控制流节点的所有数据流信息，在缺陷状态迭代计算时，与缺陷无关的数据流信息会在控制流上进行传递和计算，这种无关计算势必降低缺陷检测的效率。通过增加控制流节点构造新的路径，或重构控制流图以消除不可达路径的方法，也可实现路径敏感分析，但这是一种典型的以效率换精度的方法，限制了其在大型软件缺陷检测中的应用。 

发明内容

有鉴于此，本发明的主要目的在于提供一种应用程序切片技术的静态缺陷检测方法，以提高路径敏感缺陷检测方法的效率及精度，在检测代码量较大程序时可以进一步减少分析时间并减少误报。 

为达到上述目的，本发明的技术方案是这样实现的： 

应用程序切片技术的静态缺陷检测方法，该方法包括： 

A、获取待检测缺陷模式的缺陷特征； 

B、根据所述的缺陷特征，计算分支节点的路径条件，并生成切片准则； 

C、根据所述的切片准则，遍历控制流图进行程序切片，对控制流图进行重构，得到已重构的控制流图； 

D、利用所述的已重构的控制流图，应用缺陷状态迭代算法，进行缺陷模式状态机计算； 

E、若当前控制流图节点为非汇合节点，则将所有缺陷状态中的状态条件进行汇聚及更新操作； 

F、如果当前控制流图节点为汇合节点，则按照当前缺陷状态的状态条件进行状态合并。 

其中，所述步骤A中的根据待检测缺陷模式获取其缺陷特征的过程具体为： 

A1、根据缺陷模式状态机FSM的创建条件，检测程序中是否有缺陷模式关联的变量，该缺陷相关变量即为缺陷特征DefectFeature，记为Df(FSM)。 

其中，所述步骤B中，根据步骤A计算得到的缺陷特征，遍历控制流图中的所有分支节点n，根据分支语句块Stmt(n)中是否包含缺陷特征，来确定n是否为路径条件，记为Pc(n)，该步骤B进一步包括； 

B1、按节点序遍历控制流图，查询所有出度大于2的节点，将其加入分支语句集合BranchList，其中可能包含if-else、switch条件分支语句，以及while、do-while、for等循环语句； 

B2、将B1得到的BranchList倒置，然后依次遍历其中的每个分支节点 SplitNode，查询其所包含的语句块Stmt(SplitNode)是否包含缺陷特征Df(FSM)；如果不包含则执行步骤B3，否则执行步骤B4； 

B3、当前分支语句块不包含缺陷特征信息，设置其路径条件IsPc＝false，使其在后续的程序切片时可以根据此路径条件标志快速切片掉； 

B4、当前分支语句块内包含缺陷特征信息，因此将当前分支的条件变量加入路径条件集合PCSet，同时设置IsPc()＝true； 

如果BranchList遍历完毕，则将缺陷特征Df(FSM)与路径条件集合PCSet合并，从而得到切片准则SCSet。 

其中，步骤C中根据步骤A和步骤B得到的缺陷特征及路径条件，生成切片准则，然后根据每个控制流节点的数据流信息进行程序切片：进一步包括： 

C1、按节点序遍历控制流图，获取每个控制流节点的关联变量信息RelVarSet； 

C2、，通过比较步骤B中的切片准则SCSet与当前节点的RelVarSet的包含关系进行程序切片，如果二者交集为空则执行步骤C4；否则，执行步骤C3； 

C3、当前节点的数据流信息集合RelVarSet中包含与缺陷检测或路径条件有关的数据流信息，因此不应该被切片掉，继续执行步骤C2； 

C4、当前节点的数据流信息与缺陷检测及路径条件均无关，因此应该被切片掉，即将被切片掉语句的前驱及后继相连接；切片过程中如果遇到条件分支节点，则通过步骤B计算得到的路径条件标志IsPc()来决定是否可以对整个条件分支语句块进行快速切片。 

其中，步骤E中，从控制流图头节点依次进行状态迭代，每个缺陷状态都关联了当前控制流节点的路径条件，用当前节点每个变量的抽象取值来表示状态条件；如果当前节点为顺序控制流节点：则进一步包括： 

E1、状态条件汇聚：将当前控制流节点n的所有前驱节点进行状态条件合并，得到新的状态条件作为n的初始状态条件； 

E2、状态条件更新：根据当前控制流节点n的数据流信息，更新步骤E1中计算得到的初始状态条件，并根据状态迁移条件判断是否会发生状态迁移； 如果状态迁移到Error状态，则上报一个检测点。 

其中，步骤F中如果遇到控制流汇合节点，则根据状态属性State Attribute与步骤C1得到切片准则SCSet的包含关系，决定是否进行状态合并，其进一步包括： 

F1、获取所有前驱节点的缺陷状态，如果不是相同状态，则只进行状态条件合并操作，否则执行步骤F2； 

F2、如果前驱节点的缺陷状态相同，进一步检查其状态属性Attr(State)是否包含于切片准则SCSet，如果是包含关系则不进行状态合并。 

本发明所提供的应用程序切片技术的静态缺陷检测方法，具有以下优点： 

将本发明的方法应用于软件静态测试中，实现需求驱动的缺陷检测，能够根据不同的缺陷检测目的计算程序的不同切片，从而缩小了缺陷检测的范围，提高缺陷检测效率。由于程序切片考虑程序中存在的各种依赖关系(不仅仅是数据依赖和控制依赖)，而且任何一个程序可以与一组程序切片的并集等价，检测每个切片实际就是测试了整个程序，因此基于缺陷的程序切片方法满足了静态分析方法的保守性。实验证明，应用程序切片技术后可以有效减少静态缺陷检测的时间开销，同时减少误报。 

附图说明

图1为本发明程序切片技术在缺陷检测中的应用流程示意图； 

图1a为用有向图表示的资源泄漏模式示意图； 

图1b为用有向图表示的空指针引用模式示意图； 

图2为本发明程序切片生成算法流程示意图； 

图3为本发明基于缺陷的程序切片算法流程示意图。 

具体实施方式

下面结合附图及本发明的实施例对本发明的方法作进一步详细的说明。 

现有的基于数据流分析的路径敏感检测方法考虑分支间的组合关系，可以记录控制流图上的不同路径信息，从而有效减少静态分析时的误报。精确的路径敏感分析方法会记录程序中的所有路径信息，在控制流分支较多或存在循环 时会导致路径爆炸，从而无法进行分析。 

因此，实用的路径敏感分析方法往往会采用一些折衷策略，有可能导致精度损失： 

1)不同路径上的数据流信息在控制流汇合处合并； 

2)数据流在不可达路径上进行传递。 

例如，采用迭代求精策略，每次迭代分析的结果都会更新状态合并准则，这种可调整的合并准则会减少由于关键路径合并而带来的精度损失，但迭代求精要进行重复计算，且有可能面临迭代不终止的情况；或者，采用变量的抽象取值来表示状态条件，在控制流汇合节点通过合并相同状态中的状态条件来避免路径爆炸，但该方法的状态合并策略没有区分在哪些汇合节点可以进行安全的状态合并，导致与缺陷相关的路径信息丢失从而引起误报。 

基于上述对路径敏感缺陷检测方法的分析，可以得到以下结论： 

1)控制流图节点数决定了状态迭代计算的次数； 

2)状态条件中关联数据流信息的数量决定了沿控制流进行状态迭代时的复杂度； 

3)状态合并策略影响路径敏感检测方法的精度。本发明主要关注点是如何优化这三个方面，以提高路径敏感分析方法的效率和精度。 

借鉴需求驱动程序分析方法的思想，本发明将程序切片技术应用于缺陷检测，提出一种应用程序切片技术的测试方法，该方法基于缺陷特征和路径条件建立切片准则，根据控制流节点上的数据流信息与切片准则的包含关系进行程序切片，得到的切片程序在缺陷检测时不仅切片掉了缺陷无关节点，从而减少了数据流迭代时的计算量，而且与源程序完全等价从而保证了静态分析的保守性。为了进一步减少误报，提出一种基于切片的缺陷状态合并策略，根据控制流分支节点的路径条件，对缺陷状态添加状态属性，从而有选择地对控制流汇合节点进行状态合并，以提高检测精度。 

根据是否考虑程序语句的执行次序，静态分析可以分为流敏感分析(flow sensitive)和非流敏感分析(flow insensitive)。程序的控制流图(CFG，Control Flow  Graph)即是对语句执行次序的抽象，是具有单一的、固定的入口节点和出口节点的有向图。 

定义1  控制流图：程序的控制流图可以表示为一个有向图G＝(N，E，n₀，n_f)，其中：N代表节点的集合，每个节点n_i∈N反映程序中的顺序执行语句CommonStmt、条件判断(循环)语句SelectionStmt等，与节点n_i关联的程序语句块表示为Stmt(n_i)；E∈N×N代表有向边的集合，反映程序中语句间的控制流关系，e_h和e_t分别表示有向边e的头节点和尾节点；n₀为函数的唯一入口节点，n_f为函数的唯一退出节点。 

静态缺陷检测方法关键是对缺陷模式进行定义和检测，能处理的缺陷模式种类越多则分析检测能力越强。 

定义2 缺陷模式：指程序中经常发生的缺陷(BUG)所呈现出的语法或语义特征。 

缺陷模式是对程序属性的一种描述，如果违反该属性则造成一个缺陷。例如，申请的资源在使用完后必须释放，否则造成资源泄漏缺陷(RL，Resource Leak)；数组下标的使用必须在其数组声明大小范围以内，否则会造成数组越界缺陷(OOB，Out Of Boundary)；指针在解引用之前必须确保其指向非空，否则会造成空指针引用缺陷(NPD，Null Pointer Dereference)。 

状态机是对程序语义的一种常用和易于理解的抽象表示，缺陷模式可以用缺陷模式状态机来表示。 

定义3 缺陷模式状态机：用于描述缺陷模式的有限状态机(FSM，Finite State Machine)，包括状态集合D、状态迁移集合T、及迁移条件集合Conditions，其中D＝{$start，$error}∪D_other，T：D×Conditions→D。$start和$error分别表示起始状态和错误状态，D_other表示其他中间状态的集合。 

缺陷模式状态机可以用有向图直观地表示，例如RL和NPD缺陷模式分别 可用状态机描述如下，所述资源泄漏模式如图1a所示，和空指针引用模式如图1b所示的缺陷状态机)： 

路径敏感的缺陷检测方法，从控制流图头节点依次进行状态迭代，每个状态都关联当前控制流节点的所有变量取值信息，称之为状态条件(State Condition)。我们用变量的抽象取值来表示状态条件，在数据流迭代过程中不断更新状态条件，就会导致缺陷状态发生迁移，一旦发现状态迁移到$error就表示程序中存在该类型的缺陷。 

如下所示的中代码片断(a)，对其中存在的RL缺陷进行检测，采用相同状态合并的路径敏感分析方法，其状态迁移序列如表1所示。 

(a)                                 (b)                                 (c) 

表1所述代码片段(a)的缺陷状态迁移序列 

根据表1中缺陷状态迁移序列，在L7处缺陷状态自动机迁移到$error，这是一个明显的误报。原因在于：L3之后的控制流汇合处，将真假分支中两个$start状态进行了合并，导致flag与dump的关联关系丢失。另外还可以观察到，P1之后的状态条件中都关联了i和j的抽象取值，此类数据流信息对RL缺陷检测的结果不会产生任何影响，只会增加状态迭代时的计算量。 

通过对上述示例程序的观察与分析，我们可以得到以下结论： 

1)消除与缺陷检测无关的冗余代码，可以减少控制流图节点数，从而减少状态迭代的次数； 

2)减少状态条件中与缺陷检测无关的变量，可以降低数据流传递和计算时的复杂度； 

3)对控制流汇合节点的缺陷状态合并策略进行优化，可以减少路径合并导致的精度损失。 

根据上述三方面需求，我们借鉴需求驱动分析技术的思想，提出了本发明的应用程序切片技术的静态缺陷测试方法，以提高缺陷检测效率和精度。 

需求驱动的静态分析技术从程序分析的需求出发，抽取程序语义信息，在进行分析之前降低程序的复杂度，大幅减少了分析过程中的计算量，不仅可以快速准确地复现程序缺陷，而且可以对大型程序中某些特定故障进行检测。本发明采用程序切片技术实现了需求驱动的缺陷检测方法，利用切片程序在进行缺陷检测时与源程序完全等价，同时减少了计算复杂度，提高了分析效率和精 度。 

本发明中程序切片技术是一种分析和理解程序的技术，通过对源程序中的每个兴趣点分别计算切片来达到对程序的分析和理解。程序切片的原理和方法由Mark Weiser于1979年在其博士论文中首次提出，Weiser认为程序切片与人们在调试程序时所做的智力抽象是相对应的，他定义程序P的切片S是一个可执行的程序，这个切片程序在某个功能属性上与P完全等效。根据程序分析和理解时不同的兴趣点，可以定义相应的切片准则(Slicing Criteria)，根据不同的切片准则可以“按需”地对源程序进行功能切片。正是基于这种“简化问题、缩小目标范围”的原则，程序切片技术成为提高静态分析效率的有效途径之一。 

根据路径敏感缺陷检测方法的特点，切片准则可以从缺陷特征及路径条件两个角度获得。 

定义4缺陷特征(Defect Feature)：给定缺陷模式fsm，它可以检测某一程序属性feature是否违反了程序语法或语义规则，该feature对应的程序变量即为缺陷模式fsm的缺陷特征，记为Df(fsm)。 

定义5节点关联变量(Vex Related Variable)：对于控制流图G＝(N，E，n₀，n_f)， 其中的Var即为节点n的关联变量，记为RelVar(n)。 

定义6路径条件(Path Condition)：CFG中只有分支及循环节点可以产生新的路径，因此路径条件只能在SelectionStmt语句中产生，定义节点n的路径条件Pc(n)＝{var|var∈RelVar(n)∧n∈SelectionStmt}，它包含控制流图中条件分支及循环节点关联的所有变量。 

缺陷特征可以理解为缺陷检测是否与程序中某个变量相关，例如NPD模式必然与一个指针变量相关，RL模式必然与一个资源句柄相关；路径条件则是程序中可能会产生新路径的条件分支语句所关联的变量，例如if-else、switch、while等语句块中关联的条件变量。 

通过对程序控制流的进一步观察，并非所有的路径条件都影响缺陷检测结果，如上述的程序片断(a)中P1、P2处的条件分支不会对RL的检测结果产生任 何影响，此类路径条件不应作为切片准则。另外，变量间的别名关系也会影响切片准则的生成。考虑该程序片断(c)，L2处赋值语句为a和b建立了直接别名关系，同时也为a＝0，flag＝true数据流值建立了数据依赖关系；由于b并非路径条件，如果将L1处语句切片掉会导致上述数据依赖关系丢失，有可能导致数据流迭代的断流。 

本发明通过提前进行区间运算，避免了赋值语句形成的别名关系对程序切片的影响。我们采用数值区间来表示变量的抽象取值，在程序切片前已经通过区间运算获取了a的区间信息，即使L1处切片掉也不会对缺陷检测产生影响。基于上述分析，本发明切片准则定义如下： 

SCSet＝Df(fsm)∪{Pc(n_i)|n_i∈SelectionStmt  ∧  Df(fsm)∈RelVar(n_i)}。 

算法1：切片准则生成算法： 

BranchList：程序中所有的条件分支节点 

IsPc(n)：标志当前条件分支节点n是否为路径条件 

GetBranchVexList(n)：获取当前条件分支n所在分支的所有语句块 

SkipBranchVexList(n)：如果当前条件分支n不是路径条件，则可以跳过当前分支语句块，继续在分支后续节点中遍历查找路径条件 

输入：控制流图G和缺陷模式fsm 

输出：切片准则SCSet 

上面本发明给出了基于缺陷特征的切片准则生成算法1，其主要开销是Step2中路径条件的查询，假设CFG节点数为N，分支节点数为Q，每个分支语句块的节点数为P(P＜＜N)：Step2.1对CFG节点进行遍历，将所有条件分支节点加入到BranchList列表中，复杂度为O(N)；Step2.2首先将条件分支列表BranchList逆序，然后依次遍历每个条件分支语句块GetBranchVexList()中是否包含Var，一旦当前节点关联变量包含Var则将当前路径条件Pc(n)加入到SCSet，同时标志当前路径条件IsPc()＝true；如果存在嵌套分支结构，通过判断内层分支的路径条件IsPc()，决定是否跳过内层分支语句块的分析SkipBranchVexList()，复杂度为O(Q×P)。因此，算法1的复杂度为O(N)+O(Q×P)。 

程序切片算法比较经典的有Weiser基于数据流方程的算法，Ottenstein和L.M.Ottenstein以及Horwitz的基于程序依赖图的可达性算法，以及基于系统依 赖图的上下文敏感算法等。本发明采用Weiser基于数据流方程的算法，遍历CFG节点，观察当前节点数据流集合中是否包含算法1切片准则中的相关变量，以确定该节点是否应该被切片，并根据每个节点的切片标志重构控制流图。 

算法2：程序切片算法 

SliceBranchVexList(n)：如果条件分支节点n不是路径条件，则将n所在的整个分支语句块切片掉 

Slice(n)：将n从控制流图中切片掉，将其所有前驱与后继节点相关联 

输入：控制流图G，切片准则SCSet 

输出：切片后的控制流图G′ 

算法2遍历CFG，计算每个节点关联变量与切片准则SCSet的交集，如果交集为空表示当前节点应该被切片掉Slice()。为了进一步提高算法效率，如果被切片的节点为条件分支节点，则可以利用算法1中设置的路径条件标志IsPc()，以确定能否切片掉整个分支语句块SliceBranchVexList()。切片算法Slice(n)将n的所有前驱与后继相关联，复杂度取决于n的出度与入度之和，在实际程序中为常值；SliceBranchVexList(n)直接将分支语句块的前驱及后继相关联，复杂度取决于从分支入口节点遍历至汇合节点处的节点数，即分支语句块的节点数P，因此复杂度为O(P)。整个算法的复杂度取决于for循环中CFG节点数N，因此算法2的复杂度为O(N×P)。 

应用算法1、算法2中程序切片技术后，控制流图节点数及状态条件中变量数会相应地减少，因此可以通过切片效果对效率提升情况进行粗略估计。切片效果η可以理解为切片掉节点数与原节点数的比值，η越接近1则表明切片效果越好。假定源程序中控制流节点总数为φ，切片程序中节点总数为 则切片 效果 可以粗略反映由于节点数、变量数减少而引发的效率提升情况。当然，实际的缺陷检测还受到其他因素的影响，如状态条件的计算和传递、状态迁移的判断等，因此实际的效率提升值会小于η。 

为进一步提高检测精度，本发明提出一种基于切片的缺陷状态合并策略，根据控制流分支节点的路径条件，在缺陷状态上添加状态属性(State Attribute)，从而可以根据状态属性来决定在控制流汇合节点是否需要进行状态合并。该合并策略有选择地在汇合节点进行状态合并，保存了与缺陷特征(Defect Feature)有关的路径信息从而减少误报。 

定义7状态属性(State Attribute)：给定缺陷状态S及当前CFG节点n，如果Stmt(n)∈SelectionStmt，则S的状态属性Attr(S)＝RelVar(n)。 

算法3：一种基于切片的缺陷状态合并算法 

S_T、S_F：真假分支中的缺陷状态 

StateCompute(S)：根据当前节点的数据流信息，更新S的状态条件，并判断状态迁移情况 

MergeState(S_T，S_F)：合并真假分支汇聚处的缺陷状态，同时将相同的状态条件进行合并 

输入：分支节点n及缺陷状态S 

输出：汇合节点n′处的缺陷状态S′ 

上述算法中，Step1首先计算分支节点n的路径条件Pc(n)，为初始状态S添加 状态属性，然后根据真假分支中不同的数据流值进行状态迭代StateCompute()并更新S的状态条件；状态迭代的复杂度取决于分支语句块的节点数P，因此复杂度为O(P)；Step2首先判断汇合节点是否为相同状态，状态合并前再进一步检查状态属性Attr(S)是否包含于切片准则，以确定是否需要状态合并MergeState(S_T，S_F)；状态合并实际上是对相同的状态条件进行合并，复杂度取决于执行路径上相关变量的数量，在实际程序中这是一个常值，因此算法3的复杂度为O(P)。 

通过前文对算法1、算法2和算法3复杂度的描述，本发明算法复杂度主要依赖于控制流图节点数N、条件分支数量Q及每个条件分支语句块包含的节点数P，实际程序中Q＜＜P＜＜N＜λ，λ为常量，因此算法复杂度较低。另外，算法1生成了后续算法2和算法3所用到的大部分数据，且该部分数据可以作为控制流节点的静态属性进行传递，从而进一步减少了算法2和算法3的计算量。 

以下结合附图，对本发明提出的利用程序切片技术提高静态缺陷检测系统的效率和精度方法进行解释和说明，图1为本发明程序切片技术在缺陷检测中的应用流程示意图。如图1所示，该方法包括以下步骤： 

步骤A、根据待检测缺陷fsm的关联变量，生成相应的缺陷特征Df(fsm)； 

步骤B、根据步骤A得到的缺陷特征，遍历控制流图中所有分支语句，查询与缺陷特征相关的路径条件集合PCSet，并生成切片准则SCSet； 

B1、按节点序遍历控制流图，查询所有出度大于2的节点，将其加入分支语句集合BranchList，其中可能包含if-else、switch条件分支语句，以及while、do-while、for等循环语句； 

B2、将B1得到的BranchList倒置，然后依次遍历其中的每个分支节点SplitNode，查询其所包含的语句块Stmt(SplitNode)是否包含缺陷特征Df(FSM)；如果不包含则执行步骤B3，否则执行步骤B4； 

B3、当前分支语句块不包含缺陷特征信息，设置其路径条件IsPc＝false，使其在后续的程序切片时可以根据此路径条件标志快速切片掉； 

B4、当前分支语句块内包含缺陷特征信息，因此将当前分支的条件变量加 入路径条件集合PCSet，同时设置IsPc()＝true； 

如果BranchList遍历完毕，则将缺陷特征Df(FSM)与路径条件集合PCSet合并，从而得到切片准则SCSet。 

步骤C、根据步骤A、B得到的缺陷特征及路径条件，生成切片准则，然后根据每个控制流节点的数据流信息进行程序切片的步骤如下： 

C1、按节点序遍历控制流图，获取每个控制流节点的关联变量信息RelVarSet； 

C2、，通过比较步骤B中的切片准则SCSet与当前节点的RelVarSet的包含关系进行程序切片，如果二者交集为空则执行步骤C4；否则，执行步骤C3； 

C3、当前节点的数据流信息集合RelVarSet中包含与缺陷检测或路径条件有关的数据流信息，因此不应该被切片掉，继续执行步骤C2； 

C4、当前节点的数据流信息与缺陷检测及路径条件均无关，因此应该被切片掉，即将被切片掉语句的前驱及后继相连接；切片过程中如果遇到条件分支节点，则通过步骤B计算得到的路径条件标志IsPc()来决定是否可以对整个条件分支语句块进行快速切片。 

步骤D、根据步骤C得到的切片后重构的控制流图，进行缺陷状态迭代计算，对于普通的顺序控制流节点，执行步骤E，否则执行步骤F； 

步骤E、对于控制流图中的顺序节点，对其前驱数据流信息进行汇聚，更新每个缺陷状态的状态条件，本发明用每个变量的抽象取值来表示状态条件；然后根据当前节点的数据流信息更新状态条件，根据缺陷状态迁移条件判断是否会发生状态迁移；如果发现状态迁移到Error状态，则上报一个故障检测点(Inspect Point)，否则继续进行状态迭代执行步骤D； 

E1、状态条件汇聚：将当前控制流节点n的所有前驱节点进行状态条件合并，得到新的状态条件作为n的初始状态条件； 

E2、状态条件更新：根据当前控制流节点n的数据流信息，更新E1中计算得到的初始状态条件，并根据状态迁移条件判断是否会发生状态迁移；如果状态迁移到Error状态，则上报一个检测点。 

步骤F：对于控制流图中汇合节点，为了防止路径敏感分析时的路径爆炸，需要进行缺陷状态合并操作；首先根据当前分支语句的路径条件，生成缺陷状态的状态属性(State Attribute)，在相同状态合并前检查该状态属性是否包含于步骤C中切片准则SCSet，以决定是否需要进行状态条件的合并。 

F1、获取所有前驱节点的缺陷状态，如果不是相同状态，则只进行状态条件合并操作，否则执行F2； 

F2、如果前驱节点的缺陷状态相同，进一步检查其状态属性Attr(State)是否包含于切片准则SCSet，如果是包含关系则不进行状态合并。 

下面本发明结合具体实例对本发明做进一步说明。 

对于前文中程序片断(a)，应用前文描述的程序切片方法和缺陷状态合并策略对RL模式进行检测，其简要的分析流程如下： 

得到RL缺陷模式特征：Df(RL)＝{f}； 

应用算法1，得到L4、L6处路径条件Pc(L4)＝{dump}，Pc(L6)＝{flag}，因此切片准则SCSet(RL)＝{f，dump，flag}； 

应用算法2将程序片断(a)进行切片，即可切片掉P1、P2处与RL分析无关的代码，得到程序片断(b)； 

应用算法3，(b)片断的状态迭代序列如表2。由于切片掉了P1、P2处的冗余语句，减少了状态条件中的关联变量i和j；在L4处由于 ，因此L2分支产生的两个$start状态在控制流汇合节点L4不进行状态合并；在L6处，$start状态保留了flag与dump的关联关系，不会执行真分支中的Close操作，因此不会产生误报。 

表2：应用本发明方法后上述程序(b)的状态迁移序列 

以上所述，仅为本发明的较佳实施例。下面本发明以具体的静态缺陷检测实例，来说明本发明方法在检测代码量较大程序时效率和精度提升情况： 

GCC作为Linux系统中开发C语言程序的主流编译器(请参考http://gcc.gnu.org)，通过对ANSI C标准进行语法扩展获得了更高灵活性的同时，使得其程序语义更加复杂，导致其出现软件缺陷的机率也更高，且难于检测。本发明基于上述DTS框架设计实现了路径敏感的静态缺陷检测工具DTSGCC，不仅可以检测ANSI C标准的源程序，而且可以针对Linux中GCC标准的开源工程进行检测。 

本发明使用DTSGCC1.0采用不同的分析方法对Linux中10个开源工程进行了缺陷检测对比实验，扫描的缺陷模式包括RL和NPD。这10个开源工程中，源代码量最小的Combine为1.6万行，最大的Binutils为103万行。实验所使用电脑基本配置为：Intel E2160 1.8GHz CPU、2G内存、Windows XP操作系统。实验过程中使用两种不同的分析方法，方法1：相同状态合并的路径敏感方法，方法2：本发明提出的基于程序切片的路径敏感方法。 

基于以上实验设置，对静态缺陷检测结果进行了人工确认，结果如表3所示。其中，文件数只统计后缀为*.c或*.h的源文件，源代码行数为去除了空行后的统计结果。DTSGCC并不对C源文件直接进行检测，而是通过GCC编译器对其进行预处理(包括头文件展开、条件编译执行、宏定义替换)，对得到的中间文件进行处理，因此实际测试代码量为中间文件的代码量。应用本发明程序切片方法后，控制流图节点数的变化可以反映程序切片的效果，从而可以粗略地估计效率提升情况。 

表3：对比实验结果 

(注：上表中，由于Bash、Openssl、Binutils工程代码量较大，上报IP较多，目前为止并未完成全部的误报确认，因此本发明的效率及精度提升统计结果未包含这3个工程的数据。) 

该统计结果表明，对表3中10个工程检测其NPD和RL缺陷，共检测源代码量154万行，中间文件代码量761万行，方法1用时13.52小时，共上报2228个检查点(Inspection Point，IP)，而本发明方法用时11.73小时，IP数减少为1908个，检测效率提高了13.28％，误报率降低了4.59％。 

本发明从提高路径敏感缺陷检测方法的效率和精度出发，借鉴需求驱动的程序分析思想，将程序切片技术应用于静态缺陷检测，提出一种基于缺陷的程序切片方法，切片程序在缺陷检测时与源程序完全等价，减少了状态迭代时的计算量。为了进一步减少误报，根据控制流分支节点的路径条件生成缺陷的状态属性，有选择地对控制流汇合节点进行状态合并，减少了路径合并导致的与缺陷检测相关的精度损失。实验结果表明，本发明方法在检测代码量较大程序时，可以提高13％左右的分析效率，并减少5％左右的误报。 

以上所述，仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。