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

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

Java指针分析综述

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

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

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

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

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

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

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

Java 指针指向分析优化

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

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

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

上下文敏感的过程间指针分析

提出了一种新的指针指向信息的过程间传播方法 ,对过程间指针分析所必须解决的若干重要问题给出了详尽的算法 ,从而形成了一种实用的上下文敏感的过程间指针分析框架 .该方法已在 C程序分析工具 Agassiz系统中实现 ,实验数据说明这些方法是行之有效的 .     

上下文敏感的纵向传播算法

通过基于包含的指针分析在线优化技术中的纵向传播方法,改进基于调用图上下文敏感指针分析的环消除技术,提出一种上下文敏感的纵向传播算法。初始化约束图,在约束图中进行环探测及其合并,执行差异传播并循环处理复杂约束,直到一次调用纵向传播例程后图中所有结点指向集不变为止,从而得到图中各结点到其指向集的映射。应用CIL工具的实验结果表明,该算法能有效地对源程序进行上下文敏感的指针分析,与环消除技术相比,在分析大规模程序时具有更高的时间效率。     

缓冲区溢出静态分析中的指针分析算法

提出一个扩展的流不敏感指针分析算法,主要用于缓冲区溢出静态分析,该算法把程序控制流图（CFG）转换为静态单指派（SSA）,然后循环调用一个流不敏感指针分析,生成每个指针变量精确的指向集,更新指针变量的定义-引用链中约束信息.在LLVM编译系统下实现了该算法,实验表明其精度和流敏感的指针分析算法相当,但效率高于流敏感指针分析算法,时间复杂度低于流敏感指针分析算法.     

基于源代码的指针分析算法的安全性改进

提出了一种安全性更强的指针分析算法。通过对四种常用的指针分析算法的综合分析,选取了Steensgaard算法进行安全性改进,在该算法的基础上通过添加强制类型转换的语义并对算法的类型系统的推导规则进行改进,使其避免了因精确性损耗而导致的攻击的漏报,同时还保持了原有算法复杂度不变。     

垂悬指针检测与防御方法

随着技术的发展,信息物理融合系统（cyber-physical system,简称CPS）系统在生活中扮演着越来越重要的角色,例如电力系统,铁路系统.如果CPS遭到攻击,将对现实世界的正常运转造成巨大影响,甚至威胁生命安全.垂悬指针是指向的区域被释放后未被置为空的指针,它是一种会导致攻击的软件缺陷.由垂悬指针导致的use-after-free和double-free漏洞能够执行任意恶意代码.迄今为止,只有少量工作针对垂悬指针进行检测、防御.其中多数都会导致过高的额外运行时开销.本文提出DangDone用于检测和防御垂悬指针.首先,我们通过静态分析检测潜在垂悬指针.然后,基于检测到的垂悬指针信息和一系列预定义的指针变换规则,依据指针传播信息变换指针,使得指针及其别名都指向同一个新引入的指针.基于该方法,我们实现了DangDone的原型工具.基于11个开源项目和SPEC CPU benchmark的实验结果表明,DangDone的静态分析部分只有33%的误报率,指针变换部分只引入了1%左右的额外开销.同时,DangDone成功防护了11个开源项目中的use-after-free和double-free漏洞.实验结果体现了DangDone的高效率及有效性.     

基于颜色特征提取方法的汽车仪表指针识别研究

利用HSI颜色空间中的色调提取方法,根据汽车仪表彩色指针的颜色特征提取出仪表的指针,为了消除仪表背景中与指针同颜色的像素,通过改进的差分算法提取出指针,确定指针圆心,并利用角度法计算仪表读数。研究中用MATLAB的GUI中ActiveX控件模拟了汽车转速仪表,将指针转动状态及角度判断实时显示在了模拟仪表中,实现了动态跟随。实验结果显示该研究方法对于彩色指针仪表的动态识别快速、便捷、有效。     

Design and implementation of a fine-grained software inspection tool

