王 強,陳世航,徐 佳

(1.中國賽寶實驗室,廣州 廣東 511370;2. 南京郵電大學(xué) 江蘇省大數(shù)據(jù)安全與智能處理重點實驗室,江蘇 南京 210023)

軟件測試借助大量的測試用例對軟件產(chǎn)品進行全方位的測試,并基于反饋的測試結(jié)果,修復(fù)軟件產(chǎn)品中的缺陷,改進產(chǎn)品的質(zhì)量[1]。專業(yè)測試人員招募以及模擬測試環(huán)境構(gòu)建顯著增加了軟件測試的成本。為解決這一問題,研究者提出了基于眾包[2]的軟件測試模式。眾包軟件測試能夠通過眾包的方式以較低的成本招募到合適的測試人員,同時保證軟件測試環(huán)境為真實場景,可有效縮短軟件測試周期和降低軟件測試成本。

眾包軟件測試由3方組成:測試任務(wù)發(fā)布者、眾包工人和眾包平臺,后文分別簡化為發(fā)布者,工人和平臺。軟件測試任務(wù)需要根據(jù)任務(wù)大小、測試需求、設(shè)備需求、測試報告的規(guī)范等進行分類。工人需要具備基本的測試能力并配備相應(yīng)的測試設(shè)備,同時了解測試的對象產(chǎn)品。眾包軟件測試通常通過拍賣的方式進行。發(fā)布者提交測試任務(wù)到平臺,工人根據(jù)自身的資源提交想要執(zhí)行的測試任務(wù)報價到平臺。當(dāng)平臺收到工人提交的報價后,平臺根據(jù)測試任務(wù)的需求,為不同類型的任務(wù)招募足夠的工人,以完成測試任務(wù)。當(dāng)工人完成任務(wù)后,將生成的測試報告提交到平臺,平臺將測試報告發(fā)送給發(fā)布者審核,審核通過的工人可以獲得相應(yīng)的報酬。

目前已經(jīng)有部分研究者研究眾包軟件測試人員的招募問題[3],包括招募工人完成體驗質(zhì)量(Quality of experience,QoE)測試[4]、圖形用戶界面(Graphical user interface,GUI)測試[5]等功能性測試,以及測試用例生成[6]、程序調(diào)試與修復(fù)[7]等非功能性測試。同時也有部分工作研究工人之間的競爭[8,9]和合作[10,11]問題。另外,工人完成任務(wù)后提交的測試報告審核也是一項具有挑戰(zhàn)的任務(wù)。文獻[12]提出了使用多樣性策略和動態(tài)風(fēng)險策略對測試報告進行審核。文獻[13]利用空間金字塔的方法比較測試報告的差異距離以審核報告的可用性。除此之外,眾包軟件測試框架設(shè)計也是目前主流的研究之一[14,15]。隱私安全也是眾包軟件測試中被重點關(guān)注的領(lǐng)域。Wang等[16]研究了工人的代碼和身份隱私安全問題。文獻[17]和[18]研究了數(shù)據(jù)庫中心應(yīng)用中的工人數(shù)據(jù)安全問題。上述工作均沒有考慮眾包工人的報價隱私保護問題。

由于參與測試任務(wù)的工人通常為理性且好奇的,他們都想要獲得更多的收益并且企圖獲取其他工人的信息,所以可能存在以下兩種攻擊:(1)激勵攻擊:測試成本作為工人的隱私信息,攻擊者在報價時通過上報一個不同于測試成本的報價來隱瞞自身的測試成本,而不誠實的報價可能會使攻擊者能夠獲取更多的效用。因此,需要設(shè)計一個具有真實性的機制保證工人能夠誠實地上報自己的測試成本;(2)推斷攻擊:為了保證公平性,平臺會將獲勝工人公布,那么攻擊者能夠通過公布的結(jié)果推斷出其他工人的報價,這種攻擊被稱為推斷攻擊[19]。如果機制是真實的,工人會誠實上報自己的測試成本,那么推斷攻擊會導(dǎo)致工人的測試成本隱私暴露。因此,需要設(shè)計一個隱私保護機制保護工人的測試成本。

