自动测试程序切片机

文摘

程序切片技术提取程序的一部分(片)影响或受到一组变量在给定的点(切片准则)。计算最小片在一般情况下是不可判定的,和获得最小片给定程序通常是计算禁止即使对于非常小的项目。因此,不管我们使用什么程序切片机,一般来说,我们不能确保我们的片是最小的。这可能是根本原因没有基准的最小集合程序切片的存在。在这项工作中,我们提出一个方法自动生产quasi-minimal片。使用我们的方法,我们已经有了一套quasi-minimal片为Erlang之后手动证明他们是最小的。我们解释构建套件的过程中,使用的方法和工具,和获得的结果。套房配有一个集合一起Erlang的基准不同的切片标准和相关的最小片。

1。介绍

领域的科学和工程计算中,通常使用不同的程序转换来改变一个算法几次,直到满足一定的性能要求。其中一个转换程序切片。程序切片技术对程序分析和转换的主要目的是提取(从一个程序语句片),影响或影响一个或多个变量的值在某种程度上,通常被称为切片准则(1- - - - - -4]。这种技术已经适应几乎所有的编程语言,它有许多应用,如调试(5),项目专业化(6,软件维护7),和代码混淆(8]。

在一般情况下,确定最小片是不可判定的1]。出于这个原因,几乎所有的程序切片技术保证其计算片完整的(即。,they contain all statements that do influence the slicing criterion), but, in general, they do not guarantee that their computed slices are声音(即。,they probably contain statements that do not influence the slicing criterion).

例1。考虑到程序图。我们可以定义切片准则 在最初的计划。这意味着我们感兴趣的所有语句都需要计算的价值x在第7行。原始代码是一片本身,而是存在小片。例如,中间是一片计算的代码几乎所有当前的静态程序切片机(例如,Java切片机(这是印度河的输出9]和CodeSurfer [10])。然而,中间的部分并不是最小的。原始程序的最小片上的代码是正确的。很难计算这个片切片机,因为第7行是通过一个控制流路径可以从第6行和第6行定义了变量x,这是用于第7行。因此,大多数切片机认为,6号线影响线7。这个推理是及物地应用于线4和6。因此,程序切片机生成中间代码。
示例1说明了一个小程序没有方法调用,甚至没有循环,无法精确处理目前的程序切片机。计算最小片是不可判定的在一般情况下不,然而,阻止我们定义一个程序来计算最小片对于一个给定的具体程序。然而,通常情况下,即使是很小的项目,这个过程将是难以计算的(11,12]。不幸的是,人工干预往往是需要产生最小的片,这是唯一可行的小程序。

1.1。动机

能够计算最小片将加速许多软件过程。例如,编译器使用程序切片去除死代码,和许多分析使用程序切片作为预处理阶段检测变量的依赖关系。因此,使切片更准确也将改善后分析基于它。

因为计算最小静态切片是不可判定的,在这个工作中,我们提出一个方法来计算quasi-minimal片,这大约是最小片对于一个给定的输入(这意味着quasi-minimal片可能不是声音静态切片,即。所有可能的输入)。在许多情况下,我们感兴趣的是生产一片对一个给定的计算(称为最小的动态切片)。例如,在调试,我们常常产生一片感兴趣的程序产生一个错误对于一个特定的输入因为片生产是一个简化版的程序,再现了错误的计算(包含错误)。在回归测试,在我们测试新版本程序的回归测试,可能出现许多不同的错误。在这种情况下,我们可以生产一片很感兴趣对于一个给定的一组测试用例(被称为最小的同时动态切片)。

我们的方法产生最小的动态切片和同步动态切片,和它也可以产生静态最小片在许多情况下。一方面,如果一个程序的输入域是有限的,我们自动生成所有可能的输入值,因此,产生一个最小静态切片。另一方面,如果输入域是无限的,我们提供一个基于concolic测试仪器产生测试用例,探索所有可能的分支程序的分支覆盖(100%)。这样可以确保在许多情况下,产生静态切片也是最小的。

我们用我们的方法生产一套基准以最小的片。这表明quasi-minimal片通常是最小的片。事实上,我们已经有了一套23 quasi-minimal片,我们证明,它们实际上是最小片。

从我们所知,不存在任何公共库的基准以最小的片,这是令人惊讶的,因为一套最小片切片机开发人员很有用。特别是,我们实现了几个程序切片机不同的语言,包括佩特里网(13],XQuery [14],Erlang [15CSP], [16]。每次我们改善我们的程序切片机(例如,新技术或功能或纠正某些错误),我们发现同样的问题:我们无法测量改进实现改变。我们经常做的是实现一些基准和新的比较我们之前的结果。这给了一定程度的改善。但是,这将是更有用的开始一连串的测试,自动比较新的片生产的黄金标准(即发布的代码。、最小片)。这将允许我们不仅要客观地度量的改进新版本还发现问题可能引入的其他部分切片机,例如,相当比较我们与其他工具的工具。

作为一个应用程序的方法来生产quasi-minimal片,在这项工作中,我们也存在第一个完全自动化的系统评估和比较的程序切片机。这个系统输入一个程序切片机和输出报告精度和召回的切片机对一套最小片已经计算。该系统还可以输入两个切片机和自动进行比较。如果两个切片机是两个版本的相同的切片机,那么该系统不仅能测量取得的改善也识别错误引入新版本(或解决了)。

1.2。贡献

这项工作的主要贡献是一个方法用于生成quasi-minimal片,后为Erlang实例化并用于生成一套基准程序连同他们的最小片组成。这项工作的贡献总结如下:(我)一个方法来获取quasi-minimal片。(2)改编自基于观察的切片(orb) [12)与抽象语法树(ast)。这最大化精度,允许我们片文字的水平。(3)球体的泛化。球体在所有情况下都是不正确的。这个问题是我们的方法识别和解决。(iv)Erlang的实现方法,产生一个新的Erlang程序切片机。(v)一套基准和具有挑战性的程序切片问题连同他们的最小片。套件包括一个工具,可以用来评价一个程序切片器套件。

2。预赛和符号

本节介绍了初步定义和符号一起使用。因为存在几种不同的片和最小片的文学观念,做具体的事情,我们需要提供一个正式的定义,我们将基地的其余部分。

