Anti-Cheat proposal

Make suggestions for improving one of the best games on the net!
User avatar
FiringSquad
Sergeant
Sergeant
Posts: 847
Joined: Thu Jan 26, 2006 5:53 pm
Location: Ireland

Anti-Cheat proposal

Post by FiringSquad » Mon Sep 15, 2008 2:41 pm

Cheating is a problem, but also there is the problem of false accusations and the horrible suspicious feeling you get when your opponent just won't die.
In order to get beyond this, we need a way for Admins to investigate accusations of cheating with a reasonable chance of success.

In order for this proposal to work, it would be necessary to only allow official builds for leagues.
The basic idea is this.
The server will intermittently ask for the address of a function and store the results while recording the match.
In order to test if the results are valid, an admin launches BZFlag with a special switch that allows him/her to ask BZFlag the same question. If the answers match then the client is official.

Of course the implementation will be a little more involved. This is to prevent the cheater having 2 clients running and then forwarding the queries on to the clean client and having the cheating client just act as a go-between.

For instance, the switch to query the client, should require a passphrase. When md5 encoded, this should match a constant hardcoded into the build. Only if the passphrase, matches the hardcoded constant will it be possible to ask the client directly for the results. The md5 value can be made public without divulging the actual passphrase. md5 is reasonably secure, although not completely unbreakable. If necessary some more complicated encryption method could be used. Of course the constant does not need to be made public although it would be easy enough to figure it out, even if it were obscured in the code.

The communication of addresses (and offsets from addresses) should be encoded by a random key. This same key should be used to calculate a CRC-type value (4-bytes probably enough) which is added to all communications to the server. After each communication, the value is incremented (or altered in some other reproducible way) On signout, the initial random key is transmitted to the server.

The client should only support the server check once every 10 minutes. This is to prevent a cheater building a file of valid responses.

The idea behind this is that the server will support all clients (even cheat clients) but that the admins could investigate an accusation of cheating after the fact, with good evidence either way.

Of course there are ways around this, but I believe the amount of effort involved would make it unfeasible to produce an effective cheat client for use in the leagues.

To re-cap:

Server: Who are you?
Client1: Running vers X on platform y
Server: What do you have stored at FuncX+ABCD
Client1: ScrambledResult1
Client1: I'm Hit!! <scrambled>
Client1: CU...BTW my randomkey was 0x????????

Admin: Launch official corresponding client with special flag and passphrase and randomkey=0x????????
Admin: What do I have stored at FuncX+ABCD
OfficialClient: ScrambledResult1
Admin: Same result. Looks OK.
Admin: Launch ReplayCheck for Client1 and randomkey=0x????????
ReplayCheck: Messages do not match the expected scrambled CRC. Looks like we have a cheater acting as a go-between.

So? What do you think?
Is it a runner?
Is it a problem to only allow official builds for league matches?
Have I missed an easy way to bypass this?
What can be done to improve this anti-cheat method?
Anybody out there willing to implement this?

User avatar
blast
General
General
Posts: 4744
Joined: Fri Mar 21, 2003 3:49 pm
Location: playing.cxx
Contact:

Post by blast » Mon Sep 15, 2008 3:29 pm

Why couldn't a cheat client just send the same responses? This kind of idea has been discussed many times before. It will not work. You can't trust the client.
"In addition to knowing the secrets of the Universe, I can assure you that I am also quite potty trained." -Koenma (Yu Yu Hakusho)

Image

User avatar
FiringSquad
Sergeant
Sergeant
Posts: 847
Joined: Thu Jan 26, 2006 5:53 pm
Location: Ireland

Post by FiringSquad » Mon Sep 15, 2008 4:17 pm

