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

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

3.
基于有向弧的改进多边形拓扑关系生成算法   总被引:3,自引:0,他引:3  
文章提出了一种基于有向弧段的多边形拓扑关系生成算法,改进了传统算法.算法对每个结点的关联孤段按方位角排序并对这种有序性进行了补充定义,同时为弧段增加两个方向相关的字段,分别表示弧段的方向和是否被遍历过,搜索多边形的同时对遍历过的有向孤段加以标记.本算法避免了多边形的反复搜索和内角的计算,提高了建立多边形拓扑关系的效率.最后,时该算法进行了分析和实例计算.  相似文献   

4.
为了提高现有OpenModelica软件对DAE系统的预处理模块中求强连通分量与拓扑排序部分的性能,提出了基于Kosaraju算法实现的策略.阐述了Modelica软件的实现原理,叙述了拓扑排序相关算法在其中的重要性,分析了现有Modelica 软件中使用的求强连通分量与拓扑排序部分的算法,比较了Tarjan算法的实现方案与Kosaraju算法实现方案.对两种方案进行了比较和分析结果,表明了Kosaraju算法方案的可行性和有效性.  相似文献   

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

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

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

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

9.
相似重复记录检测对于提高数据质量有着重要意义。为了减少检测代价和提高运行效率,基于传统的窗口技术和分块技术,提出一种相似重复记录检测算法。该算法利用关键字段将数据集进行排序和分块,并利用滑动窗口技术限制分块间比对。设计一种多字段排序改进算法,对不同字段的分块共同聚类,优先比较重复密度大的分块对,摒弃聚类较差的分块。该算法减少了检测过程中的数据比较次数,并降低了字段好坏对算法速度的影响。理论和实验分析表明,该算法能有效地提高相似重复记录检测的准确率和时间效率。  相似文献   

10.
以顶点表示活动的网络(AOV网)可用来表示整个工程中各个子工程的先后次序制约关系,利用拓扑排序算法能求得子工程的线性序列--拓扑序列.按此序列安排各子工程,能保证整个工程的顺利完成.传统的拓扑排序算法基于栈结构实现,只能求得实际存在的多个拓扑序列中的一种,削弱了算法的实用价值.文中为了弥补这一缺陷,设计全拓扑排序算法求出了AOV网中实际存在的全部拓扑序列.给出了AOV网的定义及拓扑排序算法思想,分析了传统拓扑算法的不足,提出了一个全拓扑排序求解算法.并讨论了算法中用到的数据结构,以及算法的伪代码实现,通过一个应用实例验证了全拓扑排序算法的实用性和正确性.  相似文献   

11.
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(n5 ), which improves over the O(n7) worst-case bound achievable from previous approaches of T. Reps et al. (1995) and W.A. Landi and B.G. Ryder (1991)  相似文献   

12.
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  相似文献   

13.
14.
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.  相似文献   

15.
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.  相似文献   

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

17.
刘鹏  赵荣彩  庞建民  姚远 《软件学报》2014,25(11):2486-2498
指针分析是数据流分析中的关键性技术,其分析结果是编译优化和程序变换的基础。在基于包含的指针分析算法研究的基础上,对 Narse 优先权约束评估算法中存在的冗余约束评估和优先权评估模型计算开销较大的问题进行分析,以指针的指向集更新信息确定约束评估的候选集,提出了基于指向更新的约束评估算法。采用约束语句间的解,引用依赖和标量依赖构建约束依赖图,通过依赖关系确定约束评估的优先权,提出了基于约束依赖图的优先权算法,简化了既有算法中复杂的优先权评估模型,进一步给出了优化后算法的整体框架。在基准测试集 SPEC 2000/SPEC 2006上进行实验,其结果表明,该算法与Narse优先权算法相比,在时间开销和存储开销上都有明显的性能提升。  相似文献   

18.
We present a demand-driven approach to memory leak detection algorithm based on flow- and context-sensitive pointer analysis. The detection algorithm firstly assumes the presence of a memory leak at some program point and then runs a backward analysis to see if this assumption can be disproved. Our algorithm computes the memory abstraction of programs based on points-to graph resulting from flow- and context-sensitive pointer analysis. We have implemented the algorithm in the SUIF2 compiler infrastructure and used the implementation to analyze a set of C benchmark programs. The experimental results show that the approach has better precision with satisfied scalability as expected. This work is supported by the National Natural Science Foundation of China under Grant Nos. 60725206, 60673118, and 90612009, the National High-Tech Research and Development 863 Program of China under Grant No. 2006AA01Z429, the National Basic Research 973 Program of China under Grant No. 2005CB321802, the Program for New Century Excellent Talents in University under Grant No. NCET-04-0996, and the Hunan Natural Science Foundation under Grant No. 07JJ1011.  相似文献   

19.
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.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号