程序分析与验证
程序分析与验证运用严谨的技术来推断程序的行为，检测错误或证明软件符合其规范。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
程序分析是在不运行程序所有输入的情况下，自动推导程序行为属性的过程；程序验证则是通过证明或穷尽检查，确定程序满足形式化规范的过程。
Scope
该领域涵盖程序自动化和半自动化推理：静态分析和数据流技术、作为可靠近似统一框架的抽象解释、有限状态和并发系统的模型检测，以及使用证明助手的演绎验证。它涉及可靠性、精度与可判定性之间的权衡，以及这些方法在构建可信软件中的应用。
Sub-topics
Core questions
- 尽管存在不可判定性，如何可靠地计算程序属性？
- 分析如何在精度和可扩展性之间进行权衡？
- 何时可以对系统的正确性进行穷尽检查而非测试？
- 如何构建和机器验证完整的函数正确性证明？
Key theories
- 抽象解释
- Cousot夫妇建立了一个格论框架，其中可靠的静态分析被推导为程序语义的近似，统一了许多分析并保证了它们的可靠性。
- 时态逻辑模型检测
- Clarke、Emerson和Sistla展示了如何通过穷尽探索状态空间，自动验证有限状态并发系统是否符合时态逻辑规范。
- 机械化端到端验证
- Leroy的已验证编译器表明，可以使用证明助手证明现实软件的正确性，并提供编译保留程序行为的机器验证保证。
Clinical relevance
程序分析与验证是支撑大规模发现错误和安全漏洞、认证安全关键航空电子和汽车软件、以及生产机器验证编译器和操作系统内核的工具的基础。它们将正确性从基于测试的信心转变为可证明的保证。
History
数据流分析与优化编译器一同出现于20世纪70年代，同年Cousot夫妇引入了抽象解释。模型检测于20世纪80年代初由Clarke和Emerson以及独立的Queille和Sifakis提出，后来获得了图灵奖。21世纪初，大规模工业静态分析和机械化验证取得了成功，例如CompCert和seL4。
Debates
- 分析的可靠性与实用性
- 工具开发者们争论分析是应该完全可靠，报告所有可能的错误但可能产生许多误报，还是为了减少噪音和提高可扩展性而故意不可靠，这种张力塑造了工业界的错误发现工具。
Key figures
- Patrick Cousot
- Radhia Cousot
- Edmund Clarke
- E. Allen Emerson
- Xavier Leroy
Related topics
Seminal works
- cousot1977
- clarke1986
- leroy2009
- nielson1999
Frequently asked questions
- 静态分析与验证有何区别？
- 静态分析在没有完整规范的情况下自动推断近似属性（例如可能的空指针解引用），而验证则证明程序满足精确的形式化规范，通常需要更多努力并提供更强的保证。
- 如果正确性是不可判定的，分析如何工作？
- 分析通过计算可靠近似来规避不可判定性：它们可能会报告一些实际上不可能发生的情况，但绝不会遗漏它们所验证属性的真实违规。