Only an official client will be able to respond with the correct results in all cases.
It would be possible for a cheat client to build a list of valid responses, but it would take an extremely long time to do so.
Even if a valid set of sources was used to make your build, the location of the routines would not be the same and there would also be random junk that would not match.
The only way to build a list of valid responses would be to pretend to be a server and ask a valid client for a valid response. Since you could only do this once every 10 minutes, it would take months before you would have enough valid responses to be useful.
We could also rebuild the official release occasionally (without a version change) and ask league players to use this latest build. This would force cheaters to start their valid response lists all over again.
Again, this proposal is not full-proof. it's just a method to make developing cheating clients extremely hard to do without getting caught.
The compiled code is about 75MB on the mac and is similar of other platforms. Of course it will not be possible to query all of the code-content, but certainly enough of it to make cheating extremely difficult.

When code is compiled, binary code is written for each of the routines. The location of these routines depends on many things. Also there is data used for padding that is practically random. If you compile the same code twice there is every likelihood the the executables will not match exactly. Once players are forced to use the official build (and not build their own from the official sources), we can ask the client questions that only an official client can answer.

For example, If functionA is 100 bytes long in the executable and we ask for functionA+105 then the client will reply with random junk that is only true for that exact build.

I am simplifying this a little, in fact, in most cases a rebuild will produce almost the same result and deciding how large of an offset can reliably be used is certainly non-trivial task but the end result is that a cheater can not remain impervious. Their client will not be able to respond with a valid answer in all cases.

We could also mix thing up by asking questions like give me the difference between Address of functionA and address of functionB.

Let me put it this way.
If you were to build a cheat client. How would you circumvent this?
If you show me that it's feasible, then I will agree that this will not work.
I think that you will find it's harder than you think.

User avatar
blast
General
General
Posts: 4744
Joined: Fri Mar 21, 2003 3:49 pm
Location: playing.cxx
Contact:

Post by blast » Mon Sep 15, 2008 4:30 pm

How do you define an "official" client? You do realize that different linux distros build their own binary, right? Or think about distros like Gentoo that are source based. How would you verify that all of these were legit? The game is open-source, so your idea is not going to work. I don't think you actually understand what you are talking about.
"In addition to knowing the secrets of the Universe, I can assure you that I am also quite potty trained." -Koenma (Yu Yu Hakusho)

Image

User avatar
JeffM
Staff Sergeant
Staff Sergeant
Posts: 5173
Joined: Fri Dec 13, 2002 4:11 am
Location: https://discord.gg/NN9uAvx
Contact:

Post by JeffM » Mon Sep 15, 2008 4:41 pm

1) we can not distribute closed source binaries, it's against the license.
2) you can not trust ANY data from the client.
3) it is not feasible to build binary builds for every OS.

The addresses of functions is not the same on every system, also we don't provide binary builds for everyone.

It would be trivial to find out what your "special" client was doing by just looking at the network data, and then make a moded client do the same. Or just have a moded client call the official client to get the handshake code it needs.

This is NOT the way we want to go. The rules for the game are very well known. The best solution for us is to ensure that all input into the game state fits into those rules. This can be done with an authoritative server.

User avatar
FiringSquad
Sergeant
Sergeant
Posts: 847
Joined: Thu Jan 26, 2006 5:53 pm
Location: Ireland

Post by FiringSquad » Mon Sep 15, 2008 5:12 pm

In order to mix thing up even more, the code could be peppered junk code and built. The junk code could be removed from the official sources.

for example:

Code: Select all

#ifdef __UseJunkCode__
#define JUNK_CODE(Num,Str) {int x = Num; \
if (!x) \
if (x > strlen(Str)) \
{ \
#include "JunkCode.inc"
}
#else
#define JUNK_CODE(Num,Str)
#endif

for (int32 i = 0; i< Something; i++)
{
JUNK_CODE(__LINE__, __FILE__)
PerformSomeFunction(i);
}
The code contained within "JunkCode.inc" will never be executed and once the JUNK_CODE(__LINE__, __FILE__) lines are removed from the sources there will be no way to reproduce the original build.

The executables can be given as official league builds downloadable from the league sites.

User avatar
Mucho Maas
Private First Class
Private First Class
Posts: 515
Joined: Tue Sep 21, 2004 5:14 pm

Post by Mucho Maas » Mon Sep 15, 2008 5:12 pm