程序切片是基于切片准则的切片。这个切片准则通常对应于一个语句的代码和一个变量在声明。然而,如果我们使用语句定义,我们不能像我们想要精确。因此,我们的切片准则基于表达式,不实施精密障碍。

定义1(切片准则)。让P是一个程序。一个切片准则C的P是一个表达式P的评价产生一个值。

注意,尽管大多数程序切片机是基于语句,我们没有限制,精度水平。此外,任何变量在P可以被认为是一个切片准则定义,因为变量表达式,但我们也允许定义等切片标准操作的结果(例如,添加),价值分配,由过程调用返回值,值的文本。

我们的方法结合了静态和动态切片和,因此,我们还需要一个定义的动态切片准则基于表达式,以及定义的序列值的动态切片准则评估。

定义2(动态切片准则)。让P是一个程序。一个动态切片准则P是一个元组 这样C是一个切片准则我是一个输入P。

定义3(值)的序列。让P是一个程序, 是一个动态切片准则P。值的序列切片准则吗C评估执行期间P与我。

首先,重要的是要注意,我们使用标准的定义部分,不包括无尽的和不确定的项目。的理由可以发现这些排除的必要性的开创性论文Weiser [1]。另一个重要的属性是,我们希望我们的片是可执行的,这样的执行部分对于任何给定的输入必须多次评估切片准则(或更多)与原始代码,和值的序列切片准则评估时执行原始代码必须等于(或前缀)获得的序列切片。在形式上,给出的定义如下:

定义4(静态可执行程序切片(基于[3,12)))。一个静态的可执行程序年代的程序P对切片准则C是任何可执行程序有以下属性:(1)年代可以通过删除代码P(表示 )。(2)对所有输入是一个前缀 。我们定义一个动态可执行程序切片作为一个可执行程序切片对于一个给定的输入。在形式上,给出的定义如下:

定义5(动态可执行程序切片)。一个动态的可执行程序年代程序的P在一个动态切片准则 是任何可执行程序实现的两个属性定义4P关于C只有一个特定的输入我。

根据定义4和5,每个程序本身作为一个可执行程序在任何标准片。

从这里,给定一个程序P和一个切片准则C为P,我们使用域表示包含所有可能的片的有限集合P关于C。我们也使用符号参考片P关于C计算与一个特定的切片机X。

定义6(最小片)。最小的程序P对切片准则C是任何这样 。

注意最小片,根据这个定义,不一定是独一无二的,不一定是一片的最小的数表达式(例如,17])。因为计算最小片是不可判定的,类似于(12),我们可以放松其定义最小的一组有限的输入。在形式上,给出的定义如下:

定义7 (quasi-minimal片)。让是一组可能的输入程序P和C是一个切片标准P。quasi-minimal片(QM-slice) - - - - - - 的P关于C和是一个动态的可执行程序片吗P这是最小的在一个动态切片准则 。如果包含所有可能的输入P,然后 - - - - - - 是最小的P关于C。

在本文提出的方法中,除了一个程序P,一个切片准则C,和一组输入 ,我们也把片和ASTP。这是特别有用,让我们思考片(部分的准确性3)。因此,我们需要切片的概念标准适应ast。这可以很容易地通过重新定义一个切片准则这样感兴趣的点不是一个表达式但AST节点的子树表示的表达式。我们定义切片准则和动态切片准则的ast如下:

定义8 (AST-adapted切片准则)。让P是一个程序,C是一个切片准则P。让是一个的P在哪里N组节点和吗E边的集合。nAST-adapted切片准则吗C这样和n的子树的根吗代表C。

定义9 (AST-adapted动态切片准则)。让P是一个程序, 是一个动态切片准则P。一个AST-adapted动态切片准则 是一个元组 这样nAST-adapted切片准则吗C。

3所示。关注细粒度切片

程序切片通常以代码行。原因在于,大多数程序切片技术考虑行代码作为原子元素,因此,他们没有删除整行或1,5,12]。出于这个原因,大多数的工作,比较不同的程序切片技术的精度就比较检索的行数(例如,12,18])。不幸的是,这种编程风格非常敏感,而且,它可以是非常不精确的,特别是在函数式语言。

例2。考虑到Erlang程序图2(一个)和它的最小的部分2 (b)关于切片准则 。观察到一些表达式已经取代了_或新鲜的原子切片([15,19])。这是需要切片可执行。显然,所有方法基于行不能删除不需要的子表达式1,2,3,6。例如,在第2行,C=B可以删除,但程序员初始化一个,B,C在一行,因此整个线不能被删除。人们可以认为是预处理阶段可以用来重构代码和把所有语句在不同的行只要是可能的。但是,这不能解决第二个问题:有时只在一行可以删除子表达式。这是变量的情况Z,Y,C在第3行。
为了克服这些限制,已经通过,例如,CodeSurfer [10]或[15),在我们的方法中,我们建议使用表达式作为切片标准,所以精度可以增加。我们也思考片在AST水平而不是数行代码,我们可以测量的AST节点数量属于切片,从而产生更精确的测量。然而,注意,这是一个概括,即。,those program slicers that work directly on lines or statements (e.g., [9)我们的模型的一个实例,因为它们删除子树的AST对应线或语句。即行/语句表示与一个AST节点(及其子树)。这个推理也适用于那些基础的程序切片机切片在其他元素,如程序和表情甚至AST节点(例如,10,15,20.])。

4所示。一个方法来产生Quasi-Minimal片

给定一个程序和一个切片准则,我们的方法计算其QM-slice(7)定义两个连续的阶段。第一阶段产生的原始程序的静态部分,这是第二阶段的输入。第二阶段进一步片这个片,产生最终QM-slice。图3总结了方法,在以下部分说明。

4.1。第一阶段:结合静态程序切片机

在第一阶段中,我们使用一组静态程序切片机反复片原始程序直到到达一个修复点。不同的程序切片机通常实施不同的技术和优化以减少切片的大小。因此,我们可以使用任何程序切片机生产第一片,我们可以使用为出发点来进一步减少其大小与另一个程序切片机,因为片一片一片,使用同一切片准则。

定理1。让P是一个程序,是一个程序块。然后,对于任何P,C, ,和 。

