流非敏感的跨过程的别名分析

数据流分析算法可以分类成流敏感和流非敏感两类。为了提高效率,流非敏感的跨过程分析没有利用与每个过程相关的过程内的控制流信息。文中,提出了一种流非敏感的数据流分析算法来计算指针引起的跨过程的别名问题。通过如下方法来提高了分析的精度:利用某些特定类型的注销(kill)信息,这些信息可以提前计算;计算每个过程内产生的别名信息,而不是只计算每个过程的出口点产生的别名信息。     

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

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

流敏感按需指针别名分析算法

为了提高交互环境下指针别名查询的响应效率,近期研究提出通过只分析与目标相关指针的按需分析策略来降低浪费在与目标无关的指针分析的额外开销。典型的代表是基于上下文无关文法的按需别名分析算法。但是,该算法的精度只局限于控制流不敏感。控制流不敏感的别名关系将约束上层分析的精度。针对该不足,提出了具有流敏感精度的按需别名分析算法。首先采用不完全静态单赋值语句形式来区分指针变量赋值实例,然后通过层次线性化编码方法来表达控制流图中的流敏感信息以构建赋值流图,最后将别名关系查询问题转换为在赋值流图上搜索目标结点间在控制流可达条件下赋值路径的可达性问题,进而实现流敏感的按需别名分析。实验表明,与流不敏感的按需别名分析相比,该方法可以在保证查询效率的前提下,有效提高按需别名分析的精度。     

基于区域内存模型的C程序静态分析

为了提高程序的静态分析精度,提出了一种应用基于区域的符号化三值逻辑(region-based symbolic threevaluedlogic,简称RSTVL)的静态分析方法.RSTVL能够描述C程序运行时内存中数据结构的形态信息与变量的存储状态,以及可寻址表达式间的各种关系,包括指向关系、层次关系与取值逻辑关系.为了提高静态分析的精度,提出了一种基于RSTVL的流敏感、域敏感的过程内分析与基于符号化函数摘要的上下文敏感的过程间分析,能够精确地分析出每个程序点上的形态信息、数据流信息与指针指向关系.实验结果表明,相对于基于符号化三值逻辑的方法,该分析方法在保证一定分析效率的前提下,能够实现较高准确度的分析.     

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

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

针对共享内存SPMD程序的通信流依赖分析方法

传统数据流依赖分析方法在处理共享内存单指令多数据(SPMD)程序时,不能识别共享数据访问语句所属的处理节点,也不能消除执行顺序不定的控制流对共享数据流依赖造成的影响,从而在分析共享数据依赖时产生精度较低的结果。根据共享内存SPMD程序的共享数据别名特性,提出了一种可扩展的共享数据通信流依赖分析方法,并将其应用于一个编译后端分析器原型中。实验表明,该方法较传统分析方法可发现更多精确的共享数据通信流依赖。     

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

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

空指针解引用错误检测的静态方法研究

空指针解引用是C语言中的一类常见的动态内存错误。Manevich R等提出了一种适用于检测空指针解引用错误的后向分析方法。本文将后向分析的思想和流敏感、上下文敏感的指针分析结合在一起,给出了一种需求驱动的空指针解引用检测静态分析算法。该算法首先由指针分析获得别名信息,然后针对所关心的数据做后向数据流分析,追踪数据传递的源头,以确定程序中的表达式是否产生解引用错误。我们在SUIF2平台上实现了这一算法。实验结果表明,算法具有较高的检测精度。     

F1owS:一种MapReduce数据流公平调度方法

MapReduce Job的调度机制一直是学术研究的热点。在分析MapReduce数据流调度模型的基础上,提出一种面向MapReduce数据流的公平调度方法FlowS。该方法采用数据流池来分配资源以保证MapReduce数据流的隔离性,并且采用数据流池动态构建算法来确保资源的公平分配。实验表明,该调度方法可以有效提高Hadoop集群对MapReduce数据流的处理效率。     

基于污染变量关系图的Android应用污点分析工具

污点分析技术是检测Android智能手机隐私数据泄露的有效方法,目前主流的Android应用污点分析工具主要关注分析的精度,常常忽略运行效率的提升.在分析一些复杂应用时,过大的开销可能造成超时或程序崩溃等问题,影响工具的广泛使用.为了减少分析时间、提高效率,提出了一种基于污染变量关系图的污点分析方法.该方法定义了污染变量关系图用于描述程序中污染变量及其关系,摒弃了传统数据流分析框架,将污点分析和别名分析进行结合,从程序中抽象出污染变量关系图和潜在污染流,并在控制流图上对潜在污染流进行验证以提高精度.本文详细描述了基于该方法所实现的工具FastDroid的架构、模块及算法细节.实验使用了三个不同的测试集,分别为DroidBench-2.0,MalGenome以及Google Play上随机下载的1517个应用.实验结果表明,FastDroid在DroidBench-2.0测试集上的查准率和查全率分别达到93.3%和85.8%,比目前主流工具FlowDroid更高,并且在三个测试集上所用的分析时间更少且更稳定.     

