Formula to calculate logarithmic curve in the context of IT security

Question

Background

I'm actually a dev, but I think this question fits here as its about maths. I'm implementing a site wide throttle on too many failed requests as protection against distributed brute force attacks.

The question I am stuck with is, after how many failed login requests should I start to throttle?
Now one reasonable way is, as mentioned here "using a running average of your site's bad-login frequency as the basis for an upper limit". If the site has an average of $100$ failed logins, $300$ (puffer added) might be a good threshold.

Now I don't have a running average and I don't want someone having to actively increase the upper limit as the user base grows. I want a dynamic formula that calculates this limit based on the active users amount.

The difficulty is that if there are only a few users, they should have a much higher user to threshold ratio than let's say $100,000$ users. Meaning that for example for $50$ users the limit could be set at $50\%$ of the total user count which means allowing $25$ failed login requests site-wide in a given timespan. But this ratio should decrease for 100k users, the threshold should be more like around $1\%$. $1000$ failed login requests in the same let's say hour, is a lot (probably not accurate at all I am not a security expert, the numbers are only examples to illustrate).

The Question

I was wondering, is there any mathematical formula that could archive this in a neat way?

This is a chart of what I think the formula should be calculating approximately:

Here is what I have now (I know it's terrible, any suggestion will be better I'm sure):

$threshold = 1;
if ($activeUsers <= 50) {
    // Global limit is the same as the total of each users individual limit
    $threshold *= $activeUsers; // If user limit is 4, global threshold will be 4 * user amount
} elseif ($activeUsers <= 200) {
    // Global requests allows each user to make half of the individual limit simultaneously
    // over the last defined timespan
    $threshold = $threshold * $activeUsers / 2;
} elseif ($activeUsers <= 600) {
    $threshold = $threshold * $activeUsers / 2.5;
} elseif ($activeUsers <= 1000) {
    $threshold = $threshold * $activeUsers / 3.5;
} else { // More than 1000
    $threshold = $threshold * $activeUsers / 5;
}
return $threshold;

Answer 1

TL;DR $$y = 659.113 \log\left(\frac{x}{240.399} + 1\right) + \frac{-1213.555 x}{x + 739.845}$$

---

Let $f: [0, +\infty) \to [0, +\infty)$ be the function that maps the number of users to threshold, i.e. the green curve

$f$ should satisfy these properties:

1. $f = \Theta{(\log(x))}$ as $x \to +\infty$ by assumption
2. $f$ is infinitely differentiable (we take the derivatives at $x = 0$ to be right-handed derivatives at $0$, and say it is differentiable at $0$ if right-handed derivatives exist at $0$)
3. $f(0) = 0$ from the graph
4. $f'(0) \approx 1$ since $f$ more or less coincides with the blue line of slope $1$ as $x \to 0^+$
5. $f'(x) > 0$ on $[0, +\infty)$ since $f$ is strictly increasing
6. $f''(x) < 0$ on $[0, +\infty)$ since $f$ is strictly decelerating

To fit the green curve, we first make some measurements (blue dots). Then, we use R to perform regression analysis (using the nls_multstart function from the nls.multstart package).

Because of the $\Theta{(\log(n))}$ requirement, the obvious choice is to assume $y = a \log (\frac{x}{b} + 1)$ for some unknown $a, b \in \mathbb{R}$. Unfortunately, this gives us a poor fit.

We need to improve our model. To proceed, let's assume there is some correction term such that $y = a \log(\frac{x}{b} + 1) + \mathcal{O}(1)$. A commonly used $\mathcal{O}(1)$ nonlinear model is $\frac{rx}{x + s}$ for some unknown $r, s \in \mathbb{R}$. So let's add it to our model $$y = a \log\left(\frac{x}{b} + 1\right) + \frac{rx}{x + s}$$

nls_multstart finds us the following best fit (rounded to 3 decimal places): $$y = 659.113 \log\left(\frac{x}{240.399} + 1\right) + \frac{-1213.555 x}{x + 739.845}$$

From the above plot, we can see the best fit curve closely approximates the data points.

The above residual plot is also roughly symmetric with respect to the $x$-axis.

The above normal quantile-quantile plot is also roughly a straight line.

