Computation of dynamic program slices for unstructured programs

A dynamic program slice is an executable part of the program whose behaviour is identical, for the same program input, to that of the original program with respect to a variable(s) of interest at some execution position. The existing algorithms of dynamic slice computation use data and control dependencies to compute dynamic slices. These algorithms are limited to structured programs because they may compute incorrect dynamic slices for unstructured programs, due to the limitations of control dependencies that are used to compute dynamic slices. In this paper, we present a novel approach to dynamic slice computation for unstructured programs. The approach employs the notion of a removable block in finding dynamic program slices. Dynamic slices are derived by identifying not only those parts of program execution that contribute to the computation of the value of a variable of interest, but also those parts of program execution that do not contribute to the computation of the variable value. Data dependencies are used to identify contributing computations, whereas removable blocks are used to identify noncontributing computations. We have proved that the presented dynamic slicing algorithms correctly compute dynamic slices. In addition, these algorithms may compute more accurate dynamic slices compared to existing algorithms that use control dependencies. The presented algorithms have been implemented in a tool that supports dynamic slicing for Pascal programs     

面向方面程序的简化动态依赖图切片方法

程序切片是一种重要的程序分析技术,广泛应用于程序的调试、测试与维护等领域。面向方面程序设计作为一种新的软件开发范型,能够实现横切关注点的模块化,其特有的语言元素和功能为切片增加了难度。从静态切片和动态切片两种类型,讨论了面向方面程序切片技术。在此基础上,提出了一种基于简化动态依赖图的面向方面程序切片方法,可以减少动态依赖图中节点和边的数量,生成准确的面向方面程序的动态切片,从而有助于人们更好地对面向方面程序进行分析和理解。     

别名集切片与并行化研究

针对复杂程序的分析问题,提出基于别名集切片的切片级并行技术与并行程序分析技术。利用传统分析算法,在每个切片上并行地进行复杂程序分析,从而实现复杂程序分析的并行化,加快复杂程序分析速度。以SPEC CPU2000/CPU2006中的部分C程序为测试用例进行实验,结果表明,利用别名集切片技术可在4个进程并行情况下,获得3.42的加速比。     

SymPas: Symbolic Program Slicing

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 (SDG-IFDS) 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 336800 IR instructions in size,SymPas is highly size-scalable.     

Dynamic slicing of concurrent AspectJ programs: An explicit context‐sensitive approach

This paper presents a context‐sensitive dynamic slicing technique for the concurrent and aspectized programs. To effectively represent the concurrent aspect‐oriented programs, we propose an intermediate graph called the multithreaded aspect‐oriented dependence graph (MAODG). The MAODG is a dynamic graph generated from the execution trace of a given program with respect to a particular set of values given as an input. Interference dependencies between the statements are shown by a distinguished edge called the interference dependence edge in the MAODG. Based on this intermediate representation, we propose a precise and accurate dynamic slicing algorithm for the concurrent aspect‐oriented programs implemented using AspectJ. The proposed dynamic slicing algorithm is implemented in a slicing tool developed using the ASM framework. Several open source programs are studied and evaluated using the proposed technique along with some existing techniques. The experimentation shows that our proposed slicing algorithm generates slices of the same or smaller size, as compared with the existing algorithms. Furthermore, we found that the slice computation time is significantly less in our proposed algorithm, as compared with the existing algorithms.     

基于敏感路径的隐藏程序切片版权保护技术

研究了程序切片及其分解技术,通过构造软件敏感路径上的程序切片,将软件分解成公开和隐藏两个模块,防止黑客获得原软件的完整拷贝,保护软件的版权。对隐藏模块的执行状态进行透明检测,控制软件的流程,防止用户非法调用隐藏模块中的方法。实例分析表明,基于敏感路径检测的隐藏程序切片技术具有较高的安全性。     

基于数据切片度量JAVA内聚性

面向对象的程序切片在程序分析、程序理解、软件测试和调试以及软件维护方面有着广泛的用途.首先建立了抽象数据切片和类内切片的概念,然后基于这两种切片讨论了JAVA语言中存在的内聚问题,通过分析这些切片与数据、方法、类之间的关系来度量数据、方法以及类的内聚性问题.     

一种用于测试数据生成的动态程序切片算法

