閻萍

摘要：針對C語言程序的評價問題，給出了執(zhí)行點和執(zhí)行歷史相關(guān)概念的描述，討論了執(zhí)行點之間的關(guān)系，給出了關(guān)于單變量和執(zhí)行點的動態(tài)切片的定義，在此基礎(chǔ)上，給出了關(guān)于輸入輸出變量集和執(zhí)行歷史的動態(tài)切片的計算公式以及相應的程序評分方法，并通過一個實例給出了計算過程。

關(guān)鍵詞：C語言；動態(tài)切片；執(zhí)行點；執(zhí)行歷史

中圖分類號：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 概述

動態(tài)切片方法有多種并具有廣泛的應用，例如，文獻[1][2]提出了幾種動態(tài)切片計算方法，并對可執(zhí)行和不可執(zhí)行的動態(tài)切片情況進行了分析，文獻[3]運用動態(tài)切片方法維護大型的C語言程序，文獻[4]運用動態(tài)切片技術(shù)實現(xiàn)測試用例的自動生成，文獻[5]運用過程間動態(tài)切片方法實現(xiàn)過程間數(shù)據(jù)流測試。由于動態(tài)切片方法能夠識別出所有對變量的值起作用的代碼，因而可以用于程序測評。本文在運用和借鑒這些方法的基礎(chǔ)上，提出了關(guān)于單變量和執(zhí)行點的動態(tài)切片的定義，并用于C語言程序的評價。

2 相關(guān)概念與動態(tài)切片方法

2.1 執(zhí)行點和執(zhí)行歷史的定義

執(zhí)行點是語句實例和時間關(guān)系的描述，時間關(guān)系描述了語句實例的執(zhí)行位置。為了進一步解釋執(zhí)行點的含義，首先對C語言程序中的函數(shù)及其參數(shù)和語句進行編號，并給出執(zhí)行點的相應描述。函數(shù)的內(nèi)容包括4種情況：形參，函數(shù)內(nèi)的語句，函數(shù)調(diào)用，返回語句的處理。設(shè)程序有N1個函數(shù)。首先從主函數(shù)開始，按調(diào)用順序從1開始對函數(shù)進行編號，第i個函數(shù)表示為fi，N1≥i≥1. 主函數(shù)f1語句從1開始編號，遇到函數(shù)調(diào)用時，處理實參，如實參n1對應的形參為n時，引入外部變量n_in，把該實參n1處理成賦值形式：n_in=n1，并對函數(shù)調(diào)用語句進行編號，其他函數(shù)按調(diào)用順序分別進行編號。設(shè)函數(shù)調(diào)用中的主調(diào)函數(shù)為fi，被調(diào)函數(shù)為fi+1，函數(shù)fi+1的編號方法：首先處理形參，如形參n處理成n=n_in，并按形參順序從1開始編號，設(shè)函數(shù)fi+1的形式參數(shù)數(shù)為N（fi+1），則函數(shù)fi+1的參數(shù)編號范圍為1…N（fi+1），函數(shù)fi+1內(nèi)第1條語句編號為N（fi+1）+1，其他語句按序編號。對return（s）語句引入外部變量s_value處理成賦值形式如s_value=s后編號。引入外部變量的目的是為了在計算動態(tài)切片時能夠?qū)崿F(xiàn)對每個函數(shù)進行封裝處理。按語句順序和函數(shù)的調(diào)用順序?qū)γ總€函數(shù)中的每條語句進行編號，引入外部變量把每個函數(shù)的參數(shù)處理成賦值形式，并從1開始進行連續(xù)編號。函數(shù)fi的編號方法：設(shè)函數(shù)fi的參數(shù)數(shù)為N（fi），則函數(shù)fi的參數(shù)編號范圍為1…N（fi），而對函數(shù)fi的語句則從N（fi）+1開始連續(xù)編號。設(shè)C語言程序的第i個函數(shù)fi的第j條語句為fij，它的實例執(zhí)行位置為k，則執(zhí)行點記為fijk.執(zhí)行點的執(zhí)行位置k按程序執(zhí)行過程中語句實例出現(xiàn)的先后順序從1開始連續(xù)編號。執(zhí)行歷史表示為程序某次執(zhí)行過程中所有執(zhí)行點組成的有序集，則執(zhí)行歷史可以記為H={fijk|i=1，…，N1，j∈{1，…，N2}，N2是fi的形參數(shù)+fi的語句數(shù)+fi的實參數(shù)之和，k≥1}.

