Fixed-Window Rate Limiter

Challenge

Fixed-Window Rate Limiter

An API endpoint is being hammered by an attacker who wants to brute-force credentials or scrape data. Your defense is a fixed-window counter: for a given API key you keep an array of request timestamps (in seconds) and, on each new request, count how many recent requests fall inside the window. If that count exceeds the allowed limit, the request is throttled.

The asset you protect is the backend behind the endpoint; the threat is request flooding. The insecure assumption most implementations make is that the caller-supplied n (length) and window are always sane. An attacker who can influence those values (e.g. a negative or zero length, a non-positive window) can trick a naive counter into reading out of bounds or dividing by an empty window. Deny by default: validate every attacker-controllable size BEFORE you touch the buffer.

Implement:

int over_limit(const int *timestamps, int n, int now, int window, int limit);

Count how many of timestamps[0..n) fall in the half-open interval (now-window, now] and return 1 if that count is strictly greater than limit, otherwise 0.

The lower bound is exclusive and the upper bound is inclusive: a request at exactly now still counts, but one at exactly now-window has aged out.

Example

Given the array ts of request times, a 10-second window ending at time 100 that contains 7 requests:

• over_limit(ts, 8, 100, 10, 5) -> 1 (7 > 5, throttle)
• over_limit(ts, 8, 100, 10, 10) -> 0 (7 <= 10, allow)

Edge cases

• Empty (n == 0) or negative length must be rejected safely.
• window <= 0 is invalid and must be rejected.
• A NULL buffer must never be dereferenced.

Input format

The function receives a read-only int array timestamps, its element count n, the current time now, the window size window (seconds), and the allowed limit. All are passed as arguments; there is no stdin.

Output format

Return an int: 1 if the number of timestamps inside (now-window, now] is strictly greater than limit, otherwise 0. Invalid or malicious inputs return 0 (request not counted as over-limit) without touching memory.

Constraints

C11, freestanding function (no includes needed). window is expected > 0 for a valid check; n may be up to a few thousand. Do not read outside timestamps[0..n). Use a wide enough accumulator so the count cannot overflow. No dynamic allocation, no global state.

Starter code

int over_limit(const int *timestamps, int n, int now, int window, int limit)
{
    /* TODO: implement the fixed-window counter safely.
       This insecure stub trusts input and always allows the request. */
    (void)timestamps; (void)n; (void)now; (void)window; (void)limit;
    return 0;
}

Common mistakes

Using a half-open comparison on the wrong side (including now-window or excluding now); using >= instead of > against the limit so an exact-limit request is wrongly throttled; indexing the buffer before validating n and the pointer, causing out-of-bounds reads when n is negative or the pointer is NULL; treating window <= 0 as valid; accumulating the count in an int that could overflow on adversarial input.

Edge cases to handle

Empty array (n == 0) returns 0; negative/huge-negative n returns 0; NULL timestamps returns 0; window <= 0 returns 0; timestamp exactly at now-window is excluded; timestamp exactly at now is included; count exactly equal to limit returns 0 (strictly greater required); limit of 0 with any in-window event returns 1.

Background lessons

• Rate limiting and resource consumption