一種基于ELM的在線游戲外掛檢測方法

黃旭， 曾孟佳， 范婧， 高少文， 胡文軍

(1. 湖州師范學院 信息工程學院， 湖州 313000； 2. 浙江大學 控制科學與工程學院， 杭州 310027)

0 引言

大規模多用戶在線角色扮演游戲(Massively Multiuser Online Role-Playing Game，MMORPG)是目前大眾參與程度最廣的一類游戲。游戲公司為提高玩家興趣和沉浸度，會模擬真實生活場景創建一系列虛擬產品和虛擬交易[1]，通過這些虛擬行為來進一步增加游戲的魅力。同時，為了更進一步刺激玩家參與游戲，游戲公司往往同時開展虛擬裝備交易和兌換現實貨幣的業務。隨之而來的問題是有部分人為了追求高的虛擬貨幣獲得率，通過使用游戲外掛的方式達到快速積累財富的目的。游戲外掛是一種可以代替人類玩家參與游戲的計算機程序，這種程序能夠不間斷地完成游戲任務，并且具有目的性強、執行效率高等特點。這樣的做法使得游戲的趣味性降低，并且會打擊普通玩家參與游戲的熱情。為維護公平的游戲環境，游戲公司往往投入大量人力物力對游戲外掛進行辨認和標記，這對于游戲公司而言無疑是一種沉重的負擔。因而，尋求一種成本較低且易于實施的游戲外掛自動檢測方法是游戲公司的普遍需求。

研究者們在游戲外掛快速檢測方面進行了很多嘗試。A.R.Kang提出，游戲外掛的檢測方法可分為3類[2]，即客戶端的自動完備圖靈測試、網絡端的擁堵分析和服務端的用戶行為、移動路徑、人類觀察證明分析等。客戶端的游戲外掛檢測方法通過增加一些與用戶的交互性問題來實現，這些問題對人類用戶來說是很容易的，但是游戲外掛卻無法回答。該方法的檢測效果很好，但是需要中斷游戲去回答問題，會帶來玩家沉浸感的大幅度降低[3]。文獻[4、5]證明可以通過分析人類玩家和游戲外掛造成的不同網絡擁堵狀況對他們進行分辨，但是這種方法的分辨精度較低。服務端的檢測方法能夠克服上訴的客戶端和網絡端檢測方法的缺點，其思想是通過大量學習分析玩家在游戲過程中生成的標簽數據，獲得其重要行為特征，進而通過分析行為特征以達到分辨真實玩家和游戲外掛的目的。服務端的具體方法有機器學習、用戶行為分析、任務分析等等。Thawonmas等人提出了一種使用不同行為序列對人類玩家和游戲外掛進行區分的方法[6]。文獻[7]指出空閑時間和活躍時間也是一個用戶特征。Mitterhofer[8]等人通過游戲中移動序列的重復模式對游戲外掛進行識別。文獻[9]通過對游戲外掛和人類玩家在移動角度上的頻率差別進行測試來識別游戲外掛。文獻[10-11]提出可以通過對單擊、鼠標移動、鼠標拖拽和釋放等事件信息對游戲外掛進行檢測。楊丹[12]等提出通過構建用戶數據模型達到游戲反外掛的目的。

研究者們在使用服務端的游戲外掛檢測方法中做了很多努力，但是當使用自動的機器學習工具對數據進行分析時，由于游戲外掛檢測問題涉及到的數據間差別很細微，且維度高、結構復雜、數量大，所以實施起來難度很大[13]。本文提出一種基于極限學習機(Extreme Learning Machine，ELM)[14]的在線游戲外掛檢測方法，通過對游戲日志數據的分析，獲取游戲外掛特征，從而實現游戲外掛識別。后續實驗中將這種方法的識別效果與傳統的諸如SVR、KNN方法進行了對比。

2 ELM算法

極限學習機是一種快速單隱層前饋神經網絡訓練算法[15]，在確保正確率的前提下它比傳統神經網絡速度更快一些[16]。傳統的神經網絡學習算法(如BP算法)需要人為設置大量的網絡訓練參數，并且很容易陷入局部最優解。極限學習機只需要設置網絡的隱層節點個數，在算法執行過程中不需要調整網絡的輸入權值以及隱含層單元的偏置，并且產生唯一的最優解，因此具有學習速度快、泛化性能好等優點。

