面向软件可信性的可信指针分析技术综述*

对可信指针分析技术的定义和描述、指针分析对软件可信性的保障、可信指针分析属性以及该领域主要研究成果等方面进行了综述。通过对现有可信指针分析技术的分析和比较,详细讨论了面向软件可信性的可信指针分析的关键技术;此外,重点介绍了流敏感指针分析及上下文敏感指针分析的方法和理论;最后对进一步研究工作的方向进行了展望。     

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.     

A new algorithm for stable assignments

A new algorithm for solving stable assignment problems is presented. By using a weight table, the overall situation of a problem is considered. The algorithm can deal with not only the one-to-one type assignments but also multi-function assignments for both equal and unequal sets. Some examples are given to illustrate the algorithm.     

基于域敏感指针分析的细粒度数据随机化技术

针对传统的数据随机化技术静态分析精度不高的问题,提出一种基于域敏感指针分析算法的细粒度数据随机化技术。在静态分析过程中,首先对中间表示进行语法抽象,得到形式化的语言表示;然后建立非标准类型系统,描述变量之间的指向关系;最后按照类型规则进行类型推断并求解,得到域敏感的指向关系。根据指向关系对数据进行随机化加密,得到经过随机化的可执行程序。实验数据表明,基于域敏感指针分析的数据随机化技术与传统的数据随机化技术相比,分析精度显著提高;处理时间开销平均增加了2%,但运行时间开销平均减少了3%。所提技术利用域敏感的指针分析,给程序带来更少的执行开销,并能够更好地提高程序的防御能力。     

含指针程序的单子切片方法

传统的含指针程序切片方法将指向分析与切片计算分开,增加了一定系统开销,为此文中提出一种可同时进行切片计算和指向分析的单子切片算法.该算法将程序正向切片思想与数据流迭代分析相结合,它是流敏感的,具有一定的精度,而且因指向分析和切片计算同时进行,故不需要像一般的流敏感分析方法那样记录每一个程序点的指向信息,而只需记录当前所分析的程序点处指向信息,从而节省了存储空间.此外,它还继承了原有单子切片方法所具有的强语言适应性和组合性.     

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.     

基于属性可靠分析的空指针引用缺陷检测

为实现基于静态分析技术充分地检测出C程序中的空指针引用缺陷,提出了一种基于属性可靠分析的缺陷检测方法。首先介绍了空指针引用缺陷模式及特征。然后针对空指针引用缺陷的检测特点提出了属性可靠分析理论,并将指针的指向属性描述为一个属性格。通过提出的抽象内存模型,基于给出的每种程序语句上的迁移实现指针指向属性的可靠分析,根据得到的每个被引用指针的指向属性进而实现空指针引用缺陷的检测。通过对五个实际工程的检测结果分析表明,方法可充分检测出C程序的空指针引用缺陷。     

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.     

一种新型指针仪表识别方法研究

本文在简单介绍指针式仪表及其常用识别方法的基础上，提出了一种基于最大灰度相减法的新型识别方法。然后详细介绍了这一方法的工作过程，着重阐述了几个关键环节所用到的图像处理算法。最后，给出了试验的结果及分析，指出了优化的途径。     

A new subspace identification approach based on principal component analysis

Principal component analysis (PCA) has been widely used for monitoring complex industrial processes with multiple variables and diagnosing process and sensor faults. The objective of this paper is to develop a new subspace identification algorithm that gives consistent model estimates under the errors-in-variables (EIV) situation. In this paper, we propose a new subspace identification approach using principal component analysis. PCA naturally falls into the category of EIV formulation, which resembles total least squares and allows for errors in both process input and output. We propose to use PCA to determine the system observability subspace, the A, B, C, and D matrices and the system order for an EIV formulation. Standard PCA is modified with instrumental variables in order to achieve consistent estimates of the system matrices. The proposed subspace identification method is demonstrated using a simulated process and a real industrial process for model identification and order determination. For comparison the MOESP algorithm and N4SID algorithm are used as benchmarks to demonstrate the advantages of the proposed PCA based subspace model identification (SMI) algorithm.     

A new approach to rectangle intersections part I

Rectangle intersections involving rectilinearly-oriented (hyper-) rectangles in d-dimensional real space are examined from two points of view. First, a data structure is developed which is efficient in time and space and allows us to report all d-dimensional rectangles stored which intersect a d-dimensional query rectangle. Second, in Part II, a slightly modified version of this new data structure is applied to report all intersecting pairs of rectangles of a given set. This approach yields a solution which is optimal in time and space for planar rectangles and reasonable in higher dimensions.     

A robust optimization approach for imprecise data envelopment analysis

