張家奇，牟永敏，張志華

（網(wǎng)絡(luò)文化與數(shù)字傳播北京市重點實驗室（北京信息科技大學(xué)），北京 100101）

（*通信作者電子郵箱879632300@qq.com）

0 引言

近年來，隨著軟件產(chǎn)業(yè)化的發(fā)展，軟件測試逐漸成為人們關(guān)注的焦點。軟件測試的目的在于檢驗?zāi)硞€軟件系統(tǒng)是否滿足規(guī)定的要求，即驗證軟件設(shè)計與實現(xiàn)是否一致。對于小規(guī)模的軟件系統(tǒng)，人工可以完成一致性的驗證。對于軟件規(guī)模和復(fù)雜度較高的軟件系統(tǒng)，人工難以完成一致性的驗證。自動完成軟件設(shè)計與實現(xiàn)的一致性驗證工作變得越來越重要。

軟件實現(xiàn)與設(shè)計一致性驗證是指對已完成的軟件系統(tǒng)，驗證其功能實現(xiàn)是否按照軟件設(shè)計說明書的要求完成，是一種非常重要的測試［1］。Riedl-Ehrenleitner 等［2］提出面向設(shè)計模型和代碼的一致性檢測方法，通過一致性規(guī)則實時驗證代碼和設(shè)計模型的一致性，用于模型驅(qū)動的軟件開發(fā)，并在開發(fā)過程中實時檢測代碼與設(shè)計模型的一致性，沒有考慮代碼的編寫細節(jié)。曾一等［3-4］提出基于統(tǒng)一建模語言（Unified Modeling Language，UML）模型與Java 代碼一致性檢測的方法，對設(shè)計和實現(xiàn)的動態(tài)交互信息進行一致性驗證，但沒有對具體方法的實現(xiàn)進行驗證。牟永敏等［1］提出一種針對文檔和源代碼的測試方法，該方法基于函數(shù)調(diào)用路徑［5］，從設(shè)計文檔中獲取函數(shù)的功能描述，建立設(shè)計功能簇模型；從源代碼中提取實現(xiàn)函數(shù)特征，對比已知的模板集獲取實現(xiàn)函數(shù)的功能描述，建立系統(tǒng)功能簇模型；通過驗證兩個模型的一致性完成設(shè)計與實現(xiàn)一致性驗證問題。但是該方法需人工分析設(shè)計文檔以及大量的模板集，限制了模型建立的效率，并且該方法沒有對比設(shè)計函數(shù)的實現(xiàn)細節(jié)與實際函數(shù)的實現(xiàn)細節(jié)是否一致。

本文參考文獻［1］中提出的一致性驗證方法，提出了一種面向偽代碼的函數(shù)特征提取方法，選取設(shè)計文檔中的偽代碼和程序源代碼為研究對象，通過驗證偽代碼和源代碼中函數(shù)特征的一致性完成設(shè)計與實現(xiàn)的一致性檢測。此處申明本文研究的前提為設(shè)計文檔中包含偽代碼，且偽代碼語義正確。

1 本文方法

本文研究思路基于軟件設(shè)計的模塊化設(shè)計原理。模塊化原理就是把程序劃分成若干個模塊，每個模塊完成以一個子功能，把這些模塊集中起來組成一個整體，可以完成指定的功能，滿足問題的需求［6］。模塊化原理不僅使軟件結(jié)構(gòu)清晰，而且讓軟件容易測試和調(diào)試。

軟件設(shè)計過程中遵循模塊化原理。同樣，設(shè)計文檔也遵循模塊化原理，詳細描述各個模塊的實現(xiàn)算法、邏輯流程等。從文檔對各模塊的偽代碼描述和程序源代碼的各模塊中提取函數(shù)特征，并建立設(shè)計特征模型和軟件實現(xiàn)特征模型，通過計算模型的相似度解決設(shè)計與實現(xiàn)的一致性驗證問題。本文一致性檢測框架如圖1所示。

圖1 一致性檢測框架Fig.1 Framework of consistency detection

2 函數(shù)特征的提取

在軟件實現(xiàn)和設(shè)計一致性檢測中，偽代碼和源代碼的表征方式?jīng)Q定了軟件設(shè)計信息和實現(xiàn)信息的利用程度。在代碼克隆領(lǐng)域，代碼的表征方式分為文本［7］、詞匯［8］、語法［9］和語義［10-11］四個層次［12］。由于偽代碼變量不需要聲明、缺乏語法規(guī)范的特點，文本、詞匯的表征方式不能充分利用偽代碼的信息。語法的表征方式，例如基于語法分析樹的方式，會造成一致性驗證算法復(fù)雜度的提升。語義的表征方式，利用代碼語義信息進行驗證，其中，語義信息是指能夠反映一段代碼功能的信息，比如代碼的控制流和數(shù)據(jù)流［12］971。本文采用基于語義的表征方式，語義信息為代碼的控制流，基于代碼控制流獲取函數(shù)特征。

