GM / Master map hacker and general hacking and cheating th…

On May 31 2012 01:15 kmh wrote:


Again, this is addressed in the paper. Please don't blame the paper for my misinterpretation of it - you really should read it. They do discuss why sending the entire gamestate isn't feasible for RTS and go into detail that I can't go into because of space restrictions and the fact that I haven't spent enough time on the subject yet.

Like I said, my understanding is that you cannot have a fully synchronized client, i.e. have both clients simulate all movements of all units, simply because by design you will not want both clients to have full knowledge of the gamestate. If both clients have that information available to them in an unencrypted form, you cannot avoid the possibility of maphacks. However, I don't see why you couldn't simulate the movements of all units in the visibility of both players in lockstep.

However, you *can* communicate encrypted updates to the opponent and then only send the encryption keys as needed. This is done by communicating a list of what grid cells are visible to you (visibility map) as well as what units you have in each grid cell. To speed up computation, you do this hierarchically by splitting the map recursively into quadrants. You then send the changes to your opponent. In other words, you communicate your unit list and your visibility map, but do so in an encrypted fashion. Your opponent does the same to you. To avoid leaking information about the amount of units or how much of the map is available to you, you add chaff (fake data) to keep the amount of data sent constant.

Because of the encryption method used, players can decrypt V_a ^ V_b - that is, the union of the visibility map for player A as well as the union for the visibility map of player B. You cannot learn anything about the areas that aren't visible to both.

By design, this makes for the complete absence of passive attacks: i.e. maphacks and production hacks etc. However, it does nothing to prevent active attacks, such as blink hacks, burrow micro hacks, autoinject, auto-anything, adding extra units to your army, hacked build times, hacked unit stats, et cetera. Unlike maphacks however, these kinds of hacks are pretty trivial to detect post facto. That could even be made into an automatic process: i.e. to check the legality of your opponents moves after the game by uploading a signed copy of your replay after the game as well as periodically sending signed hashes of chunks of your action list to the other players during the game. That way, detecting disrepancies can be made automatic and completely traceable.

I can't answer as to how much difference this makes in lagginess off hand. In the paper, they did some analysis and came up with figures as follows: players usually only do a maximum of 2 game-state changing actions per second. The rest are camera-changes that don't change the game-state and thus don't need to be communicated. Calculating all of the encryption creates some overhead, to the tune of less than 20 microseconds per opponent in the worst case. Basically this means that you have to send in the worst case 2 encrypted state changes per second, each a few hundred bytes long, and each taking a few ten microseconds to encrypt.

As for what implications that has for the implementations of the netcode, I'm not really sure. My understanding is that you cannot send the mere input list, but rather that you have to communicate the delta of your gamestate at each simulation tick. You do not have to communicate changes that haven't happened.

It's an interesting topic, and I really don't do the researchers justice. Please don't attack my interpretation of what I've read., because I'm pretty certain I must have gotten a few things wrong when trying to relay the gist of the paper here. Instead, read the paper at http://crypto.stanford.edu/~dabo/pubs/papers/onlinegames.pdf and let me know what you think about it - also feel free to contact the researches themselves with your feedback.


---

The paper also cites another paper called "Battle of Botcraft" (available at http://www.cs.wm.edu/~hnw/paper/hop.pdf ) that proposes a method of bot detection based on machine learning methods. This is something we could already start doing right now, without any changes to any network code. By categorizing replays into "hacks" and "not hacks", and detecting common features for the hacked replays we could make hack detection automatic.

For instance, looking at the dsninetail replay, action sequences such as:

15:55 DSNiNETAiL Deselect all
15:55 DSNiNETAiL Blink (Stalker); target: x=32.3,y=46.7
15:55 DSNiNETAiL Attack; target: x=37.9,y=54.9
---
15:56 DSNiNETAiL Deselect all
15:56 DSNiNETAiL Blink (Stalker); target: x=57.8,y=45.5
15:56 DSNiNETAiL Attack; target: x=48.6,y=46.3
---
15:56 DSNiNETAiL Deselect all
15:56 DSNiNETAiL Blink (Stalker); target: x=57.8,y=45.5
15:56 DSNiNETAiL Attack; target: x=48.6,y=46.3

crop up, the same way every time. The time stamp here fails to indicate that the above sequences happen within a single frame.

Squirtle's blink micro on the other hand generates action sequences as follows:

13:59 StarTale Select Stalker x3 (10830,10834,1083c), Immortal (205ec), Deselect 2 units
13:59 StarTale Blink (Stalker); target: x=95.5,y=159.7
14:05 StarTale Select Stalker (10674), Deselect all
14:05 StarTale Blink (Stalker); target: x=97.6,y=155.2
14:06 StarTale Select Stalker x3 (306d4,206e4,10834), Deselect all

Again, the timestamp here fails to indicate that the lag between the actions is much higher: to the tune of several hundred milliseconds.


Machine learning tools could find other indicators too. Comparing the hacked replay to a pro replay you find the following split in the hack replay:

+ Show Spoiler +

Meanwhile, human players such as squirtle would have splits that generate actions as follows:

+ Show Spoiler +

There are loads of potential indicators out there to mine data from, such as click speed/accuracy etc. By comparing these sorts of action sequences and finding indicators, we could get somewhere with automatic hack detection. All we would need are corpuses of "known hack" replays as well as "known good" replays to start training.

On May 30 2012 17:19 Mendelfist wrote:
Well, in that case it's even worse. Continuously sending the current game state (encrypted) over the net is no more viable than sending parts of it on demand. There are just too many units involved in SC2. The paper focuses a lot on solving the cryptographic problem of when to lift the fog of war, and goes to length to show how efficient their algorithm is, but it does not mention that it requires a completely different network architecture than SC2 currently uses, an architecture that is so inefficient that I don't think it would be possible to use. This blog discusses exactly this problem:

http://www.altdevblogaday.com/2011/07/09/synchronous-rts-engines-and-a-tale-of-desyncs/