一個函數(shù)中的變量可以分為兩類：一般性的變量和謂詞變量，其中一般性的變量的定義形式分為常量形式的變量定義和含變量引用形式的變量定義，前者只定義變量而不使用其他變量，后者即定義變量又使用變量進行定義。對函數(shù)fi的不同的執(zhí)行點中出現(xiàn)的形式相同的邏輯表達式使用同一個謂詞變量來表示，這樣就限定了一個謂詞變量P中不可能出現(xiàn)對該謂詞變量P自身的引用情況，但是一個謂詞變量P可能控制另一個同名謂詞變量P計算其值所需的原始數(shù)據(jù)的定義。謂詞變量的值是一個邏輯值，每次都要根據(jù)它所表示的邏輯表達式中出現(xiàn)的引用變量的當前值重新進行計算。謂詞變量用于根據(jù)執(zhí)行點之間的控制依賴關(guān)系實現(xiàn)一個執(zhí)行點對另一個執(zhí)行點的執(zhí)行進行控制。執(zhí)行點fijk中定義的變量和使用的變量分別表示為集合def（fijk）和use（fijk），定義變量值的執(zhí)行點就是變量的定義點，使用變量值的執(zhí)行點就是變量的使用點。

2.2 執(zhí)行點之間的關(guān)系

給定一個程序以后，首先通過靜態(tài)分析形成系統(tǒng)依賴圖SDG.給定程序的一個執(zhí)行歷史，其中的執(zhí)行點之間存在的關(guān)系分為三類：順序關(guān)系，控制依賴關(guān)系，數(shù)據(jù)流依賴關(guān)系，其中的控制依賴和數(shù)據(jù)流依賴關(guān)系可以通過查找SDG獲知。而控制依賴關(guān)系可能是多級的，分為直接和間接控制依賴關(guān)系。執(zhí)行歷史中執(zhí)行點之間的關(guān)系可以用執(zhí)行點之間的關(guān)系圖表示出來。設(shè)函數(shù)fi中任意兩個執(zhí)行點為fij1k1與fij2k2，則當k1≠k2時，這兩個執(zhí)行點之間的出現(xiàn)存在執(zhí)行位置的先后順序關(guān)系。執(zhí)行點之間的數(shù)據(jù)流依賴關(guān)系形成了執(zhí)行點之間的數(shù)據(jù)傳遞關(guān)系。兩個執(zhí)行點之間存在控制依賴關(guān)系時，一個執(zhí)行點可以通過控制依賴關(guān)系獲得它所依賴的父結(jié)點的數(shù)據(jù)，這部分數(shù)據(jù)可能是父結(jié)點通過數(shù)據(jù)流依賴關(guān)系直接獲得的或通過父結(jié)點的控制依賴結(jié)點獲得的。

2.3 關(guān)于單變量和執(zhí)行點的動態(tài)切片的定義

以下是動態(tài)切片的定義：