函數(shù)特征分為外部特征和內(nèi)部特征。外部特征為函數(shù)間調(diào)用關(guān)系，內(nèi)部特征為函數(shù)控制流信息，包括基本塊序列和控制流圖。函數(shù)間調(diào)用關(guān)系反映了系統(tǒng)的結(jié)構(gòu)［13］，每個函數(shù)內(nèi)部的控制流信息反映了函數(shù)的內(nèi)部結(jié)構(gòu)，因此選其作為函數(shù)特征并建立特征模型。函數(shù)特征提取具體過程如下：

2.1 中間表示的生成

偽代碼和源代碼中的控制結(jié)構(gòu)會造成控制流的改變，難以直接從中獲取控制流信息，因此將其轉(zhuǎn)換成一種按順序執(zhí)行的語句序列——中間表示。該過程包括偽代碼中間表示的生成和源代碼中間表示的生成。

2.1.1 偽代碼中間表示的生成

偽代碼中間表示（Pseudocode Intermediate Representation，PIR）是一種按順序執(zhí)行的語句序列。常見的中間表示有很多形式，如三元式、四元式、后綴式、語法樹等［14］，本文采用三元式。在生成PIR 過程中，首先對偽代碼進行語法規(guī)范，根據(jù)語法規(guī)范對偽代碼進行詞法和語法分析，生成語法分析樹；然后遍歷語法分析樹，根據(jù)語法制導(dǎo)翻譯將其中的控制結(jié)構(gòu)轉(zhuǎn)換為順序執(zhí)行的語句和跳轉(zhuǎn)語句——中間代碼；最后對中間代碼劃分基本塊，得到中間表示。

1）偽代碼語法規(guī)范。

由于人們在描述算法時使用的偽碼并不相同［6］128，難以一般化，本文使用一種較為通用語法規(guī)則來規(guī)范偽代碼。語法規(guī)則用擴展巴科斯范式表示，語法規(guī)則產(chǎn)生式如下：

其中：每一個分號語句為一條規(guī)則，大寫字母開頭為詞法規(guī)則，小寫字母開頭為語法規(guī)則。NL 表示換行符，語法規(guī)則中的單引號內(nèi)容和大寫單詞表示匹配對應(yīng)的字符；prog 表示偽代碼的一個邏輯結(jié)構(gòu)，包括一個或多個函數(shù)定義；functiondef 為函數(shù)定義，包括語句集stats；id 表示標(biāo)識符；number 表示數(shù)字。為方便后文引用，語法規(guī)則結(jié)尾添加編號。

語句集stats 包含if語句、if_else 語句、while 語句、repeat語句、for語句、賦值語句、函數(shù)調(diào)用語句等。expr為表達式，包含邏輯表達式、關(guān)系表達式、算數(shù)表達式等。

2）生成語法分析樹。

使用ANTLR（ANother Tool for Language Recognition）生成語法分析樹和樹遍歷器。ANTLR 是一款強大的語法分析器生成工具，可以根據(jù)語言的語法生成一個語法分析器和語法分析樹遍歷器，并自動建立語法分析樹。

3）語法制導(dǎo)翻譯。

語法制導(dǎo)翻譯是在語法分析過程中，根據(jù)每個產(chǎn)生式所對應(yīng)的語義子程序進行翻譯的方法［14］22。通過語法制導(dǎo)翻譯可以將偽代碼語句翻譯為按順序執(zhí)行的語句。使用ANTLR內(nèi)置的樹遍歷器遍歷語法分析樹，樹遍歷器采用遞歸下降的分析方法遍歷語法分析樹，在遍歷的過程中使用語法制導(dǎo)翻譯，生成按順序執(zhí)行的中間代碼。

偽代碼中函數(shù)定義語句、函數(shù)調(diào)用語句、賦值語句、關(guān)系表達式并不影響模塊的控制流，這些語句的產(chǎn)生式對應(yīng)語法規(guī)則（1）、（7）、（8）、（11），其語義子程序（翻譯規(guī)則）不需要對原語句進行處理，即在中間表示中復(fù)用原語句。

偽代碼中布爾表達式經(jīng)常用來改變控制流和計算邏輯值，但其使用意圖要根據(jù)其語法上下文來確定，例如關(guān)鍵字IF后面的布爾表達式用來改變控制流，而一個賦值語句右部的布爾表達式用來表示一個邏輯值。因此將控制語句（IF-ELSE、WHILE 語句等）以及布爾表達式結(jié)合進行語法制導(dǎo)翻譯，再將翻譯的結(jié)果填寫在中間表示中。

