The token bucket algorithm is often used in packet switched computer networks and telecommunications networks to rate-limit or throttle traffic flows.
In the CentralNic Registry Services team, we had a need to implement a light-weight rate-limiting system on the login forms which protect our Registrar Console and other internal systems. We have a wide range of security measures in place to prevent brute-force attacks against accounts with weak passwords such as two-factor authentication, auto-locking of accounts after too many failed logins and so on. However, we had no protection against brute-force password reuse attacks such as the one that recently (as of 2018) hit GitHub.
After receiving a report through our bug bounty program we decided that we needed to implement rate-limiting of the login form at the IP address level. The token bucket approach seemed like the right approach for CentralNic Registry Services. We would only need to store two pieces of data about each IP address: an integer containing the number of tokens in its bucket, and a timestamp recording when the bucket was last “topped up”. This mean that we would not be resolving one security vulnerability by introducing another in the form of a resource exhaustion attack.
Rather than use a relational database to store this information we chose to use memcached, since it's very fast, we already have a memcached system running at each of our operations centres and the data doesn't need to be persistent in the long term.
Since our registry system is written in PHP, we needed an implementation of the token bucket algorithm in that language. Some such implementations already exist, but were not compatible with the operating system and PHP version we currently have deployed in production. Therefore, we needed to roll our own. This was then integrated into the general-purpose “CRC” foundation library which supports our registry software, and which is also used by our some of our sister companies.
Below is the core of the implementation: an object method which returns a boolean if the client has hit a rate limit. The key() method is a way of turning a client identifer such as an IP address into a key that is unique for the specific application. The $this->cache object property is an instance of the memcache class (not to be confused with the memcached class: no, we don't know why PHP has two memcached client classes either!).
This allowed us to implement a per-IP rate limit on login forms across our system, without having to maintain a lot of data in a relational database.
About the author
Gavin is Head of CentralNic's Registry Services division and also Chief Innovation Officer for CentralNic Group. When this article was originally written, he was CentralNic's Chief Technology Officer, and was still allowed to write code (he isn't any more!).