一种基于符号化函数摘要的静态分析方法及系统

摘要

本发明公开了一种基于符号化函数摘要的静态分析方法，该方法包括：利用RSTVL模型，描述当前函数的控制流图的节点的变量的存储状态；确定函数的当前节点为非最后节点且当前节点存在函数调用时，将被当前函数调用的函数的函数摘要进行实例化，并更新当前函数中受函数调用影响的变量；确定函数的当前节点为最后节点且确定当前函数具有函数返回值时，获得所述函数返回值的符号表达式，查找出存储状态发生变化的变量，并获取存储状态发生变化的变量的符号表达式；将所述函数返回值的符号表达式与存储状态发生变化的变量中的外部变量的符号表达式添加到当前函数的函数摘要中；同时，本发明还公开了基于符号化函数摘要的静态分析系统。利用本发明实施例的技术方案，可有效提高静态分析的精度效率。

说明书

技术领域

本发明涉及到静态分析技术，具体涉及到基于符号化函数摘要的静态分析 方法及系统。

背景技术

通过对软件程序进行测试可以发现程序自身的不足与缺陷。其中，软件测 试方法包括：静态分析及动态分析方法。

静态分析方法也称为静态测试，指的是不实际运行被测软件，而是通过对 源程序的扫描发现可能导致程序的结构异常、控制流异常及数据流异常等情况。 由此可见，对程序进行静态测试是保证软件质量的一个重要环节。同时，由于 静态分析方法具有成本低、实现简单、可覆盖所有路径等优势而备受青睐。

分析精确度与分析效率是评价静态分析方法的两个重要指标。目前的过程 间静态分析方法包括：过程内联、记录函数调用串、函数摘要等；其中，基于 函数摘要的静态分析方法能够实现对程序上下文的敏感分析，但是由于程序中 通常含有较多的多级指针变量、复合变量等复杂的数据类型变量，导致了分析 精度与分析效率均不够高。

发明内容

有鉴于此，本发明实施例的主要目的在于提供一种基于符号化函数摘要的 静态分析方法及系统，能够提高静态分析的精度及效率。

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

本发明实施例提供了一种基于符号化函数摘要的静态分析方法，所述方法 包括：

利用基于区域的符号化三值逻辑RSTVL模型，描述当前函数的控制流图 的节点的变量的存储状态；

依据所述控制流图，确定所述函数的当前节点为非最后节点且所述当前节 点存在函数调用时，将被当前函数调用的函数的函数摘要进行实例化，并更新 所述RSTVL模型中受函数调用影响的变量；

确定所述函数的当前节点为最后节点且确定所述当前节点具有函数返回值 时，获取所述函数返回值的符号表达式；查找出存储状态发生变化的变量，并 获取存储状态发生变化的变量的符号表达式；将所述函数返回值的符号表达式 与存储状态发生变化的变量中的外部变量的符号表达式添加到当前函数的函数 摘要中。

上述方案中，所述利用基于区域的符号化三值逻辑RSTVL模型，描述当 前函数的控制流图的节点的变量的存储状态，包括：

对所述当前函数的参数及所述当前函数使用的全局变量生成扩充变量；

利用所述RSTVL模型，描述所述当前函数的参数及所述全局变量分别占 用的内存区域、分别对应的符号表达式、以及各自的取值区间；

将所述当前函数的参数及所述全局变量的扩充变量分别占用的内存区域、 分别对应的符号表达式、以及各自的取值区间描述为变量的存储状态。

上述方案中，所述对当前函数的参数及所使用的全局变量生成扩充变量， 包括：

基于定义-使用链，识别出被所述当前函数使用的全局变量，所述全局变量 为复合类型时，扩充出所述全局变量的每个成员变量；全局变量为指针类型时， 扩充出所述全局变量的每一级指针变量；

所述当前函数的参数为复合类型时，扩充出所述参数的每个成员变量，所 述参数为指针类型时，扩充出所述参数的每一级指针变量。

上述方案中，在所述将被当前函数调用的函数的函数摘要进行实例化之前， 所述方法还包括：

生成所述被当前函数调用的函数的函数摘要。

上述方案中，所述生成所述被当前函数调用的函数的函数摘要，包括：

将所述被当前函数调用的函数作为被调用函数；

基于所述被调函数的RSTVL模型，获取所述被调函数的参数的符号表达 式、全局变量的符号表达式；

确定由所述被调函数指针类型的参数扩充出的变量在所述被调函数的函数 出口处及函数入口处不一致时，将所述扩充变量及其对应的符号表达式添加到 所述被调函数的函数摘要中；

确定所述全局变量的取值区间在所述被调函数的函数出口处及函数入口处 不一致时，将所述全局变量及其对应的符号表达式添加到所述被调函数的函数 摘要中；

所述被调函数存在有函数返回值时，依据所述RSTVL模型，获取所述函 数返回值的符号表达式，并将所述符号表达式添加到所述函数摘要中。

上述方案中，所述方法还包括：

对于所述被调用函数的参数、全局变量、函数返回值的符号表达式中的每 个符号，获取所述符号的取值区间；

