李 方，付曉東，2，岳 昆，劉 驪，劉利軍，馮 勇

1(昆明理工大學 信息工程與自動化學院，昆明 650500) 2(昆明理工大學 云南省計算機技術(shù)應(yīng)用重點實驗室，昆明 650500) 3(云南大學 信息學院，昆明 650091)

1 引 言

隨著互聯(lián)網(wǎng)應(yīng)用的飛速發(fā)展與進步，傳統(tǒng)商業(yè)環(huán)境發(fā)生了巨大的改變，以互聯(lián)網(wǎng)為媒介向用戶提供在線服務(wù)在企業(yè)中得到快速普及，成為企業(yè)運行的發(fā)展趨勢和必然選擇[1].在線服務(wù)是指利用互聯(lián)網(wǎng)技術(shù)，向用戶提供線上服務(wù)的方式.在線服務(wù)給人們的日常工作生活帶來了巨大的便利，利用這種技術(shù)，用戶可以進行數(shù)據(jù)共享、完成信息交換、購買商品和服務(wù)等[2].用戶與在線服務(wù)進行交互后，依照主觀感受對服務(wù)做出評價，表達他們的偏好及滿意程度[3].通過聚合用戶群體的偏好信息獲得服務(wù)信譽，可幫助用戶群體在具有相似功能的在線服務(wù)中選擇出滿足用戶需求的服務(wù).

在線服務(wù)信譽是用戶對在線服務(wù)的信任程度，對于在線服務(wù)選擇起著重要的作用[4].客觀、有效的在線服務(wù)信譽度量方法在幫助用戶選擇優(yōu)質(zhì)的在線服務(wù)和提升在線服務(wù)質(zhì)量方面具有重要的應(yīng)用價值[5].為了提高自身影響力或者降低對手影響力，惡意用戶或者在線服務(wù)提供商可能操縱、攻擊信譽系統(tǒng)，扭曲在線服務(wù)的信譽，致使用戶利用這種信譽進行服務(wù)選擇時會產(chǎn)生不客觀的結(jié)果，從而使用戶面臨無法選擇到滿足需求服務(wù)的風險[6].惡意用戶對信譽系統(tǒng)的攻擊通常具有欺騙性、合謀性或戰(zhàn)略性，誤導買家與服務(wù)進行交易[7，8].這其中有一類特殊的群體，就是信譽系統(tǒng)的管理者，他們掌握了普通用戶的偏好，為獲取不當利益，可以通過刪除或者增加用戶、服務(wù)以使特定服務(wù)成為信譽最高的服務(wù).

現(xiàn)有工作重點關(guān)注普通用戶或者在線服務(wù)提供者對信譽的操縱，而缺少通過技術(shù)手段防范信譽系統(tǒng)管理者對服務(wù)信譽進行控制的措施.為此，本文提出利用Fallback的在線服務(wù)信譽防控制機制.該機制通過提高控制用戶偏好策略的計算復雜性，將在線服務(wù)信譽控制建模為判斷某一服務(wù)是否能通過控制成為信譽最高的服務(wù)的問題.理論證明利用Fallback的在線服務(wù)信譽控制的問題是固定參數(shù)不可解的，即利用Fallback的用戶偏好控制問題是具有抵抗力的(Resistance)[9]，從而利用Fallback的信譽系統(tǒng)難以被控制.

2 相關(guān)工作

隨著電子商務(wù)的快速發(fā)展，用戶獲取線上服務(wù)變得越來越方便，但信用缺失問題也越來越嚴重.雖然電子商務(wù)系統(tǒng)設(shè)置了信譽排名和推薦機制，為用戶在選擇誠信服務(wù)方面提供輔助的決策支持.然而，一些惡意用戶、在線服務(wù)提供商不斷采取欺騙、偽裝、漂白、共謀、歧視等策略控制用戶偏好，進而誤導用戶進行服務(wù)選擇[10，11].

總結(jié)現(xiàn)有的在線服務(wù)信譽系統(tǒng)防控制機制，主要包括4方面：減輕通過虛假信息進行操縱的影響；識別惡意用戶，對他們做出懲罰或者進行隔離；激勵用戶表達真實偏好；增加控制者的控制成本(成本可能是金錢、時間等).

減輕通過虛假信息進行操縱的影響來防控制比較常見.Anupama Aggarwal建立了檢測用戶對信譽系統(tǒng)操縱行為的機制，利用可疑用戶的時間行為和網(wǎng)絡(luò)特征，可以從合法用戶中檢測出虛假操縱行為，減輕操縱信譽對在線社交網(wǎng)絡(luò)的影響[12].Jaehong Ahn等提出從存儲在基于區(qū)塊鏈的在線支付系統(tǒng)交易的原始評價中獲取信譽[13]，防止信息被惡意操縱.

