Accurate processing of untrusted client input

A difficult problem with action-based online games is data inaccuracy caused by the inability to trust clients.

On one extreme, a game can trust the client completely. So whatever the client tells you for position, orientation, velocity, etc, is correct. This way is both easy and results in very smooth gameplay for the clients. You never have the character jerk around or other funny stuff.

However, the problem is obvious: A hacked client can then run faster, teleport, move through walls, and do other things.

Sometimes this is tolerable. For very small games, nobody would bother. For heavily moderated games, this will be obvious to an administrator, who can ban the offender. However, even that solution isn’t that great because with human greed and stupidity as it is, you’ll end up banning a large portion of your player base. This is worse in a paid game, because not only do you lose that money, but it will result in angry chargebacks and complaints. “You banned my account!!! I didn’t do anything wrong!!! WAAAHHHH!!! I don’t know who put that program on my machine!!!! WAAAHHHH!!!”

Lets avoid that hassle. Lets not give the client more power than it usually has, namely pressing keys at certain time and that’s it. There are two problems with this approach: Past inputs and inaccuracy due to entropy.

By past inputs I mean that the commands you get from the client are in reference to a gamestate some number of milliseconds ago, rather than the present. Worse, you can’t even be sure of the times that you get due to variable pings. Worst, the client may be cheating and sending you the wrong times anyway.

Accuracy is a problem because even with zero latency, if all you were to do is process remote inputs, due to calculation, framerate, and timer differences, given enough time the positions would be off anyway.

Here is one way to semi-accurately fix the problem and still look good.

1. For every game object which has untrusted client input, we need to track the state history for the server. This is basically a list of states every 50 milliseconds for the last second. State history includes everything affected by non-discrete untrusted input. Actions, position, orientation, velocity (both angular and positional), etc.

2. Each client datagram should contain the the state of the client object (same info as the history in step 1) plus a timestamp.

3. Server: On receipt of a state update datagram.
A. Validate the timestamp by clamping between the lowest and highest of the last 5 pings. If outside these ranges, add 1 point to a “Cheat metric” (explained later) for this client.
B. Given the timestamp in A. find the nearest corresponding state in the history. Compare the state in the history against what is in the datagram for reasonableness. Reasonable means the position and orientation are not off by more than what is possible given that client’s ping, and that the client does not go through walls or warp. For each value that is unreasonable, add 1 or more points to the cheat metric, depending on how unreasonable the value is. If any values are unreasonable, use the state from the history. If no values are unreasonable, use what the client has given us.
D. For the state selected in C. extrapolate that state to the present given the set of actions specified by that state (such as running forward and turning right by 1 radian per second). This doesn’t have to be perfectly accurate. We just want to make sure that the client cannot run through walls. Fill out the history with the extrapolated values, and set the current state to what we have extrapolated.
E. If any values in B. were unreasonable, flag that we need to send a timestamped state update to the sender for the sender’s own avatar (basically force them to the right spot). Otherwise, do not send state for the sender’s avatar to the sender. Signal this object as updated, so that state updates are relayed to all viewers.

4. Client: On receipt of a state update datagram.
A. Extrapolate the state in the datagram, given the timestamp in the datagram.
B. If there is a wall or other blocking objects between our current position and the position in the datagram, just warp.
C. If the position in A is really far away, just warp.
D Otherwise, subtract the state in A from our current state. Record this as a state delta, and the current time.
E. Add the state delta over a short period of time (say 250 milliseconds) to the current state.

5. Server cheat metric.
When players cheat, they usually do not just try to cheat once, but will attempt to cheat repeatedly through the game over time. The cheat metric is simply a score that goes up on suspicious input, and down over time. When the cheat metric past a threshold, it should be logged and an admin notified to watch the player. The values can then be adjusted if they are too sensitive, or action taken against the cheater.

Leave a Reply

Your email address will not be published. Required fields are marked *