当该取值区间类型为指针类型时，且该指针类型区间的指向集合中存在有 区域编号标识的区域是局部变量的区域时，将该区域编号替换为表示野指针的 区域编号；指针类型区间的指向集合中未存在区域编号标识的区域是局部变量 的区域时，将该指针类型区间的指向集合中的区域编号与具有该区域编号的区 域所对应的变量添加到函数摘要中；

当该取值区间类型为非指针类型时，获取所述符号对应的变量；所述符号 对应的变量为局部变量时，将所述符号与所述符号的取值区间添加到函数摘要 中；所述符号对应的变量为非局部变量时，将所述符号与所述符号对应的变量 添加到函数摘要中。

上述方案中，所述将被当前函数调用的函数的函数摘要进行实例化，包括：

基于所述当前函数在函数调用点处的上下文环境，获取所述被当前函数调 用的函数的形参与所述当前函数的实参之间的对应关系；

获得实参对应的符号表达式，并依据所述对应关系，将实参对应的符号表 达式替换形参的符号表达式中的符号。

上述方案中，所述获取所述被当前函数调用的函数的形参与所述当前函数 的实参之间的对应关系，包括：

当所述被当前函数调用的函数的形参有父变量时，获取所述父变量对应的 实参，并依据所述形参的表达式类型与所述父变量对应的实参，获取所述形参 对应的实参；

当所述被当前函数调用的函数的形参没有父变量时，依据所述当前函数与 所述被当前函数调用的函数之间的变量对应关系，确定与所述形参对应的实参。

上述方案中，所述方法还包括：

在所述RSTVL模型中，当函数返回值由符号表达式来描述时，获得符号 化表达式中的每一个符号，所述符号对应于所述当前函数的变量时，获得所述 符号对应的变量，基于形参与实参的对应关系，获得该变量对应的实参，根据 所述当前函数在调用点的上下文环境，获得该实参对应的符号表达式，用实参 对应的符号表达式替换形参的符号表达式中的符号；

所述符号对应于所述被当前函数调用的函数的局部变量生成的符号，从所 述被当前函数调用的函数的函数摘要中获取所述符号对应的取值区间，该取值 区间为指针类型区间时，基于所述函数摘要对指针类型区间的指向集合进行实 例化。

上述方案中，所述方法还包括：

当所述当前函数的函数返回值由取值区间标识，且当所述取值区间为指针 类型区间时，对该指针类型区间的指向集合进行实例化。

本发明实施例还提供了一种基于符号化函数摘要的静态分析系统，所述系 统包括：

描述单元，用于利用基于区域的符号化三值逻辑RSTVL模型，描述当前 函数的控制流图的节点的变量的存储状态；

第一实例化单元，用于依据所述控制流图，确定所述函数的当前节点为当 前函数的非最后节点且所述当前节点存在函数调用，将被当前函数调用的函数 的函数摘要进行实例化，并更新所述RSTVL模型中受函数调用影响的变量；

第二实例化单元，用于所述函数的当前节点为当前函数的最后节点且确定 所述当前节点具有函数返回值时，获取所述函数返回值的符号表达式，查找出 存储状态发生变化的变量，并获取存储状态发生变化的变量的符号表达式；将 所述函数返回值的符号表达式与存储状态发生变化的变量中的外部变量的符号 表达式添加到当前函数的函数摘要中。

上述方案中，所述系统还包括：

生成单元，用于生成所述被当前函数调用的函数的函数摘要。

上述方案中，所述生成单元，还用于：

将所述被当前函数调用的函数作为被调函数；

基于所述被调函数的RSTVL模型，获取所述被调函数的参数的符号表达 式、全局变量的符号表达式；

确定由所述被调函数指针类型的参数扩充出的变量的存储状态在所述被调 函数的函数出口处及函数入口处不一致时，将所述扩充变量及其对应的符号表 达式添加到所述被调函数的函数摘要中；

确定所述全局变量的取值区间在所述被调函数的函数出口处及函数入口处 不一致时，将所述全局变量及其对应的符号表达式添加到所述被调函数的函数 摘要中；

所述被调函数存在有函数返回值时，依据所述RSTVL模型，获取所述函 数返回值的符号表达式，并将所述符号表达式添加到所述函数摘要中。

本发明实施例提供了一种基于符号化函数摘要的静态分析方法及系统，利 用基于区域的符号化三值逻辑（RSTVL，Region-based Symbolic Three Value  Logic）模型，描述当前函数的控制流图的节点的变量的存储状态；确定所述函 数的当前节点为当前函数的非最后节点且所述当前节点存在函数调用时，将被 当前函数调用的函数的函数摘要进行实例化，并更新当前函数中受函数调用影 响的所述变量；确定所述函数的当前节点为当前函数的最后节点且确定所述当 前函数具有函数返回值时，获得所述函数返回值的符号表达式，查找出存储状 态发生变化的变量，并获取存储状态发生变化的变量的符号表达式；将所述函 数返回值的符号表达式与存储状态发生变化的变量中的外部变量的符号表达式 添加到当前函数的函数摘要中。利用本发明实施例的技术方案，可有效提高静 态分析的精度与效率。

