利用动态切片方法评价C语言程序

阎萍

摘要：针对C语言程序的评价问题，给出了执行点和执行历史相关概念的描述，讨论了执行点之间的关系，给出了关于单变量和执行点的动态切片的定义，在此基础上，给出了关于输入输出变量集和执行历史的动态切片的计算公式以及相应的程序评分方法，并通过一个实例给出了计算过程。

关键词：C语言；动态切片；执行点；执行历史

中图分类号：TP312 文献标识码：A 文章编号：1009-3044（2017）31-0278-04

Using Dynamic Slice Method To Assess C-language Program

YAN Ping

（Dept.of Math and Computer Science，Gannan Normal University， Ganzhou 341000，China）

Abstract： Aiming at the assessing problem of C-language Program， the description of some concepts relating with execution point and executing history is giving， the relation between execution points is discussing， the dynamic slice definition of single variable and execution point is giving， on the basis， the dynamic slices computation formula about the input output variable set and execution history and the assessing method relating with program is giving， in the end， the computing procedure is giving by one example.

Keywords： C-language； Dynamic Slice； Execution point； Execution history

1 概述

动态切片方法有多种并具有广泛的应用，例如，文献[1][2]提出了几种动态切片计算方法，并对可执行和不可执行的动态切片情况进行了分析，文献[3]运用动态切片方法维护大型的C语言程序，文献[4]运用动态切片技术实现测试用例的自动生成，文献[5]运用过程间动态切片方法实现过程间数据流测试。由于动态切片方法能够识别出所有对变量的值起作用的代碼，因而可以用于程序测评。本文在运用和借鉴这些方法的基础上，提出了关于单变量和执行点的动态切片的定义，并用于C语言程序的评价。

2 相关概念与动态切片方法

2.1 执行点和执行历史的定义

执行点是语句实例和时间关系的描述，时间关系描述了语句实例的执行位置。为了进一步解释执行点的含义，首先对C语言程序中的函数及其参数和语句进行编号，并给出执行点的相应描述。函数的内容包括4种情况：形参，函数内的语句，函数调用，返回语句的处理。设程序有N1个函数。首先从主函数开始，按调用顺序从1开始对函数进行编号，第i个函数表示为fi，N1≥i≥1. 主函数f1语句从1开始编号，遇到函数调用时，处理实参，如实参n1对应的形参为n时，引入外部变量n_in，把该实参n1处理成赋值形式：n_in=n1，并对函数调用语句进行编号，其他函数按调用顺序分别进行编号。设函数调用中的主调函数为fi，被调函数为fi+1，函数fi+1的编号方法：首先处理形参，如形参n处理成n=n_in，并按形参顺序从1开始编号，设函数fi+1的形式参数数为N（fi+1），则函数fi+1的参数编号范围为1…N（fi+1），函数fi+1内第1条语句编号为N（fi+1）+1，其他语句按序编号。对return（s）语句引入外部变量s_value处理成赋值形式如s_value=s后编号。引入外部变量的目的是为了在计算动态切片时能够实现对每个函数进行封装处理。按语句顺序和函数的调用顺序对每个函数中的每条语句进行编号，引入外部变量把每个函数的参数处理成赋值形式，并从1开始进行连续编号。函数fi的编号方法：设函数fi的参数数为N（fi），则函数fi的参数编号范围为1…N（fi），而对函数fi的语句则从N（fi）+1开始连续编号。设C语言程序的第i个函数fi的第j条语句为fij，它的实例执行位置为k，则执行点记为fijk.执行点的执行位置k按程序执行过程中语句实例出现的先后顺序从1开始连续编号。执行历史表示为程序某次执行过程中所有执行点组成的有序集，则执行历史可以记为H={fijk|i=1，…，N1，j∈{1，…，N2}，N2是fi的形参数+fi的语句数+fi的实参数之和，k≥1}.