JeffM wrote:This is NOT the way we want to go. The rules for the game are very well known. The best solution for us is to ensure that all input into the game state fits into those rules. This can be done with an authoritative server.
The rules can only verify if the tank doesn't do things that the tank shouldn't be doing. But adding a bit of lag and jitter to the rules, the rules get all blurry and are only helpful for the most blatant cheats, like jumping on a no-jumping server.
What about cheats that help you to see things you are not supposed to see? And I am not talking about seeing tanks you shouldn't be seeing on radar or hud.
"meet the new fo0 , same as the old f0o ... no no no .. don't get fo0'ed again ... " - The Who

User avatar
joevano
General
General
Posts: 1863
Joined: Sat Jun 18, 2005 1:08 pm
Location: South Bend, Indiana, USA

Post by joevano » Mon Sep 15, 2008 5:16 pm

OK guys what part are you not listening to?

1. Any response can be faked, it is open-source they can read all the code
2. Binaries cannot possibly be compiled for all the different linux distros that people use, and the source code is always available

This has been hashed over hundreds of time, it will not work that way in an open-source application
FiringSquad wrote: The code contained within "JunkCode.inc" will never be executed and once the JUNK_CODE(__LINE__, __FILE__) lines are removed from the sources there will be no way to reproduce the original build.

The executables can be given as official league builds downloadable from the league sites.
Once you remove them, how do you add them back? The client is under constant development and needs to be built regularly. The official source is in SVN, so the removals can always be tracked.
Foo wrote:What about cheats that help you to see things you are not supposed to see? And I am not talking about seeing tanks you shouldn't be seeing on radar or hud.
That will be handled by the server only providing the info to the client that it can see. That is down the road though.
Last edited by joevano on Mon Sep 15, 2008 5:29 pm, edited 1 time in total.
There is nothing worse than aggressive stupidity. -- Johann Wolfgang von Goethe
"How many legs does a dog have if you call his tail a leg? Four. Calling a tail a leg doesn't make it a leg." -- Abraham Lincoln

User avatar
FiringSquad
Sergeant
Sergeant
Posts: 847
Joined: Thu Jan 26, 2006 5:53 pm
Location: Ireland

Post by FiringSquad » Mon Sep 15, 2008 5:28 pm

JeffM wrote:1) we can not distribute closed source binaries, it's against the license.
That's enough for me. Not feasible then. :(

Without an official client, there will always be room for client enhancement.
Unfortunately an authoritative server can not cater for enhancements to the client such as full-screen radar etc. and I see now that distributing binaries is against the license so that there can never be an official client.
JeffM wrote:It would be trivial to find out what your "special" client was doing by just looking at the network data, and then make a moded client do the same. Or just have a moded client call the official client to get the handshake code it needs.
Well the idea is dead in the water now but what you describe here would not be trivial at all. The random key is only divulged at the end and all communication is verifiable, which means that you would also need the official client to give all reports back to the server. Once the official client's tank dies and you don't, it would be impossible to keep in sync.

User avatar
CannonBallGuy
Private First Class
Private First Class
Posts: 2083
Joined: Wed Apr 12, 2006 1:31 am
Contact:

Post by CannonBallGuy » Mon Sep 15, 2008 5:33 pm

Wow.
What is stopping me from downloading the source for this "official" (??) version and changing the "true" to "false in the line that tells the server "I got shot, I am dead." as I did back in the 2.0.8-ish source? I wouldn't need to touch any of the other magic code you're spewing out the wrong end that tells the server that I am not cheating.
Image

Merry Christmas!

"Look, if I don't buy booze for the kids, I don't get any incriminating pictures to show to their parents, my business goes down the sink, my girlfriend leaves me and the baby goes on ebay. So help me search..."

"go Play With Toys urself in a dark alley u donkey ******" - Lt-Kirby2007

User avatar
JeffM
Staff Sergeant
Staff Sergeant
Posts: 5173
Joined: Fri Dec 13, 2002 4:11 am
Location: https://discord.gg/NN9uAvx
Contact:

Post by JeffM » Mon Sep 15, 2008 5:34 pm

