In video games, most anticheat software is run clientside (e.g. PunkBuster or Valve Anti-Cheat)- but isn't one of the first rules of security to never trust the client? If so, then why do these companies not offer server side verification for video games, but rather continue to insist on trusting the client?
It's less about insisting on trusting the client and more that there is no other viable anti-cheat model. Like DRM, and in fact, anti-cheat software like PB use a form of DRM, there's little that can be done.
DRM software has mitigations in place to keep the client from poking too much, but it has to be put on the client to try to prevent the client from doing things that the media companies don't want the client doing.
Anti-cheat technology relies on similar methodology. Information about the client is gathered, sent to the server, and if a client is seen as misbehaving, through whatever series of checks are done for the specific software, it can be banned at the server.
At the end of the day, it comes down to risk management. Yes, don't trust the client is one of the first tenets of security. But for mitigating risks that occur at the client, there's a cost-benefit analysis, which is what risk management is. Is the cost of letting clients continue to bot and cheat worth losing customers who want a fair and fun game? Or should some mitigations be put in to place? PB and other software packages aren't there to entirely stop cheating, but aim to make it more expensive to cheat.
Also there is another more subtle way of limiting the clients to cheat (wall hacks,...), mostly implicated by online only games but not limited to. This is achieved by not feeding the client side all data. For example unreal engine 3 has checks if an actor is in your vicinity of visibility, if this check is positive, the server sends YOU the exact location as well as your opponent YOURS. So to say, only the server knows all positions, actions and movements of all actors on the gaming instance.
This can be read in the documentation of the unreal engine 3 / Client Server Model in the paragraph cheating, to be found here: https://udn.epicgames.com/Three/ClientServerModel.html
So to say, with advanced engines/network code and Client Server models, it is not necessarily needed to trust the client 100%. The Server can decide beforehand what the client should know, effectively LIMITING the possibilities of hacks. To go even further, the server can decide what it SHOULD know itself, not to get distracted or confused by clients sending forged packets.
Client side anticheat software in and of itself isn't about security, it's about the gameplay (and customer) experience.
Thus, security rules aren't nearly as applicable. Trusting the client "hit pixel 1056 by 1723" is very different than trusting the client "can transfer $1000 to Nigera", or that the client "can access Bob's email".
Note that I am specifically excluding financial transactions, just gameplay cheats like aimbots, big head cheats, etc.
First: There are many games, which use 100% server side validation and don't trust the client. One example: Online Poker
You simply do not send the value of any cards to the client which he cannot know. So even if he hacks the client and reads the matrix, there is nothing hidden which he can reveal and no moves he can make which he couldn't do with the regular client.
But many modern games are a lot more complex. A first person shooter for example. Here it is not so easy to decide if and how good you can see another player. You might say it is easy, if there is a wall between you two you cannot see him. And for these simple cases modern games can already cull the enemy player from your view, so you won't get the position where he is. But as soon as the enemy is in a dark corner and only barely visible the game has still to send his position to you, so you graphics device can paint him there. If you use a cheat, which paints him in bright colors you can easily spot him and cheat. This is hard to prevent, because the logic which paints him in dark colors in the shadow is very complex for games with good graphics - so rending the picture on the server and only sending you the final picture would make cheating a lot harder, but also would require a ton of resources on the server and would have the serious problem of LAG.
DELAY or LAG: The second big problem to streamed gaming is lag. If you move the mouse, you can look around very fast in a first person shooter. But sending this command over the internet and receiving the result to show on your screen will necessary take longer than rendering locally. If you have a fast internet connection you can be lucky with a Ping below 20ms, but most connections can be very unstable and the lag can go higher at times. A game which reacts that slowly will play horribly slow and be almost no fun at all. On the contrary many modern games apply a ton of techniques like move prediction, time warp and others so you can lower the perceived lag of other players by making your game compute a lot of local logic and predicting the moves of other players, so the game feels more fluid than it actually is.
Hardware/Out of the box cheating. And there are always a ton of opportunities to cheat which cannot easily be defeated by software. What about doping? (a real thing in esports) Or letting a robot play for you. Or having a webcam over your shoulder, which spots enemies on your screen and tells you where they are? Or even things like DDoS attacks from a botnet on you enemy team to disturb their communications ?
There are some possibilities to make server-supported validations. The server can test the correctness of the game code/anti cheat software like DRM protection (but can of course be spoofed). The server can also check the game logic, measure your movements, collect statistics and data about your behaviour and compare it to other players and certain limits and try to decide if you are playing abnormally or if you are breaking any rules... but nothing of this is perfect.
Most online games have some consistency check every now and then.
Player32517 moved 100 units in 3 seconds, is that possible?
However, checking if every single move is valid is an enormous amount of calculations.
Take any shooter for example:
Your average gaming pc starts to struggle if there are too many granades/enemies on your screen. This load is distributed to 20 computers.
Now imagine you would have to calculate all that again on a server and check every move, every mouse swipe, every fire trigger for cheating patterns. In real time.
Because of all this it is much cheaper or even possible at all to check every now and then if you could really have jumped that far, moved that quickly or kept your mouse exactly on the enemies head for 3 seconds before you could even see him behind that wall.
And if all that fails, you still have the community reports with video footage.
Thanks Num Lock for pointing that out:
The lag isn't caused by the logic but rather by the rendering. Calculating all the vectors for the light and animations is vastly greater than calculating if something was in range to get hit.
There's two elements to be addressed here.
Firstly, client-side cheat detection is rarely the sole element in cheat prevention. Given that server software for some games is also distributed, the server-side cheat detection software may be not be fully distributed with it in order to prevent exposing it to reverse-engineering. You can't infer a lack of server-side cheat detection from the server code you may be running vs. the server code they may run internally. Also, companies may be reluctant to discuss their anti-cheat solutions for similar reasons: obscurity isn't a bad thing to have on top of a robust solution.
Yet there's also a necessity to client-side cheat detection due to the fact that games rely on player skill. This means that cheating can happen at many levels: hardware, input, and software. Software is merely the most convenient and precise, there's very little can be done to guard against a proficient robot. In order to guard against software-based cheating, you must have some kind of resident monitor on the client to have a chance of detecting it.
Furthermore, a game simulation is complex. As you rightly stated, there is little preventing someone from building a simulated client that correctly copycats all the protocols that the game uses and can arbitrarily generate inputs at the right time in order to cheat. Just that doing so is a huge undertaking; it's far easier to attempt to break the existing client. The same goes for building a fake anti-cheat client. As such, client-side security is more a case of making things as difficult as possible rather than being 100% foolproof. Valve in particular regularly make updates to VAC to compete in a continuing battle with cheat developers.
The challenge with security like this is that you have to do the computation where the information is. You either need to do the anti-cheat computations client side, or move the information server-side so the computations can be done there. For many games, passing all of the information to the server can be exorbitantly expensive. To do so, the client would need to save off all of the user-interactions and what time they occurred. Shipping all that information to the server to do analysis is too much, so instead the computation is sent to the client.
That's not to say that's the end of it. Many games implement both client side and server side tests. Some tests can be made based on information already being sent to the server. It may not be able to catch all speed hacks as someone zigs and zags, but it could catch someone who manages to move from point A to point B far faster than the game rules allow.
There's also an intriguing option: commitments. A client could offer a cryptographic commitment describing all of the user interactions, such as a SHA-1 hash. On a command from the server, they may be obliged to provide the data which generated that hash. This pattern is used in some distributed games which have no server to keep players honest. Clients are obliged to make a commitment to actions they made in the past before other clients will send then the current data. That prevents one client from rewriting its history.
Valve does do server side VALIDATION for everything.
All client input is perfectly VALID.
Valve already does checking on valid user data. For example, the client can't say to the server, "I shot Sparkles from the CT spawn, when he was in the T spawn".
It also checks that when you buy something, you aren't trying to buy that gun on credit. If the server didn't do that, then the cheater would be buying AWPs on pistol rounds.
Cheating is VALID
The problem is that cheating (on CSGO for instance) is doing perfectly valid action (the cheats that do invalid actions, like the Spawn Teleport glitch, can be fixed easily). The problem is that cheaters use a variety of methods to enter valid input that is either enhanced or made by a computer.
In effect VAC is trying to apply the Turing Test on a player. Even a server cannot verify the identity of the agent making the decisions.
Most of the other answers focus on the technical aspects of cheat prevention, I'd like to add that VAC prevents cheating by making it economically unviable:
TL;DR: Client-side cheat protection works because the effort and skill required to trick it are high and the punishment for mistakes is severe.
Hacking involves a lot of try-and-error and even if you have full access to the source it requires a significant amount of work to find out how to modify a client whilst having it pretend that it wasn't. And all this work is rendered moot every time the client is updated.
On the other hand, if you make even the slightest mistake you risk being banned forever from all VAC servers.
There is also no point in distributing your hack, as Valve also knows how to google for cheats and once they find your hack they will add some extra detection logic to find everyone who uses it. This again discourages users from using publicly available cheat tools.
Server side checks are to make sure the operations requested by the client are legal. Basically so that you don't try to run twice as fast as you're allowed.
Client side checks are to try to verify that the decision to make that change is made by a human, not by the computer - e.g. aimbots who make legal client commands (and therefor not detectable by the server) but are still not allowed.
Also, server-side you can do post-processing of large data sets to try to determine if the player is cheating, but that's something you'd need to look at after the fact and is always an imperfect science.