A constraint-weaving approach to points-to analysis for AspectJ

Points-to analysis is a static code analysis technique that establishes the relationships between variables of references and allocated objects. A number of points-to analysis algorithms have been proposed for procedural and object-oriented languages like C and Java, while few of them can be used for AspectJ as we know so far. One main reason is that AspectJ is an aspect-oriented language which implements the separation of crosscutting concerns by advices, pointcuts, and inter-type declarations, while a points-to analysis of AspectJ programs may be imprecise because any aspect woven into the base code may change the points-to relations in the program and thus a conservative analysis has to be taken in order to handle the aspects. In this paper, we propose a context-sensitive points-to analysis technique called AJPoints for AspectJ. Similar to the weaving mechanism for AspectJ, AJPoints obtains the constraints and templates on the points-to relations for the base code and the aspects, respectively, but weaves and solves them in an iterative manner in order to cross the boundary between the base code and the aspects. We have implemented AJPoints on abc AspectJ compiler and evaluated it by using twelve AspectJ benchmark programs. The experimental results show that our technique can achieve a high precision about points-to relations in AspectJ programs.     

Java 指针指向分析优化

指针指向分析的主要目的是静态地获取程序在运行时刻的指针指向信息.基于Andersen算法,设计了一种有效的、上下文敏感的指针指向分析算法,支持继承、字段对象等语言特性.不同对象的字段在算法中被分别处理,同时,算法对复合类型的对象实现了基于字段的处理.为了提高算法的效率和可扩展性,引入了两种优化方式:一种是结点间的拓扑排序以降低分析过程中的迭代次数;另一种是在线的环路侦测与消除,它与拓扑排序过程同步实现,有效地提高了处理效率.实验数据表明,该算法可以用来为较大规模的Java代码生成精确的指向关系集合.     

Searching for points-to analysis

The points-to analysis problem is to find the pointer relationships that could arise during program execution. Many points-to analysis algorithms exist, each making a particular trade off between cost of the analysis and precision of the results. In this paper, we show how points-to analysis algorithms can be defined as transformed versions of an exact algorithm. We present a set of program transformations over a general program model and use them to define some existing points-to analysis algorithms. Doing so makes explicit the approximations involved in these algorithms. We also show how the transformations can be used to define new points-to analysis algorithms. Our transformations are generic and may be useful in the design of other program analysis algorithms.     

大规模源代码增量式资源泄漏检测方法

资源泄漏是影响软件质量和可靠性的一种重要软件缺陷,存在资源泄漏的程序长时间运行会由于资源耗尽而发生异常甚至崩溃.静态代码分析是进行资源泄漏检测的一种有效的技术手段,能够基于源代码或者二进制代码有效地发现程序中潜在的资源泄漏问题.然而,精确的资源泄漏检测算法的复杂性会随着程序规模的增加呈指数级增长,无法满足生产中即时对缺陷进行分析检测的实际应用需求.面向大规模源代码提出了一种增量式的静态资源泄漏检测方法,该方法支持过程间流敏感的资源泄漏检测,在用户编辑代码的过程中,从变更的函数入手,通过资源闭包、指向分析过滤等多种技术手段缩小资源泄漏检测范围,进而实现了大规模代码的即时缺陷分析与报告.实验结果表明：该方法在保证准确率的前提下,90%的增量检测实验可以在10s内完成,能够满足在用户编辑程序过程中对缺陷进行即时检测和报告的实际应用需求.     

On the non-approximability of points-to analysis

Determining points-to sets is an important static-analysis problem. Most of the classic static analyses (used e.g., by compilers or in programming environments) rely on knowing which variables might be used or defined by each expression in a program. In the presence of pointers, the use/def set of an expression like *p = *q can only be determined given (safe) points-to sets for p and q. Previous work has shown that both precise flow-sensitive and precise flow-insensitive pointer analysis is NP-Hard, even when restricted to single-procedure programs with no dynamic memory allocation. In this paper, we show that it is not even possible to compute good approximations to the precise solutions (i.e., to compute points-to sets whose sizes are within a constant factor of the sizes of the precise points-to sets) unless P=NP. Received: 1 November 2001 / 4 February 2002     

Multilevel static analysis for improving program quality

In this paper, we discuss some program analysis methods for finding defects in source code that are combined to form a multilevel analysis system. The first level consists of the checks using abstract syntax tree (AST) walks and intraprocedural dataflow; this level also builds a memory model for the subsequent levels. The memory model requires evaluating integer expressions and points-to sets. The second level is an interprocedural summary-based approach whereby the program features of interest are calculated as attributes of value classes that are formed in the program. Finally, the third level is a path-sensitive analysis that builds reachability formulas for program points and tracks the predicates that should hold for the desired features to be observable. The errors are found by testing the formulas for satisfiability with an SMT solver. All these levels of analysis are implemented in the Svace analyzer toolset, which demonstrates scalability up to millions of lines of code and precision of 60–90% true positives.     

