Potholes in an automated multiplayer game where players can use their own algorithms

Question

About the tags

I have tagged this as being a Java and a C++ question. This means I'm not looking for language-specific answers. I have only tagged C++ and Java because I'm proficient with them, and will most likely understand your code-samples if they are written in those (or similar) languages.

What am I looking for?

Pointers and insight on security measures that I should take into consideration when developing software, mainly games, such as the one described below. By security I mean checking and double checking that a user doesn't act in a way not intended. This could mean behaviour such as sending his/her updated collection of the most malicious viruses in existance to the server/other clients, or otherwise compromise the user-experience for other players by, for example, hacking.

---

Expected comments and answers

Are you asking how to stop people from hacking your game?

This is not by any means my question, as it's way too broad for this thread. If you however do come across a simple way to win every game (by cheating), then please, tell me.

This question is better suited in X

I have asked this very question in CodeReview and in Programmers; in both networks the post was badly received. It was badly received in here as well, to be fair (referring to the comment by ADTC), hence the bounty. After placing the bounty I have rewritten this post to better meet the standards of SO. If, however, you still think this post doesn't suit here well, please tell me why. I've had a hard time determining if this really is better suited in SO or Programmers, so don't think this is just a dump that I posted here after not thinking about it for a second.

To create a connection between two machines, you should use Sockets. Google it.

I am not looking for this kind of technical help. I know how to implement the software, and it's not the first time I'm doing this. Please look at the actual question I asked.

---

Why am I asking this?

The software in question

I'm developing a snake-like multiplayer game where players can use their own algorithms to determine the next move of their snake. The players are connected to each other with a client-server connection, that is, one player will act as the host. You can assume that the server code will wait until all players have made their turns until updating the game-state between all the clients.

About the game

My game searches a folder for any compatible .jar files, whose main class extend a particular abstract class. The player can then connect to another player(s) over the network by directly connecting to them or by searching a game from a lobby.

While playing, each player will use their own algorithm to determine the next move of their snake. The duration of each game may vary a lot, depending on the update rate that has been specified for the game, but most of the time they are fast and will most likely end in less than 30 seconds.

I'm not as far yet as implementing the actual network multiplayer.

---

The template source file for a logic is as follows:

package template

import snake.*;

public class TemplateLogic extends SnakeLogic {

    @Override
    public void onLaunch() {
    }

    @Override
    public String getMove() {
        return "UP";
    }

}

---

So what I'm planning to do is, from the hosting player's perspective, to get the next move of a player over the network in a String format ("up", "down", "left", "right"), so there won't be any security issues on that front. The actual program that each each client uses to determine their next move will only ever run on the respective client's computer.

I hope you are following me so far. Anyway, what I am concerned about right now is any other potholes I may have overlooked. Determining all of those potholes may be a bit too tedious of a task to do, so I wont ask that primarily. Giving me insight on the matter is what I'm expecting. Ideally I can get a bigger picture from multiple answers by different people.

The question that floats on top of the others is that can I prevent any of the clients from using methods on their programs that would compromise the user experience for the other player(s)? Such methods could be for example Thread.sleep(): it would be pretty annoying if a player made his algorithm wait for 10 minutes between each move. For this particular problem I figured I'd set a time limit for each move, after which the lagging/malicious player will be kicked or assigned a default move so the game can continue normally.

---

Off-note:

@Darinth's answer reminded me of a very important aspect of the game: user input is allowed, meaning that the next move of the snake can be determined by a human player - that is, the game can be played normally with a keyboard. Additionally, nothing restricts you to choose between a pure AI and a keyboard-only-solution: you can mix them together and, for example, control the snake yourself and let the AI take over when it notices you are driving yourself into a trap.

---

To wrap it up

Have I overlooked something big? I have planned for this to be a small project for me and my friends to kill time with, but I'm a bit of an enthusiast.

Please answer without hesitation, no matter how small your idea is. You can later edit the answer to be more comprehensive, should you think of more points of interest. I will check any answers for edits regularly.

Thank you for your time.