Foo
there is no way to get rid of all cheats. That's just a fact of life. What we can do is minimise the cheats that can be done.

There will always be the chance that some subtle cheat effect is legit. We feel that it is much more productive to first get rid of the major cheats ( godmode, etc.. ) before working on the subtle ones, as they are the ones that outright ruin the game.

FiringSquad
please read the various comments. Anything that uses binary offsets into an executable will not work, since those offsets can simply be faked.

While I know how are your thinking through this in your head ( I've done it myself before ), this method of "security" is not well suited for our game, mostly due to our distribution system. The core issue with games is the fact that the client can not be trusted. And all you are doing is trying to shuffle what is trusted in hopes that it can not be faked. This is not a solid foundation.

I find that it helps to not get buried so much in the technical details intialy, like you seem to be, and start your design work from a very top level. If you look at it from there, you will see that you are still basically trusting code that is running on the client, code that you have no way to ensure is unmodified, since all you are doing is looking at the output. This is exactly what we do today.

We are an open source project, part of our goal is to allow the software TO be modified, that is why we have our license.

User avatar
FiringSquad
Sergeant
Sergeant
Posts: 847
Joined: Thu Jan 26, 2006 5:53 pm
Location: Ireland

Post by FiringSquad » Mon Sep 15, 2008 5:34 pm

donny_baker wrote:Once you remove them, how do you add them back? The client is under constant development and needs to be built regularly. The official source is in SVN, so the removals can always be tracked.
For this idea, I intended that an official League build would be made from sources that were not publicly available. This set of sources would be made by liberally peppering the official code with "JUNK_CODE".
I see now though that this would be against the license.
Pity.

User avatar
FiringSquad
Sergeant
Sergeant
Posts: 847
Joined: Thu Jan 26, 2006 5:53 pm
Location: Ireland

Post by FiringSquad » Mon Sep 15, 2008 5:42 pm

CannonBallGuy wrote:Wow.
What is stopping me from downloading the source for this "official" (??) version and changing the "true" to "false in the line that tells the server "I got shot, I am dead." as I did back in the 2.0.8-ish source? I wouldn't need to touch any of the other magic code you're spewing out the wrong end that tells the server that I am not cheating.
I feel like I'm flogging a dead horse since my solution can never be implemented as it breaks the distribution license, but in the spirit of clarity...
Once you rebuild your sources with the tiny modification (indeed even without modification) your binary will differ from the official build and can no longer respond with the correct answers.
It's true that you would not die during the match, but upon examination of the replay, it could be shown that you were not using an official build and would therefore be considered cheating.

User avatar
JeffM
Staff Sergeant
Staff Sergeant
Posts: 5173
Joined: Fri Dec 13, 2002 4:11 am
Location: https://discord.gg/NN9uAvx
Contact:

Post by JeffM » Mon Sep 15, 2008 5:52 pm

you seem to be implying that there would be some kind of binary offsets database on the server? Or is there some other method where you know that the response from the client isn't "official"? And how do you tell if that response is from unmodified code? if the client can also build up a database of valid offsets from a real client and just use that how could you tell the difference?

User avatar
FiringSquad
Sergeant
Sergeant
Posts: 847
Joined: Thu Jan 26, 2006 5:53 pm
Location: Ireland

Post by FiringSquad » Mon Sep 15, 2008 6:07 pm

blast wrote:How do you define an "official" client? You do realize that different linux distros build their own binary, right? Or think about distros like Gentoo that are source based. How would you verify that all of these were legit? The game is open-source, so your idea is not going to work. I don't think you actually understand what you are talking about.
Actually I had ideas to get around these problems but I didn't want to get into all that on the first post. Firstly, while BZFlag might support all distros that does not mean that the leagues would have to. I would have been surprised if the exclusion of source-based distros from the leagues would have been that much of a problem since it's a pretty good bet that those using distros such as Gentoo invariably also have other distros that they can boot from where they can launch downloaded binaries directly. And yes I understand that this creates a security breach etc.

I know many people that have given up playing BZFlag because of real or perceived cheating. Are these people less important than die-hard Gentoo users?

Let BZFlag be all-embracing. No problem. I just wanted to carve out a little restricted spot where leagues could go about their business with reasonable assurance that those playing were not cheating.

User avatar
FiringSquad
Sergeant
Sergeant
Posts: 847
Joined: Thu Jan 26, 2006 5:53 pm
Location: Ireland

Post by FiringSquad » Mon Sep 15, 2008 6:12 pm

JeffM wrote:you seem to be implying that there would be some kind of binary offsets database on the server? Or is there some other method where you know that the response from the client isn't "official"? And how do you tell if that response is from unmodified code? if the client can also build up a database of valid offsets from a real client and just use that how could you tell the difference?
Nobody would know if it was a valid response until it was tested against a valid client.
The server does not respond "Cheat". Instead an admin would look at the messages from the client and validate them against a valid client. So long as a player does not get inspected by an admin, nobody would be aware that that player was cheating.

What causes most frustration is that you might feel (wrongly or rightly) that your opponent is cheating and even if you bring it to the attention of the admins you know that there is nothing they can do.

I just wanted to provide the admins with a way to investigate an accusation and provide players with the comfort that cheaters would eventually be found out.

As for the client building up a database of valid responses. How can you do this efficiently without modifying the client and therefore producing invalid results?

User avatar
FiringSquad
Sergeant
Sergeant
Posts: 847
Joined: Thu Jan 26, 2006 5:53 pm
Location: Ireland

Post by FiringSquad » Mon Sep 15, 2008 6:24 pm

FiringSquad wrote:As for the client building up a database of valid responses. How can you do this efficiently without modifying the client and therefore producing invalid results?
Actually I can think of a way around this. :-)