Complexity of points-to analysis of Java in the presence ofexceptions

At each program point, points-to analysis for statically typed object oriented programming languages (e.g., Java, C++) determines those objects to which a reference may refer (or a pointer may point) during execution. Points-to analysis is necessary for any semantics based software tools for object oriented systems. Our new complexity results for points-to analysis distinguish the difficulty of intraprocedural and interprocedural points-to analyses for languages with combinations of single-level types (i.e., types with data members only of primitive type), exceptions with or without subtyping, and dynamic dispatch. Our results include: 1) the first polynomial-time algorithm for points-to analysis in the presence of exceptions that handles a robust subset of Java without threads and can be applied to C++; 2) proof that the above algorithm is safe, in general, and provably precise on programs with single-level types and exceptions without subtyping, but not dynamic dispatch, thus, this case is in P; 3) proof that an interprocedural points-to analysis problem with single-level types and exceptions with subtyping, but without dynamic dispatch, is PSPACE-hard, while the intraprocedural problem is PSPACE-complete. Other complexity characterizations of points-to analysis in programs without exceptions are presented, including an algorithm with worst-case bound of O(n⁵ ), which improves over the O(n⁷) worst-case bound achievable from previous approaches of T. Reps et al. (1995) and W.A. Landi and B.G. Ryder (1991)     

Static Analysis of Object References in RMI-Based Java Software

Distributed applications provide numerous advantages related to software performance, reliability, interoperability, and extensibility. This paper focuses on distributed Java programs built with the help of the remote method invocation (RMI) mechanism. We consider points-to analysis for such applications. Points-to analysis determines the objects pointed to by a reference variable or a reference object field. Such information plays a fundamental role as a prerequisite for many other static analyses. We present the first theoretical definition of points-to analysis for RMI-based Java applications, and we present an algorithm for implementing a flow- and context-insensitive points-to analysis for such applications. We also discuss the use of points-to information for corrupting call graph information, for understanding data dependencies due to remote memory locations, and for identifying opportunities for improving the performance of object serialization at remote calls. The work described in this paper solves one key problem for static analysis of RMI programs and provides a starting point for future work on improving the understanding, testing, verification, and performance of RMI-based software     

面向开源源码大数据的数据质量研究

基于开源源码大数据进行代码生成、缺陷预测等是当前智能化软件开发方法与技术的重要研究内容。然而现有的关注点主要聚焦于各种推荐、预测等智能算法的研究,较少对研究所使用数据的质量进行评估与分析。大部分智能化软件开发研究的数据来源于开源数据托管平台,受限于开发者自身水平,它们并不能保证都具有较高质量。根据"garbage in,garbage out",这会影响最终结果质量。源码数据的质量对相关的研究有重要影响,却没有得到足够的重视。针对上述问题,提出了一种面向开源源码大数据的方法块数据质量评估方法。首先研究如何定义和评估GitHub上抽取的源码的数据质量问题,然后对开源源码从不同维度进行质量评估。通过该源码数据质量评估方法可以帮助相关研究人员构建具有更高质量的数据集,进而提高智能化相关研究,比如代码生成、缺陷预测等的结果质量。     

Using linux device drivers for static verification tools benchmarking

The Linux Driver Verification system is designed for static analysis of the source code of Linux kernel space device drivers. In this paper, we describe the architecture of the verification system, including the integration of third-party tools for static verification of C programs. We consider characteristics of the Linux drivers source code that are important from the viewpoint of verification algorithms and give examples of comparative analysis of different verification tools, as well as different versions and configurations of a given tool.     

Automatic data race detection in SystemC models

Systems simulated by using the SystemC language are usually parallel and, therefore, may contain synchronization errors. Data races make up one widespread type of synchronization errors. In this paper, an approach to data race error detection in SystemC programs based on the analysis of the static source code is proposed. Algorithms for analyzing SystemC programs without quantitative time are developed. These algorithms allow one to detect all the data races existing in the program. The efficiency of the approach is proved by the experimental results obtained from using the developed tool meant for error detection for a set of test programs.     

基于结构特征的二进制代码安全缺陷分析模型

针对现有方法检测复杂结构二进制代码安全缺陷的不足,提出新的分析模型,并给出其应用方法。首先以缺陷的源代码元素集合生成特征元素集合,抽取代码结构信息,构建分析模型。然后依据各类中间表示（IR,intermediate representation）语句的统计概率计算分析模型,查找满足特征模型的IR代码组,通过IR代码与二进制代码的转换关系,实现对二进制程序中代码安全缺陷的有效检测。分析模型可应用于二进制单线程程序和并行程序。实验结果表明,相对于现有方法,应用该分析模型能够更全面深入地检测出各类结构复杂的二进制代码安全缺陷,且准确率更高。     

基于二进制的集合运算研究

通过比较二进制与集合之间的内在联系,提出了基于二进制的集合运算思想,给出了基于二进制的各种集合运算算法,该算法有效解决了传统集合操作算法中运算速度慢,效率低的不足,并提供了求幂集,交集,并集等集合运算算法的c语言源程序。     