---

Relevant ideas I have received from answers or on my own

• Compare hash of game-state with all the clients after every move. All but the players with the same hash will be kicked, with the minimum requirement that the host will be kept in the game (if there are 4 players, out of which 2 players have one hash, and the other 2 players have another hash, the group that doesn't include the host will be kicked, etc.). I came up with this one, however it's thanks to @ToYono, so the credit goes to him.

• Before the game starts, compare the checksum of each player. All players with differing checksum from the host will be kicked (or not even let in the game). Credit goes to @ToYono.

• Randomize any ranked matches. Prevents the effective use of using multiple connections from the same machine to play in the same game. If one player play multiple snakes in one game, he could have one algorithm that tries to play the game legitly, and two algorithms that simply sabotage the other player. Credit goes to @Surt.

• User input is allowed. This was designed to be a part of the game from the start, but I forgot to mention it. Credit to @Darinth for coming up with the possibility and thus reminding me of this important aspect.

Answer 1

This response summarizes the chat made above in the comment section.

• As one of the player has to host the game, What if the cheater was the host ?

If the cheater is the host, it means he runs the server code. That implies he could influence the entire game as he's operating the core engine.

A good solution would be for each player to compute a checksum, and compare it with all other players' checksums, engaged in one game. If one checksum does not match, the game is canceled. This checksum could be a unique String based one program version.

• Could the host hack this system too ?

As each player does its own comparison, all the players would have to hack the game in the same way to, which is highly unlikely. And as @Olavi Mustanoja pointed out, the checksum system would have great synergy with an update client.

Edit:

The OP's original idea was to compare game's states at each turn, between all players.

The state of the game is stored in an int array, where 0 means available space, -1 means a piece of snake, -2 means a head of a snake and 8 means apple (or cookie). After each turn, the game would compare all the state-arrays and terminate the game if at some point some of the states differ from the others. This could be easily done by sending the hashcode of the array.

This idea is not incompatible with my checksum idea, it could be a double security.

Answer 2

If a player can cheat some players will cheat. So what are the most easy methods to cheat?

1) Change the state of the game, effectively undo previous moves.

• all other players and/or the server should validate the update, since it is discreet values your dealing with it should not be a problem. Client side checks might be enough but a sharp hacker can hack the check by changing the check to some thing like

  bool allowedMove() { return true; ... remaining original check code here }

Which must then be countered by a checksum of the code, SHA3? as MD5 is nearing the end of its safe epoch.

Example: WoW teleport hack, x,y,z is calculated on the client and send to the host.

• cheaters hack the client to get the desired result.
• Bliz makes checksums on the client.
• cheaters just inserted a new network package with the x,y,z to teleport where they wished.
• Bliz checks for external programs doing this.
• cheaters randomize their external programs.
• Bliz countered with server side distance checks.
• cheaters countered with limiting the teleport to the distance allowed, result people walking on air with no flying.
• Bliz countered with further server side sanity checks apparently solving most of the problem.

2) React with inhumane speed, effectively eliminating the human delay. Not a problem in your game unless faster gives more moves, but this is between programs so ... they might always be faster than humans.

• if the reaction time often is faster than human possible a cheater is properly at the other end. Difference in reply and ping time is not large enough.

3) Automatic targeting ensuring inhumane high hit rate.

• the player has much better hit rate than the 2nd best confirmed human player.

Example: shooter game XXX

• external program catches player coordinates and feed corrected targeting to game via windows API.

4) Using other external helper programs

• much better AI than the other players

Example: online chess games, where a cheater uses a chess program to help with moves.

• Your players can make a program that saves the game state and makes an external program process the data and make a next move which is then loaded by the cheaters program and send as next move.
• check for any load in programs, players might legitimate want to have saves to analyse their programs effectiveness.
• using optimized multi-chip multi-threaded vectorized algorithm the cheater can explore most or all game states.
• it is nearly impossible to check for external programs helping, you can check for external windows event generation, but there will be a lot of false positives. You can try to prevent any load/save cheats, but cheaters can attack at the IP-level.
• the biggest protection is that the effort to make it might outweigh any benefits.

