基于区间向量抽象域的数值程序分析算法

为权衡对矩阵运算静态分析的精度和效率,针对程序中表示矩阵的变量,提出一种基于抽象解释的抽象与分析算法,即区间向量抽象域。将矩阵变量抽象为一个区间向量对,即行区间向量和列区间向量,矩阵各元素的值范围是由这两个区间向量对应元素的交集表示;设计在该抽象域上的操作以及迁移函数。通过对区间向量抽象域的计算,较好地权衡矩阵元素值范围分析的精确度和分析效率。实验结果表明,该抽象域能够较精确地分析程序中矩阵各元素的值范围,与现有的分析数组的抽象域相比,在分析精度和效率之间取得了合理权衡。     

单变量区间线性不等式抽象域

程序变量的值范围信息对于编译器优化、程序分析与验证等应用至关重要.抽象解释理论提供了一种通用框架为程序变量计算近似的但是可靠的值范围.然而该框架下已有的数值抽象域在表达非凸性质方面存在一定的局限性,影响了值范围分析的精度.文中基于抽象解释理论,提出一个新的数值抽象域——单变量区间线性不等式抽象域.其主要思想是使用单变量区间线性不等式约束作为域元素的约束表示方法.该抽象域的表达能力强于经典的区间抽象域,并允许表达某类非凸、非连通性质.同时,其域操作存在高效的实现算法.该抽象域具有很强的可扩展性,能够应用在实际大规模的程序分析中.     

自动合成数组不变式

本文提出了一个基于抽象解释框架自动合成数组程序不变式的方法.它能够分析按照特定顺序访问一维或者多维数组的程序,然后合成不变式.该方法将性质（包括区间全称量词性质和原子性质）集合作为抽象域,通过前向迭代数据流分析合成数组性质.本文证明了该方法的正确性和收敛性,并通过一些实例展示了该方法的灵活性.我们开发了一个原型工具.该工具在各种数组程序（包括Competition on Software Verification中的array-examples benchmark）上的实验展示了方法的可行性和有效性.     

一个面向C和Fortran数值程序的静态分析工具

程序的正确性验证一直以来都是计算机科学中的一个挑战性问题,抽象解释理论为程序静态分析提供了一个通用框架,可以在编译时自动地推导程序的动态性质。基于抽象解释的数值程序分析可以自动推导程序中数值变量间的不变式关系,这对于编译优化、程序错误检查至关重要。本文建立并实现了一个面向C和Fortran程序并支持过程间分析的数值程序分析框架和工具,C或Fortran源程序经过预处理后转化为具有统一格式的中间表示形式,然后基于该中间表示抽取与源程序语义等价的语义等式,最后在该语义等式上进行不动点迭代计算从而得到程序不变式。在此基础上,本文还对数组等复杂语法结构进行了建模和抽象。实验结果表明,该工具具有较高的可扩展性、精度,并能够处理大部分因数组的使用而带来的程序分析上的问题。     

Algebraic Power Analysis by Abstract Interpretation

In this paper we design abstract domains for power analysis. These domains are conceived to discover properties of the following type: The variable X at a given program point is the power of c with the exponent having a given property , where c and are automatically determined. This construction is general and includes different algebraic entities, such as numerical and polynomial (with rational coefficients), as bases. Several families of domains are presented, some of these consider that the exponent can be any natural or integer value, the others also include the analysis of properties of the exponent set. Relevant lattice-theoretic properties of these domains are proved such as the absence of infinite ascending chain and the structure of their meet-irreducible elements. The numerical domains are applied in the analysis of integer powers of imperative programs and in the analysis of probabilistic concurrent programming, with probabilistic non-deterministic choice. Moreover we use the numerical power domains in order to analyze the factorization of integer variables, i.e., invariant properties of factors and of their exponents. In this way we are able to statically detect information hidden in prime factorization, which can be used in software watermarking.     

基于缺陷关联的静态分析优化

缺陷检测一般包括静态分析与人工审查两个阶段.静态检测工具报告大量缺陷,但是主要的缺陷确认工作仍由人工完成,这是一件费时、费力的工作.巨大的审查开销可能会导致软件开发人员拒绝使用该静态缺陷检测工具.提出一种可靠的基于缺陷关联的静态分析优化方法,能够分组静态检测工具所报告的缺陷,在分组后的任意一组缺陷中,如果其主导缺陷被证明是误报(或者是真实的),就能确认其他缺陷也是误报(也是真实的).实验结果表明,基于缺陷关联的静态分析优化方法在较小的时间和空间开销下减少了22%的缺陷审查工作,能够较好地适应于大型的关键嵌入式系统程序缺陷检测.     

