關(guān)鍵詞：程序不變量;軟件可靠性;冗余不變量

0 引言（Introduction）

軟件可靠性是描述系統(tǒng)質(zhì)量的重要度量指標(biāo)，一般與軟件缺陷和故障直接相關(guān)[1-2]。傳統(tǒng)方法往往只關(guān)注實(shí)際輸出與期望輸出的差異，忽略了程序內(nèi)部的運(yùn)行狀況。僅僅根據(jù)輸入輸出信息計(jì)算軟件可靠性的方法存在以下問題：①測試用例不能覆蓋所有的輸入情況，如果測試用例的質(zhì)量不高，軟件可靠性計(jì)算的準(zhǔn)確性則無法得到保證;②存在偶然性正確的情況[3-4]。測試用例執(zhí)行了錯(cuò)誤的代碼行，結(jié)果卻與標(biāo)準(zhǔn)程序輸出一致，此類測試用例將導(dǎo)致軟件的可靠性計(jì)算出現(xiàn)偏差。

為了解決以上問題，需要獲取程序內(nèi)部數(shù)據(jù)用于計(jì)算可靠性，如程序內(nèi)部結(jié)構(gòu)、動態(tài)行為等。不變量是程序運(yùn)行當(dāng)中保持不變的性質(zhì)，能夠反映內(nèi)部的動態(tài)行為，受外部輸入測試用例的影響較小。因此，本文提出一種基于不變量的可靠性計(jì)算方法，將不變量作為失效數(shù)據(jù)輸入可靠性模型計(jì)算，同時(shí)利用函數(shù)調(diào)用關(guān)系圖消除冗余，提升失效數(shù)據(jù)的獨(dú)立性。實(shí)驗(yàn)結(jié)果表明，對于單一故障程序，不變量約簡后較約簡前可靠性平均提升50.502%，方差較小，更能準(zhǔn)確反映軟件的可靠性。

1 方法概述（Overview of the method）

程序不變量以前置條件與后置條件、循環(huán)不變量、斷言等形式表現(xiàn)，在程序驗(yàn)證、文檔完善、程序維護(hù)、缺陷定位和修復(fù)等方面得到廣泛應(yīng)用[5]。通過程序執(zhí)行動態(tài)發(fā)現(xiàn)的不變量是必然適用于有限輸入的謂詞，但并非對全部輸入都成立，因此被稱為似然不變量，一般直接稱為不變量。從一組成功執(zhí)行輸入中提取的不變量，如果某個(gè)失敗的測試用例違反了這個(gè)結(jié)果，通常是出現(xiàn)錯(cuò)誤的跡象。在這種思路下，將失效不變量作為失效數(shù)據(jù)輸入軟件可靠性模型，首先編譯程序并執(zhí)行測試套件，分別獲取成功測試用例和失敗測試用例的執(zhí)行軌跡，使用Daikon工具讀取數(shù)據(jù)跟蹤和推導(dǎo)程序不變量，利用InvariantDiff檢查異常不變量，并依據(jù)函數(shù)調(diào)用關(guān)系進(jìn)行不變量約簡，得到最終失效數(shù)據(jù)并輸入Nelson模型計(jì)算軟件的可靠性。方法的工作流程如圖1所示。

2 程序不變量（Software invariants）

程序不變量是在一個(gè)或多個(gè)特定程序點(diǎn)上為真的屬性，它們能夠解釋數(shù)據(jù)結(jié)構(gòu)和算法，幫助軟件開發(fā)人員在比代碼更高的抽象級別上記錄設(shè)計(jì)決策[6]。Daikon實(shí)現(xiàn)了對不變量進(jìn)行動態(tài)檢測，它通過程序插樁監(jiān)視程序特定位置（一般是方法入口處和出口處）的變量值，并將變量值與一組模板進(jìn)行匹配，以創(chuàng)建候選不變量，最終輸出過程前置和后置條件，以及在每個(gè)公共方法入口和出口處保持的對象不變量與置信程度[7-8]。Daikon可以理解為搜索一大組表示不變量的表達(dá)式，并刪除與執(zhí)行軌跡相矛盾的、與其他不變量冗余的或頻率與偶然性相差不大的表達(dá)式[9]。輸出結(jié)果可以用作文檔，也可以作為斷言添加到源程序中，或者用作其他工具的輸入[10-12]。Daikon工具實(shí)現(xiàn)動態(tài)不變量檢測流程如圖2所示。

