On the scalability and security of distributed multiplayer online games

Multiplayer Online Games (MOGs) are an extremely popular online technology, one that produces billions of dollars in revenues. Yet, providing scalable, fast, and cheat-resistant games is challenging. In this thesis we propose solutions to some of these challenges.The underlying architecture plays a crucial role in enabling the games to meet the scalability, response time, and low cost requirements that are of utmost importance in designing a successful massively multiplayer online game. Peer-to-peer architectures where the game runs exclusively on client machines, and hybrid approaches, where some tasks run on the clients while a central server controls other aspects, have, due to their distributed and collaborative nature, low infrastructure costs, and can achieve high scalability. They can also achieve fast response times by creating direct connections between players. However, they introduce their own challenges such as cheating. As one contribution of this thesis, we provide a comprehensive overview of current peer-to-peer and hybrid solutions for massively multiplayer games using a uniform terminology.Most of the solutions we studied fail to meet one of the following main requirements: (1) fast response time, (2) scalability, (3) cheat-resistance. This thesis makes several proposals that address these requirements: Watchmen, mobile security, AntReckoning, and AntAI.Watchmen is the first distributed scalable protocol designed with cheat detection and prevention in mind that supports fast paced games. It is based on a randomized dynamic proxy scheme for both the dissemination and verification of actions. We show that Watchmen, while scaling to hundreds of players and meeting the tight latency requirements of first person shooter games, is able to significantly reduce opportunities to cheat, even in the presence of collusion. In the context of cheating we also look at the fast rising genre of mobile games. We discuss existing and potential new avenues of cheating that can occur in such mobile environment, and suggest several solutions to improve security based on existing and novel services that are or can be offered by carriers, ecosystems, and developers.AntReckoning is a dead-reckoning algorithm, inspired from ant colonies, which models players' interests to predict their movements. It helps our architecture by allowing us to send updates at lower frequencies and with more accurate predictions which in turn improves the scalability and the quality of experience of the players. AntReckoning incorporates a player's interest in specific locations, objects, and avatars in the equations of motion in the form of attraction forces. In practice, these points of interest generate pheromones, which spread and fade in the game world, and are a source of attraction. AntReckoning greatly improves the accuracy of traditional dead reckoning techniques and can decrease the upload bandwidth by up to a third of overall traffic.Interest modeling can also be used to improve the performance of non-player characters in games. In our AntAI project, we detail how movements, interactions, use of items, and relying on static decision-making schemes result in markedly different behaviors from humans in a popular fist-person shooter game. From there, we propose a framework relying on our pheromone maps, which can lead to a more adaptive human-like behavior.Altogether, this thesis presents components that we believe are key elements for a scalable, cheat-resistant, and fast multiplayer online game architecture.Les jeux multijoueurs en ligne constituent à l’heure actuelle une technologie en ligne très populaire qui génère des milliards de dollars en revenus. En dépit de cela, offrir des jeux qui sont à la fois extensibles, rapides et résistants à la tricherie est toujours un défi. Dans cette thèse, nous proposons des solutions à certains de ces défis.L’architecture sous-jacente joue un rôle crucial lorsque l’on souhaite développer des jeux qui rencontrent des contraintes d’extensibilité, de faible temps de réponse et de faible coût. Ces contraintes sont d’une importance capitale si l’on souhaite que le jeu massivement multijoueurs en ligne ainsi développé devienne un succès. Les architectures pair-à-pair, où le jeu s’exécute uniquement sur les machines des clients (joueurs), ainsi que les approches hybrides, où certaines tâches du jeu s’exécutent sur les machines des clients tandis qu’un serveur central gère d’autres aspects du jeu, permettent, de par leur nature distribuée et collaborative, d’atteindre une haute extensibilité tout en minimisant les coûts d’infrastructure. Ces architectures permettent également d’atteindre des temps de réponse élevés en établissant des connexions directes entre les joueurs. Cependant, elles introduisent également certains défis à résoudre tels que la possibilité de tricher. En tant que contribution à cette thèse, nous exposons une vue d’ensemble exhaustive des solutions pair-à-pair et hybrides courantes pour les jeux massivement multijoueurs en ligne utilisant une technologie uniforme.La plupart des solutions que nous avons étudié ne respectent pas l’une des exigences principales suivantes: (1) temps de réponse rapide, (2) extensibilité, (3) résistance à la tricherie. Cette thèse décrit les différents projets sur lesquels nous avons travaillé qui visent à mettre en oeuvre ces exigences: Watchmen, sécurité mobile (mobile security), AntReckoning et AntAI.Watchmen est le premier protocole extensible et distribué conçu spécifiquement pour la détection et la prévention de la tricherie qui prend en charge les jeux à rythme rapide (fast-paced). Ce protocole est basé sur un schéma d’assignation dynamique aléatoire de noeuds-relais (proxie) pour effectuer tant la dissémination que la vérification des actions. Nous démontrons que Watchmen est en mesure de réduire de manière significative les possibilités de tricherie, même en présence de collusion et ce, tout en prenant en charge des centaines de joueurs et en rencontrant les exigences strictes de latence imposées par les jeux de tirs à la première personne. Dans le contexte de la tricherie, nous nous attardons également aux jeux mobiles. Nous discutons des possibilités existantes et des nouvelles avenues potentielles de tricherie qui peuvent survenir dans des environnements mobiles et nous suggérons différentes solutions pour améliorer la sécurité. Ces solutions sont basées sur des services existants ou nouveaux qui sont ou qui pourrait être offerts par les opérateurs, écosystèmes et développeurs.AntReckonning est un algorithme de navigation à l’estime (dead-reckoning) inspiré des colonies de fourmis qui modèle les intérêts des joueurs pour prédire leurs mouvements. Ce modèle est bénéfique pour notre architecture puisqu’il nous permet de transmettre les mises à jour à des fréquences inférieures et avec des prédictions plus précises, ce qui permet d’améliorer l’extensibilité et la qualité de l’expérience des joueurs. AntReckoning incorpore l’intérêt des joueurs pour des emplacements, objets et avatars spécifiques au sein d’équations de mouvement en tant que forces d’attraction. En pratique, ces points d’intérêt génèrent des phéromones qui se diffusent et s’estompent dans le monde virtuel du jeu et qui sont des sources d’attraction. AntReckoning améliore de manière significative la précision des techniques de navigation à l’estime traditionnelles et peut réduire la bande passante de téléversement (upload) jusqu’à concurrence de un tiers du trafic total