布爾表達式是布爾運算符作用于布爾變量或關(guān)系表達式上而構(gòu)成的［14］315，控制結(jié)構(gòu)是布爾表達式作用于控制語句而構(gòu)成的。布爾表達式生成文法的產(chǎn)生式對應(yīng)語法規(guī)則（8）～（10）。控制結(jié)構(gòu)生成文法的產(chǎn)生式對應(yīng)語法規(guī)則（2）～（6）。由于篇幅限制，只列出一種while 循環(huán)語句，for 和repeat 循環(huán)語句語義子程序與while循環(huán)語句類似。

由于邏輯運算短路的特點，偽代碼中會出現(xiàn)短路代碼，進而影響程序控制流。因此將運算符and、or、not 翻譯成goto 語句。運算符本身不出現(xiàn)在中間表示中，布爾表達式的值通過語句序列中的位置來表示。如表1 所示，使用轉(zhuǎn)移語句來翻譯控制語句以及布爾表達式。

表1 轉(zhuǎn)移語句Tab.1 Transfer statements

PIR 中的語句將按順序執(zhí)行，當(dāng)遇到以上語句時，執(zhí)行過程就會跳轉(zhuǎn)。在一個語句前加上前綴“Li：”，表示將標(biāo)號Li附加到該語句，其中i為正整數(shù)。同一個語句可以同時擁有多個標(biāo)號。

為方便描述，需賦予文法符號（非終結(jié)符）屬性：text、code、begin、next、true、false。其中，text 表示語句或表達式未經(jīng)處理的token 流，code 表示語句翻譯后的代碼，begin、next、ture、false 表示標(biāo)號。如stat.code 表示語句stat 翻譯后的代碼；stat.begin 表示語句stat 的標(biāo)號；stat.next 表示語句stat 后一條語句的標(biāo)號；expr.true 表示布爾表達式expr 為真時跳轉(zhuǎn)到目標(biāo)語句的標(biāo)號。后文圖中“=”表示賦值，newlabel 表示產(chǎn)生一個新的前綴標(biāo)號“Li”；gen（）表示一個語句，如：假設(shè)expr.true 的值為“L1”，則gen（“goto”expr.true），表示語句“goto L1”。

由于關(guān)系表達式、函數(shù)定義語句、函數(shù)調(diào)用語句、賦值語句對應(yīng)生成文法的語法制導(dǎo)規(guī)則不需要對原語句進行特殊處理，因此本文只列出語法規(guī)則（1）所對應(yīng)語法制導(dǎo)規(guī)則。如圖2（a）所示。

圖2 語法制導(dǎo)定義Fig.2 Syntax-directed definitions

布爾表達式的語法制導(dǎo)翻譯規(guī)則與編譯原理［14］317中布爾表達式制導(dǎo)翻譯規(guī)則類似，不做詳細描述。圖2（b）～（d）分別列出了語法規(guī)則（2）、（3）、（5）對應(yīng)的語法制導(dǎo)翻譯規(guī)則。根據(jù)圖2 語法制導(dǎo)翻譯規(guī)則，可將偽代碼翻譯為中間代碼，如圖3（a）中偽代碼翻譯為圖3（b）中的中間代碼。

4）中間代碼優(yōu)化和基本塊的劃分。

如圖3（b）中語句L7，語法制導(dǎo)翻譯生成的中間代碼存在空語句，需對中間代碼進行優(yōu)化。使用ANTLR 生成中間代碼對應(yīng)的語法分析樹，遍歷語法分析樹并使用算法1 對其優(yōu)化，優(yōu)化結(jié)果如圖3（c）。

算法1 中間代碼優(yōu)化算法。

為了更好地分析控制流，將中間代碼劃分為基本塊?；緣K是滿足下列條件的最大的連續(xù)中間表示語句序列［15］：

a）控制流只能從基本塊的第一個語句進入該塊。即沒有跳轉(zhuǎn)到基本塊中間的轉(zhuǎn)移指令。

b）除了基本塊的最后一個語句，控制流在離開基本塊之前不會停止或跳轉(zhuǎn)。

因此，每一個基本塊對應(yīng)一個入口語句，只需確定入口語句即可劃分基本塊，選擇入口語句規(guī)則如下：

a）中間代碼的第一個語句；

b）能由轉(zhuǎn)移語句轉(zhuǎn)移到的語句；

c）緊跟在一個轉(zhuǎn)移語句之后的語句。