证明。通过定义4点4,我们知道 。通过定义4点4,我们知道是一个前缀这是一个前缀 。因此,也是一个前缀的 。因此, 。

因此,一个程序P和一个切片准则C,切片机B可以使用提供的片吗切片机一个作为输入,利用代码删除一个。然而,一个也可以利用代码被B因此第一次删除代码并没有删除,这将暗示一个可以进一步利用新代码删除。因此,需要一个循环之间所有的切片机,直到没有人可以进一步消除任何额外的代码,从而达到修复点。

切片机的一个重要属性,这是一个要求的方法,是他们生产的切片必须完成(注意,在我们的上下文(根据定义4和5),一片总是完成。然而,并非所有的程序切片机产生完整的片。等切片机(21只有确保稳健。因此,在这篇论文中,完整的片应该读过是吗“静态切片”)。因此,的输出阶段1总是一个complete片,因为c的顺序组成omplete切片机产生一个完整的切片机。

定理2(完整性)。让P是一个程序,让C是一个切片标准P。给定两个完整的程序切片机 和 ,然后是一个完整的片对吗P和C。

证明。首先,因为完成,我们知道吗是一个完整的片对吗P和C。我们用反证法证明的定理假设不全对吗P和C。如果这仅仅是可能的是不完整的,因此呢并不是一个完整的片对吗和C,或者如果是完整的,但不全对吗P和C。然而,因为这两种情况下导致矛盾和是完整的。此外,由于和是完整的,那么 ,因此,也是一个完整片对吗P和C。

虽然数学上正确的说切片准则C是常见的所有程序切片机(因为C指的是一段代码P),在实践中C通常是提供一个文本模式(例如, 第5行,变量 ),所以它不是一个参考了。因此,如果一个线之前C(例如,行2)从片P第一个程序切片机获得年代,然后C需要更新(例如, )所以后续程序切片机切片准则的定位年代。图4展示了切片准则是如何更新。这个过程包括四个步骤:首先,一个AST得到的代码和切片;第二,一个映射([22,23)在AST年代计算(图中虚线);第三,节点代表切片准则(定义8和9)坐落在AST的代码;最后,使用映射节点AST片。

4.2。阶段2:增加精度通过AST-Adapted orb算法

第二阶段包括三个主要模块:球体,测试用例的生成,测试用例验证。以后我们解释模块。钻研细节之前,值得的话,第一阶段是可选的,因为第二阶段获得相同的结果单独工作时结合第一阶段。然而,第一阶段显著减少AST节点的数量,第二阶段,它能加速过程(例如,在我们的实现方法,第一阶段第二阶段的时间减少了64.99%)。

4.2.1。准备球体

我们实现了一个基于切片的变体(orb) [12]。orb是一种迭代的技术删除线从程序和检查是否所需的一个可观察到的行为。这是检查一个特定的测试用例集。如果所需的一个可观察到的行为,然后可以有效地删除和系统可以再试一下不同的线,直到没有更多的行可以删除。当系统已经完成了一次一行,它可以重复这个过程删除两条线在每个迭代中,等等。

球体的变体迭代程序的AST(而非遍历它的行)。特别是,它遍历的AST” ”(图3)。大概,这变种迭代试图删除从每个子树AST。每删除子树产生的尝试“片候选人”(见图3)。每一块的候选人,其行为是相对于原始程序的行为根据定义7。如果他们表现出相同的行为,那部分是AST生产中永久删除“新切片”(见图3),魔法球重新开始这个新的片作为输入。否则,前片恢复和球体用于新的迭代。这个迭代过程是增量(首先,它一次删除一个节点,然后,两个节点,等等),并继续,直到没有更多的节点可以被删除。这种ORBS-based技术描述的算法1,我们使用表示的反射性和传递闭包E。注意,该算法参数对锰表示节点的最大数量,可以删除生产一片候选人(可以检查所有可能的组合锰=- n -)。,该算法循环currMN从1到锰。它的收益通过删除每一个组合currMN节点,然后测试他们。例如,首先取出每一个节点(及其子树)和运行测试,以检查是否值的序列切片准则的保留。第二,拿出两个节点的组合(及其子树),测试,等等。总是建立在先前的结果。

为此,该算法使用函数 ,执行程序P的测试用例t和记录值的序列切片标准计算C。递归函数(ORBSAST)迭代自顶向下AST删除子树和检查是否值计算的序列seq原始程序的一个前缀值计算序列的子树的新项目删除。这是用电池的测试(也称为输入上下文)。函数ORBSAST直到到达fix-point (如此反复,直到循环),每个的数量从1到删除节点锰(为循环)。

这个改编的球体来AST年代自上而下的工作。这是更有效,因为它具体化的方式工作,试图删除第一个完整功能,条款,和数据结构之前与他们的组件。如果使用自底向上遍历相反,当一个函数可以被删除,它的每个语句事先将被删除。在其他情况下这可能不是一个问题,但在我们的情况下,每次一个子树(例如,声明)从AST,所有生成的测试用例运行验证。显然,这些验证是浪费时间在整个函数将被删除。

唯一的功能,用户必须提供的算法1是seq和generateTestCases在接下来的小节描述。

评论是很重要的,我们的算法是一个泛化的球体在两个方面。首先,因为它不仅可以切任何表达式和行代码。如果我们考虑到节点只能删除那些对应的子树的代码行,那么我们的算法是相当于球体。然而,还有一个泛化。orb使用一个窗口的大小δ代表的行可以删除。因此,球体可以删除各种线,但它强加的限制,所有人必须在一起(在窗口)。这意味着orb不能产生最小片示例1因为4和6线必须删除不删除第5行。我们的方法允许删除不同(不一定相邻)子树的AST,因此解决这个问题和生产最小片在示例1。

4.2.2。测试用例的生成和验证

第二个模块中使用这一阶段负责测试用例的生成,实现的功能generateTestCases在算法1。目标是生成测试用例,执行不同的路径的切片,切片准则进行评估。每一个“片候选人”由光点测试通过比较其行为与原始程序之一。如果他们显示相同的行为,那么丢失的代码片候选人绝对是移除。否则,它恢复。显然,这一阶段的质量取决于生成的测试用例。一个重要的评论是,我们的架构利用第一阶段不仅生产精制片”“但也提高测试用例的生成。特别是,我们可以观察到在图3这个模块“测试用例生成器”输入“”(而不是“原始程序”)。从“生成测试用例”产生更好的测试用例,因为这避免了生成测试用例,探讨中删除代码块(,因此,不能影响切片准则)。然而,观察,“”不是作为模块的输入“测试用例验证器”因为的输出seq片和“原始程序”根据不同属性定义4中4。这是解释的例子3。

例3。考虑以下序列切片准则产生的值当执行一个具体的输入我在原来的计划(原始),第一阶段的输出部分( ),和一片候选人(SliceCandidate): 在这种情况下,如果我们验证(即。,决定它是一个有效的片)SliceCandidate关于原始那么,根据属性4的定义,SliceCandidate是一个可执行程序片吗原始(()是一个前缀(c))。然而,如果我们验证SliceCandidate关于 ,然后验证失败因为(b)不是一个前缀(c)。这是因为一片可以产生更多的值比原来的程序切片准则。因此,模块测试用例验证器输入原始为了防止这些假阴性。
图3总结了描述阶段。在图中,各个阶段是封闭的浅灰色框内;切片机和其他进程与深灰色框表示;片和测试用例是用白色表示文件;片候选人(未验证或无效)表示虚边白色文件;和决策点与黑暗的菱形表示。第一阶段的中间值和输出片必须是静态的原始程序的可执行程序片(4)定义,而第二阶段的中间值和输出片是动态可执行程序片(见定义5)。
注意,这是一个总体方案,可以适应任何语言。为此,我们只需要实例化的深灰色部分:程序切片机,测试用例验证器,测试用例生成器(orb技术已经paradigm-independent和适用于任何语言)。

5。Erlang的实现方法

我们本节描述如何为Erlang实例化方法。在图所示的方法遵循的模式3在第一阶段,我们使用两个程序切片机Slicerl(15),e-Knife;可爱的(24作为一个测试用例生成器);证券交易委员会(25)作为一个测试用例验证器;和封面(26)作为一个覆盖计来决定何时停止生成测试用例。

5.1。阶段1:Slicerl和e-Knife

在我们的设置中,我们使用两个切片机:Slicerl(15),e-Knife。我们选择Slicerl四个理由:第一,因为它是基于一个数据结构称为Erlang依赖图(EDG)的粒度级别最小(即。令牌)。这允许删除表情甚至在一行代码。第二,因为它是开源的,因此,我们能够访问其内部行为和分析,扩展它,并使用它在我们的实现中。第三,因为它实现了一些新颖的优化技术,使它非常精确。第四,因为它是程序间。牧人的等切片机切片机(27]很快被丢弃,因为他们只是intraprocedural,因此,他们无法处理精度的基准套件(注意,这并不意味着intraprocedural切割器的套件是无用的。这仅仅意味着intraprocedural切片机不太有用的构建套件)。

第二个切片机叫做e-Knife。Erlang是一个静态切片机,我们已经在过去的几年里。e-Knife也是基于EDG,因此,它有相同的粒度级别Slicerl令牌(EDG的每一个令牌代表一个不同的节点容易被切掉)。此外,e-Knife包含一项新技术来精确片复合数据结构、静态分析由Slicerl补充。

例4。左边的程序图5切片准则 ,牧人和Slicerl产生片在中间,而e-Knife产生右边的切片。

注意,尽管X取决于一个和一个取决于2,X不依赖于2。只能够检测e-Knife不及物数据依赖关系。

5.2。阶段2:可爱、封面和交会

在本节中,我们解释我们已经为Erlang实例化测试用例的生成和验证任务所需的球体。

5.2.1。测试用例的生成

我们保证高质量的测试用例使用concolic测试。我们做了两个连续的步骤,确保分支和语句覆盖率:100%(我)Concolic测试用例的生成。这种技术分析了分支源代码和生成的条件约束的输入必须满足访问所有分支。这时,一个约束解算器是用于生产测试用例。我们使用被称为可爱的Erlang concolic测试工具24]。下面的例子显示,白盒测试可以生成测试用例,执行很不寻常的分支。

例5。再次考虑程序图2(一个)。此案在第8行将很难执行随机测试用例的生成。100%的分支覆盖率只有通过一个测试用例存在X= 123456789。然而,这并不能保证评价的表情分支。100%的语句覆盖率在第一个分支只有通过一个测试用例存在X= 123456789,Y< > 0。(2)半随机的测试用例的生成。我们补充了白盒测试和黑盒测试。我们实现了随机生成器在Erlang中所有可能的数据类型。的最大数量的测试用例生成是一个参数的方法。这个数字取决于具体的代码处理。数量也有直接影响的运行时间和精度上最后一片。在默认配置中,我们的实现生成测试用例,直到所有的代码进行测试(即。,100%的语句和分支覆盖)。10,它生成测试用例,积累和测量产生的测试用例覆盖在每个步骤中使用一种名为“覆盖”的工具(26]。封面是一个覆盖分析库Erlang,可以确定覆盖实现当执行一个程序和几个调用(在我们的设置中,测试用例),也可以识别发现分支。它基本上工具代码,以便每一行扩充为一个新的函数调用。因此,通过计算调用期间执行测试用例的执行,我们可以知道线路被处决,多少次。当封面报道,语句和分支覆盖率达到100%,测试用例的生成完成。我们要注意,这些保险只是指标而不是目标。100%的覆盖率并不一定意味着切片精度高。

例6。再次考虑程序图2(一个)。一个测试用例的输入X= 1,Y= 1并执行所有表达式在11 - 100%的分支和语句覆盖率这条线,但它不触发除零例外。发现这种情况需要生成更多的测试用例(例如,X= 1,Y= 0)。

5.2.2。测试用例验证

我们的测试用例的生成获得输入,确保100%的语句和分支覆盖率。然而,在我们的例子中,这些输入必须伴随着特定的输出,形成测试用例:评估值的序列切片准则。在我们的例子中,这是通过一个工具证券交易委员会(25)(实现功能seq在算法1)。给定一个切片准则,sec工具源代码的方式检测的执行代码获得作为一个副作用是评估的序列值。

6。评价的方法

我们确定了一组切片的问题和挑战,我们的方法获得23基准申请Erlang(23切片标准定义了18个不同的Erlang程序)(联合)实现的所有问题。这些基准套件包含三元组program-slicing criterion-minimal片。片生产在我们的实现中QM-slices(7)定义和细粒度的片,因为他们已经获得工作在AST节点(定义8和9)。在这一节中,我们展示了每个组件的行为的方法。

6.1。阶段1:Slicerl和e-Knife的行为

第一阶段达成的解决点只有一个迭代(e-Knife生产的切片(片2)无法进一步降低Slicerl)。第一个切片机需要12820毫秒片所有的基准除了九Slicerl的语法是不支持的。这使得平均916毫秒基准。Slicerl删除619个节点“原始程序”总计(平均减少31.89%)。第二个切片机需要48361毫秒片所有的基准(平均2103毫秒基准)(e-Knife multiparadigm切片机在Java中实现。出于这个原因,它需要额外的时间来访问Erlang)。e-Knife进一步减少了片由Slicerl总共59节点(平均额外的原始程序减少2.48%)。如果我们还考虑那些Slicerl不能处理的基准,然后额外的削减14.67%。

6.2。阶段2:球体和可爱的行为

6.2.1。球体

算法的执行1与和删除一个节点一次( )原始程序减少50.02%(平均)。这是一个额外的削减15.84%的第一阶段的结果。后来,算法1再次执行,但这一次删除两个节点,而不是一个。切片在所有情况下都保持不变(减少0%)。然后,三个节点被删除在每个迭代中,减少0%。最后,四个节点被移除在每个迭代中对一些基准(根据我们的估计,评价其他的基准需要约8个月)。在所有情况下,减少0%时达到四个节点被移除在每个迭代中。由于组合爆炸,我们没有运行任何基准测试的五个节点,因为它的运行时间估计。

我们比较这四个迭代执行与球体在桌子上1。的列标签我节点, ,每个迭代的代表为循环算法1(第一个删除1节点在每个迭代中,第二个删除2节点在每个迭代中,等等)。在这些列,Iter是不同的迭代的数量(即执行的算法。,the number of configurations that were checked, where each configuration is the result of removing我从AST节点),时间是用来检查的总时间配置,和%的比例是节点仍从原始代码。注意,该算法仅删除节点时试图删除单个节点(1个节点)。

这整个的过程( )花了9天,13小时51分钟。然而,orb循环与2、3、4个节点并没有产生任何减少(大部分时间和消费)。因此,除非你特别感兴趣的是生产最小片(我们),这是一个很好的设计决定配置球体只删除一个节点。这几乎总是产生完全相同的结果,但是时间显著减少。这种配置( ),整个套件的基准被14分25秒,产生相同的结果。

6.2.2。可爱的

了所生成的测试用例所覆盖的范围与所列的每一个基准的可爱可爱的表列2。在14个23的基准,可爱分支覆盖了100%。在4 23基准,可爱了分支覆盖100%。在5个基准(b16_s58C,b12_s40BS,b12_s92A,b15_s65Shown,b18_s50J),可爱返回一个错误或无法产生任何测试用例。

在所有这些基准可爱没有产生分支和语句覆盖率100%,第二阶段的半随机的测试用例的生成是激活达到100%。列随机表2显示第二个阶段中,语句和分支覆盖率达到100%平均只有0.12秒。

6.3。实证评估

之前我们的设计和应用方法,我们第一次生产的片基准Slicerl和e-Knife,另行规定。这使得评估如何精确QM-slices(与我们的方法获得)比较标准片(用两个程序切片机)。

6.3.1。可执行程序切片

我们切基准和两个Erlang程序切片机(Slicerl和e-Knife),产生一个有趣的结果:实证评估每个切片机(比较)。Slicerl不能处理九基准(由于未处理的语法结构)坠毁。如果我们忽略这些基准,那么他们的精度是相似的。平均,Slicerl减少原来的程序( ),而e-Knife减少( )。然而,由于两种切片机执行的分析不同,Slicerl好和的两倍e-Knife更好的13倍。这显然证明了程序切片机的组合在第一阶段的方法。我们也比较以下三个片为所有基准: 在哪里B是一个基准,C是一个切片准则(注意,从理论上讲,工会和十字路口片不一定是片(17),但在实践中(例如,与我们所有的基准),他们通常都是)。我们发现,尽管基准, 。因此,(i)的顺序切片机被处决并不相关,(2)组合顺序切片机(即好。、切割片)组成平行和交叉。原因是一个切片机可以利用部分被其他的切片机。这个证明需要fix-point循环在阶段1的方法。

再。Quasi-Minimal片

表2总结了实证评价该方法的特定实现。具体,它比较连续改进的大小的片,和所需的时间,两个阶段的所有进程。每一行代表一个不同的基准。对于每一个基准,列节点代表的AST节点数量,对应于程序/片的大小。在片的情况下,我们还包括节点的比例仍然在片对原来的计划。列显示了时间花费在每一个阶段以秒(s)。第二阶段分为两个不同的过程:测试用例生成和球体仅限于一次迭代(见部分4.2这一决定的理由)。最后,迭代列显示了球体的数量配置检查(也就是说,许多不同的节点删除生产片候选人)。

重要的是比较不同的数据行考虑,列提供补充信息。例如,如果我们比较减少通过Slicerl基准b5_s30C b14_s44V,可以认为一个切片生产b14_s44V要好得多(这是减少到37.8%,而b5_s30C只是减少到94.44%)。然而,如果我们观察球体的专栏中,我们可以看到,结论可能是相反的:Slicerlb5_s30C产生最小片,而产生的片b14_s44V不是最小的。

6.3.3。经验教训

我们的实现方法及其实证评价已经回答了几个研究问题的过程:(1)第一阶段真的需要吗?最后一片生产的第二阶段是相同的与独立是否使用第1阶段。然而,使用第一阶段第二阶段的时间减少了64.99%。(2)运行时间:每个进程持续多长时间?整个套件在1054年代切片。(第1阶段:62年代,球体:865年代,和测试用例生成:127年代)。这提供了一个想法相对成本的阶段。(3)准确性:每个阶段(平均)是准确的?第一阶段原始程序减少了34.07%,第二阶段进一步降低15.85%(生产最小片)。(4)Concolic和随机测试用例:Concolic测试就够了吗?不。可爱能产生所需的覆盖60.87%的时间。在另外的39.13%,需要随机测试用例的生成。(5)Slicerl vs e-Knife:这是更好的(平均)?当他们独立运行,e-Knife是更好的在13/23基准。表3显示两个切片机的比较。(6)切片机的顺序和并行成分(十字路口):哪个更好?连续切片机的合成提供了最好的结果。

7所示。一套最小片

方法后,我们已经生成一套最小片Erlang。在Erlang中,这套房是特别有用,因为它提出了特殊的挑战程序切片(高阶,匿名函数,模式匹配,等等),而且,在这门语言当中,没有研究评估现行程序切片机还存在。

7.1。选择的基准

基准设计的套件包含中小项目包含知名文献中描述的程序切片挑战性的问题(例如,死代码,遥不可及的条款21),模式匹配(15),和复合数据结构的崩溃和扩张28])。例如,套件包括古典切片程序中使用不同的论文字数等诈骗杯子,蒙特利尔船的例子,霍维茨等人程序间片(29日]。目标是挑战程序切片机来检查这些项目中有多少是他们能够片。为了测试不同的语法结构在Erlang中也具有挑战性的程序切片(如列表理解,块结构,识字课,和远程函数调用),已从各种各样的基准github库和罗塞塔的代码编程读本网站(http://rosettacode.org/)。为每个基准测试中,我们定义不同的分割标准,这样他们可以用来测试切片机切片工作功能,条款,线,或表达水平。基准设计的套件包含中小项目(我)要求程序间技术。在函数式语言程序间切片是一个挑战。例如,牧人的程序切片机20.),最先进的Erlang重构工具之一,仍然是intraprocedural。(2)可以通过切片机切片的不同性能。该套件的主要目的不是表演,而是精度。因此,我们更喜欢中小项目,我们可以系统地产生最小片而不是大型程序的推理关于最小化由于其高昂的成本是不可能的。(3)包含不同的分割问题。事实上,每个基准简明地定义一个特定的切片的挑战。

此套件可以用来评估和比较程序切片机,但它也特别有用开发切片机。在最后一个任务,帮助我们实现了一个工具,输入一个程序切片机,片中的所有基准套件与这个程序切片机。然后,程序切片机切片获得与套件中的最小片计算准确性的AST节点(即保存。,使用最小粒度)。最后,报告表明召回,精密,F1是提供给用户以及这些指标的变化对最好的结果程序切片机取得了迄今为止。套件和工具是公开的http://personales.upv.es/josilga/slicing/bencher/。

7.2。结构的套件

所有基准标记,这样他们的用途和属性可以被看他们的标签。标签分类基准根据切片的挑战包括和他们所使用的语法结构。

例7。所有基准标识代码。例如,基准b15_s65Shown指项目15切片准则 。程序的代码15最初提取rosettacode。然后,代码为切片扩充和重新设计,包括具有挑战性的问题。最后,这个基准测试已经贴上了IP, LC,房颤,快速眼动。它们的含义如下:知识产权:基准需要程序间切片LC:基准使用列表理解房颤:基准的定义和使用匿名函数雷:基准包含远程过程调用外部函数(nonavailable代码)所有的信息关于标签的含义和分类的基准可以找到公共网站的套件。

7.3。最小化

我们的方法/切片机生产quasi-minimal片。确保最小化是不可判定的,因为并不是所有可能的测试用例可以(它们潜在的无限)执行。然而,我们的方法减轻这个问题与一个测试用例的生成阶段确保100%的分支和语句覆盖率结合白盒和黑盒测试。由于这一阶段,quasi-minimal片生产实际上是最小的在许多情况下。特别是,我们有手动证明所有23 quasi-minimal片与我们的工具生成(MN = 1和生成随机测试用例到语句和分支覆盖率达到100%)实际上是最小片。具体地说,我们为每一对单身证明最小化 套件,证明切片AST实际需要的每一个节点,所有需要的节点是片的一部分。因此,每个套件的基准是伴随着一个最小化的证据。

8。相关工作

一种方法类似于我们的切割是动态的程序,提出了陈和张30.)代替静态程序切丁,原本莱尔和魏瑟提出的(31日]。这种方法获得一个程序块语句中包含的痕迹形成的一组执行失败的痕迹,而不是一组正确的执行。在大多数情况下,剩下的语句将包含错误的来源。然而,这种方法提出了两个差异对我们的方法。1)它是不完整的。片生产可能不包含差异产生的错误。(2)片产生的可能不是可执行的,因此,他们不能用于检查差异。