本文結(jié)合拍賣機制[20,21]以及差分隱私機制[22],設(shè)計了一個隱私保護眾包軟件測試激勵機制。拍賣機制已在眾包領(lǐng)域被廣泛使用[23,24]。差分隱私機制能夠保證對于任意一個工人報價的改變,輸出的改變在可以控制的范圍內(nèi),使得攻擊者無法通過輸出推斷出工人的測試成本隱私[25]。本文以最小化招募工人的成本為目標(biāo),將問題建模為一個買家(平臺)和多個賣家(工人)的反向拍賣模型,通過拍賣機制激勵工人誠實的上報自己的成本,從而防止激勵攻擊。采用差分隱私中的指數(shù)機制[26]以概率選擇獲勝工人,實現(xiàn)工人的測試成本隱私保護。

1 系統(tǒng)模型和問題定義

1.1 系統(tǒng)模型

(1)

1.2 攻擊模型

(1)激勵攻擊:眾包軟件測試系統(tǒng)中,工人是自私且理性的,所以工人有動機通過提交一個不同于測試成本的報價來提升自身的效用。

(2)推斷攻擊:真實的基于拍賣的激勵機制會激勵工人上報其真實的測試成本,即bi=ci。然而當(dāng)工人上報其真實的測試成本時,其他的工人可能通過機制的輸出(即獲勝者)推斷出這個工人的真實測試成本。

1.3 預(yù)期的性質(zhì)

(1)計算有效性:如果一個機制能夠在多項式時間內(nèi)得到結(jié)果,那么此機制是計算有效的。

(2)個體理性:如果一個機制能夠保證所有工人在誠實上報他的測試成本的情況下,所獲得的效用是非負的,即ui≥0,那么此機制是滿足個體理性的。

(3)真實性:如果一個機制能夠保證工人在真實上報測試成本的情況下的效用是最大的,那么該機制是真實的。

除此之外,還需要保護工人的測試成本隱私,本文使用差分隱私機制保護工人的隱私安全。在此之前,先介紹差分隱私的定義。

定義1差分隱私[25]:一個隨機機制M:Xn→Y能夠提供 (ε,δ)差分隱私保護,當(dāng)且僅當(dāng)對于任意相鄰數(shù)據(jù)集D,D′ ∈Xn(D和D′ 僅有一條記錄不同),對于任意的輸出O?Y,有

Pr[M(D)∈O]≤exp(ε)×Pr[M(D′)∈O]+δ

(2)

特別地,當(dāng)δ=0時,機制M滿足ε-差分隱私保護。

(1)Pri(z)關(guān)于bi是單調(diào)非遞增的。

指數(shù)機制是差分隱私保護中常常使用到的機制。指數(shù)機制的關(guān)鍵是設(shè)計得分函數(shù)S(D,o),其中D表示輸入集合,o∈O表示輸出。得分函數(shù)是評估此輸入和輸出的分值,表示對于輸入D來說,輸出o相比于最優(yōu)輸出的好壞程度。

(3)

定義Λ為兩個輸入集合的差值的上界,那么就有以下定理。

定理2[24]指數(shù)機制滿足2εΛ-差分隱私。

(4)

1.4 問題定義

本文的目標(biāo)是在保護工人的報價隱私的情況下,最小化總測試成本,并且滿足計算有效性、個體理性、真實性和差分隱私性。此測試成本最小化問題可形式化如下

(5)

s.t. ∪wi∈UTi=R

(6)

這個問題表示在保證所選擇的工人能夠完成所有測試任務(wù)的情況下,最小化總測試成本。

2 隱私保護眾包軟件測試激勵機制設(shè)計

首先分析測試成本最小化問題的難度。

定理4測試成本最小化問題是NP-難的。

證明首先證明最小權(quán)重集合覆蓋問題與測試成本最小化問題是等價的。

最小權(quán)重集合覆蓋問題的實例:給定全集K和集合S={s1,s2,…,sn},任意si∈S是K的子集,即si?K。每個si的權(quán)重為w(si),問題是找到一個總權(quán)重最小的子集S′?S,并且S′中的元素能夠覆蓋全集K。

測試成本最小化問題的實例:給定測試任務(wù)集R和工人的任務(wù)集合T={T1,T2,…,Tn},任意Ti∈T是R的子集,即Ti?R。每個Ti對應(yīng)的成本為ci,問題是找到一個總成本最小的子集T′?T,并且T′中所包含的任務(wù)能夠覆蓋測試任務(wù)集R。

綜上所述,最小權(quán)重集合覆蓋問題和測試成本最小化問題是等價的。最小權(quán)重集合覆蓋問題是典型的NP-難問題,因此測試成本最小化問題也是NP-難問題。