每個入口語句對應(yīng)的基本塊包括了從它自己開始，直到下一個入口語句或結(jié)尾語句之間的所有語句。如圖4 所示，對圖3（c）中優(yōu)化結(jié)果的基本塊劃分，其中bb代表基本塊。

圖3 偽代碼翻譯及優(yōu)化結(jié)果Fig.3 Pseudocode translation and optimization results

圖4 基本塊劃分結(jié)果Fig.4 Result of basic block partitioning

2.1.2 源代碼中間表示的生成

GNU 編譯器套件（GNU Compiler Collection，GCC）可將源代碼轉(zhuǎn)換為中間表示。通過GCC 調(diào)試選項-fdump-tree-cfg 并輸入源代碼，即可得到GCC編譯器生成的cfg中間文件。文獻［1］中使用該方法提取源代碼函數(shù)結(jié)構(gòu)特征。cfg 文件中的中間代碼是GCC 編譯器對源代碼進行詞法和語法分析后得到的中間表示，其中包含劃分基本塊后的結(jié)果以及基本塊的執(zhí)行順序。如圖5（a）中源代碼以及通過GCC 編譯器生成圖5（b）中cfg中間碼。

2.2 函數(shù)特征提取

相關(guān)定義如下：

定義1函數(shù)調(diào)用關(guān)系圖可以表示為一種有向圖G=〈V，E〉。其中：V是節(jié)點集，每一個節(jié)點代表一個函數(shù)；E=｛（x，y）|x，y∈V｝是弧集，表示函數(shù)x調(diào)用了函數(shù)y。

定義2控制流圖是一種簡單的控制流表示方法，描述邏輯控制流。控制流圖G是一種有向圖G=〈B，D〉。其中：B為節(jié)點集合，每一個節(jié)點代表一條或多條語句，即一個基本塊；D=｛（x，y）|x，y∈N+｝是弧集，表示控制流向。

定義3基本塊序列（Basic Block Sequence，BBS）為一個有序序列bbs=b1，b2，…，bi，bj∈｛seq，con_jump，uncon_jump，seq_cj，seq_nj，return｝。其中：bj表示第j個基本塊；seq為只包含順序語句的基本塊；uncon_jump為只包含無條件轉(zhuǎn)移語句的基本塊；con_jump為只包含條件轉(zhuǎn)移語句的基本塊；seq_cj為包含順序語句和條件轉(zhuǎn)移語句的基本塊；seq_nj表示包含順序語句和無條件轉(zhuǎn)移語句的基本塊；return表示包含return 的基本塊。

1）函數(shù)調(diào)用關(guān)系的提取。

偽代碼函數(shù)調(diào)用關(guān)系的獲取。在遍歷語法分析樹的過程中，匹配functiondef 規(guī)則可獲取主調(diào)函數(shù)名稱及參數(shù)信息，匹配stat 規(guī)則中函數(shù)調(diào)用規(guī)則“id′（′args？′）′”可獲取被調(diào)函數(shù)名稱及參數(shù)信息。functiondef 規(guī)則結(jié)束則完成主調(diào)函數(shù)調(diào)用信息的提取，遍歷整個語法分析樹，即可獲取全部函數(shù)調(diào)用信息并生成函數(shù)調(diào)用關(guān)系圖。

源代碼函數(shù)調(diào)用關(guān)系的獲取。使用ANTLR，將cfg 文件輸入，生成語法分析樹。遍歷語法分析樹，匹配函數(shù)定義和函數(shù)調(diào)用語句，獲取函數(shù)調(diào)用關(guān)系。圖6 所示為源碼以及根據(jù)提取的函數(shù)調(diào)用關(guān)系生成的函數(shù)調(diào)用關(guān)系圖。

2）控制流信息的提取。

控制流信息包括函數(shù)內(nèi)部的控制流圖和基本塊序列。在遍歷語法分析樹的過程中，根據(jù)基本塊中是否包含條件轉(zhuǎn)移語句、無條件轉(zhuǎn)移語句以及return 語句，判定基本塊，獲取基本塊序列。同時匹配轉(zhuǎn)移語句中的“goto bbi”，獲取基本塊流向，得到控制流圖。如圖5（c）中控制流圖，圖中節(jié)點為基本塊，其對應(yīng)的基本塊序列bbs=uncon_jump，seq，con_jump，seq，return。

圖5 中間代碼和控制流Fig.5 Intermediate code and control flow

圖6 源代碼及其對應(yīng)的函數(shù)調(diào)用關(guān)系Fig.6 Source code and corresponding function call relationship

3 特征模型的建立對比

3.1 特征模型的建立

