基于Open64的可信指针分析框架研究

提出保障程序可信性的指针分析基础架构,为上层提供通用和丰富的接口及数据信息,不仅能够完成高效精确的指针分析,同时还为上层软件检测提供可信支持。该框架采用一种高效的流敏感、上下文敏感的可信指针分析技术,该方法充分利用扩展SSA形式,采用稀疏存储形式,提高了流敏感的分析效率。同时将需求驱动的分析策略引入到可信指针分析框架中来,能够有效地避免盲目的程序分析,使可信指针分析更具针对性,大大提高了分析的性能。最后通过实验验证了该框架进行可信指针分析的高效性和准确性。     

Java指针分析综述

近年来静态程序分析已成为保障软件可靠性、安全性和高效性的关键技术之一.指针分析作为基础程序分析技术为静态程序分析提供关于程序的一系列基础信息,例如程序任意变量的指向关系、变量间的别名关系、程序调用图、堆对象的可达性等.介绍了Java指针分析的重要内容：指针分析算法、上下文敏感、堆对象抽象、复杂语言特性处理、非全程序指针分析,特别是对近年来指针分析的研究热点选择性上下文敏感技术进行了梳理和讨论.     

可信软件分析与测试研究进展*

以软件可信性问题为主攻目标,首先阐述了可信软件的五大主要特征,给出了可信软件分析方法、测试方法和步骤,并总结了各个方法的缺点,重点对可信软件测试方法进行了分类总结和对比分析,同时给出了相应方法的测试工具;其次论述了可信软件的验证方法;最后进行了总结,并对今后可信软件分析和测试研究作出了展望。     

一种混合式的指针分析算法

指针的指向分析在检测C语言多线程程序的数据竞争中占有重要的地位。Steensgaard提出的流非敏感上下文非敏感的指针别名分析算法,因其执行效率极高的优点被广泛的应用于快速的指针指向分析。但该算法计算结果精度不高,得到的指针指向集往往有误差。针对该不足,引入了Vineet Kahlon的用求最大更新序列来求指针别名的思想,对Steensgaard算法计算出的结果进行了修正。并通过一个实例证明了改进后的算法比先前的算法更精确。     

过程间流敏感的指针分析技术研究

指针分析技术是一种基础的静态程序分析技术,也是软件安全方向的研究热点之一,在软件缺陷检测、恶意代码分析、程序验证、编译器优化等应用场景中发挥着重要的作用,指针分析的精度在这些应用场景中至关重要。流敏感分析和过程间分析是提高指针分析精度最有效的两种技术。文中对现有的提高过程间流敏感指针分析精度的技术进行总结,从为提高精度所消除的信息入手,将分析方法分为两大类：一类是消除分析中的虚假信息,以避免指向信息沿虚假的返回路径或是虚假调用关系传播;另一类是消除分析中保守的指向关系,在每个程序点处根据设置的规则尽可能确定指针的唯一指向,而不是笼统地计算指针的多个可能指向。据此,详细比较了过程间流敏感指针分析技术的异同,并对指针分析技术未来的研究方向进行了展望。     

软件可信评估综述

软件可信评估是近年来计算机科学的一个新的研究热点和难点,对软件可信评估的研究有助于促进软件产业的振兴与发展。首先分析了软件可信评估的必要性;然后对可信评估的研究现状进行综述,主要包括体现可信的属性特征和软件可信等级的定义、软件可信评估模型、软件可信评估实现方案四个方面;同时分析了目前可信评估中存在的不足以及造成这些不足的根本原因;最后指出了可信评估的未来发展趋势。     

一种需求驱动的可信指针分析技术

针对现有可信指针分析技术中关于精度和效率之间的取舍和权衡的不足,提出一种需求驱动的可信指针分析技术。该技术通过扩展SSA形式,使SSA可以用来表示间接的内存操作,即可以显式地将指针的解引用表示出来;之后利用引用定值分析将每个扩展SSA变量进行抽象存储,即记录每个变量的存储位置和引用位置,然后通过链进行连接;这样能够很容易地将指针,特别是需要分析的指针进行重点的有针对性的分析,这种本着需求驱动策略的分析方法大大提高分析的效率,最后通过实验验证了该方法的有效性。     

Java 指针指向分析优化

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

流敏感的跨过程指针别名分析