附图说明

图1为本发明实施例的基于符号化函数摘要的静态分析方法的实现流程示 意图；

图2为本发明实施例的基于符号化函数摘要的静态分析方法的一具体实现 流程示意图；

图3为本发明实施例的外部变量生成扩充变量的实现流程示意图；

图4为本发明实施例的对函数摘要进行实例化的实现流程示意图；

图5为本发明实施例的获取函数摘要中每个形参及其扩充变量分别对应的 实参的实现流程示意图；

图6为本发明实施例的将获取到的父变量按照父子关系排序形成父变量集 合的实现流程示意图；

图7为本发明实施例的根据形参的表达式类型及该形参的父变量对应的实 参获得该形参对应的实参的实现流程示意图；

图8为本发明实施例的更新受函数调用的副作用影响的变量的实现流程示 意图；

图9为本发明实施例的计算函数返回值的实现流程示意图；

图10为本发明实施例的计算函数副作用的实现流程示意图；

图11为本发明实施例的将符号表达式的相关辅助信息添加到函数摘要的 实现流程示意图；

图12为本发明实施例的基于符号化函数摘要的静态分析系统的组成结构 示意图。

具体实施方式

本发明实施例提供了一种基于符号化函数摘要的静态分析方法，如图1所 示，所述方法包括：

步骤10：利用RSTVL模型，描述当前函数的控制流图的节点的变量的存 储状态；

本发明实施例中，用RSTVL的四元组模型来描述变量的存储状态，具体 请参见后续技术方案的说明。

步骤11：确定所述函数的当前节点为当前函数的非最后节点且所述当前节 点存在函数调用时，将被当前函数调用的函数的函数摘要进行实例化，并更新 当前函数中受函数调用影响的所述变量。

这里，对于受函数调用影响的变量可以视为受函数调用副作用影响的变量。

步骤12：确定所述函数的当前节点为当前函数的最后节点且确定所述当前 函数具有函数返回值时，获得所述函数返回值的符号表达式，查找出存储状态 发生变化的变量，并获取存储状态发生变化的变量的符号表达式；将所述函数 返回值的符号表达式与存储状态发生变化的变量中的外部变量的符号表达式添 加到当前函数的函数摘要中。

下面结合图2～图11对本发明实施例的技术方案进行进一步的说明。

这里，程序文件中将记载有至少一个函数，依据实际情况，每个函数在程 序文件中都将可以作为主调函数，也可能作为被调函数；所以，本发明实施例 提出的上述方法适用于程序文件中记载的所有函数。

如图2为本发明实施例的基于符号化函数摘要的静态分析方法的一具体实 现流程示意图，如图2所示：

步骤A：在当前函数的入口处，对当前函数的参数、使用的全局变量生成 扩充变量，并初始化上述变量；

本发明实施例中，将函数的变量划分为外部变量与局部变量；其中，所述 外部变量包括：全局变量与函数参数。初始化过程为：为基本类型的变量生成 符号及Region；为非基本类型的变量创建Region。

步骤B：在当前函数的控制流图中选取当前节点；判断所述当前节点是否 为当前函数的最后一个节点，如果是继续处理步骤H；否则，继续处理步骤C；

步骤C：判断当前节点是否存在函数调用，如果是继续处理步骤D，否则 执行步骤G。

步骤D：获得被调函数的函数摘要，继续处理步骤E；

本发明实施例中，称被当前函数调用的函数为被调函数；称当前函数为主 调函数。

步骤E：依据所述当前函数调用点的上下文环境，对所述被调函数的函数 摘要进行实例化，继续执行步骤F。

步骤F：对于函数摘要中的受函数调用的副作用影响的变量进行更新。

步骤G：利用RSTVL模型，对当前节点的变量的进行描述；继续执行步 骤B。

本发明实施例中，用RSTVL的四元组模型来描述程序中的每个变量及变 量的取值，该四元组模型为<Var，Region，S_Exp，Domain>；其中：元素Var表 示程序中的一个变量；该变量包括有顶级变量和复合类型变量的成员变量； Region表示为该变量分配的抽象内存区域，由区域编号来标识；S_Exp表示与该 变量有关的符号表达式；Domain表示该变量的取值区间；其中，在变量为指针 类型变量时，该变量的取值区间也称为该变量的指向集合，该指向集合由该变 量可能指向的其它变量的区域编号的集合构成。

简言之，利用RSTVL模型，描述参数及全局变量占用的内存区域、所对 应的符号表达式以及取值区间；描述参数的扩充变量、全局变量的扩充变量占 用的内存区域，所对应的符号表达式以及取值区间。

步骤H：判断当前函数是否具有函数返回值，如果是继续处理步骤I；否则， 继续处理步骤J；

步骤I：获取当前函数的函数返回值的符号化表达式，并将所述符号表达式 添加到当前函数的函数摘要中，继续执行步骤J；

步骤J：在当前函数的退出节点获取当前函数受函数调用的副作用影响的 参数与全局变量，并将该参数与全局变量及其对应的符号表达式添加到当前函 数的函数摘要中，当前处理流程结束。