Although software inspection has led to improvements in software quality, many software systems continue to be deployed with unacceptable numbers of errors, even when software inspection is part of the development process. The difficulty of manually verifying that the software under inspection conforms to the rules is partly to blame. We describe the design and implementation of a tool designed to help alleviate this problem. The tool provides mechanisms for fine-grained inspection of software by exposing the results of sophisticated whole-program static analysis to the inspector. The tool computes many static-semantic representations of the program, including an accurate call graph and dependence graph. A whole-program pointer analysis is used to make sure that the representation is precise with respect to aliases induced by pointer usage. Views on the dependence graph and related representations are supported. Queries on the dependence graph allow an inspector to answer detailed questions about the semantics of the program. Facilities for openness and extensibility permit the tool to be integrated with many software development processes. The main challenge of the approach is to provide facilities to navigate and manage the enormous complexity of the dependence graph.     

嵌入式环境指针式仪表快速识别算法研究

论文在对已有的各种使用图像处理手段进行仪表指针识别方案进行研究的基础上,根据工控环境中指针式仪表所具有特点,设计了基于多分辨率处理、霍夫变换的快速、准确的指针识别算法,该算法是已有识别方案的改进与融合。为了对算法性能进行测试,论文在所提算法的基础上,设计了简单并且容易部署的指针识别系统。识别系统的运行数据证明,论文所提算法可在资源有限的嵌入式系统中对工控环境中的指针式仪表读数进行快速而准确的识别。     

Efficient online cycle detection technique combining with Steensgaard points‐to information

Pointer analysis is a key static analysis during compilation. Several client analyses and transformations rely on precise pointer information to optimize programs. Therefore, it is paramount to improve the efficiency of pointer analysis. A critical piece of an inclusion‐based pointer analysis is online cycle detection. The efficiency of pointer analysis is significantly influenced by the efficacy of detecting cycles. Existing approaches perform poorly when they guess cycle formation in the constraint graph. Thus, the number of false cycle‐detection triggers of the state‐of‐the‐art methods is considerably high (over 99% on Standard Performance Evaluation Corporation (SPEC) benchmarks). In this paper, we propose bootstrapping as a way to improve cycle detection predictability of pointer analysis. The main idea is to run a sequence of increasingly precise analyses to feed into the next more precise analysis to improve the efficiency of the latter analysis. In this process, we develop a new notion of pointer equivalence called constraint equivalence. Using Steensgaard's fast unification algorithm as the bootstrap, we devise a new cycle detection method for Andersen's inclusion‐based analysis. We measure the effectiveness of our approach using a suite of programs including SPEC 2000 benchmarks and two open‐source programs, and find that our method can reduce the number of false cycle detections by almost 22× compared with a state‐of‐the‐art method. This leads to an overall analysis time improvement of 18% on an average. Copyright © 2015 John Wiley & Sons, Ltd.     

A bottom-up pointer analysis using the update history

Pointer analysis is an important part for the source code analysis of C programs. In this paper, we propose a bottom-up and flow- and context-sensitive pointer analysis algorithm, where bottom-up refers to the ability to perform the analysis from callee modules to caller modules. Our approach is based on a new modular pointer analysis domain named the update history that can abstract memory states of a procedure independently of the information on aliases between memory locations and keep the information on the order of side effects performed. Such a memory representation not only enables the analysis to be formalized as a bottom-up analysis, but also helps the analysis to effectively identify killed side effects and relevant alias contexts. The experiments performed on a pilot implementation of the method shows that our approach is effective for improving the precision of a client analysis.     

基于纹理分析的仪表读数区域定位新方法

仪表读数自动识别的关键是准确检测出指针在刻度区域的位置,因此仪表盘上刻度区域的准确定位是仪表自动读数识别的重要步骤。提出一种基于形态学和纹理分析的仪表读数区域定位新方法。用图像重构技术清除图像边界及与边界相连接的结构,即仪表盘边框和指针,然后利用形态学算法来分割仪表盘的各个区域,最后用纹理统计分析方法和频谱度量方法定位出刻度区域,排除非刻度区域,这样进行指针读数时就可以只对指针和刻度进行处理,排除其它干扰。实验结果表明,对方形指针式仪表而言,上述方法能有效定位仪表刻度区域,且具有较强的鲁棒性和抗干扰性。