ELM的學習過程包括兩個步驟：(1) 隨機特征映射：ELM隨機產生輸入權值和初始化隱含層單元偏置，并用非線性映射函數將輸入向量映射到特征空間；(2) 線性參數求解：利用ELM模型對輸出進行求解。

對于一個有N個任意樣本(Xi,ti)的數據集，(Xi,ti)滿足Xi=[xi1,xi2,…,xin]T∈Rn，ti=[ti1,ti2,…,tin]T∈Rm和L個隱層節點，激活函數為g(x)的單隱層神經網絡可以被描述為式(1)。

(1)

Wi=[wi1,wi2,…,win]T是輸入權值向量，β=[β1,β2,…,βL]T是L個隱層節點和輸出節點之間的輸出權值向量，b=[b1,b2,…,bL]T是隱含層的偏置向量，bi是隱層單元i的偏置。Wi·Xj是Wi和Xj的內積。

則ELM算法結構如圖1所示。

圖1 ELM算法結構圖

式(1)的矩陣表達式為式(2)。

Hβ=T

(2)

H是隱層節點的輸出，β是輸出權重，T是期望輸出。

式(2)中，

ELM的訓練目標是使輸出誤差最小，即式(3)。

(3)

也即對βi、Wi和bi有式(4)

(4)

i=1,…,L

(5)

等價于優化損失函數式(6)。

(6)

在ELM算法中，輸入權重Wi和隱含層的偏置bi是在訓練時隨機選擇的。當激發函數無限可微，隱含層節點數目足夠多時，ELM可逼近任何連續函數。根據Wi和bi的值可計算得到唯一確定的輸出矩陣H，則訓練單隱層神經網絡被轉化為求解一個線性系統Hβ=T的最小二乘解獲得，其解為，

式中，H+為輸出矩陣H的廣義逆矩陣。則ELM學習算法主要由以下步驟實現：

(1) 確定隱含層單元個數，隨機生成輸入權值Wi和隱含層偏置bi；

(2) 選取一個無限可微的函數作為隱含層單元的激發函數，求出輸出矩陣H；

(3) 根據輸出矩陣H計算輸出權值βi；

(4) 根據式(4)求出輸出tj。

此外，ELM被廣泛用于聚類[17]，特征選擇[18]和其他領域。

3 基于ELM的檢測方案

本文收集了網易提供的一款熱門游戲中超過3億條日志數據，希望通過ELM算法對單隱層神經網絡進行訓練能實現準確識別游戲外掛的目標。在本文的實驗中，激發函數g(x)可以選擇“Sigmoid”、“Sine”或“Hardlim”等函數。實驗步驟如下：(1) 對用戶的行為標簽信息根據時間段進行分組，以一天24小時為觀測單位，小時為分組單位，用戶一天的行為被分成24個組；(2) 對每組行為的再現頻率進行計算；(3) 根據再現頻率在時間序列上的分布和用戶在某個時間段的當前等級建立用戶的特征描述，從而形成用戶行為在時間上的行為矩陣。該矩陣可以被描述為，

這里將采集來的用戶行為和等級數據投射到時間軸上，選取了一定量的普通用戶和游戲外掛數據進行觀測，觀測結果如圖2和圖3所示。

圖2 等級變化趨勢

圖3 行為頻度變化趨勢

等級-時間曲線顯示用戶的信息更新情況，行為-時間曲線顯示用戶行為在時間上的變化規律。從圖2等級-時間曲線上可以看到，普通用戶的升級曲線平滑，而游戲外掛的升級曲線陡峭；在前期普通用戶的升級速度較快但是到后期由于升級難度大所以升級速度緩慢，而游戲外掛從時間上看幾乎保持勻速的升級速度。從圖2行為-時間曲線上可以看到，普通用戶的行為頻率低且變化曲線平滑，一天中會出現比較明顯的峰谷和峰頂；而對于游戲外掛，賺錢行為再現頻率很高，一天內基本一直處于非常活躍的狀態，谷頂現象不明顯。基于上訴討論，可以明顯發現普通用戶和游戲外掛在行為模式上存在很大不同，因此可以通過分析行為在時間上的再現頻率對他們進行區分。

