CVE-2022-25883: Inefficient Regular Expression Complexity (CWE-1333)
value: Versions of the package semver before 7.5.2 are vulnerable to Regular Expression Denial of Service (ReDoS) via the function new Range, when untrusted user data is provided as a range.
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: 2023-06-21T05:15Z
Repository: https://github.com/npm/node-semver
Language: JavaScript
Files changed: classes/comparator.js, classes/range.js, classes/semver.js, functions/coerce.js, internal/re.js, package.json, test/integration/whitespace.js, test/internal/re.js, test/map.js
Commit date: 2023-06-15 12:21:14 -0700
Commit message: fix: better handling of whitespace (#564)


Diff: diff --git a/classes/comparator.js b/classes/comparator.js
index 2146c88..3d39c0e 100644
--- a/classes/comparator.js
+++ b/classes/comparator.js
@@ -14,10 +14,11 @@ class Comparator {
       } else {
         comp = comp.value
       }
     }
 
+    comp = comp.trim().split(/\s+/).join(' ')
     debug('comparator', comp, options)
     this.options = options
     this.loose = !!options.loose
     this.parse(comp)
 
@@ -131,10 +132,10 @@ class Comparator {
 }
 
 module.exports = Comparator
 
 const parseOptions = require('../internal/parse-options')
-const { re, t } = require('../internal/re')
+const { safeRe: re, t } = require('../internal/re')
 const cmp = require('../functions/cmp')
 const debug = require('../internal/debug')
 const SemVer = require('./semver')
 const Range = require('./range')
