Hacker News Reader

If you have a deterministic game model(RNG seeded properly, pure functions, etc) you can actually just send the user inputs(which are very small compared to the whole game state) and replay the whole game to verify.

This is the common model in RTS games called Lock Step since all clients are advancing a number of frames based on all inputs from other clients in "lock step".

It's also very common way to implement replay and debugging for reproducing rare network bugs.

Using the Bejeweled example of a single-player game, and assuming it's properly deterministic, could a malicious actor not just falsify the steps taken as well as the score? It would be more difficult, but not that much more difficult considering the challenge is the time limit and lack of undo. Both would be removed if you were simulating steps.

They could, but they can't falsify the game seed - the server determined order for what gems spawn when. This way I can send actions (whether real or hacked) that would be executed in the server against the "real game". If the client's move did not result in a score then no score is recorded, even if the client thinks it should.

But it would mean a bot could get the highest possible score for that seed by going back in time and trying again.

Yeah, that's assuming you know what the RNG algo is.

There's a sibling comment below that mentions this. Most RTS games checksum the game state and send an out of sync when the checksums fail. If you generated different random values you'd definitely hit this.

Always sucked when it happens about 1 hour into a game of Homeworld.

This is entirely possible and its why things like Punk Buster, etc. exist. For a lot of single player games it'd be hard to verify that an actual human physically executed the plays vs. a bot. I'm ok with accepting a high score from someone that went through that level of effort to falsify replays to get on a leader board. If a puzzle game is truly interesting that kind of cheating isn't necessarily optimal anyway.

If you don't care about overkill, you could employ machine learning and anormaly detection: send the input sequences, timing and other difficult to fake data (e.g. gyroscope state) to the server and learn the "typical" distribution of those values. A perfect game played by a robot will likely be an outlier in a lot of the values.

(Note that some legit games will also look suspicious, so you'd want to use this to find out which players you should keep an eye on, not as a tool for auto-banning.)

If I was a game developer and a person developed a bot to play my game perfectly, I'd let them have the high score.

But that doesn't happen, that person distributes that bot and suddenly you have a huge issue where all the high scores are bots which frustrates real users.

This works great for proper RTS games because the steps are usually pretty lengthy (in game terms, like around 200ms) and the way the game genre typically works means relatively little prediction or complicated simulation design are needed to make even huge steps feel responsive.

Recording and playing back input events, at least, shouldn't be that expensive unless you're emulating the entire stack up to the application. If the logic is written in some portable manner (Xamarin [1], etc.) you could just re-execute on the server with the same logic as the client. It requires a fair amount of discipline to keep everything deterministic, too. The real difficulty would be identifying the AI players from the humans; you'd basically have to recreate re-captcha's humanity checkbox, and that's still not a guarantee.

Or, identify that your business need is just to provide 'some' sort of ranking and compare the user against their Facebook/G+/Twitter friends, who are probably less likely to cheat.

[1]: https://www.xamarin.com/

Ah shoot, you beat me to it by 5 minutes :). Yeah, that's how you do it in practice.

Gah, sorry about that :/ fwiw, it looks like your explanation has more upvotes, so it worked out alright! :)

Nah, not an issue at all :).

FWIW it's a fun domain space, partially these cool technical approaches(lock-step, dead-reckoning) and partially smart user interactions(how you decide to give users immediate feedback when you won't actually know until 100-800ms later).

Your second point is the important one for most games I think. Global leaderboards on a popular game are meaningless for the vast majority of players (do you care that you are in position 324,675?) and almost all of the implementations I've seen have been hacked. As this thread has discussed it's hard to protect false data from getting in the leaderboard.

Limiting leaderboards to friends both gives relevant context for fun competition and mostly eliminates the cheating problem by making it a social issue. I know my friends wouldn't be happy if we were all competing on a game and I cheated.

This is actually impossible without hardware encryption. Apple should have no problem with this since they have control over their hardware, but they don't do anything to prevent fake scores from showing up in their leaderboards. Xbox is a great example of being able to trust the client. The console tells the server that it has unlocked an achievement by using a signed request which was signed by the secure chip. The same chip verifies that the games you are playing are legitimate, etc. It's a very important piece of hardware and it would likely be the Xbox's demise if that secure chip suddenly became insecure.

Running the game on the server is the only option as far as I know for securing the integrity of the data. You could add a private key to your app, but then you're shipping the private key to the client.

> Apple should have no problem with this since they have control over their hardware, but they don't do anything to prevent fake scores from showing up in their leaderboards.

Apple has leaderboards? For what?

Apple's "Game Center" (https://en.wikipedia.org/wiki/Game_Center) provides integrated cross-game leaderboards and achievements/badges.

Not even such a secure chip is secure. People can take apart hardware security modules in credit card scanners and scam the credit card networks over millions (a "how to" on how to do this was shown on 32C3).

Your Xbox hardware is even less secure.

We had to deal with this issue with a website that hosted 3rd party games, so we were restricted in our options. Since we didn't make the games ourselves things like server side playback wouldn't work.

For us, there was no foolproof method. So our main goal was to ensure that the leaderboard wasn't full of obvious cheating.

First, to reduce the volume of cheating, we obfuscated things:

1) We encrypted all communication.

