共查询到16条相似文献,搜索用时 203 毫秒
1.
2.
缓冲区溢出静态分析中的指针分析算法 总被引:2,自引:0,他引:2
提出一个扩展的流不敏感指针分析算法,主要用于缓冲区溢出静态分析,该算法把程序控制流图(CFG)转换为静态单指派(SSA),然后循环调用一个流不敏感指针分析,生成每个指针变量精确的指向集,更新指针变量的定义-引用链中约束信息.在LLVM编译系统下实现了该算法,实验表明其精度和流敏感的指针分析算法相当,但效率高于流敏感指针分析算法,时间复杂度低于流敏感指针分析算法. 相似文献
3.
《计算机应用与软件》2014,(2)
针对当前最优秀的基于包含的指针分析在线优化技术即横向传播和纵向传播方法的不足之处,提出一个改进的算法。首先简要介绍基于包含的指针分析方法及其在线优化技术;其次描述横向传播和纵向传播方法,进而说明它们存在的一些缺陷;然后针对这些缺陷提出一个改进的算法,该算法能够在不损失时间开销的条件下以更小的内存开销实现横向传播,能在纵向传播过程中检测出约束图中所有的强连通分量;最后通过一个实例分析及使用CIL工具进行的实验验证了该改进算法的优越性。 相似文献
4.
5.
6.
指针的指向分析在检测C语言多线程程序的数据竞争中占有重要的地位。Steensgaard提出的流非敏感上下文非敏感的指针别名分析算法,因其执行效率极高的优点被广泛的应用于快速的指针指向分析。但该算法计算结果精度不高,得到的指针指向集往往有误差。针对该不足,引入了Vineet Kahlon的用求最大更新序列来求指针别名的思想,对Steensgaard算法计算出的结果进行了修正。并通过一个实例证明了改进后的算法比先前的算法更精确。 相似文献
7.
8.
由于面向对象程序具有多态性等复杂特性,在软件单元测试中仅凭静态分析难以判断指针和引用指向对象的具体类型,为了解决这一问题,对类的抽象内存模型进行研究,并提出类的操作语义模拟算法;在路径分析时,通过构建和更新抽象内存模型,从而对变量所属类的范围进行限定;对于单元测试,对基于输入域的随机测试进行优化,提出基于路径的随机测试方法,得到输入变量的类型集合;实验表明,类的抽象内存模型结合操作语义模拟算法能够有效提取出路径中类相关的约束,基于路径的随机测试方法比起基于输入域的随机测试方法能够明显提高测试效率。 相似文献
9.
针对传统的数据随机化技术静态分析精度不高的问题,提出一种基于域敏感指针分析算法的细粒度数据随机化技术。在静态分析过程中,首先对中间表示进行语法抽象,得到形式化的语言表示;然后建立非标准类型系统,描述变量之间的指向关系;最后按照类型规则进行类型推断并求解,得到域敏感的指向关系。根据指向关系对数据进行随机化加密,得到经过随机化的可执行程序。实验数据表明,基于域敏感指针分析的数据随机化技术与传统的数据随机化技术相比,分析精度显著提高;处理时间开销平均增加了2%,但运行时间开销平均减少了3%。所提技术利用域敏感的指针分析,给程序带来更少的执行开销,并能够更好地提高程序的防御能力。 相似文献
10.
随着技术的发展,信息物理融合系统(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的高效率及有效性. 相似文献
11.
Efficient online cycle detection technique combining with Steensgaard points‐to information 下载免费PDF全文
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. 相似文献
12.
别名分析对于数据流分析、程序优化和分析工具的实现非常重要.文章提出了一种需求驱动,流非敏感的分析算法来解决指针别名问题.通过构造程序表达式图(PEG)把指针别名问题转化成判断两个指针节点是否是联通的问题,它不同于传统的别名分析方法,它不需要构造别名集合和对其求交集,所以提高了分析指针别名的效率. 相似文献
13.
MOD问题是指在进行过程调用时哪些信息可能在被调用的过程中被修改。针对C语言,本文提出了一种基于流敏感、上下文敏感指针分析结果的MOD分析算法。该算法通过计算表达式在指向图中的左值,得到所有可能被修改的内存位置,从而计算出所有可能在被调用过程中被修改的表达式。我们在SUIF2平台下实现了该算法,得到了预期的实验结果。 相似文献
14.
Ji Wang Senior Member CCF Xiao-Dong Ma Wei Dong Hou-Feng Xu and Wan-Wei Liu Member CCF 《计算机科学技术学报》2009,24(2):347-356
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. 相似文献
15.