Using transaction rate-limiting to improve service reliability

I develop and publish multiplayer games for a living, and have discovered some useful solutions for running reliable online services. The one I’m writing about today is how to implement reasonable usage limits so that services are less likely to be abused by hackers.

Y’see, hackers find ways to manipulate games by simulating the behavior of human players, but in ways that exploit bugs and misfeatures; for example, by performing tasks faster than humans could ever hope to do. One example is a “speed hack”, where a player is able to perform actions like swinging a sword more rapidly than should be possible according to the rules of the game. If you’ve ever seen a monster go from full health to instant death in a flurry of blows you’ve likely seen a speed-hack.

Now honestly a speed hack doesn’t sound like such a bad thing; before I was a game programmer I speed-hacked games myself, and thought it was more fun than playing! And I also had to “slow-hack” several older games (including one I developed — Warcraft) to make them playable on fast computers, because the programmers (me included) had forgotten that computers keep getting faster every year.

But then there are professional cyber-criminals, who steal accounts, use speed-hacks to generate lots of game-gold, and sell it for real money to other players, something known as Real Money Trading, or RMT for short. And with such hacks it becomes impossible for honest players to keep up. So what’s to be done?

The code I’ve shared below implements rate-limiting useful for preventing many forms of speed hacking. I’ve used similar code for login rate-limiting, to prevent hackers from brute-force cracking account passwords. It can be used to moderate online chat so that one person can’t “flood” a channel with messages. It’s great for transaction rate-limiting to ensure that no one person can overwhelm a server with requests. And in fact I’ve used it to successfully mitigate distributed denial of service (DDOS) attacks, which I’ll detail in a future article.

Here’s how to use the rate-limiter:

// Using these values a player can attempt to login once
// every 30 seconds, but with as many as ten login attempts
// in a burst. While this sounds like a lot many players
// forget their passwords and need a number of attempts to
// remember it, which I discovered by analyzing log files.
// They should try LastPass, which is an awesome solution
// to this problem.
const unsigned LOGIN_COST_MS      = 30 * 1000;
const unsigned MAX_LOGIN_COST_MS  = 10 * LOGIN_COST_MS;

ErrorCode CPlayer::PlayerLogin () {
    if (!m_rateLimiter.AddTime(LOGIN_COST_MS, MAX_LOGIN_COST_MS))
        return ERROR_LOGIN_RATE_LIMIT;
    ... login code here
}

In any event, here’s the code, which is surprisingly trivial considering how powerful it is. The algorithm is a modified form of the “Leaky Bucket Algorithm as a Meter“, but uses the passage of time instead of incrementing a counter to perform its magic.

RateLimiter.h definitions:

class CRateLimiter {
public:
    CRateLimiter ();
    bool AddTime (unsigned costMs, unsigned maxCostMs);

private:
    unsigned m_timeMs;
};

RateLimiter.cpp implementation:

CRateLimiter::CRateLimiter ()
:   m_timeMs(PlatformTimeMs())
{}

bool CRateLimiter::AddTime (unsigned costMs, unsigned maxCostMs) {
    ASSERT(costMs < maxCostMs);

    // Reset rate-limiter time value if it has expired
    // - handles integer overflow safely
    unsigned currTimeMs = PlatformTimeMs();
    if ((int) (currTimeMs - m_timeMs) > 0)
        m_timeMs = currTimeMs;

    // Has the user accrued too much time-cost?
    // - handles integer overflow safely
    unsigned newTimeMs = m_timeMs + costMs;
    if ((int) (newTimeMs - currTimeMs) >= (int) maxCostMs)
        return false;

    m_timeMs = newTimeMs;
    return true;
}

And somewhere you’ll have to define the PlatformTimeMs function:

unsigned PlatformTimeMs () {
#if defined(_WINDOWS_)
    return GetTickCount();
#else
    #error Your implementation here
   // something like clock_gettime(CLOCK_MONOTONIC, ...) for Unix/Linux
#endif
}

I hope you'll find this code useful for your project, and would enjoy hearing about the novel purposes you find for it.