識別惡意用戶，對他們做出懲罰或隔離方面，Xin Wang等基于印象理論，提出了一種由最近鄰搜索算法及分類算法組成的無監(jiān)督策略，隔離誠實和不誠實的用戶及服務(wù)[14].Nitin Kumar Saini等提出了一種針對共謀檢測的反應(yīng)性解決方案，并針對檢測到的惡意用戶提出了降低其聲譽的懲罰策略[15]；馬述忠等基于網(wǎng)絡(luò)店鋪銷售假冒行為，構(gòu)建了不完全信息的動態(tài)博弈模型，考察了懲罰機制和信譽機制的治理效果[16].

激勵用戶表達真實偏好方面，Junsheng Chang等提出了一種基于政策的公平差別化服務(wù)激勵機制，定義了參與水平和推薦可信度這兩個參數(shù)，識別了信譽系統(tǒng)中用戶的行為特征[17].基于上述兩個參數(shù)，還提出了一個簡單而有效的信譽信息交換協(xié)議，以激勵用戶誠實的表達真實偏好；Ali Ghaffarinejad等針對面向服務(wù)的環(huán)境，提出了一種基于多個特殊信譽中心的分布式信譽機制[18].該機制具有抗共謀的能力，并激勵企業(yè)資信管理人員嘗試全面收集信譽信息并如實報告；Yingtao Xu等基于信譽評價的動態(tài)特性，提出了一種基于最優(yōu)控制問題的在線信譽動態(tài)反饋激勵模型[19].

增加控制者的控制成本方面，Kevin Hoffman等提出的抗Sybil攻擊的解決方案分為集中式和分布式兩種[20].在集中式方法中，中央權(quán)威機構(gòu)發(fā)出和驗證每個實體唯一的憑證.為了增加獲得多個身份的成本，中央權(quán)威可能需要為每個身份支付貨幣或計算費用；Bhupender Kumar等通過設(shè)置身份節(jié)點在網(wǎng)絡(luò)中保持可信的全局信任閾值，增加控制成本來阻止攻擊[21].

上述研究中對于信譽系統(tǒng)的防控制對象都是使用信譽系統(tǒng)的普通用戶或在線服務(wù)提供者.然而對信譽系統(tǒng)內(nèi)部的管理者來說，他們更容易掌握用戶信息，可以根據(jù)掌握到的用戶偏好對當前的用戶、在線服務(wù)進行增加、刪除等操作對服務(wù)信譽進行有針對性的操縱，使信譽系統(tǒng)面臨被其管理者操縱的道德風險.為此，本文考慮了掌握所有用戶偏好的信譽系統(tǒng)管理者的易控制性，利用了社會選擇理論中的方法，提出了一種利用Fallback的在線服務(wù)信譽防控制機制.最后通過理論分析和實驗驗證了方法的合理性和有效性.

3 問題描述

3.1 問題定義

對信譽系統(tǒng)的控制可分為構(gòu)造性控制和破壞性控制，并且兩種控制類型都通過增加和刪除用戶或服務(wù)進行控制.構(gòu)造性控制作為一種最經(jīng)典且最常見的控制[22]，不失一般性，本文重點闡述構(gòu)造性控制問題.為了更好地闡述利用Fallback的在線服務(wù)信譽防控制的問題，本文首先給出相關(guān)定義如下：

定義1.集合U={ui|i=1，2，…，n}為所有用戶集合；集合S={sj|j=1，2，…，m}為用戶產(chǎn)生交互的所有服務(wù)集合.其中，n為用戶的個數(shù)，m為在線服務(wù)的個數(shù).

定義2.評分向量ri=(ri1，ri2，…rij，…，rim)表示用戶ui對所有服務(wù)的評分信息，rij表示用戶ui對服務(wù)sj的評分，說明用戶ui對服務(wù)sj的滿意程度.評分采用電子商務(wù)評價機制中常用的5個評分等級，1-5分別表示很不滿意、不滿意、一般、滿意和很滿意.所有用戶對服務(wù)的評分信息用矩陣R=[rij]m×n表示.

由于在線服務(wù)規(guī)模非常龐大，用戶不可能對所有服務(wù)進行評分.目前，協(xié)同過濾方法已被廣泛地用于信譽系統(tǒng)，該方法通過尋找與自己偏好相似的用戶進行評分預測.為此，可采用Fernández-Tobías I等人提出的協(xié)同過濾方法[23]對評分進行填充.

