Skip to content

fix(accept): replace regex split to mitigate ReDoS#4758

Merged
yusukebe merged 5 commits intohonojs:mainfrom
EdamAme-x:fix/accept-redos
Mar 6, 2026
Merged

fix(accept): replace regex split to mitigate ReDoS#4758
yusukebe merged 5 commits intohonojs:mainfrom
EdamAme-x:fix/accept-redos

Conversation

@EdamAme-x
Copy link
Contributor

@EdamAme-x EdamAme-x commented Feb 23, 2026

Summary

In proxy configurations without header size limits, this can cause real impact.

Proof

curl http://127.0.0.1:3000/ \                                                                                                                                                                                                                                                                       
    -H "Accept-Language: $(node -e "process.stdout.write('a;'.repeat(16000) + '\"')")"
[                                                                                                                                                                                                                                                                                     
 {"segments": 4000, "time": 12.8},
 {"segments": 8000, "time": 51.07},                                                                                                                                                                                                                                           
 {"segments": 16000, "time": 203.52}                                                                                                                                                                                                                                          
]
import {
    Hono
} from 'hono'
import {
    languageDetector
} from 'hono/language'

async function main() {
    const app = new Hono()
    app.use('*', languageDetector({
        supportedLanguages: ['en', 'ja'],
        fallbackLanguage: 'en'
    }))
    app.get('/', (c) => c.text(String(c.get('language'))))

    const run = async (segments: number) => {
        const v = 'a;'.repeat(segments) + '"'
        const req = new Request('http://localhost/', {
            headers: {
                'accept-language': v
            },
        })

        const t0 = performance.now()
        const res = await app.request(req)
        await res.text()
        return {
            segments,
            time: Number((performance.now() - t0).toFixed(2))
        }
    }

    const a = await run(4000)
    const b = await run(8000)
    const c = await run(16000)

    console.log(JSON.stringify([
        a,
        b,
        c
    ], null, 2))
}

main().catch(console.error)

The author should do the following, if applicable

  • Add tests
  • Run tests
  • bun run format:fix && bun run lint:fix to format the code

@codecov
Copy link

codecov bot commented Feb 23, 2026

Codecov Report

❌ Patch coverage is 98.44560% with 3 lines in your changes missing coverage. Please review.
✅ Project coverage is 91.55%. Comparing base (df97e5f) to head (0866c10).
⚠️ Report is 19 commits behind head on main.

Files with missing lines Patch % Lines
src/utils/accept.ts 98.44% 3 Missing ⚠️
Additional details and impacted files
@@            Coverage Diff             @@
##             main    #4758      +/-   ##
==========================================
+ Coverage   91.48%   91.55%   +0.07%     
==========================================
  Files         177      177              
  Lines       11551    11736     +185     
  Branches     3353     3432      +79     
==========================================
+ Hits        10567    10745     +178     
- Misses        983      990       +7     
  Partials        1        1              

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:
  • ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.
  • 📦 JS Bundle Analysis: Save yourself from yourself by tracking and limiting bundle sizes in JS merges.

@usualoma
Copy link
Member

Hi @EdamAme-x
Thanks for creating the pull request!
It's definitely a regular expression with potential ReDoS issues.

However, while this module can parse standard headers without problems, I believe the following current test is buggy because the expected value is incorrect. (b should be 2, not "2", and e is invalid, so it should either throw an error or be ignored).

    test('handles complex parameters', () => {
      const header = 'type;a=1;b="2";c=\'3\';d="semi;colon";e="nested"quoted""'
      const result = parseAccept(header)
      expect(result[0].params).toEqual({
        a: '1',
        b: '"2"',

        c: "'3'",
        d: '"semi;colon"',
        e: '"nested"quoted""',
      })
    })

I think the PR's proposed fix was made to pass the current (buggy) tests, but I'm hesitant about whether we should leave it as-is.

With the current code, it can't handle patterns where there's a comma inside double quotes either (even though this is a valid header)...

type;a=1;b="2,2"

