DoS against core using a large number of OR search query terms

There is a patch against search module.

Manually testing the feature works fine, but sadly the simpeltest doesn't work currently.
Perhaps my local test system is broken, let's see what the bot says.

+++ b/modules/search/search.admin.inc
@@ -104,6 +104,16 @@ function search_admin_settings($form) {
+  $form['search']['search_limit_or'] = array(
+    '#type' => 'textfield',
+    '#title' => t('Maximum ORs'),
+    '#default_value' => variable_get('search_limit_or', 10),

we need a description here. people may wonder what this setting is about. Maybe: "Maximum number of OR connected search terms to avoid denial of service attacks".

And: do we want positive integer validation on this input? Any invalid string will lead to zero allowed ORs which is bad I guess ...

+++ b/modules/search/search.extender.inc
@@ -323,6 +332,10 @@ class SearchQuery extends SelectQueryExtender {
+    if ($this->countOr > variable_get('search_limit_or', 10)) {
+      form_set_error('keys', t("You aren't allowed to input more then @count words connect with OR.", array('@count' => variable_get('search_limit_or', 10))));

spelling: "more than", not "more then". "connected" instead of "connect".

24 days to next Drupal core point release.

I don't think this should be a visible setting either, maybe an unexposed variable in case a site is really relying on complicated searches.

Maximum keywords seems like a good plan to me.

Assign to myself, as i would like to work on it.

I agree with both points: UI and keyswords

Uploadng a patch made by dereine.

Can I haz upload credit. Lol :)

Works for me. Just to be clear on this, copy/paste of sentences over 10 words, like "The quick brown fox jumped over the lazy dog two times." will not be searchable unless the sentence is quoted (so it is treated as a single key word). Maybe this is overkill, but I wonder if a note about that should be included in the message? Something like:

You aren't allowed to enter more than !count search words. If you are searching for a specific phrase, add quotes around it, such as "The quick brown fox..."

Why not only search with the first 'search_limit_expressions' words?

And/Or

 variable_get('search_limit_expressions ', 25); 

@oriol_e9g
So you suggest that just the list of search values should be trimmed?

The question is, are the actual users using so many words, or is this all about fixing possible DoS attacks.

#7: 1265946-search-dos.patch queued for re-testing.

1) I agree that 10 terms ought to be enough for anybody.

2) I suggest that we just ignore the excess and add a warning message like "Your search exceeded the maximum allowed amount of !count search words. Terms beyond that limit have been ignored." So the user still gets search results and we are DoS safe.

And here comes the patch. I think the actual message can be improved, suggestions welcome.

EDIT: sorry for the unrelated trailing white spaces fixes, my Eclipse removes them automatically on saving.

+++ b/modules/search/search.extender.incundefined
@@ -232,8 +236,13 @@ class SearchQuery extends SelectQueryExtender {
+      if ($expression_count >= $limit_expressions) {
+        drupal_set_message(t('Your search exceeded the maximum allowed amount of @count search words. Terms beyond that limit have been ignored.', array('@count' => $limit_expressions)), 'warning');

It's somehow annoying to have a drupal_set_message in a more like api function. Yes there is already stuff in there, but i think we should better avoid it, if it's possible.

16 days to next Drupal core point release.

Yes, I thought the same, but then I also found it ugly to pass around a boolean class instance variable that tells whether the limit was exceeded or not. Would like to hear more opinions on that.

New patch with some improvements:
* drupal_set_message() moved to executeFirstPass() method as suggested by dereine
* introduced a boolean $expressionsIgnored to indicate ignored search terms
* OR operators are now not counted as expressions
* warning does not show if the exact limit was reached (moved foreach() break to the top of the loop)
* Test case does not hard code the limit anymore

From the technical standpoint this looks perfect now and RTBC.

The question is whether we want to set an error on the form or just display the message as currently.
I think something like this has to be decided by the search module maintainers, but i would personally vote
for the current way.

Would someone please paste the query that is used with the OR terms that causes this DoS? I know that MySQL has a problem with too many JOIN's, but I'm a bit surprised that simply OR'ing together 10 or more words causes the query to take so long that it's a DoS attack. IIRC the more dangerous queries are ones that combine AND and OR, see the simple flag in the code.

I don't think we really know what the problem is. This problem has existed since the search module was first written, and the changes I introduced in D6 reduced the use of temporary tables to solve this very problem, so pushing out a quick hotfix seems rash.

Ok, I did some benchmarks. I created 1000 nodes with devel generate and indexed them with a cron loop (took quite a while).

while [ true ]; do drush cron; done;

I think this setup is quite a common use case for small to mid range sites that use the core search module.
Then I picked some words from the generated content and created a long OR query. As you rightfully said this was boring - the page load took 520ms with the patch and 575ms without it on my quad core desktop computer (Ubuntu, default Apache/MySQL setup, measured with devel query log).

diam OR dolore OR usita OR interdico OR nimis OR erat OR Tincidunt OR paulatim OR Pertineo OR Tation OR Occuro OR diam OR dolore OR usita OR interdico OR nimis OR erat OR Tincidunt OR paulatim OR Pertineo OR Tation OR Occuro OR diam OR dolore OR usita

Then I combined AND/OR expressions and made sure that each search word is unique:

diam OR dolore usita OR interdico nimis erat OR Tincidunt paulatim OR Pertineo Tation OR Occuro tamen OR volutpat comis OR persto Gilvus OR patria Consectetuer OR Humo macto OR facilisis Abdo OR Jugis sudo OR damnum qui OR valetudo immitto OR Capto probo

Now it gets interesting: while the page load took 1820ms with the patch (also quite bad) it took 9386ms without it! I have attached the 3 involved DB search queries.

So I think this is a serious problem, and yes we know what the problem is. We can't accept indefinitely long search queries as they pose a threat to the site's performance and health. Anyone that is capable of writing a simple bash script and has control over a handful of computers can cause serious load problems on your server.

This patch is not a lot of code and I think it is not hard to maintain. It even allows site administrators to configure how long the search queries can be on their site. Entering that many search words is not a valid use case, so no functionality is lost.

I just did a quick and simple benchmark, but I think the magnitude of the numbers is enough evidence. I would even argue that we should reduce the default number of search expressions to 7 (page load of 1060ms with the above query).

Why do you consider this patch just a hotfix? What would you consider a better solution?

I agree with klausi, even 7 seems a lot to me. But I'm sure 99% of users won't even get close to that number

Looking at the queries posted by @klausi, I think it's the non-simple terms creating the LIKE clauses by combining AND and OR that's causing the problem. You say you know what the problem is, but do you? Are you sure that we generate similar queries with simple OR terms; off the top of my head, I don't think we do ... I think we only add the LIKE terms under certain circumstances. If the problem is AND combined with OR, a restriction to 4 or 5 or 7 terms when the query is not simple, makes a lot of sense. But let's be careful to not restrict queries that don't have the problem, just because we know the solution.

I did some further testing and tried different patterns of AND/OR combinations. LIKE clauses are only avoided in simple AND-only cases. OR-only cases do not use LIKE-conditions in the executeFirstPass() query, but also make use of them in the execute() query. And yes, the LIKE conditions slow down the queries a lot (I tried several queries with and without the LIKE parts, I estimate that they are responsible for 60%-95% of the query execution time).

The interesting thing is that OR-only queries are not always faster than OR/AND combined queries, I guess it depends on where the search terms appear in the text and how mysql looks for it with the LIKE operator.

I'm still not convinced we should allow an indefinite number of search expressions even if we believe the particular query will be fast. How do we know that it will be as fast on other databases like Postgres or SQLite? From a security point of view I think it is a good measurement the avoid long queries where possible.

Anyway, what I found is that OR expressions are expensive. We could just limit them.

New approach: tackle the use of OR operators. No more than 7 OR operators are allowed. If combined with AND operators ==> no more than 7 operators overall are allowed (OR+AND). If only AND operators are used there is no limitation.

Now every search query that I could imagine executes below 1100ms in my test environment, which is pretty OK I guess.

Advantages: Leaves fast AND queries unlimited. Is more strict to AND/OR combinations that showed to be the slowest during my testing.
Drawbacks: Logic is a little more complex. Wording of the warning message is not perfect.

+++ b/modules/search/search.extender.incundefined
@@ -323,6 +343,9 @@ class SearchQuery extends SelectQueryExtender {
+      drupal_set_message(t('Your search exceeded the maximum allowed amount of @count AND/OR combined expressions. Terms beyond that limit have been ignored.', array('@count' => variable_get('search_and_or_limit', 7))), 'warning');

How bout...

"Your search used too many AND/OR expressions. Only the first @count terms were included in this search"

3 days to next Drupal core point release.

done.

Oh this was caused by the whitespace changes in the patch, because they were fixed in the meantime.

So here is a new version of the patch.

Looks good to me but it'd be great if Doug could give this a once over before commit too since it's a new approach to those previously discussed, assigning to him (also I haven't had a chance to try out the new fancy MAINTAINERS.txt assignage yet).

Nice approach here!

+    if ($this->expressionsIgnored) {
+      drupal_set_message(t('Your search used too many AND/OR expressions. Only the first @count terms were included in this search.', array('@count' => variable_get('search_and_or_limit', 7))), 'warning');
+    }

This doesn't belong in the extender. Could we move this to the page callback?

@Damien: unfortunately this would require more refactoring, as warnings or errors would need to be passed back over several levels (from class SearchQuery to hook_search_execute() to search_data() to search_view()). I know this is not ideal, but there is already a drupal_set_message() in this class. So I would say that this is a separate/followup issue.

Reroll.

+++ b/core/modules/search/search.extender.inc
@@ -123,6 +123,14 @@ class SearchQuery extends SelectQueryExtender {
   /**
+   * Indicates whether the number of AND/OR combinations exceeded the configured
+   * limit. Expressions beyond the limit are ignored.

This should start with a one-line comment.

+++ b/core/modules/search/search.extender.inc
@@ -183,7 +191,17 @@ class SearchQuery extends SelectQueryExtender {
+    // The first search expression shall not count as AND.

'shall' sounds weirdly imperative: 'shall' -> 'does'

+++ b/core/modules/search/search.extender.inc
@@ -183,7 +191,17 @@ class SearchQuery extends SelectQueryExtender {
+        // Ignore all further search expressions to prevent DoS attacks using a

I'm wondering, do people who look at this all know what a "DoS" is? I'm not sure...
The first hit on Google is "Disk-Operating-System", so I changed it to Denial-of-Service so people can Google it at least.

+++ b/core/modules/search/search.test
@@ -290,6 +290,20 @@ class SearchPageText extends DrupalWebTestCase {
+    for ($i = 0; $i < $limit + 1; $i++) {

Is there some standard for this? I prefer $i <= $limit but I left it, as it's sort of a matter of taste.

I rerolled for that.

I also opened #1366020: Overhaul SearchQuery; make search redirects use GET query params for keywords for the drupal_set_message() issue (#31/#32).

Marking this RTBC. I didn't touch a line of code, so this doesn't count as "my" patch. I'm also uploading a tests-only patch to prove that the test works.

I did try this out locally again and it works as advertised. The code is also very clear and is tested.
Let's do this!

19 days to next Drupal core point release.

d.o--

There's another instance of DoS in a later comment; do we want to fix that one as well?

#38 looks good.

Well if we open a followup issue as suggested in #32, do we also need the @todo?

I already opened #1366020: Overhaul SearchQuery; make search redirects use GET query params for keywords for that.
I personally think that, because this issue is critical, it should go in as is, but that is not for me to decide.

I'm happy with a follow-up issue to document this, moving back to CNR.

Thanks tstoeckler. Still looks good, back to RTBC.

Thanks for the follow-up issue, committed/pushed to 8.x, moving back to D7.

#38: 1265946-search-dos_0.patch queued for re-testing.

Edit: Let's see if we need to port at all...

D'uh!....

I didn't have time to re-roll it properly right now, but let's see if manually removing the 'core' part from the patch works.

Good for D8, same for D7

Committed to 7.x. Thanks.