2) We required a single use submit token, generated by the server, with each game play.

We also manually reviewed scores. In particular, the top 10 scores of each game.

Beyond that, since we required a single use submit token, it means that we knew how long the player took to obtain their score. For most games, the higher your score, the longer you played. So we flagged any scores with an out of whack score/play time ratio for further review before showing the score to anyone else.

IIRC in Puzzle & Dragons (one of the highest grossing F2P mobile games ever) the matches are purely client side, with a simple "I won" or "I lost" sent to the server after the match. I don't think it has leaderboards as a focus, which I bet is not an isolated decision. In general, the design of online games of any kind need to take into account all the potential issues & hacks and not be designed in a vacuum.

There's no universal answer to your question, but analysing behaviour of players and flagging various kinds of suspicious activity for more detailed inspection is likely the most common way. Designing the way to respond to such incidents is also non trivial, i.e. banning the player vs deleting the score, doing it quietly vs doing a large batch and prominently talking about it with the community, etc.

There are basically two low cost solutions that work well. A rolling window so your score is in the top X% out of the last 1,000 scores. People may still cheat, but doing so get's boring in the long term so most scores are real. Second validating some chunk of the game. So, for example with chess if you validate every move was valid, and then pick a few random moves and validate that's what your engine would pick.

Note, both of these fail if the high score has any real value.

PS: Another option is to more heavily validate higher scores, keep the top 0.5% honest and cheating to get a lower high score has less value.

> Another option is to more heavily validate higher scores, keep the top 0.5% honest and cheating to get a lower high score has less value.

That's one kind of thing I've thought about in the past. I'm thinking things like Game Center's global scoreboard, so if you only every check scores that are supposed to break the top 1000 then you don't have to bother checking everyone's games. If you fake a score of 270 points, well there isn't a huge benefit in stoping you.

> You could use this model of recording inputs and playing them back on the server but that seems like it would be a ton of work if your game is popular and an extraordinary cost for keeping a simple score board clean.

You only need to validate scores that would actually make it onto the leaderboard, which would be a tiny fraction of all plays. To avoid being overwhelmed by bad submissions, you flag users who send them as "don't even bother checking, just log and reject".

The real problem is RNG manipulation and TAS-ing in general. How do you to ensure a malicious user automatically can't brute force the whole tree of possible plays?

> You could use this model of recording inputs and playing them back on the server but that seems like it would be a ton of work if your game is popular

The main costs would be setting up servers / network serialization code, and isolating the game logic enough that you can reuse the same code on the client and server.

The latter is potentially useful for replay systems as well (so you can see how other top players are playing the game.)

> and an extraordinary cost for keeping a simple score board clean.

Some ways to keep costs down:

- Offload validation onto other clients (this is better suited for matchmaking based multiplayer games where you're communicating anyways, where it can be as simple as having both clients upload the score or result for a given match id - flag both clients when they disagree, whoever racks up flags consistently is cheating / has bad ram / ???)

- Only validate N% of the games from the event stream at random

- Only validate the top N% of scores from the event stream (who cares if people are cheating to give themselves terrible scores?)

> You could use this model of recording inputs and playing them back on the server

Before King was known for its mobile games they were a cash tournaments website (now royalgames.com). This is what they did as well as recording a user's mouse movements.

Perhaps you can solve this as follows. The client is going to go through a series of states, guided by some inputs. You can compute a hash from these states. Now you let the server go through the same states (using the same inputs), and compute the hash, and compare the hash codes from server and client.

This sounds prohibitively complicated (and requires work from the server). But note that the state can be a partial state (with obviously weaker protection against hacking), but perhaps still good enough.

from my recollections forever ago, RTS games like the spring engine use checksums on state to prevent manipulation. the game client gets "out of sync" if a client's checksum doesn't match. The state checksum is computed at every tick of the simulation. This makes it so you don't have to run the simulation on the server. Debugging is very hard though, and odd things like FPU precision on different processors can create all kinds of difficult bugs.

Those fpu precision issues are a nightmare. The most common way to get Around them is to do integer math instead.

One thing that makes this possible is that many of those games run st much slower update rates (typical games are 30/60hz, many rts games run at 10hz) and they run in lock step. If you have different clients with slightly different views of the world it doesn't work at all

I thought that IEEE floating point operations were well-defined, and guaranteed to always behave in the same way (but there are a few CPU flags that can influence e.g. rounding).

You could send the score on a regular basis, and check to make sure it isn't increasing at an impossible rate?

You can send the replay of client actions taken, including the random seed to be sure the board and subsequent random results are accurate. A bejeweled game probably represents a few KB of data in this format. Here's the seed, a list of which two gems were switched, and when special abilities were activated. Done.

Chess has a standard notation, and there's even tools to detect when human players are cheating by having chess engines play their moves by replaying parts of the game to those engines and checking for too many move similarities.

Build a community that's honestly interested in skill and frowns on cheating. Then trust that community to detect and flag the (hopefully very few) cheaters. An example would be Dustforce.

Of course this only works with the right community.

Essentially a social instead of a technical solution.

You could send events to the server (connected these gems, hit this target), and let the server calculate the score. Of course, that's subject to abuse as well. Short of hosting the game remotely, I'm not sure there is a solution.