2.1 獲得程序不變量

如果已知錯(cuò)誤程序的正確版本，可以通過以下5個(gè)步驟獲取失效不變量。

（1）生成測試用例集，在啟用gdwarf-2標(biāo)志的情況下編譯程序，以生成DWARF-2格式的調(diào)試信息和程序，并執(zhí)行測試用例。

（2）獲得程序執(zhí)行軌跡文件。C語言程序使用Kvasir作為前端工具，這會生成與每個(gè)測試用例的執(zhí)行相對應(yīng)的.dtrace和.decls文件。

（3）定義Daikon不變量類型和配置控制參數(shù)。不變量的形式有常數(shù)（x=a），范圍（a

（4）從軌跡文件中推導(dǎo)不變量。Daikon枚舉了所有簡單的候選不變量，并只保留了出現(xiàn)在所有軌跡文件上的不變量。

（5）消除冗余不變量。Daikon工具報(bào)告了3種情況下的冗余不變量。①若兩個(gè)或多個(gè)不變量總是相等，則所有相等的不變量都具有任一不變量所表示的性質(zhì)。例如，如果x=y，那么對于任何不變量f，f（x）意味著f（y）。②如果變量等于常數(shù)值，它將滿足其他一些不變性質(zhì)。例如，若x=5，則意味著x 是奇數(shù)，x≥5等。③對于兩個(gè)程序點(diǎn)A 和點(diǎn)B，如果點(diǎn)B 的所有樣本也出現(xiàn)在點(diǎn)A 處，那么在點(diǎn)B 處的任何不變量在點(diǎn)A 處都必然為真，在點(diǎn)B 中檢測到的不變量是冗余的[14]。這種關(guān)系形式轉(zhuǎn)化為偏序?D，其中較小的元素接收由較高元素接收的樣本的子集，而較高的元素包含在較低元素處為真的不變量的子集。

2.2 異常不變量

對比不變量生成結(jié)果發(fā)現(xiàn)，正確程序和錯(cuò)誤程序生成的不變量存在較大差異。這些異常不變量以（type，relationship）的形式出現(xiàn)，例如不變量（Una，DJJ）中出現(xiàn)DJJ關(guān)系，即兩個(gè)不變量不同（Different）、均得到確認(rèn)（Justified），暗示著程序出現(xiàn)了影響可靠性的異常。如果將正確程序生成的不變量集合表示為集合A，錯(cuò)誤程序生成的不變量集合表示為集合B，異常不變量在絕大多數(shù)情況下出現(xiàn)在差集B＼A 中。

2.3 依據(jù)調(diào)用關(guān)系約簡

上文提及，Daikon消除了3種情形下的冗余不變量，但不變量之間的關(guān)聯(lián)性仍未得到完全消除。許多函數(shù)的異常不變量是由其調(diào)用的函數(shù)引起的，即其他函數(shù)的錯(cuò)誤狀態(tài)傳遞到了該函數(shù)，這些不變量會導(dǎo)致統(tǒng)計(jì)的失效數(shù)據(jù)偏多，進(jìn)而影響可靠性計(jì)算的準(zhǔn)確性，因此需要進(jìn)一步區(qū)分。

定義1：如果異常不變量是由其程序錯(cuò)誤直接導(dǎo)致的，那么這類異常不變量稱為根因不變量;由于所在函數(shù)和錯(cuò)誤函數(shù)之間存在依賴關(guān)系，即因錯(cuò)誤傳播引起的異常不變量，這類異常不變量稱為非根因不變量。