图3为步骤A中为外部变量生成扩充变量的实现流程示意图；如图3所示：

步骤A.1：获取当前函数的全部全局变量，并添加到外部变量列表中；

步骤A.2：逐一提取添加到外部变量列表中的全局变量，判断是否还有未 被提取的全局变量，如果有提取该未被提取的全局变量执行步骤A.3；否则执 行步骤A.5；

步骤A.3：基于定义-使用链，识别全局变量是否被当前函数所使用，如果 识别出被当前函数所使用执行步骤A.4；否则执行步骤A.2；

步骤A.4：为该全局变量生成扩充变量，并将该全局变量与其生成的扩充 变量添加到外部变量列表中，执行步骤A.2；

步骤A.5：获得当前函数的所有形参，并添加到外部变量列表中；

步骤A.6：逐一提取添加到外部变量列表中的形参，判断是否还有未被提 取的形参，如果有，则提取该未被提取的形参执行步骤A.7；否则，执行步骤 A.8；

步骤A.7：为该形参生成扩充变量，并将该形参与生成的扩充变量添加到 外部变量列表中，继续执行步骤A.6，直到所有形参被提取完；

步骤A.8：判断外部变量列表中是否还有未被初始化的外部变量，如果判 断为有则提取出该未被初始化的外部变量并执行步骤A.9；否则，执行步骤 A.12；

步骤A.9：判断该外部变量是否是基本类型的变量，如果是，则执行步骤 A.10；否则，执行步骤A.11；

步骤A.10：为外部变量创建一个符号，继续进行步骤A.11；

步骤A.11：为外部变量创建抽象区域Region，并建立外部变量与其直接父 变量的关联关系；继续执行步骤A.8，直至所有外部变量均被初始化，之后， 执行步骤A.12。

这里，建立的直接关系为：建立外部变量与其直接父变量的关系。

步骤A.12：外部变量初始化结束。

图4为本发明实施例步骤E中对被调函数的函数摘要进行实例化的实现流 程示意图，如图4所示：

步骤E.1：获取被调函数的函数摘要中每个形参及其扩充变量分别对应的 实参；

步骤E.2：获取被调函数的函数摘要中的所有符号化表达式，并添加到符 号化表达式列表中；

步骤E.3：逐一提取添加到符号化表达式列表中符号化表达式，判断是否 还有未被实例化的符号化表达式，提取出该未被实例化的符号化表达式继续执 行步骤E.4；否则，执行步骤E.10；

步骤E.4：逐一提取该符号表达式中的所有符号，继续执行步骤E.5；

步骤E.5：判断在该符号表达式中是否还有未被实例化的符号，如果有继 续执行步骤E.6；否则继续执行步骤E.3；

步骤E.6：提取符号表达式中未被实例化的符号，继续执行步骤E.7；

步骤E.7：判断该未被实例化的符号在函数摘要中是否有其对应的变量， 如果有执行步骤E.9；否则，执行步骤E.8；

步骤E.8：从函数摘要中查找该符号对应的区间，如果查找到的取值区间 为指针类型的取值区间，则对取值区间的指向集合进行实例化，并将实例化后 的取值区间添加到程序调用点的符号区间集合中；继续执行步骤E.5；

步骤E.9：在被调函数的函数摘要中，查找该符号所对应的变量，以及查 找该变量对应的实参，根据程序调用点的上下文环境，获取实参对应的符号表 达式，并用实参对应的符号表达式替换被实例化的符号表达式中的该符号；继 续执行步骤E.5；

步骤E.10：被调函数的函数摘要实例化过程结束。

图5为步骤E.1中获取被调函数的函数摘要中每个形参及其扩充变量分别 对应的实参的实现流程图；步骤E.1也可以看成是形参映射实参的过程。

如图5所示：

步骤E.1.1：从被调函数的函数摘要中获得所有形参及其扩充变量，并添加 到形参列表；

这里，所述形参包括顶级形参。

步骤E.1.2：逐一提取添加到形参列表中的形参，判断是否还有未被提取的 形参；如果有提取该未被提取的形参执行步骤E.1.3；否则，执行步骤E.1.11；

步骤E.1.3：获取该形参对应的直接父变量及间接父变量，并将获取到的父 变量按照父子关系排序形成父变量集合，继续执行步骤E.1.4；

步骤E.1.4：逐一提取父变量集合中的形参变量，并判断父变量集合中是否 还有未被提取的形参，如果有提取该形参继续执行步骤E.1.5；否则执行步骤 E.1.2；

步骤E.1.5：判断该形参是否已是获取到了实参的变量，如果是，则执行步 骤E.1.6；否则，执行步骤E.1.4；

步骤E.1.6：判断该形参变量是否有父变量，如果有，则执行步骤E.1.7； 否则，执行步骤E.1.9；

步骤E.1.7：从形参实参映射集合中获得该形参的父变量所对应的实参，继 续执行步骤E.1.8；

步骤E.1.8：根据该形参的表达式类型及该父变量对应的实参的类型，获得 该形参对应的实参；

