CVE-2021-23490: Inefficient Regular Expression Complexity (CWE-1333)
value: The package parse-link-header before 2.0.0 are vulnerable to Regular Expression Denial of Service (ReDoS) via the checkHeader function.
CWE description: The product uses a regular expression with an inefficient, possibly exponential worst-case computational complexity that consumes excessive CPU cycles.
CVSS v3 base score: 7.5
Published: 2021-12-24T20:15Z
Repository: https://github.com/thlorenz/parse-link-header
Language: JavaScript
Files changed: README.md, index.js, test/parse-link-header.js
Commit date: 2021-12-16 09:32:52 -0600
Commit message: Limit linkHeader length, throw error if exceeds (#25)

* Limit linkheader length, add checkHeader func, update documentation

* indentation
Diff: diff --git a/README.md b/README.md
index a55c218..1eb4ff7 100644
--- a/README.md
+++ b/README.md
@@ -44,8 +44,16 @@ console.log(parsed);
 ***parseLinkHeader(linkHeader : String) : Object***
 
 Parses the given link header containing [web links](http://tools.ietf.org/html/rfc5988) and returns an object keyed by
 the `rel` property that contains information about each link.
 
+### Environmental Variables
+
+To avoid redundantly parsing of extremely long (invalid) input, the package uses 2 env variabes:
+
+`PARSE_LINK_HEADER_MAXLEN` - Sets the number of characters the input should be limited to - longer inputs will not be handled. Defaults to `2000`.
+
+`PARSE_LINK_HEADER_THROW_ON_MAXLEN_EXCEEDED` - Defines behavior for when the `PARSE_LINK_HEADER_MAXLEN` parameter is exceeded. if defined, an error will be thrown; if it's `null`, the function fails silently by returning `null`. Defaults to `null`.
+
 ### Formatting a link header
 
 The purpose of this module is to parse the link header information. To format an object generated by this module back to the link header string, use the [format-link-header](https://github.com/jonathansamines/format-link-header) module.
diff --git a/index.js b/index.js
index e01bfbe..3bb1c3d 100644
--- a/index.js
+++ b/index.js
@@ -2,10 +2,13 @@
 
 var qs = require('querystring')
   , url = require('url')
   , xtend = require('xtend');
 
+const PARSE_LINK_HEADER_MAXLEN = parseInt(process.env.PARSE_LINK_HEADER_MAXLEN) || 2000;
+const PARSE_LINK_HEADER_THROW_ON_MAXLEN_EXCEEDED = process.env.PARSE_LINK_HEADER_THROW_ON_MAXLEN_EXCEEDED != null
+
 function hasRel(x) {
   return x && x.rel;
 }
 
 function intoRels (acc, x) {
@@ -44,12 +47,25 @@ function parseLink(link) {
   } catch (e) {
     return null;
   }
 }
 
+function checkHeader(linkHeader){
+  if (!linkHeader) return false;
+
+  if (linkHeader.length > PARSE_LINK_HEADER_MAXLEN) {
+    if (PARSE_LINK_HEADER_THROW_ON_MAXLEN_EXCEEDED) {
+      throw new Error('Input string too long, it should be under ' + PARSE_LINK_HEADER_MAXLEN + ' characters.');
+    } else {
+        return false;
+      }
+  }
+  return true;
+}
+
 module.exports = function (linkHeader) {
-  if (!linkHeader) return null;
+  if (!checkHeader(linkHeader)) return null;
 
   return linkHeader.split(/,\s*</)
    .map(parseLink)
    .filter(hasRel)
    .reduce(intoRels, {});
diff --git a/test/parse-link-header.js b/test/parse-link-header.js
index 067f6f7..9339edf 100644
--- a/test/parse-link-header.js
+++ b/test/parse-link-header.js
@@ -184,5 +184,23 @@ test('parsing a proper link header with matrix parameters', function (t) {
           url: 'https://imaginary.url.notreal/segment;foo=bar;baz/item?name=What,+me+worry' }}
     , 'correctly parses url with matrix parameters'
   )
   t.end()
 })
+
+test('parsing an extremely long link header', function (t) {
+  function payload (n) {
+    var ret = ""
+    for (var i = 0; i < n; i++) {
+      ret += " "
+    }
+    return ret
+    }
+  var linkHeader = '; rel="' + payload(10000) + '",'
+
+  t.equal(
+      parse(linkHeader)
+    , null
+    , 'correctly returns null when dealing with an extremely long link header'
+  )
+  t.end()
+})

Vulnerable code:   if (!linkHeader) return null;
Fixed code: ### Environmental Variables

To avoid redundantly parsing of extremely long (invalid) input, the package uses 2 env variabes:

`PARSE_LINK_HEADER_MAXLEN` - Sets the number of characters the input should be limited to - longer inputs will not be handled. Defaults to `2000`.

`PARSE_LINK_HEADER_THROW_ON_MAXLEN_EXCEEDED` - Defines behavior for when the `PARSE_LINK_HEADER_MAXLEN` parameter is exceeded. if defined, an error will be thrown; if it's `null`, the function fails silently by returning `null`. Defaults to `null`.

const PARSE_LINK_HEADER_MAXLEN = parseInt(process.env.PARSE_LINK_HEADER_MAXLEN) || 2000;
const PARSE_LINK_HEADER_THROW_ON_MAXLEN_EXCEEDED = process.env.PARSE_LINK_HEADER_THROW_ON_MAXLEN_EXCEEDED != null

function checkHeader(linkHeader){
  if (!linkHeader) return false;

  if (linkHeader.length > PARSE_LINK_HEADER_MAXLEN) {
    if (PARSE_LINK_HEADER_THROW_ON_MAXLEN_EXCEEDED) {
      throw new Error('Input string too long, it should be under ' + PARSE_LINK_HEADER_MAXLEN + ' characters.');
    } else {
        return false;
      }
  }
  return true;
}

  if (!checkHeader(linkHeader)) return null;

test('parsing an extremely long link header', function (t) {
  function payload (n) {
    var ret = ""
    for (var i = 0; i < n; i++) {
      ret += " "
    }
    return ret
    }
  var linkHeader = '; rel="' + payload(10000) + '",'

  t.equal(
      parse(linkHeader)
    , null
    , 'correctly returns null when dealing with an extremely long link header'
  )
  t.end()
})