Crisp input and output data are fundamentally indispensable in traditional data envelopment analysis (DEA). However, the input and output data in real-world problems are often imprecise or ambiguous. Some researchers have proposed interval DEA (IDEA) and fuzzy DEA (FDEA) to deal with imprecise and ambiguous data in DEA. Nevertheless, many real-life problems use linguistic data that cannot be used as interval data and a large number of input variables in fuzzy logic could result in a significant number of rules that are needed to specify a dynamic model. In this paper, we propose an adaptation of the standard DEA under conditions of uncertainty. The proposed approach is based on a robust optimization model in which the input and output parameters are constrained to be within an uncertainty set with additional constraints based on the worst case solution with respect to the uncertainty set. Our robust DEA (RDEA) model seeks to maximize efficiency (similar to standard DEA) but under the assumption of a worst case efficiency defied by the uncertainty set and it’s supporting constraint. A Monte-Carlo simulation is used to compute the conformity of the rankings in the RDEA model. The contribution of this paper is fourfold: (1) we consider ambiguous, uncertain and imprecise input and output data in DEA; (2) we address the gap in the imprecise DEA literature for problems not suitable or difficult to model with interval or fuzzy representations; (3) we propose a robust optimization model in which the input and output parameters are constrained to be within an uncertainty set with additional constraints based on the worst case solution with respect to the uncertainty set; and (4) we use Monte-Carlo simulation to specify a range of Gamma in which the rankings of the DMUs occur with high probability.     

一种基于鲁棒自适应观测器的故障区分方法

设计了一种鲁棒自适应观测器,通过其输出残差对传感器故障信息敏感性很高,而对系统故障信息敏感性很低的特点,实现了故障区分.设计了一套故障区分控制系统和检测策略,用以区分两类故障,以免发生误判现象.举例说明了该策略的可行性和有效性.     

基于扫描线处理的指针式仪表快速读数算法

针对光照不均匀、指针检测速度过慢等因素造成指针式仪表读数算法无法快速、准确读取示数的问题,提出一种基于扫描线处理的快速准确读数新算法。新算法首先利用单尺度Retinex提取光照鲁棒性特征图像,然后应用提出的扫描线处理算法快速抽取进行Hough变换的特征像素点,最后用双阈值Hough变换检测直线。实验表明,所提算法创新性地将指针图像细化与双阈值Hough变换等相结合,不仅解决了光照变化的影响以及检测速度慢等问题,而且具有读数精度高、读取速度可调节等特点。     

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.     

A statistical approach to knowledge acquisition for expert systems

Classical expert systems are rule based, depending on predicates expressed over attributes and their values. In the process of building expert systems, the attributes and constants used to interpret their values need to be specified. Standard techniques for doing this are drawn from psychology, for instance, interviewing and protocol analysis. This paper describes a statistical approach to deriving interpreting constants for given attributes. It is also possible to suggest the need for attributes beyond those given.The approach for selecting an interpreting constant is demonstrated by an example. The data to be fitted are first generated by selecting a representative collection of instances of the narrow decision addressed by a rule, then making a judgement for each instance, and defining an initial set of potentially explanatory attributes. A decision rule graph plots the judgements made against pairs of attributes. It reveals rules and key instances directly. It also shows when no rule is possible, thus suggesting the need for additional attributes. A study of a collection of seven rule based models shows that the attributes defined during the fitting process improved the fit of the final models to the judgements by twenty percent over models built with only the initial attributes.     

A new DEA approach to fully rank DMUs with an application to MBA programs

Data envelopment analysis (DEA) can be used to evaluate the efficiencies of decision‐making units (DMUs) in various areas like education, healthcare, and energy. Several DEA methods are proposed for this purpose; however, some of these methods cannot provide a full ranking and others often overlook some considerations that arise with special characteristics of DMUs. We propose a new DEA‐based approach to achieve a full ranking of DMUs. Our approach takes various issues into account such as the initial efficiency score of the DMU, the DMUs that should be removed from the set for it to become efficient (if any) and its effects on the efficiency scores of other DMUs. We demonstrate the shortcomings of several other DEA methods and discuss how our approach overcomes these. We apply our approach to evaluate 50 MBA programs from Financial Times 2018 rankings and compare the results with the evaluations of other methods. As opposed to some methods, our approach has the advantage of differentiating between all efficient DMUs as well as inefficient ones. In addition, the results demonstrate that we can achieve a consistent ranking that considers different aspects of the problem setting. The generated scores are also used to sort DMUs in classes of preference.     

A neuro-fuzzy approach for functional genomics data interpretation and analysis

The paper is concerned about the application of neuro-fuzzy techniques for the functional analysis of gene expression data from microarray experiments. The objective of this paper is to learn and predict functional classes of the E. coli genes using neuro-fuzzy based techniques, such as modular neuro and neuro-fuzzy networks. Methods of combining explicit and implicit knowledge in functional interpretation and analysis of gene expression data are proposed.