定義3.服務(wù)集S的信譽用信譽向量rp=(rp1，rp2，…rpj，…，rpm)表示，rpj為服務(wù)sj的信譽值.根據(jù)用戶對在線服務(wù)的評分R采用不同的信譽度量方法可以得到在線服務(wù)的信譽rp.

定義4.管理者對在線服務(wù)信譽控制的問題可表述為f：O→sj，sj∈S，其中sj為信譽最高的服務(wù)，集合O為所有用戶的序數(shù)偏好.即管理者通過對所有用戶對在線服務(wù)的偏好O實施控制使服務(wù)sj成為信譽最高的服務(wù).

管理者對在線服務(wù)信譽控制問題具體可分為增加用戶構(gòu)造性控制問題、刪除用戶構(gòu)造性控制問題、增加服務(wù)構(gòu)造性控制問題和刪除服務(wù)構(gòu)造性控制問題.

定義5.增加用戶構(gòu)造性控制問題：給定用戶偏好集合O，實施控制前的初始用戶集合U1、增加的干擾用戶集合U2(U=U1∪U2，U1∩U2=?)，控制后信譽最高的服務(wù)sj∈S，基于用戶群體偏好O通過增加干擾用戶U2使得服務(wù)sj成為信譽最高的服務(wù).

即信譽系統(tǒng)管理者利用掌握到的用戶偏好，通過增加干擾用戶使得實施控制前的某一特定服務(wù)成為信譽最高的服務(wù).

定義6.刪除用戶構(gòu)造性控制問題：給定用戶偏好集合O，實施控制后信譽最高的服務(wù)sj∈S，基于用戶群體偏好O通過刪除用戶集U中k個用戶使得服務(wù)sj成為信譽最高的服務(wù).

即信譽系統(tǒng)管理者利用掌握到的用戶偏好，通過刪除用戶使得某一特定服務(wù)成為信譽最高的服務(wù).

定義7.增加服務(wù)構(gòu)造性控制問題：給定用戶偏好集合O，實施控制前的初始服務(wù)集合S1、增加的干擾服務(wù)集合S2(S=S1∪S2，S1∩S2=?)，控制后信譽最高的服務(wù)sj∈S1，基于用戶群體偏好O通過增加干擾服務(wù)S2使得服務(wù)sj成為信譽最高的服務(wù).

即信譽系統(tǒng)管理者利用掌握到的用戶偏好，通過增加干擾服務(wù)使得實施控制前的某一特定服務(wù)成為信譽最高的服務(wù).

定義8.刪除服務(wù)構(gòu)造性控制問題：給定用戶偏好集合O，實施控制后信譽最高的服務(wù)sj∈S，基于用戶群體偏好O通過刪除服務(wù)集S中k個服務(wù)使得服務(wù)sj成為信譽最高的服務(wù).

即信譽系統(tǒng)管理者利用掌握到的用戶偏好，通過刪除服務(wù)使得某一特定服務(wù)成為信譽最高的服務(wù).

因此，本文旨在解決通過增加、刪除用戶或服務(wù)的構(gòu)造性控制問題，防止信譽系統(tǒng)內(nèi)部的管理者將某特定服務(wù)控制為信譽最高的服務(wù)，干擾用戶的選擇.

3.2 舉例說明

例.以常見的均值法增加用戶的構(gòu)造性控制問題為例.假設(shè)有用戶集U={u1，u2，u3，u4，u5}，u5是增加的干擾用戶，服務(wù)集S={s1，s2，s3，s4}，用戶-服務(wù)的評分矩陣R如表1所示，需解決基于用戶對服務(wù)的偏好信息通過增加用戶使得服務(wù)s2成為信譽最高服務(wù)的問題：

表1 用戶-服務(wù)評分表Table 1 User-service score sheet

由表1可見，通過計算所有用戶對服務(wù)評分的平均值得到其服務(wù)信譽，得到的信譽向量為rp=(3，2.75，2.25，2.5)，s1為當前信譽最高的服務(wù).通過增加干擾用戶u5后的用戶-服務(wù)評分表如表2所示.

表2 用戶-服務(wù)評分矩陣表Table 2 User-service score sheet

增加干擾用戶u5后得到的信譽向量為rp=(2.8，3.2，2.4，2.8).通過增加用戶控制，使得服務(wù)s2成為了信譽最高的服務(wù).因此通過增加用戶可以很容易地對均值法實施構(gòu)造性控制.本文提出Fallback方法進行在線服務(wù)信譽度量，以解決信譽系統(tǒng)內(nèi)部的管理者利用掌握到的用戶偏好，對服務(wù)信譽進行控制的問題.

