什么是抽象域？

抽象域是具体程序状态集的一种简化、可计算的表示，例如变量之间的区间或关系，分析在此域中计算行为的可靠过近似。

为什么需要加宽算子？

在无限或高抽象域上，朴素的不动点迭代可能不会终止；加宽算子会故意进行过近似以强制收敛，之后收窄可以恢复部分精度。

抽象解释是一种数学理论，通过在更简单的抽象域中系统地近似程序语义，来设计可靠的静态分析。

用 PaperMind 寻找选题即将推出Find papers & topics

Tools & resources

Learn & explore

视频即将推出

抽象解释是一种程序语义可靠近似的理论，其中具体语义与可计算的抽象语义相关联，从而保证在抽象域中证明的属性在实际程序中也成立。

本主题涵盖了抽象解释的框架：通过伽罗瓦连接（Galois connections）关联具体语义和抽象语义，抽象域（区间、多面体、八边形），使用加宽（widening）和收窄（narrowing）确保终止的不动点计算，以及系统化、正确性构造的分析设计。它解决了如何保证可靠性以及如何调整精度的问题。

抽象解释的格模型: Cousot 和 Cousot 于 1977 年提出的框架将静态分析形式化为在格中近似程序语义的不动点，其可靠性源于抽象关系。
分析框架的系统设计: Cousot 夫妇 1979 年的工作展示了如何通过伽罗瓦连接推导出正确性构造的分析，并引入了加宽和收窄算子，以保证在无限高域上的终止性。
工业规模的抽象解释: ASTRÉE 分析器应用抽象解释和专门的抽象域，证明了大型安全关键航空电子软件中不存在运行时错误。

抽象解释为用于认证安全关键软件（如飞行控制代码）的可靠静态分析器提供了理论基础，通过证明完全不存在某类运行时错误。它也为许多实际分析的可靠性论证奠定了基础。

Patrick Cousot 和 Radhia Cousot 于 1977 年引入了抽象解释，并于 1979 年发展了其系统设计方法，包括加宽和收窄。随后出现了八边形和多面体等抽象域，2000 年代初的 ASTRÉE 分析器在航空电子软件上展示了该理论的工业规模应用。