Heuristic graph partitioning and cheat detection in mobile games

Abstract

Existing graph partitioning algorithms usually adopt random hashing in vertex assignment while overlooking the effect of high-degree replica on partitioning result. Inadequate vertex cut on high-degree vertices may result in a huge number of unnecessary replicas scattering around different partitions. In this thesis, a heuristic greedy graph partitioning algorithm is proposed to address this issue. It minimizes the number of cuts on high-degree vertices to avoid generating excessive replicas by assigning them with first priority during the partitioning process. Head to head comparisons are made between the proposed algorithm and the state-of-the-art algorithm. Supported by a theoretic proof, experimental results show that the proposed algorithm outperforms the state-of-the-art algorithm by achieving a smaller replication factor in partitioning random graphs, power-law graphs and real-life graphs with minor sacrifice on the balance of the partitions. In the latter part of this thesis, two outstanding issues in cheating in mobile games have been addressed. The first one is the abuse of auto clickers where cheaters setup automated programs to perform tasks effortlessly in games to gain advantage over other players. A behavioural detection methodology is proposed to identify potential auto clicking behaviours by investigating the touch inputs provided by the players. It makes use of two detection features which respectively look at the clicking frequency and the dispersion of positions of the touch inputs. By examining the methodology in two famous mobile games, it is shown that auto clicking behaviours can be efficiently identified with larger dispersion on touching positions and higher clicking frequency. The second issue in mobile game cheating is the usage of location spoofing in location-based augmented reality mobile games. With the help of a large pool of well-developed location spoofing applications available in market, cheaters can effortlessly travel from place to place in game. Traditional system detection approaches taken by game publishers cannot solve the entire problem as they may fail if the application undergoes privilege escalation. In the third part of this thesis, a novel detection approach is proposed by making use of the gyroscope and accelerometer commonly equipped in most mobile devices. It compares the facing direction provided by the gyroscope of the mobile device with the travel direction deduced from the GPS data to identify location spoofing behaviours. It also checks on the genuineness of each travel by comparing its average step length with the adult average step length. Sample walks and spoofing simulations on various paths are carried out and the orientation, GPS data and step count are being recorded for detailed comparison. Experiment results show that the rotation of the mobile device synchronises well with the change of the travelling direction of the user in normal cases, while on the other hand gives fuzzy results when location spoofing takes place. The average step length deduced from the GPS data and step count aligns well with the adult average step length, showing that one can effectively identify location spoofing behaviours with the help of these identification criteria.