Next, we need to show properties $1$ - $6$ holds. Property $1$ obviously holds because $y = \Theta(\log x) + \mathcal{O}(1) = \Theta(\log x)$ as $x \to \infty$. To see property $2$ holds, observe

$$f'(x) = \frac{a}{x + b} + \frac{rs}{(x + s)^2} = \frac{a(x + s)^2 + r s (x + b)}{(x + b)(x + s)^2}$$

Now we can obtain $f^{(k)}$ by keep applying the quotient rule. Because of how quotient rule works and $f'$ being a rational function, $f^{(k)}$ can only be non-differentiable at $-b = -240.399$ or $-s = -739.845$, which means $f$ is infinitely differentiable on $[0, +\infty)$.

Property $3$ holds by simple computation. Property $4$ holds because $$f'(0) = \frac{659.113}{0 + 240.399} + \frac{-1213.555}{(0 + 739.845)^2} = 1.101... \approx 1$$

Now $f'(x) = 0$ exactly when $$a(x + s)^2 + r s (x + b) = 659.113 x^2 + 77440.315994 x + 1449386311.619988 = 0$$ which has negative discriminant, implying $f'$ has no real roots and hence never crosses the $x$-axis. From above, $f'(0) = 1.101... > 0$ and $f'$ is differentiable hence continous on $[0, \infty)$. By the Intermediate Value Theorem, $f'(x) > 0$ on $[0, +\infty)$ holds (property $5$). Similar arguments show $f''$ has no non-negative real roots, continous, take a negative value at $x = 0$, and hence property $6$ holds again by the IVT.

---

Here is the R code I use for regression and plots:

## To the extent possible under law, the author(s) have dedicated all
## copyright and related and neighboring rights to this software to the
## public domain worldwide. This software is distributed without any
## warranty.
You should have received a copy of the CC0 Public Domain Dedication
along with this software.
If not, see <https://creativecommons.org/publicdomain/zero/1.0/>.
library('nls.multstart')
options(digits=8) # show 3 decimal places in summary
draw the residual plot using the x data points and residuals
residual_plot <- function(x, res)
{
    plot(x, res, ylab='Residuals')
    abline(0, 0)
}
draw the normal quantile-quantile plot using the residuals
norm_q_q_plot <- function(res)
{
    qqnorm(res)
    qqline(res)
}
draw the best fit curve using the x, y data points
and a function f taking x data points to best fit value
best_fit_curve <- function(x, y, f)
{
    plot(x, y)
    lines(x, f(x), col='red')
}
data points
x <- 0:41 * 25
y <- c(  0,  24,  48,  68,  84, 102, 114,
       128, 142, 152, 164, 174, 182, 194,
       202, 212, 218, 230, 236, 244, 252,
       260, 268, 274, 282, 288, 296, 302,
       308, 316, 322, 328, 336, 342, 348,
       354, 360, 366, 372, 378, 384, 390)
best fit model of the equation a * log(x / b + 1) + r * x / (x + s)
model <- nls_multstart(y ~ a * log(x / b + 1) + r * x / (x + s),
                       iter=500,
                       start_lower=-rep(max(x), 4),
                       start_upper=rep(max(x), 4),
                       supp_errors='Y')
compute best fit value from x data points using the best fit model
f <- function(x)
{
    coefs <- round(coef(model), 3)
    coefs['a'] * log(x / coefs['b'] + 1) +
        coefs['r'] * x / (x + coefs['s'])
}
residuals
res <- y - f(x)

Answer 2

I ended up not using some math formula but a ratio of unsuccessful to total login requests.
Code looks like this:

$loginAmountStats = $this->requestTrackRepository->getLoginAmountStats();
// Calc integer amount from given percentage and total login
$allowedFailureAmount = $loginAmountStats['login_total'] / 100 * $this->settings['login_failure_percentage'];
if ($loginAmountStats['login_failures'] > $allowedFailureAmount) {
    // If changed, update SecurityServiceTest distributed brute force test expected error message
    $msg = 'Maximum amount of tolerated requests reached site-wide.';
    throw new SecurityException('captcha', SecurityException::GLOBAL_LOGIN, $msg);
}