5) Multi-boxing, some players might have multiple computers cooperating for victory

• using multiple computers or instances of the program can increase the chance of the cheaters main instance wins as the other sabotage the other players.

Example: could happen in a shooter game?

• cheater sends decoy or suppression unit in drawing fire or hindering enemy movement while the real player shoots the opposing player or scores points in other ways.
• difficult to check as 2 persons could legitimately play from the same location.
• if the MAC address of the computer is that same for multiple players it might be indicative of cheating as they would then be plying on the same PC. But even this could not be cheaters as they could be playing from closed Virtual Machines.

6) Pre-compute all game states so that the cheater can use the most optimal strategy.

• players not doing this will chose suboptimal starting moves.

Example: tic-tac-toe

• it is possible to calculate all game states. (you can possible do this in your head for tic-tac-toe).
• rating the players should help here, but the cheater could still easily win.
• pre-compile opening sequences are usual for chess programs for example.
• only way to beat this is very randomized maps and starting positions with so large a state that it cannot be pre-calculated.

7) Creating new identities to beat ratings.

• cheaters are trilled by winning, they will create new "players" for themselves at low rating to "win" again.
• this happens even if players don't cheat, they will create new identities so they can beat easy victims.

8) Win trading

• 2 cheaters trade wins with each other

Example: WoW battlegrounds

• using external programs to increase chance of getting the right opponent.

• disconnecting to avoid it registering if not paired with the right opponent. Disconnects often happens even without cheating (don't play wireless or on mobiles if you want to reduce this).

• detect if 2 Mac-addresses plays a lot with different identities and only one on each Mac wins.

9) Disconnect when your losing.

X) The unknown unknown (as opposed to the known known, the unknown known, the known unknown)

• there is always someone inventing some new ways to cheat that we didn't think about.

Example: tax evasion

• there are always loop holes, missing or false reporting of income, new deductions that are fraudulent etc.

• luckily there is always a way to find out if someone is cheating to the top position, you can check the algorithm they submitted to the program and see it its cheating. Beware that the program you will get retrieved can be a fake, but testing if it could have won so much might be trivial.

• the smarter cheater will stay a bit below the radar.

Answer 3

A lot of this depends on what you intend on limiting. Is it okay for the algorithm to ask user input? Is there supposed to be a limit on what information the algorithm has access to? Using java/c++ code gives the algorithm the ability to do almost anything. You could setup a window to choose a path for the snake to follow, allowing them operate with human intelligence, but machine precision. You could give the option to swap between different algorithms that might activate an 'escape' mode to get out of a sticky situation, or an attack mode to specifically attempt to trap a player who you noticed is in a bad spot. If this is something you want to avoid, my recomendation is to provide a scripting language (like Lua or Javascript). These can easily be customized to limit their capabilities and prevent the users from accessing anything you don't want them to. Do it decently well, and you can actually safely send these scripts to all of the clients/servers and they can all safely run the simulation and compare steps/results.

If you're okay with these things, than the only other concerns I could have would involve hosts using hacked clients that have already been mentioned.

Answer 4

The main problem is the server. It has the game state and needs to be trusted. The client in your case can be modified since the client is allowed to do whatever it takes to determine the next step. You can't by any means really trust the server if it is executed on a remote machine. It may manipulate all checksums and digital signatures since the machine itselve is not trusted.

I can think of 3 things you could do to make your server trusted:

• Execute the server one a machine that is controlled by you -> the game clients connect to the server. IMHO the best solution to the problem
• Host the server on UserA. UserB and UserC are using this server to play. UserA and UserD can play on a Server hosted @ UserB. No one has a interest on hacking/modifying the client/server code. => difficult to implement but you don't need any server infrastructure (only the game lobby...)
• All clients have a local server. Only if the two combatants agree on the result of a game it is counted => you could detect that someone is doing something bad, but not who exactly. You could make a counter on the server and if one user is often having manipulated matches you could exclude them and their result