Some inputs taking long time to parse

[manunio]

Hi, While fuzzing using jazzer.js (for oss-fuzz) Parser().parse() was taking longer than exptected time to parse.

const commonmark = require('./dist/commonmark.js');

console.time("test")
const data = `---
pedaommen-

 >-t<!--
	This is another comm| baz | boParagraph two.

<!-- ntic: true
---

Just a [URL](/url/).

[URL and title](/url/ "title").

[URL and ttle](/url/ "title").

[URL and title](/url/  "title preceded by two spaces").

[URL and title](/url/	"title precede/ "title has spaces afterward"  ).

[URL and title]( e]( /url/has space/ "url has space and title").

[Empty]().`

new commonmark.Parser().parse(data)
console.timeEnd("test")

node test.js
test: 2:35.008 (m:ss.mmm)

[jgm]

I tried the input

---
pedaommen-

 >-t<!--
	This is another comm| baz | boParagraph two.

<!-- ntic: true
---

Just a [URL](/url/).

[URL and title](/url/ "title").

[URL and ttle](/url/ "title").

[URL and title](/url/  "title preceded by two spaces").

[URL and title](/url/	"title precede/ "title has spaces afterward"  ).

[URL and title]( e]( /url/has space/ "url has space and title").

[Empty]().

with the commonmark dingus and it reported a parse time of 1 ms.

I then tried your program above. It completed in 1.682 ms.

So...I can't reproduce this! Are you using the latest code from the repository?

[manunio]

Hi, Yes its latest, I have tested it against 97da298. I have attached the input file produced by jazzer.js maybe that helps :)

const commonmark = require('./dist/commonmark.js')
const fs = require('fs')
const data = fs.readFileSync('./timeout-64699b4ddd13b0497d6ec6ffb5f21d485800abfc.txt').toString()

console.time("test")
new commonmark.Parser().parse(data)
console.timeEnd("test")

timeout-64699b4ddd13b0497d6ec6ffb5f21d485800abfc.txt

[manunio]

Following are system configs

❯ node --version
v18.18.2

❯ npm --version
9.8.1

OS: Ubuntu 20.04.6 LTS x86_64

[manunio]

Tested it against master in github's codespace following is what it produces.

@manunio ➜ /workspaces/commonmark.js (master) $ cat fuzz.js
const commonmark = require('./dist/commonmark.js')
const fs = require('fs')
const data = fs.readFileSync('./timeout-64699b4ddd13b0497d6ec6ffb5f21d485800abfc.txt').toString()

console.time("test")
new commonmark.Parser().parse(data)
console.timeEnd("test")

@manunio ➜ /workspaces/commonmark.js (master) $ node fuzz.js 
test: 1:38.560 (m:ss.mmm)

@manunio ➜ /workspaces/commonmark.js (master) $ node --version
v20.8.1

@manunio ➜ /workspaces/commonmark.js (master) $ git --no-pager log --oneline | head -n 5
97da298 Track underscore bottom separately mod 3, like asterisk
df3ea1e Fix list tightness.
20b52e5 Fix "CommomMark" typo (#270)
9a16ff4 Declarations do not need a space, per the spec.
46538e5 Allow `<!doctype` to be case-insensitive.

[jgm]

I couldn't reproduce it with this fuzz.js and timeout file either. Odd! Can you reproduce it on the online "try commonmark" dingus?

I was using node v18.17.1, but it's hard to imagine that's the issue.

[manunio]

I was not able to reproduce it with https://spec.commonmark.org/dingus/ .
I think its using an older version as i found following changes in source introduced here 4874cb4.

- var reClosingCodeFence = /^(?:`{3,}|~{3,})(?= *$)/;
+ var reClosingCodeFence = /^(?:`{3,}|~{3,})(?=[ \t]*$)/;

Then i tried testing it locally against local dingus build, It was throwing following error in browser console

Uncaught InternalError: too much recursion
    match http://127.0.0.1:9000/commonmark.js:9270
    parseHtmlTag http://127.0.0.1:9000/commonmark.js:9385
    parseInline http://127.0.0.1:9000/commonmark.js:10115
    parseInlines http://127.0.0.1:9000/commonmark.js:10139
    processInlines http://127.0.0.1:9000/commonmark.js:11098
    parse http://127.0.0.1:9000/commonmark.js:11149
    parseAndRender http://127.0.0.1:9000/dingus.js:87
    Lodash 6
    jQuery 9
    onIframeLoad http://127.0.0.1:9000/dingus.js:122
    jQuery 8
    <anonymous> http://127.0.0.1:9000/dingus.js:141

at

commonmark.js/lib/inlines.js

Line 121 in 97da298

var m = re.exec(this.subject.slice(this.pos));

[jgm]

OK, I can reproduce it now. I had not regenerated dist/, that was the issue.

[jgm]

Bisected: the problem starts with commit 28c82d8 and the next one.
Here's the regex that is causing the problem:

 var HTMLCOMMENT = "<!-->|<!--->|<!--(?:[^-]+|-[^-]|--[^>])*-->"

[jgm]

OK, I can see why this causes pathological behavior!

[jgm]

This should fix it. Thanks for noticing the issue!

[manunio]

@jgm would be interested in Fuzzing this project at oss-fuzz? It's a free service run by Google to fuzz important open source projects. as an example cmark is already being fuzzed at oss-fuzz.

[jgm]

Sure.
Well, to be honest I'm not sure. I don't think it's as critical if a client-side library has a performance bug like this.

[manunio]

Sure. Well, to be honest I'm not sure. I don't think it's as critical if a client-side library has a performance bug like this.

Fair enough , I'm too more inclined towards other type of bugs for client slide libs, like the bugs found in yaml package(see below). The above mentioned performance reports were result of running it for few minutes , and i believe that through oss-fuzz and proper seed we will be able to discover other type of bugs. As for timeouts, we can fine tune input length so that it produces less noise.

• Fix malformed uri eemeli/yaml#498
• TypeError: object null is not iterable eemeli/yaml#501

Edit:
Jazzer.js was able to find prototype pollution vulnerability by their Prototype Pollution bug detector and many such bug-detectors are in works as per their earlier twitter post.

• https://www.code-intelligence.com/blog/cve-protobufjs-prototype-pollution-cve-2023-36665

[jgm]

What would be required to put it on oss-fuzz?