You need to handle three basic categories of cheating:
- Sending too few updates ("starvation")
Sending too many updates ("flooding")
Sending bogus updates ("forging")
Starvation is tricky, because you want to only penalize clients who are trying to move without telling anyone about it. However, you don't want clients who are sitting still to send you 4 packets per second (or whatever) if you can avoid it. My general trick here is to send a "start/stop" message pair any time the player wants to begin or end movement. If the client claims it should be moving but starts missing required updates, lock them in place until they begin behaving again. This is also an effective anti-packet-loss solution if done carefully, since players whose connections drop will quickly come to a halt instead of just wandering away into infinite space.
Flooding is simple: if I see more than, say, 2 seconds worth of position reports from you within a 1 second period, I just boot your client entirely. There is no excuse for this and it helps avoid a class of Denial-of-Service attacks. If you want to do this right, rig it up so that your latency compensation code "knows" how bursty the client's connection has been recently. If you have a really smooth client that all the sudden starts spamming you position reports, kick the bastard ;-) The flip side of course is that you may easily get, say, 6 position updates in 1 second instead of 4 updates, due to network hiccups. So intelligent lenience can be a little tricky.
Forging is where it all gets messy, though. A common approach is to send commands from client to server, such as "move north at 1 m/s for 3 seconds" and then report your position along the way. This allows you to verify that the client is doing what it asked to do, and you can easily boot anyone who exceeds a tiny threshold of discrepancy from this planned path. Again, intelligent latency compensation can be complex, but is by no means hard to do if you think through all the edge cases on paper before writing your code.
Basically, for defense against forging, you have to follow a "promise/expectation" model. The client promises it's going to try to do X, and the server then carries on with the expectation that the client will do what it said. Any deviation and you get booted.
How difficult that really is depends on the complexity of your game simulation, but from the sound of it, that should be pretty easy to pull off in your case.
