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系统，以检查日益重要的属性？比如关键系统的活动性和响应性。此外，拟议的研究将涉及研究生和高级本科水平的学生。最后，开发的技术将成为抽象解释和验证研究生课程主题的一部分。