isUrl check causes infinite loop

[pyhrus]

Following code can be use to reproduce the infinite loop

var check = require('validator').check;

console.log('my pid ' + process.pid);

var str = 'http://www.google.com/url?testing=testing&testing=testing&testing=testing&testing=testing&testing=testing&testing=testing&testing=testing&testing=testing&testing=testing&testing=testing&testing=testing&testing=testing&';

console.log('str length : ' + str.length);

check(str).isUrl(str);

MDB js stack

::jsstack
80475d8 0xfe632a3e
8047638 v8::internal::NativeRegExpMacroAssembler::Execute+0x6a
8047678 v8::internal::NativeRegExpMacroAssembler::Match+0x7e
80476e8 v8::internal::RegExpImpl::IrregexpExecRaw+0x124
8047738 v8::internal::RegExpImpl::IrregexpExec+0x6e
8047788 v8::internal::RegExpImpl::Exec+0x80
80477e8 v8::internal::Runtime_RegExpExec+0x133
8047808 0x4050a336 internal (Code: 4050a2c1)
804782c 0xfe632335 RegExpExecNoTests (26c2f0b5)
8047854 0xfe6321b1 match (26c2e1c1)
804786c 0xfe627560 (as module.exports.isUrl) (297aa561)
8047888 0x4050db41
80478b0 0x4052461e
80478d4 0xfe625725 (as Validator.(anonymous function)) (58a1ab35)
80478ec 0x4050db41
804790c 0xfe612d17 (as ) (297760ad)
8047940 0x40524625
8047978 0x40555b3b (as Module._compile) (26c46b55)
8047998 0x40555c19 (as Module._extensions..js) (26c46b95)
80479bc 0x40554cff (as Module.load) (26c46b0d)
80479fc 0x405547f3 (as Module._load) (26c46ac5)
8047a1c 0x40555f53 (as Module.runMain) (26c46c01)
8047a40 0x4052957c (as startup.processNextTick.process._tickCallback) (26c438d9)
8047a5c 0x40521c39
8047a98 0x40512c2a
8047b18 _ZN2v88internalL6InvokeEbNS0_6HandleINS0_10JSFunctionEEENS1_INS0_6ObjectEEEiPS5_Pb+0x101
8047b58 v8::internal::Execution::Call+0xc9
8047bb8 v8::Function::Call+0xf0
8047c38 _ZN4nodeL4TickEv+0xae
8047c58 uv__run_idle+0x37
8047c98 uv__run+0x23
8047ca8 uv_run+0x17
8047d08 node::Start+0x1c7
8047d28 main+0x1b
8047d48 _start+0x83

[Radagaisus]

Also, I think this part is wrong str.length > 2083 and should be str.length < 2083. URLs can't (practically) be bigger than ~2000 characters

[chriso]

@shankar0306 it's a regular expression denial of service. Not sure what the best course of action is here beyond replacing the check with a parser that doesn't use regex.

@Radagaisus the isUrl() check fails if length > 2083. See #53 for the reasoning behind this.

[ralyodio]

I think limit of 2000 chars is reasonable: http://stackoverflow.com/questions/417142/what-is-the-maximum-length-of-a-url

[Radagaisus]

@chriso @chovy yep, I was misreading the code. The problem shankar mentioned is more serious though.

[corvi42]

It would probably be more efficient to put the length > 2083 check before the regex. This way, the regex is never used for really long strings. I'm pretty sure that checking the length of the string is a faster operation than that really long & hairy regex.

[chriso]

@corvi42 RegExp in V8 is fast enough that checks on urls of any length should be considered negligible. The DOS problem arrises from excessive backtracking.

[corvi42]

@chriso I understand that the infinite loop issue is not from the performance of the regex, and I also appreciate that V8 is a mighty powerful machine. It was just a passing observation. In general I think its good style to fail fast, and avoid more costly operations when the code is functionally equivalent. Its really a very minor point, and I'm sure won't really affect anybody's code adversely either way. Do as you wish.

[corpix]

I think that problem in the regexp used in the node-validator. If you delete "&" at the end of the url it will work fine.

Have you seen this https://gist.github.com/729294 ?
I have found it while searching for good javascript url validation regex and wrote little test(urls borrowed from this page http://mathiasbynens.be/demo/url-regex) for node.js https:/corpix/dperini_isurl_test

EDIT: I have also added regex that used in node-validator at the moment of 0e391de