1

Lets say I have a search form for a blog (or any other system that would use SQL to run queries) and I want to protect it from denial of service. An attacker wants to attack my site by flooding the search function, which would cause a lot of SQL queries and might result in DoS.

This is theoretical so it's not about a single type of language or database management system, but if you want to you can imagine it's PHP and MySQL (although I'm wondering about the effects in general rather than specific to one platform).

A request like GET /search.php?s=[SEARCH] searches the database for all articles containing [SEARCH] and returns them. Let's say the maximum character length for [SEARCH] is 128.

I am wondering in terms of "performance loss" which would be the worst form of attack between these two scenarios:

  1. The attacker searches for a random string of 128 characters (ex. aisoizeuf[...]deuedujed).
  2. The attacker searches for a single character each time (ex. e).

At first I thought that attack #1 would be more effective, thus legitimizing a strict limit on the character length of the search query. But then I thought, since in my example we're talking about a blog, that multiple searches on a single character might return a lot more articles because almost anything you write will contain at least one vowel. So then I realized perhaps it's not such a clear cut answer.

Attack #1 will require more ressources to send the query and scan all the entries in the database, but it won't return anything, whereas attack #2 will do the opposite - it won't take up a lot of ressources to scan the database but since almost every entry will contain an occurrence of the search query, it will return almost every entry in the database

Which attack do you think will be more dangerous and use up more ressources?

  • I would think #2 would be more dangerous. Also, why are you not paginating/limiting results? – Lighthart Apr 27 '16 at 16:51
2

You can mitigate both of these issues by creating a FULLTEXT index. In other words, instead of having the database system read the entire table and scan every character in every field, the system builds an index that can be quickly searched while discarding common words/letters. Your attacker can search for "e" as fast as they want, and the index will answer with no results returned in a matter of a very small fraction of a second (and with appropriate caching, future searches will cost even less). This can reduce the amount of searching needed from millions of bytes to just a few hundred bytes, which is a trivial operation for a computer.

Most FULLTEXT indexes tend to use a "b-tree" (or, binary tree) implementation. This means that even if your attacker sends 128 random characters, as opposed to just one character, the database only needs to go until it can prove that there's no matching values, which means it will not search all 128 characters, assuming we're talking about actual random values. The most exhaustive search that the attacker could perform would be to actually use real words from a dictionary that are also in your blog. You could also restrict searches to a minimum length by discarding words less than, for example, three characters long. This would make your index more effective and reduce the capabilities to spam small searches.

As far as "dangerous" goes, it's unlikely that either attack would cost very much in terms of cost assuming it were a personal blog-- the entire database can fit in memory and thus wouldn't contribute very much to server load even if it were being hit hundreds of times per second. You'd be more likely that a DDoS would occur simply because your server's OS can't handle any more pending connections rather than the limitation of the database itself. Most databases can handle hundreds of simple index queries per second, even on a home computer.

1

After having a client's site go down because of this exact problem, we introduced a somewhat simplistic solution that helped dramatically minimise the effect of such attacks. As phyrfox said in his answer, a FULLTEXT index is a very effective tool for both performance and counter DoS.

As we were already tracking visitors for statistic information, we went a step further and began tracking their form behaviour. Each user was given a tinyint column in their statistics that tracked how many times they've submit a form (or filled a form in in the case of ajax requests, but that was logged in users only.) When the user's total reached 32 (a quarter of a tinyint's maximum value) all requests to use the form were delayed by a second. When the total reached 48, two seconds, 64, three seconds, etc. At the point of reaching 128, the user was then banned from any attempts at using the forms but were not informed of this. The likelihood of an attacker changing IP addresses constantly is quite low in such a short period of time and they'll assume the slowdown is due to the success of their DoS attack and not counter DoS strategy. The method works quite similar to how the bcrypt algorithm works for passwords. The more somebody tries processing it, the slower it gets. Rather than process any SQL queries at 128, they were given "No results found" or cached results pages. From their view, they're still implementing an attack but behind the scenes they're just making another HTTP request. It's possible, of course, to take this further and ban them from accessing somehow, but remember that banning them completely is pointless if they're hell bent on DoSing you - they'll just change their proxy and go again. This is why all our efforts to lower the efficiency of the attack were invisible.

The real benefit to this approach is how little overhead it produces. In the grand scheme of a large website receiving plenty of spam visitors, an extra tinyint per user isn't going to contribute to any substantial gain on the database. This, combined with a FULLTEXT index, should prevent most DoS attacks doing serious damage without a lot of effort on your part.

0

There are a few things that come into mind with regards to DoS via what you described. The first is network based, the second is query based (what is the maximum cut off). The first network based: This will depend on the design or your network. E.g., is there load balancing configured somewhere, do you have multiple providers, do you have filtering in place, e.g. if query exceeds N then block offender. The second is what you seem to be more concerned about.

Things to consider:

  1. System - does it have enough memory to process huge volumes of queries
  2. Configuration - what is the maximum query set to (MySQL, Apache/etc)
  3. Filtering - is there a filter to block out offenders
  4. Buffer/Quotas - if you set a maximum length to 10 chars, what are you doing if someone goes over this limit.

1) Your system should be designed properly to ensure this does not occur. Your design should include buffers for N amount of processing, queries, connections.

2) Most congifurations allow you to set a hardcoded limit on the amount of connections occur.

3) Filtering (especially with mod_ratelimit, etc) can ensure this does not occur.

4) Buffer / quotas. Same as #3

So what is your ultimate goal? A traditional DoS will overwhelm you because you weren't prepared. In a network based DoS there is little you can do to stop 40Gbps from hitting your 1Gbps system without third party help (Cloud servers, caching (Akamai), and so forth). From a system/process perspective, there are plenty of ways to mitigate against this. What would be your endgame here?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.