Refining Model Checking by Abstract Interpretation

Formal methods combining abstract interpretation and model-checking have been considered for automated analysis of software.In abstract model-checking, the semantics of an infinite transition system is abstracted to get a finite approximation on which temporal-logic/-calculus model-checking can be directly applied.The paper proposes two improvements of abstract model-checking which can be applied to infinite abstract transition systems:iA new combination of forwards and backwards abstract fixed-point model-checking computations for universal safety. It computes a more precise result than that computed by conjunction of the forward and backward analyses alone, without needing to refine the abstraction;When abstraction is unsound (as can happen in minimum/maximum path-length problems), it is proposed to use the partial results of a classical combination of forward and backward abstract interpretation analyses for universal safety in order to reduce, on-the-fly, the concrete state space to be searched by model-checking.     

基于约束的多面体抽象域的弱接合

基于约束的多面体抽象域的处理能力主要受限于其高代价的(强)接合操作,即两多面体的凸闭包计算。针对基于约束的多面体抽象域提出了一系列低代价的弱接合操作,以作为凸闭包计算的可靠替代候选。为了能够在分析效率和精度之间取得合理权衡,还提出了一种启发式策略,以把强、弱接合动态地、有机地结合起来进行程序分析。实验结果表明,弱接合能够极大地提升基于约束的多面体抽象域的效率、可扩展性和鲁棒性。     

Kleene Algebra and Bytecode Verification

Most standard approaches to the static analysis of programs, such as the popular worklist method, are first-order methods that inductively annotate program points with abstract values. In [6] we introduced a second-order approach based on Kleene algebra. In this approach, the primary objects of interest are not the abstract data values, but the transfer functions that manipulate them. These elements form a left-handed Kleene algebra. The dataflow labeling is not achieved by inductively labeling the program with abstract values, but rather by computing the star (Kleene closure) of a matrix of transfer functions. In this paper we show how this general framework applies to the problem of Java bytecode verification. We show how to specify transfer functions arising in Java bytecode verification in such a way that the Kleene algebra operations (join, composition, star) can be computed efficiently. We also give a hybrid dataflow analysis algorithm that computes the closure of a matrix on a cutset of the control flow graph, thereby avoiding the recalculation of dataflow information when there are cycles in the graph. This method could potentially improve the performance over the standard worklist algorithm when a small cutset can be found.     

Strictness analysis in the Imperative Lambda Calculus

Concerns over efficiency and expressiveness of functional languages have motivated the study of languages that allow state and pure functionality to coexist peacefully. However, state-oriented features complicate the static analyses which are essential for efficient compilation of these languages. The problem is an interesting one because it combines traditional strictness analysis with the abstract storage structure analysis familiar from imperative languages. We apply the technique of abstract interpretation to perform strictness analysis in the Imperative Lambda Calculus of Swarup, Reddy, and Ireland. A basic analysis is presented, along with some extensions to handle certain evident weaknesses; proofs for these analyses are discussed in some detail.Partially supported by NASA grant NAG-1-613Partially supported by NSF grant CCR 93-03043     

Static analysis of JavaScript libraries in a scalable and precise way using loop sensitivity

Statically analyzing JavaScript applications often requires an analysis of JavaScript libraries because many JavaScript applications use libraries. However, static analysis techniques for JavaScript are not yet ready for analyzing libraries in a scalable and precise manner. Simply loading JavaScript libraries uses various dynamic features of JavaScript, which cause static analyzers to suffer from mutually intermingled problems of scalability and imprecision. In this paper, we present a loop‐sensitive analysis (LSA) technique, which can improve the analysis scalability when analyzing JavaScript libraries by enhancing the analysis precision of loops. The LSA technique distinguishes loop iterations when loop conditions can be determined to be either true or false precisely. We formalize LSA in the abstract interpretation framework in the presence of tricky language features such as exceptions and prove its soundness and precision theorems using Coq. We evaluate our LSA implementation with the analysis results of programs that use 5 JavaScript libraries and show that LSA significantly improves the analysis scalability and precision of an existing JavaScript static analyzer when analyzing JavaScript libraries. In addition, using the configurability of LSA, we experimentally show the correlation between scalability and precision in the analysis of JavaScript libraries. We found that even the analysis of simple programs that just load jQuery, which is the most popular JavaScript library, in a scalable way requires distinguishing not only the last 4 functions being called but also 40 iterations in each loop with 2‐level nested loops at least. Both the mechanization and implementation of LSA are publicly available.