設(shè)計文檔中的偽代碼描述了每一模塊的實現(xiàn)方式，包括實現(xiàn)算法、邏輯流程等，通過分析設(shè)計文檔中偽代碼，獲取設(shè)計函數(shù)間調(diào)用關(guān)系以及設(shè)計函數(shù)控制流，建立設(shè)計特征模型。通過靜態(tài)分析源代碼獲取實現(xiàn)函數(shù)調(diào)用關(guān)系以及每個函數(shù)的控制流，建立軟件實現(xiàn)特征模型。由于圖能有效表示對象的屬性以及對象之間的關(guān)系［16］，因此采用圖來表示函數(shù)調(diào)用關(guān)系和函數(shù)控制流信息。

根據(jù)函數(shù)特征中的函數(shù)間調(diào)用關(guān)系和函數(shù)控制流信息，分別建立函數(shù)調(diào)用關(guān)系圖和控制流圖。以函數(shù)調(diào)用關(guān)系圖為載體，將圖中每個節(jié)點映射到對應(yīng)函數(shù)的基本塊序列和控制流圖，從而建立設(shè)計特征模型和軟件實現(xiàn)特征模型。

3.2 特征模型對比

對比軟件設(shè)計與實現(xiàn)的函數(shù)調(diào)用關(guān)系圖可以驗證實際系統(tǒng)是否按照設(shè)計要求的系統(tǒng)結(jié)構(gòu)實現(xiàn)。對比軟件設(shè)計與實現(xiàn)函數(shù)的控制流圖可以檢查每個函數(shù)否是按指定的邏輯流程實現(xiàn)。因此，特征模型的對比包括函數(shù)調(diào)用關(guān)系圖和函數(shù)控制流圖的對比。

特征模型對比過程：首先進行外部特征（函數(shù)調(diào)用關(guān)系圖）的對比，通過計算函數(shù)調(diào)用關(guān)系圖的相似度來驗證外部特征的一致性。如果外部特征（函數(shù)調(diào)用關(guān)系圖）不一致，說明實際系統(tǒng)沒有按照設(shè)計要求的系統(tǒng)結(jié)構(gòu)進行實現(xiàn)，直接給出系統(tǒng)結(jié)構(gòu)不一致的檢測結(jié)果。如果外部特征（函數(shù)調(diào)用關(guān)系圖）一致，則獲取函數(shù)調(diào)用關(guān)系圖中函數(shù)的匹配狀態(tài)，并對匹配函數(shù)進行內(nèi)部特征（控制流圖）的對比。通過計算控制流圖的相似度驗證內(nèi)部特征的一致性，過程中可獲取獨立路徑的匹配狀況；然后逐一比對已匹配的獨立路徑，對路徑中每一個節(jié)點（基本塊）類型進行匹配，并標(biāo)記類型不匹配的基本塊；最終獲取類型不匹配的基本塊標(biāo)號，作為一致性檢測結(jié)果。

3.3 相似度的計算

定義4圖G使用二元組表示，即G=（V，E）。其中：V為圖G中的所有節(jié)點的集合；E?V×V表示邊的集合。

圖相似度的計算基于圖編輯距離，采用圖匹配算法領(lǐng)域中常用方法——二分圖編輯距離，將圖編輯距離問題轉(zhuǎn)化為二分圖匹配問題［17］。對源圖G1（V1，E1）和目標(biāo)圖G2（V2，E2）構(gòu)造完全二分圖G，圖G中邊的權(quán)值為圖中節(jié)點的相似度，節(jié)點相似度越大，權(quán)值越大。因此，圖G1、G2的相似度問題轉(zhuǎn)變?yōu)閹?quán)二分圖最優(yōu)匹配問題，采用Kuhn-Munkers 算法即可求出最大權(quán)匹配。Kuhn-Munkers 算法是一種二分圖最佳匹配算法，文獻［18-19］使用Kuhn-Munkers算法分析惡意代碼函數(shù)調(diào)用圖的相似度。

3.3.1 函數(shù)調(diào)用圖相似度計算

函數(shù)調(diào)用圖g1和g2所構(gòu)成的二分圖G的邊權(quán)值通過對應(yīng)函數(shù)的相似度和函數(shù)調(diào)用關(guān)系相似度聯(lián)合計算得到。下文中v1和v2分別表示圖g1和g2中的函數(shù)。

1）函數(shù)相似度計算。