4 利用Fallback的在線服務(wù)信譽防控制機制

Fallback方法是Bucklin與Approal混合的社會選擇方法[24].Bucklin方法中每個用戶要根據(jù)他的偏好對所有的服務(wù)進行嚴格的線性排序；Approal方法中用戶通過批準向量(0，1)表達偏好，0代表不贊同，1代表贊同.Fallback將Bucklin和Approal結(jié)合起來，每個用戶提供對他所認可服務(wù)的嚴格偏好排序.目前已知的社會選擇方法中，F(xiàn)allback方法顯示了最廣泛的控制抵抗力[9].因此，本文利用Fallback，設(shè)計了一種在線服務(wù)信譽防控制機制，利用Fallback控制用戶偏好問題的計算復雜性高的特性來防止管理者控制信譽.

4.1 利用Fallback的在線服務(wù)信譽度量

本文信譽度量方法的核心是根據(jù)所有用戶對在線服務(wù)的偏好獲取滿足Fallback絕對多數(shù)閾值條件的在線服務(wù)信譽向量.

定義9.用戶ui對在線服務(wù)的評分rij越大表示ui對sj越滿意，rij>rik表示用戶ui認為服務(wù)sj優(yōu)于服務(wù)sk(記作sj?isk)；rij

首先根據(jù)用戶ui對在線服務(wù)的評分信息ri，將每個用戶對在線服務(wù)的評分按大小進行排序，若在線服務(wù)對應(yīng)的評分相同則采用隨機法對評分相同的服務(wù)進行排序，獲取所有用戶的序數(shù)偏好集合.例如，對于表1中用戶u1的評分信息為r1=(4，2，3，1)，對4個服務(wù)分數(shù)進行排序可以得到用戶u1對在線服務(wù)的偏好序β1：s1?1s3?1s2?1s4.

若用戶提供了對在線服務(wù)的偏好排序，則可直接使用該排序作為用戶偏好O.由于用戶不可能對所有服務(wù)進行偏好排序，即用戶偏好序是不完全序.為此，可采用William Webber[6]、Riku Togashi等提出[25]的概率用戶模型，處理不完整偏好排序，從而得到一個完整偏好排序.

獲取所有用戶對在線服務(wù)的偏好排序后利用Fallback方法計算信譽向量，得到最終所有用戶對服務(wù)的信譽度及最終的用戶群體偏好.首先需要得到在線服務(wù)在偏好排序中的l級分數(shù).基于所有用戶的序數(shù)偏好集合O，計算每一個在線服務(wù)sj∈S在偏好排序中的l級分數(shù)scorel(sj)，其表示將在線服務(wù)sj排在前l(fā)位的用戶的數(shù)量，l=1，2，…，n.

定義10.函數(shù)Di的取值為0、1：若用戶ui認為服務(wù)sj優(yōu)于sk，即sj?isk則Di(sj?isk)=1、Di(sk?isj)=0；認為sk優(yōu)于sj，則Di(sk?isj)=1、Di(sj?isk)=0.

定義11.函數(shù)Mi的取值為0、1，可以表示為：

(1)

最終服務(wù)sj在偏好排序中的l級分數(shù)scorel(sj)為：

(2)

比如，根據(jù)表1的評分信息得出偏好排序，沒有用戶將在線服務(wù)s3排在第1位，所以服務(wù)s3的1級分數(shù)為0；用戶u1、u2將在線服務(wù)s3排在前2位，所以服務(wù)s3的2級分數(shù)為2；用戶u1、u2、u3將在線服務(wù)s3排在前3位，所以服務(wù)s3的3級分數(shù)為3.同理我們也可以分別計算出其余在線服務(wù)的l級分數(shù)，最終得到l級分數(shù)scorel(sj)如表3所示.

表3 服務(wù)的l級分數(shù)表Table 3 Level l score of services sheet

得到在線服務(wù)在偏好排序中的l級分數(shù)后，需要判斷這些分數(shù)是否滿足絕對多數(shù)閾值條件.用戶集U中的用戶的絕對多數(shù)閾值為：

maj(U)=|U|/2+1

(3)

1)根據(jù)在線服務(wù)在偏好排序中的l級分數(shù)，判斷第一級中是否有達到scorel(sj)≥maj(U)條件的服務(wù)；

2)若有，則該服務(wù)的信譽值即為當前滿足絕對多數(shù)閾值條件的一級分數(shù)；

