CSR - EHCS(EHS), TM: Abstract Interpretation-Based Analysis and Verification for Critical Systems

CSR - EHCS(EHS), TM：关键系统基于抽象解释的分析和验证

• 批准号: 0834535
• 负责人: Patrick Cousot
• 金额: --
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2010-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0834535&HistoricalAwards=false
• 关键词: CSR; EHCS; EHS; TM; Abstract

Modern embedded critical systems are generally interactive and reactive, i.e. they are programs that interact with mechanical or electronic devices such as sensors and actuators. Errors in safety-critical and mission-critical programs (such as in the aviation arena) can be catastrophic. This research proposal identifies several areas in which the static analysis of critical systems using abstract interpretation can ensure the correctness of various aspects of critical systems. There are important issues in the analysis of critical systems for which abstract interpretation provides a promising approach. This research pursues analysis of liveness and responsiveness properties of critical systems. Most present-day static analyzers analyze safety properties, stating that no unwanted error can ever appear during any program execution. Recent work on termination has shown that abstract interpretation can also be useful in proving liveness properties like termination. Such liveness properties state that something good must eventually happen when the program is executed. In the context of reactive critical systems, an important liveness property is responsiveness: the program should react to an external event in a timely fashion. Abstract interpretation has proven to be a powerful method for verifying the safety properties of programs. On the other hand, temporal logic and its related methods provide ways for dealing with liveness properties of programs. An important aspect of the work proposed here is the integration of the two approaches in order to reason formally about a wide class of properties incorporating both safety and liveness. Furthermore, existing verification methods using abstraction are often restricted to finitary abstractions, i.e. abstractions into a finite domain. As another aspect of the proposed work, these verification methods will be extended to infinite domains. The research results are expected to have impact in a number of diverse areas. First, the new methodologies developed in the area of abstract interpretation as part of this research will provide the theoretical basis for future uses of static analysis to ensure the correctness of critical and embedded systems. Second, we anticipate the construction of software will be performed to extend the capability of current analyzers used in industry, such as the ASTRÉE system, to check increasingly important properties ? such as liveness and responsiveness of critical systems. Additionally, the proposed research will involve students at both the graduate and senior undergraduate level. Finally, the techniques developed will become part of the topics covered graduate courses in abstraction interpretation and verification.

现代嵌入式关键系统通常是交互式和反应性的，即它们是与机械或电子设备(如传感器和执行器)交互的程序。安全关键型和任务关键型程序中的错误(例如在航空领域)可能是灾难性的。这项研究建议确定了几个领域，在这些领域中，使用抽象解释对关键系统进行静态分析可以确保关键系统各个方面的正确性。在关键系统的分析中有一些重要的问题，抽象解释为其提供了一种很有前途的方法。本研究致力于分析关键系统的活性和响应性。目前大多数静态分析器都会分析安全属性，声明在任何程序执行过程中都不会出现不必要的错误。最近关于终止性的研究表明，抽象解释在证明终止性等活性性质时也是有用的。这样的活跃性属性表明，当程序执行时，最终一定会发生一些好的事情。在反应性关键系统的上下文中，一个重要的活性属性是响应性：程序应该及时对外部事件做出反应。抽象解释已被证明是验证程序安全性的一种强有力的方法。另一方面，时态逻辑及其相关方法提供了处理程序活跃性属性的方法。这里提出的工作的一个重要方面是将这两种方法结合起来，以便对包含安全性和活性的广泛类别的属性进行形式上的推理。此外，现有的基于抽象的验证方法往往局限于有限抽象，即抽象到有限域。作为拟议工作的另一个方面，这些验证方法将扩展到无限大域。预计研究结果将在多个不同领域产生影响。首先，作为本研究的一部分，在抽象解释领域开发的新方法将为今后使用静态分析确保关键和嵌入式系统的正确性提供理论基础。其次，我们预计将进行软件建设，以扩展工业中使用的当前分析仪的能力，例如ASTRéE系统，以检查日益重要的属性？例如关键系统的活跃性和响应性。此外，拟议的研究将涉及研究生和高年级本科生。最后，所开发的技术将成为研究生课程抽象解释和验证主题的一部分。