生成时序安全属性类缺陷模式相关的函数摘要信息的方法

摘要

本发明涉及一种生成时序安全属性类缺陷模式相关的函数摘要信息的方法，包括：判定被测程序中时序安全属性类的缺陷模式，并生成时序安全属性类缺陷模式的描述文件；根据所述描述文件获取所述时序安全属性类缺陷模式的有限自动状态机；根据所述有限自动状态机为所述被测程序中的函数生成函数摘要信息。本发明根据描述时序安全属性类缺陷模式的有限自动状态机为被测程序中的函数生成函数摘要信息，通过所述函数摘要信息进行软件静态测试，从而提高软件静态缺陷的检测效率。

说明书

技术领域

本发明涉及软件静态测试技术领域，尤其涉及一种生成时序安全 属性类缺陷模式相关的函数摘要信息的方法。

背景技术

静态代码缺陷分析技术通过对代码进行静态分析来推测程序运 行时的表现行为，从而发现代码中可能存在的缺陷。这类技术主要包 括抽象解释、定理证明、模型检测、符号执行和基于缺陷模式的代码 检查等。

基于模式匹配的代码缺陷查找方法主要包括如下两大步骤：首 先，对已有代码中出现过的缺陷进行总结并提炼出“缺陷模式知识”； 然后，采用静态分析的方法对受检代码进行“缺陷模式匹配”以确定 受检代码是否包含相应缺陷，并把匹配结果以缺陷检测报告的形式呈 现给用户。

在对现有的若干基于模式匹配的代码缺陷静态分析工具研究之 后，我们发现：在对C程序代码进行静态代码缺陷分析的过程中，特 别是检测时序安全属性类缺陷模式时，往往要处理复杂的函数调用关 系。传统的做法类似函数内联，在函数调用点处将被调用函数一层一 层地展开进行分析，但是这会严重地影响分析效率。

发明内容

（一）要解决的技术问题

本发明所要解决的技术问题是：如何生成时序安全属性类缺陷模 式相关的函数摘要信息，提高静态缺陷检测的分析效率。

（二）技术方案

本发明提出了一种生成时序安全属性类缺陷模式相关的函数摘 要信息的方法，包括以下步骤：

判定被测程序中时序安全属性类的缺陷模式，并生成时序安全属 性类缺陷模式的描述文件；

根据所述描述文件获取所述时序安全属性类缺陷模式的有限自 动状态机；

根据所述有限自动状态机为所述被测程序中的函数生成函数摘 要信息。

优选地，所述根据所述有限自动状态机为所述被测程序中的函数 生成函数摘要信息之后，还包括：

在所述被测程序的函数调用点实例化与所述函数对应的函数摘 要信息。

优选地，所述根据所述有限自动状态机为所述被测程序中的函数 生成函数摘要信息具体为：

根据所述有限自动状态机，采用后向数据流分析法为所述被测程 序中的函数生成对应的函数摘要信息。

优选地，所述采用后向数据流分析法为所述被测程序中的函数生 成对应的函数摘要信息具体包括：

生成所述被测程序的函数控制流图；

逆向遍历所述函数控制流图中的节点；

合并当前节点的后继节点传递来的数据流值；

更新合并后的数据流值；

对更新后的数据流值进行逻辑表达式化简，并根据预设规则删除 无效的数据流值。

优选地，所述在所述被测程序的函数调用点实例化与所述函数对 应的函数摘要信息具体包括：

将所述函数摘要信息中的型参变量替换为函数调用点处的实参 变量；

判断所述实参变量是否满足所述函数摘要信息中的约束条件；

如果满足所述约束条件，则获取所述函数摘要信息所关注的内存 对象；并根据所述约束条件实现所述内存对象的状态迁移；如果不满 足所述约束条件，则判定所述函数摘要信息在所述函数调用点不合 法，结束本次操作。

优选地，所述获取所述函数摘要信息所关注的内存对象具体包 括：

获取所述实参变量对应的指向信息；

根据所述指向信息获取所述实参变量指向的内存对象；

根据函数摘要信息内所有实参变量指向的内存对象，获取所述函 数摘要信息所关注的内存对象。

（三）有益效果

本发明公开生成时序安全属性类缺陷模式相关的函数摘要信息 的方法，根据描述时序安全属性类缺陷模式的有限自动状态机为被测 程序中的函数生成函数摘要信息，通过所述函数摘要信息进行软件静 态测试，从而提高软件静态缺陷的检测效率。

附图说明