步骤E.1.9：；依据当前函数与被调函数之间的变量对应关系，获得与该形 参对应的实参，继续执行步骤E.1.10；

步骤E.1.10：将该形参对应的实参添加到形参实参映射集合中，继续执行 步骤E.1.4；

步骤E.1.11：形参映射实参的处理结束。

图6为步骤E.1.3中将获取到的父变量按照父子关系排序形成父变量集合 的实现流程示意图，如图6所示：

步骤E.1.3.1：提取形参列表中的一个形参变量作为当前形参变量；

步骤E.1.3.2：判断当前形参变量是否形如*.exp，如果是，执行步骤E.1.3.6； 否则，执行步骤E.1.3.3；

步骤E.1.3.3：判断当前形参变量是否形如exp.f，如果是，执行步骤E.1.3.6； 否则，执行步骤E.1.3.4；

步骤E.1.3.4：判断当前形参变量是否形如exp[i]，如果是，执行步骤E.1.3.6； 否则，执行步骤E.1.3.5；

步骤E.1.3.5：判断当前形参变量是否形如（exp），如果是，执行步骤E.1.3.6； 否则，执行步骤E.1.3.7；

步骤E.1.3.6：将名为exp的变量添加到父变量集合，并将exp作为当前形 参变量，继续执行步骤E.1.3.2；

步骤E.1.3.7：对父变量集合中的变量按照父子关系排序，继续执行步骤 E.1.3.8；

步骤E.1.3.8：获取父变量集合处理结束。

图7为步骤E.1.8中根据形参的表达式类型及该形参的父变量对应的实参 获得该形参对应的实参的实现流程示意图，如图7所示：

步骤E.1.8.1：提取形参列表中的一个形参变量作为当前形参变量；

步骤E.1.8.2：判断当前形参变量是否形如*.exp，如果是，执行步骤E.1.8.3； 否则，执行步骤E.1.8.4；

步骤E.1.8.3：基于公式得到当前形参变量的抽象区域 Region，执行步骤E.1.8.10；

步骤E.1.8.4：判断当前形参变量是否形如exp.f，如果是，执行步骤E.1.8.5； 否则，执行步骤E.1.8.6；

步骤E.1.8.5：基于公式得到当前形参变量的抽象区 域Region，执行步骤E.1.8.10；

步骤E.1.8.6：判断当前形参变量是否形如exp[i]，如果是，执行步骤E.1.8.7； 否则，执行步骤E.1.8.8；

步骤E.1.8.7：基于公式得到当前形参变量的抽象区域 Region，执行步骤E.1.8.10；

步骤E.1.8.8：判断当前形参变量是否形如（exp），如果是，执行步骤E.1.8.9； 否则，执行步骤E.1.8.11；

步骤E.1.8.9：基于公式R^l[[(e)]]=R^l[[e]]得到当前形参变量的抽象区域 Region，执行步骤E.1.8.10；

步骤E.1.8.10：得到当前形参变量的抽象区域Region所对应的变量；

步骤E.1.8.11：处理结束。

这里，RSTVL模型描述的抽象存储的信息间关联可表示为一个四元组 σ=(σ_r,σ_s,σ_f,σ_d)，其中：

σ_r:V→R,表示可寻址表达式与抽象区域的关系,是一个多对多的关联,一 个可寻址表达式可能对应多个抽象区域,一个抽象区域也可能描述多个可寻址 表达式的抽象存储；

σ_s:R→S_Exp，表示抽象区域与符号表达式映射；

σ_f:S_Exp→S，表示符号表达式与符号的关系,是一个多对多的关联,一个符 号表达式由若干个符号通过数学运算构成；

σ_d:S→D，表示符号与抽象区间的映射,每个符号都有一个区间；

对可寻址表达式的各种操作,都首先需要获得所对应的抽象区域。定义 R^l[[e]]表示在程序点l上，抽象存储ρ中，可寻址表达式e对应的区域集合。

下面给出获得各种类型的可寻址表达式对应的抽象区域的策略：

$R^l\left[\right[v\left]\right]={\rho }_v^l\left(v\right)$

$R^l\left[\right[e.f\left]\right]=\underset{r\in R^l\left[e\right]}{\cup }{\rho }_f^l(r,f)$

$R^l\left[\right[e\left[i\right]\left]\right]=\underset{r\in R^l\left[e\right]}{\cup }{\rho }_f^l(r,i)$

$R^l\left[\right[*e\left]\right]=\underset{r\in R^l\left[e\right]}{\cup }{\rho }_r^l\left(r\right)$

R^l[[(e)]]=R^l[[e]]

$R^l\left[\right[e->f\left]\right]=\underset{r\in R^l\left[e\right]}{\cup }\left(\underset{r^{\prime }\in {\rho }_r^l\left(r\right)}{\cup }{\rho }_f^l(r^{\prime },f)\right)$

其中，对每个程序点l，集合R^l模拟在l处能够被访问的区域集合。集合S^l表示在l程序点处使用的符号集合。

本发明实施例中，对每个程序点l均有一个抽象存储：其 中：

映射一个内存对象到一个抽象区域；

表示抽象区域间的指向关系；

