We use cookies to improve your experience with our site.

SymPas:符号化程序切片

SymPas: Symbolic Program Slicing

  • 摘要: 程序切片是一种重要程序分解技术,可有助于人们更好地理解程序结构以及用途,提高软件开发效率和软件质量。因“上下文敏感计算”在美国商务部出口管制清单中,当前主流的C/C++程序分析/程序切片商业工具CodeSurfer(美国GrammaTech公司核心产品)我们无法使用,且这种经典的基于依赖图(PDG/SDG或超图)程序切片方法也有其固有缺陷,例如:依赖图的构造过程繁杂且易爆炸,而且不能直接回答/查询依赖图中两个节点是否有依赖关系,需要多次遍历整个依赖图(同时每次遍历需要小心选择不同类型的节点和边),所以我们提出了一种基于轻量级上下文敏感依赖分析的符号化程序切片方法SymPas(Symbolic Program Slicing),并基于LLVM实现了SymPas切片器原型工具llvm-slicing。为比较方便,我们利用当前主流依赖图分析方法(包括过程间有限分布子集IFDS方法)首次实现LLVM中间码IR过程间切片器,还扩展实现基于信息流方程的程序切片方法。经在相关基准测试程序集上对比实验,我们SymPas切片方法明显优于当前最快的SDG-IFDS切片方法,其中后向切片的时间成本平均降低了6倍,空间成本平均降低了4倍;同时具有很高的可扩展性;且无需构造易爆炸的SDG图或超图,还可直接回答/查询语句节点间是否存在依赖关系。

     

    Abstract: Program slicing is a technique for simplifying programs by focusing on selected aspects of their behavior. Current mainstream static slicing methods operate on dependence graph PDG (program dependence graph) or SDG (system dependence graph), but these friendly graph representations may be a bit expensive for some users. In this paper we attempt to study a light-weight approach of static program slicing, called Symbolic Program Slicing (SymPas), which works as a dataflow analysis on LLVM (low-level virtual machine). In our SymPas approach, slices are stored in symbolic forms, not in procedures being re-analyzed (cf. procedure summaries). Instead of re-analyzing a procedure multiple times to find its slices for each callling context, we calculate a single symbolic slice which can be instantiated at call sites avoiding re-analysis; SymPas is implemented with LLVM to perform slicing on LLVM intermediate representation (IR). For comparison, we systematically adapt IFDS (interprocedural finite distributive subset) analysis and the SDG-based slicing method (SDGIFDS) to statically slice IR programs. Evaluated on open-source and benchmark programs, our backward SymPas shows a factor-of-6 reduction in time cost and a factor-of-4 reduction in space cost, compared with backward SDG-IFDS, thus being more efficient. In addition, the result shows that after studying slices from 66 programs, ranging up to 336 800 IR instructions in size, SymPas is highly size-scalable.

     

/

返回文章
返回