3)若沒有達到條件，判斷下一級分數(shù)中是否存在滿足條件的服務(wù)，直到得到每個服務(wù)的信譽值.

最先達到絕對多數(shù)閾值條件的服務(wù)是用戶群體偏好排名第1的服務(wù)，若在同一級分數(shù)中存在幾個滿足條件的服務(wù)，則對這些服務(wù)的分數(shù)進行排序從而得到最終的用戶群體偏好.比如，表3中在第2級中服務(wù)s1的信譽是最先達到閾值3的，服務(wù)s2、s3的信譽都在第3級達到閾值3，服務(wù)s2的信譽4大于服務(wù)s3的信譽3，最終得到的信譽向量為rp=(3，4，3，4)，最終的偏好排序為s1?s2?s3?s4.

基于以上分析，最后確定出利用Fallback的在線服務(wù)信譽度量函數(shù)：

f(sj)=scorel(sj)，scorel(sj)≥maj(U)

(4)

算法1給出了利用Fallback的在線服務(wù)信譽度量算法.其中Mi(sj)由公式(1)計算得出.

算法1.利用Fallback的在線服務(wù)信譽度量算法

輸入：所有用戶的序數(shù)偏好集合O

輸出：在線服務(wù)信譽向量rp

2.fori=1 tondo

3.forj=1 tomdo

4.fork=1 tomdo

6.endfor

7.endfor

8.endfor

10.ifscorel(sj)≥maj(U) then

11.rpj=scorel(sj);

12.else if

13.l+1;

14. goto to (10);

15.fill the vectorrpbyrpj;

16.returnrp;

從上面描述可以看出，算法1中第2行-第4行的for循環(huán)表示每個用戶都對服務(wù)sj與除sj以外的其他服務(wù)逐一進行比較，其時間復雜度為O(nm2)，最終算法1的時間復雜度為O(nm2).

4.2 理論分析

為了通過理論驗證本方法防控制的有效性，下面對利用Fallback的在線服務(wù)信譽度量方法的防控制性進行證明.

防控制性表明Fallback控制用戶偏好問題的計算復雜性高，即證明構(gòu)造性控制問題是固定參數(shù)不可解的.本文以利用Fallback的刪除服務(wù)構(gòu)造性控制問題為例，證明該控制問題固定參數(shù)不可解，首先給出參數(shù)化問題[26]相關(guān)定義如下：

定義12.參數(shù)化問題分為固定參數(shù)可解(fixed- parameter tractability，F(xiàn)PT)和固定參數(shù)不可解.FPT：給定利用Fallback的刪除服務(wù)構(gòu)造性控制問題Π′，如果有一個算法在運行時間O(g(k′)|I|O(1))內(nèi)可以解決該問題，則該問題稱為固定參數(shù)可解，其中k′為最多刪除服務(wù)的個數(shù)，g是任意函數(shù)，(I′，k′)是刪除服務(wù)構(gòu)造性控制問題的實例即利用Fallback的在線服務(wù)集S中服務(wù)的信譽度量.否則利用Fallback的刪除服務(wù)構(gòu)造性控制問題Π′被稱為固定參數(shù)不可解.

FPT-歸約：如果存在一種算法，可以在時間O(g(k)|I|O(1))內(nèi)，把k-支配集問題Π的實例(I，k)轉(zhuǎn)換為利用Fallback的刪除服務(wù)構(gòu)造性控制問題Π′的實例(I′，k′)，則k-支配集問題Π可FPT-歸約到刪除服務(wù)構(gòu)造性控制問題Π′.其中k為k-支配集的參數(shù)k，k′為最多刪除服務(wù)的個數(shù)，在定理1中k=k′，g是任意函數(shù).

定義13.參數(shù)化問題Π可FPT-歸約到WCNF-2SAT問題，那么稱Π屬于W[1]；參數(shù)化問題Π可FPT-歸約到WCS[t]問題，那么稱Π屬于W[t].WCS[2]問題是WCNF-2SAT問題的拓展.W[1]?W[2].一個問題如果是W[t]-hard問題，則被認為是固定參數(shù)不可解的.

即只需要找到一個已知的W[2]-complete問題k-支配集Π的實例可以轉(zhuǎn)換到利用Fallback的刪除服務(wù)構(gòu)造性控制問題Π′的實例則可證明該構(gòu)造性控制問題是W[2]-hard問題即固定參數(shù)不可解問題.

定理.利用Fallback的刪除服務(wù)構(gòu)造性控制問題是W[2]-hard問題.

證明：已知的W[2]-complete問題k-支配集問題：在一個無向圖G=(B，E)中，對于子集B′?B，若每一個節(jié)點bi，bi∈B′或鄰接B′中至少一個點，則稱子集B′為支配集.

