Journal of so/hare软件学报Vol.30,No., January2019 程序分析的对象既可以是源代码,也可以是二进制可执行代码对于源程序,根据其实现语言不同,可能需 要不同的分析技术比如C程序和Java程序的分析,其技术可能就不一样后者需要处理一些面向对象的结构 即使是同一种高级语言编写的程序,也可能具有不同的特性比如程序中是否有比较多的指针?是否使用并发 控制结构、通信机制?是否有大量的数值计算从规模看,被分析的程序可以是几百行的代码,也可以是几十万行 乃至于上千万行代码 2)程序性质的多样性 对不同类型的程序在不同的应用环境下,人们关注的性质也不一样以C程序为例,很多C程序会用到指 针,用于动态分配、释放内存对这样的程序,人们会关注空指针、内存泄漏等问题但对某些嵌入式系统来说, 程序中很少动态分配内存空间,却可能要处理中断另外一些C程序可能有大量的数值(浮点数)计算程序员可 能更关注其中是否存在溢出问题 13程序分析的难度及评价 由于程序语言的复杂性、程序性质的多样性自动化的程序分析往往具有相当大的难度根据Rce定理对 于程序行为的任何非平凡属性都不存在可以检查该属性的通用算法也就是说大量的程序分析问题都是不 可判定的比如,一般情况下,程序的终止性就是不可判定的也就是说,不存在一种算法,它能判断任何给定的程 序是否总能终止程序路径的可行性( path feasibility)是不可判定的如果存在输入数据使得程序沿着一条 路径执行,程序中该路径被称为是可行的( feasible)没有一种算法,它能判断程序中某条给定路径是否可行最 近 Cousot等人从抽象解释的角度形式化地证明了:从可计算性角度看,相比程序验证(只需要检查一个给定的 程序不变式是否正确)程序分析(需要综合出正确的程序不变式)是一个更难的问题具体而言:对于证明有穷域 上的程序断言,程序分析与程序验证是等价的问题但是对于无穷域上的断言程序分析比程序验证更难 鉴于程序分析的理论难度以及被分析程序的复杂度我们往往不要求对程序进行完全精确的分析这就可 能带来误报( false positive)、漏报( false negative)等问题:前者指的是报警信息指出的缺陷实际上不存在、不可 能发生;后者指的是程序中存在的某个缺陷,没有被程序分析工具所发现 对程序分析技术或工具进行评价,不仅要看其分析对象的规模、复杂度分析过程的效率还要看其对用户 的要求发现缺陷的严重程度,以及误报率、漏报率等 2程序分析方法和技术 本节主要介绍一些近期有重要进展的程序分析方法和技术,包括抽象解释、数据流分析、基于摘要的过程 间分析、符号执行、动态分析、基于机器学习的程序分析等这6项方法和技术的关系如图1所示 据流分析过程间 F执行‖动态分析 基础理论抽象解 Fig 1 Main program analysis techniques 图1主要的程序分析技术 程序分析总体可以分为静态分析和动态分析,涉及的基础理论包括抽象解释、约束求解、自动推理等而 静态分析的关键技术包括数据流分析、过程间分析、符号执行等最后近期机器学习技术被用于提升各种不 同的程序分析技术 除了这6种基本程序分析技术之外,还有一些其他广泛使用的程序分析技术也在近期有显著进展,如污点 分析、模型检验、编程规则检查等由于受篇幅所限,本文将不再对这些技术进行详述 2.1抽象解释 抽象解释是一种对程序语义进行可靠抽象(或近似)的通用理论该理论为程序分析的设计和构建提供了82 Journal of Software 软件学报 Vol.30, No.1, January 2019 程序分析的对象既可以是源代码,也可以是二进制可执行代码.对于源程序,根据其实现语言不同,可能需 要不同的分析技术.比如,C 程序和 Java 程序的分析,其技术可能就不一样:后者需要处理一些面向对象的结构. 即使是同一种高级语言编写的程序,也可能具有不同的特性.比如,程序中是否有比较多的指针?是否使用并发 控制结构、通信机制?是否有大量的数值计算.从规模看,被分析的程序可以是几百行的代码,也可以是几十万行 乃至于上千万行代码. 2) 程序性质的多样性 对不同类型的程序,在不同的应用环境下,人们关注的性质也不一样.以 C 程序为例,很多 C 程序会用到指 针,用于动态分配、释放内存.对这样的程序,人们会关注空指针、内存泄漏等问题.但对某些嵌入式系统来说, 程序中很少动态分配内存空间,却可能要处理中断.另外一些 C 程序可能有大量的数值(浮点数)计算,程序员可 能更关注其中是否存在溢出问题. 1.3 程序分析的难度及评价 由于程序语言的复杂性、程序性质的多样性,自动化的程序分析往往具有相当大的难度.根据 Rice 定理:对 于程序行为的任何非平凡属性,都不存在可以检查该属性的通用算法[3].也就是说,大量的程序分析问题都是不 可判定的.比如,一般情况下,程序的终止性就是不可判定的.也就是说,不存在一种算法,它能判断任何给定的程 序是否总能终止.程序路径的可行性(path feasibility)也是不可判定的[4].如果存在输入数据使得程序沿着一条 路径执行,程序中该路径被称为是可行的(feasible).没有一种算法,它能判断程序中某条给定路径是否可行.最 近,Cousot 等人[5]从抽象解释的角度形式化地证明了:从可计算性角度看,相比程序验证(只需要检查一个给定的 程序不变式是否正确),程序分析(需要综合出正确的程序不变式)是一个更难的问题.具体而言:对于证明有穷域 上的程序断言,程序分析与程序验证是等价的问题;但是对于无穷域上的断言,程序分析比程序验证更难. 鉴于程序分析的理论难度以及被分析程序的复杂度,我们往往不要求对程序进行完全精确的分析.这就可 能带来误报(false positive)、漏报(false negative)等问题:前者指的是报警信息指出的缺陷实际上不存在、不可 能发生;后者指的是程序中存在的某个缺陷,没有被程序分析工具所发现. 对程序分析技术或工具进行评价,不仅要看其分析对象的规模、复杂度,分析过程的效率,还要看其对用户 的要求,发现缺陷的严重程度,以及误报率、漏报率等. 2 程序分析方法和技术 本节主要介绍一些近期有重要进展的程序分析方法和技术,包括抽象解释、数据流分析、基于摘要的过程 间分析、符号执行、动态分析、基于机器学习的程序分析等.这 6 项方法和技术的关系如图 1 所示. 提升手段 基于机器学习的程序分析 关键技术 数据流分析 过程间分析 符号执行 动态分析 基础理论 抽象解释 约束求解 自动推理 静态分析 动态分析 Fig.1 Main program analysis techniques 图 1 主要的程序分析技术 程序分析总体可以分为静态分析和动态分析,涉及的基础理论包括抽象解释、约束求解、自动推理等.而 静态分析的关键技术包括数据流分析、过程间分析、符号执行等.最后,近期机器学习技术被用于提升各种不 同的程序分析技术. 除了这 6 种基本程序分析技术之外,还有一些其他广泛使用的程序分析技术也在近期有显著进展,如污点 分析、模型检验、编程规则检查[6]等,由于受篇幅所限,本文将不再对这些技术进行详述. 2.1 抽象解释 抽象解释是一种对程序语义进行可靠抽象(或近似)的通用理论[7].该理论为程序分析的设计和构建提供了