一种基于逆向程序流的程序切片算法*

传统的程序切片方法一般基于程序依赖图(PDG)和系统依赖图(SDG)的可达性算法,但是在建立PDG和SDG的过程中会计算一些与切片无关的数据依赖,造成时空资源的浪费及切片效率的降低。提出了一种基于程序逆向流的切片算法,它事先建立逆向程序流,再从切片点开始沿逆向程序流扫描程序以获得程序切片,只计算与切片相关的数据依赖,从而提高了切片计算的时空效率。通过实验发现该算法具有一定的可行性和实用性。本算法适用于包括Fortran、C等编程语言在内的命令式程序的切片生成。     

一种基于抽象解释的WCET自动分析工具

利用基于抽象解释的变量值范围传播技术,提出了一种自动分析高级语言程序流信息的方法;并在白盒测试工具NPCA的基础上,利用该方法实现了WCET分析工具NPCA-WCET。     

基于逆向程序流和函数依赖集的程序切片算法

程序切片技术大多是根据程序依赖图(PDG)和系统依赖图(SDG)的图可达性算法来优化得到感兴趣的程序集合,但是构造PDG和SDG需要很大的空间开销。本文提出一种基于逆向程序流和函数依赖集的切片算法,从兴趣点开始扫描逆向程序流来计算程序切片,只计算与切片相关的数据依赖,并且考虑函数调用时切片的计算,提高计算切片的效率。通过实例表明该算法减少了计算程序切片的复杂度,具有一定的可行性和实用性。     

基于GCC关键变量数据流分析算法的程序切片技术

随着程序的规模的扩大和复杂度的提高,通过直接分析源码进行程序切片,变得十分困难。在现有的利用编译优化技术来优化程序切片的方法中,存在无法有效利用程序的编译时信息和编译器的优化技术,以及对语言的支持不完善的问题。为此,分析了GCC编译器在编译时的中间表示,首次提出了基于GCC关键变量数据流分析算法的程序切片技术,以程序的GIMPLE中间表示为基础,以程序基本块为单位,通过迭代求解数据流方程,分析程序基本块内和不同基本块间的关键变量数据流信息。该程序切片技术可以获取源程序中仅与预设目标函数相关的关键变量和关键语句,缩减程序规模。最后通过实验,证明了该算法的可行性。     

采用自然语言的移动机器人任务编程

本文在机器人具备基本运动技能的基础上［1］，采用基于指令教导的学习方法．通 过自然语言教会机器人完成抽象化任务，并以程序体方式保存所学知识，也即通过自然语言 对话自动生成程序流．通过让机器人完成导航等任务，验证所提自然语言编程方法的可行性 ．     

程序切片技术在软件测试中的应用*

基于程序切片的软件测试是一种以程序或程序和需求相结合为基础的测试,它根据程序的不同切片来缩小软件的测试范围、提高软件测试的效率、辅助测试数据的自动生成等.同时由于程序切片不仅考虑了数据依赖和控制依赖,还考虑了程序存在的其他各种依赖关系,使得测试的准确性得到提高.详细阐述了目前存在的各种切片技术及其应用领域,重点探讨了目前切片技术在测试领域中的具体应用.     

用VC++实现卫星数据文件的自动转换

介绍了利用VC＋＋实现数据文件到BMP图像文件的格式转换技术，以及利用注册表编程实现程序自启动和可持续性的方法。该程序最终实现了卫星数据文件到图像文件的自动转换。     

实时系统程序最差情况执行时间(WCET)的分析

事先获知系统中程序最差情况的执行时间(Worst-CaseExecutionTime,WCET),是设计和验证实时系统调度及可调度性分析的前提,也是确定周期性任务是否满足其性能目标,从而发现系统性能瓶颈的基础。本文概述了程序WCET的分析方法,描述了WCET分析的定义和组成,重点总结其中的程序流事实分析方法,并指出程序流事实分析存在的问题和WCET分析的研究热点。     

基于XML文档的图书信息XQuery查询技术

XML与HTML相比在数据管理和格式化组织上具有更大的优越性,XQuery能够有效地查询和处理XML文档.为了查询网上基于XML文档的图书信息,文章设计了一些统一格式的XML文档作为图书信息的数据源,利用XQuery技术,将XQuery查询程序嵌入实现格式控制的JAVA程序中,JAVA程序可以调用并运行XQuery查询程序,查询的结果保存到一个XML文件中,将查询得到的XML文档转换成需要的格式输出给用户.初步实验证明这种方法是可行的并具有较强的实用性,为实现网上基于XML文档的信息查询提供了技术基础.     

并发程序切片原型系统的设计与实现

并发程序切片是并发程序分析的一种重要手段。针对多线程共享变量通信机制,在通过程序分析工具CodeSurfer获取程序基本信息的基础上构造程序可达图,生成以程序状态和语句二元组为节点的并发程序依赖图,实现了基于程序可达图的并发程序切片原型系统。初步实验结果表明,与传统的切片方法相比,采用基于程序可达图的并发程序切片方法,可有效地解决依赖关系不可传递问题,获得高精度的并发程序切片。     