研究用戶行為的再現頻率有兩種方法：

(1) 選擇矩陣Log所有行中關于f(aij)的所有元素，并將它們映射成一個N維向量，

LLINE=[(l1,f(ax11)),…,(li,f(axii)),…,(lN,f(axNN))]

這里的f(aij)是{f(a1i),…,f(aKi)}的最大值，其中xi∈{1,…,K}。這種方法檢測的是某種行為的最高再現頻率。

(2) 將矩陣Log的所有行序列化為一個K×N維的向量，

LALL=[(l1,f(a11)),…,(lN,f(a1N)),…,(l1,f(aK1)),…,(lN,f(aKN))]

這種方法包含了調查范圍的所有行為序列，能夠得到更廣泛的信息表達，但是以這種方式作為輸入在訓練時需要花費更多的計算時間。

結合ELM算法結構，N維向量LLINE或K×N維向量LALL被分別當做輸入向量，記為L。則游戲外掛檢測問題即是一個二分類問題，游戲外掛檢測的ELM模型可以被描述為，

這里，

gi(x)=G(ai,bi,x),ai∈Rd,bi∈R,oj=[oi1,oi2]T

實驗過程如下：(1) 分析游戲標簽數據，對用戶行為序列在時間上進行分組，計算其每組再現頻率；(2) 結合用戶行為、等級、時間信息，序列化成用戶標簽信息矩陣；(3) 確定ELM模型參數，使用用戶標簽信息矩陣對單隱層前饋神經網絡進行訓練；(4) 使用訓練好的ELM對測試數據進行普通用戶和游戲外掛的分類檢測；(5) 將同樣的數據集使用SVM和KNN進行分類，與ELM分類結果做對比分析。實驗處理過程如圖4所示。

圖4 實驗處理過程

通過上述實驗過程，一方面，ELM模型參數被求解和優化，縱向上實現了針對游戲中的外掛和普通用戶的分類；另一方面，將ELM算法的識別效果與傳統SVM、KNN方法進行了橫向的對比。

4 實驗結果分析

本文采用網易提供的新倩女幽魂日志數據約460G，包含了3 785 522 567種事件和38 793個有效玩家帳號。算法的實驗環境配置為i5-2450M 2.50 GHz CPU、16G內存、操作系統為Ubuntu 14.04，程序使用C語言編寫。

為了證明算法效果，實驗中隨機的從前期分析數據中選取了1 000、10 000和100 000條數據作為不同規模的測試數據。這里主要檢測用戶行為的再現頻率，前部分所述的最大值和所有值的兩種方法均被用于實驗。實驗結果如圖5所示。

(a)(b)

(c)(d)

圖5 實驗結果

其中圖5(a)、(b)是采用最大值的情況下，行為識別與用戶識別的結果；圖5(c)、(d)是在采用全部值的情況下，行為識別與用戶識別的結果。數據分別對比了不同數據規模、不同算法的執行情況。實驗結果表明，在目標較少的時候3種算法均表現良好。然而，當目標數增多以后，ELM算法的優點突顯出來。在同一時間段相同目標條件下，使用所有數據的實驗結果優于使用最大值的實驗結果。該結果表明ELM算法在數據量大和參數多的情況下的分類效果更出色。從圖5可知，KNN算法的表現在3種算法中最差，可能的原因是選擇的相似計算函數未能充分發揮KNN算法的效能。下一步，將在相似函數選擇方面做進一步研究。

5 總結

游戲公司采用人工進行游戲外掛檢測的方法存在效率低下、識別錯誤率高、成本高等問題，本文提出將ELM算法用于游戲外掛自動檢測，通過進行對數據做標簽、分類、計算、訓練、測試等步驟實現了ELM算法對游戲外掛的自動檢測。從實驗結果來看，ELM算法能夠用于游戲外掛檢測，且識別效率高、錯誤率較低。在與傳統的SVM、KNN方法對比發現，ELM的識別率更高。下一步，將在ELM平行化和促進識別效率方面做進一步研究。