通过参考附图会更加清楚的理解本发明的特征和优点，附图是示 意性的而不应理解为对本发明进行任何限制，在附图中：

图1是本发明生成时序安全属性类缺陷模式相关的函数摘要信息 的方法流程图；

图2是本发明中采用后向数据流分析法为被测程序中的函数生成 对应的函数摘要信息的流程图；

图3是本发明中在被测程序的函数调用点实例化与函数对应的函 数摘要信息的流程图；

图4是本发明中获取函数摘要信息所关注的内存对象的流程图。

具体实施方式

下面将结合附图对本发明的实施例进行详细描述。

本发明提出了一种生成时序安全属性类缺陷模式相关的函数摘 要信息的方法，如图1所示，包括以下步骤：

S101判定被测程序中时序安全属性类的缺陷模式，并生成时序 安全属性类缺陷模式的描述文件；

S102根据所述描述文件获取所述时序安全属性类缺陷模式的有 限自动状态机；

S103根据所述有限自动状态机为所述被测程序中的函数生成函 数摘要信息。

优选地，所述根据所述有限自动状态机为所述被测程序中的函数 生成函数摘要信息之后，还包括：

在所述被测程序的函数调用点实例化与所述函数对应的函数摘 要信息。

本发明使用一种描述时序安全类缺陷模式的语言—— SDDL-Typestate（Static Defect Description Language for Typestate）定 义时序安全属性类的缺陷模式；依据SDDL-Typestate给出的描述时 序安全属性类缺陷模式的有限自动状态机，使用后向的数据流分析方 法，为被测代码中的每一个函数生成摘要信息；静态检测时序安全属 性类缺陷时，在函数调用点实例化函数摘要信息，从而完成对摘要信 息关注的内存对象的状态迁移。

SDDL-Typestate是基于XML进行设计的，具有比较好的结构化 特征，其通过关键字和标签对XML文档赋予特定的语义信息来描述 时序安全属性类的缺陷模式，即定义描述时序安全属性类缺陷模式的 有限自动状态机FSM（Finite State Machine）。

XML Schema文件用于约束SDDL-Typestate的结构及内容，具体 如下面的Schema文件所示：

其中，<Defect>标签是SDDL-Typestate缺陷描述文件的根标签。 每一个<Defect>标签都包含一个<Description>子标签和多个<State> 子标签。

<Description>标签包含五个子标签<Name>、<Time>、 <Category>、<Language>和<Example>，分别用于描述缺陷模式的名 称、创立时间、类属、目标语言和示例代码；

<State>标签都定义了有限自动状态机（FSM）中的一个状态，以 及可能发生在这个状态上的各种状态迁移。<State>标签包含三个子标 签<Number>、<Status>和<Transition>。

<Number>标签用来给当前定义的状态都赋予了一个唯一的标 号。这样一来就可以根据标号开区分不同的状态了；

<Status>标签用来表明当前定义的状态是初始状态（init）、中间 状态（intermediate），还是错误状态（error）；

<Transition>标签用来说明当前定义的状态上可能发生的状态迁 移。它又包含两个子标签<To>和<Op>，其中前者用来指明要迁移到 的状态，而后者用来表示何种操作会引起状态迁移，这种操作一般是 调用库函数。

任取有限自动状态机FSM中的任一非初始的状态设为函数之行 结束后的状态，然后逆向遍历函数的控制流图，进行后向的数据流分 析，以求出相应的函数摘要信息。后向数据流分析的数据流值形如 <Must,Not,Formula,State>，而计算得到的函数摘要信息形如<Must, Not,Formula,State1→State2>；

在后向的数据流分析过程中，当遍历到函数控制流图中的某一节 点时，需要首先要合并由其后继节点传递来的数据流值；

在后向的数据流分析过程中，当遍历到函数控制流图中的某一节 点、完成数据流值的合并后，需要接着更新合并后的数据流值；

在后向的数据流分析过程中，当遍历到函数控制流图中的某一节 点、完成数据流值的更新后，需要进一步化简更新后的数据流值，并 排除其中无效的数据流值。

Must和Not是两个特定类型的（与缺陷模式相关的）指针变量 的集合。它们一起用来表示标识当前摘要信息所考察的内存对象，其 中Must集合中的指针变量一定指向该内存对象，而Not集合中的指 针变量一定不指向该内存对象；

Formula用于表示摘要信息成立的约束条件，其构成遵守如下的 文法规则：

Formula::=Formula+Term|Term；

Term::=CoefficientConjunct|Conjunct；

