[$csp2 adblockpluscore] Issue 6329 - Add the CSP filter type

lib/filterClasses.js

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-present eyeo GmbH
  *
  * Adblock Plus is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 3 as
  * published by the Free Software Foundation.
  *
  * Adblock Plus is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
@@ skipping 80 matching lines @@
 /**
  * Regular expression that RegExp filters specified as RegExps should match
  * @type {RegExp}
  */
 Filter.regexpRegExp = /^(@@)?\/.*\/(?:\$~?[\w-]+(?:=[^,\s]+)?(?:,~?[\w-]+(?:=[^,\s]+)?)*)?$/;
 /**
  * Regular expression that options on a RegExp filter should match
  * @type {RegExp}
  */
 Filter.optionsRegExp = /\$(~?[\w-]+(?:=[^,]+)?(?:,~?[\w-]+(?:=[^,]+)?)*)$/;
+/**
+ * Regular expression that matches an invalid Content Security Policy
+ * @type {RegExp}
+ */
+Filter.invalidCSPRegExp = /(;|^) ?(base-uri|referrer|report-to|report-uri|upgrade-insecure-requests)\b/i;
 
 /**
  * Creates a filter of correct type from its text representation - does the
  * basic parsing and calls the right constructor then.
  *
  * @param {string} text   as in Filter()
  * @return {Filter}
  */
 Filter.fromText = function(text)
 {
@@ skipping 54 matching lines @@
  * Removes unnecessary whitespaces from filter text, will only return null if
  * the input parameter is null.
  * @param {string} text
  * @return {string}
  */
 Filter.normalize = function(text)
 {
   if (!text)
     return text;
 
-  // Remove line breaks and such
-  text = text.replace(/[^\S ]/g, "");
+  // Remove line breaks, tabs etc
+  text = text.replace(/[^\S ]+/g, "");
 
   // Don't remove spaces inside comments
-  if (/^\s*!/.test(text))
+  if (/^ *!/.test(text))
     return text.trim();
 
   // Special treatment for element hiding filters, right side is allowed to
   // contain spaces
   if (Filter.elemhideRegExp.test(text))
   {
     let [, domain, separator, selector] = /^(.*?)(#@?#?)(.*)$/.exec(text);
-    return domain.replace(/\s/g, "") + separator + selector.trim();
-  }
-
-  // For most regexp filters we strip all whitespace, but the values of $csp

[Manish Jethani, 2018/03/12 18:53:59]

So this doesn't work for the following cases:

 1.  foo?csp=b a r$csp=script-src  'self'
 2.  foo$bar=c s p = ba z,cs p = script-src  'self'

(In the second case, assume "bar" is a future option type that can take a value
that contains the substring "csp=")

I'm just wondering now, why not just use the following instead of all this:

  let index = text.indexOf("$");
  if (index >= 0)
  { 
    let options = text.substring(index + 1).split(",");
    for (let i = 0; i < options.length; i++)
    { 
      let csp = /^ *c *s *p *=/.exec(options[i]);
      if (csp)
      { 
        options[i] = csp[0].replace(/ +/g, "") +
                     options[i].substring(csp[0].length).replace(/ +/g, " ")
                     .trim();
      }
      else
      { 
        options[i] = options[i].replace(/ +/g, "");
      }
    }
    
    return text.substring(0, index + 1).replace(/ +/g, "") + options.join(",");
  }
  
  return text.replace(/ +/g, "");

This is easier to understand, technically more correct (will not get confused
with "csp=" in the option value or in the URL part of the filter), and performs
just as well.

[Sebastian Noack, 2018/03/12 23:19:01]

Splitting the options list into an array (for every filter that has options),
likely has measurable performance implications in the common case.

[Manish Jethani, 2018/03/13 06:59:30]

You mean in terms of memory consumption? I ran a test with both implementations
and the one I suggested above wasn't any slower than the original. Since strings
are immutable in JS, I would be surprised if String.split didn't just return
strings that simply pointed back to the same memory locations in the original
string.

If we want to avoid creating that array we could try with generators:

  function* splitOptions(string)
  {
    let startIndex = 0;
    let index = -1;

    while ((index = string.indexOf(",", startIndex = index + 1)) != -1)
      yield string.substring(startIndex, index + 1);

    yield string.substring(startIndex);
  }

  ...

  let index = text.indexOf("$");
  if (index >= 0)
  {
    let options = "";
    for (let fragment of splitOptions(text.substring(index)))
    {
      let csp = /^ *c *s *p *=/.exec(fragment);
      if (csp)
      {
        options += csp[0].replace(/ +/g, "") +
                   fragment.substring(csp[0].length).replace(/ +/g, " ").trim();
      }
      else
      {
        options += fragment.replace(/ +/g, "");
      }
    }

    return text.substring(0, index).replace(/ +/g, "") + options;
  }

This seems to be a bit slower but not too much.

[Manish Jethani, 2018/03/13 07:35:00]

OK, so I inlined that bit, now this seems to perform well:

  let index = text.indexOf("$");
  if (index >= 0)
  {
    let options = text.substring(index + 1);
    text = text.substring(0, index + 1).replace(/ +/g, "");

    for (let start = 0, end; end != options.length; start = end + 1)
    {
      end = options.indexOf(",", start);
      if (end == -1)
        end = options.length;

      let fragment = options.substring(start, end);
      let csp = /^ *c *s *p *=/.exec(fragment);
      if (csp)
      {
        text += csp[0].replace(/ +/g, "") +
                fragment.substring(csp[0].length).replace(/ +/g, " ").trim();
      }
      else
      {
        text += fragment.replace(/ +/g, "");
      }
    }

    return text;
  }

[kzar, 2018/03/14 13:54:37]

Well spotted, I've added some unit tests for those cases.

[Sebastian Noack, 2018/03/14 20:59:20]

Any reason, why this suggestion was ignored, without a comment?

[kzar, 2018/03/15 10:26:24]

I ignored that since it assumed the first '$' was the start of the options
string, which I pointed out elsewhere is not necessarily the case. Sorry I
thought that was obvious but I guess not.

[Manish Jethani, 2018/03/15 10:42:41]

I think Sebastian is referring to the rest of the code, i.e. the part where we
already have the correct index of the options part.

So basically starting with this:

  let options = text.substring(index + 1);
  text = text.substring(0, index + 1).replace(/ +/g, "");

  for (let start = 0, end; end != options.length; start = end + 1)
  ...

In my tests I found that this was much faster than using String.split, but
arguably it makes the code harder to read.

[kzar, 2018/03/15 11:38:50]

So instead of splitting the options string by "," instead using substring and
indexOf(",") to pick out each option?
Well fair enough, but I feel like optimising this rarely used code path at the
cost of code readability isn't worth it.

I would see the utility of moving the logic out into a generator function
*parseOptions which yields each option part however, since that could also be
used in the parsing code which is worth optimising. However if I got it right
using a generator here would make performance even worse than simply splitting
the string.

[Manish Jethani, 2018/03/15 12:00:11]

Yes, it just turned out to be faster.
I'm cool with using String.split here in the interested of
readability/maintainability.
Yeah, I tested with the generator, it performs worse. String.split is faster.

[Sebastian Noack, 2018/03/15 17:25:41]

I guess, if it's only in the code path hit for $csp filters, the performance
penalty is acceptable.

-  // filter options are allowed to contain single (non trailing) spaces.
-  let strippedText = text.replace(/\s/g, "");

[Manish Jethani, 2018/03/12 16:34:53]

Since we have already stripped out all non-space whitespace, we can just use " "
(space) instead of \s here?

  let strippedText = text.replace(/ /g, "");

[kzar, 2018/03/14 13:54:38]

I think you're right, Done.

-  if (!/csp=/i.test(strippedText))
+    return domain.replace(/ +/g, "") + separator + selector.trim();
+  }
+
+  // For most regexp filters we strip all spaces, but $csp filter options
+  // are allowed to contain single (non trailing) spaces.
+  let strippedText = text.replace(/ +/g, "");
+  if (!strippedText.includes("$") || !/\bcsp=/i.test(strippedText))
     return strippedText;
 
   let optionsMatch = Filter.optionsRegExp.exec(strippedText);

[Manish Jethani, 2018/03/12 16:34:53]

We can just look for "$" here and if none is present then there are no options,
right? We don't have to match the regular expression.

Combined with the above then we could do:

  if (strippedText.indexOf("$") == -1 || !/[$,]csp=/i.test(strippedText))
    return strippedText;

[kzar, 2018/03/14 13:54:38]

No, that's not good enough unfortunately. There can be a $ (or multiple) with no
options part. I added a test case for that as well FWIW.

[Manish Jethani, 2018/03/14 18:10:49]

OK, but I wonder if we shouldn't just look for a "$" first anyway before running
the regular expression. I see the same thing being done in
RegExpFilter.fromText:

  let match = (text.indexOf("$") >= 0 ? Filter.optionsRegExp.exec(text) : null);
  if (match)
  {
    ...
  }

   if (!optionsMatch)
     return strippedText;
 
-  // We know where the options part starts in the filter text that's stripped
-  // of whitespace, next we must find the corresponding position in the original
-  // filter text.
-  let optionsPosition = 0;

[Manish Jethani, 2018/03/12 16:34:53]

This part is not being used at all.

[kzar, 2018/03/14 13:54:38]

Whoops, you're right. I've fixed that now.

-  let offset = 0;
-  while (offset > -1)
-  {
-    optionsPosition = text.substring(optionsPosition).indexOf("$");
-    offset = strippedText.substring(offset, optionsPosition).indexOf("$");
-  }
-
-  // Finally with that we can generally strip whitespace, being careful to not
-  // to for $csp filter values.
-  let parts = [];
-  let position = 0;
-  let cspRegexp = /(c\s*s\s*p\s*=)([^,]+)/ig;
-  let cspMatch;
-  while (cspMatch = cspRegexp.exec(text))
-  {
-    parts.push(

[Manish Jethani, 2018/03/12 16:34:53]

We've already stripped whitespace once, now we're stripping it again. This only
affects filters with a $csp option, but I wonder if we shouldn't just check for
$csp before stripping whitespace the first time.

i.e. above:

  if (text.indexOf("$") == -1 || !/[$,] *c *s *p *=/i.test(text))
    return text.replace(/ /g, "");

[kzar, 2018/03/14 13:54:37]

No because we're expecting thousands of non-csp filters and maybe 5 csp filters.
We should optimise for the common case.

-      text.substring(position, cspMatch.index + cspMatch[1].length)
-          .replace(/\s/g, "")
-    );
-    parts.push(
-      text.substr(cspMatch.index + cspMatch[1].length, cspMatch[2].length)
-          .replace(/\s+/g, " ")
-          .trim()
-    );
-    position = cspMatch.index + cspMatch[0].length;
-  }
-  parts.push(text.substr(position).replace(/\s/g, ""));
-  return parts.join("");
+  // For $csp filters we must first separate out the options part of the
+  // text, being careful to preserve its spaces.
+  let beforeOptions = strippedText.substring(0, optionsMatch.index);
+  let strippedDollarIndex = -1;
+  let dollarIndex = -1;
+  do
+  {
+    strippedDollarIndex = beforeOptions.indexOf("$", strippedDollarIndex + 1);
+    dollarIndex = text.indexOf("$", dollarIndex + 1);
+  }
+  while (strippedDollarIndex != -1);
+  let optionsText = text.substr(dollarIndex + 1);
+
+  // Then we can normalize spaces in the options part safely
+  let options = optionsText.split(",");
+  for (let i = 0; i < options.length; i++)
+  {
+    let option = options[i];
+    let cspMatch = /^ *c *s *p *=/i.exec(option);
+    if (cspMatch)
+    {
+      options[i] = cspMatch[0].replace(/ +/g, "") +
+                   option.substr(cspMatch[0].length).trim().replace(/ +/g, " ");
+    }
+    else
+      options[i] = option.replace(/ +/g, "");
+  }
+
+  return beforeOptions + "$" + options.join();
 };
 
 /**
  * @see filterToRegExp
  */
 Filter.toRegExp = filterToRegExp;
 
 /**
  * Class for invalid filters
  * @param {string} text see Filter()
@@ skipping 533 matching lines @@
   {
     options = match[1].split(",");
     text = match.input.substr(0, match.index);
     for (let option of options)
     {
       let value = null;
       let separatorIndex = option.indexOf("=");
       if (separatorIndex >= 0)
       {
         value = option.substr(separatorIndex + 1);
-        option = option.substr(0, separatorIndex).toUpperCase();
-
-        if (option == "CSP")
-          value = value.trim();
-        else
-          value = value.replace(/\s/g, "");
+        option = option.substr(0, separatorIndex);
       }
-      else
-        option = option.toUpperCase();
-
-      option = option.replace(/-/, "_");
-
+      option = option.replace(/-/, "_").toUpperCase();
       if (option in RegExpFilter.typeMap)
       {
         if (contentType == null)
           contentType = 0;
         contentType |= RegExpFilter.typeMap[option];
 
         if (option == "CSP" && typeof value != "undefined")
-        {
-          if (csp)
-            csp.push(value);
-          else
-            csp = [value];
-        }
+          csp = value;
       }
       else if (option[0] == "~" && option.substr(1) in RegExpFilter.typeMap)
       {
         if (contentType == null)
           ({contentType} = RegExpFilter.prototype);
         contentType &= ~RegExpFilter.typeMap[option.substr(1)];
       }
       else if (option == "MATCH_CASE")
         matchCase = true;
       else if (option == "~MATCH_CASE")
         matchCase = false;
       else if (option == "DOMAIN" && typeof value != "undefined")
         domains = value.toUpperCase();
       else if (option == "THIRD_PARTY")
         thirdParty = true;
       else if (option == "~THIRD_PARTY")
         thirdParty = false;
       else if (option == "COLLAPSE")
         collapse = true;
       else if (option == "~COLLAPSE")
         collapse = false;
       else if (option == "SITEKEY" && typeof value != "undefined")
         sitekeys = value.toUpperCase();
       else
         return new InvalidFilter(origText, "filter_unknown_option");
     }
   }
-  text = text.replace(/\s/g, "");
 
   try
   {
     if (blocking)
     {
-      if (csp)
-      {
-        csp = csp.join("; ").toLowerCase();
-
-        // Prevent filters from injecting report-uri or report-to directives
-        // since they are a privacy concern. Regexp based upon reBadCSP[1].
-        // [1] - https://github.com/gorhill/uBlock/blob/67e06f53b4d73df6179f6d320553a55da4ead40e/src/js/static-net-filtering.js#L1362
-        if (/(;|^)\s*report-(to|uri)\b/.test(csp))
-          return new InvalidFilter(origText, "filter_invalid_csp");
-      }
+      if (csp && Filter.invalidCSPRegExp.test(csp))
+        return new InvalidFilter(origText, "filter_invalid_csp");
 
       return new BlockingFilter(origText, text, contentType, matchCase, domains,
                                 thirdParty, sitekeys, collapse, csp);
     }
     return new WhitelistFilter(origText, text, contentType, matchCase, domains,
                                thirdParty, sitekeys);
   }
   catch (e)
   {
     return new InvalidFilter(origText, "filter_invalid_regexp");
@@ skipping 238 matching lines @@
  */
 function ElemHideEmulationFilter(text, domains, selector)
 {
   ElemHideBase.call(this, text, domains, selector);
 }
 exports.ElemHideEmulationFilter = ElemHideEmulationFilter;
 
 ElemHideEmulationFilter.prototype = extend(ElemHideBase, {
   type: "elemhideemulation"
 });