根據(jù)上述定義，約簡異常不變量需要獲得函數(shù)間的依賴關(guān)系，研究人員使用Doxygen[15]和Graphiz解析源文件生成函數(shù)調(diào)用關(guān)系圖，可以剔除一些與失效無關(guān)的函數(shù)，盡量只保留根因不變量。

假定存在函數(shù)fi、fj，fi 是fj 的父函數(shù)，Enfi表示函數(shù)fi∷Enter 處，即函數(shù)入口處的異常不變量集合，Exfi 表示函數(shù)fi∷Exit處，即函數(shù)出口處的異常不變量集合。按照以下公式，對不變量進(jìn)行約簡：

公式（1）與公式（2）基于的約簡規(guī)則主要有以下4條。

（1）移除主函數(shù)因命令行參數(shù)差異導(dǎo)致的差異不變量。

（2）移除在函數(shù)入口處和出口處保持一致的不變量。

形如lt;1，yΔxgt;或lt;yΔx，1gt;（Δ∈{==，！ =，gt;=，lt;=，lt;，gt;}）的失效不變量出現(xiàn)在函數(shù)入口處，同時(shí)出口處出現(xiàn)對應(yīng)的lt;1，yΔorig（x）gt;或lt;yΔorig（x），1gt;。

形如或的差異不變量出現(xiàn)在函數(shù)入口處，同時(shí)出口處出現(xiàn)對應(yīng)的或。

orig（x）是指進(jìn)入函數(shù)時(shí)變量的值（因函數(shù)主體可能會修改的值），如果函數(shù)出口處仍保持進(jìn)入函數(shù)時(shí)的變量的值，說明函數(shù)未對變量進(jìn)行修改。這些失效不變量是由之前調(diào)用的函數(shù)引起的，只作傳遞使用，因此予以移除。

（3）移除父函數(shù)和子函數(shù)出口處一致的不變量。

在父函數(shù)出口處和子函數(shù)出口處保持一致的不變量，只保留子函數(shù)出口處的不變量。父函數(shù)出口處的差異不變量是由子函數(shù)的差異不變量引起的，只需保留子函數(shù)出口處的差異不變量。例如，getccl∷Exit 及dodash ∷Exit 均出現(xiàn)= 3{0-}，i[] elementsgt;=1{1+}gt;（Una，DUJ），并且函數(shù)getccl調(diào)用函數(shù)dodash。因此，推斷函數(shù)getccl處的差異不變量是因調(diào)用dodash引起的，予以移除。

（4）移除可合并的異常不變量。

在函數(shù)入口處或出口處，形如和的異常不變量可合并，實(shí)際不存在異常不變量;在函數(shù)入口處或出口處，出現(xiàn)兩組幾乎一致只有置信度不同的異常不變量，可移除這兩組異常不變量。

不變量約簡程序?qū)崿F(xiàn)中，將函數(shù)調(diào)用圖G 作為輸入，圖節(jié)點(diǎn)數(shù)據(jù)包含每個(gè)程序點(diǎn)入口處和出口處的失效不變量集合，遍歷該有向圖所有節(jié)點(diǎn)，依據(jù)約簡規(guī)則從數(shù)據(jù)集合中刪除非根因不變量，約簡過程偽代碼見算法1。

3 可靠性計(jì)算模型（Reliability calculation model）

3.1 可靠性模型

本文使用Nelson模型評估軟件的可靠性，Nelson認(rèn)為，計(jì)算機(jī)程序可看成一個(gè)可計(jì)算函數(shù)F 的說明[16]。

程序的輸入數(shù)據(jù)域E= Ei|i=1，2，3，…，N ，其中Ei是程序單次運(yùn)行時(shí)輸入數(shù)據(jù)，E 是全部輸入數(shù)據(jù)的集合，N 為集合E 中的數(shù)據(jù)總數(shù)。

