Contribution-based call stack abstraction for call string based pointer analysis

Context

Different method calls may have different contributions to the precision of the final application when abstracted into the call strings. The existing call string based pointer analysis algorithms do not consider such contribution difference and hence may not achieve best cost-effectiveness.

Objective

To be more cost-effective, we try to leverage the contribution information of each method call in call string based pointer analysis.

Method

The paper firstly proposes a contribution-based call stack abstraction method which abstracts the call stacks into call strings with the contribution information under consideration. Then, we apply the new call stack abstraction method to the pointer analysis of AspectJ programs and propose a concern-sensitive points-to analysis method. Besides, the new abstraction method is also applied to multi-threaded Java programs and results in a thread-sensitive pointer analysis method.

Results

The experimental results show that the two pointer analysis methods with contribution-based call stack abstraction can be more cost-effective than the ordinary call string based approaches for an application that detects harmful advices and an application that detects inter-thread data flow.

Conclusion

These pointer analysis methods more concretely and more clearly show that the contribution-based call stack abstraction can lead to better cost-effectiveness for the given applications.     

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     

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.     

字符串分析研究进展

随着软件应用范围的不断扩大,尤其是数据库软件和Web软件的广泛应用,字符串变量在软件程序中扮演的角色日益重要与此同时,针对字符串变量的程序分析技术——字符串分析,也取得了长足的发展,并在软件工程中的很多领域中得到了成功的应用.字符串分析的基本应用模式是首先使用字符串值分析获得字符串变量的所有可能取值,然后使用字符串约束求解判断这些变量的取值是否满足一定约束,从而对程序进行正确性验证.为了使得字符串分析能够应用在安全分析和软件维护应用中,研究人员对字符串分析进行了扩展,进一步分析字符串变量的数据来源.综述了字符串分析技术的研究进展,提出了字符串分析的问题构型,介绍了这一领域现在的主要研究内容:字符串值分析、字符串约束求解、字符串数据来源分析以及字符串分析在软件工程中的应用.     

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

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

Comparison of type-based and alias-based component recognition for embedded systems software

Component-based software engineering has found broad acceptance within the embedded systems community over the last years. However, to fully exploit its potential in terms of reusability and cost-efficiency, existing code-bases have to be refactored in a component-based way. To support refactorization, static analysis techniques can be used to identify components within coarse-grained layered or even monolithic legacy software for embedded systems. We present an approach for semi-automatic extraction of components from automotive software and compare two different versions, one type-based component-recognition analysis of linear complexity with a more precise version based on a points-to analysis of almost linear algorithmic complexity. Both analyses are applied to an industrial implementation of an automotive communication stack. Each analysis is evaluated with two sets of additional manually created annotations of distinct size and precision. Thus, both analyses are fully evaluated in terms of execution-time, memory consumption and analysis precision, and its impact on the number of recognized components. We show that the analysis with higher precision allows the use of a smaller user-provided filter set and obtain a proper component recognition.     

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

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

C语言的别名分析方法研究

别名分析对于数据流分析、程序优化和分析工具的实现非常重要.文章提出了一种需求驱动,流非敏感的分析算法来解决指针别名问题.通过构造程序表达式图(PEG)把指针别名问题转化成判断两个指针节点是否是联通的问题,它不同于传统的别名分析方法,它不需要构造别名集合和对其求交集,所以提高了分析指针别名的效率.     

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

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

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.     

Invariant relations, invariant functions, and loop functions

The increasing criticality of software applications, the increasing size and complexity of such applications, and the increasing reliance of software engineering paradigms on third party software assets combine to place a high premium on the ability to analyze software products to an arbitrary level of thoroughness and precision. Yet despite several decades of research, the goal of analyzing the functional properties of software products to an arbitrary level of thoroughness and precision remains unfulfilled. In this paper, we discuss the use of a relation-theoretic approach inspired from Mills?? logic to analyze while loops, and we support our approach by an operational prototype tool. The proposed method and tool have applications in program comprehension, reverse engineering, program verification, software maintenance, and programmer education.     

Fortran与VB传递字符串数据(Ⅰ)—由内建类型

为使Fortran与VB混合计算工程中的接口容纳更丰富的数据类型,研究了以内建类型为载体的字符串数据的传递.通过协调两种语言在字符串表达、存储及参数传递方面的不同,成功实施了单一字符串的传递.根据CVF字符串型函数调用机制,提出了VB调用Fortran字符串型函数的变通手段.基于对VB安全数纽参数的本质认识,并通过挖掘CVF语言扩展功能,解决了字符串数组的传递.通过对Fortran 90派生类型存储结构及VB字符串成员编码的剖析,给出了含字符串派生类型数组的传递方式.结合实例验证了各种传递方法的可行性.     

恶意软件动态分析云平台

