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.

Fermanagh

Better off submitting your working code to code review and asking there. – Virtuosity

Your API / template interface will have to be bulletproof. Tell us more about it. If any user would want to cheat, he'll have to find a hole in it. – Clance

If the cheater is the host, it means he runs the server code ? So I guess the cheater could influence the all game – Clance

Some kind of checksum yes, to check the integrity of the game. Unless the player hacks this too :) – Clance

It's a good approach I think. One hacked game cancels the whole set of players. – Clance

Conversation with @Clance deleted, since he formatted it into an answer. – Fermanagh

the comment on User input is allowed. isn't that Darinth instead of Sarinth, maybe your spellchecker "helped" you there. – Tedium

Answer 1

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.

Tedium

Thank you for your answer. Do you think some of these points would apply to my case? As opposed to a normal snake where each snake is controlled by a human, in my case the very point is that the snakes are controlled by AI; that all the choices are inhumanly accurate and lightning fast, and always maximize the probability of winning (given a good AI, of course). You gave an excellent overview of the general case - what could be done in some software. I think points 2, 3 and 4 are not issues with my game, however. Point 5 could be rendered less worrying by randomizing ranked matches. – Fermanagh

Issue 1. was, I think, covered in @ToYonos's answer, but it's good you mentioned a similar case (with an example!) in your answer. Some of the general issues are also ongoing problems with no good comeback. For example point 4: I was inspired by this and went to see if chess.com had any counter measures for this. It did not. I easily won 2 matches against players with decent ELO. Given that chess.com is a pretty big website for online chess, I had to conclude that they have nothing to answer with - it's simply impossible to determine whether or not there is a human behind the controls. – Fermanagh

Again, thanks for your insight. If you can come up with more issues with my software, please edit your answer and I'll be sure to upvote. – Fermanagh

Point 4 is a possibility as an optimized multi-chip multi-threaded vectorized algorithm could compute all game states, where the java programs might not. – Tedium

Can you come up with ways to prevent #4 and/or #6? – Fermanagh

Split 6 in two and added 8 and X, elaborated a bit more on #4+ – Tedium

Answer 2

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.

Clance

I will remove the conversation from the above comments, you should do the same to keep things organized :) Also, my original thought was to run a simulated game. 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. – Fermanagh

Ok, got it. My idea was more an upstream verification. Your idea is good too and both could be accomplished. I will update my answer. – Clance

I didn't mean to exclude the checksum idea. By testing later on I will decide on one or the other, or both if they work better together :) – Fermanagh

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.

Andalusia

Having a human operating the snake fully or partially has been made possible. I have actually made it very easy for the user to do; the API keeps in memory the last key that the user has pressed, and moves the snake in the appropriate direction. This is part of the design. I intended that when making a game, the speed of the game would be predetermined, but adjustable by the host. This way the host could tell other players if the game is supposed to be played by humans (slow speed) or algorithms (high speed). If a new move is made every 5ms, a human would be at a significant disadvantage. – Fermanagh

Generally, any way to determine the next move of the snake is allowed. It doesn't matter how the player determines his/her snake's next move, the best algorithm wins. All players stand on equal ground on this matter, since the very point is that if you have a good idea for an algorithm, you will most likely win. If you have an underhanded/out-of-the-box idea, you will trump good algorithms. If you have an excellent algorithm that covers everything, you will win. – Fermanagh

However, noticing that user input will be possible, even though I didn't mention that, earns you a +1. It's an important aspect of the game that I forgot to mention. – Fermanagh

Edit to the first comment: the API keeps in memory the last key that the user has pressed, and the user can choose to move into a direction according to it. – Fermanagh

In theory, you should be able to use the class's methods to create an entire window to host a UI for controlling an AI agent. At that point, you could set an AI mode, level of aggressiveness, etc... Also, you spelled by name incorrectly in your edit. :) – Andalusia

That's not necessary at all. You can determine whether or not use the AI to drive the algorithm without much or any hocus pocus. Did I understand your comment correctly? – Fermanagh

You'd just mentioned that the API tracks the last key pressed, and while that can be used to allow user input, you could actually use java's classes to create an entire window to give much more fine-tuned control over an AI agent. – Andalusia

Ah you mean allow additional settings, such as make space bar adjust the algorithm at run time? That is true, and entirely allowed. However most of the time it may be difficult to control the AI efficiently, because, as I have mentioned, most of the games will be too fast-paced for a human to react really. But it's totally possible in slower games. – Fermanagh

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

Romantic

Thanks for your answer. I had thought about making a single server on my machine, however I thought it would be the most boring solution :) and I would have to keep the server running. From the other answers I have received I think I've ended up into a hybrid of points #2 and #3, where all players see if the game-state is the same with the game-state of all the other players. If it isn't, the whole game is cancelled, since the game went "out of sync", and it's entirely possible that a) someone cheated, or b) someone has a different version of the game. This is, I think, fair for everyone. – Fermanagh

Be careful of false positives here, some people playing on wifi or mobile will have lots of DCs. – Tedium

@Tedium disconnects should not be a problem here the serve needs to keep track of the state (using tcp it's clear what the client knows). If there is a disconnect the state can be preserved and continued on reconnect. If the state goes out of sync there should be a huge possibility to have detected a manipulation – Romantic

Which remind me I forgot one 9) Disconnect when your losing. – Tedium

@Tedium jep this is a problem -> the game will stay in the waiting position forever. But you could give games a timeout -> if one of the players is not connected for let's say a day he/she looses the game – Romantic