对指针别名及其表示方式进行了阐述。描述了跨过程指针别名分析的框架,通过在分析时创建PCG(程序调用图)来处理函数指针。研究了基于此框架的一个流敏感的跨过程指针别名分析算法,算法是跨过程阶段和过程内阶段交叉进行的。最后对算法进行了实例分析和验证。     

基于包含的指针分析优化技术综述

指针分析是程序分析和编译优化的基础,针对基于包含的指针分析算法的改进一直是指针分析领域研究的热点之一.文中从该指针分析算法改进的两类技术来总结近二十年来相关的研究工作,包括在线优化技术如约束图上的强连通分量的检测和消除等和离线优化技术如变量替换等.通过实验对比了7种较有影响力的分析算法和三种离线优化算法,并从性能、内存...     

基于证据的可信软件过程评估方法

现有软件过程可信性评估方法中,评估结果往往基于评估人员的主观经验,其准确性和客观性无法得到保证.为解决这个问题,提出了一种基于证据的可信软件过程评估方法(evidence-based trustworthy software process assessment method,EB-TSPAM).该方法以可信软件过程管...     

基于QFD技术的软件可信性评估研究*

对软件可信性的多维属性进行系统综合的度量评估,在软件设计开发过程中有效地跟踪和控制软件可信度是一个重要且亟待解决的研究课题。针对该问题,运用质量机能展开（QFD）技术分析软件可信需求和设计质量特性,并整合运用Kano质量模型测量软件可信性对于软件设计质量特性的敏感程度,提出了一个软件设计开发过程中的可信性评估方法。最后采用某航天操作系统软件的开发实例验证了该评估方法的可行性和有效性。     

Making context‐sensitive inclusion‐based pointer analysis practical for compilers using parameterised summarisation

Because of its high precision as a flow‐insensitive pointer analysis, Andersen's analysis has been deployed in some modern optimising compilers. To obtain improved precision, we describe how to add context sensitivity on top of Andersen's analysis. The resulting analysis, called ICON , is efficient to analyse large programs while being sufficiently precise to drive compiler optimisations. Its novelty lies in summarising the side effects of a procedure by using one transfer function on virtual variables that represent fully parameterised locations accessed via its formal parameters. As a result, a good balance between efficiency and precision is made, resulting in ICON that is more powerful than a 1‐callsite‐sensitive analysis and less so than a call‐path‐sensitive analysis (when the recursion cycles in a program are collapsed in all cases). We have compared ICON with FULCRA , a state of the art Andersen's analysis that is context sensitive by acyclic call paths, in Open64 (with recursion cycles collapsed in both cases) using the 16 C/C++ benchmarks in SPEC2000 (totalling 600 KLOC) and 5 C applications (totalling 2.1 MLOC). Our results demonstrate scalability of ICON and lack of scalability of FULCRA . FULCRA spends over 2 h in analysing SPEC2000 and fails to run to completion within 5 h for two of the five applications tested. In contrast, ICON spends just under 7 min on the 16 benchmarks in SPEC2000 and just under 26 min on the same two applications. For the 19 benchmarks analysable by FULCRA , ICON is nearly as accurate as FULCRA in terms of the quality of the built Static Single Assignment (SSA) form and the precision of the discovered alias information. Copyright © 2013 John Wiley & Sons, Ltd.     

一种可信软件设计方法及可信性评价

针对可信计算组织TCG(Trusted Computing Group)的信任链无法保障软件运行时动态可信的问题,对该信任链进行扩充,引入对软件运行时动态可信性的检测,提出了可信引擎驱动的可信软件信任链模型,并在此基础上提出了一种可信软件设计方法及可信性评价策略.通过引入描述软件可信行为轨迹的可信视图,在可信软件检查点处植入检查点传感器,将软件可信性融入软件设计中.通过对软件的完整性度量以及运行过程中软件行为轨迹的监测,实现软件的可信性保障.实验分析表明:采用该方法设计的软件能够有效地检测软件异常,并且成功检测软件异常的能力明显优于基于TCG信任链的软件.     

面向Web服务的动态可信性评估模型

网络化软件是由分布在互联网上多源异构的Web服务构成,但受其所处动态开放网络环境的影响,服务可信性处在不断变化之中.针对传统Web服务可信性难以适应动态评估的问题,提出了一种基于信息熵权重和带修正指标的动态信任评估模型（Dynamic Trustworthy Evaluation based on Information Entropy and Correction Metrics,DTEIECM）.首先,该模型充分挖掘模糊矩阵中的客观信息,利用信息熵对易受人为因素影响的主观权重进行修正.同时,考虑到所处运行环境对当前服务可信性的影响,增加了修正指标和受反馈影响的外部指标,以提高评估模型的自适应性.最后,通过对一个商务订单管理系统中的地图服务进行实例分析,结果表明DTMIECM模型在可信性度量中具有可行性,而且能够适应多变的环境并重新配置服务组合,有利于提高整个系统的可信度.     

