Simple IP-based rate limiting seems quite effective to all but the most determined abuser.
Most (noticeable) abusers are quite determined. They will try Tor, then various anonymizer proxies (forcing you to block all of them or give up), then sometimes Amazon EC2 instances or other VPS, or large public proxies / ISP proxies that you cannot block. In Germany, they can also use cheap DSL where they can switch to new IP addresses almost instantaneously (T-Online is a godsend for abusers/scrapers).
> In Germany, they can also use cheap DSL where they can switch to new IP addresses almost instantaneously
That one is easy to reduce the effect of: as well as a per-IP limit have a per-/24 limit that is much lower then 256 times the single address limit. To avoid seeming to be too unfair to other people on the same ISP who happen to be at an address next to a heavy-but-not-abusive user make this limit's bucket refill more often (i.e. if you limit to 100 requests/day per IP, try 100 requests/hour per 256 address block).
You might consider different granularities instead of or as well as /32 and /24. It is not uncommon for a small organisation to have a /29 or /28 allocated (heck, I have a /29 on my line at home as I host a couple of services from it that need their own address). Perhaps set limits for granularities of /32, /28, /24 and /20? Of course this requires development effort, implementing an efficient method of enforcing these limits, but not lots.
> They will try Tor, then various anonymizer proxies (forcing you to block all of them or give up)
Are there really enough reliable cost-free options out there to make that a massive problem? A few determined people will use more resource than you wont by these methods, but the majority will either put up with the rate limit, pay what-ever you are asking for a less limited option, or do somewhere else (the third option being something you'd prefer didn't happen, of course, but you'll always lose some users by refusing to give them the moon on a stick).
> Amazon EC2 instances or other VPS, or large public proxies / ISP proxies that you cannot block
While you can't block them, you can apply rate limits at multiple granularities as mentioned above to limit their effect. To reduce the effect of ISP proxies on HTTP APIs force the use of HTTPS (less HTTPS traffic goes via a proxy than does HTTP traffic - ISPs that use transparent proxies for HTTP caching don't do the same for HTTPS as there would be no point).
THE THING NO ONE HAS MENTIONED YET
Of course this all changes a little once you consider IPv6. A per address limit is meaningless when everyone has a /64 or wider to play with so you are going to have to implement ranged limits (perhaps with gradiated limits like above for /64, /56, /48, ...) if you are limiting by address, and you are going to limit by ISP when trying to limit by individual more often than you will filtering IPv4 addresses this way (some VPS providers hand out small numbers of v6 addresses to each VM so they presumably use one /64 for everyone, where-as I have a /64 allocated to my home line.
Perhaps set limits for granularities of /32, /28, /24 and /20?
Our last case of T-Online abuse originated from 79.192.0.0/10 (e.g. 79.241.205.250, 79.241.223.141, 79.241.207.37 in rapid succession) and there's not much we could do about it (we blocked the changing IPs for 15 minutes each time and hoped we didn't lose too many legitimate users who happened to get one of the blocked IPs).
Are there really enough reliable cost-free options out there to make that a massive problem?
Apparently there are hundreds of free/open proxies out there. They don't seem to change often and there are some lists of such IP adresses circulating the web, so it's possible to keep up with those. But it's a hassle...
While you can't block them (EC2)
Actually with obvious server/VPS addresses, blocking is feasible for web sites (not APIs!) because the chances that legitimate website visitors will be affected, are slim.
IPv6
Indeed, but at least the problem of rapidly changing IPv4 addresses will probably disappear there (you block the offender's /64 and he's not likely to get another quickly).
> you block the offender's /64 and he's not likely to get another quickly
That might not always be the case. The /64 I have is from a /48 and apparently I could have other /64s from that block mapped to this line if I wish (http://aa.net.uk/kb-broadband-ipv6-tech.html).
This could be an uncommong perculiarity of course, A&A are in the habit of doing things a little differently to other ISPs (usually to their customer's convenience; like offering fully delegated rDNS, which I've not heared of other UK ISPs doing, and refusing to implement ineffectial and false-positive-ridden content filtering attempts).
Comments
Is it? Simple IP-based rate limiting seems quite effective to all but the most determined abuser.
Most (noticeable) abusers are quite determined. They will try Tor, then various anonymizer proxies (forcing you to block all of them or give up), then sometimes Amazon EC2 instances or other VPS, or large public proxies / ISP proxies that you cannot block. In Germany, they can also use cheap DSL where they can switch to new IP addresses almost instantaneously (T-Online is a godsend for abusers/scrapers).
What's to stop them from creating a bit that creates API keys every 5 minutes?
A delay on the API key generation or approval?
> In Germany, they can also use cheap DSL where they can switch to new IP addresses almost instantaneously
That one is easy to reduce the effect of: as well as a per-IP limit have a per-/24 limit that is much lower then 256 times the single address limit. To avoid seeming to be too unfair to other people on the same ISP who happen to be at an address next to a heavy-but-not-abusive user make this limit's bucket refill more often (i.e. if you limit to 100 requests/day per IP, try 100 requests/hour per 256 address block).
You might consider different granularities instead of or as well as /32 and /24. It is not uncommon for a small organisation to have a /29 or /28 allocated (heck, I have a /29 on my line at home as I host a couple of services from it that need their own address). Perhaps set limits for granularities of /32, /28, /24 and /20? Of course this requires development effort, implementing an efficient method of enforcing these limits, but not lots.
> They will try Tor, then various anonymizer proxies (forcing you to block all of them or give up)
Are there really enough reliable cost-free options out there to make that a massive problem? A few determined people will use more resource than you wont by these methods, but the majority will either put up with the rate limit, pay what-ever you are asking for a less limited option, or do somewhere else (the third option being something you'd prefer didn't happen, of course, but you'll always lose some users by refusing to give them the moon on a stick).
> Amazon EC2 instances or other VPS, or large public proxies / ISP proxies that you cannot block
While you can't block them, you can apply rate limits at multiple granularities as mentioned above to limit their effect. To reduce the effect of ISP proxies on HTTP APIs force the use of HTTPS (less HTTPS traffic goes via a proxy than does HTTP traffic - ISPs that use transparent proxies for HTTP caching don't do the same for HTTPS as there would be no point).
THE THING NO ONE HAS MENTIONED YET
Of course this all changes a little once you consider IPv6. A per address limit is meaningless when everyone has a /64 or wider to play with so you are going to have to implement ranged limits (perhaps with gradiated limits like above for /64, /56, /48, ...) if you are limiting by address, and you are going to limit by ISP when trying to limit by individual more often than you will filtering IPv4 addresses this way (some VPS providers hand out small numbers of v6 addresses to each VM so they presumably use one /64 for everyone, where-as I have a /64 allocated to my home line.
Our last case of T-Online abuse originated from 79.192.0.0/10 (e.g. 79.241.205.250, 79.241.223.141, 79.241.207.37 in rapid succession) and there's not much we could do about it (we blocked the changing IPs for 15 minutes each time and hoped we didn't lose too many legitimate users who happened to get one of the blocked IPs).
Apparently there are hundreds of free/open proxies out there. They don't seem to change often and there are some lists of such IP adresses circulating the web, so it's possible to keep up with those. But it's a hassle...
Actually with obvious server/VPS addresses, blocking is feasible for web sites (not APIs!) because the chances that legitimate website visitors will be affected, are slim.
Indeed, but at least the problem of rapidly changing IPv4 addresses will probably disappear there (you block the offender's /64 and he's not likely to get another quickly).
> you block the offender's /64 and he's not likely to get another quickly
That might not always be the case. The /64 I have is from a /48 and apparently I could have other /64s from that block mapped to this line if I wish (http://aa.net.uk/kb-broadband-ipv6-tech.html).
This could be an uncommong perculiarity of course, A&A are in the habit of doing things a little differently to other ISPs (usually to their customer's convenience; like offering fully delegated rDNS, which I've not heared of other UK ISPs doing, and refusing to implement ineffectial and false-positive-ridden content filtering attempts).