NIPS 2018 | 南大周志華等人提出無組織惡意攻擊檢測演算法UMA
網際網路的繁榮使得線上活動早已成為我們日常生活中一個必不可少的部分，例如，越來越多的客戶更喜歡使用Amazon和 eBay 購物；很多人在 Youtube 和 Netflix 上觀看各種各樣的電影和電視節目。由於內容和使用者的數量都在急劇增長，有效地推薦合適的產品是很有挑戰性的工作。因此，各種各樣的協同過濾技術被開發用於形形色色的系統，以幫助客戶在一眾內容中選擇他們最喜愛的產品（Li et al., 2009; Bresler et al., 2014; Rao et al., 2015）。
很多協同過濾方法無力應對垃圾郵件製造者和排名操縱（Ling et al., 2013; Gunes et al., 2014），攻擊者可能會向 user-item 評分矩陣中插入虛假的評分來使系統產生偏差。一些攻擊者可能會增加他們內容的流行度（push attack，推攻擊），一些攻擊者則可能會減少競品的流行度（nuke attack，核攻擊）。大多數攻擊檢測研究聚焦於託攻擊（shilling attack），並且在多種託攻擊策略上表現出了較好的檢測效能 (Mehta, 2007; Hurley et al., 2009; Ling et al., 2013)。他們認為所有的攻擊都在使用同樣的策略使某個特定的條目升級或者降級。例如，某個攻擊組織者可能會生成數百個虛假使用者資料，在這種策略中，每個假使用者會給最流行的電影給出高分評價，而給要降級的目標電影給出低分評價。
各種各樣切實可行的技術被開發用於控制託攻擊，例如，網站註冊需要實名和電話號碼認證；驗證碼被用於確定某個響應是否由機器人生成；客戶在購物網站上購買了某個產品之後才能進行評價。基於這些方法，傳統的託攻擊可能面臨比較高昂的代價。例如，Amazon等電商網站上的小型線上零售商可能不太願意生成百上千個虛假客戶來實現一次託攻擊。
這篇論文研究了一種新型攻擊模型——無組織惡意攻擊（unorganized malicious attack），攻擊者在沒有任何組織者的情況下單獨使用少量的使用者資料來攻擊目標。這種攻擊型別在很多實際應用中都有發生，例如，Amazon上的線上商店可能會製造一些虛假評價，降低其競品高質量鞋子的評分；作家可能會僱傭幾個讀者給他們的低質量書籍打好評。實際證明這種少數的無組織惡意攻擊會嚴重地影響系統，例如，首次惡意差評能夠將賣家的銷量較低 13% (Luca, 2016)。
研究者先將無組織惡意攻擊公式化為矩陣補全問題的變體。X 代表沒有噪聲和攻擊的真實評價矩陣，該矩陣是低秩矩陣，因為使用者的偏好會受多個因素的影響 (Salakhutdinov et al., 2007)。讓 Y 代表稀疏攻擊評分矩陣，Z 代表噪聲矩陣。我們可以觀察到一個（部分）矩陣 M = X + Y + Z。據我們所知，之前的研究工作沒有對攻擊檢測做出類似的公式化闡述。本研究中的優化問題和魯棒 PCA 之間的主要區別是：魯棒 PCA 主要聚焦於從完全或者不完全矩陣中恢復低秩矩陣 X，本研究則更注重從微弱擾動的噪聲項 Z 中區分稀疏攻擊項 Y。
理論上，本研究證明了低秩評價矩陣 X 和稀疏矩陣 Y 可以在一些經典的矩陣補全假設下恢復。本研究提出了無組織惡意攻擊檢測演算法（UMA），可以看作是一種近似交替分裂增廣拉格朗日（proximal alternating splitting augmented Lagrangian）方法。研究者開發了一些新技術，證明該方法在全域性收斂的最糟糕的情況下也具有 O(1/t) 的收斂速度。實驗結果證明了該演算法的有效性，且優於當前最優的攻擊檢測方法。
論文：Unorganized Malicious Attacks Detection
論文連結：https://arxiv.org/pdf/1610.04086.pdf
摘要：過去十年，推薦系統吸引了很多關注。人們開發了許多攻擊檢測演算法來提供更好的推薦，這些演算法大多數聚焦於託攻擊，在託攻擊中，攻擊組織者生成大量的使用者資料，通過同樣的策略來升級或者降級某個商品。本研究考慮了一種不同的攻擊型別：無組織惡意攻擊。在這種攻擊中，攻擊者在沒有組織者的情況下單獨使用少量的使用者資料來攻擊不同的目標。儘管這種無組織惡意攻擊發生在很多實際應用中，但是相關的研究仍然是一個開放性問題。我們首次將無組織惡意攻擊公式化地闡述為一個矩陣補全問題，並且提出了無組織惡意攻擊檢測演算法（UMA），這是一種近似交替分裂增廣拉格朗日方法。我們分別在理論上和實驗中驗證了該方法的有效性。
UMA 演算法：
實驗
表 1：在結合了傳統策略的無組織惡意攻擊下，UMA 與其他演算法在資料集 MovieLens 100K 和 MovieLens 1M 上的檢測查準率、查全率以及 F1 得分對比。
表 2：在一般無組織惡意攻擊下，UMA 和其他演算法在資料集 MovieLens 100K 和 MovieLens 1M 上的檢測查準率、查全率和 F1 得分對比。
表 3：UMA 與其他演算法在 Douban 10K 上的檢測查準率，查全率以及 F1 得分對比。