Journal of software软件学报Vol.30,No.1, January2019 得了显著的可扩展性提升效果0,3 利用矩阵分解等在线分解优化策略来对抽象域操作的算法进行优化.基于该思想,最近, Singh等 人B23对常用的八边形抽象域、多面体抽象域的实现进行了优化优化后分析的性能取得了显著的 提升性能提升最大的达140多倍在此基础上, Singh等人还提出了一种通用的基于分解的优化策 ,能够在不改变基抽象域的基础上自动实现基于分解的优化从而无需人工重新实现基抽象域, 并基于这一思想实现了开源抽象域库 ELINA这种基于在线分解的方法不会造成精度损失 最近, Singh等人还提出了一种基于强化学习来加速静态程序分析的方法在每次迭代过程中,利用强化 学习来决策选择哪个转换子以在精度和不动点迭代收敛速度之间进行权衡在抽象域编码实现上 Becchi等 人最近改进了未必封闭多面体域(支持严格不等式约束)的双重描述法在表示中避免了松弛变量的引入,极 大地提高了分析效率并开发了多面体域的开源实现 PPLite 此外,将抽象解释应用到特定类型程序或特定性质的分析验证方面的研究也取得了不少进展,主要的关注 点包括复杂数据结构自动分析的支持、不同谱系目标程序的支持、活性性质分析的支持在复杂数据结构的自 分析方面最近的研究重点关注针对数组内容的精确分析、混杂数据结构的建模3、数值与形态混合的 程序分析围、关系型形态分析1在支持不同谱系目标程序方面最近的研究重点关注多线程程序的自动分 析1、中断驱动型程序的自动分析4、概率程序的分析:4、操作系统代码的安全和功能性分析13846 近年来在抽象解释领域出现了一些新的用来分析时序性质和终止性的方法下析在目标性质支持方面 未来,抽象解释技术将进一步在新的架构、语言、应用等实际需求驱动下不断发展值得关注的方向包括 对弱内存模型的分析验证、神经网络的分析与验证巧、大数据处理相关错误的分析、 Python程序的 自动分析等与约束求解、自动推理、人工智能等基础支撑技术的紧密结合,将是抽象解释后续的研究趋势 之一5961同时,降低误报率将依然是基于抽象解释的程序分析技术拓展实际应用的研究挑战和重点 2.2数据流分析 数据流分析通过分析程序状态信息在控制流图中的传播来计算每个静态程序点(语句)在运行时可能出现 的状态经典的数据流分析理论62用有限高度的格L来抽象表示所有可能状态的集合并对每个程序语句定 义一个单调的转移函数( transfer function),以计算其对程序状态的更新数据流分析可以是前向或后向,对应程 序状态信息在控制流图中的前向或后向传播在程序控制流图中,多个分支交汇的程序点状态为其所有前驱(或 后继,如果是后向传播)程序点状态的几表示不同执行路径下可能出现的所有程序状态 数据流分析为抽象解释的一个特例,其计算的状态信息(抽象域)局限于有限高度的格L,)数据流分析己 编译器实现中得到广泛应用常见的应用包括常数传播分析、部分冗余分析等相比于通用的抽象解释理 论,经典数据流分析的实现可以通过一个迭代计算框架来计算所有语句的输出直至不动点单调性和格的有限 高度保证了数据流分析迭代计算框架的收敛性而无需引入加宽算子编译器中的数据流分析多为过程内数据 流分析,全局过程间的分析可以使用基于摘要的方法,通过对函数自动分析摘要得以实现近年来,对数据流分 析方向的应用己不仅仅局限于编译优化,研究者们也提出了多种方法来高效实现过程间的上下文敏感的数据 流分析,主要包括如下两种方法 I) IFDS/IDE数据流分析框架 IFDS分析框架由Reps等人于1995年提出IFDS将抽象域(即数据流分析计算的状态信息)为满足分配 性的有限集合的一大类数据流分析问题转换为一个图可达问题,从而能够有效地进行上下文敏感的过程间分 析.IFDS框架基于程序过程间控制流图定义了一个超级流图( supergraph),其中,每个节点对应在一个程序点的 抽象域中的一个元素;而节点间的边表示该元素在过程间控制流图的传播对应着数据流分析中的转移函数通 过求解是否存在从程序入口到每个程序点的一个可达路径我们可以得到该程序点的状态信息基于该分析方 法的框架已经实现于开源分析系统,如Soot和wala中,并广泛用于包括 Android污点分析在内的多种应84 Journal of Software 软件学报 Vol.30, No.1, January 2019 得了显著的可扩展性提升效果[30,31];  利用矩阵分解等在线分解优化策略来对抽象域操作的算法进行优化.基于该思想,最近,Singh 等 人[32,33]对常用的八边形抽象域、多面体抽象域的实现进行了优化,优化后,分析的性能取得了显著的 提升,性能提升最大的达 140 多倍;在此基础上,Singh 等人还提出了一种通用的基于分解的优化策 略[34],能够在不改变基抽象域的基础上自动实现基于分解的优化,从而无需人工重新实现基抽象域, 并基于这一思想实现了开源抽象域库 ELINA.这种基于在线分解的方法不会造成精度损失. 最近,Singh 等人[35]还提出了一种基于强化学习来加速静态程序分析的方法,在每次迭代过程中,利用强化 学习来决策选择哪个转换子,以在精度和不动点迭代收敛速度之间进行权衡.在抽象域编码实现上,Becchi 等 人[36]最近改进了未必封闭多面体域(支持严格不等式约束)的双重描述法,在表示中避免了松弛变量的引入,极 大地提高了分析效率,并开发了多面体域的开源实现 PPLite. 此外,将抽象解释应用到特定类型程序或特定性质的分析验证方面的研究也取得了不少进展,主要的关注 点包括复杂数据结构自动分析的支持、不同谱系目标程序的支持、活性性质分析的支持.在复杂数据结构的自 动分析方面,最近的研究重点关注针对数组内容的精确分析[37]、混杂数据结构的建模[38]、数值与形态混合的 程序分析[39,40]、关系型形态分析[41].在支持不同谱系目标程序方面,最近的研究重点关注多线程程序的自动分 析[18]、中断驱动型程序的自动分析[42,43]、概率程序的分析[44,45]、操作系统代码的安全和功能性分析[38,46]、 JavaScript 等动态语言的分析[47]、二进制代码的分析[48]、Web 应用程序的安全性分析[49].在目标性质支持方面, 近年来,在抽象解释领域出现了一些新的用来分析时序性质和终止性的方法[5052]. 未来,抽象解释技术将进一步在新的架构、语言、应用等实际需求驱动下不断发展.值得关注的方向包括 对弱内存模型的分析验证[53,54]、神经网络的分析与验证[55,56]、大数据处理相关错误的分析[57]、Python 程序的 自动分析[58]等.与约束求解、自动推理、人工智能等基础支撑技术的紧密结合,将是抽象解释后续的研究趋势 之一[5961].同时,降低误报率将依然是基于抽象解释的程序分析技术拓展实际应用的研究挑战和重点. 2.2 数据流分析 数据流分析通过分析程序状态信息在控制流图中的传播来计算每个静态程序点(语句)在运行时可能出现 的状态.经典的数据流分析理论[62]用有限高度的格L,来抽象表示所有可能状态的集合,并对每个程序语句定 义一个单调的转移函数(transfer function),以计算其对程序状态的更新.数据流分析可以是前向或后向,对应程 序状态信息在控制流图中的前向或后向传播.在程序控制流图中,多个分支交汇的程序点状态为其所有前驱(或 后继,如果是后向传播)程序点状态的,表示不同执行路径下可能出现的所有程序状态. 数据流分析为抽象解释的一个特例,其计算的状态信息(抽象域)局限于有限高度的格L,.数据流分析已 经在编译器实现中得到广泛应用,常见的应用包括常数传播分析、部分冗余分析等.相比于通用的抽象解释理 论,经典数据流分析的实现可以通过一个迭代计算框架来计算所有语句的输出直至不动点.单调性和格的有限 高度保证了数据流分析迭代计算框架的收敛性,而无需引入加宽算子.编译器中的数据流分析多为过程内数据 流分析,全局过程间的分析可以使用基于摘要的方法,通过对函数自动分析摘要得以实现.近年来,对数据流分 析方向的应用已不仅仅局限于编译优化,研究者们也提出了多种方法来高效实现过程间的上下文敏感的数据 流分析,主要包括如下两种方法. 1) IFDS/IDE 数据流分析框架 IFDS 分析框架由 Reps 等人[63]于 1995 年提出.IFDS 将抽象域(即数据流分析计算的状态信息)为满足分配 性的有限集合的一大类数据流分析问题转换为一个图可达问题,从而能够有效地进行上下文敏感的过程间分 析. IFDS 框架基于程序过程间控制流图定义了一个超级流图(supergraph),其中,每个节点对应在一个程序点的 抽象域中的一个元素;而节点间的边表示该元素在过程间控制流图的传播,对应着数据流分析中的转移函数.通 过求解是否存在从程序入口到每个程序点的一个可达路径,我们可以得到该程序点的状态信息.基于该分析方 法的框架已经实现于开源分析系统,如 Soot[64]和 Wala[65]中,并广泛用于包括 Android 污点分析[66]在内的多种应