基于控制流的軟件設(shè)計(jì)與實(shí)現(xiàn)一致性分析方法

張家奇，牟永敏，張志華

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

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

0 引言

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

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

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

1 本文方法

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

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

圖1 一致性檢測(cè)框架Fig.1 Framework of consistency detection

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

在軟件實(shí)現(xiàn)和設(shè)計(jì)一致性檢測(cè)中，偽代碼和源代碼的表征方式?jīng)Q定了軟件設(shè)計(jì)信息和實(shí)現(xiàn)信息的利用程度。在代碼克隆領(lǐng)域，代碼的表征方式分為文本［7］、詞匯［8］、語法［9］和語義［10-11］四個(gè)層次［12］。由于偽代碼變量不需要聲明、缺乏語法規(guī)范的特點(diǎn)，文本、詞匯的表征方式不能充分利用偽代碼的信息。語法的表征方式，例如基于語法分析樹的方式，會(huì)造成一致性驗(yàn)證算法復(fù)雜度的提升。語義的表征方式，利用代碼語義信息進(jìn)行驗(yàn)證，其中，語義信息是指能夠反映一段代碼功能的信息，比如代碼的控制流和數(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］，每個(gè)函數(shù)內(nèi)部的控制流信息反映了函數(shù)的內(nèi)部結(jié)構(gòu)，因此選其作為函數(shù)特征并建立特征模型。函數(shù)特征提取具體過程如下：

2.1 中間表示的生成

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

2.1.1 偽代碼中間表示的生成

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

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

由于人們?cè)诿枋鏊惴〞r(shí)使用的偽碼并不相同［6］128，難以一般化，本文使用一種較為通用語法規(guī)則來規(guī)范偽代碼。語法規(guī)則用擴(kuò)展巴科斯范式表示，語法規(guī)則產(chǎn)生式如下：

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

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

2）生成語法分析樹。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

a）中間代碼的第一個(gè)語句；

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

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

每個(gè)入口語句對(duì)應(yīng)的基本塊包括了從它自己開始，直到下一個(gè)入口語句或結(jié)尾語句之間的所有語句。如圖4 所示，對(duì)圖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)試選項(xiàng)-fdump-tree-cfg 并輸入源代碼，即可得到GCC編譯器生成的cfg中間文件。文獻(xiàn)［1］中使用該方法提取源代碼函數(shù)結(jié)構(gòu)特征。cfg 文件中的中間代碼是GCC 編譯器對(duì)源代碼進(jìn)行詞法和語法分析后得到的中間表示，其中包含劃分基本塊后的結(jié)果以及基本塊的執(zhí)行順序。如圖5（a）中源代碼以及通過GCC 編譯器生成圖5（b）中cfg中間碼。

2.2 函數(shù)特征提取

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

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

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

定義3基本塊序列（Basic Block Sequence，BBS）為一個(gè)有序序列bbs=b1，b2，…，bi，bj∈｛seq，con_jump，uncon_jump，seq_cj，seq_nj，return｝。其中：bj表示第j個(gè)基本塊；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)用信息的提取，遍歷整個(gè)語法分析樹，即可獲取全部函數(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 語句，判定基本塊，獲取基本塊序列。同時(shí)匹配轉(zhuǎn)移語句中的“goto bbi”，獲取基本塊流向，得到控制流圖。如圖5（c）中控制流圖，圖中節(jié)點(diǎn)為基本塊，其對(duì)應(yīng)的基本塊序列bbs=uncon_jump，seq，con_jump，seq，return。

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

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

3 特征模型的建立對(duì)比

3.1 特征模型的建立

設(shè)計(jì)文檔中的偽代碼描述了每一模塊的實(shí)現(xiàn)方式，包括實(shí)現(xiàn)算法、邏輯流程等，通過分析設(shè)計(jì)文檔中偽代碼，獲取設(shè)計(jì)函數(shù)間調(diào)用關(guān)系以及設(shè)計(jì)函數(shù)控制流，建立設(shè)計(jì)特征模型。通過靜態(tài)分析源代碼獲取實(shí)現(xiàn)函數(shù)調(diào)用關(guān)系以及每個(gè)函數(shù)的控制流，建立軟件實(shí)現(xiàn)特征模型。由于圖能有效表示對(duì)象的屬性以及對(duì)象之間的關(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)系圖為載體，將圖中每個(gè)節(jié)點(diǎn)映射到對(duì)應(yīng)函數(shù)的基本塊序列和控制流圖，從而建立設(shè)計(jì)特征模型和軟件實(shí)現(xiàn)特征模型。

3.2 特征模型對(duì)比

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

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

3.3 相似度的計(jì)算

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3.2 控制流圖相似度計(jì)算

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

1）獨(dú)立路徑的相似度計(jì)算。

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

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

2）控制流圖相似度計(jì)算。

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

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

4 實(shí)驗(yàn)與分析

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

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

4.1 實(shí)驗(yàn)一

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

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

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

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

分析被測(cè)代碼，獲取實(shí)際函數(shù)特征模型，與設(shè)計(jì)特征模型進(jìn)行對(duì)比。表2 顯示了實(shí)現(xiàn)與設(shè)計(jì)系統(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表示未匹配到對(duì)應(yīng)函數(shù)。Code1為與設(shè)計(jì)特征模型中函數(shù)調(diào)用關(guān)系一致的代碼；Code2 為與設(shè)計(jì)特征模型中函數(shù)調(diào)用關(guān)系部分一致的代碼，其中函數(shù)Sort 和Search 未調(diào)用任何函數(shù)；Code3為只實(shí)現(xiàn)了查找功能的代碼。

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

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

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

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

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

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

4.2 實(shí)驗(yàn)二

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

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

5 結(jié)語

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

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