Token-Bucket Rate Limiter

Challenge

Token-Bucket Rate Limiting

A public API endpoint is being hammered by scripted clients trying to brute-force credentials and scrape data. The asset you are protecting is server capacity (and everything behind the endpoint); the threat is abusive, high-volume request floods. A token bucket is the classic defense: each caller has a bucket that refills at a steady rate up to a maximum cap, and every request costs a fixed number of tokens. If the bucket cannot cover the cost, the request is throttled.

The insecure assumption to avoid: trusting that the inputs (current token count, elapsed time, cost) are well-formed. An attacker who can influence the elapsed-time value (clock rollback) or send crafted negative costs could otherwise mint free credit or trigger integer overflow to bypass the limit. Deny by default: any negative input is invalid and must be rejected.

Implement:

int tokens_after(int tokens, int cap, int refill_per_sec, int elapsed, int cost);

Compute new = min(cap, tokens + refill_per_sec * elapsed). If new >= cost, the request is allowed: return new - cost (the remaining balance). Otherwise the caller is throttled: return -1. If any argument is negative, return -1.

Edge cases: exact match (new == cost) is allowed and returns 0; refill must be clamped to cap; the refill_per_sec * elapsed product must not overflow a 32-bit int.

Input format

Five ints: tokens (current balance), cap (bucket ceiling), refill_per_sec (tokens added each second), elapsed (seconds since last refill), cost (tokens this request consumes).

Output format

An int: the remaining token balance if the request is allowed, or -1 if throttled or if any input is invalid (negative).

Constraints

All five parameters are ints. Any negative parameter makes the call invalid (return -1). Valid inputs may be large enough that refill_per_sec * elapsed overflows 32-bit int, so compute the intermediate values in a 64-bit (long) accumulator before clamping to cap. Do not read or write any memory outside the function's own locals.

Starter code

int tokens_after(int tokens, int cap, int refill_per_sec, int elapsed, int cost){
    /* TODO: implement token-bucket logic.
       - Reject any negative input (deny by default).
       - new = min(cap, tokens + refill_per_sec * elapsed), computed without overflow.
       - If new >= cost, return new - cost; else return -1. */
    return -1; /* insecure stub: always throttles, fails the tests */
}

Common mistakes

Computing tokens + refill_per_sec * elapsed in 32-bit int, letting a crafted large product overflow and wrap negative (or positive) to bypass the limit. Forgetting to clamp the refilled amount to cap. Using strict > instead of >= so an exact-cost request is wrongly throttled. Only checking that cost is negative while trusting elapsed, allowing a clock-rollback value to slip through. Returning 0 instead of -1 for a throttled request.

Edge cases to handle

Exact match (new == cost) returns 0 and is allowed. Empty bucket with zero cost returns 0. Refill that would exceed cap is clamped to cap. Negative tokens, cap, refill_per_sec, elapsed, or cost each return -1. A large refill_per_sec * elapsed product must be computed in 64-bit to avoid overflowing int and falsely satisfying the cost check.

Background lessons

• Rate limiting and resource consumption