程序分析简介

程序分析的目的是什么

对计算机程序进行自动化的处理,以确认或发现其特性,比如性能、正确性、安全性等. 其结果可用于编译优化、提供警告信息等,比如被分析程序在某处可能出现指针为空、数组下标越界的情形等.

被分析的对象

被分析的程序可以是源代码(各种语言),也可以是是二进制可执行代码(各种指令集),也可以是中间代码(LLVM IR, VEX IR).

欲获取的程序性质

根据分析目的不同,非常多样.大致可分为性能/正确性/安全性.

如何评价程序分析技术

不仅要看其分析对象的规模、复杂度,分析过程的效率,还要看其对用户的要求,发现缺陷的严重程度,以及误报率、漏报率等.

有哪些程序分析技术

总体上分为动态和静态.所谓的静态分析,是指对程序代码进行自动化的扫描、分析,而不必运行程序;与静态分析相对应的是动态分析技术,其利用程序运行过程中的动态信息,分析其行为和特性. 以下几种都是静态分析技术.

抽象解释

基于抽象解释来设计程序分析,本质上是通过对程序语义进行不同程度的抽象,以在分析精度和计算效率之间取得权衡.由于分析过程赋予了源程序一种抽象语义,所以分析器就变成了一种在抽象语义上的解释器,这也是名称"抽象解释"的由来. 抽象解释的典型应用案例是,Astrée 成功应用于空客 A340(约 13.2 万行 C 代码)、 A380(约 35 万行 C 代码)等系列飞机飞行控制软件的自动分析并实现了分析的零误报.

数据流分析

通过分析程序状态信息在控制流图中的传播来计算每个静态程序点(语句)在运行时可能出现的状态.可视为抽象解释的一个特例,其计算的状态信息(抽象域)局限于有限高度的格. 主要应用在编译器中,其分析结果可用于编译优化.

符号执行

使用符号化输入代替实际输入以模拟执行(不实际执行)被分析程序,程序中的操作被转化为相应的符号表达式操作.在遇到条件语句时,程序的执行也相应地分叉以探索每个分支,分支条件则被加入到当前路径的路径条件(path condition)中.通过调用 SAT/ SMT 求解器,对路径条件的可满足性进行求解来加以判断. 典型的应用案例是微软公司把自己开发的二进制动态符号执行工具 SAGE 用于 Win 7 的测试,发现了文件模糊测试中 1/3 的 缺陷;2016 年 8 月,在美国 DARPA 举办的网络空间安全竞赛(CGC)中,最终排名前三的参赛队伍全 部使用了符号执行技术,用于自动发现并利用二进制程序中的漏洞.

基于机器学习的程序分析

随着近年来通用计算设备能力的提高,海量的程序执行数据被存储和管理;研究者采用机器学习、统计分析等系列技术提升现有的程序分析能力.

待补充…

Reference

• 张健 等:程序分析研究进展