Automated verification of pointer programs in pointer logic

Reasoning about pointer programs is difficult and challenging, while their safety is critical in software engineering. Storeless semantics pioneered by Jonkers provides a method to reason about pointer programs. However, the representation of memory states in Jonkers’ model is costly and redundant. This paper presents a new framework under a more efficient storeless model for automatically verifying properties of pointer programs related to the correct use of dynamically allocated memory such as absence of null dereferences, absence of dangling dereferences, absence of memory leaks, and preservation of structural invariants. The introduced logic-Pointer Logic, is developed to achieve such goals. To demonstrate that Pointer Logic is a useful storeless approach to verification, the Schorr-Waite tree-traversal algorithm which is always considered as a key test for pointer formalizations was verified via our analysis. Moreover, an experimental tool-plcc was implemented to automatically verify a number of non-trivial pointer programs.     

A new approach to pointer analysis for assignments

Pointer analysis is a technique to identify at copile-time the potential values of the pointer expressions in a program,which promises significant benefits for optimzing and parallelizing complilers.In this paper,a new approach to pointer analysis for assignments is presented.In this approach,assignments are classified into three categories:pointer assignments,structure(union)assignents and normal assignments which don‘t affect the point-to information.Pointer analyses for these three kinds of assignments respectively make up the integrated algorithm.When analyzing a pointer assigemtn.a new method called expression expansion is used to calculate both the left targets and the right targets.The integration of recursive data structure analysis into pointer analysis is a significant originality of this paper,which uniforms the pointer analysis for heap variables and the pointer analysis for stack variables.This algorithm is implemented in Agassiz,an analyzing tool for C programs developed by Institute of Parallel Processing,Fudan University,Its accuracy and effectiveness are illustrated by experimental data.     

Optimized statistical analysis of software trustworthiness attributes

Software trustworthiness has become one of the key restrictions for software service quality and the development of the software industry.However,trustworthiness attributes interlace structured and dynamical coupling relations,which causes great barriers for trustworthiness measurements of large-scale software.According to the dynamical evolutionary characteristics of software trustworthiness attributes,this paper proposes a new approach for optimizing the trustworthiness measurement in terms the kernel trustworthiness attributes,and improves a downsize-optimized statistical analysis method for software trustworthiness attributes based on their nonlinear relations.The improved method considerably simplifies the trustworthiness assessment of largescale software.Using theoretical analysis and numerical simulations,the feasibility of this method is verified using two typical examples that illustrate the realization of the trustworthiness measurement.     

5种指针分析算法的精度和效率比较

指针分析的研究已经有20多年的历史，也发表了很多相关的算法。对于研究者和工程人员来说，对不同的指针分析算法进行研究并用统一的标准进行精度及效率等内容的对比，是一件有意义的工作。考察了5种具有代表性的指针分析算法，并在固定外界影响因素的条件下对它们的精度和效率进行了测量和比较，最后分析了指针分析的结果如何影响一些客户分析的精度和效率。     

Cycle elimination for invocation graph-based context-sensitive pointer analysis

Context

Pointer analysis is an important building block of optimizing compilers and program analyzers for C language. Various methods with precision and performance trade-offs have been proposed. Among them, cycle elimination has been successfully used to improve the scalability of context-insensitive pointer analyses without losing any precision.

Objective

In this article, we present a new method on context-sensitive pointer analysis with an effective application of cycle elimination.

Method

To obtain similar benefits of cycle elimination for context-sensitive analysis, we propose a novel constraint-based formulation that uses sets of contexts as annotations. Our method is not based on binary decision diagram (BDD). Instead, we directly use invocation graphs to represent context sets and apply a hash-consing technique to deal with the exponential blow-up of contexts.

Result

Experimental results on C programs ranging from 20,000 to 290,000 lines show that applying cycle elimination to our new formulation results in 4.5 ×speedup over the previous BDD-based approach.

Conclusion

We showed that cycle elimination is an effective method for improving the scalability of context-sensitive pointer analysis.