Scalable Static Techniques for Exhaustive and Incremental Analyses of C Systems

在软件系统中，诸如编译器、测试器和调试器之类的工具需要静态语义信息，以确保它们的正确性并提高性能。 增量更新算法只计算受程序变化影响的数据流信息，避免了总的重新计算，有效地为大型不断发展的软件系统提供一致的文档。 在此之前，已经开发了用于类似Fortran的语言的增量技术和用于C程序的详尽分析。当C系统的这些分析产生解决方案时，它们是廉价和高质量的;然而，通常分析耗尽了可用的资源而没有产生完整的解决方案，特别是对于大型程序（超过5，000 - 10，000行代码）。本研究的目的是扩大穷举技术的适用性，以处理更广泛的一类程序，并为C系统开发增量技术。这项工作由一个学术和工业团队进行，重点是开发新的分析技术及其在研究工业应用中的测试。 目标是：（i）缩放现有原型以处理具有10，000到100，000行代码的程序，（ii）开发用于分析模块而不分析整个程序的技术（即，分析的单独编译模式），（iii）开发用于具有通用指针的语言的有趣的过程间静态分析的增量技术，以及（iv）增强用于现代编程语言的语义分析的理论基础设施（即，C、C++和Fortran 90）。 这项研究探索了通过设计新的、对流量不敏感的方法来改变别名信息精度的技术，以增强我们目前对流量敏感的方法。 对程序变量进行分区允许对不同的变量集具有不同精度的混叠解决方案。 实验进行了不同的k值为这些不同的集合，使用k-限制来处理递归结构中的解引用。本文提出了一种混合增量式分析算法，并以此为基础对C程序进行增量式副作用分析。

In software systems, tools such as compilers, testers, and debuggers require static semantic information, both to insure their correctness and to enhance performance. Incremental update algorithms, which only calculate data flow information affected by the program changes, avoiding total recalculation, efficiently provide consistent documentation for a large evolving software system. Previously, incremental techniques for Fortran-like languages and exhaustive analyses for C programs have been developed. When these analyses of C systems produce solutions, they are inexpensive and high quality; however, often the analyses exhaust available resources without yielding a complete solution, especially for larger programs (over 5,000-10,000 lines of code). This research aims at expanding the applicability of exhaustive techniques to handle a wider class of programs and developing incremental techniques for C systems. The work is performed by an academic and industrial team, focusing on the development of new analysis techniques and their testing on research industrial applications. Goals are to: (i) scale the existing prototype to handle programs with 10,000 to 100,000 lines of code, (ii) develop techniques for analyzing modules without analyzing the entire program (i.e., a separate compilation mode of analysis),(iii) develop incremental techniques for interesting interprocedural static analyses for languages with general purpose pointers, and (iv) enhance the theoretical infrastructure for semantic analysis of modern programming languages (i.e., C, C++, and Fortran 90). The research explores techniques for varying the precision of alias information by designing new, flow-insensitive methods, to augment our current flow-sensitive ones. Partitioning the program variables allows for an aliasing solution with varying degrees of precision for different sets of variables. Experiments are conducted varying the value of k for these different sets, using k-limiting to handle dereferencing in recursive structures. A hybrid incremental analysis algorithm is used as a basis for incrementalizing side effect analysis of C programs.