本文提出的隱私保護眾包軟件測試激勵機制如算法1所述。算法共包含3個階段:工人篩選階段,獲勝者選擇階段以及報酬計算階段。首先初始化已完成任務(wù)集合RU為空集,初始化候選工人集合Re為工人集合W(行1)。

算法1隱私保護眾包軟件測試激勵機制

2:foreachwi∈Wdopi=0;

3:whileRU≠Rdo

//工人篩選階段

4: foreachwi∈Redo

5: ifTi?RUthenRe←Rewi};

6: end

//獲勝者選擇階段

7: foreachwi∈Redo

8: 基于式(9)計算每個工人被選中的概率Pri(bi);

9: end

10: 基于式(9)計算得到的概率分布,隨機選擇一個工人作為獲勝者,記為w′i;

11:U←U∪{w′i};RU←RU∪Ti′;Re←Rew′i};

12:end

//報酬計算階段

13:foreachwi∈Udo

15:end

(1)工人篩選階段。

算法4～6行,遍歷候選工人集合,查看被遍歷的工人的任務(wù)子集是否已經(jīng)在已完成任務(wù)集合RU中。如果已經(jīng)被RU所覆蓋,那么就將這個工人從候選工人集合Re中刪除。

(2)勝者選擇階段。

算法7～12行,為每一個在候選工人集合Re中的工人計算被選中的概率(行8),并根據(jù)概率分布隨機選擇一個工人作為獲勝者(行10)。工人被選中的概率根據(jù)得分函數(shù)計算得到。在計算得分函數(shù)之前,首先確定每個工人wi的選擇標(biāo)準r(βi)

(7)

本文的機制是選擇r(βi)最小的工人。下一步為選擇標(biāo)準r(βi)設(shè)計一個單調(diào)非遞增的得分函數(shù)。本文將對數(shù)函數(shù)S(x)=log1/2x作為選擇標(biāo)準r(βi)的得分函數(shù)。對任意的工人wi,在每次迭代中被選中的概率服從如下分布

(8)

Pri(bi)=

(9)

最后更新獲勝者集合U,已完成任務(wù)集合RU和候選工人集合Re(行11)。

(3)報酬計算階段。

在報酬計算階段,每個獲勝者wi∈U的報酬計算為

(10)

3 激勵機制性質(zhì)分析

本節(jié)從理論角度分析隱私保護眾包軟件測試激勵機制的性質(zhì)。

定理5隱私保護眾包軟件測試激勵機制的時間復(fù)雜度為O(mn)。

證明算法1第3～12行的while循環(huán)中,總共包含m個任務(wù),最多迭代m次可以保證所有的測試任務(wù)被完成,內(nèi)層4～6行和7～9行的兩個for循環(huán),遍歷了所有投標(biāo)的工人,工人的總數(shù)為n,所以算法3～12行的時間復(fù)雜度為O(mn)。算法13～16行計算每個獲勝工人的報酬,獲勝集合U最大工人數(shù)為n,所以時間復(fù)雜度為O(n)。綜上,機制的時間復(fù)雜度為O(mn)。

定理6隱私保護眾包軟件測試激勵機制是真實的。

E[pi]=(1-Pri(bi))×0+Pri(bi)×

(11)

根據(jù)定理1,可以得出,隱私保護眾包軟件測試激勵機制是真實的。

定理7隱私保護眾包軟件測試激勵機制是個體理性的。

(12)

式中:Wj=Wwi1,wi2,…,wij-1}。

以下分兩種情況討論。

情況1當(dāng)bd

(13)

情況2當(dāng)bd≥b′d,當(dāng)j∈[1,l],并且任意工人wj=wd時,第一項小于1,否則第一項等于1,綜上,第一項的最大值為1,所以有

(14)

(15)

(16)

至此,定理得證。

證明令U*表示測試成本最小化問題的最優(yōu)解,假設(shè)有一系列獲勝者工人被本文提出的算法選中,即U=w1,w2,…,wl。

對于每個wi,1≤i≤l,假設(shè)Ui表示工人集合,此集合滿足?j∈Ui:

(1)j∈U*;

(2)Tj∩Twj≠?;

(3)Tj∩Twk=?,?k∈[1,i-1];

Ui表示部分工人集合,Ui中的工人在U*中,但是由于工人wi的原因不在U中。根據(jù)定理6證明的真實性,有bi=ci。根據(jù)定理3,取α=t,有至少1-e-t的概率得到

(17)