在我们的方法中,我们使用一种技术,可以被认为是一种类似球体(12]。orb是一种语言无关的技术,因此它删除行没有解析。因此,如果两个语句放置在同一条线上,他们一起被删除。当然,这也可以产生编译错误如果删除一个语法构造的一部分。而不是删除的代码中,我们使用一种机制将表达式或更换新的常数切片;因此,获得精度更高,此外,这使我们能够消除表达式如何编码的独立。我们建议的orb算法提出了相似的(32),一个接一个地删除节点。具体来说,这个工作是一个综合的算法(32),因为我们也允许迭代地删除N节点(而不是一个)通过计算所有可能的组合与一个高效的自顶向下的修剪算法。

我们的技术也类似于三角洲调试(DD) [11,33]。DD最初定义进行调试,但它也可以用来计算片。DD和我们的技术计算切片的方式不同。DD依赖于使用跟踪,这是减少中间首先,在一个季度,等等。这个过程太贵了而我们的方法(也比球体)。此外,DD可以产生片是不正确的,在某种意义上,他们的行为不同于原始程序之一。显然,这是无用的对于我们的目的,因为我们需要确保套件的片是正确的。

另一个相关的方法是至关重要的切片(5]。关键切片是一样的球体背后的想法:他们都去除皱纹和检查是否产生的部分删除每一行保留原来的行为。所不同的是,临界切一次删除行,而球体增量地删除它们。因此,(i)相反球体,临界切需要一个固定数量的编译(每行一个),和(2)关键片可以在不改变错误的因为两行单独删除切片准则的行为可能会产生一个程序用不同的行为当他们一起被删除。因此,作为DD,关键的切片也产生了不正确的片。

