近幾年網路遊戲業快速地成長,有許廠商紛紛加入這個領域並且賺取了大量的收入。然而,玩家於遊戲中使用不法程式成為了網路遊戲業一個嚴重的問題。許多玩家使用外掛程式自動進行遊戲,這些玩家幾乎不用付出努力就能獲取大量的利益,這個情況嚴重影響到網路遊戲產業的發展。外掛程式是一種設計用來自動模仿玩家行為的程式,因此他們很難被分辨出來。至今為止,大多數的廠商利用人力資源來偵測外掛而不是使用電腦自動偵測,這造成遊戲商一個額外的支出。在此我們提出了一個偵測外掛的系統架構,並使用玩家路俓做為我們分辨普通玩家與外掛的資訊來源,我們嘗試從這些路俓萃取出一些有用的特性來幫助我們區分人類與外掛程式。為了儘可能取得較多的資訊,我們的前處理動作會產生一個維度較高的資料,所以我們引進流形技術來降低資料維度,我們將一個稱為等量特徵映射的降維演算法加入我們的架構中來達成降維的目的。經由這個演算法,原本資料在高維度時的結構特性在降至低維度後也能保存。我們的實驗結果顯示人類及外掛在很多情況下都能藉由他們的路徑來區分他們,因此我們有不錯的偵測準確率。

The online game industry grows explosively in recent years. Many entertainment companies invest in online game development and receive great profit. Unfortunately, players cheating in games has became a serious problem. Many players use game bots to gain rewards without paying too much effort. The game bots are designed to imitate human behavior. Thus they are diffcult to detect. Until now, most of the companies still detect bots by human identication instead of automatic machine detection. In this thesis, we propose a trajectory-based framework to detect game bots and apply manifold learning techniques in the framework. Using the trajectory data from a real life online game, we try to find some useful features from the original trajectory which can distinguish humans from bots. The data that we obtain are in a high dimensional space, so we apply a dimension reduction skill called Isomap to reduce the data dimension into a lower dimension. The structure of the data will be preserved in the new dimensional space. Our experiment results show that the bot trajectories can be distinguished from human trajectories very well in many cases, thus we can identify them in a high accuracy.