传统的杀毒软件基于特征码识别的方式有效但具有一定的局限性.使用沙箱动态分析的方法能通过目标软件的行为特征对其恶意属性进行判断,可以同时达到检测恶意软件和帮助分析人员快速分析恶意软件的目的.为了提高沙箱平台分析的易用性和高效性,本文设计并实现了一个恶意软件动态分析云平台,通过分布式的沙箱控制机制,保证沙箱的分析能力以及可扩展性,并可通过对目标软件的分析结果来判断其是否属于恶意软件.实验表明,设计的云沙箱系统能够有效和高效的检测出恶意软件的恶意行为.     

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.     

StrSolve: solving string constraints lazily

Reasoning about strings is becoming a key step at the heart of many program analysis and testing frameworks. Stand-alone string constraint solving tools, called decision procedures, have been the focus of recent research in this area. The aim of this work is to provide algorithms and implementations that can be used by a variety of program analyses through a well-defined interface. This separation enables independent improvement of string constraint solving algorithms and reduces client effort. We present StrSolve, a decision procedure that reasons about equations over string variables. Our approach scales well with respect to the size of the input constraints, especially compared to other contemporary techniques. Our approach performs an explicit search for a satisfying assignment, but constructs the search space lazily based on an automata representation. We empirically evaluate our approach by comparing it with four existing string decision procedures on a number of tasks. We find that our prototype is, on average, several orders of magnitude faster than the fastest existing approaches, and present evidence that our lazy search space enumeration accounts for most of that benefit.     

数值稳定性相关漏洞隐患的自动化检测方法

安全漏洞检测是保障软件安全性的重要手段.随着互联网的发展,黑客的攻击手段日趋多样化,且攻击技术不断翻新,使软件安全受到了新的威胁.本文描述了当前软件中实际存在的一种新类型的安全漏洞隐患,我们称之为数值稳定性相关的安全漏洞隐患.由于黑客可以利用该类漏洞绕过现有的防护措施,且已有的数值稳定性分析方法很难检测到该类漏洞的存在,因而这一新类型的漏洞隐患十分危险.面对这一挑战,本文首先从数值稳定性引起软件行为改变的角度定义了数值稳定性相关的安全漏洞隐患,并给出了对应的自动化检测方法.该方法基于动静态相结合的程序分析与符号执行技术,通过数值变量符号式提取、静态攻击流程分析、以及高精度动态攻击验证三个步骤,来检测和分析软件中可能存在的数值稳定性相关安全漏洞.我们在业界多个著名开源软件上进行了实例研究,实验结果表明,本文方法能够有效检测到实际软件中真实存在的数值稳定性相关漏洞隐患.     

递归子程序的依赖性分析及其应用

程序依赖性是一种重要的程序分析、理解与维护方法,广泛应用于软件工程及软件逆向工程的各个方面,但递归子程序间的依赖分析一直是依赖性分析中的难点。为此,该文提出了一种新的递归子程序间的依赖性分析方法,它首先分析子程序内部的各种依赖关系;然后,结合子程序调用图分析子程序参数间的依赖关系;最后,通过模拟递归子程序的执行过程来分析它们之间的依赖关系。利用该文提供的方法可得到比较精确的递归子程序间的依赖关系。     

Software Bertillonage

Deployed software systems are typically composed of many pieces, not all of which may have been created by the main development team. Often, the provenance of included components—such as external libraries or cloned source code—is not clearly stated, and this uncertainty can introduce technical and ethical concerns that make it difficult for system owners and other stakeholders to manage their software assets. In this work, we motivate the need for the recovery of the provenance of software entities by a broad set of techniques that could include signature matching, source code fact extraction, software clone detection, call flow graph matching, string matching, historical analyses, and other techniques. We liken our provenance goals to that of Bertillonage, a simple and approximate forensic analysis technique based on bio-metrics that was developed in 19th century France before the advent of fingerprints. As an example, we have developed a fast, simple, and approximate technique called anchored signature matching for identifying the source origin of binary libraries within a given Java application. This technique involves a type of structured signature matching performed against a database of candidates drawn from the Maven2 repository, a 275 GB collection of open source Java libraries. To show the approach is both valid and effective, we conducted an empirical study on 945 jars from the Debian GNU/Linux distribution, as well as an industrial case study on 81 jars from an e-commerce application.     

Precise Call Graphs for C Programs with Function Pointers

The use of pointers presents serious problems for software productivity tools for software understanding, restructuring, and testing. Pointers enable indirect memory accesses through pointer dereferences, as well as indirect procedure calls (e.g., through function pointers in C). Such indirect accesses and calls can be disambiguated with pointer analysis. In this paper we evaluate the precision of one specific pointer analysis (the FA pointer analysis by Zhang et al.) for the purposes of call graph construction for C programs with function pointers. The analysis is incorporated in a production-strength code-browsing tool from Siemens Corporate Research in which the program call graph is used as a primary tool for code understanding.The FA pointer analysis uses an inexpensive, almost-linear, flow- and context-insensitive algorithm. To measure analysis precision, we compare the call graph constructed by this analysis with the most precise call graph obtainable by a large category of existing pointer analyses. Surprisingly, for all our data programs the FA analysis achieves the best possible precision. This result indicates that for the purposes of call graph construction, inexpensive pointer analyses may provide precision comparable to the precision of expensive pointer analyses.