函數(shù)v1和函數(shù)v2的相似度通過計算函數(shù)內(nèi)基本塊序列bbs的相似度得到。代碼塊序列的相似度度量方法有多種，如最長公共子序列、后綴數(shù)組［20］、哈希比較法［21］、機器學(xué)習(xí)［22］等。在v1和v2的相似度度量中，bbs長度一致時，更能說明二者的相似性，即函數(shù)v1和v2對應(yīng)的基本塊序列bbs1和bbs2長度是否相同，對應(yīng)的權(quán)重是不同的。而最長公共子序列，后綴數(shù)組的方法，只能說明bbs1是否包含bbs2，精確度較低。哈希比較法又過于敏感，容易造成誤判。機器學(xué)習(xí)的方法需要大量的模板集，難以一般化。

本文采用萊溫斯坦距離（Levenshtein Distance，ld），萊溫斯坦距離是一種度量方法，通常用來比較基于字符序列的兩個字符串［23］。字符序列定義了字符串的結(jié)構(gòu)［23］，基本塊序列類似于字符串序列，可以使用該方法計算其相似度。由定義3基本塊有6種類型，用1～6表示，則圖4中函數(shù)基本塊序列可表示為bbs=3，4，1，2，1，6。函數(shù)v1和v2的相似度計算公式如下：

其中：bbs1、bbs2為函數(shù)v1、v2對應(yīng)的基本塊序列；ld（bbs1，bbs2）為基本塊序列bbs1和bbs2的萊溫斯坦距離；|bbs1|、|bbs2|為兩個序列的基本塊個數(shù)。當(dāng)基本塊序列得相似性達到一定的閾值，就認(rèn)為兩個函數(shù)是相似的。大量實驗結(jié)果表明，基本塊序列的相似度達到80%，則可判定兩個函數(shù)是相似的。

2）函數(shù)調(diào)用關(guān)系相似度計算。

函數(shù)調(diào)用關(guān)系相似度計算公式如下：

其中：n1為函數(shù)v1和v2的主調(diào)函數(shù)的相似對個數(shù)；n2為函數(shù)v1和v2的被調(diào)函數(shù)的相似對個數(shù)；N為函數(shù)v1、v2的主調(diào)函數(shù)和被調(diào)函數(shù)組成的所有函數(shù)對個數(shù)。

3）二分圖邊權(quán)值計算。

二分圖邊權(quán)值計算公式如下：

函數(shù)調(diào)用圖g1和g2對應(yīng)的二分圖構(gòu)造完成后，采用KM（Kuhn-Munkers）算法求其最大權(quán)匹配M，匹配M的邊權(quán)值占比為函數(shù)調(diào)用圖g1和g2的相似度，權(quán)值越大，相似度越大。圖相似度計算公式如下：

其中：w（M）為最大權(quán)匹配M的權(quán)值；N為圖g1和g2中函數(shù)構(gòu)成的函數(shù)對個數(shù)。

3.3.2 控制流圖相似度計算

控制流cg1和cg2構(gòu)成二分圖Gcg，二分圖Gcg的頂點為控制流圖cg1和cg2中的獨立路徑，圖Gcg的邊權(quán)值為圖cg1、cg2中各獨立路徑之間的相似度。

1）獨立路徑的相似度計算。

控制流圖中的獨立路徑為基本塊序列，相似度計算同樣采用萊溫斯坦距離。計算公式如下：

其中：pbbs1、pbbs2為獨立路徑p1與p2對應(yīng)的基本塊序列；ld（pbbs1，pbbs2）為基本塊序列pbbs1與pbbs2的萊溫斯坦距離；|pbbs1|、|pbbs2|為兩個序列的基本塊個數(shù)。

2）控制流圖相似度計算。

采用KM 算法獲取二分圖Gcg的最大權(quán)匹配M，并根據(jù)匹配M計算控制流圖的相似度。計算公式如下：

其中：w（M）為最大權(quán)匹配M的權(quán)值；PN為圖cg1和cg2中獨立路徑的對數(shù)。

4 實驗與分析

實驗采用數(shù)據(jù)結(jié)構(gòu)中常規(guī)排序算法和查找算法，源代碼下載自GitHub（https：//github.com/TheAlgorithms/C）。偽代碼則根據(jù)各排序算法和查找算法的算法思路以及偽代碼語法規(guī)則人工編寫完成。由于函數(shù)間調(diào)用關(guān)系是否一致會導(dǎo)致實驗結(jié)果的不同，因此實驗一驗證不同函數(shù)調(diào)用關(guān)系情況下的一致性檢測結(jié)果。由于本文一致性檢測方法依賴于設(shè)計文檔偽代碼，因此實驗二驗證在設(shè)計文檔偽代碼功能描述不完善情況下的一致性檢測結(jié)果。使用本文方法，分析功能完全的設(shè)計文檔偽代碼獲取函數(shù)特征并建立設(shè)計特征模型。如圖7所示。

圖7 設(shè)計特征模型Fig.7 Design feature model

4.1 實驗一