給定k-支配集問題的實例I=(G，k)，其中G=(S1，E)，k

構(gòu)造利用Fallback的刪除服務(wù)構(gòu)造性控制問題的實例I′：給定用戶集U、服務(wù)集S，其中S=S1∪S2∪{sj}∪S3∪S4，sj是控制后信譽最高的服務(wù).

S2：S2是一組k+1個服務(wù)，這些服務(wù)防止刪除最多k個服務(wù)使服務(wù)sj成為唯一的信譽最高的服務(wù).

S4：S4是一組n(k+1)個服務(wù)，對于每個j，1≤j≤k+1，可以找到具有n個元素的子集S4j?S4，這些子集確保每個服務(wù)s2j∈S2總是位于表4的第2個偏好排序的第(n+k+1)個位置.

U是2n+1個用戶集合，因此n+1為絕對多數(shù)閾值.用戶集U中的用戶對服務(wù)集S中服務(wù)的偏好排序如表4所示.

表4 用戶-服務(wù)偏好排序表Table 4 User-service preference ranking sheet

服務(wù)的l級分數(shù)如表5所示：

表5 服務(wù)的l級分數(shù)表Table 5 Level l score of services sheet

證明實例I可以轉(zhuǎn)換到實例I′，即需要證明下面結(jié)果是成立的：實例I存在大小為k的支配集當且僅當實例I′中通過刪除k個服務(wù)使sj成為唯一的信譽最高的服務(wù)(這里k-支配集的參數(shù)k與最多刪除k個服務(wù)的k相同).

從右到左：假設(shè)sj可以通過刪除最多k個服務(wù)而成為唯一的信譽最高的服務(wù).由于除了sj之外(即S2中的服務(wù))，還有k+1個服務(wù)在第n+k+1級達到絕對多數(shù)，從S2中刪除k個服務(wù)不足以使sj成為最終的唯一的信譽最高的服務(wù).因此sj必須在低于或等于n+k級上才能成為唯一的信譽最高的服務(wù)，那么在表4中sj在第一個偏好排序中的排名至少向前一個位置才有可能，這說明k′≤k個被刪除的服務(wù)可能：

1.全被包含在S1中并且對應(yīng)G中的一個k′大小的支配集.

2.都在S1∪S3中.

證明過程表明已知的W[2]-complete問題k-支配集可以FPT-歸約到利用Fallback的刪除服務(wù)構(gòu)造性控制問題，因此利用Fallback的刪除服務(wù)的構(gòu)造性控制問題是W[2]-hard問題即該控制問題是固定參數(shù)不可解的，說明Fallback的刪除服務(wù)的構(gòu)造性控制問題的計算復雜性高.同理，要證明其余構(gòu)造性控制類型問題是NP-hard/W[2]-hard問題也可以通過找到已知的NP-complete/W[2]-complete問題歸約到控制問題來證明.

5 實驗結(jié)果及分析

為驗證Fallback的防控制性，設(shè)計實現(xiàn)相關(guān)實驗并對實驗結(jié)果進行分析.實驗環(huán)境為Intel Core i7 處理器，8G內(nèi)存，64位Windows 10操作系統(tǒng)，開發(fā)環(huán)境為pyCharm 2019.1，開發(fā)語言為 Python 3.7.

5.1 數(shù)據(jù)集

為了避免實驗的偏向性，使實驗更加真實和可靠，實驗同時采用合成數(shù)據(jù)集和真實數(shù)據(jù)集.合成數(shù)據(jù)集使用Mallows模型生成[27]；真實數(shù)據(jù)集為MovieLens數(shù)據(jù)集[28].

Mallows模型在序數(shù)偏好研究中被廣泛認可并應(yīng)用[27]，其合成的偏好數(shù)據(jù)集用ML表示.在Mallows模型中設(shè)置兩個參數(shù)：中心偏好序σ和離散參數(shù)θ.其中，σ為由m個在線服務(wù)構(gòu)成的完整偏好排序，離散參數(shù)θ用于控制合成的偏好序與中心偏好序σ的離散程度.本文隨機生成中心偏好序σ，離散參數(shù)θ設(shè)置為0.5，設(shè)置較大數(shù)量的用戶量n及在線服務(wù)量m，合成不同的偏好數(shù)據(jù)集.