Alias Analysis in Java with Reference-Set Representation for High-Performance Computing

In this paper, a flow-sensitive, context-insensitive alias analysis in Java is proposed. It is more efficient and precise than previous analyses for C++, and it does not negatively affect the safety of aliased references. To this end, we first present a reference-set alias representation. Second, data-flow equations based on the propagation rules for the reference-set alias representation are introduced. The equations compute alias information more efficiently and precisely than previous analyses for C++. Third, for the constant time complexity of the type determination, a type table is introduced with reference variables and all possible types for each reference variable. Fourth, an alias analysis algorithm is proposed, which uses a popular iterative loop method for an alias analysis. Finally, running times of benchmark codes are compared for reference-set and existing object-pair representation.     

高效而精确的锁别名分析方法

锁别名分析能够得到锁指针变量的指向信息,有效的锁别名分析可以更好地辅助数据竞争分析和死锁分析.现有锁别名分析往往采用保守的方式处理,进而影响分析结果的准确性.针对这一问题,提出了一种锁别名分析方法,该方法首先使用GCC插件获取SSA形式的中间代码,然后对中间代码进行预处理以获得与锁、函数指针操作相关的语句,最后对预处理后的程序使用本文提出的FP_LOCK算法进行准确的流敏感、上下文敏感分析.实验结果表明该方法能精确地确定锁别名,并且经过预处理后的FP_LOCK算法对分析大程序平均有9.95倍的加速比.     

不可达基路径的静态检测方法

不可达路径增加了程序的复杂度和冗余度,不可达路径的检测是结构测试中的一个关键问题。提出了一种包含异常处理结构的程序不可达路径的静态检测方法。该方法根据数据流信息判断产生冲突的分支,进而利用分支冲突检测路径的可达性;在数据流分析时考虑异常处理结构和变量别名对数据流信息的影响。实例分析结果表明,该方法可以进一步提高路径可达性检测的准确度。     

Alias verification for Fortran code optimization

Alias analysis for Fortran is less complicated than for programming languages with pointers but many real Fortran programs violate the standard: a formal parameter or a common variable that is aliased with another formal parameter is modified. Compilers, assuming standard-conforming programs, consider that an assignment to one variable will not change the value of any other variable, allowing optimizations involving the aliased variables. Higher performance results but anything may happen: the program may appear to run normally, or may produce incorrect answers, or may behave unpredictably. The results may depend on the compiler and the optimization level.To guarantee the standard conformance of programs and to maintain the referential transparency in order to make program analyses exact and program optimizations safe, precise alias information retrieval at a reasonable cost, especially the determination of overlaps between arrays are studied in this paper. Static analyses and code instrumentation are used to find all violations of the prohibitions against aliasing in Fortran code. Alias violation tests are inserted only at places where it cannot be proved statically that they are useless in order to reduce the number of dynamic checks at run-time. A specific memory location naming technique is used to compact representation and enhance the precision of alias analysis. Modifications on the dependence graph created by aliasing are also studied to show the impact of aliases on some program optimizing transformations. Experimental results on SPEC95 benchmark are presented and some related issues are also discussed.     

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

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

Probabilistic Alias Analysis of Executable Code

In this paper we present a method for flow-sensitive, context-insensitive probabilistic alias analysis at the assembly level. A memory disambiguation algorithm is also developed for revealing the probability of two registers holding the same memory location. The alias analysis and memory disambiguation algorithms are implemented based on the Diablo post-link optimizer. Experimental results show that the technique can estimate the probabilities that registers refer to the same memory address in benchmark programs with an overall average error of about 6.8%. The post-link optimizer can leverage the obtained quantitative information to facilitate aggressive analyses and optimizations.     

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.     

基于函数指针数组的代码迷惑技术

移动代理在网络计算中经常遇到有目的的篡改攻击，只要通过代码迷惑技术使得对移动代理的程序分析复杂度增加或精确性降低，就能有效地增加这种攻击的难度，从而在一定程度上阻止这种攻击．函数指针分析及控制流分析是程序分析中的难点，也是引起分析的精确度降低的原因．文章首先给出一种增添函数指针数组的程序变换方法，使得函数之间的调用关系函数变得难以分析；同时提出一种控制流变换方法来增加程序分析中的数据流及控制流分析的复杂度，从而使得程序分析的精确度大大降低，最终使篡改攻击难以达到目的。     

Type-based initialization analysis of a synchronous dataflow language

One of the appreciated features of the synchronous dataflow approach is that a program defines a perfectly deterministic behavior. But the use of the delay primitive leads to undefined values at the first cycle; thus a dataflow program is really deterministic only if it can be shown that such undefined values do not affect the behavior of the system.This paper presents an initialization analysis that guarantees the deterministic behavior of programs. This property being undecidable in general, the paper proposes a safe approximation of the property, precise enough for most dataflow programs. This analysis is a one-bit analysis – expressions are either initialized or uninitialized – and is defined as an inference-type system with subtyping constraints. This analysis has been implemented in the Lucid Synchrone compiler and in a new Scade-Lustre prototype compiler at Esterel Technologies. The analysis gives very good results in practice.