介绍了程序切片技术的基本概念，提出了一种基于前向分析的动态程序切片算法，探讨了程序切片在软件测试数据生成中的应用，结果表明可以有效地提高基于路径的测试数据生成效率。     

Better Debugging via Output Tracing and Callstack-Sensitive Slicing

Debugging often involves 1) finding the point of failure (the first statement that produces bad output) and 2) finding and fixing the actual bug. Print statements and debugger break points can help with step 1. Slicing the program back from values used at the point of failure can help with step 2. However, neither approach is ideal: Debuggers and print statements can be clumsy and time-consuming and backward slices can be almost as large as the original program. This paper addresses both problems. We present callstack-sensitive slicing, which reduces slice sizes by leveraging the series of calls active when a program fails. We also show how slice intersections may further reduce slice sizes. We then describe a set of tools that identifies points of failure for programs that produce bad output. Finally, we apply our point-of-failure tools to a suite of buggy programs and evaluate callstack-sensitive slicing and slice intersection as applied to debugging. Callstack-sensitive slicing is very effective: On average, a callstack-sensitive slice is about 0.31 time the size of the corresponding full slice, down to just 0.06 time in the best case. Slice intersection is less impressive, on average, but may sometimes prove useful in practice.     

Hypersliceplorer: Interactive visualization of shapes in multiple dimensions

In this paper we present Hypersliceplorer, an algorithm for generating 2D slices of multi‐dimensional shapes defined by a simplical mesh. Often, slices are generated by using a parametric form and then constraining parameters to view the slice. In our case, we developed an algorithm to slice a simplical mesh of any number of dimensions with a two‐dimensional slice. In order to get a global appreciation of the multi‐dimensional object, we show multiple slices by sampling a number of different slicing points and projecting the slices into a single view per dimension pair. These slices are shown in an interactive viewer which can switch between a global view (all slices) and a local view (single slice). We show how this method can be used to study regular polytopes, differences between spaces of polynomials, and multi‐objective optimization surfaces.     

一种C++程序的分层切片方法

该文介绍了一种C++程序的分层切片方法。通过构造系统程序层依赖图、类层依赖图、方法层依赖图和语句层依赖图,对C++程序进行分层切片,有效地表示了C++中的单重继承、多重继承、多态和动态绑定,该方法比其它C++切片技术更清晰地描述了C++程序中类之间的各种关系和消息传递机制。     

Program slicing with dynamic points-to sets

Program slicing is a potentially useful analysis for aiding program understanding. However, in reality even slices of small programs are often too large to be useful. Imprecise pointer analyses have been suggested as one cause of this problem. In this paper, we use dynamic points-to data, which represents optimistic pointer information, to obtain a bound on the best case slice size improvement that can be achieved with improved pointer precision. Our experiments show that slice size can be reduced significantly for programs that make frequent use of calls through function pointers because for them the dynamic pointer data results in a considerably smaller call graph, which leads to fewer data dependences. Programs without or with only few calls through function pointers, however, show considerably less improvement. We discovered that C programs appear to have a significant fraction of direct and nonspurious pointer data dependences so that reducing spurious dependences via pointers is only of limited benefit. Consequently, to make slicing useful in general for such programs, improvements beyond better pointer analyses are necessary. On the other hand, since we show that collecting dynamic function pointer information can be performed with little overhead (average slowdown of 10 percent for our benchmarks), dynamic pointer information may be a practical approach to making slicing of programs with frequent function pointer use more successful in practice.     

Experimental Evaluation of Program Slicing for Fault Localization

Debugging large and complex software systems requires significant effort since it is very difficult to localize and identify faults. Program slicing has been proposed to efficiently localize faults in the program. Despite the fact that a number of debug systems using program slicing, have been developed, the usefulness of this method to fault localization has not been sufficiently evaluated. This paper aims to experimentally evaluate the usefulness of the program slicing method to fault localization. In order to conduct the experiment, we first developed a debug tool based on program slicing, after which two experimental projects were conducted, in which subjects (debuggers) were divided into two groups. A program that includes several faults is given to each subject of the group. Each subject in Group 1 localizes the faults by using the slicing-based method, whereas in Group 2 each subject localizes the faults by using the conventional debugger-based method. Finally, the effectiveness of program slicing is analyzed by comparing the data collected from both groups. As the results of these experiments, we confirm that the program slicing method is indeed useful to localize program faults.     