diff --git a/classes/range.js b/classes/range.js
index d9e866d..53c2540 100644
--- a/classes/range.js
+++ b/classes/range.js
@@ -24,23 +24,30 @@ class Range {
 
     this.options = options
     this.loose = !!options.loose
     this.includePrerelease = !!options.includePrerelease
 
-    // First, split based on boolean or ||
+    // First reduce all whitespace as much as possible so we do not have to rely
+    // on potentially slow regexes like \s*. This is then stored and used for
+    // future error messages as well.
     this.raw = range
-    this.set = range
+      .trim()
+      .split(/\s+/)
+      .join(' ')
+
+    // First, split on ||
+    this.set = this.raw
       .split('||')
       // map the range to a 2d array of comparators
-      .map(r => this.parseRange(r.trim()))
+      .map(r => this.parseRange(r))
       // throw out any comparator lists that are empty
       // this generally means that it was not a valid range, which is allowed
       // in loose mode, but will still throw if the WHOLE range is invalid.
       .filter(c => c.length)
 
     if (!this.set.length) {
-      throw new TypeError(`Invalid SemVer Range: ${range}`)
+      throw new TypeError(`Invalid SemVer Range: ${this.raw}`)
     }
 
     // if we have any that are not the null set, throw out null sets.
     if (this.set.length > 1) {
       // keep the first one, in case they're all null sets
@@ -62,25 +69,21 @@ class Range {
     this.format()
   }
 
   format () {
     this.range = this.set
-      .map((comps) => {
-        return comps.join(' ').trim()
-      })
+      .map((comps) => comps.join(' ').trim())
       .join('||')
       .trim()
     return this.range
   }
 
   toString () {
     return this.range
   }
 
   parseRange (range) {
-    range = range.trim()
-
     // memoize range parsing for performance.
     // this is a very hot path, and fully deterministic.
     const memoOpts =
       (this.options.includePrerelease && FLAG_INCLUDE_PRERELEASE) |
       (this.options.loose && FLAG_LOOSE)
@@ -103,13 +106,10 @@ class Range {
     range = range.replace(re[t.TILDETRIM], tildeTrimReplace)
 
     // `^ 1.2.3` => `^1.2.3`
     range = range.replace(re[t.CARETTRIM], caretTrimReplace)
 
-    // normalize spaces
-    range = range.split(/\s+/).join(' ')
-
     // At this point, the range is completely trimmed and
     // ready to be split into comparators.
 
     let rangeList = range
       .split(' ')
@@ -201,11 +201,11 @@ const cache = new LRU({ max: 1000 })
 const parseOptions = require('../internal/parse-options')
 const Comparator = require('./comparator')
 const debug = require('../internal/debug')
 const SemVer = require('./semver')
 const {
-  re,
+  safeRe: re,
   t,
   comparatorTrimReplace,
   tildeTrimReplace,
   caretTrimReplace,
 } = require('../internal/re')
@@ -255,14 +255,17 @@ const isX = id => !id || id.toLowerCase() === 'x' || id === '*'
 // ~2.0, ~2.0.x, ~>2.0, ~>2.0.x --> >=2.0.0 <2.1.0-0
 // ~1.2, ~1.2.x, ~>1.2, ~>1.2.x --> >=1.2.0 <1.3.0-0
 // ~1.2.3, ~>1.2.3 --> >=1.2.3 <1.3.0-0
 // ~1.2.0, ~>1.2.0 --> >=1.2.0 <1.3.0-0
 // ~0.0.1 --> >=0.0.1 <0.1.0-0
-const replaceTildes = (comp, options) =>
-  comp.trim().split(/\s+/).map((c) => {
-    return replaceTilde(c, options)
-  }).join(' ')
+const replaceTildes = (comp, options) => {
+  return comp
+    .trim()
+    .split(/\s+/)
+    .map((c) => replaceTilde(c, options))
+    .join(' ')
+}
 
 const replaceTilde = (comp, options) => {
   const r = options.loose ? re[t.TILDELOOSE] : re[t.TILDE]
   return comp.replace(r, (_, M, m, p, pr) => {
     debug('tilde', comp, _, M, m, p, pr)
@@ -296,14 +299,17 @@ const replaceTilde = (comp, options) => {
 // ^1.2, ^1.2.x --> >=1.2.0 <2.0.0-0
 // ^1.2.3 --> >=1.2.3 <2.0.0-0
 // ^1.2.0 --> >=1.2.0 <2.0.0-0
 // ^0.0.1 --> >=0.0.1 <0.0.2-0
 // ^0.1.0 --> >=0.1.0 <0.2.0-0
-const replaceCarets = (comp, options) =>
-  comp.trim().split(/\s+/).map((c) => {
-    return replaceCaret(c, options)
-  }).join(' ')
+const replaceCarets = (comp, options) => {
+  return comp
+    .trim()
+    .split(/\s+/)
+    .map((c) => replaceCaret(c, options))
+    .join(' ')
+}
 
 const replaceCaret = (comp, options) => {
   debug('caret', comp, options)
   const r = options.loose ? re[t.CARETLOOSE] : re[t.CARET]
   const z = options.includePrerelease ? '-0' : ''
@@ -356,13 +362,14 @@ const replaceCaret = (comp, options) => {
   })
 }
 
 const replaceXRanges = (comp, options) => {
   debug('replaceXRanges', comp, options)
-  return comp.split(/\s+/).map((c) => {
-    return replaceXRange(c, options)
-  }).join(' ')
+  return comp
+    .split(/\s+/)
+    .map((c) => replaceXRange(c, options))
+    .join(' ')
 }
 
 const replaceXRange = (comp, options) => {
   comp = comp.trim()
   const r = options.loose ? re[t.XRANGELOOSE] : re[t.XRANGE]
@@ -441,16 +448,19 @@ const replaceXRange = (comp, options) => {
 // Because * is AND-ed with everything else in the comparator,
 // and '' means "any version", just remove the *s entirely.
 const replaceStars = (comp, options) => {
   debug('replaceStars', comp, options)
   // Looseness is ignored here.  star is always as loose as it gets!
-  return comp.trim().replace(re[t.STAR], '')
+  return comp
+    .trim()
+    .replace(re[t.STAR], '')
 }
 
 const replaceGTE0 = (comp, options) => {
   debug('replaceGTE0', comp, options)
-  return comp.trim()
+  return comp
+    .trim()
     .replace(re[options.includePrerelease ? t.GTE0PRE : t.GTE0], '')
 }
 
 // This function is passed to string.replace(re[t.HYPHENRANGE])
 // M, m, patch, prerelease, build
@@ -484,11 +494,11 @@ const hyphenReplace = incPr => ($0,
     to = `<${tM}.${tm}.${+tp + 1}-0`
   } else {
     to = `<=${to}`
   }
 
-  return (`${from} ${to}`).trim()
+  return `${from} ${to}`.trim()
 }
 
 const testSet = (set, version, options) => {
   for (let i = 0; i < set.length; i++) {
     if (!set[i].test(version)) {
diff --git a/classes/semver.js b/classes/semver.js
index 99dbe82..e1208fe 100644
--- a/classes/semver.js
+++ b/classes/semver.js
@@ -1,8 +1,8 @@
 const debug = require('../internal/debug')
 const { MAX_LENGTH, MAX_SAFE_INTEGER } = require('../internal/constants')
-const { re, t } = require('../internal/re')
+const { safeRe: re, t } = require('../internal/re')
 
 const parseOptions = require('../internal/parse-options')
 const { compareIdentifiers } = require('../internal/identifiers')
 class SemVer {
   constructor (version, options) {
diff --git a/functions/coerce.js b/functions/coerce.js
index 2e01452..febbff9 100644
--- a/functions/coerce.js
+++ b/functions/coerce.js
@@ -1,8 +1,8 @@
 const SemVer = require('../classes/semver')
 const parse = require('./parse')
-const { re, t } = require('../internal/re')
+const { safeRe: re, t } = require('../internal/re')
 
 const coerce = (version, options) => {
   if (version instanceof SemVer) {
     return version
   }
diff --git a/internal/re.js b/internal/re.js
index ed88398..f73ef1a 100644
--- a/internal/re.js
+++ b/internal/re.js
@@ -2,20 +2,31 @@ const { MAX_SAFE_COMPONENT_LENGTH } = require('./constants')
 const debug = require('./debug')
 exports = module.exports = {}
 
 // The actual regexps go on exports.re
 const re = exports.re = []
+const safeRe = exports.safeRe = []
 const src = exports.src = []
 const t = exports.t = {}
 let R = 0
 
 const createToken = (name, value, isGlobal) => {
+  // Replace all greedy whitespace to prevent regex dos issues. These regex are
+  // used internally via the safeRe object since all inputs in this library get
+  // normalized first to trim and collapse all extra whitespace. The original
+  // regexes are exported for userland consumption and lower level usage. A
+  // future breaking change could export the safer regex only with a note that
+  // all input should have extra whitespace removed.
+  const safe = value
+    .split('\\s*').join('\\s{0,1}')
+    .split('\\s+').join('\\s')
   const index = R++
   debug(name, index, value)
   t[name] = index
   src[index] = value
   re[index] = new RegExp(value, isGlobal ? 'g' : undefined)
+  safeRe[index] = new RegExp(safe, isGlobal ? 'g' : undefined)
 }
 
 // The following Regular Expressions can be used for tokenizing,
 // validating, and parsing SemVer version strings.
 
diff --git a/package.json b/package.json
index 204e008..7207703 100644
--- a/package.json
+++ b/package.json
@@ -35,11 +35,11 @@
     "index.js",
     "preload.js",
     "range.bnf"
   ],
   "tap": {
-    "check-coverage": true,
+    "timeout": 30,
     "coverage-map": "map.js",
     "nyc-arg": [
       "--exclude",
       "tap-snapshots/**"
     ]
diff --git a/test/integration/whitespace.js b/test/integration/whitespace.js
new file mode 100644
index 0000000..eb9744d
--- /dev/null
+++ b/test/integration/whitespace.js
@@ -0,0 +1,39 @@
+const { test } = require('tap')
+const Range = require('../../classes/range')
+const SemVer = require('../../classes/semver')
+const Comparator = require('../../classes/comparator')
+const validRange = require('../../ranges/valid')
+const minVersion = require('../../ranges/min-version')
+const minSatisfying = require('../../ranges/min-satisfying')
+const maxSatisfying = require('../../ranges/max-satisfying')
+
+const s = (n = 500000) => ' '.repeat(n)
+
+test('regex dos via range whitespace', (t) => {
+  // a range with this much whitespace would take a few minutes to process if
+  // any redos susceptible regexes were used. there is a global tap timeout per
+  // file set in the package.json that will error if this test takes too long.
+  const r = `1.2.3 ${s()} <1.3.0`
+
+  t.equal(new Range(r).range, '1.2.3 <1.3.0')
+  t.equal(validRange(r), '1.2.3 <1.3.0')
+  t.equal(minVersion(r).version, '1.2.3')
+  t.equal(minSatisfying(['1.2.3'], r), '1.2.3')
+  t.equal(maxSatisfying(['1.2.3'], r), '1.2.3')
+
+  t.end()
+})
+
+test('semver version', (t) => {
+  const v = `${s(125)}1.2.3${s(125)}`
+  const tooLong = `${s()}1.2.3${s()}`
+  t.equal(new SemVer(v).version, '1.2.3')
+  t.throws(() => new SemVer(tooLong))
+  t.end()
+})
+
+test('comparator', (t) => {
+  const c = `${s()}<${s()}1.2.3${s()}`
+  t.equal(new Comparator(c).value, '<1.2.3')
+  t.end()
+})
diff --git a/test/internal/re.js b/test/internal/re.js
index 1aad22b..2851b32 100644
--- a/test/internal/re.js
+++ b/test/internal/re.js
@@ -1,7 +1,7 @@
 const { test } = require('tap')
-const { src, re } = require('../../internal/re')
+const { src, re, safeRe } = require('../../internal/re')
 const semver = require('../../')
 
 test('has a list of src, re, and tokens', (t) => {
   t.match(Object.assign({}, semver), {
     src: Array,
@@ -11,7 +11,13 @@ test('has a list of src, re, and tokens', (t) => {
   re.forEach(r => t.match(r, RegExp, 'regexps are regexps'))
   src.forEach(s => t.match(s, String, 'src is strings'))
   for (const i in semver.tokens) {
     t.match(semver.tokens[i], Number, 'tokens are numbers')
   }
+
+  safeRe.forEach(r => {
+    t.notMatch(r.source, '\\s+', 'safe regex do not contain greedy whitespace')
+    t.notMatch(r.source, '\\s*', 'safe regex do not contain greedy whitespace')
+  })
+
   t.end()
 })
diff --git a/test/map.js b/test/map.js
index 8179e71..5c36eb7 100644
--- a/test/map.js
+++ b/test/map.js
@@ -1,49 +1,46 @@
 const t = require('tap')
+const { resolve, join, relative, extname, dirname, basename } = require('path')
+const { statSync, readdirSync } = require('fs')
+const map = require('../map.js')
+const pkg = require('../package.json')
 
-// ensure that the coverage map maps all coverage
-const ignore = [
-  '.git',
-  '.github',
-  '.commitlintrc.js',
-  '.eslintrc.js',
-  '.eslintrc.local.js',
-  'node_modules',
-  'coverage',
-  'tap-snapshots',
-  'test',
-  'fixtures',
-]
+const ROOT = resolve(__dirname, '..')
+const TEST = join(ROOT, 'test')
+const IGNORE_DIRS = ['fixtures', 'integration']
 
-const { statSync, readdirSync } = require('fs')
-const find = (folder, set = [], root = true) => {
-  const ent = readdirSync(folder)
-  set.push(...ent.filter(f => !ignore.includes(f) && /\.m?js$/.test(f)).map(f => folder + '/' + f))
-  for (const e of ent.filter(f => !ignore.includes(f) && !/\.m?js$/.test(f))) {
-    if (statSync(folder + '/' + e).isDirectory()) {
-      find(folder + '/' + e, set, false)
+const getFile = (f) => {
+  try {
+    if (statSync(f).isFile()) {
+      return extname(f) === '.js' ? [f] : []
     }
+  } catch {
+    return []
   }
-  if (!root) {
-    return
-  }
-  return set.map(f => f.slice(folder.length + 1)
-    .replace(/\\/g, '/'))
-    .sort((a, b) => a.localeCompare(b))
 }
 
-const { resolve } = require('path')
-const root = resolve(__dirname, '..')
+const walk = (item, res = []) => getFile(item) || readdirSync(item)
+  .map(f => join(item, f))
+  .reduce((acc, f) => acc.concat(statSync(f).isDirectory() ? walk(f, res) : getFile(f)), [])
+  .filter(Boolean)
 
-const sut = find(root)
-const tests = find(root + '/test')
-t.strictSame(sut, tests, 'test files should match system files')
-const map = require('../map.js')
+const walkAll = (items, relativeTo) => items
+  .reduce((acc, f) => acc.concat(walk(join(ROOT, f))), [])
+  .map((f) => relative(relativeTo, f))
+  .sort()
 
-for (const testFile of tests) {
-  t.test(testFile, t => {
-    t.plan(1)
-    // cast to an array, since map() can return a string or array
-    const systemFiles = [].concat(map(testFile))
-    t.ok(systemFiles.some(sys => sut.includes(sys)), 'test covers a file')
-  })
-}
+t.test('tests match system', t => {
+  const sut = walkAll([pkg.tap['coverage-map'], ...pkg.files], ROOT)
+  const tests = walkAll([basename(TEST)], TEST)
+    .filter(f => !IGNORE_DIRS.includes(dirname(f)))
+
+  t.strictSame(sut, tests, 'test files should match system files')
+
+  for (const f of tests) {
+    t.test(f, t => {
+      t.plan(1)
+      t.ok(sut.includes(map(f)), 'test covers a file')
+    })
+  }
+
+  t.end()
+})

Vulnerable code: const { re, t } = require('../internal/re')
    // First, split based on boolean or ||
    this.set = range
      .map(r => this.parseRange(r.trim()))
      throw new TypeError(`Invalid SemVer Range: ${range}`)
      .map((comps) => {
        return comps.join(' ').trim()
      })
    range = range.trim()

    // normalize spaces
    range = range.split(/\s+/).join(' ')

  re,
const replaceTildes = (comp, options) =>
  comp.trim().split(/\s+/).map((c) => {
    return replaceTilde(c, options)
  }).join(' ')
const replaceCarets = (comp, options) =>
  comp.trim().split(/\s+/).map((c) => {
    return replaceCaret(c, options)
  }).join(' ')
  return comp.split(/\s+/).map((c) => {
    return replaceXRange(c, options)
  }).join(' ')
  return comp.trim().replace(re[t.STAR], '')
  return comp.trim()
  return (`${from} ${to}`).trim()
const { re, t } = require('../internal/re')
const { re, t } = require('../internal/re')
    "check-coverage": true,
const { src, re } = require('../../internal/re')
// ensure that the coverage map maps all coverage
const ignore = [
  '.git',
  '.github',
  '.commitlintrc.js',
  '.eslintrc.js',
  '.eslintrc.local.js',
  'node_modules',
  'coverage',
  'tap-snapshots',
  'test',
  'fixtures',
]
const { statSync, readdirSync } = require('fs')
const find = (folder, set = [], root = true) => {
  const ent = readdirSync(folder)
  set.push(...ent.filter(f => !ignore.includes(f) && /\.m?js$/.test(f)).map(f => folder + '/' + f))
  for (const e of ent.filter(f => !ignore.includes(f) && !/\.m?js$/.test(f))) {
    if (statSync(folder + '/' + e).isDirectory()) {
      find(folder + '/' + e, set, false)
  if (!root) {
    return
  }
  return set.map(f => f.slice(folder.length + 1)
    .replace(/\\/g, '/'))
    .sort((a, b) => a.localeCompare(b))
const { resolve } = require('path')
const root = resolve(__dirname, '..')
const sut = find(root)
const tests = find(root + '/test')
t.strictSame(sut, tests, 'test files should match system files')
const map = require('../map.js')
for (const testFile of tests) {
  t.test(testFile, t => {
    t.plan(1)
    // cast to an array, since map() can return a string or array
    const systemFiles = [].concat(map(testFile))
    t.ok(systemFiles.some(sys => sut.includes(sys)), 'test covers a file')
  })
}
Fixed code:     comp = comp.trim().split(/\s+/).join(' ')
const { safeRe: re, t } = require('../internal/re')
    // First reduce all whitespace as much as possible so we do not have to rely
    // on potentially slow regexes like \s*. This is then stored and used for
    // future error messages as well.
      .trim()
      .split(/\s+/)
      .join(' ')

    // First, split on ||
    this.set = this.raw
      .map(r => this.parseRange(r))
      throw new TypeError(`Invalid SemVer Range: ${this.raw}`)
      .map((comps) => comps.join(' ').trim())
  safeRe: re,
const replaceTildes = (comp, options) => {
  return comp
    .trim()
    .split(/\s+/)
    .map((c) => replaceTilde(c, options))
    .join(' ')
}
const replaceCarets = (comp, options) => {
  return comp
    .trim()
    .split(/\s+/)
    .map((c) => replaceCaret(c, options))
    .join(' ')
}
  return comp
    .split(/\s+/)
    .map((c) => replaceXRange(c, options))
    .join(' ')
  return comp
    .trim()
    .replace(re[t.STAR], '')
  return comp
    .trim()
  return `${from} ${to}`.trim()
const { safeRe: re, t } = require('../internal/re')
const { safeRe: re, t } = require('../internal/re')
const safeRe = exports.safeRe = []
  // Replace all greedy whitespace to prevent regex dos issues. These regex are
  // used internally via the safeRe object since all inputs in this library get
  // normalized first to trim and collapse all extra whitespace. The original
  // regexes are exported for userland consumption and lower level usage. A
  // future breaking change could export the safer regex only with a note that
  // all input should have extra whitespace removed.
  const safe = value
    .split('\\s*').join('\\s{0,1}')
    .split('\\s+').join('\\s')
  safeRe[index] = new RegExp(safe, isGlobal ? 'g' : undefined)
    "timeout": 30,
const { test } = require('tap')
const Range = require('../../classes/range')
const SemVer = require('../../classes/semver')
const Comparator = require('../../classes/comparator')
const validRange = require('../../ranges/valid')
const minVersion = require('../../ranges/min-version')
const minSatisfying = require('../../ranges/min-satisfying')
const maxSatisfying = require('../../ranges/max-satisfying')

const s = (n = 500000) => ' '.repeat(n)

test('regex dos via range whitespace', (t) => {
  // a range with this much whitespace would take a few minutes to process if
  // any redos susceptible regexes were used. there is a global tap timeout per
  // file set in the package.json that will error if this test takes too long.
  const r = `1.2.3 ${s()} <1.3.0`

  t.equal(new Range(r).range, '1.2.3 <1.3.0')
  t.equal(validRange(r), '1.2.3 <1.3.0')
  t.equal(minVersion(r).version, '1.2.3')
  t.equal(minSatisfying(['1.2.3'], r), '1.2.3')
  t.equal(maxSatisfying(['1.2.3'], r), '1.2.3')

  t.end()
})

test('semver version', (t) => {
  const v = `${s(125)}1.2.3${s(125)}`
  const tooLong = `${s()}1.2.3${s()}`
  t.equal(new SemVer(v).version, '1.2.3')
  t.throws(() => new SemVer(tooLong))
  t.end()
})

test('comparator', (t) => {
  const c = `${s()}<${s()}1.2.3${s()}`
  t.equal(new Comparator(c).value, '<1.2.3')
  t.end()
})
const { src, re, safeRe } = require('../../internal/re')

  safeRe.forEach(r => {
    t.notMatch(r.source, '\\s+', 'safe regex do not contain greedy whitespace')
    t.notMatch(r.source, '\\s*', 'safe regex do not contain greedy whitespace')
  })

const { resolve, join, relative, extname, dirname, basename } = require('path')
const { statSync, readdirSync } = require('fs')
const map = require('../map.js')
const pkg = require('../package.json')
const ROOT = resolve(__dirname, '..')
const TEST = join(ROOT, 'test')
const IGNORE_DIRS = ['fixtures', 'integration']
const getFile = (f) => {
  try {
    if (statSync(f).isFile()) {
      return extname(f) === '.js' ? [f] : []
  } catch {
    return []
const walk = (item, res = []) => getFile(item) || readdirSync(item)
  .map(f => join(item, f))
  .reduce((acc, f) => acc.concat(statSync(f).isDirectory() ? walk(f, res) : getFile(f)), [])
  .filter(Boolean)
const walkAll = (items, relativeTo) => items
  .reduce((acc, f) => acc.concat(walk(join(ROOT, f))), [])
  .map((f) => relative(relativeTo, f))
  .sort()
t.test('tests match system', t => {
  const sut = walkAll([pkg.tap['coverage-map'], ...pkg.files], ROOT)
  const tests = walkAll([basename(TEST)], TEST)
    .filter(f => !IGNORE_DIRS.includes(dirname(f)))

  t.strictSame(sut, tests, 'test files should match system files')

  for (const f of tests) {
    t.test(f, t => {
      t.plan(1)
      t.ok(sut.includes(map(f)), 'test covers a file')
    })
  }

  t.end()
})