[1] Demo Squad. http://q2scene.net/ds/.
[2] GotFrag Quake. http://www.gotfrag.com/quake/home/.
[3] id Software, Inc. http://www.idsoftware.com/.
[4] In-stat. http://www.in-stat.com.
[5] Inca. http://eng.nprotect.com/index.html.
[6] Network and systems support for games (netgames 2008).
http://netgames2008.cs.wpi.edu/index.html.
[7] Planet Quake. http://planetquake.gamespy.com/.
[8] Pricewaterhousecoopers. http://www.pwc.com/.
[9] Revilla Quake Site. http://www.revilla.nildram.co.uk/demos-
full.htm.
[10] C. M. Bishop. Pattern Recognition and Machine Learning. Springer,
2006.
[11] J. Bruske and G. Sommer. Intrinsic dimensionality estimation with
optimally topology preserving maps. IEEE Trans. on Pattern Anal-
ysis and Machine Intelligence, 20(5):572{575, 1988.
[12] C. J. C. Burges. A tutorial on support vector machines for pattern
recognition. Data Mining and Knowledge Discovery, 2(2):121{167,
1998.
[13] F. Camastra and A. Vinciarelli. Estimating the intrinsic dimension of
data with a fractal-based method. IEEE Trans. on Pattern Analysis
and Machine Intelligence, 24(10):1404{1407, 2002.
[14] E. Castronova. Synthetic Worlds: The Business and Culture of On-
line Games. 2006.
[15] K. T. Chen, H. K. Kenneth Pao, and H. C. Chang. Game bot iden-
ti‾cation based on manifold learning. Network and Systems Support
for Games (NetGames 2008), 2008.
[16] A. L. Coates, H. S. Baird, and R. J. Faternan. Pessimal print: A
reverse turing test. In Proceedings of the International Conference
on Document Analysis and Recognition, LIX(236):1154{1159, 2001.
[17] C. Cortes and V. Vapnik. Support vector networks. Machine Learn-
ing, 20:273{297, 1995.
[18] J. Costa and A.O. Hero. Manifold learning using euclidean k-nearest
neighbor graphs. Proceedings of IEEE International Conference on
Acoustic Speech and Signal Processing, 4:988{991, 2004.
[19] T. Cox and M. Cox. Multidimensional scaling. Chapman & Hall,
London, 1994.
[20] N. Cristianini and J. Shawe-Taylor. An Introduction to Support Vec-
tor Machines. Cambridge University Press, 2000.
[21] V. de Silva and J. B. Tenenbaum. Global versus local methods in
nonlinear dimensionality reduction. Advances in Neural Information
Processing Systems, pages 705{712, 2003.
[22] D. Donoho and C. Grimes. Hessian eigenmaps: locally linear embed-
ding techniques for high dimensional data. Proc. of National Academy
of Sciences, 100:5591{5596, 2003.
[23] R. R. Feltrin. Eraser bot 1.01.
[24] R. A. Fisher. The use of multiple measurements in taxonomic prob-
lems. Annals of Eugenics, 7:179{188, 1936.
[25] D. Gibson, C. Aldrich, and M. Prensky. Game and Simulations inOn-
line Learning: Research and Frameworks. Information Science, USA,
2007.
[26] P. Golle and N. Ducheneaut. Preventing bots from playing online
games. Computers in Entertainment, 3(3):3{3, 2005.
[27] M. Hein and J. Y. Audibert. Intrinsic dimensionality estimation of
submanifolds in Rd. ACM International Conference Proceeding Se-
ries, 119:289{296, 2005.
[28] H. Hotelling. Analysis of a complex of statistical variables into prin-
cipal components. Journal of Educational Psychology, 24:417{441,
1933.
[29] F. W. Jamison. Security lock system. Technical Report 19, United
State Patent, 1979.
[30] M. C. Jeruchim, P. Balaban, and K. S. Shanmugan. Simulation
of Communication Systems: Modeling, Methodology and Techniques.
2000.
[31] jibe. ICE Bot 1.0, 1998. http://ice.planetquake.gamespy.com/.
[32] B. Kegl. Intrinsic dimension estimation using packing numbers. Ad-
vances in Neural Information Processing Systems 15. MIT Press,
2003.
[33] H. Kim, S. Hong, and J. Kim. Detection of auto programs for
MMORPGs. In Proceedings of AI 2005: Advances in Arti‾cial Intel-
ligence, pages 1281{1284, 2005.
[34] J. B. Kruskal. Multidimensional scaling by optimizing goodness of ‾t
to a nonmetric hypothesis. Psychometrika, 29:1{27, 1964.
[35] M. H. C. Law and A. K. Jain. Incremental nonlinear dimensionality
reduction by manifold learning. IEEE Trans. on Pattern Analysis
and Machine Intelligence, 28(3):377{391, 2006.
[36] Y.-J. Lee. Smooth support vector machine toolbox.
http://dmlab1.csie.ntust.edu.tw/downloads/SSVM Code.htm.
[37] Y. J. Lee and O. L. Mangasarian. Rsvm: Reduced support vector
machines. Proceedings of the First SIAM International Conference
on Data Mining, 2001.
[38] Y. J. Lee and O. L. Mangasarian. Ssvm: A smooth support vec-
tor machine. Computational Optimization and Applications, 20:5{22,
2001.
[39] E. Levina and P.J. Bickel. Maximum likelihood estimation of intrinsic
dimension. Advances in Neural Information Processing Systems, MIT
Press, 2005.
[40] K. C. Li. High Dimensional Data Analysis via the SIR/PHD Ap-
proach. 2000.
[41] K. C. Li. Sliced inverse regression for dimension reduction. Journal
of the American Statistical Association, 86:316{327, 2000.
[42] N. W. Lo, S. H. Chen, and F. C. Chang. Bot detection models and
corresponding game security processes in computer onlines. TANET,
2006.
[43] M. Malakhov. CR Bot 1.15, May 2000.
http://arton.cunst.net/quake/crbot/.
[44] T. M. Mitchell. Machine Learning. McGRAW-HILL International
Edition, 1997.
[45] J. Mulligan and B. Patrovsky. Developing Online Games: An In-
sider's Guide. New Riders, 2003.
[46] K. Pettis, A.K. Jain T. Bailey, and R. Dubes. An intrinsic dimen-
sionality estimator from near-neighbor information. IEEE Trans. on
Pattern Analysis and Machine Intelligence, 1(1):25{36, 1979.
[47] S. M. Ross. First Course in Probability Sheldon. 1997.
[48] S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by
locally linear embedding. Science, 290:2323{2326, 2000.
[49] S. T. Roweis and L. K. Saul. Think globally, ‾t locally: Unsupervised
learning of nonlinear manifolds. Technical report, Journal of Machine
Learning Research, 2003.
[50] B. SchÄolkopf and A. Smola. Learning with Kernels Support Vector
Machines, Regularization, Optimization and Beyond. MIT Press,
Cambridge, MA, USA, 2001.
[51] B. SchÄolkopf, A.J. Smola, and K.-R.MÄuller. Nonlinear component
analysis as a kernel eigenvalue problem. Technical Report 44, Max
Planck Institut, 1996.
[52] J. Shlens. A tutorial on principal component analysis. 2005.
[53] J. B. Tenenbaum. Mapping a manifold of perceptual observations. In
In Advances in Neural Information Processing Systems, volume 10,
pages 682{688, Cambridge, 1998. MIT Press.
[54] J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric
framework for nonlinear dimensionality reduction. Science, 290:2319{
2323, 2000.
[55] C. Thurau and C. Bauckhage. Tactical waypoint maps: Towards im-
itating tactics in fps games. In M. Merabti, N. Lee, and M.H. Over-
mars, editors, Proc. 3rd International Game Design and Technology
Workshop and Conference (GDTW'05), pages 140{144, 2005.
[56] C. Thurau and C. Bauckhage. Towards manifold learning for gamebot
behavior modeling. In In Proc. Int. Conf. on Advances in Computer
Entertainment Technolog (ACE'05), pages 446{449, 2005.
[57] C. Thurau, C. Bauckhage, and G. Sagerer. Learning human-like
movement behavior for computer games. In In Proc. 8th Int. Conf.
on the Simulation of Adaptive Behavior (SAB'04), pages 315{323.
IEEE Press, 2004.
[58] C. Thurau, C. Bauckhauge, and G. Sagerer. Combining self orga-
nizing maps and multilayer perceptrons to learn bot-behavior for a
commercial game. In Proceedings of the GAME-ON03 Conference,
pages 119{123, 2003.
[59] C. Thurau, T. Paczian, and C. Bauckhage. Is bayesian imitation
learning the route to believable gamebots? In In Proc. GAME-ON
North America, pages 3{9, 2005.
[60] A. M. Turing. Computing machinery and intelligence. MIND(the
Journal of the Mind Association), LIX(236):433{460, 1950.
[61] V. N. Vapnik. The Nature of Statistical Learning Theory. Springer,
1995.
[62] B. Woodcock. Mmogchart.com. http://www.mmogchart.com/.
[63] S. F. Yeung, J. C. S. Lui, J. Liu, and J. Yan. Detecting cheaters
for multiplayer games: theory, design and implementation. Con-
sumer Communications and Networking Conference, 2006. 3rd IEEE,
2:1178{1182, 2006.