Scalable Static Techniques for Exhaustive and Incremental Analyses of C Systems

在软件系统中，诸如编译器、测试器和调试器之类的工具需要静态语义信息，以确保它们的正确性并增强性能。增量更新算法仅计算受程序变化影响的数据流信息，避免了总体重新计算，有效地为大型演化软件系统提供了一致的文档。以前，已经开发了用于fortran类语言的增量技术和用于C程序的详尽分析。当这些对C系统的分析产生解决方案时，它们是廉价且高质量的；然而，分析通常会耗尽可用资源，而不会产生完整的解决方案，特别是对于较大的程序（超过5,000-10,000行代码）。本研究旨在扩展穷举技术的适用性，以处理更广泛的程序类别，并为C系统开发增量技术。这项工作由一个学术和工业团队完成，重点是开发新的分析技术及其在研究工业应用中的测试。目标是：(i)扩展现有的原型，以处理1万到10万行代码的程序，（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.