[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是任意執(zhí)行點。u在SDG中，離d最近的數(shù)據(jù)流，P2所在的執(zhí)行點是d所在執(zhí)行點的父結(jié)點，k1

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

這個定義用于對被調(diào)函數(shù)fi的形參d所在執(zhí)行點fijk求動態(tài)切片。其中，j是參數(shù)的編號，j=1，2，…，參數(shù)數(shù)N（fi）.引入的外部變量d_in與形參變量d對應，jd是第i0個函數(shù)fi0中離得最近的那條語句的編號，kd是離賦值d=d_in 最近的執(zhí)行點位置，必然有外部變量的定義點位置kd

為此，需給出動態(tài)切片的一個定義：DynamicSlice（v，fijk）= DynamicSlice（v，fijk-1）=… = DynamicSlice（v，fi0j0k0）.這個定義表示，對于[?]變量v，[?]執(zhí)行點fijk，當v[?]fijk時，即v不在fijk中出現(xiàn)，關(guān)于v和當前執(zhí)行點fijk的動態(tài)切片就是關(guān)于v和前一個執(zhí)行點的動態(tài)切片，當v[?]fijk-1時，這個動態(tài)切片就是關(guān)于v和fijk-2的動態(tài)切片，…，一直往前推直到關(guān)于v和fi0j0k0的動態(tài)切片為止，此時的v[∈]fi0j0k0，即有v∈def（fi0j0k0）或者v∈use（fi0j0k0），這樣給出了關(guān)于任意一個變量和任意一個執(zhí)行點的動態(tài)切片的定義。

3 評價方法與實例分析

3.1 評價路徑和評分方法

設(shè)教師需要對第i個學生的程序進行測評，提供的測試數(shù)據(jù)和結(jié)果有nDR組，分別對應學生程序變量集V中的變量varUijv和varRij的值，i是學生序號，j是第幾組測試數(shù)據(jù)，每次有n個測試變量和1個輸出結(jié)果，即v=1，2，…，n，j=1，2，…，nDR，n≤V中的變量數(shù)，nDR≤V中的變量數(shù)。用Hij表示第i個學生的第j個執(zhí)行歷史，mij表示Hij中的執(zhí)行點個數(shù)Len（Hij）， Hij={hij1，hij2，…，hijmij}，表示第i個學生的第j個執(zhí)行歷史的執(zhí)行點集合，第i個學生有nDR個執(zhí)行歷史，表示為執(zhí)行歷史集{Hi1，Hi2，…，Hi，nDR}，這個執(zhí)行歷史集中的每一個執(zhí)行歷史都對應這個學生程序的一條關(guān)鍵的執(zhí)行路徑，作為評價路徑，hijmij表示Hij中最后的那個執(zhí)行點，則定義關(guān)于輸入輸出變量集和執(zhí)行歷史的動態(tài)切片為關(guān)于每一個輸入或輸出變量和執(zhí)行歷史中最后那個執(zhí)行點的動態(tài)切片集的并集，即：

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

這里一般要求輸入變量或輸出變量出現(xiàn)在執(zhí)行歷史中最后的那個執(zhí)行點，通常該執(zhí)行點為一條輸出語句的執(zhí)行點，即varUijv∈use（hijmij），varRij∈use（hijmij）.

為了利用前面給出的公式求出關(guān)于輸入輸出變量集和執(zhí)行歷史的動態(tài)切片，需要對關(guān)于變量和使用該變量的執(zhí)行點的動態(tài)切片的計算作如下定義：

其中，往回看執(zhí)行歷史，找出fi0j0k0，它是執(zhí)行歷史中離fijk最近的那個關(guān)于v變量的定義點， 即滿足條件：1≤k0

這個定義對應的是定義變量v的賦值表達式右邊沒有出現(xiàn)形如v_value這樣的外部變量的引用這種情況，即沒有出現(xiàn)函數(shù)調(diào)用返回值的引用情況，此時i0=i，該變量屬于局部變量，否則同一個變量出現(xiàn)在兩個不同的函數(shù)中，該變量屬于外部變量。

（2） 往回看執(zhí)行歷史，給出如下定義：

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

其中，函數(shù)fi調(diào)用函數(shù)fi0，并且根據(jù)前面給定的執(zhí)行歷史中執(zhí)行點的編碼方法必然有k0=k-1，根據(jù)k0查找執(zhí)行歷史可以確定j0的值，即fijk與fi0j0k0是執(zhí)行位置相鄰的兩個執(zhí)行點，而這兩個執(zhí)行點分別出現(xiàn)在兩個不同的函數(shù)所對應的執(zhí)行歷史片斷中。這個定義對應的是外部變量v_value的賦值定義v_value=v與外部變量v_value的使用出現(xiàn)在兩個不同的函數(shù)fi0j0k0和fijk中的情況，與函數(shù)返回值的處理相對應。

給定需要評分的學生程序，對其執(zhí)行歷史的動態(tài)切片或?qū)某绦虬慈缦鹿竭M行評分：[Scorei=j=1nDRDMij*Sij]，[DMij]表示第j條評價路徑的所得分值，[Sij]表示分值所占比例，滿足條件：[j=1nDRSij=1]。

