JavaScript ReDoS
-
Here's an example of ReDoS:
https://jsfiddle.net/fyswjnmb/4/
For those who don't want to run a single regular expression in their browser, here's a recording of a more complicated version of that: https://asciinema.org/a/203205
...so why are people using language implementations where it isn't either of those things?
-
node -e 'console.time("ReDoS"); /^(?:a?){30}a{30}$/.test(new Array(31).join("a")); console.timeEnd("ReDoS");'
For PowerShell users:
node -e 'console.time(''ReDoS''); /^(?:a?){30}a{30}$/.test(new Array(31).join(''a'')); console.timeEnd(''ReDoS'');'
Or for those without NodeJS: https://jsfiddle.net/fyswjnmb/6/
Machine Owner CPU Time Generic workstation name @Placeholder i7-8086k 38196.000ms WIN10-PC @loopback0 i7-6700K 81032.404ms Bobbo @Tsaukpaetra i5-8600K 84905.200ms TurkVolt @Tsaukpaetra i7-4790 96990.800ms Desktop @boomzilla i7-4770 99734.400ms urist @ben_lubar Ryzen 5 1600 100810.355ms MACBOOK-PRO @loopback0 i7-6700HQ 101220.150ms GODZILLA @ben_lubar i7-4770k 102283.544ms x58-mint @Atazhaia i7-990X 110622.434ms CHMMR @Parody i7-2600k 115167.000ms x58-w10 @Atazhaia i7-990X 116100.792ms School MacBook Air @Benjamin-Hall i7-5650U 116942.100ms ALEX-PC @AlexMedia i7-4790K 130867.300ms what @shadowmod Xeon D-1520 132823.957ms DESKTOP-V87P68A @barisu i5-750 135163.309ms a-X550LD :@aliceif: @aliceif i5-4200U 139399.600ms australium @ben_lubar Core2 Duo E7500 144597.496ms Very Quick Brick :@aliceif: @aliceif Snapdragon 845 151009.300ms Odin @calzonesteve@mastodon.b4yp.co.uk AMD FX-4130 154688.752ms LAPTOP @izzion i7-6600U 155479.300ms Hawkbit @Atazhaia i7-2677M 170733.359ms Edgar @ben_lubar Celeron N3160 253908.831ms CURSORMOB @Cursorkeys Krait 400 344974.100ms azahome @Atazhaia AMD A4-5000 384160.857ms Macbook Air 2015 @topspin i7-5650U 547105.000ms sneakybits @Carnage i7-7500U 568598.000ms Anyone wanna measure their CPU's e-peen?
-
@ben_lubar Sure then...
x58-mint | i7-990X | 110622.434ms
-
You should sort the table by time
-
@barisu said in JavaScript ReDoS:
You should sort the table by time
ok, time to do an insertion sort by hand
-
@barisu
Perhaps he could use a regular expression to display it
-
@izzion said in JavaScript ReDoS:
@barisu
Perhaps he could use a regular expression to display itI'll get back to you in a few hundred seconds.
-
Hmm I'll have to measure some e-peen on my 8086 when I get home
-
@sloosecannon said in JavaScript ReDoS:
Hmm I'll have to measure some e-peen on my 8086 when I get home
Can it run JavaScript?
-
@ben_lubar said in JavaScript ReDoS:
Can it run JavaScript?
For what else does it have
JS
instruction then?
-
@ben_lubar The fiddle doesn't work. It burns CPU but forgets to spit out the time.
-
@ben_lubar said in JavaScript ReDoS:
...so why are people using language implementations where it isn't either of those things?
-
@Rhywden said in JavaScript ReDoS:
@ben_lubar The fiddle doesn't work. It burns CPU but forgets to spit out the time.
Whoops, looks like I don't remember DOM as well as I thought I did.
-
@Rhywden said in JavaScript ReDoS:
@ben_lubar The fiddle doesn't work. It burns CPU but forgets to spit out the time.
-
@ben_lubar said in JavaScript ReDoS:
node -e 'console.time("ReDoS"); /^(?:a?){30}a{30}$/.test(new Array(31).join("a")); console.timeEnd("ReDoS");'
MACBOOK-PRO
i7-6700HQ @ 2.60GHz
ReDoS: 101220.150ms WIN10-PC
i7-6700K @ 4.00GHz
ReDoS: 81032.404ms@ben_lubar said in JavaScript ReDoS:
i7-6700HQ @ 2.60GHz
Time: 109223.300ms
i7-6700K @ 4.00GHz
Time: 80727.300ms
-
@ben_lubar For whatever it's worth:
Computer name: CHMMR
Operating system: Windows 10 64-bit
CPU model: i7-2600k
Time: 115167.000ms
-
MacBook Air (mid-2011) Hawkbit | i7-2677M | 170733.359
-
@Rhywden
I think it's just blocking data reporting due to GDPR... even the original link's version 4 works fine on my machine...W10, LAPTOP, Intel i7-6600U
-
This benchmarking nonsense makes me want to spin up a VM with a single core and max CPU resources at 1%.
-
@mott555 said in JavaScript ReDoS:
This benchmarking nonsense makes me want to spin up a VM with a single core and max CPU resources at 1%.
Limiting it to a single core won't matter for this single-core benchmark.
Also, here's the benchmark run in a JavaScript interpreter written in Go transpiled to JavaScript: https://play.jsgo.io/4ce013ba901f5ee9f71884bc051982f90a1af2aa
Yes, I added two layers of emulation and significantly improved performance.
-
@ben_lubar said in JavaScript ReDoS:
Yes, I added two layers of emulation and significantly improved performance.
-
Yes, I beat @ben_lubar with my awesome score! (Higher is better, right?)
(Ubuntu Server 18.04) azahome | AMD A4-5000 | 384160.857ms
-
Desktop Ubuntu 14.04 64-bit
CPU model: i7-4770 CPU @ 3.40GHz
Time: 99734.400ms
-
(AryaMod v6.5) CURSORMOB
CPU: Krait 400 @ 2.3GHzEdit: A twofer
Windows Server 2008 R2 (DOMAINSRV02)
Intel(R) Xeon(R) CPU E5630
257.676810000 SecondsInteresting, only one core showed activity and that only went to about 7%
-
-
@ben_lubar said in JavaScript ReDoS:
School Macbook Air | 2.2 GHz mobile core i7 | 116942.100ms
No, it doesn't tell me the actual part number. Sigh.
-
It runs slightly slower on Windows.
x58-w10 | i7-990X | 116100.792ms
-
@Benjamin-Hall said in JavaScript ReDoS:
No, it doesn't tell me the actual part number. Sigh.
sysctl -n machdep.cpu.brand_string
-
@Benjamin-Hall said in JavaScript ReDoS:
Macbook Air | 2.2 GHz mobile core i7
Based off that combination the only fitting model is the i7-5650U which is in the 2015 and 2017 MBA models.
-
@loopback0 said in JavaScript ReDoS:
@Benjamin-Hall said in JavaScript ReDoS:
No, it doesn't tell me the actual part number. Sigh.
sysctl -n machdep.cpu.brand_string
-
Pretty sure I should cross-post this to the UI bites thread:
So I got: iPhone 6S, 1.85GHz A8, 0.1 ms.
Do I win?If I run this on a computer, is the time for node.js vs jsfiddle in Firefox going to be significantly different?
-
@topspin said in JavaScript ReDoS:
jsfiddle in Firefox
I gave up.
"a script is slowing..." kill/continue
popped up every couple seconds.
-
@topspin said in JavaScript ReDoS:
If I run this on a computer, is the time for node.js vs jsfiddle in Firefox going to be significantly different?
Shouldn't be too different assuming Firefox uses a similar implementation of regex to V8.
-
Alright,
MacBook Air 2015, 2.2GHz i7, Firefox 61.0.2
Output:
Number of seconds:
547.105000000X11 forwarding over XQuartz is too slow to get firefox running on a workstation, at least to the point I can't type anything into the address bar.
-
@ben_lubar said in JavaScript ReDoS:
Anyone wanna measure their CPU's e-peen?
Shir.
@ben_lubar said in JavaScript ReDoS:
For PowerShell users:
node -e 'console.time(''ReDoS''); /^(?:a?){30}a{30}$/.test(new Array(31).join(''a'')); console.timeEnd(''ReDoS'');'
Your "For PowerShell users" is WRONG!
@ben_lubar said in JavaScript ReDoS:
Or for those without NodeJS: https://jsfiddle.net/fyswjnmb/6/
Almost 97 seconds, Chrome Version 68.0.3440.106 (Official Build) (64-bit),
i7-4790 @ 306 GHz. Oh, and the PC name is my real name. So.. we'll go with... TurkVolt. Yeah, that's my new pseudonym.
-
@Benjamin-Hall said in JavaScript ReDoS:
@ben_lubar said in JavaScript ReDoS:
School Macbook Air | 2.2 GHz mobile core i7 | 116942.100ms
No, it doesn't tell me the actual part number. Sigh.
@topspin said in JavaScript ReDoS:
MacBook Air 2015, 2.2GHz i7, Firefox 61.0.2
Output:
Number of seconds:
547.105000000Why the hell is my MacBook like 5 times slower than yours?
-
@Tsaukpaetra said in JavaScript ReDoS:
Almost 97 seconds,
Microsoft Edge 41.16299.611.0, Microsoft EdgeHTML 16.16299 on the same machine.
On Bobbo (the build machine):
i5-8600K @ 3.60 GHz, Edge the same as above. Chrome is not installed on it.Apparently JSFiddle does not work on IE11.
-
Where are the rich kids with their 8700k's?
-
I think the exact numbers are irrelevant, but my Edge is 30% faster than my Vivaldi.
-
@barisu said in JavaScript ReDoS:
Where are the rich kids with their 8700k's?
Computer name: Generic workstation name
Operating system: Windows 10 64-bit
CPU model: i7-8086k
Time: 46160.300msOn Edge
-
@ben_lubar said in JavaScript ReDoS:
language implementations where it isn't either of those things?
One common regular expression extension that does provide additional power is called backreferences. ... The power that backreferences add comes at great cost: in the worst case, the best known implementations require exponential search algorithms, like the one Perl uses. Perl (and the other languages) could
PCREs are not actually REs, and maintaining two execution paths is
Although not benchmarked here, Java uses a backtracking implementation too. In fact, the java.util.regex interface requires a backtracking implementation, because arbitrary Java code can be substituted into the matching path
-
Computer name: ALEX-PC
Operating system: Windows 10 64-bit, Chrome 69
CPU model: Intel Core i7 4790K (4GHz, at factory settings)
Time: 130867.300msedit:
Same test in Edge:
Time: 82400.100ms
-
@Placeholder And since this is an e-peen measuring contest...
Computer name:
Operating system: Windows 10 64-bit
CPU model: i7-8086k @ 5.2GHz
Time: 38196.000msIt's great to finally have a use for all that CPU power!
-
@topspin said in JavaScript ReDoS:
MacBook Air
OK, I lied, this is the most boring computer name.
@Tsaukpaetra said in JavaScript ReDoS:
Or for those without NodeJS: https://jsfiddle.net/fyswjnmb/6/
Can you people make sure you're clicking the correct link so I don't need to keep doing math?
-
It's interesting to see how much quicker Edge is at this than Chrome.
I just redid the same test in Edge (Edge 42, EdgeHTML 17), and that browser needed 82400.100ms while Chrome needed much more time.
-
DESKTOP-ELSLLMG
i7-6700K
90.9374 seconds (though with 2 "non responsive" prompts, not sure if the time it took me to click them was delaying the test)
56.866 secondsEdit: because @ben_lubar is too to convert seconds to milliseconds... interesting that I got different results on 2nd run... albeit I did have FFXIV open the first time and not the second time, but that's heavily GPU bound so I wouldn't expect an impact...
Time: 78399.600ms
Time: 48817.900ms
-
@ben_lubar said in JavaScript ReDoS:
Can you people make sure you're clicking the correct link so I don't need to keep doing math?
Or you could switch to seconds which is clearly more useful in this context.
-
Work Laptop
OS X El Capitan
Version 10.11.6
Mackbook Pro (Retina, 15-inch Mid 2015)
Processor: 2.5 Ghz Intel Core i7
Memory: 16GB 1600 Mhz DDR3Here's where it gets fun: Windows 7 Professional under Parallels Desktop 13 for Mac Pro Edition. Google Chrome 69.0.3497.100 (Official Build) (64-bit)
Time: 99286.7ms
Time under OS X proper (same Chrome version): 104937.7ms
-
Computer name: SLAVE-VIII
Operating system: Windows 10 64-bit
CPU model: Ryzen 7 2700X
Time: 67157ms
-
@ben_lubar said in JavaScript ReDoS:
Can you people make sure you're clicking the correct link so I don't need to keep doing math?
What correct link? I've used the same one five times and got two different results!