带有指针的嵌套式语言的全程分析方法

对指针变量以及过程间的数据的分析是嵌套式语言全程分析的关键问题之一。本文提出了一种对带有指针的嵌套式语言的全程分析方法，该方法可以有效地解决上述问题。     

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

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

指针数组的过程内别名分析

指针别名分析在C语言的并行优化中占有重要的地位,但已有的指针别名分析只能处理指针标量的情况.文章在介绍已有指针别名信息表示法的不足的基础上,提出了一种能够表示指针数组别名信息的表示方法,它可以更加准确地表示指针别名信息.在此表示法的基础上,提出了指针数组的过程内别名分析算法.此算法完全包含了指针标量的别名分析,对现有的指针别名分析算法所不能解决的一些问题能进行有效地处理.     

Java 指针指向分析优化

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

一种基于指针逻辑的代码安全属性分析方法

在分析和总结前人工作的基础上,提出了一种改进的代码安全属性验证方法.该方法在利用传统的源代码安全属性验证工具的基础上,加入了指针逻辑,针对现有代码属性分析技术只能对C语言子集进行分析验证的不足,利用指针逻辑对源代码的分析结果对源代码中的指针进行替换,从而避开了传统静态代码属性验证工具对指针处理功能太弱的瓶颈,可以实现对C语言中的部分指针及运算进行处理.     

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

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

基于指向与数值抽象的带指针算术程序的分析方法

带指针算术的程序往往包含数组越界、缓冲区溢出等运行时错误。单纯的指针分析技术和数值分析技术都无法有效处理指针算术。为了将指针分析与数值分析相结合,首先提出一种新的指针内存模型,然后基于该模型设计了一个刻画指针指向关系和指针偏移量的抽象域。最后在抽象解释框架下,设计并实现了一个面向带指针算术C程序的静态分析工具原型PAA。实验结果表明,PAA能够有效地分析指针程序的指向关系和数值性质,并能够在效率和精度间取得合理的权衡。     

基于卷积神经网络的指针式仪表识别

目前大部分研究指针式仪表识别的方法中提取指针是完全基于传统的图像处理技术,提取过程较为复杂且步骤繁多.为了有效解决指针式仪表读数识别中指针中轴线所在直线提取困难及识别精度不高等问题,本文提出了一种基于深度学习的指针式仪表的识别方法.首先用Faster R-CNN算法检测仪表圆盘,再采用基于深度学习的方法Faster R-CNN算法检测指针,根据得到的指针目标框的位置信息裁剪得到指针图像,在指针图像的基础上进行二值化、细化、霍夫变换检测直线、最小二乘法拟合直线等步骤识别仪表最终读数.和直接在仪表表盘目标框图像或原始图像上进行传统图像处理相比很大程度上减少了定位指针中轴线所在直线过程中的干扰.实验结果表明本文所提出的基于深度学习的指针检测的平均准确率高达96.55％.对于复杂背景下指针式仪表的指针区域的检测具有良好的准确性与稳定性.     

一种用于指针程序安全性证明的指针逻辑

在高可信软件的各种性质中,安全性是被关注的重点,其中软件满足安全策略的证明方法是研究的热点之一.文中根据作者所设想的安全程序的设计和证明框架,为类C语言的一个子集设计了一个指针逻辑系统.该逻辑系统是Hoare逻辑系统的一种扩展,它用推理规则来表达每一种语句引起指针信息的变化情况.它可用来对指针程序进行精确的指针分析,所获得的信息用来证明指针程序是否满足定型规则的附加条件,以支持程序的安全性验证.该逻辑系统也可用来证明指针程序的其它性质.     

对C语言指针理解方式的探讨

指针是C语言的精华但又最难掌握。本文在分析一般变量的指针、指针与数组的关系、指针的指针等知识点的基础上，探讨了对C语言指针的理解方法，特别针对二维数组的指针，本文给出了一种有效的理解方法。     

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

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

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

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

Code optimization across procedures

Procedure calls can be a major obstacle to the analysis of computer programs, preventing significant improvements in program speed. A broad range of techniques, each of which is in some sense interprocedural by nature, is considered to overcome this obstacle. Some techniques rely on interprocedural dataflow in their analysis. Others require interprocedural information in the form of detailed profile data or information concerning the scope of a given procedure in relation to other procedures. These include procedure integration, interprocedural register allocation, pointer and alias tracking, and dependency analysis     