A system for debugging via online tracing and dynamic slicing

Dynamic slicing is a promising trace based technique that helps programmers in the process of debugging. In order to debug a failed run, dynamic slicing requires the dynamic dependence graph (DDG) information for that particular run. The two major challenges involved in utilizing dynamic slicing as a debugging technique are the efficient computation of the DDG and the efficient computation of the dynamic slice, given the DDG. In this paper, we present an efficient debugger, which first computes the DDG efficiently while the program is executing; dynamic slicing is later performed efficiently on the computed DDG, on demand. To minimize program slowdown during the online computation of DDG, we make the design decision of not outputting the computed dependencies to a file, instead, storing them in memory in a specially allocated fixed size circular buffer. The size of the buffer limits the length of the execution history that can be stored. To maximize the execution history that can be maintained, we introduce optimizations to eliminate the storage of most of the generated dependencies, at the same time ensuring that those that are stored are sufficient to capture the bug. Experiments conducted on CPU‐intensive programs show that our optimizations are able to reduce the trace rate from 16 to 0.8 bytes per executed instruction. This enables us to store the dependence trace history for a window of 20 million executed instructions in a 16‐MB buffer. Our debugger is also very efficient, yielding slicing times of around a second, and only slowing down the execution of the program by a factor of 19 during the online tracing step. Using recently proposed architectural support for monitoring, we are also able to handle multithreaded programs running on multicore processors. Copyright © 2011 John Wiley & Sons, Ltd.     

一种基于模块单子语义的动态程序切片方法

提出一种基于程序模块单子语义的新动态切片方法--模块单子动态切片.首先通过单子转换器,将切片这一类计算抽象成独立于具体语言的实体：切片单子转换器.然后,将该切片转换器作为模块加载到实际程序中,并给出相应的模块单子动态切片算法.据此,可直接在抽象语法结构上计算动态切片,不必记录程序执行历史;相应单子切片器也无需显式地构造诸如依赖图的中间结构.这种模块化抽象机制使得文中的动态切片算法具有很强的可扩展性和重用性.     

Dynamic Slicing of Petri Nets Based on Structural Dependency Graph and its Application in System Analysis

Petri net models are frequently complex and difficult to understand and modify. Slicing technology is very useful in analyzing programs, and has been widely used in specification level for model reduction. So it is necessary to explore slicing methods for Petri nets. This paper proposes a dynamic slicing technique for Petri nets based on the structural dependency graph (SDG). Firstly, the SDG is constructed from the slicing criterion by a backtracking algorithm. Secondly, based on the SDG and a given marking, the dynamic slice can be acquired. As a case study, the proposed method is applied to a control system, and a simulation tool is developed for validating this method and automatically generating the slice. The algorithms can be useful in automatically identifying the parts of the model that affect a state of interest, and provide the basic technical support for alleviating the difficulty of formal verification and analysis.     

基于简化系统依赖图的静态粗粒度切片方法

基于系统依赖图是计算面向对象程序切片的一个有效方法.但是,系统依赖图的缺点是太复杂,而且在建立系统依赖图的过程中容易出错,一旦出现错误就可能导致切片结果的不准确.通过对系统依赖图进行简化,得到了简化的系统依赖图.它省略了那些表示输入参数和输出参数的结点和概括边.同时,还定义了一种面向对象程序的粗粒度切片概念,讨论了它的性质,分析了它与细粒度切片的关系,并基于简化的系统依赖图计算面向对象程序的粗粒度切片.最后还讨论了切片技术的简单实现.     

多域网络中基于域间时延博弈的端到端动态协同切片方法

针对多域网络中的切片存在域间时延不均的问题,提出了一种基于域间时延博弈的端到端动态协同切片方法（inter-domain dynamic game algorithm,IDGA）。采用博弈论方法将端到端时延约束分配到不同的网络域,通过在域内部署切片来获得相应的博弈收益,采用DDPG算法不断更新博弈策略,最终得到最佳的时延分配比例和切片部署方案。实验表明,该算法与传统的静态分配算法对比有明显优势,与经验迭代的DSDP方法以及DQN-SNAF算法相比,IDGA算法在100个切片请求下,切片部署成功率分别提高了8%和3%左右,同时节点资源利用率提高了5.75%和1.96%左右,在降低部署成本方面也有显著优势。