Once you locate the binary code where the 10 minutes difference is tested, you can alter the binary code directly to return that 10 minutes have passed.

Since almost none of the binary code would be effected the results would be 99.999% correct.

In turn of course, I can think of ways to circumvent this circumvention... :)

e.g. CRC values for ranges of code, ways to hide the test for 10 minutes so that it's extremely difficult to locate, introduction of time-base control-flow so that somebody stepping through the code with a debugger would not follow the usual code-path, etc.

User avatar
JeffM
Staff Sergeant
Staff Sergeant
Posts: 5173
Joined: Fri Dec 13, 2002 4:11 am
Location: https://discord.gg/NN9uAvx
Contact:

Post by JeffM » Mon Sep 15, 2008 6:28 pm

so the server has to have a copy of all possible valid clients? since the cheater could also have access to the server code that does this validation ( as it is open source ) could they not just go get valid responses from an unmodified client and send those back.

I understand what you are trying to do, but I don't feel you fully understand the logistics of what you are proposing, and how it could be worked around.

As for your last point, what you don't see is you could modify your client to NOT pull it's data from it's own running image, but from another one. If you make this mod to your client, then the transition you send back to the server is not based on the modded client, so the server never sees any evidence that you have modded the code. Basically since you trust the messages, it becomes simple to sidestep the code that looks for a modded client.

Your system dosn't ensure that the code is not modded, it simply ensures that the message from the client match some known good set, and that message can be faked by simply changing where it gets it's information from.

The system you are talking about is similar to how WoW and other MMOs work. It works (partly) for them for a couple reasons. 1) closed source, 2) constant updates, 3)required logins.

Since they constantly update the software and only run on a limited platform set, they can do binary checks. They can be assured that everyone is using the same binary client. They also have a way to track that back to the customer. These things mean that people that do cheat, are only able to do so for a short time ( until the next forced update)

In our case we don't have any of those things. Like I say, I understand where you are going, but this is not something that would benefit us, all it would do would limit our users, make a LOT more work for people, and provide even more confusion since the results of it could not be trusted ( someone who simply built from source because the bin we made doesn't work with there version of the C runtime on there distribution could be flaged as a cheater by you, where someone who mods out the messages and DOES cheat is said to be clean ).