這表示可以以最低1-e-t的概率得到

(18)

將所有的j∈Ui求和,可以得到以最低1-e-t的概率得到

(19)

最后,對所有的wi∈U求和可以得到

(20)

4 性能評估

4.1 試驗設(shè)置

本節(jié)測試隱私保護眾包軟件測試激勵機制的性能。試驗部分設(shè)計一個無隱私保護的眾包軟件測試激勵機制作為對比算法,此機制的目標(biāo)是在完成所有測試任務(wù)的情況下保證最小測試成本,并且不考慮工人的報價隱私。試驗參數(shù)設(shè)置如表1所示。

表1 試驗參數(shù)設(shè)置

本文通過3個指標(biāo)測試隱私保護眾包軟件測試激勵機制的性能:總招募成本、總報酬和隱私泄露。

(1)總招募成本:所有獲勝工人的總成本。

(2)總報酬:所有獲勝工人獲得的報酬之和。

(21)

PL的值越小,攻擊者越難分辨出兩個標(biāo)書集合,隱私保護效果越好。

4.2 總招募成本

圖1和圖2分別比較了在不同任務(wù)數(shù)量下和不同測試工人數(shù)量下的招募工人的總成本。從圖1中可以看出,隨著任務(wù)數(shù)量的增加,兩種算法的招募工人的總成本均增加。因為增加任務(wù)數(shù)量,平臺需要招募更多的工人完成任務(wù),所以總成本會增加。與圖1不同,招募工人的總成本隨著工人數(shù)量的增加呈下降趨勢。因為當(dāng)參與測試任務(wù)的測試工人增加時,平臺可以選擇更便宜的工人完成任務(wù),所以招募工人的總成本會下降。由于無隱私保護的眾包激勵機制不需要考慮工人的隱私保護,所以其總成本最低,而本文提出的隱私保護眾包激勵機制通過概率選擇測試工人,可能會招募到選擇標(biāo)準r較高的工人,所以本文的招募工人總成本高于無隱私保護的眾包激勵機制。本文提出的隱私保護激勵機制的總成本比無隱私保護激勵機制的總成本平均高出27.31%。

圖1 不同測試任務(wù)數(shù)量下的總成本

圖2 不同測試工人數(shù)量下的總成本

4.3 總報酬

圖3和圖4分別測試了在不同測試任務(wù)數(shù)量和測試工人數(shù)量下平臺需要支付的總報酬。平臺支付的總報酬隨著任務(wù)數(shù)量的增加而增加,更多的任務(wù)意味著招募更多的工人,平臺需要支付更多的報酬。測試工人的數(shù)量增加,使得平臺能夠選擇價格更低廉的工人,那么支付的總報酬也隨之降低。定理7中證明了任意工人的效用是非負的,因此,實際支付給測試工人的報酬是不低于其報價的,圖3和圖4中的總報酬在相同的情況下是分別高于圖1和圖2中的總成本的,試驗結(jié)果與理論相符合。

圖3 不同測試任務(wù)數(shù)量下的總報酬

圖4 不同測試工人數(shù)量下的總報酬

4.4 隱私泄露

圖5分別測試了隱私預(yù)算ε對招募工人的總成本以及測試工人的隱私泄露的影響。從圖中可以看出,工人隱私泄露的概率隨著隱私預(yù)算的提高而上升,較大的隱私預(yù)算使得隱私泄露PL的值增加,攻擊者能夠通過輸出發(fā)現(xiàn)兩個鄰居數(shù)據(jù)集之間的差異,使得工人的隱私泄露的可能性增加。而較差的隱私保護,使得平臺能更精確地找到選擇標(biāo)準r最小的測試工人,所以招募工人的總成本隨著隱私預(yù)算的增加而降低。

圖5 不同的隱私預(yù)算下的總成本以及隱私泄露

5 結(jié)束語

本文提出了一種隱私保護眾包軟件測試激勵機制以防止激勵攻擊并保護工人的測試成本隱私。文章通過理論分析證明了本文的激勵機制能夠保證計算有效性、真實性、個體理性以及差分隱私性,試驗結(jié)果表明本文的激勵機制平均犧牲了27.31%的招募成本以保證工人的隱私安全,理論結(jié)果和試驗結(jié)果相符合,為眾包軟件測試的隱私保護領(lǐng)域提供理論依據(jù)。在未來的工作中,將考慮根據(jù)每個工人的實際需求,為每個工人提供個性化的隱私保護。