3.2 計算實例

給定一個需要評分的C語言程序例子，給出一組測試數(shù)據(jù)及其對應的執(zhí)行歷史，分析執(zhí)行點之間的關(guān)系，可以得到執(zhí)行點之間的關(guān)系圖，運用前面給出的動態(tài)切片的定義，可以計算出關(guān)于變量和所在執(zhí)行點（變量的定義點）的動態(tài)切片，記錄在執(zhí)行歷史的動態(tài)切片表中。最終可以求出關(guān)于輸入輸出變量集和執(zhí)行歷史的動態(tài)切片DynamicSlice（{n1，a1，s1}，H11），這個動態(tài)切片對應的程序比源程序減少了兩條語句if（a>0）s=0；，但結(jié)果相同，于是可以由教師對DynamicSlice（{n1，a1，s1}，H11）或?qū)@個集合對應的程序進行評分，即可得到一條評價路徑的分值。給定幾組測試數(shù)據(jù)，按照這種方法對每組測試數(shù)據(jù)所得的評價路徑都進行評分，按照教師預先設(shè)定的分值所占比例可以求出該程序的最終分值，作為這個學生程序的得分。以下是計算過程示例，其中對每個函數(shù)的參數(shù)和語句給出了相應的編號：

程序：#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）； } 測試數(shù)據(jù)和結(jié)果：2，-1，4。

用謂詞變量P21表示a>0，用P22表示i<=n.具有相同形式的謂詞變量所在的不同執(zhí)行點，如f259，f2811，f2816都含謂詞變量P21，這些執(zhí)行點的動態(tài)切片之間的關(guān)系未必形成了包含關(guān)系，如有DynamicSlice（P21，f259）[?]DynamicSlice（P21，f2811），但DynamicSlice（P21，f2811）[?]DynamicSlice（P21，f2816），這是因為f2811與f2816具有不同的a變量數(shù)據(jù)來源，一個來自于f226，另一個來自于f2，1113.任意兩個執(zhí)行點之間都具有順序關(guān)系，這是由執(zhí)行位置確定的，但不一定具有數(shù)據(jù)流依賴關(guān)系和控制依賴關(guān)系，如 f2811與f2816之間是順序關(guān)系，而不存在數(shù)據(jù)流依賴關(guān)系和控制依賴關(guān)系。f2，1012和f2，1113，f2，1214和f2811，f2816和f2，1218之間也都只有順序關(guān)系。當變量的值是常量時，關(guān)于該變量在其定義點的動態(tài)切片為空集。同一個實例的執(zhí)行點之間存在這樣一種情況，執(zhí)行位置不一定是等距離的執(zhí)行點實例關(guān)系，如f2710，f2715，f2719之間的距離不相同。這是由于改變了形參a的值，造成了P22的值發(fā)生了變化，程序的執(zhí)行走了另一條分支，其中的語句數(shù)量不同了。

以下計算關(guān)于輸入輸出變量集和執(zhí)行歷史的動態(tài)切片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 結(jié)束語

對于需要測評的C語言程序，通過計算出其執(zhí)行歷史的動態(tài)切片，對這個動態(tài)切片或與這個動態(tài)切片對應的程序進行評價，可以給出這個源程序的測評分。由于執(zhí)行歷史對應評價路徑，它的動態(tài)切片能與源程序結(jié)果一致，但對應的程序更簡單，而且是可執(zhí)行的，這樣就在一定程度上降低了評價的難度，因此評價會更準確一些。

參考文獻：

[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] 劉磊。基于動態(tài)程序切片技術(shù)的測試用例自動生成研究[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/.