MovieLens數(shù)據(jù)集在服務(wù)研究的相關(guān)領(lǐng)域內(nèi)得到普遍應(yīng)用[28]，該數(shù)據(jù)集包含了1682部電影，943個用戶，以及 100000 條左右的評分(1～5)，每個用戶至少對 20 部電影進行過評分，用MV表示.由于MV中用戶對服務(wù)的評分非常稀疏，首先采用協(xié)同過濾方法對評分進行填充，然后根據(jù)每個用戶對服務(wù)的評分進行排序，若評分相同則采用隨機法對其進行排序，最終獲得用戶-服務(wù)完整偏好排序.

5.2 防控制性實驗

為了在最容易控制的情況下測試各個方法的防控制性，實驗通過使用預先排序，找到控制的最優(yōu)策略.即對增加用戶構(gòu)造性控制來說，先增加將想控制服務(wù)排在最好位置的用戶；對刪除用戶構(gòu)造性控制來說，先刪除將想控制服務(wù)排在最差位置的用戶；對增加服務(wù)構(gòu)造性控制來說，先增加對想控制服務(wù)威脅最小的服務(wù)；對刪除服務(wù)構(gòu)造性控制來說，先刪除對想控制服務(wù)最具威脅的服務(wù).在最能滿足控制要求的情況下，測試控制成功所需的時間.控制成功所需的時間越長，說明方法的防操縱性越強.

Felix Brandt等指出Copeland方法是已知的第一個完全抵制所有類型的構(gòu)造性控制的方法[22]；Condorcet方法是控制用戶偏好問題研究的第1個方法，所以在Mallows模型中本文使用Copeland和Condorcet方法作為與Fallback的對比方法.基于Mallows模型的實驗對4種控制類型進行實驗，增加/刪除用戶的構(gòu)造性控制、增加/刪除服務(wù)的構(gòu)造性控制.

由于均值法(Average)易于理解并且被廣泛的應(yīng)用于在線服務(wù)信譽系統(tǒng)中[4]，所以在MovieLens數(shù)據(jù)集上的實驗對比方法除了Copeland和Condorcet方法之外多增加了均值法(Average).基于MovieLens數(shù)據(jù)集的實驗同樣對上述4種控制類型進行實驗.

在增加/刪除用戶或服務(wù)的場景中，設(shè)置增加/刪除用戶或服務(wù)的數(shù)量與初始用戶或服務(wù)的數(shù)量相同大小[9].

5.2.1 增加用戶和刪除用戶的構(gòu)造性控制

在增加用戶的構(gòu)造性控制中，實驗對新增用戶進行預排序，找到增加用戶的構(gòu)造性控制的最優(yōu)策略，在最易控制的情況下測試各個方法的防控制性.首先增加的用戶是將想控制的服務(wù)排在最好位置的用戶，最后增加的用戶是將服務(wù)排在最差位置的用戶.刪除用戶的預排序過程與增加用戶的預排序過程相反.由于ML數(shù)據(jù)集中的用戶直接提供對在線服務(wù)的偏好排序，而均值法需要根據(jù)用戶的評分信息得到服務(wù)的信譽，所以在基于ML數(shù)據(jù)集的實驗中未使用均值法(Average)作為對比方法.

基于ML數(shù)據(jù)集的增加用戶構(gòu)造性控制實驗?zāi)M了控制前的50-500個初始用戶、50-500個增加的干擾用戶和10個在線服務(wù).由于MV數(shù)據(jù)集的用戶總量為943個，基于MV數(shù)據(jù)集的增加用戶實驗?zāi)M了50-450個初始用戶、50-450個增加的干擾用戶和10個在線服務(wù)，兩個實驗增加用戶量與初始用戶量相同.實驗記錄Fallback方法及對比方法的控制成功所需的時間.ML增加用戶構(gòu)造性控制成功所需的時間如表6所示，MV控制成功所需的時間如圖1所示.

表6 ML數(shù)據(jù)集增加用戶構(gòu)造性控制時間表Table 6 Time of constructive control by adding users in ML data sets sheet

圖1 MV數(shù)據(jù)集增加用戶構(gòu)造性控制時間Fig.1 Time of constructive control by adding users in MV data sets

在刪除用戶的構(gòu)造性控制中，基于ML、MV的實驗?zāi)M了50-500個用戶和10個在線服務(wù)，最多可以刪除的用戶量與初始用戶量相同.ML刪除用戶構(gòu)造性控制成功所需的時間如表7所示，MV控制成功所需的時間如圖2所示.

表7 ML數(shù)據(jù)集刪除用戶構(gòu)造性控制時間表Table 7 Time of constructive control by deleting users in ML data sets sheet

