Journal of software软件学报Vol.30,No.1, January2019 ·基于简化的分析:这个方案的思路是针对环形依赖导致的大模块上的分析通过标准的编译技术(如 partial evaluation)进行化简提高分析速度每个模块上的分析程序可以被当成是一个函数,然后,把这 些函数看成是标准程序之后就可以应用普通的程序分析进行化简了; ·最坏情况分析:每个模块分别分析,对于该模块所依赖的其他模块作最坏情况假设.这样的分析会导致 不精确,并且在多数情况下严重不精确; ·符号化关系型分析:把未知的信息做成符号化信息,然后把程序分析转变成符号化分析所有与符号化 相关的部分不进行计算 Smaragdakis等人提出了针对所有流不敏感指针分析的代码库预处理技术,属于基于简化的分析该工作 发现:当代码中存在符合图代码模式时,将模式中的冗余语句删除,进而避免冗余运算,加速代码分析 Rountev和 yder2提出了另一种代码库的简化方式,对库的摘要就是把库里面所有的赋值语句提取出来这个摘要本身 只是省掉了语法分析的时间然后在摘要上进行了两个优化 a)对于连续赋值,比如a=b,c=a,去掉中间变量,替换成c=b b)去掉与客户端无关的赋值语句 这两个优化能省掉4%69%的时间该方法仅支持上下文不敏感且流不敏感的分析 Rountev等人3提出的构件级别分析( (component-level analysis)对代码库的IFDS/DE框架进行了摘要分 析该方法采用 Sharir和 Pnueli提出的函数型分析方法,为过程内的数据流和过程间的部分数据流建立了摘 要对于过程间边相关的未知量,即虚函数调用( virtual function)和回调点( callback site),该方法在计算过程中不 予考虑该方法只考虑了函数中的局部变量 tubEroid在 FlowDroid的基础上采用了构件级别分析对库进行 了自动分析,支持多层字段敏感性无需手动编写摘要 Tang等人提出了条件可达性解决了传统摘要无法描述的回调函数问题具体而言该工作考虑了过程 间的数据依赖分析当代码库存在回调函数时,部分信息缺失导致已有方法难以为代码库建立有效的摘要.为了 处理回调函数带来的影响该工作提出了基于树邻接语言的可达性的摘要分析技术注意到包含回调函数信息 的可达性关系(称为“条件可达性关系”)可用于加速用户代码的分析为描述条件可达性关系该工作引入了原 本用于描述自然语言语法的形式语言一一树-邻接语言提出了树邻接语言的可达性分析技术树邻接语言可 性扩展了表达两点间可达关系的传统上下文无关语言可达性,具有表达4个点之间的可达关系的能力,从 更自然地描述了上述条件可达性关系实验结果表明:建立基于树-邻接语言的可达性摘要可以在合理的时间内 完成该技术所建立的摘要可以使得对用户代码分析的效率平均提高约8倍在后续工作中,ang等人进一步 将该方法扩展到了 Dyck-CFL可达性分析上该方法通过直接在较为通用的CFL可达性分析过程中引入带 条件边,使得大量基于CFL可达性的分析就可以直接支持条件摘要同时,该方法引入桥接边来避免条件组合爆 炸的问题通过这些处理,该方法避免了原有的Dyck-CFL分析中摘要不完整和分析效率不高的问题实验结果 表明,其分析速度相比树-邻接语言进一步提升了3倍多 由于模块含有大量的未知量,建立考虑所有情况的摘要在许多分析任务中非常困难所以,一些工作通过动 态程序分析或训练的方式建立了部分摘要 Palepu等人例提出了加速程序分析速度的动态依赖摘要技术 ynamic dependence summary),提前创建软件库的摘要用来快速创建程序切片尽管得到的是不充分的摘要, 导致生成的程序切片并不保证完全正确,然而在程序测试的实践中能够找到大部分的错误 Kulkarni等人采 用跨程序的训练办法为代码库建立不完整的摘要,以提高客户代码的分析速度该方法基于 Datalog语言,有效 地对中间计算过程进行剪枝并将剪枝结果记录于摘要中同时该方法还对 Datalog语言进行改造,使得利用摘 要进行分析时可以跳过中间计算过程该方法保证正确性的方式是人工编写时间复杂度较低的规则判断训练 得到的摘要是否能够保证正确:如果不能保证正确性,则不采用摘要来进行计算 上述工作都是针对整个代码库进行摘要分析当精度要求较高时分析完整的代码库比较困难部分工作只 对单个函数进行分析 Yorsh等人提出的框架可以为函数建立精确而简练的函数摘要在不同上下文环境中 采用函数摘要与重新分析函数所得到的最终结果相同,从而保证精确性框架中采用有限显式输入输出表来表86 Journal of Software 软件学报 Vol.30, No.1, January 2019  基于简化的分析:这个方案的思路是针对环形依赖导致的大模块上的分析通过标准的编译技术(如 partial evaluation)进行化简,提高分析速度.每个模块上的分析程序可以被当成是一个函数,然后,把这 些函数看成是标准程序之后就可以应用普通的程序分析进行化简了;  最坏情况分析:每个模块分别分析,对于该模块所依赖的其他模块作最坏情况假设.这样的分析会导致 不精确,并且在多数情况下严重不精确;  符号化关系型分析:把未知的信息做成符号化信息,然后把程序分析转变成符号化分析.所有与符号化 相关的部分不进行计算. Smaragdakis 等人[81]提出了针对所有流不敏感指针分析的代码库预处理技术,属于基于简化的分析.该工作 发现:当代码中存在符合图代码模式时,将模式中的冗余语句删除,进而避免冗余运算,加速代码分析.Rountev 和 Ryder[82]提出了另一种代码库的简化方式,对库的摘要就是把库里面所有的赋值语句提取出来.这个摘要本身 只是省掉了语法分析的时间.然后在摘要上进行了两个优化. a) 对于连续赋值,比如 a=b;c=a;去掉中间变量,替换成 c=b; b) 去掉与客户端无关的赋值语句. 这两个优化能省掉 4%~69%的时间.该方法仅支持上下文不敏感且流不敏感的分析. Rountev 等人[83,84]提出的构件级别分析(component-level analysis)对代码库的 IFDS/IDE 框架进行了摘要分 析.该方法采用 Sharir 和 Pnueli[85]提出的函数型分析方法,为过程内的数据流和过程间的部分数据流建立了摘 要.对于过程间边相关的未知量,即虚函数调用(virtual function)和回调点(callback site),该方法在计算过程中不 予考虑.该方法只考虑了函数中的局部变量.StubDroid[86]在 FlowDroid 的基础上采用了构件级别分析对库进行 了自动分析,支持多层字段敏感性,无需手动编写摘要. Tang 等人[87]提出了条件可达性,解决了传统摘要无法描述的回调函数问题.具体而言,该工作考虑了过程 间的数据依赖分析.当代码库存在回调函数时,部分信息缺失导致已有方法难以为代码库建立有效的摘要.为了 处理回调函数带来的影响,该工作提出了基于树-邻接语言的可达性的摘要分析技术.注意到包含回调函数信息 的可达性关系(称为“条件可达性关系”)可用于加速用户代码的分析.为描述条件可达性关系,该工作引入了原 本用于描述自然语言语法的形式语言——树-邻接语言,提出了树-邻接语言的可达性分析技术.树-邻接语言可 达性扩展了表达两点间可达关系的传统上下文无关语言可达性,具有表达 4 个点之间的可达关系的能力,从而 更自然地描述了上述条件可达性关系.实验结果表明:建立基于树-邻接语言的可达性摘要可以在合理的时间内 完成,该技术所建立的摘要可以使得对用户代码分析的效率平均提高约 8 倍.在后续工作中[88],Tang 等人进一步 将该方法扩展到了 Dyck-CFL 可达性分析上.该方法通过直接在较为通用的 CFL 可达性分析过程[67]中引入带 条件边,使得大量基于 CFL 可达性的分析就可以直接支持条件摘要.同时,该方法引入桥接边来避免条件组合爆 炸的问题.通过这些处理,该方法避免了原有的 Dyck-CFL 分析中摘要不完整和分析效率不高的问题.实验结果 表明,其分析速度相比树-邻接语言进一步提升了 3 倍多. 由于模块含有大量的未知量,建立考虑所有情况的摘要在许多分析任务中非常困难.所以,一些工作通过动 态程序分析或训练的方式建立了部分摘要.Palepu 等人[89]提出了加速程序分析速度的动态依赖摘要技术 (dynamic dependence summary),提前创建软件库的摘要,用来快速创建程序切片.尽管得到的是不充分的摘要, 导致生成的程序切片并不保证完全正确,然而在程序测试的实践中能够找到大部分的错误.Kulkarni 等人[90]采 用跨程序的训练办法为代码库建立不完整的摘要,以提高客户代码的分析速度.该方法基于 Datalog 语言,有效 地对中间计算过程进行剪枝,并将剪枝结果记录于摘要中.同时,该方法还对 Datalog 语言进行改造,使得利用摘 要进行分析时可以跳过中间计算过程.该方法保证正确性的方式是人工编写时间复杂度较低的规则,判断训练 得到的摘要是否能够保证正确:如果不能保证正确性,则不采用摘要来进行计算. 上述工作都是针对整个代码库进行摘要分析.当精度要求较高时,分析完整的代码库比较困难.部分工作只 对单个函数进行分析.Yorsh 等人[91]提出的框架可以为函数建立精确而简练的函数摘要.在不同上下文环境中, 采用函数摘要与重新分析函数所得到的最终结果相同,从而保证精确性.框架中采用有限显式输入输出表来表