精华内容
下载资源
问答
  • 本资源包含有资源包含了快速灵活的动态结构测试解决方案的各种资源。
  • 通过加强对本地文件包含(LFI)渗透测试技术的研究,可以帮助渗透测试人员和学生在未来的渗透测试过程中,识别和测试LFI漏洞。在Web程序渗透测试中,利用本文中的技术发现的LFI漏洞是渗透测试中的典型漏洞。此外,在...
  • 基于放电激励方法建立了高温环境下 MEMS微构件动态特性测试系统,该系统主要由激励装置、激光多普勒测振仪、微构件温度控制系统组成。激励装置利用尖端放电产生的激波激励微构件,通过进给机构调节电极间距以改变激励...
  • 动态测试

    2019-09-30 00:58:45
     虽然静态分析技术不需要软件的执行,而从动态分析本身来看更像是一个“测试”。它包含了系统的执行。当软件系统在模拟的或真实的环境中执行之前、之中和之后,对软件系统行为的分析是动态分析的主要特点。动态分析...

    动态测试

     

    1.1 动态分析技术

      虽然静态分析技术不需要软件的执行,而从动态分析本身来看更像是一个“测试”。它包含了系统的执行。当软件系统在模拟的或真实的环境中执行之前、之中和之后,对软件系统行为的分析是动态分析的主要特点。动态分析包含了程序在受控的环境下使用特定的期望结果进行正式的运行。它显示了一个系统在检查状态下是正确还是不正确。

      

      当今,在软件开发过程中有许多动态分析工具。下面给出了这些工具的分析。

      表1、动态分析工具

     

    1.2 常用的白盒动态测试工具

    常用的动态分析工具功能:

    例:测试覆盖率分析:

      logiscope 的 testchecker 工具就是采用了覆盖率分析的思想,对代码的覆盖率进行统计分析的。

      跟踪:

      以调试器为例,调试器在调试程序的过程中,可以将已经执行的代码中的变量的信息记录下来,通过 watch out 窗口输出欻里。

      调整:

      模拟:

      断言检查:

    调试的一种手段

     

    1.3 常用的黑盒动态测试工具

     

    转载于:https://www.cnblogs.com/Boohee/p/5701145.html

    展开全文
  • 针对钻孔瓦斯涌出初速度法存在的问题,提出了钻屑与瓦斯动态分离技术,采用了理论分析、正交实验与单指标极差分析的方法对瓦斯泄漏量的运移规律与影响因素、泄漏率曲线进行了研究.研究结果表明:钻屑与瓦斯动态分离技术...
  • 软件测试 PPT 北大青鸟 软件测试技术 信息系统测试
  • 软件测试技术

    2011-12-27 16:48:02
    软件测试技术基础,包括软件测试技术分类,软件测试阶段,软件测试模型,软件开发模型简介
  • 工程试验技术

    2012-02-22 15:09:55
    工程实验技术 适合学习机械类的学者,包括试验规划、相似理论和信号分析等
  • 静态测试动态测试

    万次阅读 2015-09-19 13:16:21
    静态测试包含哪些内容? 静态测试:静态测试是指不运行被测程序本身,通过分析或检查源程序的语法、结构、过程、接口等来检查程序的正确性。其被测对象是各种与软件相关的有必要进行测试的产物,是对需求规格说明书...

    A。什么是静态测试?静态测试包含哪些内容?

    静态测试:静态测试是指不运行被测程序本身,通过分析或检查源程序的语法、结构、过程、接口等来检查程序的正确性。其被测对象是各种与软件相关的有必要进行测试的产物,是对需求规格说明书、软件设计说明书、源程序做结构分析、流程图分析、符号执行来找错。静态测试可以手工进行,充分发挥人的思维的优势,并且不需要特别的条件,容易展开,但是静态测试对测试人员的要求较高,至少测试人员需要具有编程经验。

    静态测试包含的内容:

    静态测试主要包括各阶段的评审、代码检查、程序分析、软件质量度量等,用于对被测程序进行特性分析。其中评审通常有人来执行;代码检查程序分析、软件质量度量等即可人工完成,也可用工具来完成,但工具的作用和效果相对更大更好一些。

    B什么是动态测试,包含哪些分类

    动态测试:通过运行被测程序来检查运行结果与预期结果的差异,并分析运行效

    率和健壮性等指标;这种方法包括三部分:构造测试用例、执行程序、分析程序的输出结果。

    动态测试分类:可从不同角度进行分类。

    1)从是否关心软件内部结构和具体实现的角度划分,可分为“白盒”测

    试、“黑盒”测试、“灰盒”测试。

    2)从软件开发过程的角度划分,可分为:单元测试、集成测试、确认测

    试、系统测试、验收测试、回归测试。

    3)从测试执行是否需要人工干预的角度划分,可分为:人工测试、自动

    化测试。 

    4)从测试实施组织的角度划分,可分为开发方测试、用户测试(β测试)、

    第三方测试。

    C白盒测试、黑盒测试灰盒测试

    白盒测试:“白盒”测试又称为结构测试或逻辑驱动测试是一种按照程序内部逻辑结构和编码结构设计测试数据并完成测试的一种测试方法。

    黑盒测试:又称功能测试或数据驱动测试

    把测试对象当作看不见内部的黑盒,在完全不考虑程序内部结构和处理过程的情况下,测试者仅依据程序功能的需求规范考虑,确定测试用例和推断测试结果的正确性.

    灰盒测试:是一种综合测试法,它将“黑盒”测试、“白盒”测试、回归测试和变异测试结合在一起,构成一种无缝测试技术。既基于程序运行时的外部表现又结合程序内部逻辑结构来设计测试用例,执行程序并采集程序路径执行信息和外部用户接口结果的测试技术。

    D动态白盒测试、静态白盒测试

    静态白盒测试测试主要包括代码的检查,通过测试人员仔细阅读代码来检代码和设计的一致性,代码的可读性,代码是否循序了相应的标准、逻辑表达是否正确,结构是否合理等。而动态白盒测试要在Host环境或者Target环境中实际运行软件,并有测试用例的设计与执行,和结果的分析


    展开全文
  • 编译技术试验

    2016-04-06 18:51:44
    资源包含完整工程,测试通过,主要包含4个试验内容:词法分析器,递归下降语法分析器,算符优先语法分析器,LR(K)通用分析器
  • 动态摄像技术原理及评价

    千次阅读 2015-09-14 16:29:51
    [摘要] 宽动态摄像机成为安防技术的热点已经很长时间了,厂家也都有把它作为主要的卖点,但是对于宽动态摄像机在技术上深入的分析却很少。通常认为:实现宽动态技术越复杂、技术指标(数值)越高,摄像机的图像效果...
    
    [摘要] 宽动态摄像机成为安防技术的热点已经很长时间了,厂家也都有把它作为主要的卖点,但是对于宽动态摄像机在技术上深入的分析却很少。通常认为:实现宽动态的技术越复杂、技术指标(数值)越高,摄像机的图像效果就越好,摄像机的应用范围就越广。其实不然、摄像器件适应景物照度的能力是有限度的,因此可实现的动态范围是有限值的;同时,人眼视觉特性可以适应(接受)的动态范围也是有限度的。
      宽动态摄像机成为 安防技术的热点已经很长时间了,厂家也都有把它作为主要的卖点,但是对于宽动态摄像机在技术上深入的分析却很少。通常认为:实现宽动态的技术越复杂、技术指标(数值)越高,摄像机的图像效果就越好,摄像机的应用范围就越广。其实不然、摄像器件适应景物照度的能力是有限度的,因此可实现的动态范围是有限值的;同时,人眼视觉特性可以适应(接受)的动态范围也是有限度的。而且,目前宽动态摄像机还没有一个统一的测试方法(标准),各厂家给出的技术指标差别很大、含义不同,没有可比性。笔者曾写过《宽动态技术研修与商榷》一文,文中说明了各种宽动态技术的原理,本文在此基础上对各种上宽动态技术进行比较,并重点说明宽动态技术的测试,以期引起更深入的探讨。

      宽动态的概念

      摄像机的动态范围有两方面的含义:

      一是指摄像设机适应景物照度变化的能力。通常是时间域的概念,比如摄像机可全天(从早到晚)在自然光照下摄取良好的图像。用可以适应的最高照度和最低照度的范围(比值)来表示;另一是指摄像机对一个场景(一幅图像)可以适应其照度差别的能力,这显然是空间域的概念。就是说:对一幅图像而言,保证图像具有适中的反差(灰度变化),可以适应其中最明亮部分和最暗淡部分的照度的变化范围。它的作用是使摄像机可在逆光情况下,或景物中具有过亮、过暗部分时,可以摄取良好的图像,图像各部分的细节都能得到较好的表现。

      在视频监控领域,宽动态就是指:摄像机在空间域中适应照度反差(变化范围)的能力。而“宽”是强调,宽动态摄像机的动态范围很大地超过普通摄像机。

      解决上述两个方面的问题可以采用不同的方法,自然也是分为两类,一是时间域的处理,一是空间域的处理。它们的适用范围不同,效果也不同。

      传统的时域处理

      通过图1可以说明传统的时域处理技术。首先解释图中各种曲线和标记,图中的理论曲线(粗虚斜线)是假设摄像器件可以适应无限范围的照度时,摄像器件的输出曲线,景物照度与图像信号输出呈线性。但摄像器件只能适应有限范围的照度,特别是当照度高到一定值后,器件会出现饱和现象。既摄像器件有最大输出的限值(图中水平细虚线),表示摄像器件的输出不能超过这个限值。这是宽动态限值的根本原因。

    \

      根据摄像器件的技术能力,并结合人眼的视觉特性,电视标准把摄像机视频输出的图像信号0.7V时,摄像器件的输出定为最大输出。实际曲线是的摄像器件输出经各种技术处理之后的综合结果(是摄像机视频输出的等效表示)。主要技术有:

      1、Y校正、AGC(自动增益控制),都是传统时域处理的电路技术。前者工作在低照度段,为了补偿电视机显像管电/光转换特性的非线性失真,因此、具有提高摄像机灵敏度,提升低照度段的图像亮度,改善图像质量的作用。一般有3dB的调节范围;后者、通过电路增益的自动调节,使得在一定照度变化范围内,摄像机图像信号保持稳定的输出。AGC通常工作在中等照度段,具有15-18dB的调节能力。

      2、光圈调节,通过改变摄像机镜头的光栏孔径来调节进光量,从而调节摄像器件的图像信号输出。检测摄像机输出信号的幅度,用以产生镜头光圈电机的驱动电压来调节镜头的孔径,就是自动光圈镜头。它是对图像整体(亮度)的调节,范围由镜头的最大光圈与最小光圈之比来度量(数值是两者比值的平方),最高可达10万倍。

      采用这样的镜头,摄像机可以适应全天室外自然环境的应用。自动光圈的调整方式有平均值和峰值两种,实质上是控制电路基准(参考)值设定方式的不同。前者是以整个图像的平均亮度为基准,后者则是以图像中的最高亮度为基准。大多数情况应设在平均值方式;如图像中有过分明亮的部分,又是观察者注意的内容,设在峰值方式为宜,但它压低了图像较暗部分的亮度,会使其细节不能表现出来(见图2)。

      3、电子快门,利用CCD器件的溢出功能,改变器件的曝光时间来调节摄像机的输出。它不是调节进光量,而是调节曝光时间,因此,称为电子快门。摄像机的电子快门可以人工设置,也可能自动调节,工作原理与自动光圈相同。调节范围就是标准曝光时间与可以设定的最小曝光时间的比值,一般为几百倍。摄像机标准曝光时间是由电视制式和CCD积累方式决定的,通常为1/50s(20ms),目前摄像机最小快门可达1/20000s。

      空间域处理

      显然,时域处理技术可以有效的解决动态范围第一个方面的问题,但对第二个方面问题作用不大,图2可以清楚说明这一点。

    \

      曲线1是自动光圈或电子快门产生的效果,可以看出:它线性地改变了整个图像的特性曲线,而扩大了适应照度变化的范围,但对一幅图像照度反差的调节却很小,而且,在抑制高照度部分时也压低了低照度部分。

      要想实现宽动态,曲线2最佳的,既要抑制高照度部分,又要增强低照度部分。这是上述技术不能完成的,必须采用新的空间域处理的宽动态技术。

      宽动态技术

      安全需求的特殊性在于:要求摄像机能在恶劣环境下获得有效的图像,它包括在低照度下摄取图像,也就是高灵敏度;更重要的是能同时表现出一幅图像中高度照度部分和低照度部分的细节。解决这个问题采用时间域处理是不行的,必须对图像进行空间域的变换;同时,应在摄像器件的光电转换过程中进行,不能在图像信号处理过程中进行,既宽动态技术必须以摄像器件为基础(根据其技术特点)来实现。目前应用较多的宽动态技术主要有:

      背光补偿

      背光补偿是最早应用的宽动态技术,它是将一幅图像进行分区域(依其照度来划分)的处理,通过设定不同的亮度控制阈值,来突出图像各区域的细节。目前摄像机还普遍采用这种技术。

      它对表现图像中亮背景下低亮度部分的细节很有效,故称为背光补偿。反之则不佳、因为在图像信号处理时,图像高亮度部分的细节已经丢失了。

      双曝光技术

      通过CCD曝光控制与图像信号处理相结合,可以同时得到图像高照度部分和低照度部分细节的一种方法,采用通常的CCD芯片就可以实现。如针对低照度部分,采用10ms固定曝光,针对高照度部分,采用高速快门曝光(曝光时间随照度调节,如图3上所示),两次曝光形成的图像信号经过运算生成最终的输出信号。这种方式可以得到不错的效果,但也有不足,它降低了低照度部分的曝光量(比正常图像低了一倍),使得暗部的图像质量下降。还有,在一场期间进行两次曝光,要求CCD进行两次电荷转换(转移速度加倍),也是不利于摄像机电路的设计。但它不增加总的曝光时间,图像信号运算所产生的延迟不会对运动图像产生影响。

      双曝光方式还可在两帧图像进行(如图3下所示),一帧采用标准快门(20ms),生成一帧图像信号存贮在存贮器里,下一帧采用高速快门曝光,生成另一帧图像也存在存贮器中,它的作用是获得高亮度部分的细节(在上场图像已丢失)。两者经DSP运算形成最终的输出图像。由于它加倍了总的曝光时间,会影响高速运动图像的清晰度,但它对图像低亮度部分有增强作用(未完,后续请见下期)。

    \

      下期将给大家带来宽动态多重取样技术等内容的分析及介绍,敬请期待。

    展开全文
  • 内容有交换概论,交换技术基础,信令系统,分组,智能网以及一些试验
  • 软件测试实战-测试技术模型整理,思维导图xmind文件,包括测试技术分类系统、启发式方法、测试先知、漫游测试、快速测试、情景测试、多样选择测试技术,综合整理了多个测试技术
  • ADC静态测试的方法已研究多年,国际上已有标准的测试方法,但静态测试不能反映ADC的动态特性,因此有必要研究动态测试方法?动态特性包括很多,如信噪比(SNR)?信号与噪声+失真之比(SINAD)?总谐波失真(THD)?无杂...
  • 软件测试技术.xmind

    2021-04-18 11:09:46
    软件测试技术的思维导图,包括软件测试技术定义,分类,测试的流程,相关工具等知识。初学软件测试小白可以看看这个有了解,思维导图也包含相关的网页链接,本人也是尽可能包含很多知识。
  • 程序动态切片技术研究

    千次阅读 2016-08-31 21:16:06
    程序切片技术是一种重要的程序分析技术,广泛应用于程序的调试、测试与维护等领域。程序切片主要通过寻找程序内部的相关特性,从而分解程序,然后对分解所得的程序切片进行分析研究,以此达到对整个程序理解和认识的...

    摘 要

    程序切片技术是一种重要的程序分析技术,广泛应用于程序的调试、测试与维护等领域。程序切片主要通过寻找程序内部的相关特性,从而分解程序,然后对分解所得的程序切片进行分析研究,以此达到对整个程序理解和认识的目的。而动态程序切片主要是指在某个给定输入的条件下,源程序执行路径上所有对程序某条语句或兴趣点上的变量有影响的语句。

    面向对象技术仍是目前软件开发方法的主流,其中封装、继承、多态、并发等特征都为程序的理解与分析提出了新的问题。本文在程序的分析评测中引入使用基于依赖图的程序切片技术,实现其切片功能,解决在程序理解、程序复杂性度量、程序转换和评测中遇到的问题。

    本文采用一种基于依赖图的面向对象的动态程序切片方法,核心算法是以静态程序的程序依赖图为基础,先从程序依赖图里提取出对应给定执行历史的数据依赖节点和控制依赖节点,使用图可达性算法,计算得出可达语句集,从而获得所需的动态切片,对程序进行理解分析。 

    【关键词】:数据依赖、控制依赖、程序依赖图、程序切片、动态切片 

    Abstract

    Program slicing is an important program analysis techniques, widely used in debugging, testing and maintenance and other fields. Program slicing within the main 

    program by finding the relevant features to break down program, and then proceeds to the decomposition of the analysis of program slicing, in order to achieve the 

    overall objective of understanding and awareness programs. The dynamic program slice is the main input in a given condition, the source of all the program execution 

    path of a statement or point of interest on the variable impact statement. 

        Object-oriented software development method is still the mainstream, including encapsulation, inheritance, polymorphism, concurrency and other features are the 

    understanding and analysis of the program raised new problems. In this paper, the introduction of evaluation procedures for the analysis of dependence graph-based 

    program slicing techniques to achieve its slice function to solve the program comprehension, program complexity metrics, program transformation and evaluation of 

    problems encountered.

    This paper, a dependency graph based on dynamic program slicing of object-oriented approach, the core algorithm is the program that rely on a static picture shows 

    the base, starting with the program dependence graph to extract the corresponding implementation of the history of a given node and the control dependence data 

    dependence Nodes, using the graph accessibility algorithm calculated statements set up to obtain the necessary dynamic slicing, program understanding of the analysis.

    【Key words】:DD,CD,PDG,Program Slicing,Dynamic Slicing 

    目  录

    摘 要 I

    Abstract II

    第一章 绪 论 

    第一节 课题研究目的和意义 

    第二节  研究内容和本文结构 

    第二章 程序切片技术 

    第一节 程序切片技术的概述 

    第二节 切片技术的应用 

    第三章 动态程序切片技术 

    第一节 动态切片法产生的背景及现有算法 

    第二节 动态程序切片实现算法 

    第四章 动态程序切片系统设计 

    第一节 系统概要设计 

    第二节 详细设计 

    第三节 实例分析 

    第五章 系统的实现环境和运行结果的分析 

    第一节 开发与运行环境 

    第二节 系统输出 

    第六章 结束语 

    第一节 本文的主要工作 

    第二节 展望 

    致谢 

    参考文献 

    附录 

    附录A核心代码 

    附录B 英文原文 

    附录C英文翻译 

    附录D

    第一章 绪 论

    第一节 课题研究目的和意义

    软件危机曾经是软件界甚至整个计算机界最热门的话题为了解决这场危机,软件从业人员、专家和学者做出了大量的努力。现在人们已经逐步认识到所谓的软件危机实际上仅是一种状况,那就是软件中存在故障,正是这些故障导致了软件开发在成本、进度和质量上的失控。故障是软件的属性,而且是无法改变的,因为软件是由人来编写的,所有由人做的工作都不会是完美无缺的。

    软件测试就是“为了发现故障而执行程序的过程”,其根本目的就是尽可能地消除软件中的故障,使得软件在正式投入使用之前,软件中的故障密度达到尽可能低或者可以接受的程度。软件测试是软件生命周期中的重要一环,在当前的软件开发过程中发挥着越来越重要的作用。统计表明,在典型的软件开发项目中,软件测试工作量往往占软件开发总工作量的40%以上;在软件开发的总成本中,用在测试上的开销要占到50%左右。

    软件测试的实质是根据软件开发各阶段的规格说明和程序的内部结构精心选取一批测试数据,形成测试用例,并用这些测试用例去驱动被测程序,观察程序的执行结果,验证实际运行结果与期望结果是否一致,然后做相应的调整。可见,测试数据生成是软件测试的核心与关键。

    白盒测试(结构测试)一般是根据被测程序的内部结构设计测试用例,具有很强的理论基础。这种结构测试要求对被测程序的结构特性做到一定程度的覆盖。路径覆盖是一种相对比较强的覆盖标准,要求生成足够多的测试数据,尽可能覆盖所有程序路径。但是,实际中往往会出现这样的情况:多个测试用例执行的是同一条程序路径,而有的程序路径则从未被执行过。因此,探讨一种有效的手段,以辅助基于路径的测试数据生成,有着很现实的意义。

    第二节  研究内容和本文结构

    本文在理解M.Weiser的切片算法的基础上,根据H.Agrawai等人提出的基于静态程序依赖图的算法,编写程序,最终实现切片系统。并对程序切片进行测试分析。

    本文的第一章简要介绍本课题研究的背景、意义以及关于切片系统的实现目标;第二章主要介绍程序切片的技术概述和应用发展;第三章则是动态程序切片的具体算法设计;第四章关于动态程序切片系统设计的介绍;第五章则是本系统的开发环境和运行结果分析;第六章则是对本文的总结以及展望。 

    第二章 程序切片技术

    第一节 程序切片技术的概述

    程序切片技术是M.Weiser在他的1979年的博士论文中首次提出的一种程序分解技术。主要通过寻找程序内部的相关特性,从而分解程序,然后对分解所得的程序切片进行分析研究,以此达到对整个程序理解和认识的目的。后来在1981年和1984年,M.Weiser博士又发表了两篇论文对这种技术进行推广和完善。后来切片技术引起了研究者们广泛的关注,由于它起到了其他技术无可替代的作用,因此可以说是程序分解领域的一场大变革,无论在程序的分析和理解、调试还是测试和维护过程都起到了巨大的作用,另外切片技术还在硬件描述语言和其他规约语言以及形式化模型等方面的分析有至关重要的作用,因此它的研究具有极其重要的理论和实际意义。

    M.Weiser博士首先在1979年定义了程序切片的概念:程序中的某个输出只与这个程序的部分相关语句以及控制谓词有关系,因此如果删除其他的语句或者控制谓词将对这个输出没有任何影响。也就是说,对于一个特定的输出,源程序和对于删除不相关的语句和控制谓词后所得的程序是作用相同的。其形式化定义如下:

    把满足如下两个条件的切片称为M.Weiser切片:第一,一个程序切片需要对应一个切片准则,用<n,V>表示,其中n指程序中的某个兴趣点,一般指一条语句,V表示在这条语句使用的变量的集合。第二,程序P的切片s可以通过在P中删除零条或者多条语句后得到,且保证程序P和所得的切片S关于切片准则的作用是相同的。

    当时,M.Weiser博士把只与某个输出相关联的语句和控制谓词构成的程序称之为源程序的静态切片。由此可见,一个程序的切片大多数是源程序的一个子集,这个概念准确的说其实就是程序切片的一个核心思想。

    后来随着研究的发展,研究者们对M.Weiser博士程序切片的概念进行了扩展,由于程序切片不一定都是可执行的,因此又包含了不可执行的切片思想,这也是一种静态切片,这样就丰富和发展了程序切片的内涵。随后,KorelLaski又提出了动态切片的概念,它只考虑程序的某个特定执行情况,程序中的信息如数组、指针和循环依赖关系都可以在程序执行时动态确定。因此,动态切片与静态切片相比结果更加的准确。

    在程序切片技术二十几年的发展过程中主要经历了如图2.1所示的四个阶段

    图2.1 程序切片技术的发展历程

    第一个阶段是基于数据流方程的切片阶段,这其实就是M.Weiser博士提出切片概念的阶段,主要使用了基于控制流图的数据流方程来计算程序切片。

    第二个阶段是基于依赖图的程序切片阶段,这一阶段产生了对程序切片提出了很多新的概念和算法。首先,Ottenstein等人在提出了基于程序依赖图的图可达性算法,并可以计算过程内后向程序切片,接着又提出了前向切片的概念和算法,以及基于依赖图的两步遍历图的可达性算法。最后KorelLaski提出了动态切片的概念和算法。

    第三个阶段是面向对象的程序切片阶段,这一阶段是伴随着面向对象的高级程序语言的发展而产生,在1996M.J.Horrald等人首次使用类依赖图来扩展系统依赖图,从而表示面向对象的c++程序,并通过改进的两步遍历图可达性算法来计算程序的切片。随后Christon Steindl在1999年通过对各种数据流以及控制流的计算,提出了面向对象程序切片计算的解决方法,起到了很重要的作用。

    最后一个阶段是程序切片变体阶段,这一阶段出现了各种程序切片的变体形式,例如砍片、削片、层次切片等等,这些都极大地促进了程序切片技术的迅速发展。

    通过上面程序切片的发展阶段可以看出程序切片有很多种,主要有静态切片和动态切片,前向切片和后向切片,规约切片,削片,砍片,无定型切片等等。这些种类其实本质都是一致的,也是随着发展阶段一步步演化而来的。

    由于本文主要使用到动态切片,因此这里主要对与之相关的静态切片和动态切片以及前向切片和后向切片作简要介绍。后文中将详细分析动态切片。

    如果在计算程序切片时不考虑程序的具体输入,计算对某个感兴趣点影响的语句和谓词集合,这样得到的切片就是静态切片。其切片准则为<n,V>。

    如果在计算程序切片时考虑程序的某个具体输入,然后计算程序P在这个特定输入。的条件下所有影响V在n点的值的语句和谓词集合,这样得到的切片就是动态切片。其切片准则为<n,V,>。

    后向切片是指构造一个集合aflect(v/n),使得这个集合由所有影响v在n点的语句和谓词组成。例如如果在测试程序时发现了其中的某个错误,我们就需要知道是前面哪条语句或者哪个谓词表达式导致了这个错误,这样也就需要计算程序的后向切片。

    前向切片正好相反,是指构造一个集合affect (v/n),使得这个集合由受到n点的变量V的值的影响的所有语句和谓词构成。前向切片也有广泛的应用,如果对程序的bug修改以后,我们可能想知道这点修改是否会带来其他的副作用,也就是说这点修改会影响后面的哪些语句,这就需要计算程序的前向切片。

    第二节 切片技术的应用

    由于是程序切片,与程序有关,因此毫无疑问在软件的编码和调试阶段用处是最明显的。尤其在调试阶段,当出现错误时通过程序切片可以快速对程序中的错误进行定位,这样引起错误的代码就被限定在这个程序切片里,从而方便了程序员调试。对于软件度量,可以利用软件体系结构的切片技术验证体系结构是否正确,从而保证按照这个体系结构设计出的软件是正确可靠的,同时在设计阶段利用模块间的切片技术也可以设计出高内聚低祸合的模块,从而为软件的重用性起到大的作用。此外,程序切片技术还应用于软件安全方面和软件测试方面。在软件测试中主要用于回归测试,在软件开发过程中,当系统修改了一处或多处后需要对整个软件重新测试,以防止修改不会带来其他模块的问题、一周此工作量是非常大的,而且也会消耗大量的人力物力。由于在回归测试时,软件只有小部分代码被修改,因此只要通过程序切片技术获得源程序中受到修改代码影响的所有其他代码,这样只要对这些受影响的代码进行测试就可以了,这样就给回归测试带来了极大的方便。本文主要采用程序切片技术来自动生成测试用例,也属于程序切片的一个应用之一。

    程序切片技术有着广泛的应用场合,主要应用如图2.2所示:

    图2.2 切片技术的应用 

    第三章 动态程序切片技术

    第一节 动态切片法产生的背景及现有算法

    本文主要研究的是动态切片程序,所以在这里对动态切片再进行细致的介绍。顾名思义,动态切片法是与静态切片法相对应的,它由静态切片法演化而来。在1988年,B.KorelJ.Laski首次提出动态切片的概念,主要由基于数据流方程的静态切片扩展而来。他们认为动态切片是源程序的一个可以执行的子集,在对某个变量输入相同的变量值时切片和源程序将会执行相同的程序路径。后来,1990年,H.AgrawalJ.Horgan又提出了新的动态切片的思想:动态切片主要包含在某个给定输入的条件下,源程序执行路径上所有对程序某条语句或兴趣点上的变量有影响的语句。这两种概念的不同之处在于,前者产生的动态切片比较大,常常包含一些多余不必要的语句,而后者产生的切片较小,而且更加的精确。动态切片法相对与静态切片法有很多优点,首先,由于它只考虑程序在某个特定输入条件下的情况,所以很多如数组下标、指针、循环依赖关系等程序信息可以在动态执行时动态确定,所以相比静态切片结果会更加的精确。其次,在某些场合下,例如在程序调试过程中,处理一次bug时通常只关注在某个输入下执行的路径行为,而不会关注变量所有可能输入导致的行为,所以动态切片比静态切片更加的方便,大大的减少了切片的大小,调试也因此大大缩小了范围。当然,动态切片法也有缺点,由于动态切片需要追踪程序的执行行为和执行历史,所以空间代价较高。

    从动态切片概念的产生发展至今,主要有以下几个动态切片算法。

    1.H.AgrawalJ.Horgan1990年提出的四种计算动态切片的方法。第一种方法是以静态程序的程序依赖图为基础,先从程序依赖图里提取出对应给定执行历史的一个投影图,再利用静态切片法对投影图进行操作,即使用两次图可达性算法,从而获得所需的动态切片。但是这种方法由于常常包含多余的节点,对同一个变量来说某一个节点可能存在很多由该变量引出的数据依赖边,因此计算出的动态切片不够精确。第二种方法类似第一种方法,也是以静态程序的程序依赖图为基础,在程序执行时首先在程序依赖图中标记出产生的依赖边,然后在图中沿着这些标记的边进行遍历,这样由所有标记经过的节点对应的语句集合就构成了动态切片。这种方法改进了第一种方法产生多余节点的问题,但是缺点是却不能处理包含循环结构的源程序。第三种方法不再基于静态依赖图,而是重新提出了一个新图,即动态依赖图:即为执行历史中语句每一次的出现创建一个节点并只对这一次出现有依赖关系的语句添加引出的依赖边。对于不同的程序执行历史,同一个程序有不同的动态依赖图。当建立了程序的动态依赖图之后,先找到执行历史中变量的最后定义所在的节点,然后在图中使用二次图形可达性算法,从而获得变量的动态切片。

    2.B.Korels.Yalamanchih1994年提出的前向计算的动态切片算法。算法的主要思想为把程序看成是若干个基本块,然后通过执行到基本块的出口时判断这个基本块是否应该包含在动态切片中。这种方法虽然不需要建立动态依赖图,因此节省了大量的执行代价和执行空间。

    3.Goswami和Mall在2002年提出的基于压缩的动态程序依赖图的算法。算法的主要思想为首先建立程序的控制依赖子图,然后再通过程序的执行序列和数据流信息建立程序的数据依赖子图,最后生成动态切片

    第二节 动态程序切片实现算法

    一、相关定义:

    这里主要对算法相关的术语和定义作一下介绍,后文将不再解释。动态切片准则用三元组 (v)表示,s为程序中的某条语句,s表示在第k步执行语句Sv是程序变量或变量集,为输入数据。

    定义1:基本模块:指程序中一组连续执行的语句,在模块的开始处控制流

    进入,在模块的结束时离开,而且不能在模块的执行过程中终止或者出现分支。对于基本模块,控制流只能从模块的入口进入,从模块的出口离开。

    定义2:控制流图   (Control Flow GraphCFG):控制流图CFG是一个有向图,该有向图的节点是一个包括唯一入口和出口的基本模块,如果控制流可以从一个模块流入另外一个模块,则这两个模块之间有一条边。可以用四元组表示为G=(NE, EntryExit),其中N是节点的集合,也就是基本模块的集合,E是边的集合,每一条边为一个有序节点对<ninj>,表示从ni执行完以后开始立即执行njEntry表示子程序的入口,Exit表示子程序的出口,程序从入口节点Entrynk的节点序列<n1,n2n3nk>是一条执行路径,其中n1为入口Entry节点,<nini+l> Ei k。

    定义3:DEF:CFG中节点n定义变量的集合,记为DEF[n]

    定义4:USE:CFG中节点n使用变量的集合,记为USE[nl

    定义5:后必经节点:如果从节点n到程序出口节点Exit的每一条路径都经过节点m,则称mn的后必经节点,记为nm

    定义6:控制依赖(CD):CFG中,设和是其中的两个节点,如果满足以下三个条件,则称控制依赖于,,记为CD(,)

    (1)节点到节点之间有一条可执行路径A

    (2)A上除了和外的每一个节点n,节点n:都是它的后必经节点。

    (3)节点不是节点的后必经节点。

    定义7:控制依赖节点集(CDNC):CDNC()表示当前执行的第k步语句s的控制依赖节点集合。

    定义8:数据依赖(DD):CFG中,设和是其中的两个节点,v为一个

    变量,如果满足以下三个条件,则称关于变量v数据依赖于,记为口D(,,v)

    (1)节点,对变量v进行了定义,即vDEF[]

    (2)节点对变量v进行了使用,即vUSE[]

    (3) 存在一条到的可执行路径A,并且在A上除了处没有语句对v进行重新定义。

    定义9:数据依赖节点集(DDNC):DDNC()表示当前执行的第k步语句s的数据依赖节点集合。

    定义10:程序依赖图(PDG):主要由包含控制依赖和数据依赖的控制流图CFG组成。

    定义11:直接前驱:CFG中,如果<,>E,则称为的直接前驱,记为Pre()=。

    定义12:执行历史:由程序实际执行时经过的一系列节点语句所构成。

    定义13:可到达语句:和为程序中的两条语句,如果控制依赖于或者数据依赖于,则称为,的可到达语句,记为accessible()=。

    定义14:程序的循环依赖:,…….. ,为语句s在含有循环的程序Pn次循环执行,则称语句循环依赖于,,记为cyd()=。

    定义15:动态切片:给定一个动态切片准则(v)Dslice(v)指在当前执行的第k步语句s处变量v的动态切片。

    二、实现算法:

    本文根据H.Agrawai等人提出的四种算法中的前两种基于静态程序依赖图的算法,通过程序实际的执行路径上的控制依赖和数据依赖节点以及可到达语句,从而计算出满足给定的切片准则的程序切片。

    算法描述:

    初始化:     For all v V do Dslice (,v)= 

                For all  do accessible()={s}

    依次执行每个之后

    accessible()=accessible()  DDNC()  CDNC()

     if Cyd(s)=   then

    {

    accessible()=accessible()  DDNC()  CDNC()

               For v V do

               If vUse(s)  

    then

    Dslice(,v)=accessible(DDNC())

    End for

    }

    Else

    {

    accessible()=accessible()  DDNC()  CDNC()

    if  

    Cyd()= and  accessible()==accessible()

    then 

    =Cyd ()

    else if  

    accessible(Pre())= =accessible()

    then  

    Pre()=Pre()

    For v V do

       vUse(s) then

    Dslice(,v)=accessible(DDNC())

      End for

    }

     

     

    下图是本系统的流程图:

    图3.1 程序流程图

    算法的主要功能:在确定的源程序的的基础上,给定一个输入即某条语句的动态切片准则(v)以及源程序的程序依赖图,求出数据依赖节点集、控制依赖节点集,进而求出可到达语句最后输出的变量v的动态切片Dslice(v)

    算法分两种情况考虑,设为程序中输入为时当前语句s执行到第k步,vs中被使用,此时如果程序中不存在循环结构,则语句s也就没有循环依赖,即Cyd(s)= ,则只需要计算所有的数据依赖节点集DDNC(),然后计算该节点集里的所有的可到达语句accessible(DDNC()),从而可以得到护的变量v的动态切片为Dslice(v)=accessible(DDNC()。如果程序中有循环结构,并且语句s有循环依赖,例如和之间存在循环依赖,即Cyd()=,这时要首先计算的可到达语句accessible(),然后再分两种情况,第一种情况,如果accessible()accessible()相等时,就可以合并节点和,即合并accessible()accessilile(),第二种情况,如果s的直接前驱节点的可到达语句与s的可到达语句相等,就把ss的前驱节点合并,即合并s和其前驱节点的可到达语句,从而最终得到的变量v的动态切片为Dslice (v)=accessible(DDNC())。 

    第四章 动态程序切片系统设计

    第一节 系统概要设计

    在第三章已经详细介绍了动态切片的技术,而且提出了明确的算法,在本章将阐述动态切片系统的设计与实现,并详细介绍系统中各个模块的功能以及它们之间的关系。

        动态程序切片系统的输入为:源程序、程序依赖图、切片准则。系统的结构示意图4.1如下图所示:

    4.1 程序结构图

    动态切片程序系统的切片准则用一个三元组<V,p,x>表示,其中x表示程序的输入,p表示程序中一条语句,V表示程序中的变量。切片结果包含了当前输入下所有影响p点的V变量值的语句。

    该系统对程序的处理大致如下:

    (1)对于输入的源程序进行代码格式化,以获取符合我们要求的程序;

    (2)对格式化后的用改造后的编译器执行,以此得到程序的执行记录;

    (3)对格式化后的程序进行静态分析,并利用获取的执行记录,生成动态系统依赖图;

    (4)在动态系统依赖图的基础上,根据切片准则,进行切片;

    (5)将切片的中间结果还原为程序形式。

    以下对于每个子系统进行简单介绍:

    代码格式器:由于输入的程序各式各样,很多并不符合系统的输入要求,所以要有一部分专门来处理程序的输入,使之符合系统要求并输出合格源程序,因此定制这个部分来进行系统处理,这部分主要的功能是去除源程序空格,空行,分别不规范写法等。并在下一步,程序编译处理之前做预处理动作,一方面极大的降低编译处理的复杂度,另一方面也可以使得编译处理更加规范化,方便和其他系统进行集成。

    程序编译处理器:程序编译处理是本功能中比较重点的子系统,因为这里的输出直接影响到一下步执行顺序的生成。而且由于编译器的复杂性,所以这里不应该承担太多的功能,因此,这里的实现原则应该为最简化处理,即:只负责源程序执行顺序的输出,不再进行任何其他功能处理。所以,本文在这里将外围功能均由第一个子系统中的代码格式器承担。

    程序分析处理器:这部分主要负责对源程序进行分析,包括找出类中变量定义,类定义。函数定义等,分析各语句之间的依赖关系,包括数据依赖和控制依赖,通过这些分析结果,就可以得到程序依赖图。这里也是比较重要的一部分。这里的结果将会影响到程序依赖图的生成。

    切片生成器:切片生成器是得到切片的核心部分,前面几个子系统都是在为这里的切片生成器做数据准备和预处理动作。它运用前一章节提到的算法,把他们用程序逻辑去实现,最后得到切片结果。它的输入包括依赖图的定义,执行历史顺序,源程序。它的输出应该是包含源程序的一种数据结构的表示。

    切片表示器:切片生成器得到的结果是动态系统依赖图上的一些节点的数据结构表示,所以我们需要把它还原成源程序,用直观、简洁的方式将程序切片展现出来。具体的方法是利用语句的标号和源程序之间的关系得到原来的程序。因为标号是唯一的,利用这个中间的表示,我们就可以在源程序中找到切出来的语句。

    系统实现难点:这个系统中有三个部分比较难于实现,分别是:程序编译处理器,程序分析处理器,和切片表示器。程序编译处理器涉及Java程序的编译处理。由于一般的优秀的商业编译处理器都无法得知源码进行改造,所以这里会尽量使用开源编译器。程序分析处理器和编译处理器一样,一般在编译处理器中都会有实现。这里要实现相应的功能,也可用开源来实现。在这里我采用JavaCC这个开源的程序编译器和分析处理器。

    第二节 详细设计

    由前几章的算法以及上面根要设计的分析可得,整个系统实现主要分为以下几个部分:

    第一部分:读取输入:读取输入包括源程序读取输入以及程序切片准则输入。

    第二部分:程序编译处理:读取源程序后,采用JavaCC进行程序编译,根据切片准则以及源程序生成程序执行历史顺序。

    第三部分:程序分析处理:读取源程序,进行采用JavaCC进行程序分析每个节点的数据依赖和控制依赖。

    1、基本语句控制依赖分析

    语句是程序的基本组成单位,语句间的控制依赖关系在语法分析过程中就可以确定。

    顺序执行语句:此类语句的执行结果不会影响程序的执行流程,如变量声明语句、赋值语句等,此类语句中无谓词出现,不存在控制依赖。

    if语句:如图所示,语句1执行与否,取决于if语句的执行结果,语句1控制依赖于if语句(语句1不一定是一条语句,可能是一个语句块,此情况下,语句1语句块中所有语句控制依赖于if语句)。

     

    图4.2  if语句的流程图和控制流图

    if-else语句:如图所示,语句2控制依赖于if语句,实际上语句1也是控制依赖于if语句,为了后面切片过程的方便,我们看作语句1控制依赖于else语句,else语句控制依赖于if语句。

    图4.3  if-else语句的流程图和控制流图

    while语句:如图所示,语句1控制依赖于while语句。 

    图4.4 while语句的流程图和控制流图

    for语句:同while语句情况相似。

    switch-case语句:此类语句可以看作特殊形式的拥有多个分支的if语句。图中语句1语句2…….语句n控制依赖于switch语句。 

    图4.5  switch-case语句的流程图和控制流图

    2、基本语句数据依赖分析

    类作为面向对象程序中最重要的概念,引入了面向对象程序的许多重要特性,如封装性、继承、多态性等,对类依赖关系的分析是研究面向对象程序切片的基础。

    类成员关系:类成员依赖表示了类与类的成员之间的依赖关系。若类C2中以类C1的对象作为成员,则类C2与类C1之间存在类成员依赖关系。如下示例程序中,类C2成员依赖于类成员m,即类C2成员依赖于类C1

    引用关系:引用依赖关系表示一个类通过另一个类的接口去使用该类(包括成员变量的直接引用与成员方法的直接调用)。如下示例程序中,类C2引用依赖于类C1

    继承依赖:继承依赖表示了类与类之间的继承依赖关系,C1与类C2之间存在继承依赖关系,当且仅当C1C2的一个子类。下面示例程序中,C2继承依赖于C1

    实例化关系:一个类可能实例化其它类的对象。若类C1中直接实例化一个类C2的对象,则称类C1和类C2之间存在实例化关系。下面示例程序中,C2实例依赖于C1

    从对面向对象程序类的依赖性分析,我们可以利用如下的算法得到数据依赖图:

    图4.6  数据依赖子图的建立算法

    第四部分:程序数据依赖节点集(DDNC)控制依赖节点集(CDNC):由上述算法和程序动态数据依赖图可以得到输入程序的数据依赖节点集(DDNC)以及控制依赖节点集(CDNC

    动态程序切片的依赖图是基于程序的执行历史的,在第三部分得到了各个

    节点的控制依赖和数据依赖子图之后,将其根据算法建立源程序的动态语句依赖图和相应的数据依赖节点集(DDNC/控制依赖节点集(CDNC)。

    图4.7  动态语句依赖图的建立算法

    本文旨在研究动态程序切片的求解过程,程序依赖图的的求解并非重点,所以在切片系统中默认程序依赖图已经给出。

    所以需要一个程序引用的常量类,用来代表源程序常量数据,所有的源程序常量以及所需的输入数据(如切片准则,源程序内容等),均由此处定义。程序文件CharData用于实现这个功能。这里显示部分源码:

    public class CharData {

     private static int[][] history = null;

        private static ArrayList<String> programDNC;

    }

    CharData这个类中,数据定义如下:history[][]这个二维数组就定义了程序的历史执行顺序,programDNC 这个ArrayList定义了程序要进行分析的源程序

    这个类中包包含四个方法:

    public static int[][] getHistory( );

    public static void setHistory(int[][] history);

    public ArrayList getProgramDNC( );

    public void setProgramDNC(ArrayList programDNC);

    其中getHistory( )setHistory(int[ ][ ] history) 相配对,用来取得和设置源程序的历史执行顺序;getProgramDNC( )setProgramDNC(ArrayList programDNC)配对,用来取得和设置被分析的源程序,实现这四个方法是为了以后和其他系统对接,以后要连接其他系统,只需要调用相应的set方法,即可改变这里和默认分析数据。

    程序依赖图也由默认定义给出,Tree源码文件用来定义相应的数据结构:

    public class Tree {

    private ArrayList<TreeChild> TreeData = new ArrayList<TreeChild>();

    TreeData 这个ArrayList定义了依赖图的数据结构,为了能更好的表示依赖图,为此定义了一个元数据结构,给出TreeChild元数据结构:

    ArrayList<TreeParent> parents = new ArrayList<TreeParent>();

    private Object data;

    private ArrayList<TreeChild> children = new ArrayList<TreeChild>();

    private ArrayList<String> typeList = new ArrayList<String>();

    parents childrentypeList 三个ArrayList分别定义了依赖图一个节点的父级节点、子级节点、以级子级节点所对应的类型。

    程序运行节点的数据结构表示如下图:

    图4.8  程序运行节点的数据结构

    在图4.8中,每个运行节点都包含N个子节点,其中每个依赖子节点都有其子节点依赖属性其中对每个子节点的依赖类型都做了标注,节点的依赖类型对应该子节点顺序。这样就可以把整个依赖图表示为一个ArrayList结构,其中每个节点都为一个ArrayList,节点的数据结构为多个子结点和节点控制类型组成。 

    图4.9  程序依赖图的数据结构

    整个程序依赖图的数据结构可表示为图4.9,其中每个依赖图内都包含N个源程序节点,每个源程序节点下面又包含Nn>=0)个依赖子节点,其中每个依赖子节点都有其子节点属性

    第五部分:程序可达语句集:由第四部分的DDNC和以及公式accessible()=accessible()+NNDC()+CNDC()可以得到程序的可达语句集。

    可达语句集数据结构如下图:

     

    图4.10  数据结构图

    利用已知的可达语句求解公式,第一步先设计类AccessibleTable,用于得到可达语句数据集,由于可达语句数据集元数据的具有特殊性,如带顺序,和执行历史相关等等,所以为可达语句数据集设计一个元数据类DNCnode,这个元数据类中应该包括源程序以及执行历史顺序等,每个可达语句集内都包含N个可达语句节点,每个源程序节点下面又包含Nn>=0)个DNCnode子节点数据类型,其中每个DNCnode子节点数据类型都有其子节点属性。即:nodeindex nodestep dDNCnodelist cDNCnodelist

    进而建立getAccessibleTable 这个方法是用来得可达语句,getAccessibleTable是这个类的主方法。以下为部分代码片断:

    for (IndexTreeNode cDNCChild : cDNCList) {

                    //求出每个控制依赖节点的可达语句

    for (Object accessibleBefore : accessibleList.get(cDNCChild.getStep() - 1)) {

              accessibleChildList.add((IndexTreeNode) accessibleBefore);

                    }

                }

         ArrayList<IndexTreeNode> dDNCList = node.getdDNCNodeList();

         for (IndexTreeNode dDNCChild : dDNCList) {

           for (Object accessibleBefore : accessibleList.get(dDNCChild.getStep() - 1)) {

              accessibleChildList.add((IndexTreeNode) accessibleBefore);

                    }

                } //自身的TreeChild

         Tree tree = new Tree();

         IndexTreeNode indexNode = new IndexTreeNode();

         indexNode.setIndex(node.getNodeIndex()); indexNode.setTreeChild(tree.getTreeData().get(data.getHistory()[node.getNodeIndex() - 1][0] - 1));

         accessibleChildList.add(indexNode);

    第六部分:程序的切片集:由第五部分的程序可达语句集和公式:Dslice(v)=accessible(DDNC())可以得到程序的切片集合。

    在前面的模块中已经求出了相应的可达语句表,根据求取切片的公式进而求出程序切片。而ShowTest 是整个系统的入口,也是由这里得到具体的程序切片。这个类中只有一个主方法,用来调用程序,得到切片。 

    第三节 实例分析

    因为在算法的主要功能是在确定的源程序的的基础上,给定一个输入即某条语句的动态切片准则(v)以及源程序的程序依赖图,求出数据依赖节点集、控制依赖节点集,进而求出可到达语句最后输出的变量v的动态切片Dslice(v)。而不去考虑如何去具体求出源程序的程序依赖图。所以,本文将选取一个具有代表性的程序,进行具体分析,进而通过动态切片系统求出切片。源程序如下:

     

     

    4.11 源程序

    输入n=2;切片标准:(v=xn=2);

    程序依赖图:

     图4.12  程序依赖图

    输入n=2,程序的执行历史为<>

    由源程序、程序依赖图和执行历史可得:数据依赖节点集(DDNC)控制依赖节点集(CDNC)如下:

    4.1 数据依赖/控制依赖节点集

    节点()

    DDNC()

    CDNC

       
       
     

     
       
       
       
     

     
       
       
       
     

     
       

    然后由上表和公式accessible()=accessible()+NNDC()+CNDC()可得每个节点的可达语句如下:

     

     

     

     

     

     

    4.2 可达语句集

     

    初始化

    可达语句

    accessible()

    1

    1

    accessible()

    2

    2

    accessible()

    3

    1,2,3

    accessible()

    4

    1,2,3,4

    accessible()

    6

    1,2,3,4,6

    accessible()

    7

    12,3,7

    accessible()

    3

    1,2,3,7

    accessible()

    4

    1,2,3,4,7

    accessible()

    5

    1,2,3,4,57

    accessible()

    7

    1,2,3,4,7

    accessible()

    3

    1,2,3,4,7

    accessible()

    8

    1,2,3,4,578

    由于本程序带有循环结构,所以选择程序第一次执行还没有出现循环前的节点作为新的切片标准(,v),此时,n=2.此时的执行历史为<1,2,3,4,6,7,8,3>。这时节点的切片Dslice(,v)=accessible(DDNC()),根据语句可达表,可知accessible(DDNC())=accessible=<2>

    (1) 若accessible()=accessible(),则就将,合并。由此可得,没有可以合并的节点。

    (2) 如果s的直接前驱节点的可到达语句与s的可到达语句相等,就把ss的前驱节点合并,即合并s和其前驱节点的可到达语句。 、可合并 、、可合并。

    4.3 各个节点程序切片

    节点

    Dslice()

    初始化

     
      
      
     

    1,2

     

    1,2,3

      

     

    、、

     
      
     

    123457

    由此可得到切片标准为为(,v=xn=2)时的切片为<123457>即:

     

     

     

     

     

     

     

     

     

     

    4.13 最终生成的切片

    第五章 系统的实现环境和运行结果的分析

    第一节 开发与运行环境

    本系统的开发在配置为2.00GHz2.00G RAMPC上完成;软件环境是Windows xp,使用JDK 1.6.0_17MySQL 5.1.43JAVA语言在MyEclipse 7.5下完成。

    JDKMySQLMyEclipse的安装文件分别可以从其官方网站http://java.sun.com/javase/downloads/index.jsphttp://www.mysql.com/http://www.myeclipseide.com/上下载,采用默认安装方式。完成安装后,需要对环境进行配置。JDK的配置步骤如下:(1)我的电脑-->属性-->高级-->环境变量;(2)新建 JAVA_HOME,设置为C:\Program Files\Java\jdk1.6.0_17JDK的安装路径);(3)新建PATH,设置为C:\Program Files\Java\jdk1.6.0_17\bin;(4)新建 CLASSPATH,设置为C:\Program Files\Java\jdk1.6.0_17\lib

    本系统的测试与开发在同一台PC、同一软件环境下完成。因JAVA具有可移植的特点,最终本系统也可以成功运行于装有JAVA运行环境的PC上。

    第二节 系统输出

    程序在调试成功之后第四章引用的程序实例对程序进行了测试,在输入确定的切片准则的情况下对源程序进行动态切片。

    1、首先对程序进行数据依赖和控制依赖分析,根据算法求出其程序依赖图,进而得到各个节点的数据依赖节点集合控制依赖节点集:

     

     

     

     

     

     

     

     

    5.1  数据依赖节点集合控制依赖节点集

    2、进入系统的下一个功能模块,根据求出的数据依赖节点集合控制依赖节点集计算得出各个节点的可达语句集:

    5.2 可达语句集

    3、最后根据可达语句集得到各个节点的切片:

     

    5.3 程序切片输出结果

     

     

     

     

     

     

     

     

     

     

     

     

     

    第六章 结束语

    第一节 本文的主要工作

    软件测试对于软件尤其是大型软件的开发至关重要,高质量的软件花费的测试代价是相当大的,尤其在测试用例的编写上花费了大量的精力,而且常常生成的测试用例覆盖率不高,对一些判断较多的逻辑程序生成测试用例更是困难,如何在有效地时间提高测试用例生成的效率变得更加的重要。本文主要完成的工作有以下二点:

    1.H.Agrawal等人提出的四种动态算法的方法和过程进行了主要的分析和研究,通过程序实际的执行路径上的控制依赖和数据依赖节点以及可到达语句,从而计算出满足给定的切片准则的程序切片。

    2.通过具体的实例进行分析表明本文提出的动态切片算法是行之有效的。

    第二节 展望

    由于技术上和时间等问题,开发出的工具仍然存在一定的问题和不足,比如,系统的总体设计还不够完善,只能对特定的源程序进行分析,不能对其他程序进行分析;实现的切片系统只能对源程序进行粗粒度的切片,不能切割出更为精细的切片。总体来说,该工具距离实用性还有一定的差距,因此进一步的研究将主要放在以下几个方面:

    1.进一步提高工具的自动化程度,提高工具的效率。例如对可以导入不同的源程序进行分析,甚至可以标出源程序中的错误。另外增加一些相关功能,例如对测试用例生成后生成相应的报告,.并可以用文件形式导出。

    2. 对于多个文件的程序调用问题进行研究,这样工具的应用范围将会显著地扩大。 

    参考文献

    [1]Mark Weiser. Program slicing. Proceedings of 5th International Conference on Software Engineering, pp. 439-449, San Diego,CA, Mar. 1981.

    [2]Glenford J.Myers,Corey Sandler,Tom Badgett,Todd M.Thomas.The Art of

    Software Testing(2nd Edition)[M].2004.

    [3]Clarke L.A system to generate test data and symbolieally exeeute Progrom.IEEE Transaetions on Software Engineering [J]. September 1976; 215-22.

    [4]Huang J C.An~Proach to Program testing Computing Surveys [J]. SeP. 1975.7(3):113-128.

    [5]GloverF,Kelly J,Laguna M.Genetic Algorithms and Tabu Seareh,Hybrids for OPtimizations[J].Computers Opa Res,1995,22(1),111-134.

    [6]W.Miller and D.SPooner.Automatic generation of floating point test data[J].IEEE Transactions on Software Engineering, 2(3):223-226,SePtember 1976.

    [7]B.Korel.Automated software test data generation[J]. IEEE Transactions on Software Engineering,16(8):870-879,1990.

    [8]荚伟,高仲仪.基于遗传算法的软件结构测试数据生成技术研究闭.北京航空

    航天大学学报.1997,23(1):36-40.

    [9]李必信.面向对象程序切片技术及其在软件度量和软件测试中的运用.[D1

    南京大学博士论文.2000.

     

    附录

    附录A核心代码

    一、可达语句数据集求解算法:

    public class AccessibleTable {

         public AccessibleTable(){

        }

         public ArrayList<ArrayList> getAccessibleTable(){

            ArrayList<ArrayList>accessibleList=new ArrayList<ArrayList>();

            GetDNCTable dncTable = new GetDNCTable();

            CharData data = new CharData();

            ArrayList<DNCNode>ndcNodeList= dncTable.getDNCNodeList(data.getHistory());

            for(DNCNode node : ndcNodeList){

                ArrayList<IndexTreeNode> accessibleChildList  = new ArrayList<IndexTreeNode>();

                ArrayList<IndexTreeNode>cDNCList= node.getcDNCNodeList();

            for (IndexTreeNode cDNCChild : cDNCList) {

                    //求出每个控制依赖节点的可达语句

            for (Object 

    accessibleBefore: accessibleList.get(cDNCChild.getStep()- 1)) {

                 accessibleChildList.add((IndexTreeNode) accessibleBefore); 

                    }

                }

           ArrayList<IndexTreeNode> dDNCList = node.getdDNCNodeList();

           for (IndexTreeNode dDNCChild : dDNCList) {

                for (Object 

    accessibleBefore : accessibleList.get(dDNCChild.getStep() - 1)) {

                      accessibleChildList.add((IndexTreeNode)

    accessibleBefore);

                    }

                }//自身的TreeChild

    Tree tree = new Tree();

           IndexTreeNode indexNode = new IndexTreeNode();

           indexNode.setIndex(node.getNodeIndex());

           indexNode.setTreeChild(tree.getTreeData()

    .get(data.getHistory()[node.getNodeIndex() - 1][0] - 1));

         accessibleChildList.add(indexNode);//去除重复记录

    boolean[]  flag = new boolean[8];

           for (int i = 0; i < accessibleChildList.size(); i++) {

                 int index = accessibleChildList.get(i).getIndex();

    //    System.out.println("---------------->" + index);

                 if (flag[index-1]) {

                     accessibleChildList.remove(i);

    i--;

                 }else {

                     flag[index-1] = true;

                        }

                }

                 accessibleList.add(accessibleChildList);

            }

            return accessibleList;

        }/*合并可达语句 

    二、依赖节点集(DDNC)控制依赖节点集(CDNC)的数据集算法:

    public class GetDNCTable {

       ArrayList<DNCNode> dncTable = new ArrayList<DNCNode>();

          /* 数据依赖节点集(DDNC)控制依赖节点集(CDNC)的list */

    public ArrayList<DNCNode> getDNCNodeList(int[][] history){

          Tree tree = new Tree();

          ArrayList<TreeChild> treeChildList = tree.getTreeData();

          String historyTemp = "";

          int j = 1;

          for(int[] i : history){ //已经执行的历史顺序

          historyTemp = historyTemp + i[0] + ":" + j + ",";

          reeChild child = treeChildList.get(i[0]-1);

          DNCNode childNode = new DNCNode();

          childNode.setNodeName(i[0] + "" + j);

          childNode.setNodeIndex(i[0]);

          childNode.setNodeStep(j);

          ArrayList<IndexTreeNode> cList =  tree.getCDNC(child);

          for(int ic = 0; ic < cList.size(); ic++){

          IndexTreeNode ch = cList.get(ic);

          int jtemp = historyTemp.indexOf(ch.getIndex() + ":");

          if(jtemp >= 0 ){

             ch.setIndex(Integer.parseInt(historyTemp.

    (jtemp, jtemp + 1)));//取最近的执行步骤的index

    String[] jStemp = historyTemp.split(ch.getIndex() + ":");

    String sjtemp =  jStemp[jStemp.length- 1];

    .setStep(Integer.parseInt(sjtemp.substring(0, sjtemp.indexOf(","))));

         }else {

             cList.remove(ch);

             ic--;

                    }

                }

         childNode.setcDNCNodeList(cList);

         ArrayList<IndexTreeNode> dList =  tree.getDDNC(child);

    for(int ic = 0; ic < dList.size(); ic++){

             ndexTreeNode ch = dList.get(ic);

             int jtemp = historyTemp.indexOf(ch.getIndex() + ":");

    if(jtemp >= 0){

                ch.setIndex(Integer.parseInt(historyTemp.

    substring(jtemp, jtemp + 1)));//取最近的执行步骤的index

                String[] jStemp = historyTemp.split(ch.getIndex() + ":");

                String sjtemp =  jStemp[jStemp.length- 1];

                ch.setStep(Integer.parseInt(sjtemp.substring(0, sjtemp.indexOf(","))));

             }else {

                dList.remove(ch);

                ic--;

                    }

                }

            childNode.setdDNCNodeList(dList);

    j++;

            dncTable.add(childNode);

            }

            return dncTable;

        }

    }

    三、切片数据集:

    public class GetDslice {

        public GetDslice(){

    }/ *  Dslice(sk ,v)=accessible(DDNC(sk)) */

    publicArrayList<IndexTreeNode> getDsliceNodeList(int index, int step){

           ArrayList<IndexTreeNode>dsliceNodeList=new ArrayList<IndexTreeNode>();

           AccessibleTable accTable = new AccessibleTable();

           // 取得可达语句表

           ArrayList<ArrayList>acciList=accTable.getAccessibleTable();

           GetDNCTable dncTable = new GetDNCTable();

           CharData data = new CharData();

    //取得数据依赖节点集 和 控制依赖节点集

           ArrayList<DNCNode>ndcNodeList= dncTable.getDNCNodeList(data.getHistory())//DDNC(sk)

           DNCNode dsliceNode = ndcNodeList.get(step-1);

           ArrayList<IndexTreeNode>ddncList= dsliceNode.getdDNCNodeList();

      for(IndexTreeNode child : ddncList){

           for(Object accChild : acciList.get(child.getStep()-1)){

               dsliceNodeList.add((IndexTreeNode)accChild);

                }

            }//对求出的结果排序

      for(int i = 0; i < dsliceNodeList.size(); i++){

           IndexTreeNode treeNode = dsliceNodeList.get(i);

           for(int j = i + 1; j < dsliceNodeList.size(); j++){

               ndexTreeNode treeNodeTemp = dsliceNodeList.get(j);

               if(treeNode.getIndex() > treeNodeTemp.getIndex()){

                  if(j+1 < dsliceNodeList.size() && (treeNode.getIndex() < dsliceNodeList.get(j+1).getIndex())){

                       dsliceNodeList.add(j, treeNode);

                       dsliceNodeList.remove(i);

                       break;

              }else if(j+1 >= dsliceNodeList.size()){

                       dsliceNodeList.add(j+1, treeNode);

                       dsliceNodeList.remove(i);

                       break;

                        }

                    }

                }

            }

            return dsliceNodeList;

    }

    附录B 英文原文

    PROGRAM SLICING

    Mark Weiser

    Computer Science Department

    University of Maryland

    College Park, MD 20742

     

    Abstract

    Program slicing is a method used by experienced computer programmers for abstracting from programs. 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 faithfully represent the original program within the domain of the specified subset of behavior. 

    Finding a slice is in general unsolvable. A dataflow algorithm is presented for approximating slices when the behavior subset is specified as the values of a set of variables at a statement. Experimental evidence is presented that these slices are used by programmers during debugging. Experience with two automatic slicing tools is summarized. New measures of program complexity are suggested based on the organization of a program's slices. 

     

    KEYWORDS: debugging, program maintenance, software tools, program metrics, human factors, dataflow analysis

     

    Introduction

    A large computer program is more easily constructed, understood, and maintained when broken into smaller pieces. Several different methods decompose programs during program design, such as information hiding (Parnas 1972), data abstraction (Liskov and Zilles 1975), and HIPO (Stay 1976). These methods are not mutally exclusive, but rather complement one another. Proposed here is another complementary method of program decomposition: program slicing. Unlike most other methods (but see Tarjan and Valdes, 1980), slicing is applied to programs after they are written, and is therefore useful in maintenance rather than design. Unlike design methodologies, working on actual program text allows slicing to be specified pre-cisely and performed automatically.

    Slicing starts with the observation that these are times when only a portion of a program's behavior is of interest. For instance, during debugging a subset of Dehavior is being corrected, and in program modification or maintenance a sub- set of behavior is being improved or replaced. In these cases, a programmer starts from the program behavior and proceeds to find and modify the corresponding portions of program code. Code not having to do with behavior of interest is ignored. Gould and Dronkowski k19/4) report programmers behaving this way during debugging, and a further confirming experiment is presented below.

    *This research was supported in part by the Computer Science Center at the University of Maryland, and by grants from the Air Force Office of Scientific Research and the General Research Board at the University of Maryland.

    A programmer maintaining a large, unfamiliar program would almost have to use this behavior-first approach to the code. Understanding an en- tire system to change only a small piece would take too much time. Since most program maintenance is done by persons other than the program designers, and since 67 percent of programming effort goes into maintenance (Zelkowitz, Shaw, and annon 1979), decomposing programs by behavior must be a common occurence.

    Automatic slicing requires that behavior be speclfied in a certain form. If the behavior of interest can be expressed as the values of some sets of variables at some set of statements, then this specification is said to be a slicing criterion. Dataflow analysis (Hecht 1977) can find all the program code which might have influenced the specified behavior, and this code is called a slice of the program. A slice is itself an executable program, whose behavior must be identical to the specified subset of the original program's behavior.

    Figure 1 gives examples of some slicing criteria and their corresponding slices.

    There are usually many different slices for a given program and slicing criterion, depending on how minimal a slice is desired. The issue of minimality is discussed further below. There is always at least one slice the program itself. The interesting slices are the ones which, compared to the original program, are significantly smaller and simpler.

    The idea of isolating portions of programs according to their behavior has appeared previously. Schwartz (1971) hints at such a possibility for a debugging system. Browne and Johnson (1978) describe a question-answerer for Fortran programs.

     

    Examples  of  Slices

    The ori ginal program:

    1 BEGIN

    2 READ(X,Y)

    3 TUTAL:=0.0

    4 SUM:=0.0

    5 IF X<=1

    6 THEN SUM:=Y

    7 ELSE BEGIN

    8 READ(Z)

    9 TOTAL:=X*Y

    10 END

    11 WRITE (TOTAL,SUM)

    12 END

    Slice on the value of Z at statement 12.

         BEGIN

         READ(X,Y)

         IF X<1

          THEN

          ELSE READ(Z)

             END

    Slice on the value of X at statement 9.

         BEGIN

         READ(X,Y)

         END

    Slice on the value of TOTAL at statement 12.

         BEGIN

         READ(X,Y)

         TOTAL:=0

         IF X<=1

          THEN

          ELSE TOTAL:=X*Y

             END

    Figure 1

    which, through a succession of questions, could bemade to reveal the slices of a program although very slowly. Several on-line debuggers permit a limited traceback of the location of variable references (e.g. Aygun, 1973), and this information is a kind of "dynamic slice".

    Slicing is a source code transformation of a program. Previous work in program transformation has concentrated on preserving program correctnesswhile improving some desirable property of programs. For instance, Baker (1977) and Ashcroft and Manna (1973) both are concerned with adding "good structure" to programs. Wegbreit (1976), Arsac (1979), Gerhart (1975), and Loveman (1977), are more oriented to improving a program's performance.

     

    Slicing  Algorithms

    This section more formally discusses the ideas of a slicing criterion and a slicing algorithm, using the reader's intuitive understanding of machine execution. All proofs have been carried out in an abstract operational model (Weiser 1979). This paper considers the slicing of block-structured, possibly recursive programs written in a Pascal-like language. All variables are assumed to be uniquely named, and all procedures are assumed to be single-entry, single exit.

    The following notation is used throughout this paper. Due to typesetting limitations, square brackets ([...]) are used to enclose superscripted and subscripted quantities. Set notation is expressed as follows. Let A and B denote sets, let f and g be functions whose values are sets, and let C(i) be a finite family of sets indexed by i. Then:

    A union B                           denotes the set union of A and B.

    A intersect B                         denctes the set intersection of A and B.

    f union g                            denotes the function whose value is f(n) union g(n) for each n in the domain of f and g, and is undefined elsewhere.

    UNION C(i)                           denotes the union of all C(i) for each i.

    A slicing_ criterion for a program specifies a window for observing its behavior. A window is specified as a statement and a set of variables. The window allows the observation of the values of the specified variables just before executing the specified statement. If the statement specified by the slicing criterion is executed several times while the program is running, then a sequence of variable values will be observed.

    Identifying statements by numbers and vari-ables by name, a slicing criterion is a pair < i,v>, where i is the number of the statement at which to observe and v is the set of variable values to be observed.

    There are two properties intuitively desirable in a slice. First, the slice must have been obtained from the original program by statement deletion. Second, the behavior of the slice must correspond to the behavior of the original program as observed through the window of the slicing criterion. Both of these informal properties allow several interpretations. The interpretation used here is derived and justified in the next several paragraphs.

    The problem with obtaining a slice by state-ment deletion is that the source code of a programmay become ungrammatical. For instance, removing

    the THEN clause from an IF-THEN-ELSE statement leaves an ungrammatical fragment if the "null" statement is not permitted between THEN and ELSE.Because of their language dependence, detailed consideration of these issues is beyond the scope of this paper. See Arsac (1979) for some approaces. Instead, a flow-graph will be used to represe a program, with each node in the graph correspond ing to a single source language statement. The terms "node" and "statement" will be used inter-changably.

    A flow-graph is a structure G = <N,E,n0>, where N is the set of nodes, E is a set of edges in NxN, and n0 is the distinguished initial node. If (n,m) is an edge in E then n is an immediate predecessor of m, and m is an immediate successor of n. A path of length k from n to m is a set of nodes p(0,p(1), .... p(k) such that p(0) : n, p(k) = m, and (p(i), p(i+l))is in E for all i,0 < i < k-l. There is a path from n0 to every other node in N. A node n is nearer than a node m to some node q if the shortest path from n to q has length less than the shortest path from m to q. A node m is dominated by a node n if n is on every path from n0 to m. An inverse dominator is a dominator on the flow-graph obtained by reversing the direction of all edges and making the final node the initial node.

    Deleting statements in a flow-graph produces a meaningful new flow-graph so long as any group of statements deleted have only a single successor (see figure 2). This restriction ensures that no statement increases its number of immediate successors as a result of statement deletion. The graph transformation following statement deletion is just: All predecessors of any member of a deleted group of statements have the deleted group's unique successor as their new successor.

    Group of statements with a single successor

     

     

     

     

     

     

     

    Nodes C,D, and E form a set with a single successor, F, not in the set. The flow-graph is shown before and after removing this set.

    Figure  2

    The second desirable property of slices is that they duplicate the behavior observable through the window of the slicing criterion. This means observing original program and slice through the "same" window, and not being able to distinguish between them. But how can a slicing criterion for one program (the original) be used to specify a window for a different program (the slice)? A slicing criterion has the form <i,v>. v can be used in both the slice and the original program, of course. However statement number "i" may not even exist in the slice. Therefore, the window for observation of the slice is specified as <SUCC(i),v>. SUCC(i) is the nearest successor to "i" in the original program which is also in the slice, or "i" itself if present. It is easy to prove that SUCC(i) is unique.

    The program and its slice now have corresponding windows for observing behavior. A reasonable requirement for a slice might be that the trajectories of behavior observable through the slice window must be identical to that observable through the original program window for all inputs. Unfortunately this condition is too strong, because it implies the unsolvability of finding slices. Consider the following program skeleton:

    1 BEGIN

    2 READ(X)

    3 IF X=0

    4    THEN BEGIN

             .

             perform infinite loop

             without changing X.

             .

    5   X:=1

    6   END

    7 ELSE X:=2

    8 END

    Let the slicing criterion be the value of X at line 8. A slicing algorithm based on equivalent behavior trajectories for all inputs would necessarily include line 5 unless there were some as- surance that for all input line 5 was never reached. Such a slicing algorithm could be used to determine the termination of an arbitrary procedure by suitably inserting that procedure between lines 4 and 5, and then noticing whether or not line 5 appeared in the slice. But there can be no algorithm to determine if an arbitrary procedure must terminate, and hence no such slicer can exist.

    To fix this problem, the requirement of equivalent projected behaviors can be weakened to be: projected behaviors must be equivalent whenever the original program terminates. This definition is the one intended in the remainder of this paper whenever the phrase "equivalent behavior" is used.

    A similar problem now arises with finding the smallest possible slice. The reader can easily generalize the above example to show that no algorithm can always find the slice with the mini- mum number of statements, because of the impossibility of evaluating the functional quivalence of two different pieces of code. This problem suggests that a practical definition of a minimal slice must avoid exact knowledge of the functions computed by pieces of code. Dataflow information about a program is of this type, and it permits an exact slicing algorithm. The remainder of this section considers the computation of slices from dataflow information alone.

     

    附录C英文翻译

    摘要

    程序切片是有经验的程序员使用的一种方法,用来将程序抽象化。它从一个程序的行为的子集开始,将程序切片减少为能仍旧产生前者行为的最小形式。被缩小后的程序,就成为一个“切片”,它是一个独立的程序,而且能够保证在指定子集行为的领域里完全代表原始程序。

    一般来说,找到一个切片是不可能的。一个数据流的运算法则是用来大致估计(当此行为子集作为一个声明中一系列变量的值是明确的)。实验结果表明这些切片由程序员在调试以排除故障时使用,包括了两个自动切片工具的使用经验。程序的复杂性使得人们用新的方法基于组织去对程序进行切片。

    关键词:程序调试排除故障 程序维护 软件工具 程序特性 人为因素 数据流分析

    简介

    一个大型的电脑程序在切分成小片后是容易构造的,易懂的,并且是容易维护的。在程序设计中,一些不同的方法将程序分解,例如信息隐藏(Parnas,1972),数据提取(Liskov和Zilles 1975),和HIPO(Stay 176)。这些方法不是相互独立排斥的,而是相辅相成的。这里所推荐的是另一种补充的程序切片的方法。不像大多数其他的方法(但是看Tarjan 和Valdes,1980),切片适用于那些写好的程序,因此不是为了设计上有用,而是为了维护是有用。不像设计方法论,它作用于实际的程序文档允许切片精确地指定和自动的执行。

    切片始于观察法,有时仅有一部分的程序涉及。

    *这个研究是支持于马里兰大学的计算研究中心,资助于美国空军研究协会用于科学研究和普通研究伙同马里兰大学。行为是在兴趣下的。比如,当调试排除故障时一个子集的行为正在被修正,在程序修改或维护一个子集行为在改进或替换。在这些情况下,一个程序员从程序行为开始,然后发现和修饰相应部分的程序代码。不相关的代码则被忽略。Gould和Dronkowski(19/4)报道说程序员在调试排错中表现出这种方式,一个论证的实验如下。

    一个程序员若第一次接近代码维护大型的不熟悉的程序大多数最可能必须用这种方法。完全理解一个系统去改变只是一个很小的部分,而且它还会花费很多时间。自从大多数软件维护是由其他个人解决而不仅仅是软件设计者。而且67%的精力花在程序维护上(Zelkowitz,Shaw,和Gannon 1979),按行为分解程序必须是一个普通的事件。

    自动切片需要的行为必须要有一个固定格式的规定。如果相关行为能用一系列特点下变量的值表达,那么这个规格可以说成为一个分片判据。数据流分析(Hecht 1977)可以找到所有那些影响到规定行为的程序代码,这些代码就被叫做程序的一个切片。一个切片是一个可执行程序,它的行为对与规定子集来说必须是独立的。而且有原始程序的特性。

    图1给了一些例子,它们是切片标准和它们相对应的切片。

    一个既定程序和切割标准通常有许多不同的切片,这取决于需要多小的切片。这个最小值的问题将在下面进行讨论。但是通常至少又一个切片,这就是程序它本身。有趣的是切片通常比源程序小而且更简单。

    这种通过程序特性分离程序部分的想法以前就已经出现过。Schwartz(1971)暗示了这个调试排错系统的可能性。Browne和Johnson(1978)为公式翻译程序描述了这样一个问题解答器。

    切片举例

    原始程序:

    1 BEGIN

    2 READ(X,Y)

    3 TUTAL:=0.0

    4 SUM:=0.0

    5 IF X<=1

    6 THEN SUM:=Y

    7 ELSE BEGIN

    8 READ(Z)

    9 TOTAL:=X*Y

    10 END

    11 WRITE (TOTAL,SUM)

    12 END

    Slice on the value of Z at statement 12.

         BEGIN

         READ(X,Y)

         IF X<1

          THEN

          ELSE READ(Z)

             END

    Slice on the value of X at statement 9.

         BEGIN

         READ(X,Y)

         END

    Slice on the value of TOTAL at statement 12.

         BEGIN

         READ(X,Y)

         TOTAL:=0

         IF X<=1

          THEN

          ELSE TOTAL:=X*Y

             END

    Figure 1

    通过一系列问题反映程序切片,虽然比较慢。一些在线调试排错程序允许变量有限的回溯,这种信息是动态切片。

    切片时一个程序源码的翻译的过程。先前程序转化的工作重在保持源程序的正确性的同时改进程序。举一个实例,Baker(1977)、Ashcroft和Manna(1973)都考虑加入一些好结构到成血中去。Wegbreit(1976),Arsac(1979),Gerhart(1975),和Loveman(1977)使之更适应程序,改进程序的性能。

     

    切片法则

    这部分更正式的讨论了切片标准和规则,利用读者对机器运行的只觉得理解。已经在一个提炼操作模型里得到了所有的数据。

    本论文认为切片的块结构,尤其像Pascal一类语言便携的递归的程序。所有的变量有唯一的名称,所有的程序上有单一的出口。以下的注释全文都有使用。由于种类设置的局限性方法,围绕在上标或者下表上使用方括号。标记如下表示。让A和B表示为集合,让f和g设为是变量的集合,设C(i)是有i的属性的有穷集合。那么:

    A union B                           表示A和B的并集

    A intersect B                         表示A和B的交集

    f union g                 表示每个f(n)和g(n)的n的并集,并且没有在任何地方定义

    UNION C(i)                           表示所有每个i的C(i)的并集

     

    一个切片程序的分割标准决定了观察它行为的视窗。一个视窗被视为一个节点和一系列变量。视窗允许在执行特定变量的值。当程序运行时,如果程序准则的声明规定在执行了数次,那么一系列的变量值可以被观察到。

    根据数字和变量的名称识别状态标识,一个切片准则是一组<i,v>,i是要观察的原有状态的序号,v是要观察的一系列不同的变量的值。

    在一个切片里有两个内容让人直观上满意。首先,切片必须从原始程序里删除得到,切片的行为必须和通过切片标准视窗观察到的原始程序一致。这两个非正式内容可以有不同的理解。此处作用的理解方法可以由下面几段得到和验证。

    通过语句的删除获取到一个切片的方法存在的问题便是这种方式下的源代码也许会成为不符合语法规则的。例如,如果在THEN和ELSE之间“空”语句是不允许的,从一个IF-THEN-ELSE语句中去除THEN子句就会留下一个不符合语法规则的碎片。因为他们语言的依赖,这些争议的详细考虑已经超出了这篇论文的范围。参考Arsac(1979)来获取一些方法。取而代之的是,一个流程图将会用来反应一个程序,在图中的没一个节点对应一个单独的语言表述来源。这个“节点”和“表述”将会互换。

    一个流程图是这样一个结构G=<N,E,n0>,这里N代表一系列的节点,E是一系列NxN图的边,n0是最初的节点的区别。如果(n,m)是E中的一条边,n是m的一个直接原有项,m是一个n的直接原有项。一条由n到m的路径的长k就是一系列的节点p(0), p(1)….. p(k)就像p(0)=n, p(k)=m,并且(p(i),p(i+1))是在E中的,对于所有的i,0<i<k-1。在N中,有一条从n0开始到任意其它节点的路径。如果由n到q的最短路径的长度比m 到q的最短长度还短,那么节点n就比节点m离即节点q进。如果你是在每一条由n0到m的路径中的,那么节点m是由节点n控制的。一个相反的控制者是一个控制者在流程图中通过颠倒所有变的方向并且使最终节点变为最初节点获取的。

    只要删除任何一组的语句将只有一个继承物,在一个流程图里删除语句生成一个有意义的新流程图。这个限制确保了删除语句之后语句数量不会增加,语句删除后图转化如下:所有被删除的语句只有一个前项作为新的继承者。一个单独继承者伴随着很多组语句 

     

    节点C,D和E由一个单独的继承者的集合而来,F,并不在集合中。这个流程图向我们展示了在移除集合前后的情况。

    第二个令人满意的特性是它们复制了通过切片标准视窗可观察的行为,这意味着在同一个窗口中查看原始程序和切片的程序,而不能将它们区分开来。但是一个程序(原始程序)的切片标准怎么能用来指定另一个不同程序的视窗呢(切片的)?一个切片准则有形式<i,v>,v可以同时用在切片和程序里,然而,语句序号i可能在切片里不存在。因此,观察窗口被指定为<SUCC(i),v> SUCC(i)是同时存在于程序和切片里最近的继承者,或者有就是i自己。证明SUCC(i)是独一无二的是非常容易的。

    这个程序和它的切片现在有相应的窗口用来观察它们的行为。对于一个切片,一个合理的需求可能通过切片窗口是可以观察到它的行为轨迹,它们必须和观察到的原始程序窗口中所有的输入相一致。不幸的是这种情况是太强大,因为它意味着找到切片是不可行的。考虑到以下程序的纲要:

    9 BEGIN

    10 READ(X)

    11 IF X=0

    12    THEN BEGIN

             .

             perform infinite loop

             without changing X.

             .

    13   X:=1

    14   END

    15 ELSE X:=2

    16 END

    把第8行中的切割标准设为值x,一个基于所有的输入程序都相等的切片规则,必须包含第5行,除非保证第5行的输入程序永远无法完成。通过合理输入第4行和第5行,并注意第5行是否出现在切片中,这样的切片规则可以用来发现并终止一个任意的程序。但是如果一个任意的程序必须终止,不能没有规则的去判定,因此,这样的一个切片是不存在的。

    要想解决这个问题,等价的计划行为可以减弱为:无论何时原始的程序终止,计划行为必须是一致的。无论何时“等价的行为”短语被使用,这个定义在本篇论文意指在剩余物中。

    一个类似的问题现在出现在寻找最小可能的切片中。读者可以很容易的概括以上的例子来说明没有运算法则经常可以找到最小数量的语句的切片,因为评估两个不同的程序片段的功能的一致性是不可能的。关于一个程序数据流信息是这个类型的,而且它允许一个精确的切片运算法则。这个部分剩余物考虑了数据流信息独立的切片的估算。 

     

    附录D

    一、 程序切片相关知识理解与掌握:

    动态程序切片根据程序的输入,从源程序删除零条或多条语句,得到对最终结果有潜在影响的源序子集 ,可用于程序调试、程序理解、软件测试和软件维护等方面。

    程序切片是一种代码分析技术 ,它从语义角度对程序进行分解, 根据切片准则,识别源代码中影响已知点变量值的所有语句 ,基本程序切片可分为静态切片和动态切片,静态切片不需执行程序,即可找到影响变量值的语句;而动态切片依赖程序的特定输入 ,保留对最终结果有影响的语句 ,通过运行动态程序切片,有助于缩小错误的范围 。

    基本概念:

        定义1:程序控制流图是一个有向图,用G=NAse)表示,其中N是节点集,节点表示语句;A是边集,边表示语句间可能的控制流向;s是唯一的源结点,对应程序的开始语句;e是唯一的汇结点,对应程序的终止语句。从结点s到某结点kn的路径是语句序列T=,其中n=sn=kn1i<q),(,) 。若存在输入数据使某一条路径可执行,则称该路径是可达的。;一个程序的状态迹是对某特定输入数据而实际执行的可达路径。语句X在状态迹中的位置p处可表示为(Xp),记为

    定义2:设T是程序P对输入x的状态迹,P的动态切片准则表示为一个三元组C=xV),其中xP的输入,I是状态迹T中第q个元素的状态迹符号;V是程序P的变量子集。

    定义3:设C=(x,,V)是程序P的动态切片准则,TP对输入x的状态迹,CP的动态切片是满足如下条件的一个可执行程序:

     1、删除P中零条或者若干条语句可得到P

    2、若P对输入x可终止执行且状态迹wT,则对输入x也可终止执行且状态迹为 ,且存在相应执行位置,使T值与中相等。

    定义4:一个变量在程序中的某处出现,使之与该变量相绑定的内容被引用,则称该出现是引用性的出现,形式定义为:

    一个变量在程序中的某处出现使数据与该变量相绑定,则称该出现是定义性出现,形式定义为:

     

    算法:

    1,给定一个程序p切片准则,生成其状态迹T

    2,确定 DUTCIR 关系;

    3,定义 是在执行位置qV中变量最后定义集,LT)是对 有TC关系的测试控制集;

    4,定义 ,其中 ,对   项中,将最后得到的最为切片  ;

    5,通过反复计算产生 作为序列的极限(  );

    6,对于 中所有的 ,切片包括语句X和切片准则中的语句I

    至此得到所需切片如Ⅰ:

     

      

     

     

     

     

             

    1 readn

    2 i=1

    3 while(i<=n) do

    begin

    4       if(i mod 2=0) then

    5           x=17

    else Ⅰ

    6          x=18

    endif

    7        i=i+1

         end

    8  write(x)  

    以上程序对输入n=2的执行过程状态迹T=<1,2,3,4,6,7,3,4,5,7,3,8>,如:

    readn

    i=1

    i<=n

    i mod 2=0

    x=18

    i=i+1 Ⅱ

    i<=n

    i mod 2=0

    x=17

    i=i+1

    i<=n

    write(x)  

    构造DUTCIR关系:

    1DU关系描述一个行为为一个数据项分配一个值,其他行为引用该值,即将一个变量的引用和其最后定义联系起来,在上述第二个执行语句中: DU=

    2TC关系描述测试行为以及其影响执行的行为间的关系,即将一个逻辑表达式的最新出现和控制依赖于其上的状态迹中出现的语句联系起来。如上述第二个执行语句中  影响 的执行,但不影响的执行,影响他们的是  。在上述第二个执行语句中:

    TC=

    3IR关系描述出现的相同语句。在第二个执行语句中:

    IR=

    在程序Ⅰ中切片准则(2x)为计算切片  ,首先找到对 有直接影响的所有行为集  ,因x=17对 write(x)有直接影响,所以LD8{x}={}LT=,从而={}, 反复计算产生作为序列 的极限()。在语句Ⅱ中:

    LD(8,{x})={},LT()=

    ={}, ={}

    ={,},=(,,)

    ={},={}

    ={},={}

    =

    至此停止计算,得到的切片为

    ={}={}

    至此停止计算,得到的切片 为:

    1  readn

    2   i=1

    3   while(i<=n) do

    begin

    4     if(I mod 2=0) then

    5       x=17

    endif

    7      i=i+1

      end

    8  write(x)

    二、下步的工作计划: 

    在理解了和掌握了程序切片的相关知识之后,接下来的根据任务书的要求,理解动态程序切片的方法,初步设计一个具有动态切片功能的程序分析系统, 最终采用面向对象可视化语言编程实现上述系统,进行性能测试,并分析测。

    三、存在的问题:

        对算法的理解可能还不够准确,需要在后面的工作中随时加强对算法的理解,以保证系统实现,编写程序工作的顺利进行。

    展开全文
  • 静态测试动态测试

    千次阅读 2019-03-31 16:59:37
    不运行被测试的软件系统, 而是采用其他手段和技术对被测试软件进行检测的一种测试技术。(代码走读、文档评审、程序分析等) 。 ·静态测试常用技术——静态分析技术: 1.定义:一种不通过执行程序而分析程序执行的...
  • 动态编译技术在开源框架中的应用非常的广泛,现在市面上的插件化框架,热修复框架几乎都使用了动态编译技术,原理几乎都是在编译期间动态的在class文件中注入代码或者或修改。那就让我们来了解一下这高大上的技术吧...
  • 1、测试部分的不同 静态测试是指测试不运行的部分:只是检查和审阅,如规范测试、软件模型测试、文档...静态测试是指不用执行程序的测试,它主要采取方案—代码走查、技术评审、代码审查的方法对软件产品进行测试。...
  • 动态网页技术基础

    千次阅读 2008-01-07 17:12:00
    内容提要 动态网站结构 动态网页特征 主要动态网页技术 1.动态网站结构?答:采用Web方式、实时动态交互等形式,将应用逻辑集中到服务器端;一般由浏览器、WEB服务器、应用服务器、数据库服务器组成;客户层的浏览器...
  • 电力试验技术方案

    2012-12-03 14:23:48
    电力试验的管理信息化系统的技术解决方案,包括电气试验、化学试验、仪器、仪表试验等的试验管理,并自动生成试验报告等
  • android测试技术.ppt

    2020-08-27 11:36:33
    android测试技术包含对android测试要素,详细具体的测试步骤以及安装测试工具等,有利于自我提升
  • 上文说到,我们可以通过分析Ajax访问服务器的方式来获取Ajax数据。Ajax也算动态渲染页面的一种。所以,动态页面也是可以爬取滴。...这个工具的主要功能包括测试与浏览器的兼容性——测试你的应用
  • 软件测试技术路线怎么走

    千次阅读 2017-05-19 10:50:34
    软件测试工程师发展路线(这里只说的是纯技术路线,不包括测试管理路线)分为技术路线中级域、技术路线高级域、技术路线专家域。
  • 静态分析是一种不通过执行程序而进行测试技术。静态分析的关键功能是检查软件的表示和描述是否一致,没有冲突或者没有歧义。  动态分析的主要特点是...在动态分析技术中,最重要的技术是路径和分支测试。下面要介绍

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 964,256
精华内容 385,702
关键字:

动态测试技术包括