比较和评估程序切片机的性能和slicing-based技术已经广泛利益的传统,不仅因为这使开发人员能够选择最好的切片机或技术的目的,还因为它提供了切片机的精确程度的信息。出于这个原因,许多调查和工作存在(例如,18,34,35]),评估和比较的大小片由不同的技术。不幸的是,由于缺乏一套标准的基准,在大多数情况下,基准实现从头做实验(34,35),它们来自不同的论文和项目(12),或者他们不属于的套装软件特定的切片(18]。此外,通常,实验中所使用的基准不公开或访问(例如,在18,34,35),这使得他们不可能复制和/或验证研究。此外,不可用的基准可以防止其他研究人员和开发人员比较他们的技术和报道的结果。结果,这些报告只是一个固定的图片状态的艺术,但它们不是未来技术可用来衡量和比较。

一套程序切片基准会解决这些问题,但我们没有意识到任何基准套件准备切片,即。切片,与特定的挑战问题和解决方案(小片)为每一个基准。此套件的建设是完全的小说。不幸的是,计算每个指标的最小片不是微不足道的。事实上,在一般情况下这是不可判定的,所以我们不得不手动证明最小化。该系统中使用的技术是非常相关的其他现有的技术和方法。特别是,我们使用半随机的测试用例生成类似于一个由SmallCheck实现(36]。我们也避免重复的测试用例,但SmallCheck相反,我们的测试用例的生成不是基于属性。