由表6、表7、圖1、圖2可見，隨著增加的干擾用戶或刪除用戶的數(shù)量增加，F(xiàn)allback方法、Copeland方法、Condorcet方法、均值法(Average)的控制成功所需的時間均增加，F(xiàn)allback方法控制時間比另外3種方法更長，Copeland方法、Condorcet方法控制時間比較接近，均值法(Average)控制時間最短.對

圖2 MV數(shù)據(jù)集刪除用戶構(gòu)造性控制時間Fig.2 Time of constructive control by deleting users in MV data sets

于較大數(shù)量級的用戶來說，F(xiàn)allback方法的防控制性優(yōu)勢更明顯，通過增加用戶或刪除用戶的構(gòu)造性控制更為困難.

5.2.2 增加服務(wù)和刪除服務(wù)的構(gòu)造性控制

增加服務(wù)的構(gòu)造性控制中，實驗對新增服務(wù)進行預排序，找到增加服務(wù)的構(gòu)造性控制的最優(yōu)策略，預排序首先增加的第1個服務(wù)為：有最少的用戶將該服務(wù)排在想控制的服務(wù)之前；最后增加的服務(wù)為：有最多的用戶將該服務(wù)排在想控制的服務(wù)之前，即通過將服務(wù)升序排序之后，首先增加了對控制服務(wù)威脅最小的服務(wù)，找到了當前控制的最優(yōu)策略.刪除服務(wù)構(gòu)造性控制的預排序過程與增加服務(wù)構(gòu)造性控制的預排序過程相反，需要首先刪除對控制服務(wù)成為唯一贏家最具威脅的服務(wù).基于ML、MV數(shù)據(jù)集的增加服務(wù)構(gòu)造性控制實驗?zāi)M了控制前10-100個初始服務(wù)、10-100個增加的干擾服務(wù)和10個用戶，兩個數(shù)據(jù)集的實驗增加服務(wù)量與初始服務(wù)量相同.實驗記錄Fallback方法及對比方法的控制成功所需的時間.ML數(shù)據(jù)集增加服務(wù)構(gòu)造性控制成功所需時間如圖3所示，MV數(shù)據(jù)集控制成功所需時間如圖4所示.

圖3 ML數(shù)據(jù)集增加服務(wù)構(gòu)造性控制時間Fig.3 Time of constructive control by adding services in ML data sets

圖4 MV數(shù)據(jù)集增加服務(wù)構(gòu)造性控制時間Fig.4 Time of constructive control by adding services in MV data sets

刪除服務(wù)的構(gòu)造性控制中，基于ML、MV的實驗?zāi)M了10-100個服務(wù)和10個用戶.ML數(shù)據(jù)集刪除服務(wù)構(gòu)造性控制成功所需時間如圖5所示，MV數(shù)據(jù)集控制成功所需時間如圖6所示.

圖5 ML數(shù)據(jù)集刪除服務(wù)構(gòu)造性控制時間Fig.5 Time of constructive control by deleting services in ML data sets

圖6 MV數(shù)據(jù)集刪除服務(wù)構(gòu)造性控制時間Fig.6 Time of constructive control by deleting services in MV data sets

由圖3-圖6可見，隨著增加的干擾服務(wù)或刪除服務(wù)的數(shù)量增加，F(xiàn)allback方法控制成功所需的時間呈指數(shù)型增長，當服務(wù)數(shù)量達到70個以上時，與其他方法的對比更加明顯.Copeland方法、Condorcet方法控制成功時間比較接近，均值法(Average)控制成功時間最短.兩種數(shù)據(jù)集的實驗均表明，增加服務(wù)或刪除服務(wù)構(gòu)造性控制中，F(xiàn)allback方法控制成功所需的時間最長，F(xiàn)allback方法具有更強的防控制性.

6 結(jié) 語

本文提出了利用Fallback的在線服務(wù)信譽防控制機制，以解決信譽系統(tǒng)內(nèi)部能夠掌握用戶偏好的管理者的控制問題.該機制通過Fallback方法集結(jié)所有用戶的評分信息或偏好排序得到最終服務(wù)的信譽及用戶群體偏好，利用Fallback方法提高控制用戶偏好問題的計算復雜性，增加管理者的攻擊時間成本以達到防控制的目的，為在線服務(wù)的防控制提供了一種新的思路.理論分析表明了該方法的防控制性，實驗進一步驗證了該方法防控制的有效性.

本方法在增加或者刪除用戶、服務(wù)的控制類型中驗證了Fallback方法對指定服務(wù)的防控制性，但未對控制用戶群體偏好序的防控制性進行驗證.因此下一步的工作將針對各類控制的偏好序的防控制性進一步開展研究.