軟件設(shè)計與軟件實現(xiàn)之間可能存在以下幾種情況：

1）實現(xiàn)系統(tǒng)完全按照設(shè)計要求實現(xiàn)了所有函數(shù)，實現(xiàn)系統(tǒng)函數(shù)調(diào)用關(guān)系滿足設(shè)計要求，需要進行函數(shù)調(diào)用關(guān)系圖和控制路圖的對比，如實驗Code1。

2）實現(xiàn)系統(tǒng)按照設(shè)計要求實現(xiàn)了所有函數(shù)，但存在部分函數(shù)調(diào)用關(guān)系與設(shè)計要求不一致，如實驗Code2中函數(shù)Search和Sort未調(diào)用任何函數(shù)。

3）實現(xiàn)系統(tǒng)實現(xiàn)系統(tǒng)未實現(xiàn)所有函數(shù)，但其函數(shù)調(diào)用關(guān)系與設(shè)計要求部分一致，如實驗Code3只實現(xiàn)了排序功能。

分析被測代碼，獲取實際函數(shù)特征模型，與設(shè)計特征模型進行對比。表2 顯示了實現(xiàn)與設(shè)計系統(tǒng)中各函數(shù)匹配結(jié)果以及函數(shù)調(diào)用關(guān)系相似度simFC。simFC＞0.8表示匹配成功，且函數(shù)基本塊序列和函數(shù)調(diào)用關(guān)系非常相似；0＜simFC＜0.8 表示匹配到函數(shù)但函數(shù)基本塊序列或者函數(shù)間調(diào)用關(guān)系一致度較低；simFC=0表示未匹配到對應(yīng)函數(shù)。Code1為與設(shè)計特征模型中函數(shù)調(diào)用關(guān)系一致的代碼；Code2 為與設(shè)計特征模型中函數(shù)調(diào)用關(guān)系部分一致的代碼，其中函數(shù)Sort 和Search 未調(diào)用任何函數(shù)；Code3為只實現(xiàn)了查找功能的代碼。

表2 函數(shù)調(diào)用關(guān)系圖匹配結(jié)果Tab.2 Function call relationship matching results

表2所示Code1實驗結(jié)果中，各函數(shù)調(diào)用關(guān)系相似度均大于0.8，表明Code1的函數(shù)調(diào)用關(guān)系與設(shè)計要求一致?？梢缘贸觯谠O(shè)計和實現(xiàn)的函數(shù)調(diào)用關(guān)系一致的情況下，檢測結(jié)果與預(yù)期結(jié)果較為一致，說明在設(shè)計特征模型和實際特征模型一致時，本文方法能夠正確匹配對應(yīng)函數(shù)。

Code2 實驗結(jié)果中，每個函數(shù)都得到匹配結(jié)果，而函數(shù)Sort 和Search 的函數(shù)調(diào)用關(guān)系相似度均低于0.8，表明Code2雖然實現(xiàn)了所有函數(shù)，但函數(shù)Sort 和Search 的函數(shù)調(diào)用關(guān)系與設(shè)計要求不一致。說明在設(shè)計和實現(xiàn)的函數(shù)調(diào)用關(guān)系部分不一致的情況下，本文方法可以檢測到函數(shù)調(diào)用關(guān)系不一致的部分。另外，其他函數(shù)的函數(shù)調(diào)用關(guān)系相似度也低于0.8，如所有查找函數(shù)和部分排序函數(shù)，說明檢測結(jié)果雖然與預(yù)期方向一致，但部分結(jié)果粗糙。這是由于Code2中Sort和Search函數(shù)未調(diào)用任何函數(shù)，使相關(guān)的排序算法和查找算法的被調(diào)用關(guān)系受到影響。導(dǎo)致即使實現(xiàn)了設(shè)計要求的函數(shù)，比如函數(shù)InterpolatSearch、LinearSearch、BinarySearch 等，卻由于被調(diào)用關(guān)系的不一致，仍被視為匹配度較低，而函數(shù)maxHeapify、partition、Swap 未受到影響，檢測結(jié)果仍然大于0.8。但是實驗檢測結(jié)果仍能說明實現(xiàn)代碼Code2 的函數(shù)調(diào)用關(guān)系與設(shè)計要求不一致。

Code3 實驗結(jié)果中，排序相關(guān)函數(shù)的匹配結(jié)果均為0，表明Code3 沒有實現(xiàn)排序功能。查找相關(guān)的函數(shù)匹配結(jié)果均大于0.8，表明Code3 完成了查找功能。實驗結(jié)果與預(yù)期一致，說明在實現(xiàn)代碼只完成部分功能時，仍可以正確匹配實現(xiàn)代碼中功能完成部分的函數(shù)，如Code3 中實現(xiàn)查找功能的函數(shù)。對于未完成部分函數(shù)并不能匹配到對應(yīng)函數(shù)，如排序功能相關(guān)的函數(shù)。同時，檢測結(jié)果能夠說明實現(xiàn)代碼的函數(shù)調(diào)用關(guān)系與設(shè)計要求不一致。