一个函数中的变量可以分为两类：一般性的变量和谓词变量，其中一般性的变量的定义形式分为常量形式的变量定义和含变量引用形式的变量定义，前者只定义变量而不使用其他变量，后者即定义变量又使用变量进行定义。对函数fi的不同的执行点中出现的形式相同的逻辑表达式使用同一个谓词变量来表示，这样就限定了一个谓词变量P中不可能出现对该谓词变量P自身的引用情况，但是一个谓词变量P可能控制另一个同名谓词变量P计算其值所需的原始数据的定义。谓词变量的值是一个逻辑值，每次都要根据它所表示的逻辑表达式中出现的引用变量的当前值重新进行计算。谓词变量用于根据执行点之间的控制依赖关系实现一个执行点对另一个执行点的执行进行控制。执行点fijk中定义的变量和使用的变量分别表示为集合def（fijk）和use（fijk），定义变量值的执行点就是变量的定义点，使用变量值的执行点就是变量的使用点。

2.2 执行点之间的关系

给定一个程序以后，首先通过静态分析形成系统依赖图SDG.给定程序的一个执行历史，其中的执行点之间存在的关系分为三类：顺序关系，控制依赖关系，数据流依赖关系，其中的控制依赖和数据流依赖关系可以通过查找SDG获知。而控制依赖关系可能是多级的，分为直接和间接控制依赖关系。执行历史中执行点之间的关系可以用执行点之间的关系图表示出来。设函数fi中任意两个执行点为fij1k1与fij2k2，则当k1≠k2时，这两个执行点之间的出现存在执行位置的先后顺序关系。执行点之间的数据流依赖关系形成了执行点之间的数据传递关系。两个执行点之间存在控制依赖关系时，一个执行点可以通过控制依赖关系获得它所依赖的父结点的数据，这部分数据可能是父结点通过数据流依赖关系直接获得的或通过父结点的控制依赖结点获得的。

2.3 关于单变量和执行点的动态切片的定义

以下是动态切片的定义：

[DynamicSlice（d，fkij）d∈def（fkij）=?（DynamicSlice（u，fk1ij1）?{fk1ij1}）?u∈def（fk1ij1）?u∈use（fkij）?（DynamicSlice（P2，fk2ij2）?{fk2ij2}）P2∈def（fk2ij2）?fkij←fk2ij2]其中，d是任意变量，可以是一般性的变量v或者是谓词变量P1， fijk是任意执行点。u在SDG中，离d最近的数据流，P2所在的执行点是d所在执行点的父结点，k1

[DynamicSlice（d，fkij）d∈def（fkij）=DynamicSlice（d_in，fkdi0jd）d_in∈def（fkdi0jd）?fkdi0jd]

这个定义用于对被调函数fi的形参d所在执行点fijk求动态切片。其中，j是参数的编号，j=1，2，…，参数数N（fi）.引入的外部变量d_in与形参变量d对应，jd是第i0个函数fi0中离得最近的那条语句的编号，kd是离赋值d=d_in 最近的执行点位置，必然有外部变量的定义点位置kd

为此，需给出动态切片的一个定义：DynamicSlice（v，fijk）= DynamicSlice（v，fijk-1）=… = DynamicSlice（v，fi0j0k0）.这个定义表示，对于[?]变量v，[?]执行点fijk，当v[?]fijk时，即v不在fijk中出现，关于v和当前执行点fijk的动态切片就是关于v和前一个执行点的动态切片，当v[?]fijk-1时，这个动态切片就是关于v和fijk-2的动态切片，…，一直往前推直到关于v和fi0j0k0的动态切片为止，此时的v[∈]fi0j0k0，即有v∈def（fi0j0k0）或者v∈use（fi0j0k0），这样给出了关于任意一个变量和任意一个执行点的动态切片的定义。

3 评价方法与实例分析

3.1 评价路径和评分方法

设教师需要对第i个学生的程序进行测评，提供的测试数据和结果有nDR组，分别对应学生程序变量集V中的变量varUijv和varRij的值，i是学生序号，j是第几组测试数据，每次有n个测试变量和1个输出结果，即v=1，2，…，n，j=1，2，…，nDR，n≤V中的变量数，nDR≤V中的变量数。用Hij表示第i个学生的第j个执行历史，mij表示Hij中的执行点个数Len（Hij）， Hij={hij1，hij2，…，hijmij}，表示第i个学生的第j个执行历史的执行点集合，第i个学生有nDR个执行历史，表示为执行历史集{Hi1，Hi2，…，Hi，nDR}，这个执行历史集中的每一个执行历史都对应这个学生程序的一条关键的执行路径，作为评价路径，hijmij表示Hij中最后的那个执行点，则定义关于输入输出变量集和执行历史的动态切片为关于每一个输入或输出变量和执行历史中最后那个执行点的动态切片集的并集，即：

