以性质代替逐个具体状态
抽象解释是研究程序语义如何被可靠近似的理论框架,常用于静态分析。它不是把程序换一种自然语言解释,也不等于用解释器执行几个测试输入,而是选择一种能计算的状态描述,在其中推导程序可能具有的性质。Patrick Cousot与Radhia Cousot的1977年论文以格结构和固定点组织了这一思路。
例如,只关心整数变量是否为正时,可以用符号描述替代具体数值;若需要检查数组下标范围,则可用区间。把可能取值集合{1,3}抽象成区间[1,3],保留了上下界,却把实际上未出现的2也包括进来。这种多包含一些可能性的表示,说明抽象通常不是无损压缩。
可靠近似与误报
在常见的前向安全分析中,抽象状态应覆盖所有具体可达状态,抽象运算也须覆盖对应具体运算的结果。例如,若x位于[1,3],执行x加2后用[3,5]描述,就没有漏掉任何原区间可能产生的结果。具体到机器整数时,还必须采用该语言的溢出语义,不能不加说明地套用无限精度整数规则。
如果整个过近似结果与错误状态不相交,就可证明所建模范围内没有这种错误。反过来,两者相交未必意味着真有可执行的错误路径,可能只是丢失相关性造成误报。通过漏掉真实行为来减少告警,会破坏这种安全证明的可靠性;可靠分析的取舍通常是精度与成本,而不是任意交换误报和漏报。
循环与固定点计算
循环的执行次数可能事先未知,分析器不能只沿源码走一遍。它把初始状态与循环体产生的新状态反复合并,寻找一个再次执行转移仍被自身覆盖的不变描述。固定点观点把这类程序分析组织成方程或约束求解,也使不同分析方法能够放进共同的数学框架。
抽象域并不一定有限。区间端点可无限增长,直接迭代可能出现[0,0]、[0,1]、[0,2]等永不稳定的序列。加宽通过保守外推使计算更快稳定,例如在适当规则下放宽不断增长的上界;它保留覆盖关系,但可能牺牲精度。之后可用收窄恢复部分信息,不过不能保证得到最精确的可达状态集。
参考:[2]
选择适合问题的抽象域
单独记录x、y的区间可能丢失两者关系;关系型抽象域则可以保留某些线性不等式。区间、同余、八边形和多面体等描述各有表达能力与计算成本。采用更强的域或组合多个域,可能减少误报,却也会增加运算和存储负担,因而必须围绕要证明的性质选择。
抽象解释可以支持编译器优化所需的数据流分析、类型分析和安全验证,但“分析成功”只针对所采用语义、环境假设及目标性质。一般程序的非平凡行为存在不可判定性,有限资源下的自动分析不能同时承诺完全精确并适用于所有程序。得到保守而有用的答案,正是这一框架的实际目标。