Conjunct::=ConjunctPredicate|Predicate；

Predicate::=Expression Op Expression|TRUE|FALSE；

Op::==|≠；

需要说明的是符号“+”和符号“”分别用来表示逻辑或和逻 辑与；

State1是FSM中的任一状态，而State2特别要求是FSM中的任 一非初始的状态。函数摘要信息的含义是当约束条件Formula成立时， 调用函数会使得由Must和Not标识的内存对象的状态由State1迁移 至State2。而数据流值中的State表示（在函数执行结束后内存对象 的状态为State2的条件下）函数控制流图上某一节点处内存对象所处 的状态。

Formula表达式中的系数Coefficient的取值是“1”、“0”和“1/2”， 其中“1”和“0”分别表示TRUE和FALSE，而“1/2”用以说明一 种非确定的可能。这三个值一起构成了Kleene的三值逻辑结构。

对于任意两个符号状态{must₁,not₁,formula₁,state₁}和{must₂, not₂,formula₂,state₂}，若满足如下条件：

state₁=state₂；

must₁must₂；

not₁not₂；

则合并这两个符号状态，得到合并后的符号状态为{must₁,not₁, (1/2)(formula₁+formula₂),state₁}。

在赋值语句“p:=q;”处对数据流值{must,not,formula,state}的 更新；

在库函数调用语句“f(p);”处对数据流值{must,not,formula,state} 的更新。特别地，库函数f是会引起状态迁移的某种操作；

在一般函数调用语“g(p,q,…);”处对数据流值{must,not, formula,state}的更新。特别地，函数g包含摘要信息{must_g,not_g, formula_g,state_g1→state_g2}；

在if-head处对数据流值{must,not,formula,state}的更新。

若p∈must，则用q替代p在must中的所有出现，于是更新 后的符号状态为{must[q/p],not,formula,state}；

若x∈must且x和p间存在可能内存别名关系，则一方面假 设p和x满足必然内存别名关系，用q替代x在must中的所有出现， 同时将formula更新为formula(&x=&p)；另一方面假设p和x间不 存在内存别名关系，保持must不变，同时将formula更新为 formula(&x≠&p)。于是，得到更新后的符号状态为{must[q/x],not, formula(&x=&p),state}和{must,not,formula(&x≠&p),state}。

若p∈must，则将state更新为δ(state,f)，得到更新后的符号 状态为{must,not,formula,δ(state,f)}。其中δ(state,f)表示state因为 操作f而迁移到的状态；

若p∈Not，则符号状态不会被更新;

若pmust∪Not且x∈must满足x和p间存在可能值别名 关系，则一方面假设p和x满足必然值别名关系，将state更新为 δ(state,f)；另一方面假设p和x间不存在值别名关系，生成新的符 号状态{{p},must,true,final}，同时更新原符号状态为{must,not∪ {p},formula,state}。于是，得到更新后的符号状态为{must∪{p},not, formula,δ(state,f)}、{must,not∪{p},formula,state}和{{p},must,true, δ(final,f)}。其中final表示当前假设的函数之行结束后所处的状态；

若pmust∪Not且x∈must满足x和p间存在可能值别名 关系，则除去原有符号状态外，生成新的符号状态{{p},true, δ(final,f)}。

用函数调用点处的实参变量替换摘要信息{must_g,not_g,formula_g, state_g1→state_g2}中对应的形参变量，若满足如下条件：

·state=state_g1；

·must∩not_g=

·must_g∩not=

·must∩must_g≠并设A:=must∩must_g；

则，更新后的符号状态为{must∪must_g,not∪not_g,formulaformula_g,state_g2}和{must,not∪{must_g-A},formula,state}。此外若 state_g2=final，那么除以上两个更新后的符号状态外，还会新生成符 号状态{must_g,not∪{must-A},formula_g,state_g1}；

用函数调用点处的实参变量替换摘要信息{must_g,not_g,formula_g, state_g1→state_g2}中对应的形参变量，若满足如下条件：

·state=state_g1；

·must∩not_g=

·must_g∩not=

·x∈must和y∈must_g且x和y间存在可能值别名关系

则，更新后的符号状态为{must∪must_g,not∪not_g,formulaformula_g,state_g2}和{must,not∪must_g,formula,state}。此外，如果 state_g2=final，那么除以上两个更新后的符号状态外，还会新生成符 号状态{must_g,not∪must,formula_g,state_g1}。

