跳到主要內容

臺灣博碩士論文加值系統

(100.26.196.222) 您好!臺灣時間:2024/03/02 22:48
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:徐健智
研究生(外文):Chien-Chih Hsu
論文名稱:網路桌面遊戲之模式與系統設計
論文名稱(外文):On the Model and System Design for Online Tabletop Games
指導教授:吳毅成
指導教授(外文):I-Chen Wu
學位類別:博士
校院名稱:國立交通大學
系所名稱:資訊科學與工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:英文
論文頁數:92
中文關鍵詞:桌面遊戲遊戲模式化事件驅動程式設計軟體框架
外文關鍵詞:Tabletop gamesGame modelingEvent-driven programmingFramework
相關次數:
  • 被引用被引用:0
  • 點閱點閱:437
  • 評分評分:
  • 下載下載:47
  • 收藏至我的研究室書目清單書目收藏:5
網路桌面遊戲,如西洋棋、圍棋、橋牌、麻將等,在Internet上十分受歡迎。許多桌面遊戲擁有相同的特性,如玩家圍坐在桌子旁,使用撲克牌之類的小物體來玩遊戲。由於桌面遊戲普及性及相似性,讓我們想研究如何加速網路桌面遊戲的發展。根據桌面遊戲的相同特性,我們設計兩個模式。第一個模式允許玩家在一個虛擬的大廳中邀請朋友一起玩遊戲。第二個模式則是為桌面遊戲定義了物件、狀態、以及遊戲的動作。根據這兩個模式,我們設計並實作了了一套網路桌面遊戲發展系統。這個系統的功能包括了網路通訊功能,玩家及遊戲伺服器管理,以及專為桌面遊戲提供的圖形介面支援等等。
在實作的過程中,我們遇到了兩個會造成我們的系統服務暫停或中止的問題。第一個問題是某些對網路讀寫資料的動作可能會造成遊戲伺服器暫時停止運作。第二個問題是當緩衝區溢位 (buffer overflow) 這種錯誤發生時,會讓整個遊戲伺服器程式被破壞,無法繼續提供服務。我們深入研究了這兩個問題並在本論文中提出了我們的解決方法。我們的研究成果可以讓遊戲伺服器程式避免被上述那兩個問題干擾,而能夠正確地持續提供服務。
實際上在台灣和香港已經有數個遊戲網站採用我們的系統。近年來,這些遊戲網站已經擁有超過百萬的會員,而最高的同時上線玩遊戲人數,也屢次超過了一萬人,足以說明我們的系統的實用性及穩定性。
Online tabletop games, such as Chess, Go, Bridge, Mahjong, etc, are popular in the Internet. Many online tabletop games share the same characteristics, e.g., players play around tables using physical objects such as cards. Due to the popularity and similarity of tabletop games, we are motivated to facilitate the development of online tabletop games. We design two models for online tabletop games according to the shared characteristics. The first model allows players to invite friends to play games together in a virtual room. The second model defines game objects, game states, and playing operations for tabletop games. Based on the two models, we design and implement a system for developing online tabletop games. The functionalities of the game system include network communication, player management, game server management, and graphical support for online tabletop games.
While implementing the game system practically, we encounter two issues on which the services of our system for online tabletop games are blocked or disrupted. The first issue is that some network I/O operations may block servers in our system unexpectedly for a long time. The second issue is that buffer overflow failures may crash servers in our system and therefore disrupt the services. In this dissertation we propose solutions to the two issues respectively so that our game system can support services smoothly and correctly without suffering form the two issues.
In practice, our game system has been used in some commercial game sites in Taiwan and Hong-Kong. These game sites have attracted more than one million people to register as members and have supported up to 10,000 concurrent players.
摘  要 I
ABSTRACT III
誌  謝 V
CONTENTS VII
LIST OF FIGURES IX
CHAPTER 1 INTRODUCTION 1
1.1 BACKGROUND 1
1.2 MOTIVATION 3
1.3 ORGANIZATION OF DISSERTATION 6
CHAPTER 2 MODELS FOR TABLETOP GAMES 7
2.1 THE GROUPED ONLINE TABLETOP GAME (GOTG) MODEL 7
2.2 THE TABLETOP GAME (TG) MODEL 9
2.2.1 The Simplified Tabletop Game (STG) Model 9
2.2.2 The General TG Model 17
CHAPTER 3 THE DESIGN AND IMPLEMENTATION OF THE GOTG SYSTEM 21
3.1 THE BASIC FUNCTIONALITIES OF THE GOTG SYSTEM 21
3.2 THE SPECIFIC SUPPORT FOR TABLETOP GAMES 25
3.3 A GOBANG BASED ON THE TG FRAMEWORK 27
3.4 AN UNIVERSAL TABLETOP GAME SYSTEM 31
CHAPTER 4 RELATED ISSUE 1: RESOLVING PROBLEMS OF BLOCKING I/O OPERATIONS FOR SERVER PROGRAMMING 35
4.1 SERVER PROGRAMMING FOR INTER-USER COMMUNICATION 35
4.2 THE EVENT-DRIVEN PROGRAMMING MODEL 38
4.3 OUTPUT BLOCKING PROBLEM AND SOLUTION 40
4.3.1 Output Blocking Problem 41
4.3.2 Solution to the Output Blocking Problem 41
4.4 REQUEST BLOCKING PROBLEM AND SOLUTION 45
4.4.1 Request Blocking Problem 45
4.4.2 Solutions for HTTP Access Requests 47
4.4.3 Solutions for Other Service Requests 50
4.5 EXPERIMENTS 55
CHAPTER 5 RELATED ISSUE 2: FAST RECOVERY FROM OVERFLOW FAILURES FOR NON-DISRUPTIVE GAME SERVICES 59
5.1 THE BUFFER OVERFLOW PROBLEM 59
5.2 THE DESIGN AND IMPLEMENTATION OF BODAR 61
5.2.1 Integration of Address Space Permutation and Trapping OOB by Unallocated Address Space 61
5.2.2 Guarding Buffers with Addresses within Unallocated Regions 63
5.2.3 Faulty Address Resolution 65
5.2.4 Source Code Transformation for the Guarded OOB Instrument 66
5.3 RESULTS 68
5.3.1 Stack Buffer Allocation Overhead 68
5.3.2 Security Tolerance and Availability Evaluation 69
5.3.3 Efficiency Evaluation 71
5.4 DISCUSSIONS 75
5.4.1 The Utilizable Virtual Address Space 75
5.4.2 Limitations 77
CHAPTER 6 CONCLUSION 79
6.1 SUMMARY OF CONTRIBUTIONS 79
6.2 FUTURE WORK 83
6.2.1 The Improvements on the GOTG System 83
6.2.2 GAML and History Authoring Systems 84
6.2.3 The Improvement on BODAR 84
REFERENCES 87
[1] ACME Laboratories. thttpd. http://www.acme.com/software/thttpd/ (last access: May 2005).
[2] T. Austin, S. Breach and G. Sohi. "Efficient detection of all pointer and array access errors." In Proceedings of the ACM SIGPLAN'94 Conference on Programming Language Design and Implementation, June 2004.
[3] I. Baldine. Divert Sockets mini-HOWTO. http://www.faqs.org/docs/Linux-mini/Divert-Sockets-mini-HOWTO.html (last access: April 2006).
[4] S. Bao. XQFtoAny. http://www.hgchess.com/ReadNews.asp?NewsID=355 (last access: May 2006).
[5] A. Baratloo, N. Singh and T. Tsai. "Transparent Run-Time Defense against Stack-Smashing Attacks." In Proceedings of the 2000 USENIX Annual Technical Conference (USENIX-00), pp. 251, June 2000.
[6] Beyond Security. SecuriTeam. http://www.securiteam.com/ (last access: May 2006).
[7] S. Bhatkar, D.C. DuVarney and R. Sekar. "Address Obfuscation: An Efficient Approach to Combat A Broad Range of Memory Error Exploits." In USENIX Security Symposium, pp. 105-120, August 2003.
[8] BioWare. Baldur's Gate. http://www.bioware.com/games/baldurs_gate/ (last access: May 2006).
[9] Blizzard Entertainment Inc. Blizzard Entertainment – Warcraft III. http://www.blizzard.com/war3/ (last access: April 2006).
[10] Blizzard Entertainment Inc. Diablo II. http://www.blizzard.com/diablo2/ (last access: May 2006).
[11] M. Boland. Mathopd. http://www.mathopd.org/ (last access: April 2006).
[12] G. Booch, I. Jacobson and J. Rumbaugh. The Unified Modeling Language User Guide. Addison-Wesley, Massachusetts, 1998.
[13] A. Chankhunthod, P.B. Danzig, C. Neerdaels, M.F. Schwartz and K.J. Worrell. "A Hierarchical Internet Object Cache." In Proceedings of the 1996 USENIX Technical Conference, San Diego, California, USA, pp. 153-163, 1996.
[14] M. Chew and D. Song. "Mitigating buffer overflows by operating system randomization." Technical Report CMU-CS-02-197, Carnegie Mellon University, December 2002.
[15] T.C. Chiueh and F.H. Hsu. "Rad: A compile-time solution to buffer overflow attacks." In 21st International Conference on Distributed Computing, Phoenix, Arizona, USA, pp. 409, 2001.
[16] Chunghwa Telecom. HiNet Game Zone. http://games.hinet.net/ (last access: May 2006).
[17] A. Cobbs. Divert. http://www.freebsd.org/cgi/man.cgi?query=divert (last access: April 2006).
[18] D.E. Comer. Internetworking with TCP/IP Vol. 1: Principles, Protocols, and Architecture, Forth Edition. Prentice Hall, New Jersey, 2000.
[19] D.E. Comer and D.L. Stevens. Internetworking with TCP/IP Vol. 3: Client-Server Programming and Applications – BSD Socket Version, Second Edition. Prentice Hall, New Jersey, 1996.
[20] C. Cowan, C. Pu, D. Maier, H. Hinton, J. Walpole, P. Bakke, S. Beattie, A. Grier, P. Wagle and Q. Zhang. "StackGuard: Automatic adaptive detection and prevention of buffer overflow attacks." In Proceedings of the 7th USENIX Security Symposium, pp. 63-78, January 1998.
[21] C. Dahn and S. Mancoridis. "Using Program Transformation to Secure C Programs Against Buffer Overflows." In IEEE Proceedings of the 2003 Working Conference in Reverse Engineering (WCRE'03), British Columbia, Canada, pp. 323-332, November 2003.
[22] Electric Arts Inc. ORIGIN – Ultima Online. http://www.uo.com/ (last access: April 2006).
[23] H. Etoh and K. Yoda. Protecting from Stack-Smashing Attacks. http://www.trl.ibm.com/projects/security/ssp/main.html (last access: January 2006).
[24] FICS. Free Internet Chess Server. http://www.freechess.org/ (last access: April 2006).
[25] Firaxis Games. Civilization IV. http://www.2kgames.com/civ4/home.htm (last access: May 2006).
[26] M. Fisher, J. Ellis and J. Bruce. JDBC API Tutorial and Reference, Third Edition. Addison-Wesley, New Jersey, 2003.
[27] S. Forrest, A. Somayaji and D.H. Ackley. "Building diverse computer systems." In 6th Workshop on Hot Topics in Operating Systems, Los Alamitos, CA, USA, pp. 67-72, 1997.
[28] J. Foster, M. Fahndrich and A. Aiken. "A theory of type qualifiers." In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), May 1999.
[29] E. Gamma, R. Helm, R. Johnson and J. Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, Massachusetts, 1995.
[30] GigaMedia. FunTown. http://www.funtown.com.tw/ (last access: May 2006).
[31] R. Hastings and B. Joyce. "Purify: A tool for detecting memory leaks and access errors in C and C++." In Proceedings of the Winter USENIX Conference, pp. 125-138, January 1992.
[32] A. Hollosi. SGF File Format. http://www.red-bean.com/sgf/ (last access: May 2006).
[33] IBM. DeepBlue. http://www.research.ibm.com/deepblue/ (last access: May 2006).
[34] id Software. DOOM 3. http://www.doom3.com/ (last access: May 2006).
[35] Institute for Information Industry. View Point of MIC. http://mic.iii.org.tw/pop/micnews2_op_new.asp?sno=110&cred=2005/7/8 (last access: May 2006).
[36] T. Jim, G. Morrisett, D. Grossman, M. Hicks, J. Cheney and Y. Wang. "Cyclone: Asafe dialect of C." In Proceedings of the USENIX Annual Technical Conference, pp. 275-288, June 2002.
[37] R. Jones and P. Kelly. "Backwards-compatible bounds checking for arrays and pointers in C programs." In Third International Workshop on Automated Debugging, May 1997.
[38] S.C. Kendall. "Bcc: run-time checking for c programs." In Proceedings of the USENIX Summer Conference, 1983.
[39] A. Kirmse, "A Network Protocol for Online Games," in Game Programming Gems, M.A. DeLoura Ed. Massachusetts: Charles River Media, INC., 2000, pp. 104-108.
[40] D. Larochelle and D. Evans. "Statically Detecting Likely Buffer Overflow Vulnerabilities." In Proceedings of the 10th USENIX Security Symposium, pp. 177-190, August 2001.
[41] M.K. McKusick, K. Bostic, M.J. Karels and J.S. Quarterman. The Design and Implementation of the 4.4BSD Operation System. Addison-Wesley, Massachusetts, 1996.
[42] Microsoft. Age of Empires. http://www.microsoft.com/games/empires/ (last access: May 2006)
[43] Microsoft Corporation. Active Server Pages. http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnanchor/html/activeservpages.asp (last access: April 2006).
[44] Microsoft Corporation. Internet Information Services. http://www.microsoft.com/WindowsServer2003/iis/default.mspx (last access: April 2006).
[45] Microsoft Corporation. MSDN: ODBC. http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vccore98/HTML/_core_odbc.asp (last access: April 2006).
[46] Microsoft Corporation. MSDN: Thread Stack Size. http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dllproc/base/thread_stack_size.asp (last access: April 2006).
[47] Mindcraft Inc. Webstone. http://www.mindcraft.com/benchmarks/webstone/ (last access: January 2006).
[48] Mudge. How to write buffer overflows. http://www.insecure.org/stf/mudge_buffer_overflow_tutorial.html (last access: May 2006).
[49] Multimedia University. Multiplayer Board Game Framework. http://foe.mmu.edu.my/software/gameframework/ (last access: May 2006).
[50] G.C. Necula, S. McPeak and W. Weimer. "CCured: Type-Safe Retrofitting of Legacy Code." In Proceedings of the Principles of Programming Languages (PoPL), pp. 128-139, January 2002.
[51] B. Nichols, D. Buttlar and J.P. Farrel. Pthreads Programming: A POSIX Standard for Better Multiprocessing. O’Reilly, California, 1996.
[52] H. Nielsen, T. Berners-Lee and J. Groff. Libwww – the W3C Sample Code Library. http://www.w3.org/Library/ (last access: April 2006).
[53] NKB Inc. Internet Go Service. http://igs.joyjoy.net/ (last access: April 2006).
[54] OpenLDAP Foundation. OpenLDAP Software Man Pages: ldap. http://www.openldap.org/software/man.cgi?query=ldap (last access: April 2006).
[55] J. Orwant, "Eggg: Automated programming for game generation," IBM Systems Journal, vol. 39(3):782–794, 2000.
[56] J. Orwant. "EGGG: The Extensible Graphical Game Generator." PhD Thesis, MIT, December 1999.
[57] J. Ousterhout. Why Threads Are A Bad Idea (for most purposes). http://home.pacbell.net/ouster/threads.pdf (last access: April 2006).
[58] V. Pai, P. Druschel and W. Zwaenepoel. "Flash: An Efficient and Portable Web Server." In Proceedings of USENIX Annual Technical Conference, Monterey, California, USA, pp. 199-212, 1999.
[59] B. Perens. "Electric Fence Malloc Debugger." In Pixar Animation Studios, 1993.
[60] W. Pree. Design Patterns for Object-Oriented Software Development. Addison-Wesley, Massachusetts, 1995.
[61] E. Rescorla and A. Schiffman. "The Secure HyperText Transfer Protocol." Technical Report RFC 2660, August 1999.
[62] M. Rinard, C. Cadar, D. Dumitran, D.M. Roy and T. Leu. "A Dynamic Technique for Eliminating Buffer Overflow Vulnerabilities (and Other Memory Errors)." In Proceedings of the 20th Annual Computer Security Applications Conference (ACSAC'04), 2004.
[63] R. Rugina and M. Rinard. "Symbolic bounds analysis of pointers, array indices, andaccessed memory regions." In Proceedings of the ACM SIGPLAN'00 Conference on Programming Language Design and Implementation, pp. 182-195, June 2000.
[64] O. Ruwase and M.S. Lam. "A Practical Dynamic Buffer Overflow Detector." In Proceedings of the 11th Annual Network & Distributed System Security Symposium, pp. 159-169, February 2004.
[65] D.C. Schmidt, "Reactor: An Object Behavioral Pattern for Concurrent Event Demultiplexing and Event Handler Dispatching," in Pattern Languages of Program Design, Massachusetts: Addison-Wesley, 1995, pp. 529-545.
[66] D.C. Schmidt, M. Stal, H. Rohnert and F. Buschmann. Pattern-Oriented Software Architecture Vol. 2: Patterns for Concurrent and Networked Object. John Wiley & Sons, New York, 2000.
[67] SecurityFocus. Mod_mylo apache module REQSTR buffer overflow vulnerability. http://www.securityfocus.com/bid/8287/ (last access: January 2006).
[68] SecurityFocus. Thttpd defang remote buffer overflow vulnerability. http://www.securityfocus.com/bid/8906/ (last access: January 2006).
[69] SEGA and Creative Assembly. Total War. http://www.totalwar.com/ (last access: May 2006).
[70] Sina. SinaHK. http://game.sina.com.hk/cgi-bin/index.cgi (last access: May 2006).
[71] Sina. SinaTW. http://games.sina.com.tw/ (last access: May 2006).
[72] W.R. Stevens. Advanced Programming in the UNIX Environment. Addison-Wesley, Massachusetts, 1992.
[73] W.R. Stevens. TCP/IP Illustrated Vol. 1: The Protocols. Addison-Wesley, Massachusetts, 1994.
[74] W.R. Stevens. UNIX Network Programming Vol. 1: Networking API: Sockets and XTI, Second Edition. Prentice Hall, New Jersey, 1998.
[75] Sun Microsystems Inc. JavaServer Pages Technology. http://java.sun.com/products/jsp/ (last access: April 2006).
[76] Sun Microsystems Inc. JDBC Technology. http://java.sun.com/products/jdbc/ (last access: April 2006).
[77] Tanguy Urvoy and gnugo team. Pattern Matching in Go with DFA. http://www.irisa.fr/galion/turvoy/papers/dfabstract.ps (last access: May 2006).
[78] The Apache Software Foundation. The Apache HTTP Server Project. http://httpd.apache.org/ (last access: May 2006).
[79] The MITRE Corporation. Common Vulnerabilities and Exposures. http://cve.mitre.org/ (last access: May 2006).
[80] The PHP Group. PHP: Hypertext Preprocessor. http://www.php.net/ (last access: April 2006).
[81] The Software Technology Laboratory, Queen's University, Kingston, Canada. TXL Home Page. http://www.txl.ca/ (last access: January 2006).
[82] ThinkNewIdea Inc. CYC Game League. http://cycgame.com (last access: April 2006).
[83] J. Tranter, "Exploring the sendfile system call," Linux Gazette, vol. Issue 91, June. 2003.
[84] Valve. Half Life 2. http://half-life2.com/ (last access: May 2006).
[85] Vendicator. Stack shield. http://www.angelfire.com/sk/stackshield/ (last access: January 2006).
[86] W3C. Extensible Markup Language (XML). http://www.w3.org/XML/ (last access: May 2006)
[87] D. Wagner, J.S. Foster, E.A. Brewer and A. Aiken. "A First Step towards Automated Detection of Buffer Overrun Vulnerabilities." In Network and Distributed System Security Symposium, pp. 3-17, February 2000.
[88] R. Wahbe, S. Lucco, T.E. Anderson and S.L. Graham. "Efficient software-based fault isolation." In Proceedings of the Fourteenth ACM Symposium on Operating Systems Principles, Asheville, North Carolina, United States, pp. 203-216, December 05-08.
[89] M. Welsh, D. Culler and E. Brewer. "SEDA: An Architecture for Well-Conditioned Scalable Internet Services." In Proceedings of the 18th ACM Symposium on Operating Systems Principles, Alberta, Canada, pp. 230-243, 2001.
[90] D. Wessels . Squid Web Proxy Cache. http://www.squid-cache.org/ (last access: May 2005).
[91] R. Wu and D.F. Beal, "Solving Chinese Chess Endgames by Database Construction," Information Sciences, 2001.
[92] I.C. Wu and D.Y. Huang. "A New Family of k-in-a-row Games." In The 11th Advances in Computer Games (ACG11) Conference, Taipei, Taiwan, 2006.
[93] I.C. Wu, D.Y. Huang and H.C. Chang, "Connect6," Internation Computer Game Association, 2005.
[94] J. Xu, Z. Kalbarczyk and R.K. Iyer. "Transparent runtime randomization for security." Technical Report UIUL-ENG-03-2207, Center for Reliable and High-Performance Computing, University of Illinois at Urbana-Champaign, May 2003.
[95] Yahoo! Inc. Yahoo! Games. http://games.yahoo.com/ (last access: April 2006).
[96] S.J. Yen, J.C. Chen, T.N. Yang and S.C. Hsu, "Computer Chinese Chess," ICGA Journal, March 2004.
[97] Zeus Technology limited. Zeus Web Server. http://www.zeus.co.uk/products/zws/ (last access: April 2006).
[98] M. Zhivich, T. Leek and R. Lippmann. "Dynamic Buffer Overflow Detection." In 2005 Workshop on the Evaluation of Software Defect Detection Tools (BugWorkshop05), Chicago, 12 June 2005.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文