由于Code2和Code3的函數(shù)調(diào)用關(guān)系與設(shè)計要求不一致，不進行函數(shù)內(nèi)部控制流的驗證。Code1 函數(shù)調(diào)用關(guān)系與設(shè)計要求一致，則根據(jù)函數(shù)對應(yīng)關(guān)系，對函數(shù)內(nèi)部控制流進行對比。表3 列出了設(shè)計函數(shù)與實現(xiàn)函數(shù)控制流圖的相似度以及控制流圖中基本塊不一致檢測結(jié)果，基本塊的標(biāo)號為實際函數(shù)中基本塊標(biāo)號。實驗結(jié)果中除函數(shù)bubbleSort外，控制流圖相似度均大于0.8，說明這些函數(shù)實現(xiàn)邏輯與設(shè)計要求一致。實驗14 個函數(shù)中，僅有函數(shù)bubbleSort 與預(yù)期不符，控制流圖匹配準(zhǔn)確度達到92.8%，總體實驗結(jié)果與預(yù)期較為一致。另外，Code1 中函數(shù)bubbleSort 的實現(xiàn)邏輯雖與設(shè)計要求一致，但由于控制流圖中3 個不同類型基本塊在所有獨立路徑中，導(dǎo)致控制流圖相似度較低，但可通過基本塊檢測結(jié)果進行精確驗證。因此實際檢測中應(yīng)以控制流圖相似度作為參考，并根據(jù)基本塊檢測結(jié)果進行精確驗證。

表3 對應(yīng)函數(shù)控制流一致性檢測結(jié)果Tab.3 Consistency detection results of corresponding function control flow

4.2 實驗二

設(shè)計文檔偽代碼中函數(shù)Searh不調(diào)用任何函數(shù)，建立設(shè)計特征模型，與Code1 進行一致性檢測，Code1 為按設(shè)計要求完成的代碼。實驗結(jié)果如圖8 所示，說明在設(shè)計文檔偽代碼不準(zhǔn)確時會導(dǎo)致誤判，如函數(shù)InterpolatSearch、LinearSearch、BinarySearch、FibMoncianSearch。由于是以設(shè)計文檔偽代碼為根據(jù)，建立設(shè)計特征模型，并以此作為檢測依據(jù)，因此在設(shè)計文檔偽代碼部分不準(zhǔn)確時，會造成不準(zhǔn)確部分函數(shù)調(diào)用關(guān)系的誤判，但并不影響其余準(zhǔn)確部分功能的檢測。另外，后續(xù)的函數(shù)內(nèi)部結(jié)構(gòu)的檢測可以對該問題進行彌補，所以在實際軟件系統(tǒng)一致性檢測中，應(yīng)保證設(shè)計文檔偽代碼的質(zhì)量，設(shè)計文檔偽代碼質(zhì)量越高，一致性檢測越準(zhǔn)確。

圖8 設(shè)計系統(tǒng)與實際系統(tǒng)函數(shù)相似度Fig.8 Functional similarity between design system and actual system

5 結(jié)語

軟件實現(xiàn)與設(shè)計一致性驗證是軟件測試的重要部分之一。本文提出了一種面向設(shè)計文檔偽代碼的設(shè)計與實現(xiàn)一致性檢測方法，為基于文檔的測試提供一種新的研究思路。從設(shè)計文檔偽代碼和程序源代碼自動提取函數(shù)特征，建立特征模型，并利用二分圖最大權(quán)匹配算法驗證特征模型相似度，獲取函數(shù)對應(yīng)關(guān)系，完成函數(shù)內(nèi)部結(jié)構(gòu)的對比，進而完成軟件設(shè)計與實現(xiàn)的一致性檢測。該方法不需要大量的模板集，即可獲取一致性檢測結(jié)果，提升了一致性驗證的工作效率，并具有更優(yōu)越的一般性。

但是該方法還存在以下不足：1）在對函數(shù)內(nèi)部結(jié)構(gòu)驗證過程中，并沒有對條件轉(zhuǎn)移語句的條件進行驗證；2）對基本塊驗證的過程中，沒有考慮其對數(shù)據(jù)的依賴關(guān)系。后續(xù)工作可以充分研究基本塊內(nèi)部結(jié)構(gòu)的驗證，提高驗證的準(zhǔn)確度。