9。结论

这项工作提出了一种方法来生成一个新的类型的片,我们称之为quasi-minimal片。这种方法已被用于获得一套最小片。在我们所有的基准,我们证明了quasi-minimal片获得的方法确实是最小片。

方法包括使用一些工具,包括程序切片机,白盒和黑盒测试用例生成器,覆盖工具相结合的方式他们减少全球计算工作量和最大化性能。

设计方法的过程中,我们必须定义新的算法来进一步减少我们的片的大小。特别是,我们实现了一个新的Erlang程序间切片机,e-Knife,我们适应了orb技术使用AST节点而不是行。当然,方法可以完全使用标准的魔法球技术,而是重新实现它使用AST行增加了其精度。

我们已经实例化该方法和制造了第一个程序切片为Erlang基准套件。结果,我们已经开发出一种集合的基准程序切片的具体和具有挑战性的问题。每个基准测试的套件由切片标准,相关最小片(伴随着证明),而且其易用性和分类的元信息。

评价方法产生了有趣的剩余的结果。特别是,我们有经验评估和比较两个Erlang切片机,证明他们是互补的,应该结合如果减少切片的大小是至关重要的。我们也评估了三种组合的切片机(两个序列和一个并行)显示顺序组合产生更好的结果。我们也评估了orb技术基准套件。这显示,通常一次删除一个节点(总是在我们的实验中)产生相同的结果,删除2,3,4个节点。这证明跳过这些昂贵的配置。