Compiler optimizations for processors with SIMD instructions

To achieve maximum efficiency, modern embedded processors for media applications exploit single instruction multiple data (SIMD) instructions. SIMD instructions provide a form of vectorization where a large machine word is viewed as a vector of subwords and the same operation is performed on all subwords in parallel. Systematic usage of SIMD instructions can significantly improve program performance. With C becoming the dominant language for programming embedded devices, there is a clear need for C compilers that use SIMD instructions whenever appropriate. However, SIMD instructions typically require each memory access to be aligned with the instruction's data access size. Therefore an important problem in designing the compiler is to determine whether a C pointer is aligned, i.e. whether it refers to the beginning of a machine word. In this paper, we describe our SIMD generation algorithm and present an analysis method which determines the alignment of pointers at compile time. The alignment information is used to reduce the number of dynamic alignment checks and the overhead incurred by them. Our method uses an interprocedural analysis which propagates pointer alignment information in function bodies and through function calls. The effectiveness of our method is supported by experimental results which show that in typical programs the alignments of about 50% of the pointers can be statically determined. Copyright © 2006 John Wiley & Sons, Ltd.     

基于程序分析的自动化漏洞挖掘工具的研究

研究和设计了一个基于程序分析的源代码漏洞分析与检测工具框架,框架中的各个模块如控制流分析(控制流图的构建、函数调用图的实现及过程内分析与过程间分析等)、数据流分析(求定义引用链、污染数据传播的设计、指针别名分析)、结构分析器、安全调度器、规则构建器,本文主要对代码分析的两个阶段进行了较为详细的介绍,同时对主要采取的过程内和过程间分析算法做了说明。     

Complexity of points-to analysis of Java in the presence ofexceptions

At each program point, points-to analysis for statically typed object oriented programming languages (e.g., Java, C++) determines those objects to which a reference may refer (or a pointer may point) during execution. Points-to analysis is necessary for any semantics based software tools for object oriented systems. Our new complexity results for points-to analysis distinguish the difficulty of intraprocedural and interprocedural points-to analyses for languages with combinations of single-level types (i.e., types with data members only of primitive type), exceptions with or without subtyping, and dynamic dispatch. Our results include: 1) the first polynomial-time algorithm for points-to analysis in the presence of exceptions that handles a robust subset of Java without threads and can be applied to C++; 2) proof that the above algorithm is safe, in general, and provably precise on programs with single-level types and exceptions without subtyping, but not dynamic dispatch, thus, this case is in P; 3) proof that an interprocedural points-to analysis problem with single-level types and exceptions with subtyping, but without dynamic dispatch, is PSPACE-hard, while the intraprocedural problem is PSPACE-complete. Other complexity characterizations of points-to analysis in programs without exceptions are presented, including an algorithm with worst-case bound of O(n⁵ ), which improves over the O(n⁷) worst-case bound achievable from previous approaches of T. Reps et al. (1995) and W.A. Landi and B.G. Ryder (1991)     

过程间并发程序分析不可判定的一个新证明方法

过程间并发程序分析问题是一个不可判定问题,理解这个不可判定问题的来源是发展一个有效的分析算法的基础.现有的证明[1]通过构造三个并发任务的PCP问题实例,证明过程间并发程序分析是一个不可判定问题.利用反射的思想,仅仅用两个并发任务构造该问题的一个PCP问题实例,证明在两个并发任务的情况下,过程间并发程序分析是一个不可判定问题.     

C++指针机制与源文件关联关系的可视化研究

研究了C++中的指针机制、以及指针类型对象(变量)在多个源程序代码文件中关联关系。基于信息提取和结果整理,计算机可视化实现和表示C++中的指针机制和多源程序代码文件的关联关系。研究了抽取结果的存储机制和基于该机制的自动排序源文件引用关系的方法,最后提出了一种手工调整图元布局的算法,作为自动排序算法的补充。对实际代码分析的结果表明该方法利于程序分析并支持对源代码的辅助理解。     

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.