[DynamicSlicevarUi，j，1，varUi，j，2，…，varUi，j，nDR，varRij，Hij=v=1nDRDynamicSlice（varUi，j，v，hmijij）?DynamicSlice（varRij，hmijij）]

这里一般要求输入变量或输出变量出现在执行历史中最后的那个执行点，通常该执行点为一条输出语句的执行点，即varUijv∈use（hijmij），varRij∈use（hijmij）.

為了利用前面给出的公式求出关于输入输出变量集和执行历史的动态切片，需要对关于变量和使用该变量的执行点的动态切片的计算作如下定义：

其中，往回看执行历史，找出fi0j0k0，它是执行历史中离fijk最近的那个关于v变量的定义点， 即满足条件：1≤k0

这个定义对应的是定义变量v的赋值表达式右边没有出现形如v_value这样的外部变量的引用这种情况，即没有出现函数调用返回值的引用情况，此时i0=i，该变量属于局部变量，否则同一个变量出现在两个不同的函数中，该变量属于外部变量。

（2） 往回看执行历史，给出如下定义：

[DynamicSlicev_value，fijkv_value∈usefijk?v_value?deffijk=DynamicSlice（v_value，fk0i0j0）?{fk0i0j0}v_value∈def（fk0i0j0）?k0=k-1]

其中，函数fi调用函数fi0，并且根据前面给定的执行历史中执行点的编码方法必然有k0=k-1，根据k0查找执行历史可以确定j0的值，即fijk与fi0j0k0是执行位置相邻的两个执行点，而这两个执行点分别出现在两个不同的函数所对应的执行历史片断中。这个定义对应的是外部变量v_value的赋值定义v_value=v与外部变量v_value的使用出现在两个不同的函数fi0j0k0和fijk中的情况，与函数返回值的处理相对应。

给定需要评分的学生程序，对其执行历史的动态切片或对应的程序按如下公式进行评分：[Scorei=j=1nDRDMij*Sij]，[DMij]表示第j条评价路径的所得分值，[Sij]表示分值所占比例，满足条件：[j=1nDRSij=1]。

3.2 计算实例

给定一个需要评分的C语言程序例子，给出一组测试数据及其对应的执行历史，分析执行点之间的关系，可以得到执行点之间的关系图，运用前面给出的动态切片的定义，可以计算出关于变量和所在执行点（变量的定义点）的动态切片，记录在执行历史的动态切片表中。最终可以求出关于输入输出变量集和执行历史的动态切片DynamicSlice（{n1，a1，s1}，H11），这个动态切片对应的程序比源程序减少了两条语句if（a>0）s=0；，但结果相同，于是可以由教师对DynamicSlice（{n1，a1，s1}，H11）或对这个集合对应的程序进行评分，即可得到一条评价路径的分值。给定几组测试数据，按照这种方法对每组测试数据所得的评价路径都进行评分，按照教师预先设定的分值所占比例可以求出该程序的最终分值，作为这个学生程序的得分。以下是计算过程示例，其中对每个函数的参数和语句给出了相应的编号：

程序：#include "stdio.h" void main（）{ int n1，a1，s1； scanf（”%d”，&n1）； scanf（“%d”，&a1）； s1=f（n1，a1）； printf（“%d”，s1）；}

int f（int n， int a） { int i，s； i=1； s=1； if（a>0） s=0； while（i<=n）{ if（a>0） s=s+2； else {s=s*2； a=2； }

i++；} return（s）； } 测试数据和结果：2，-1，4。