映射一个复合结构变量的成员到一个抽象区域。

图8为步骤F中更新受函数调用的副作用影响的变量的实现流程示意图； 如图8所示：

步骤F.1：获取形参对应的实参的区域集合；

步骤F.2：判断该区域集合中是否只有一个区域，如果是，执行步骤F.3； 否则，执行步骤F.4；

步骤F.3：用实例化后的符号表达式替换区域中对应的符号表达式，实现强 更新，执行步骤F.8；

步骤F.4：判断区域集合中是否还有未被更新的区域，如果有，执行步骤 F.5；否则，执行步骤F.8；

步骤F.5：从区域集合中取一个未被更新的区域作为当前区域，继续执行步 骤F.6；

步骤F.6：基于程序调用点的上下文环境，计算出实例化后的符号表达式的 区间（第一区间），并计算该区间（第一区间）的符号表达式所对应的区间（第 二区间），对第一区间与第二区间求并得到一个新区间；

步骤F.7：为当前区域对应的变量创建一个新的符号，该新的符号对应的区 间为求并后的所述新区间，并将所述新的符号与所述新的区间添加到程序点的 符号区间集合中；为所述新的符号生成一个新的符号表达式，用该新的符号表 达式替换当前区域中的符号表达式，实现弱更新操作，继续执行步骤F.4；

步骤F.8：当前处理流程结束。

图9为步骤I中获取当前函数的函数返回值的符号化表达式，并将所述符 号表达式添加到当前函数的函数摘要中的实现流程示意图；图9也可以视为计 算函数返回值的过程；具体的，如图9所示：

步骤I.1：从控制流图中通过获得函数退出节点的所有前驱节点进而得到所 有函数返回语句的节点；

步骤I.2：逐一提取函数返回语句的节点，判断是否还有未被提取的函数返 回语句的节点，如果有，则执行步骤I.3；否则，执行步骤I.6；

步骤I.3：将该未被提取的函数返回语句的节点作为当前节点，继续执行步 骤I.4；

步骤I.4：根据当前函数的返回节点的程序状态，基于RSTVL模型得到当 前节点的符号表达式，继续执行步骤I.4；

步骤I.5：将所述符号表达式作为对当前节点的函数返回值的描述值，添加 到当前函数的函数摘要中；

步骤I.6：计算函数返回值结束。

图10为步骤J获取受函数调用的副作用影响的参数与全局变量，并将该参 数与全局变量及其对应的符号表达式添加到函数摘要中的实现流程示意图；此 外，图10也可以视为计算函数副作用的过程；具体的，如图10所示：

步骤J.1：获取当前函数的所有外部变量；

该外部变量包括：形参、全局变量及其的扩充变量；

步骤J.2：逐一提取外部变量，判断是否有被未提取的外部变量，如果有， 执行步骤J.3；否则，执行步骤J.8；

步骤J.3：将该未被提取的外部变量作为待分析变量；

步骤J.4：获得该待分析变量在函数退出节点的符号表达式；

步骤J.5：判断该待分析变量在函数退出节点的符号表达式与在函数起始节 点的符号表达式是否一致，如果是，执行步骤J.2；否则，执行步骤J.6；

步骤J.6：将该待分析变量与其在函数退出节点的符号表达式添加到函数摘 要中；

步骤J.7：将该符号表达式的相关辅助信息添加到函数摘要中；

这里，所述符号表达式的相关辅助信息包括：符号表达式对应的抽象区域， 该抽象区域所对应的变量等。

步骤J.8：计算函数副作用结束。

图11为步骤J.7将符号表达式的相关辅助信息添加到函数摘要的实现流程 示意图；如图11所示：

步骤J.7.1：基于当前函数的RSTVL模型，获得当前函数的符号表达式中 的所有符号；

步骤J.7.2：逐一提取符号表达式中的符号，判断是否还有未提取的符号表 达式；如果是，执行步骤J.7.3；否则执行步骤J.7.17；

步骤J.7.3：将未提取的符号作为待处理符号；

步骤J.7.4：判断函数摘要中是否已有该待处理符号，如果有执行步骤J.7.2； 否则执行步骤J.7.5；

步骤J.7.5：获得该符号对应的变量，继续执行步骤J.7.6；

步骤J.7.6：判断该符号对应的变量是否是外部变量，如果是，执行步骤J.7.7； 否则执行步骤J.7.8；

步骤J.7.7：将该符号与其对应的变量添加到函数摘要中，继续执行步骤 J.7.2；

步骤J.7.8：获得该符号对应的变量的取值区间，继续执行步骤J.7.9；

步骤J.7.9：判断该取值区间是否是指针类型取值区间，如果是，执行步骤 J.7.11；否则，执行步骤J.7.10；

步骤J.7.10：将该符号与其对应的取值区间添加到函数摘要中，执行步骤 J.7.2；

步骤J.7.11：获得该指针类型取值区间的指向集合，继续执行步骤J.7.12；

步骤J.7.12：逐一提取该指向集合中的区域编号，判断是否还有未提取的 区域编号时，如果是执行步骤J.7.13；否则执行步骤J.7.10；