每一次函數(shù)運(yùn)行Ei，產(chǎn)生對應(yīng)的結(jié)果F'（Ei），表示函數(shù)此次運(yùn)行的實(shí)際輸出結(jié)果，而函數(shù)的真值為F（Ei）。Δj 表示函數(shù)實(shí)際輸出值F'（Ei）與真值F（Ei）容許的最大誤差，當(dāng)差值超過這個(gè)范圍，即F（Ei）-F'（Ei） gt;Δj，則認(rèn)為程序發(fā)生了一次失效。

當(dāng)程序運(yùn)行時(shí)選用的數(shù)據(jù)不服從均勻分布，可用Pi 表示Ei 被選用的概率，當(dāng)Ei∈El 時(shí)，yi=1;當(dāng)Ei∈Er 時(shí)，yi=0。程序按選用數(shù)據(jù)概率分布運(yùn)行一次的失效概率定義為

其中：n 表示輸入數(shù)據(jù)域數(shù)據(jù)總數(shù)，P（Ei）表示此次輸入域Ei數(shù)據(jù)中被選中的概率，Ki 表示Ei 域中被選中的數(shù)據(jù)個(gè)數(shù)，fi 表示Ki 中導(dǎo)致程序失效的數(shù)據(jù)個(gè)數(shù)。

3.2 可靠性計(jì)算方法

在獲取程序不變量的示例中，研究人員介紹了如何在已知正確程序的情況下獲得錯(cuò)誤程序的失效不變量。在軟件的實(shí)際運(yùn)行過程中，不存在“正確程序”，無法獲得“正確程序”的不變量。本文將成功測試用例執(zhí)行中推導(dǎo)得到的不變量作為“正確程序”的不變量，將失敗測試用例執(zhí)行中推導(dǎo)得到的不變量作為“錯(cuò)誤程序”的不變量，并利用這兩組不變量進(jìn)行軟件可靠性的計(jì)算。

以西門子程序包中replace程序V1為例，闡述如何計(jì)算程序的可靠性，具體步驟如下。

（1）根據(jù)“2 程序不變量”節(jié)的描述，分別獲取成功執(zhí)行和失敗執(zhí)行測試用例，運(yùn)行程序并收集軌跡數(shù)據(jù)，推導(dǎo)程序不變量。

（2）replace程序生成函數(shù)調(diào)用關(guān)系圖（圖3）。

（3）異常不變量約簡，依據(jù)“2.3 依據(jù)調(diào)用關(guān)系約簡”小節(jié)中描述的約簡規(guī)則，盡可能地移除非根因不變量，得到最終失效不變量。replace V1程序點(diǎn)共有42處，異常不變量所在程序點(diǎn)共有10處，失效不變量所在程序點(diǎn)有3處。

（4）統(tǒng)計(jì)程序點(diǎn)、失效不變量、每個(gè)程序點(diǎn)失效不變量出現(xiàn)的概率，計(jì)算得到replace程序V1可靠性為96.96%。

4 實(shí)驗(yàn)與分析（Experiment and analysis）

4.1 程序來源

本文選取的實(shí)驗(yàn)程序?yàn)槲鏖T子程序包，來源于SIR（Software-artifact Infrastructure Repository），包括print_tokens、print_tokens2、replace、schedule、schedule2、tcas、tot_info七個(gè)程序[17]。每個(gè)程序包含一個(gè)正確版本和若干個(gè)錯(cuò)誤版本，某個(gè)程序?qū)?yīng)的每個(gè)錯(cuò)誤版本只包含一個(gè)人工植入的錯(cuò)誤，西門子程序包見表1。

4.2 傳統(tǒng)方法計(jì)算軟件可靠性

對西門子程序包中的7個(gè)程序進(jìn)行實(shí)驗(yàn)發(fā)現(xiàn)，132個(gè)錯(cuò)誤版本中的一部分版本無法使用：①執(zhí)行時(shí)發(fā)生了段錯(cuò)誤，不能收集到完整的覆蓋信息;②沒有失敗的測試用例;③錯(cuò)誤發(fā)生在頭文件變量聲明中。排除這些錯(cuò)誤版本，余下每個(gè)程序選擇4個(gè)錯(cuò)誤版本執(zhí)行所有測試用例，通過對比實(shí)際輸出值與期望值獲取程序失效數(shù)據(jù)，傳統(tǒng)方法計(jì)算的可靠性結(jié)果見表2。

