Program Analysis: Logics, Algorithms, and Application

程序分析：逻辑、算法和应用

• 批准号: 9416973
• 负责人: Alexander Aiken
• 金额: $ 13.48万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-09-15 至 1998-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9416973&HistoricalAwards=false
• 关键词: Program; Analysis; Logics; Algorithms; Application

This project is undertaking a systematic investigation of a general class of structural program analysis problems. The term structural program analysis refers to compile-time program analyses that deal with the types and structure of values computed by programs. This class of program analyses is broad, including within it the classical dataflow analyses of C and FORTRAN compilers, type inference for languages such as ML, and analysis of class membership of values in object-oriented languages. The primary goal of this work is the synthesis of set constraint techniques for structural program analysis in a common framework; in particular, an implementation of set constraints suitable for use in a general class of program analysis problems will be developed and distributed for use in research and teaching. There has been considerable activity directed towards using set constraints for structural analyses in recent years. Most of the work has been directed either towards studying the theory of set constraints itself, or at applications of set constraints to particular problems. Set-based analysis is the exception; set- based analysis provides a high-level characterization of a class of program analyses in terms of set constraints. Currently, however, there is no general-purpose implementation of set constraints available for experimentation with set-based (or any other class of) analyses. This system is expected to be expressive enough to encompass all set-based analyses and many analyses that are not set-based. Aside from the primary goal of developing an `off-the-shelf` implementation of set constraints that can be used in many settings, the project also pursues three secondary goals. The first goal is to develop a common technical language for structural analyses. The second goal is to describe the structure of the design space for structural program analyses using this common technical framework. The tradeoffs between accuracy and speed in structural analyses are poorly understood. By studying these problems in an abstract setting, it should be possible to make general statements about the relative efficiency and precision of various program analysis techniques that apply across a wide spectrum of applications. The third goal is to design algorithms using the above results. General algorithms are sought that would provide the best precision-speed tradeoffs for various classes of analysis problems.

该项目正在对一般的结构计划分析问题进行系统的研究。术语结构程序分析是指涉及程序计算的值类型和结构的编译时间计划分析。这类程序分析很广泛，包括在其中，C和Fortran编译器的经典数据流分析，诸如ML之类的语言的推断以及对目标语言中值的类成员的分析。 这项工作的主要目的是在共同框架中综合用于结构程序分析的集合约束技术。 特别是，将开发和分发适合于一类计划分析问题的集合约束，以用于研究和教学。 近年来，有大量活动用于使用集合约束进行结构分析。大多数工作都是针对研究集合约束本身的理论，或者是针对特定问题的限制的应用。基于集合的分析是例外。 基于设置的分析提供了对集合约束的一类程序分析的高级表征。但是，目前尚无对基于集合（或任何其他类别的）分析进行实验的集合约束的通用实现。预计该系统将足够表达，以涵盖所有基于集合的分析和许多不基于设定的分析。 除了开发可在许多环境中使用的设定约束实施“现成”实施的主要目标外，该项目还实现了三个次要目标。第一个目标是为结构分析开发通用的技术语言。第二个目标是使用此通用技术框架来描述结构程序分析的设计空间的结构。在结构分析中的准确性和速度之间的权衡知之甚少。 通过在抽象环境中研究这些问题，应该有可能对各种应用程序中适用的各种程序分析技术的相对效率和精度进行一般性陈述。第三个目标是使用上述结果设计算法。寻求一般算法，可以为各种分析问题提供最佳的精确速度权衡。