[1] Jehwan Oh, Zoheb Hassan Borbora, Dhruv Sharma, et al. Bot Detection based on Social Interactions in MMORPGs[C]. International Conference on Social Computing, 2013, 10 (1) :536-543.

[2] Ah Reum Kang, Jiyoung Woo, Juyong Park, et al. Online game bot detection based on party-play log analysis[J]. Computers and Mathematics with Applications, 2013, 65(9): 1384-1395.

[3] Thomas P. Novak, Donna L. Hoffman, Adam Duhachek. The influence of gloal-directed and experiential activities on online flow experiences[J]. Journal of Consumer Psychology, 2003, 13(1-2) : 3-16.

[4] Sylvain Hilaire, Hyun-chul Kim, Chong-kwon Kim. How to deal with bot scum in MMORPGs[C]. IEEE International Workshop Technical Committee on Communications Quality and Reliability, 2010: 1-6.

[5] Kuan-Ta Chen, Jhih-Wei Jiang, Polly Huang, et al. Identifying MMORPG bots: A traffic analysis approach[J]. EURASIP Journal on Advances in Signal Processing, 2008, 2009: 797159. https://doi.org/10.1155/2009/ 797159

[6] Ruck Thawonmas, Yoshitaka Kashifuji, Kuan-Ta Chen. Detection of MMORPG bots based on behavior analysis[J]. International Conference on Advances in Computer Entertainment Technology, 2008, 34(6): 91-94.

[7] Kuan-Ta Chen Li-Wen Hong. User indentification based on game-play activity patterns[J]. Workshop on Network and System Support for Games, 2007: 7-12.

[8] Stefan Mitterhofer, Christopher Krügel, Engin Kirda. Server-side bot detection in massively multiplayer online games[J]. IEEE Security & Privacy, 2009, 7(3): 29-36.

[9] Marlieke van Kesteren, Jurriaan Langevoort, Franc Grootjen. A step in the right direction: Bot detection in mmorpgs using movement analysis[J]. In Proc. of the 21st BelgianDutch Conference on Artificial Intelligence (BNAIC 2009), 2009,7(3):29-36.

[10] Hyungil Kim, Sungwoo Hong, Juntae Kim. Detection of auto programs for MMORPGs[J]. Australian Joint Conference on Artificial Intelligence, 2005, 3089: 1281-1284.

[11] Steven Gianvecchio, Zhenyu Wu, Mengjun Xie, et al. Battle of botcraft: fighting bots in online games with human observational proofs[J]. Proceedings of the 16th ACM conference on Computer and communications security, 2009: 256-268.

[12] 楊丹，高員，顧欣，等. 基于用戶數據分析的網頁游戲反外掛方法[J]. 電子產品可靠性與環境試驗, 2015, 33(4):25-31.

[13] YeonJun Choi, SungJune Chang, YongJun Kim, et al. Detecting and monitoring game bots based on large-scale user-behavior log data analysis in multiplayer online games. The Journal of Supercomputing, 2016, 72(9): 3572-3587.

[14] Gao Huang, Guang-Bin Huang, Shiji Song, and Keyou You. Trends in Extreme Learning Machines: A Review. Neural Networks, 2015, 61: 32-48.

[15] Guang-Bin Huang, Qin-Yu Zhu, Chee-Kheong Siew. Extreme learning machine: theory and application [J]. Neurocomputing, 2006, 70(1-3): 489-501.

[16] Gao Huang, Shiji Song, Jatinder N. D. Gupta, Cheng Wu. Semi-Supervised and Unsupervised Extreme Learning Machines[J]. IEEE Transactions on Cybernetics, 2014, 44(12): 2405-2417.

[17] Qing He, Xin Jin, Changying Du, Fuzhen Zhuang, Zhongzhi Shi. Clustering in extreme learning machine feature space[J]. Neurocomputing, 2014, 128: 88-95.

[18] Guang-Bin Huang. An Insight into Extreme Learning Machines: Random Neurons, Random Features and Kernels[J]. Cognitive Computation, 2014, 6(3): 376-390.