4.3 不變量計(jì)算軟件可靠性

程序不變量是在程序運(yùn)行過程中始終保持真的屬性，使用傳統(tǒng)方法獲得的軟件可靠性在很大程度上依賴于測試用例的質(zhì)量，測試用例無法覆蓋錯(cuò)誤代碼或是存在多個(gè)偶然性正確的測試用例，都會導(dǎo)致計(jì)算結(jié)果產(chǎn)生誤差，而基于不變量的方法依賴的失效數(shù)據(jù)刻畫了程序的動態(tài)行為，對程序內(nèi)部發(fā)生的過程有更深入的理解。研究人員獲取失敗測試用例產(chǎn)生的不變量違反正確測試用例產(chǎn)生的不變量程序點(diǎn)數(shù)量和總不變量程序點(diǎn)數(shù)量，使用Nelson模型可計(jì)算得到軟件可靠性。西門子程序包中的7個(gè)程序不變量約簡前使用Nelson模型計(jì)算的可靠性結(jié)果見表3。

這些不變量中也存在一些無用的非根因不變量，會影響計(jì)算結(jié)果的準(zhǔn)確性。因此，結(jié)合函數(shù)調(diào)用關(guān)系圖約簡可能產(chǎn)生偏差的不變量，能夠進(jìn)一步提升Nelson模型可靠性計(jì)算的準(zhǔn)確性，依據(jù)約簡規(guī)則篩除部分不變量后，表4為西門子程序包中的7個(gè)程序不變量約簡后使用Nelson模型計(jì)算的可靠性結(jié)果。

圖4展示了西門子程序包中的7個(gè)程序各4個(gè)示例的軟件可靠性結(jié)果。這些示例分別通過3種不同的方法計(jì)算軟件可靠性：傳統(tǒng)的計(jì)算方法、在Nelson模型中應(yīng)用約簡前不變量的方法，以及在Nelson模型中應(yīng)用約簡后不變量的方法。從中可以發(fā)現(xiàn)，基于不變量的可靠性計(jì)算方法經(jīng)過不變量約簡，可靠性大幅提升，并且通過本文方法得到的同一程序的4個(gè)示例可靠性結(jié)果方差較小。這是由于約簡之前的差異不變量之間存在較大的相關(guān)性，例如一些不變量之間具有等價(jià)關(guān)系或者不變量之間的關(guān)系具有傳遞性，導(dǎo)致最后獲取的失效數(shù)據(jù)較實(shí)際情況偏多。不變量約簡后可靠性結(jié)果和傳統(tǒng)方法比較，數(shù)值上還存在一定差距，分析其原因，一是選擇的程序測試用例數(shù)量較大，其中影響可靠性結(jié)果的測試用例占比較小，二是約簡后失效數(shù)據(jù)還存在一定相關(guān)性。

5 結(jié)論（Conclusion

本文以程序不變量收集失效數(shù)據(jù)，并通過函數(shù)調(diào)用關(guān)系圖約簡非根因不變量，從而更準(zhǔn)確地評估軟件的可靠性。軟件的可靠性是由其內(nèi)部信息決定的，從不變量角度刻畫可靠性能反映整體行為。實(shí)驗(yàn)結(jié)果表明，基于不變量的可靠性計(jì)算方法約簡后計(jì)算得到的可靠性結(jié)果，較約簡前平均提升50.502%，其中print_tokens2最小方差可達(dá)到0。該方法應(yīng)用于單故障程序得到的可靠性數(shù)據(jù)較穩(wěn)定，更接近實(shí)際可靠性，但與傳統(tǒng)方法計(jì)算結(jié)果相比，數(shù)值上仍存在一定差距，因此在未來研究中，還需要進(jìn)一步消除冗余不變量，提高失效數(shù)據(jù)的獨(dú)立性。