步骤J.7.13：获取该未被提取的区域编号对应的区域所描述的变量（简言 之该区域编号对应的变量）；

步骤J.7.14：判断该区域编号对应的变量是否是外部变量，如果是，执行 步骤J.7.15；否则，执行步骤J.7.16；

步骤J.7.15：将该区域编号与该区域编号所对应的变量添加到函数摘要中；

步骤J.7.16：将该区域编号替换为野指针“wild”；

步骤J.7.17：当前处理结束。

下面结合一段代码，以RSFVL模型为例对本发明实施例的技术方案进行 进一步的说明。该代码中主调函数为函数g、被调函数为函数f，具体如下：

在上述代码中，左侧部分的S1～S16代表该段代码的行数；由此可见，代 码的S9～S16行为函数g的执行语句；S5～S8为函数f的执行语句；其中，主调 函数g在S15行调用被调函数f。

顺序执行上述代码，在执行到被调函数f时，对函数f进行过程内分析先 定义函数f的函数摘要；此时的函数f的函数摘要为空，需要随着对函数f的过 程内分析填充函数f的函数摘要。其中，所述函数摘要记录有：变量及其对应 的符号表达式之间的对应关系、和变量及其对应的Region之间的对应关系、和 变量的符号表达式及其对应的Domain之间的对应关系、和用符号表达式表示 的函数返回值。

在函数f入口处即代码的S5位置，获取到函数f所使用的变量为参数pst 及p；并分别为参数pst及p生成各自的扩充变量；因为参数pst是指针类型的 结构体变量，所以为参数pst生成的扩充变量包括有：*pst、(*pst).m、(*pst).n、 *(*pst).n；参数p为指针类型变量，所以为参数p生成的扩充变量为*p。在上述 参数pst、参数p及其各自的扩充变量中，pst、(*pst).m、(*pst).n、*(*pst).n、p、 *p为基本类型的变量，则为这些基本类型的变量生成符号及创建各自的 Region，如(*pst).n生成的符号为*(*pst).n_1213、区域编号为1213。而扩充变量 *pst不是基本类型的变量，无需为*pst生成符号，只需为*pst创建Region即可。 这里，*pst是(*pst).n的直接父变量、pst是*pst的直接父变量，建立子变量与直 接父变量的关系。通过为每一个外部变量创建Region来为这些外部变量分配抽 象内存区域。

由于S6、S7行存在有如上所示的程序语句，所以，在函数f的出口处，外 部变量(*pst).m与(*pst).n的取值均发生了变化；其中，由于在函数入口处时为 *(*pst).n生成的符号表达式为*(*pst).n_1213，所以将*(*pst).n与符号表达式 *(*pst).n_1213之间的对应关系添加到函数f的函数摘要中；

在执行S6行的语句之后，将*(*pst).n_1213+1作为外部变量(*pst).m的符号 表达式；并将外部变量(*pst).m及其符号表达式*(*pst).n_1213+1之间的对应关 系添加到函数f的函数摘要中。由于在函数入口处为外部变量*p创建的Region 的区域编号为ubm_3，所以将*p与其对应的区域编号ubm_3添加到函数f的函 数摘要中。至此，函数f的函数摘要生成，对函数f的过程内分析结束。

执行到有关主调函数g的程序语句，用RSTVL模型描述控制流图上主调 函数g的每个程序点上的程序状态即通过对主调函数g的程序语句的执行，逐 步获取主调函数f的所有变量、每个变量所对应的抽象内存区域（由区域编号 来表征）、与变量有关的符号表达式、以及每个变量的取值区间。

在S15行存在有对函数f的调用，获得函数f的函数摘要，之后需要对函 数f函数摘要中的变量(*pst).m、*p、*(*pst).n获得与其对应的实参变量，过程 如下：

判断*(*pst).n是形如*.exp的变量，将(*pst).n添加到父变量集合；并判断 (*pst).n是形如exp.f的变量，将*pst添加到父变量集合；判断*pst是形如*.exp 的变量，将pst添加到父变量集合；由此可得到*(*pst).n的父变量集合为{pst、 *pst、(*pst).n}；与上述处理过程类似，可得到(*pst).m的父变量集合为{pst、*pst}。 由S15行可知pst对应着实参ps，根据主调函数g中S15行之前的程序点的上 下文环境又可知*pst对应着实参s，判断实参s对应的形参*pst是形如*.exp的 变量，那么依据公式得到*pst所对应的区域的区域编号为 s_03，s_03指向s.n,实参，在代码的S14行可知，s.n,指向了实参a，所以*(*pst).n 对应着实参a；与上述处理过程类似可得到(*pst).m对应着实参s.m；

因为*p的父变量列表为{p}，p对应着实参&b，根据主调函数g中S15行 之前的程序点的上下文环境可知*p对应着实参b；至此完成了变量(*pst).m、*p、 *(*pst).n与其对应的实参变量的处理过程。

在找出函数f的函数摘要中的变量所对应的实参变量后，找出受函数调用 副作用影响的变量，并在主调函数g的RSTVL模型中更新受副作用影响的变 量，过程如下：

