一种基于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.