Demand Driven Computation of Partial Data Flow and its Application in Software Engineering

虽然数据流分析最初是为了在编译器中使用而开发的，但它的有用性现在已经在许多软件工程工具中得到承认。由于全局数据流分析的起源，即编译器，软件工具的数据流计算是基于传统的数据流框架。然而，这种计算数据流的框架并没有产生软件工具所需的效率、精确度或数据流问题的类型。这些问题是由于穷举数据流的要求，即在所有点上计算所有可能的执行的信息，并且在每个程序点计算所有信息。本文研究了当穷举数据流的所有执行、所有程序点和每个程序点的所有信息的性质被放松，产生按需计算的部分数据流信息时，数据流问题的定义。其目标是在传统框架的基础上定义一个正式的框架，在该框架中可以定义和计算部分数据流问题。由于问题的数量会随着部分数据流的增长而增加，而数据流问题在许多情况下直到运行时才会知道，因此本项目通过定义一种规范技术来表达需求驱动的问题并自动生成计算信息的算法，来研究部分数据流分析的实现。为了定义部分数据流，必须提供缩小数据流分析范围的信息。此信息可以是在执行前提供的静态信息，也可以是用于进一步细化静态数据流或驱动其计算的动态信息。这项工作首先关注调试和测试工具，然后探索软件工程中的其他应用。

Although data flow analysis was first developed for use in compilers, its usefulness is now recognized in many software engineering tools. Because of the origin of global data flow analysis, that is, compilers, the computation of data flow for software tools is based on the traditional data flow framework. However, this framework for computing data flow is not producing the efficiency, the preciseness, or the type of data flow problem needed for software tools. These problems are due to the requirements of exhaustive data flow that information is computed for all possible executions, at all points, and all information is computed at each program point. This work investigates the definition of data flow problems when the properties of all executions, all program points and all information at each program point of exhaustive data flow are relaxed, producing partial data flow information computed on demand. The goal is to define a formal framework, in the vein of the traditional framework, where partial data flow problems can be defined and computed. Because the number of problems will grow with partial data flow, and the data flow problems will not be known in many cases until run time, this project investigates the implementation of partial data flow analysis by defining a specification technique to express the demand driven problem and automatically generating the algorithm that computes the information. In order to define partial data flow, information has to be provided that reduces the scope of data flow analysis. This information can either be static information, provided before execution, or dynamic information that is used to either further refine static data flow or to drive its computation. This work first focuses on debugging and testing tools and then explores other applications in software engineering.