面向顺序存储结构的数据流分析

C程序中数组、malloc动态分配后的连续内存等顺序存储结构被大量使用，但大多数传统的数据流分析方法未能充分描述其结构及其上的操作，特别是在利用指针访问顺序存储结构时，传统的分析方法只关注了指针的指向关系，而未讨论指针可能发生偏移的数值信息，且未考虑发生偏移时可能存在越界的不安全问题，导致了对顺序存储结构分析不精确.针对以上不足，首先对顺序存储结构进行抽象建模，并对顺序存储结构与指针结合使用时的指向关系与偏移量进行有效表示，建立了用于顺序存储结构的抽象内存模型SeqMM；其次，归纳总结C程序中顺序存储结构涉及的指针相关迁移操作、谓词操作及遍历顺序存储结构的循环操作，提出了安全范围判别保证操作安全性；之后，针对函数调用时形参指针引用顺序存储结构与实参的映射过程进行过程间推导规则设计；最后，基于上述分析，提出了一种内存泄漏缺陷检测算法对5个开源C工程的内存泄漏缺陷进行检测.实验结果表明：所提出的SeqMM能够有效地刻画C程序中的顺序存储结构及其涉及的各种操作，其数据流分析结果能够用于内存泄漏的检测工作，同时在效率和精度之间取得合理的权衡.     

Fast and precise points-to analysis

Many software engineering applications require points-to analysis. These client applications range from optimizing compilers to integrated program development environments (IDEs) and from testing environments to reverse-engineering tools. Moreover, software engineering applications used in an edit-compile cycle need points-to analysis to be fast and precise.In this article, we present a new context- and flow-sensitive approach to points-to analysis where calling contexts are distinguished by the points-to sets analyzed for their call target expressions. Compared to other well-known context-sensitive techniques it is faster in practice, on average, twice as fast as the call string approach and by an order of magnitude faster than the object-sensitive technique. In fact, it shows to be only marginally slower than a context-insensitive baseline analysis. At the same time, it provides higher precision than the call string technique and is similar in precision to the object-sensitive technique. We confirm these statements with experiments using a number of abstract precision metrics and a concrete client application: escape analysis.     

A novel analysis space for pointer analysis and its application for bug finding

The size of today’s programs continues to grow, as does the number of bugs they contain. Testing alone is rarely able to flush out all bugs, and many lurk in difficult-to-test corner cases. An important alternative is static analysis, in which correctness properties of a program are checked without running it. While it cannot catch all errors, static analysis can catch many subtle problems that testing would miss.We propose a new space of abstractions for pointer analysis—an important component of static analysis for C and similar languages. We identify two main components of any abstraction—how to model statement order and how to model conditionals, then present a new model of programs that enables us to explore different abstractions in this space. Our assign-fetch graph represents reads and writes to memory instead of traditional points-to relations and leads to concise function summaries that can be used in any context. Its flexibility supports many new analysis techniques with different trade-offs between precision and speed.We present the details of our abstraction space, explain where existing algorithms fit, describe a variety of new analysis algorithms based on our assign-fetch graphs, and finally present experimental results that show our flow-aware abstraction for statement ordering both runs faster and produces more precise results than traditional flow-insensitive analysis.     

Register allocation and exhaustive peephole optimization

Emerging peephole optimizers can relieve code generators of much case analysis, but delaying code generation decisions requires register allocation algorithms that accept object code instead of the more usual intermediate code. This paper describes two programs that implement such algorithms for a retargetable optimizing compiler. In a machine-independent fashion, they allocate and assign registers, eliminate common subexpressions (including often-missed machine-specific ones), identify dead variables, and define windows for the companion peephole optimizer. Their techniques for handling machine-specific data should generalize to other optimizations as well.     

一种利用指向组合优化依赖图构建的方法

指针的动态性使得程序分析中一个指针变量往往被认为有多个可能的指向目标,构成多个指向关系。现有的依赖图构建方法虽然较全面地考虑了指针的多指向性,但并未考虑指向关系之间的可组合性,因此精度上仍存在许多不足。为此,提出了一种利用无效指向组合优化依赖图构建的方法,新方法可以排除现有方法所不能识别的伪依赖,从而有效地提高依赖图的构建精度。     

基于指向与数值抽象的带指针算术程序的分析方法

带指针算术的程序往往包含数组越界、缓冲区溢出等运行时错误。单纯的指针分析技术和数值分析技术都无法有效处理指针算术。为了将指针分析与数值分析相结合,首先提出一种新的指针内存模型,然后基于该模型设计了一个刻画指针指向关系和指针偏移量的抽象域。最后在抽象解释框架下,设计并实现了一个面向带指针算术C程序的静态分析工具原型PAA。实验结果表明,PAA能够有效地分析指针程序的指向关系和数值性质,并能够在效率和精度间取得合理的权衡。