Program Slicing

Program slicing is a method for automatically decomposing programs by analyzing their data flow and control flow. Starting from a subset of a program's behavior, slicing reduces that program to a minimal form which still produces that behavior. The reduced program, called a ``slice,' is an independent program guaranteed to represent faithfully the original program within the domain of the specified subset of behavior. Some properties of slices are presented. In particular, finding statement-minimal slices is in general unsolvable, but using data flow analysis is sufficient to find approximate slices. Potential applications include automatic slicing tools for debuggng and parallel processing of slices.     

别名集切片与并行化研究

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

Program Slicing:Its Improved Algorithm and Application in Verification

Program slicing is a method for automatical program decomposition.This paper presents an improvedslicing algorithm on the basis of static analysis of the control structure of loop statements.The slice obtainedby the new algorithm is guaranteed to be no larger than that obtained by the previous slicing algorithmdeveloped by Mark Weiser.Moreover,the former will be much smaller than the latter for certain kinds ofprograms.In addition,a brief discussion of using slicing in program verification has been given for the sakeof extending the application area of program slicing.     

面向数据库模式变更的代码演化推荐方法

许多软件依赖数据库来存储信息。数据库模式的变更可能导致程序代码中与数据库相关的SQL语句代码不能正常执行,因而找出一种能够直接定位到需要修改的SQL语句代码并推荐出这些代码可能的修改方案的方法是十分必要的。提出的面向数据库模式变更的代码演化推荐方法首先自动检测出软件系统数据库模式发生的变更,随后采用程序切片技术得出与数据库操作相关的程序切片;确定受到数据库模式变更影响的程序切片后,利用源程序转换流程图算法将程序切片转化为程序流程图;根据程序流程图的分支条件得出SQL语句所有可能的特定执行路径;最后采用图映射的方法对每条路径的SQL语句进行变更语句推荐,推荐出新数据库模式下可执行的SQL语句。为了验证该方法的可行性,实现了一个用于自动检测数据库模式变更并能推荐出SQL语句演化后代码的插件工具。     

Actor-based slicing techniques for efficient reduction of Rebeca models

Slicing is a program analysis technique which can be used for reducing the size of the model and avoid state space explosion in model checking. In this work a static slicing technique is proposed for reducing Rebeca models with respect to a property. For applying the actor-based slicing techniques, the Rebeca control flow graph (RCFG) and the Rebeca dependence graph (RDG) are introduced. We propose two different approaches for constructing the RDG, where each approach can be more effective under certain conditions. As the static slicing usually produces large slices, two other slicing-based reduction techniques, step-wise slicing and bounded slicing, are proposed as simple novel ideas. Step-wise slicing first generates slices that overapproximate the behavior of the original model and then refines it, and bounded slicing is based on the semantics of nondeterministic assignments in Rebeca. We also propose a static slicing algorithm for deadlock detection (in absence of any particular property). The efficiency of these techniques is checked by applying them to several case studies which are included in this paper. Similar techniques can be applied on the other actor-based languages.     

Program Slicing-Based Regression Testing Techniques

After changes are made to a previously tested program, a goal of regression testing is to perform retesting based on the modifications while maintaining the same testing coverage as completely retesting the program. This paper presents a novel approach to data flow based regression testing that uses slicing algorithms for the explicit detection of definition-use associations that are affected by a program change. An important benefit of this slicing technique is that, unlike previous techniques, neither data flow history nor recomputation of data flow for the entire program is required to detect affected definition-use associations. The program changes drive the recomputation of the required partial data flow through slicing. Another advantage is that the technique achieves the same testing coverage with respect to the affected definition-use associations as a complete retest of the program, without maintaining a test suite. Thus, the overhead of maintaining and updating a test suite is eliminated.     

基于关键谓词的程序错误定位方法

将程序切片技术应用于程序错误定位可以大量减少需要测试的语句数。提出一种基于关键谓词的程序错误定位方法,从程序中找出能影响输出结果的关键谓词,对该谓词和错误输出语句进行数据切片,并引入代码优先技术。该方法考虑了数据依赖和控制依赖,能实现准确快速的错误定位。     

面向对象软件回归测试技术研究

回归测试的目标之一是在程序修改后,只对进行修改的部分重新测试,从而达到与完全测试相同的测试覆盖.利用数据流或部分数据流技术,对结构化程序进行回归测试的技术已相继提出.随着面向对象方法的逐渐成熟,对面向对象软件测试技术的研究有了迫切的需求.通过分析对象系统的特性,定义了对象之间的依赖关系,通过这个依赖关系,导出测试对象的方法序列,并应用程序切片技术,标识那些受到程序修改影响的测试用例,只有这些测试用例才需要在回归测试中重新执行.最后给出了一完整的对象系统的回归测试解决方案.     

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

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