Basicly the time and effort would be better spent on verify the input for the major cheaters. That is a much more quantifiable thing, since you can show "here" is where the input is bad.

User avatar
FiringSquad
Sergeant
Sergeant
Posts: 847
Joined: Thu Jan 26, 2006 5:53 pm
Location: Ireland

Post by FiringSquad » Mon Sep 15, 2008 6:43 pm

JeffM wrote:so the server has to have a copy of all possible valid clients? since the cheater could also have access to the server code that does this validation ( as it is open source ) could they not just go get valid responses from an unmodified client and send those back.
No.
It's not enough to return the results from an unmodified client, since they are scrambled with the current state of the client. Unless you know what the random key of the running official client is, you can not fake your messages to the server. Since the official client only divulges this key at the end, the messages you send from your cheat client can be shown to be invalid, since the extra CRC-value does not match the random-key.

One way around this would be to tamper with the production of this key by the official client by modifying the binary code directly. Again there are ways to combat this also, some of which are listed above.

User avatar
FiringSquad
Sergeant
Sergeant
Posts: 847
Joined: Thu Jan 26, 2006 5:53 pm
Location: Ireland

Post by FiringSquad » Mon Sep 15, 2008 6:51 pm

JeffM wrote:Your system dosn't ensure that the code is not modded, it simply ensures that the message from the client match some known good set, and that message can be faked by simply changing where it gets it's information from.
Not a "known" good set, rather an unknown but easily verifiable set. The difference is that an admin can easily test if something is correct without knowing how to create a valid result.
It's a relatively easy task, for instance, to check if AxB=C, even for extremely large values of A, B and C. But it's far more difficult to split C into factors A and B.

I wanted to do something similar here. Make it difficult to calculate valid responses but easy to validate if they were correct.

User avatar
JeffM
Staff Sergeant
Staff Sergeant
Posts: 5173
Joined: Fri Dec 13, 2002 4:11 am
Location: https://discord.gg/NN9uAvx
Contact:

Post by JeffM » Mon Sep 15, 2008 6:53 pm

How is this key communicated to the server?

User avatar
FiringSquad
Sergeant
Sergeant
Posts: 847
Joined: Thu Jan 26, 2006 5:53 pm
Location: Ireland

Post by FiringSquad » Mon Sep 15, 2008 7:01 pm

JeffM wrote:How is this key communicated to the server?
Upon sign-off, the last thing sent is this initial encryption key. In order to check if a client was "unofficial", you locate this message and then go back to the start and validate all messages to the server. If the CRC value does not match then an official client was not responsible for all messages.

User avatar
JeffM
Staff Sergeant
Staff Sergeant
Posts: 5173
Joined: Fri Dec 13, 2002 4:11 am
Location: https://discord.gg/NN9uAvx
Contact:

Post by JeffM » Mon Sep 15, 2008 7:03 pm

what "messages" are you talking about? messages containing offsets or something?

also what happens if the client drops connection? are all droped connections cheaters?

User avatar
FiringSquad
Sergeant
Sergeant
Posts: 847
Joined: Thu Jan 26, 2006 5:53 pm
Location: Ireland

Post by FiringSquad » Mon Sep 15, 2008 7:14 pm

JeffM wrote:what "messages" are you talking about? messages containing offsets or something?

also what happens if the client drops connection? are all droped connections cheaters?
All messages from the client to the server should carry a validation value that is calculated using a key that is not revealed until the end.

As for dropped connections, this will look very suspicious if a particular client always drops a connection before signing off properly and anyway this could be easily circumvented by producing a logfile for keyvalues that could not be sent. Then all you need to do to clear your name is send this file to the admin doing the investigation.

User avatar
JeffM
Staff Sergeant
Staff Sergeant
Posts: 5173
Joined: Fri Dec 13, 2002 4:11 am
Location: https://discord.gg/NN9uAvx
Contact:

Post by JeffM » Mon Sep 15, 2008 7:18 pm

what prevents a moded client from computing it's own validation value based off of faked info then just sending a CRC that works with the faked info at the end?

Post Reply