用谓词变量P21表示a>0，用P22表示i<=n.具有相同形式的谓词变量所在的不同执行点，如f259，f2811，f2816都含谓词变量P21，这些执行点的动态切片之间的关系未必形成了包含关系，如有DynamicSlice（P21，f259）[?]DynamicSlice（P21，f2811），但DynamicSlice（P21，f2811）[?]DynamicSlice（P21，f2816），这是因为f2811与f2816具有不同的a变量数据来源，一个来自于f226，另一个来自于f2，1113.任意两个执行点之间都具有顺序关系，这是由执行位置确定的，但不一定具有数据流依赖关系和控制依赖关系，如 f2811与f2816之间是顺序关系，而不存在数据流依赖关系和控制依赖关系。f2，1012和f2，1113，f2，1214和f2811，f2816和f2，1218之间也都只有顺序关系。当变量的值是常量时，关于该变量在其定义点的动态切片为空集。同一个实例的执行点之间存在这样一种情况，执行位置不一定是等距离的执行点实例关系，如f2710，f2715，f2719之间的距离不相同。这是由于改变了形参a的值，造成了P22的值发生了变化，程序的执行走了另一条分支，其中的语句数量不同了。

以下计算关于输入输出变量集和执行历史的动态切片DynamicSlice（{n1，a1，s1}，H11）：

[DynamicSlice（n1，f2216）n1?def（f2216）?n1?use（f2216）=DynamicSlice（n1，f2116）n1?def（f2116）?n1?use（f2116）=DynamicSlice（n1，f414）n1?def（f416）?n1?use（f416）=DynamicSlice（n1，f313）n1∈def（f313）?n1?use（f313）=DynamicSlice（n1，f111）?{f111}n1∈def（f111）?dmin=3-1=2=??{f111}={f111}DynamicSlice（a1，f2216）a1?def（f2216）?a1?use（f2216）=DynamicSlice（a1，f2115）a1?def（f2115）?a1?use（f2115）=DynamicSlice（a1，f414）a1?def（f414）?a1∈use（f414）=DynamicSlice（a1，f212）?{f212}a1∈def（f212）?dmin=4-2=2=??{f212}={f212}DynamicSlice（s1，f2216）s1?def（f2216）?s1∈use（f2216）=DynamicSlice（s1，f2115）?{f2115}s1∈def（f2115）?dmin=22-21=1=DynamicSlice（s_value，f202，13）?{f202，13}?{f2115}s_value∈def（f202，13）?s_value∈use（f2115）?k0=20，k=21，k0=k-1={f111， f122，f133， f144，f521，f622，f723，f824，f1027，f1128，f122，10，f132，11，f142，12，f1527， f1628，f1729，f202，13，f2115}DynamicSlice（{n1，a1，s1}，H11）=DynamicSlice（{n1，a1，s1}，h2211）=DynamicSlice（{n1}，h2211）?DynamicSlice（{a1}，h2211）?DynamicSlice（{s1}，h2211）=DynamicSlice（n1，f2216）n1?def（f2216）?n1?use（f2216）?DynamicSlice（a1，f2216）a1?def（f2216）?n1?use（f2216）?DynamicSlice（s1，f2216）s1?def（f2216）?s1∈use（f2216）]

[={f111}?{f212}?{f111， f122，f133， f144，f521，f622，f723，f824，f1027，f1128，f122，10， f132，11，f142，12，f1527，f1628f1729，f202，13，f2115}={f111， f122，f133， f144，f521，f622，f723，f824，f1027，f1128，f122，10，f132，11，f142，12，f1527， f1628f1729，f202，13，f2115}]

4 结束语

对于需要测评的C语言程序，通过计算出其执行历史的动态切片，对这个动态切片或与这个动态切片对应的程序进行评价，可以给出这个源程序的测评分。由于执行历史对应评价路径，它的动态切片能与源程序结果一致，但对应的程序更简单，而且是可执行的，这样就在一定程度上降低了评价的难度，因此评价会更准确一些。

参考文献：

[1] Bogdan KOREL，Janusz LASKI，DYNAMIC PROGRAM SLICING，Information Processing Letters[J].1988（29）：155-163.

[2] Bogdan Korel，Jurgen Rilling，Dynamic Program Slicing Methods，Information and Software Technology[J].December 1998.https：//www.researchgate.net/.

[3] A? Beszedes，T Gergely，Z M Szabo，J Csirik，T Gyimothy.Dynamic Slicing Method for Maintenance of Large C Programs，2001.

[4] 刘磊。基于动态程序切片技术的测试用例自动生成研究[D].硕士学位论文，2010.

[5] Mariam Kamkar，Peter Fritzson，Nahid Shahmehri.Interprocedural Dynamic SlicingApplied toInterprocedural Data Flow Testing[C]. October 1993：386-395，https：// www.researchgate.net/.