I know this is asking a lot, but could we refactor the whole thing?

@EdamAme-x
Copy link
Contributor Author

EdamAme-x commented Feb 25, 2026

sure

@usualoma
Copy link
Member

Hi @EdamAme-x

Thank you for the update!

While this strays from the ReDoS fixes, I'd like to take this opportunity to handle the entire parsing in one pass.

(It will require a complete rewrite, but) I've created a PR against your branch. Would you mind pulling it in?

EdamAme-x#12

benchmark

accept.bench.ts
import { bench, describe } from 'vitest'

// ---------------------------------------------------------------------------
// main (regex-based)
// ---------------------------------------------------------------------------
const Main = (() => {
  interface Accept {
    type: string
    params: Record<string, string>
    q: number
  }

  const parseAcceptValueRegex = /;(?=(?:(?:[^"]*"){2})*[^"]*$)/
  const parseAcceptValue = ({ value, index }: { value: string; index: number }) => {
    const parts = value
      .trim()
      .split(parseAcceptValueRegex)
      .map((s) => s.trim())
    const type = parts[0]
    if (!type) {
      return null
    }

    const params = parseParams(parts.slice(1))
    const q = parseQuality(params.q)

    return { type, params, q, index }
  }

  const parseParams = (paramParts: string[]): Record<string, string> => {
    return paramParts.reduce<Record<string, string>>((acc, param) => {
      const [key, val] = param.split('=').map((s) => s.trim())
      if (key && val) {
        acc[key] = val
      }
      return acc
    }, {})
  }

  const parseQuality = (qVal?: string): number => {
    if (qVal === undefined) {
      return 1
    }
    if (qVal === '') {
      return 1
    }
    if (qVal === 'NaN') {
      return 0
    }
    const num = Number(qVal)
    if (num === Infinity) {
      return 1
    }
    if (num === -Infinity) {
      return 0
    }
    if (Number.isNaN(num)) {
      return 1
    }
    if (num < 0 || num > 1) {
      return 1
    }
    return num
  }

  const sortByQualityAndIndex = (a: Accept & { index: number }, b: Accept & { index: number }) => {
    const qDiff = b.q - a.q
    if (qDiff !== 0) {
      return qDiff
    }
    return a.index - b.index
  }

  const parseAccept = (acceptHeader: string): Accept[] => {
    if (!acceptHeader) {
      return []
    }
    const acceptValues = acceptHeader.split(',').map((value, index) => ({ value, index }))
    return acceptValues
      .map(parseAcceptValue)
      .filter((item): item is Accept & { index: number } => Boolean(item))
      .sort(sortByQualityAndIndex)
      .map(({ type, params, q }) => ({ type, params, q }))
  }

  return { parseAccept }
})()

// ---------------------------------------------------------------------------
// 947b22f4 (splitByDelimiter)
// ---------------------------------------------------------------------------
const C947b22f4 = (() => {
  interface Accept {
    type: string
    params: Record<string, string>
    q: number
  }

  const splitByDelimiterOutsideQuotes = (value: string, delimiter: string): string[] => {
    const parts: string[] = []
    let current = ''
    let inQuotes = false
    let escaped = false
    for (let i = 0; i < value.length; i++) {
      const char = value[i]
      if (escaped) {
        current += char
        escaped = false
        continue
      }
      if (char === '\\' && inQuotes) {
        current += char
        escaped = true
        continue
      }
      if (char === '"') {
        inQuotes = !inQuotes
        current += char
        continue
      }
      if (char === delimiter && !inQuotes) {
        parts.push(current)
        current = ''
        continue
      }
      current += char
    }
    parts.push(current)
    return parts
  }

  const parseAcceptValue = ({ value, index }: { value: string; index: number }) => {
    const parts = splitByDelimiterOutsideQuotes(value.trim(), ';').map((s) => s.trim())
    const type = parts[0]
    if (!type) {
      return null
    }
    const params = parseParams(parts.slice(1))
    const q = parseQuality(params.q)
    return { type, params, q, index }
  }

  const parseParams = (paramParts: string[]): Record<string, string> => {
    return paramParts.reduce<Record<string, string>>((acc, param) => {
      const separatorIndex = param.indexOf('=')
      if (separatorIndex <= 0) {
        return acc
      }
      const key = param.slice(0, separatorIndex).trim()
      const rawVal = param.slice(separatorIndex + 1).trim()
      if (!key || !rawVal) {
        return acc
      }
      const val = parseParamValue(rawVal)
      if (val !== null) {
        acc[key] = val
      }
      return acc
    }, {})
  }

  const parseParamValue = (value: string): string | null => {
    if (value[0] !== '"') {
      return value.includes('=') ? null : value
    }
    return parseQuotedString(value)
  }

  const parseQuotedString = (value: string): string | null => {
    let unescaped = ''
    let escaped = false
    for (let i = 1; i < value.length; i++) {
      const char = value[i]
      if (escaped) {
        unescaped += char
        escaped = false
        continue
      }
      if (char === '\\') {
        escaped = true
        continue
      }
      if (char === '"') {
        return value.slice(i + 1).trim() ? null : unescaped
      }
      unescaped += char
    }
    return null
  }

  const parseQuality = (qVal?: string): number => {
    if (qVal === undefined) {
      return 1
    }
    if (qVal === '') {
      return 1
    }
    if (qVal === 'NaN') {
      return 0
    }
    const num = Number(qVal)
    if (num === Infinity) {
      return 1
    }
    if (num === -Infinity) {
      return 0
    }
    if (Number.isNaN(num)) {
      return 1
    }
    if (num < 0 || num > 1) {
      return 1
    }
    return num
  }

  const sortByQualityAndIndex = (a: Accept & { index: number }, b: Accept & { index: number }) => {
    const qDiff = b.q - a.q
    if (qDiff !== 0) {
      return qDiff
    }
    return a.index - b.index
  }

  const parseAccept = (acceptHeader: string): Accept[] => {
    if (!acceptHeader) {
      return []
    }
    const acceptValues = splitByDelimiterOutsideQuotes(acceptHeader, ',').map((value, index) => ({
      value,
      index,
    }))
    return acceptValues
      .map(parseAcceptValue)
      .filter((item): item is Accept & { index: number } => Boolean(item))
      .sort(sortByQualityAndIndex)
      .map(({ type, params, q }) => ({ type, params, q }))
  }

  return { parseAccept }
})()

// ---------------------------------------------------------------------------
// c829099 (single-pass)
// ---------------------------------------------------------------------------
const Cc829099 = (() => {
  interface Accept {
    type: string
    params: Record<string, string>
    q: number
  }

  const isWhitespace = (char: number): boolean =>
    char === 32 || char === 9 || char === 10 || char === 13

  const consumeWhitespace = (acceptHeader: string, startIndex: number): number => {
    while (startIndex < acceptHeader.length) {
      if (!isWhitespace(acceptHeader.charCodeAt(startIndex))) {
        break
      }
      startIndex++
    }
    return startIndex
  }

  const ignoreTrailingWhitespace = (acceptHeader: string, startIndex: number): number => {
    while (startIndex > 0) {
      if (!isWhitespace(acceptHeader.charCodeAt(startIndex - 1))) {
        break
      }
      startIndex--
    }
    return startIndex
  }

  const skipInvalidParam = (acceptHeader: string, startIndex: number): [number, boolean] => {
    while (startIndex < acceptHeader.length) {
      const char = acceptHeader.charCodeAt(startIndex)
      if (char === 59) {
        return [startIndex + 1, true]
      }
      if (char === 44) {
        return [startIndex + 1, false]
      }
      startIndex++
    }
    return [startIndex, false]
  }

  const skipInvalidAcceptValue = (acceptHeader: string, startIndex: number): number => {
    let i = startIndex
    let inQuotes = false
    while (i < acceptHeader.length) {
      const char = acceptHeader.charCodeAt(i)
      if (inQuotes && char === 92) {
        i++
      } else if (char === 34) {
        inQuotes = !inQuotes
      } else if (!inQuotes && char === 44) {
        return i + 1
      }
      i++
    }
    return i
  }

  const getNextParam = (
    acceptHeader: string,
    startIndex: number
  ): [number, string | undefined, string | undefined, boolean] => {
    startIndex = consumeWhitespace(acceptHeader, startIndex)
    let i = startIndex
    let key: string | undefined
    let value: string | undefined
    let hasNext = false
    while (i < acceptHeader.length) {
      const char = acceptHeader.charCodeAt(i)
      if (char === 61) {
        key = acceptHeader.slice(startIndex, ignoreTrailingWhitespace(acceptHeader, i))
        i++
        break
      }
      if (char === 59) {
        return [i + 1, undefined, undefined, true]
      }
      if (char === 44) {
        return [i + 1, undefined, undefined, false]
      }
      i++
    }
    if (key === undefined) {
      return [i, undefined, undefined, false]
    }

    i = consumeWhitespace(acceptHeader, i)
    if (acceptHeader.charCodeAt(i) === 61) {
      const skipResult = skipInvalidParam(acceptHeader, i + 1)
      return [skipResult[0], key, undefined, skipResult[1]]
    }

    let inQuotes = false
    const paramStartIndex = i
    while (i < acceptHeader.length) {
      const char = acceptHeader.charCodeAt(i)
      if (inQuotes && char === 92) {
        i++
      } else if (char === 34) {
        if (inQuotes) {
          let nextIndex = consumeWhitespace(acceptHeader, i + 1)
          const nextChar = acceptHeader.charCodeAt(nextIndex)
          if (nextIndex < acceptHeader.length && !(nextChar === 59 || nextChar === 44)) {
            const skipResult = skipInvalidParam(acceptHeader, nextIndex)
            return [skipResult[0], key, undefined, skipResult[1]]
          }
          value = acceptHeader.slice(paramStartIndex + 1, i)
          if (value.includes('\\')) {
            value = value.replace(/\\(.)/g, '$1')
          }
          if (nextChar === 44) {
            return [nextIndex + 1, key, value, false]
          }
          if (nextChar === 59) {
            hasNext = true
            nextIndex++
          }
          i = nextIndex
          break
        }
        inQuotes = true
      } else if (!inQuotes && (char === 59 || char === 44)) {
        value = acceptHeader.slice(paramStartIndex, ignoreTrailingWhitespace(acceptHeader, i))
        if (char === 59) {
          hasNext = true
        }
        i++
        break
      }
      i++
    }
    return [
      i,
      key,
      value ?? acceptHeader.slice(paramStartIndex, ignoreTrailingWhitespace(acceptHeader, i)),
      hasNext,
    ]
  }

  const getNextAcceptValue = (
    acceptHeader: string,
    startIndex: number
  ): [number, Accept | undefined] => {
    const accept: Accept = { type: '', params: {}, q: 1 }
    startIndex = consumeWhitespace(acceptHeader, startIndex)
    let i = startIndex
    while (i < acceptHeader.length) {
      const char = acceptHeader.charCodeAt(i)
      if (char === 59 || char === 44) {
        accept.type = acceptHeader.slice(startIndex, ignoreTrailingWhitespace(acceptHeader, i))
        i++
        if (char === 44) {
          return [i, accept.type ? accept : undefined]
        }
        if (!accept.type) {
          return [skipInvalidAcceptValue(acceptHeader, i), undefined]
        }
        break
      }
      i++
    }
    if (!accept.type) {
      accept.type = acceptHeader.slice(
        startIndex,
        ignoreTrailingWhitespace(acceptHeader, acceptHeader.length)
      )
      return [acceptHeader.length, accept.type ? accept : undefined]
    }

    let param: string | undefined
    let value: string | undefined
    let hasNext: boolean
    while (i < acceptHeader.length) {
      ;[i, param, value, hasNext] = getNextParam(acceptHeader, i)
      if (param && value) {
        accept.params[param] = value
      }
      if (!hasNext) {
        break
      }
    }
    return [i, accept] as [number, Accept]
  }

  const parseQuality = (qVal?: string): number => {
    if (qVal === undefined) {
      return 1
    }
    if (qVal === '') {
      return 1
    }
    if (qVal === 'NaN') {
      return 0
    }
    const num = Number(qVal)
    if (num === Infinity) {
      return 1
    }
    if (num === -Infinity) {
      return 0
    }
    if (Number.isNaN(num)) {
      return 1
    }
    if (num < 0 || num > 1) {
      return 1
    }
    return num
  }

  const parseAccept = (acceptHeader: string): Accept[] => {
    if (!acceptHeader) {
      return []
    }
    const values: Accept[] = []
    let i = 0
    let accept: Accept | undefined
    let requiresSort = false
    let lastAccept: Accept | undefined
    while (i < acceptHeader.length) {
      ;[i, accept] = getNextAcceptValue(acceptHeader, i)
      if (accept) {
        accept.q = parseQuality(accept.params.q)
        values.push(accept)
        if (lastAccept && lastAccept.q < accept.q) {
          requiresSort = true
        }
        lastAccept = accept
      }
    }
    if (requiresSort) {
      values.sort((a, b) => b.q - a.q)
    }
    return values
  }

  return { parseAccept }
})()

// ---------------------------------------------------------------------------
// Benchmark
// ---------------------------------------------------------------------------
const inputs = {
  'simple: text/html': 'text/html',
  'standard: 3 types with q': 'text/html, application/json;q=0.9, */*;q=0.8',
  'many: 10 types':
    'text/html, application/xhtml+xml, application/xml;q=0.9, text/plain;q=0.8, image/webp, image/apng, */*;q=0.7, application/signed-exchange;v=b3;q=0.6, text/css;q=0.5, application/json;q=0.4',
  'quoted params': 'text/html;param="value with spaces";q=0.9, application/json;charset="utf-8"',
  'ReDoS pattern': 'a' + ']'.repeat(40),
} as const

for (const [label, input] of Object.entries(inputs)) {
  describe(label, () => {
    bench('main (regex)', () => {
      Main.parseAccept(input)
    })

    bench('947b22f4 (splitByDelimiter)', () => {
      C947b22f4.parseAccept(input)
    })

    bench('c829099 (single-pass)', () => {
      Cc829099.parseAccept(input)
    })
  })
}
% npx vitest bench --project main benchmarks/accept/accept.bench.ts
Benchmarking is an experimental feature.
Breaking changes might not follow SemVer, please pin Vitest's version when using it.

 DEV  v3.2.4


 ✓  main  benchmarks/accept/accept.bench.ts > simple: text/html 5373ms
     name                                    hz     min     max    mean     p75     p99    p995    p999     rme  samples
   · main (regex)                  6,249,359.94  0.0000  4.9963  0.0002  0.0002  0.0003  0.0003  0.0014  ±1.96%  3124681
   · 947b22f4 (splitByDelimiter)   4,560,439.52  0.0001  0.1684  0.0002  0.0002  0.0003  0.0004  0.0008  ±0.13%  2280221
   · c829099 (single-pass)        13,502,436.24  0.0000  6.4372  0.0001  0.0001  0.0001  0.0002  0.0004  ±2.91%  6751219

 ✓  main  benchmarks/accept/accept.bench.ts > standard: 3 types with q 2689ms
     name                                   hz     min     max    mean     p75     p99    p995    p999     rme  samples
   · main (regex)                 1,252,902.40  0.0006  6.9349  0.0008  0.0008  0.0019  0.0020  0.0047  ±2.94%   626452
   · 947b22f4 (splitByDelimiter)    931,436.42  0.0009  0.1975  0.0011  0.0010  0.0015  0.0018  0.0054  ±0.34%   465719
   · c829099 (single-pass)        3,596,223.48  0.0002  0.2347  0.0003  0.0003  0.0004  0.0005  0.0009  ±0.29%  1798112

 ✓  main  benchmarks/accept/accept.bench.ts > many: 10 types 2000ms
     name                                 hz     min     max    mean     p75     p99    p995    p999     rme  samples
   · main (regex)                 396,381.38  0.0022  0.2144  0.0025  0.0025  0.0035  0.0055  0.0078  ±0.33%   198191
   · 947b22f4 (splitByDelimiter)  237,276.01  0.0037  0.2630  0.0042  0.0041  0.0067  0.0078  0.0196  ±0.34%   118639
   · c829099 (single-pass)        781,001.12  0.0011  0.2450  0.0013  0.0013  0.0017  0.0020  0.0053  ±0.28%   390501

 ✓  main  benchmarks/accept/accept.bench.ts > quoted params 2377ms
     name                                   hz     min     max    mean     p75     p99    p995    p999     rme  samples
   · main (regex)                 1,087,585.90  0.0007  0.2086  0.0009  0.0009  0.0013  0.0014  0.0044  ±0.34%   543793
   · 947b22f4 (splitByDelimiter)    522,050.19  0.0017  0.2065  0.0019  0.0019  0.0027  0.0053  0.0073  ±0.30%   261026
   · c829099 (single-pass)        1,998,735.27  0.0004  0.2270  0.0005  0.0005  0.0007  0.0008  0.0040  ±0.38%   999432

 ✓  main  benchmarks/accept/accept.bench.ts > ReDoS pattern 3610ms
     name                                   hz     min     max    mean     p75     p99    p995    p999     rme  samples
   · main (regex)                 5,020,245.33  0.0001  7.7531  0.0002  0.0002  0.0003  0.0004  0.0010  ±3.06%  2510123
   · 947b22f4 (splitByDelimiter)  1,240,443.63  0.0007  0.1826  0.0008  0.0008  0.0011  0.0012  0.0045  ±0.26%   620222
   · c829099 (single-pass)        6,123,986.76  0.0000  0.1929  0.0002  0.0002  0.0002  0.0003  0.0005  ±0.14%  3061994

 BENCH  Summary

   main  c829099 (single-pass) - benchmarks/accept/accept.bench.ts > simple: text/html
    2.16x faster than main (regex)
    2.96x faster than 947b22f4 (splitByDelimiter)

   main  c829099 (single-pass) - benchmarks/accept/accept.bench.ts > standard: 3 types with q
    2.87x faster than main (regex)
    3.86x faster than 947b22f4 (splitByDelimiter)

   main  c829099 (single-pass) - benchmarks/accept/accept.bench.ts > many: 10 types
    1.97x faster than main (regex)
    3.29x faster than 947b22f4 (splitByDelimiter)

   main  c829099 (single-pass) - benchmarks/accept/accept.bench.ts > quoted params
    1.84x faster than main (regex)
    3.83x faster than 947b22f4 (splitByDelimiter)

   main  c829099 (single-pass) - benchmarks/accept/accept.bench.ts > ReDoS pattern
    1.22x faster than main (regex)
    4.94x faster than 947b22f4 (splitByDelimiter)

refactor: improve accept header parsing
@EdamAme-x
Copy link
Contributor Author

Sorry! I missed it. I've just merged it now!

@usualoma
Copy link
Member

usualoma commented Mar 5, 2026

Thank you!

@usualoma
Copy link
Member

usualoma commented Mar 5, 2026

Hi @yusukebe
I've been asking @EdamAme-x for various things, which has taken some time, but I believe this PR will resolve the ReDoS issue and improve performance. How does this sound?

Copy link
Member

@yusukebe yusukebe left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM!

@yusukebe
Copy link
Member

yusukebe commented Mar 6, 2026

@EdamAme-x @usualoma Thank you! Merging.

@yusukebe yusukebe merged commit 5086956 into honojs:main Mar 6, 2026
20 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants