王 強(qiáng),陳世航,徐 佳

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

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

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

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

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

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

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

1.1 系統(tǒng)模型

(1)

1.2 攻擊模型

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

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

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

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

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

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

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

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

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

(2)

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

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

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

(3)

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

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

(4)

1.4 問題定義

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

(5)

s.t. ∪wi∈UTi=R

(6)

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

2 隱私保護(hù)眾包軟件測(cè)試激勵(lì)機(jī)制設(shè)計(jì)

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

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

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

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

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

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

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

算法1隱私保護(hù)眾包軟件測(cè)試激勵(lì)機(jī)制

2:foreachwi∈Wdopi=0;

3:whileRU≠Rdo

//工人篩選階段

4: foreachwi∈Redo

5: ifTi?RUthenRe←Rewi};

6: end

//獲勝者選擇階段

7: foreachwi∈Redo

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

9: end

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

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

12:end

//報(bào)酬計(jì)算階段

13:foreachwi∈Udo

15:end

(1)工人篩選階段。

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

(2)勝者選擇階段。

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

(7)

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

(8)

Pri(bi)=

(9)

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

(3)報(bào)酬計(jì)算階段。

在報(bào)酬計(jì)算階段,每個(gè)獲勝者wi∈U的報(bào)酬計(jì)算為

(10)

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

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

定理5隱私保護(hù)眾包軟件測(cè)試激勵(lì)機(jī)制的時(shí)間復(fù)雜度為O(mn)。

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

定理6隱私保護(hù)眾包軟件測(cè)試激勵(lì)機(jī)制是真實(shí)的。

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

(11)

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

定理7隱私保護(hù)眾包軟件測(cè)試激勵(lì)機(jī)制是個(gè)體理性的。

(12)

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

以下分兩種情況討論。

情況1當(dāng)bd

(13)

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

(14)

(15)

(16)

至此,定理得證。

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

對(duì)于每個(gè)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證明的真實(shí)性,有bi=ci。根據(jù)定理3,取α=t,有至少1-e-t的概率得到

(17)

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

(18)

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

(19)

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

(20)

4 性能評(píng)估

4.1 試驗(yàn)設(shè)置

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

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

本文通過3個(gè)指標(biāo)測(cè)試隱私保護(hù)眾包軟件測(cè)試激勵(lì)機(jī)制的性能:總招募成本、總報(bào)酬和隱私泄露。

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

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

(21)

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

4.2 總招募成本

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

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

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

4.3 總報(bào)酬

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

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

圖4 不同測(cè)試工人數(shù)量下的總報(bào)酬

4.4 隱私泄露

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

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

5 結(jié)束語

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