将formula更新为(1/2)formula，得到更新后的符号状态为 {must,not,(1/2)formula,state}。这里的系数（coefficient）乘以1/2 用以说明更新后的符号状态只是表示部分而非全部执行路径上的信 息。

待对逻辑表达式化简完成后，如果符号状态满足下列条件之一， 则称该符号状态无效：

must∩not≠

state=

formula=false；

无效的符号状态会被删除无效的符号状态。

设函数的一条摘要信息{must,not,formula,state₁→state₂}，则静 态检测时序安全属性类缺陷时，在函数调用点实例化函数摘要信息， 从而完成对摘要信息关注的内存对象的状态迁移，具体如下的步骤：

C1将摘要信息中的型参变量替换为函数调用点处的实参变量。 设替换后的must域等于{p,q}、not域等于{r}；

C2判断实参变量是否满足摘要信息中的formula约束表达式： 若满足，则继续步骤C3；否则跳转到步骤C6；

C3取得变量p、q和r对应的指向信息（指向分析得到的指向集） pt(p)、pt(q)和pt(r)，每一个变量的指向集都表示该变量（可能）指 向哪些内存对象。由集合“(pt(p)∩pt(q))-pt(r)”求得摘要信息所关注 的内存对象；

C4判断摘要信息所关注的内存对象在调用点处的状态是否等 于State₁：若是，则继续步骤C5；否则跳转到步骤C6；

C5摘要信息所关注的内存对象的状态会迁移到State₂；

C6结束。

优选地，所述根据所述有限自动状态机为所述被测程序中的函数 生成函数摘要信息具体为：

根据所述有限自动状态机，采用后向数据流分析法为所述被测程 序中的函数生成对应的函数摘要信息。

其中，采用后向数据流分析法为所述被测程序中的函数生成对应 的函数摘要信息，如图2所示，具体包括：

S201，生成所述被测程序的函数控制流图；

S202逆向遍历所述函数控制流图中的节点；

S203合并当前节点的后继节点传递来的数据流值；

S204更新合并后的数据流值；

S205对更新后的数据流值进行逻辑表达式化简，并根据预设规 则删除无效的数据流值。

后向数据流分析方法逆向遍历函数的控制流图（Control Flow  Graph，CFG），在控制流图上的每一个节点处，首先合并后继节点传 递来的数据流值，接着更新、化简这些数据流值，最后排除掉无效的 数据流值。

其中，在所述被测程序的函数调用点实例化与所述函数对应的函 数摘要信息，如图3所示，具体包括：

S301将所述函数摘要信息中的型参变量替换为函数调用点处的 实参变量；

S302判断所述实参变量是否满足所述函数摘要信息中的约束条 件；

如果满足所述约束条件，则执行步骤S303；

S303获取所述函数摘要信息所关注的内存对象；

S304根据所述约束条件实现所述内存对象的状态迁移，转步骤 S305；

如果不满足所述约束条件，判定所述函数摘要信息在所述函数调 用点不合法，则直接执行步骤S305；

S305结束本次操作。

其中，获取所述函数摘要信息所关注的内存对象，如图4所示， 具体包括：

S401获取所述实参变量对应的指向信息；

S402根据所述指向信息获取所述实参变量指向的内存对象；

S403根据函数摘要信息内所有实参变量指向的内存对象，获取所 述函数摘要信息所关注的内存对象。

本发明公开的生成时序安全属性类缺陷模式相关的函数摘要信 息的方法，根据描述时序安全属性类缺陷模式的有限自动状态机为被 测程序中的函数生成函数摘要信息，通过所述函数摘要信息进行软件 静态测试，从而提高软件静态缺陷的检测效率。

通过以上的实施方式的描述，本领域的技术人员可以清楚地了解 到本发明可以通过硬件实现，也可以借助软件加必要的通用硬件平台 的方式来实现。基于这样的理解，本发明的技术方案可以以软件产品 的形式体现出来，该软件产品可以存储在一个非易失性存储介质（可 以是CD-ROM，U盘，移动硬盘等）中，包括若干指令用以使得一台 计算机设备（可以是个人计算机，服务器，或者网络设备等）执行本 发明各个实施例所述的方法。

本领域技术人员可以理解附图只是一个优选实施例的示意图，附 图中的流程并不一定是实施本发明所必须的。

以上所述仅为本发明的实施例，并非因此限制本发明的专利范 围，凡是利用本发明说明书及附图内容所作的等效结构或等效流程变 换，或直接或间接运用在其他相关的技术领域，均同理包括在本发明 的专利保护范围内。