函数摘要中的(*pst).m所对应的符号表达式为*(*pst).n_1213+1， *(*pst).n_1213是为*(*pst).n生成的符号表达式，而*(*pst).n对应着主调函数g 中的实参a，实参a的符号表达式为0（实参a的取值为0），则用0替换符号表 达式*(*pst).n_1213+1中的*(*pst).n_1213，得到0+1，即得到1。而(*pst).m对 应着实参s.m，即主调函数f经过对被调函数f的调用之后，参数s.m的值受到 了函数调用的副作用影响被修改为1，则更新主调函数g的RSTVL模型中的参 数s.m的取值区间Domain。

对于函数摘要中的(*pst).n，所对应的指针类型区间的指向集合为{ubm_3}， 在函数f的函数摘要中，ubm_3为*p所分配的区域编号，而*p对应着主调函数 g中的实参b；在主调函数g的S14执行后，b的区域编号为bm_2，函数摘要f 中(*pst).n的指向集合{ubm_3}被替换为实参b的区域编号{bm_2}，而(*pst).n 对应着主调函数中的实参s.n，函数f经过对被调函数f的调用之后，参数s.n 受函数调用的副作用影响指向了实参b，则更新主调函数g的RSTVL参数s.n 的指向集合。

同时，本发明实施例还记载了一种基于符号化函数摘要的静态分析系统， 如图12所示，所述系统包括：

描述单元21，用于利用RSTVL模型，描述当前函数的控制流图的节点的 变量的存储状态；

第一实例化单元22，用于依据所述控制流图，确定所述函数的当前节点为 当前函数的非最后节点且所述当前节点存在函数调用，将被当前函数调用的函 数的函数摘要进行实例化，并更新所述RSTVL模型中受函数调用影响的变量；

第二实例化单元23，用于所述函数的当前节点为当前函数的最后节点且确 定所述当前节点具有函数返回值时，获取所述函数返回值的符号表达式，查找 出存储状态发生变化的变量，并获取存储状态发生变化的变量的符号表达式； 将所述函数返回值的符号表达式与存储状态发生变化的外部变量的符号表达式 添加到当前函数的函数摘要中。

所述系统还包括：生成单元24，用于生成所述被当前函数调用的函数的函 数摘要。

所述生成单元24，具体用于：

将所述被当前函数调用的函数作为被调函数；

基于所述被调函数的RSTVL模型，获取所述被调函数的参数的符号表达 式、全局变量的符号表达式；

确定由所述被调函数指针类型的参数扩充出的变量的存储状态在所述被调 函数的函数出口处及函数入口处不一致时，将所述扩充变量及其对应的符号表 达式添加到所述被调函数的函数摘要中；

确定所述全局变量的取值区间在所述被调函数的函数出口处及函数入口处 不一致时，将所述全局变量及其对应的符号表达式添加到所述被调函数的函数 摘要中；

如果所述被调函数存在有函数返回值，依据所述RSTVL模型，获取所述 函数返回值的符号表达式，并将所述符号表达式添加到所述函数摘要中。

本领域技术人员应当理解，图12中所示的基于符号化函数摘要的静态分析 系统的各处理单元的实现功能可参照前述基于符号化函数摘要的静态分析方法 的相关描述而理解。本领域技术人员应当理解，图12所示的基于符号化函数摘 要的静态分析系统中各处理单元的功能可通过运行于处理器上的程序而实现， 也可通过具体的逻辑电路而实现。

本发明实施例提供的上述方法与系统，与现有技术相比，可有效提高静态 分析的分析精确度与分析效率，此外，还具有以下优点：

1）本发明实施例应用RSTVL模型来描述变量，应用此模型既可表示变量 的取值，又可表示变量间的别名关系、复合数据类型变量与其成员间的层次关 系、还可表示基本类型变量的取值的逻辑关联关系；也就是说，此模型可表示 程序运行时的内存对象间可能存在的左值与右值间关联、左值间关联、右值间 关联的所有可能关联；由此可见，本发明实施例RSTVL模型可准确全面的描 述变量自身的关联关系及变量间的关联关系。

2）本发明实施例采用符号化的函数摘要，其中变量的取值用符号表达式描 述，对于符号表达式中的符号，将其对应的变量分为局部变量与外部变量两种 情况；对于局部变量的符号，将该符号与函数退出节点的取值区间添加到函数 摘要中；对于外部变量的符号，包括：参数或者全局变量，将该符号与其对应 的外部变量添加到函数摘要中供函数摘要实例化时使用；如果函数摘要中的取 值区间为指针类型取值区间，则将该指针类型取值区间的指向集合中的区域编 号与其对应的变量添加到函数摘要中；由此可见，本发明实施例采用的函数摘 要，全面记录了与函数摘要有关的信息。

3）因为函数摘要全面的封装了被调用函数的信息，基于RSTVL模型获取 函数摘要中的变量与在程序调用点处的变量之间的对应关系，从而将函数摘要 中的符号表达式、指针类型取值区间进行实例化。由此可见，采用本发明实施 例的技术方案，可有效提高函数摘要实例化的准确性。

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