If you self-host services on the internet, you may have seen waves of crawlers hammering your websites without mercy.

[soblow@eldritch.cafe]

That's frightening.
Like, legitimately, I'm scared of what that means.

I'll try to ratelimit at 10req/min per ip.

[soblow@eldritch.cafe]

@lilacperegrine Are you familiar with the concept of a quadtree?

[lilacperegrine@clockwork.monster]

@Soblow
a data structure where every node has 4 children?
im sorta familiar with it, but i havent used it much

[ifixcoinops@retro.social]

@Soblow I've been following this with interest

[soblow@eldritch.cafe]

@lilacperegrine Well, I have an intuition that the problem I'm looking to solve is akin to the construction of a quadtree:
I have a list of IPv4/32. I want to generalize this list using the properties of subnets (a n subnet contains 2 n+1 subnets).
I don't have an explaination though, and my math skills are rusty...

[eragon@pl.eragon.re]

@Soblow@eldritch.cafe @lilacperegrine@clockwork.monster Seems like a cool thing to do… if only I could use university's time to do that.

[lilacperegrine@clockwork.monster]

@Soblow
so you have a list of ips, and are using a binary(or quad) tree in order to classify them into clean vs dirty?

[soblow@eldritch.cafe]

@lilacperegrine No, not really...
I talked about quadtree because that's something I manipulated and it made met think of it.
Let's take a step back and formalize the problem:

Let's assume I have a list of unique IPv4 adresses.
They are represented on 32 bits.
I want to construct a list of subnets (so still 32 bits) that summarize the list of IPs I have.

For example, if I have 192.168.1.0 and 192.168.1.1, I could generalize this with the 192.168.1.0/31 subnet (if I'm not mistaken), which contains the previous two IPs without containing any other IPs.
If it helps, represent them in binary and find the common upper bits:

11000000.10101000.00000001.00000000 (192.168.1.0)
11000000.10101000.00000001.00000001 (192.168.1.1)

The common part is everything up to the last bit, thus the mask is a `/31` which is 255.255.255.254, or in binary `11111111.11111111.11111111.11111110`.

Now, I have tens of thousands of IPs and I'd like the smallest list of subnets that includes all bad IPs without including good IPs

I'm sure there are academic papers about this, this sounds like a problem folks must already have had

[_syhmac@meow.social]

@Soblow Yeah… last time my website had been bombed like this, I decided that Cloudflare is not such a bad idea… I hope you’ll figure it out.

[stupidcamille@eldritch.cafe]

@Soblow I don't always read a blog post til the end. But when I do, it's always a banger

[soblow@eldritch.cafe]

@StupidCamille Glad you liked it!

[stupidcamille@eldritch.cafe]

@Soblow

[stupidcamille@eldritch.cafe]

@Soblow also, don't be insecure about nginx. I'm still using Apache2 and don't plan on changing anytime soon

[soblow@eldritch.cafe]

@StupidCamille I mean, Apache2 is okay for regular users, using nginx is a professional bias at this point

[nicole4fox@datastream.cortexvoid.net]

@Soblow @StupidCamille i also use nginx mostly and i setup a fail2ban that throws 444 at crawlers

[stupidcamille@eldritch.cafe]

@nicole4fox @Soblow yeah fail2ban is a must

[peq42@mastodon.social]

@Soblow how did that work for ya after a while?
I have a website thats, sadly, not self hosted(basic php host with 4 cores) and when I tried some tar pit methods it just... overloaded its CPU until the website went down for 1h

I ended up just settling with a hidden, no-follow, no index link on every page that if you click 3x, IP bans you(405 IPs banned so far)

[soblow@eldritch.cafe]

@peq42 That's the topic of a follow-up blogpost I'm writing but, basically, I rate-limit at 1 req/m the IPs that reached a given threshold (50 req / months on my iocaine maze) with an HTTP code 429.
Behind this, if any IP hits 429 too often, they get fail2banned.
So far, I'm getting a background noise of roughly 1.5kreq/min and spikes at 5kreq/min but my server survives

[peq42@mastodon.social]

@Soblow in my case it lowered the CPU usage, but I don't think the crawlers took the hint to F off as the amount of hits/day remained the same on avg x.x

[soblow@eldritch.cafe]

@peq42 you may want to use the ipset ban method then, but keep in mind the limitations!