也是有趣的评论,我们的实现方法是可以使用全自动和自己是一个非常精确的切片机,因为它需要一个程序并生成QM-slice。此外,这种新的切片机不仅准确,而且可伸缩的如果我们参数化算法1与锰=1。根据我们的实验(表2),这大大减少了运行时免费(精度不降低,因为根据我们的实验锰>1永远不会减少任何片)的大小。

数据可用性

使用的数据来支持本研究的结果包括在本文中。

信息披露

本文的初步版本是十六版的西班牙研讨会编程语言(无产阶级的2016)。

的利益冲突

作者宣称没有利益冲突。

确认

这项工作已经部分由MINECO / AEI费德(欧盟)授予tin2016 - 76843 - c4 - 1 - r和Generalitat Valenciana格兰特PROMETEO-II / 2015/013 (SmartLogic)。

引用

1. m·魏瑟“程序切片,”学报5软件工程国际会议(81年ICSE”)IEEE出版社,页439 - 449年,圣地亚哥,美国,1981年3月。视图:谷歌学术搜索
2. f .提示“程序切片技术的调查,”《编程语言,3卷,不。3、121 - 189年,1995页。视图:谷歌学术搜索
3. d . w . Binkley和k·b·加拉格尔“程序切片,”电脑的发展,43卷,不。2,1-50,1996页。视图:出版商的网站|谷歌学术搜索
4. j·席尔瓦,“词汇项目slicing-based技术”,ACM计算调查,44卷,不。3,1-41,2012页。视图:出版商的网站|谷歌学术搜索
5. r . a . DeMillo h·潘,e·h·清单”关键切片软件故障定位,”ACM SIGSOFT软件工程,21卷,不。3、121 - 134年,1996页。视图:出版商的网站|谷歌学术搜索
6. c .奥乔亚j·席尔瓦和g·维达尔,“轻量级程序通过动态切片,专业化”学报2005 ACM SIGPLAN研讨会咖喱和功能逻辑编程,WCFLP 05爱沙尼亚塔林,页1 - 7,ACM, 2005年9月。视图:谷歌学术搜索
7. 一个。Hajnal和i Forgacs切片遗留COBOL系统需求驱动的方法。”软件学报:进化和过程,24卷,不。1,第82 - 67页,2011。视图:出版商的网站|谷歌学术搜索
8. a . Majumdar s . j .褶皱和c d . Thomborson”切片陷阱:设计、正确性和评价”学报2007 ACM数字版权管理研讨会,DRM ' 07ACM,页70 - 81年,亚历山大,弗吉尼亚州,美国,2007年10月。视图:谷歌学术搜索
9. V.-P。R . .印度河、“工具包来定制和适应Java程序”,http://indus.projects.cis.ksu.edu。视图:谷歌学术搜索
10. p·安德森,t代表,t .分类,“细粒度的软件检测工具的设计和实现,”IEEE软件工程卷,29号8,721 - 733年,2003页。视图:出版商的网站|谷歌学术搜索
11. 西和r . Hildebrandt“简化和隔离failure-inducing输入,”IEEE软件工程,28卷,不。2、183 - 200年,2002页。视图:出版商的网站|谷歌学术搜索
12. d . Binkley:黄金,m·哈曼美国伊斯兰教,j . Krinke和柳,“魔法球:语言程序切片,”学报》22日ACM SIGSOFT国际研讨会的基础软件工程,工程师2014人ACM,页109 - 120年,香港,中国,2014年11月。视图:谷歌学术搜索
13. m . Llorens j .奥利弗·j·席尔瓦,s . Tamarit g·维达尔,”佩特里网动态切片技术,”电子票据在理论计算机科学卷,223年,第165 - 153页,2006年。视图:谷歌学术搜索
14. j . m . Almendros-Jimenez j·席尔瓦,s . Tamarit“基于程序切片,Xquery优化”学报20 ACM国际会议信息和知识管理,CIKM‘11ACM,页1525 - 1534年,格拉斯哥,英国,2011年10月。视图:谷歌学术搜索
15. j·席尔瓦、美国Tamarit和c·托马斯“系统依赖图在顺序Erlang,”15日学报》国际会议上基本的软件工程方法(熔丝2012),体积7212年计算机科学的课堂讲稿(信号)施普林格,页486 - 500年,塔林,爱沙尼亚,2012年4月。视图:谷歌学术搜索
16. m . Llorens j .奥利弗·j·席尔瓦,s . Tamarit“并发规范语言的动态切片,”并行计算卷,53岁,22页,2016页。视图:出版商的网站|谷歌学术搜索
17. a .德卢西亚·m·哈曼r .神庙和j . Krinke”工会不切片,切片”学报》第七欧洲会议软件维护和重建,CSMR 03p。363年,IEEE计算机协会,战后,意大利,2003年3月。视图:谷歌学术搜索
18. d . Binkley:黄金,m·哈曼,“静态程序片规模的实证研究”,ACM交易软件工程和方法论,16卷,不。2,p。2007。视图:出版商的网站|谷歌学术搜索
19. d . Binkley“精确的可执行程序间片”,ACM字母编程语言和系统,卷2,不。1 - 4,31 - 45岁,1993页。视图:出版商的网站|谷歌学术搜索
20. h·李·s·汤普森,l·拉兹洛et al .,“erlang程序,重构”12日学报》国际Erlang / OTP用户会议,斯德哥尔摩,德国,2006年11月。视图:谷歌学术搜索
21. k . Sagonas j·席尔瓦,s . Tamarit“精确解释成功的打字错误,”ACM SIGPLAN学报》2013车间部分评估和程序操作,PEPM 13页33-42 ACM,罗马,意大利,2013年1月。视图:谷歌学术搜索
22. K.-C。大”,树与树之间的修正问题,“ACM的杂志,26卷,不。3,第433 - 422页,1979年7月。视图:出版商的网站|谷歌学术搜索
23. d d。c .里斯·b·Golgher a . s .席尔瓦和a·h·f·Laender”网络新闻自动提取使用树编辑距离,”13日学报》国际会议上万维网(WWW的04)ACM,页502 - 511年,纽约,纽约,美国,2004年5月。视图:谷歌学术搜索
24. a . Giantsios n Papaspyrou, k . Sagonas“Concolic测试函数式语言,”学报》17日声明性编程的原理和实践国际研讨会(PPDP 15)ACM,页137 - 148年,锡耶纳,意大利,2015年7月。视图:谷歌学术搜索
25. d .早期美国佩雷斯,j·席尔瓦和s . Tamarit“Erlang代码进化控制,”27日学报》国际研讨会上基于逻辑的程序合成和转换(LOPSTR 2017)2017年10月,比利时那慕尔。视图:谷歌学术搜索
26. Erlang-cover, 1997,http://www.erlang.org/doc/apps/tools/cover_chapter.html。
27. 奥罗兹·g·h·李·s·汤普森,m·托斯”重构与牧人,更新:数据和流程重构,并与eclipse的集成,”学报》7日ACM SIGPLAN研讨会ERLANG, ERLANG 08年ACMd,页61 - 72年,维多利亚,公元前,加拿大,2008年9月。视图:谷歌学术搜索
28. 霍瓦特·m·托斯,笨蛋,z, l .第29卷m . Tejfel和t . Kozsik”erlang程序使用行为的影响分析依赖图,”第三暑期学校学报》会议上中欧函数式编程学校,此项举措的09年斯普林格出版社,页372 - 390年,布达佩斯,匈牙利,2010年5月。视图:谷歌学术搜索
29. 霍维茨,t代表,d . Binkley“程序间使用依赖图切片,”ACM SIGPLAN学报》1988年会议上编程语言设计和实现,PLDI 88年页35-46 ACM,亚特兰大,乔治亚州,美国,1988年6月。视图:谷歌学术搜索
30. t . y .陈和y y张”,动态程序切丁,”软件维护学报1993年会议加拿大蒙特利尔,页378 - 385,,1993年9月。视图:谷歌学术搜索
31. w·m·莱尔“自动程序错误位置的程序切片,”2日学报》国际会议、计算机和应用程序,卷2,页877 - 883,北京,中国,1987。视图:谷歌学术搜索
32. d . Binkley:黄金,美国伊斯兰教,j . Krinke和柳,“面向树与面向行的基于观察的切片,”学报2017年IEEE 17日国际源代码分析工作会议和操纵(诈骗),21 - 30页,上海,中国,2017年9月。视图:谷歌学术搜索
33. h·克里夫和西,“通过自动化测试,找到失败的原因”学报》第四国际研讨会自动化调试慕尼黑,德国,2000年8月。视图:谷歌学术搜索
34. t . Hoffner“评估和比较的程序切片工具,”石- ida - r - 95 - 01计算机和信息科学、肯特大学瑞典,瑞典林雪平大学,1995年,技术报告。视图:谷歌学术搜索
35. d . Giffhorn和c .锤”,一个并发程序切片算法的评价,”学报》7日IEEE源代码分析工作会议和操纵(骗局' 07)页,17-26 Maison国际歌,巴黎,法国,2007年9月。视图:谷歌学术搜索
36. c·西曼,m·内勒f . L . .Smallcheck, l . Smallcheck”自动详尽的测试值小,”SIGPLAN不,44卷,不。2,页37-48,2008年9月。视图:谷歌学术搜索

版权

版权©2019塞尔吉奥·佩雷斯等。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。