50579 2010-12-06 12:18:28 -0800 Regular expression methods crashing browser (buffer overflow?) 2010-12-09 10:53:06 -0800 1 1 1 Unclassified WebKit JavaScriptCore 528+ (Nightly build) Mac (Intel) OS X 10.6 RESOLVED FIXED InRadar P1 Major --- 1 alexei msaboff abarth abecsi barraclough commit-queue eric ggaren msaboff pvarga webkit.review.bot oldest_to_newest 317778 0 alexei 2010-12-06 12:18:28 -0800 Calling test() on regular expressions over some character length crashes WebKit. Here is an example regex that crashes every time: /indextools\.js|static\.scribefire\.com\/ads\.js|(static\.getclicky\.com\/|clicky\.js)|statisfy\.net\/javascripts\/stats\.js|gmodules.com\/|rate\.thummit\.com\/js\/|twitter\.com\/(javascripts\/[0-9a-z]+\.js|statuses\/user_timeline\/)|analytics\.live\.com\/|(pub\.lookery\.com\/js\/|lookery\.com\/look\.js|\/j\/pub\/look\.js)|google-analytics\.com\/(urchin\.js|ga\.js|__utm\.gif)|\.mybloglog\.com\/|(\.quantserve\.com\/|\/quant\.js)|sitemeter\.com\/(js\/counter\.js|meter\.asp)|www\.lijit\.com\/informers\/wijits|(\.1[12]2\.2o7\.net\/|\/hbx\.js|\/s_code[0-9a-zA-Z_-]*(\.[0-9a-zA-Z_-]*)?\.js|\.omtrdc\.net\/|omniunih\.js|\/(omniture|mbox)(.*)?\.js|common\.onset\.freedom\.com\/fi\/analytics\/cms\/)|cetrk\.com\//i I am using WebKit r73340. 317783 1 alexei 2010-12-06 12:22:31 -0800 An example call that will crash WebKit: /indextools\.js|static\.scribefire\.com\/ads\.js|(static\.getclicky\.com\/|clicky\.js)|statisfy\.net\/javascripts\/stats\.js|gmodules.com\/|rate\.thummit\.com\/js\/|twitter\.com\/(javascripts\/[0-9a-z]+\.js|statuses\/user_timeline\/)|analytics\.live\.com\/|(pub\.lookery\.com\/js\/|lookery\.com\/look\.js|\/j\/pub\/look\.js)|google-analytics\.com\/(urchin\.js|ga\.js|__utm\.gif)|\.mybloglog\.com\/|(\.quantserve\.com\/|\/quant\.js)|sitemeter\.com\/(js\/counter\.js|meter\.asp)|www\.lijit\.com\/informers\/wijits|(\.1[12]2\.2o7\.net\/|\/hbx\.js|\/s_code[0-9a-zA-Z_-]*(\.[0-9a-zA-Z_-]*)?\.js|\.omtrdc\.net\/|omniunih\.js|\/(omniture|mbox)(.*)?\.js|common\.onset\.freedom\.com\/fi\/analytics\/cms\/)|cetrk\.com\//i.test('http://google.com'); 317945 2 ap 2010-12-06 17:01:57 -0800 Could you please attach a crash log <http://webkit.org/quality/crashlogs.html>? 318101 3 pvarga 2010-12-07 02:34:01 -0800 I have analyzed the mentioned regex pattern. It didn't cause a crash on jsc for me, but the matching seems to run into an infinite loop. The pattern isn't a fallback case and the YARR Interpreter works well with this pattern so it seems there is a bug in the YARR JIT. The problem exists since http://trac.webkit.org/changeset/73307 (https://bugs.webkit.org/show_bug.cgi?id=50295). The problem surely isn't the length of pattern. I have created a more simple test case to reproduce this regression: /(a(b|c)(.*))|xxx/.test('aaa'); I haven't checked the generated JIT code yet. 318181 4 pvarga 2010-12-07 07:47:16 -0800 I checked the YARR JIT. I don't have a complete solution but I summarize the partial results of my investigation: Here is a more simple test case which I'm using for debugging: /a(b)(a*)|aaa/.test('aaa') The problem is if the matching of term 'b' fails then it resets the result of subpattern matching and it starts the matching from the beginning, but the index of position (edx) is never increased. Thus the JIT does the same character check again and again in an infinite loop. Wrong backtrack code block is executed since the backtrack logic extension was introduced. Here is a simple asm example from the generated code: match_b: cmpw $0x62,-0x2(%eax,%edx,2) jne parentheses_tail ... expected_backtrack: add $0x1,%edx jmp available_input ... current_backtrack: mov %edx,%ebx sub $0x2,%ebx mov %ebx,(%edi) jmp match_b available_input: mov %edx,%ebx sub $0x2,%ebx mov %ebx,(%edi) add $0x0,%edx cmp %ecx,%edx jbe match_b ... parentheses_tail: movl $0xffffffff,0x8(%edi) jmp current_backtrack; It should jump to the "expected_backtrack" instead of "current_backtrack" label in the "parentheses_tail" code block. The state.linkAlternativeBacktracks(this, true) links to the "current_backtrack" at RegexJIT.cpp:1958. I guess the desired place of this link is at RegexJIT.cpp:1902 where the notEnoughInputForPreviousAlternative label is linked now. I hope this information is useful. 318398 5 ggaren 2010-12-07 12:34:51 -0800 <rdar://problem/8739597> 318466 6 msaboff 2010-12-07 15:51:55 -0800 Testing fix. 319086 7 75981 msaboff 2010-12-08 15:39:13 -0800 Created attachment 75981 Patch to protect from prior backtrack label don't get overwritten 319236 8 75981 commit-queue 2010-12-08 20:28:31 -0800 Comment on attachment 75981 Patch to protect from prior backtrack label don't get overwritten Rejecting patch 75981 from commit-queue. Failed to run "['./WebKitTools/Scripts/webkit-patch', '--status-host=queues.webkit.org', '--bot-id=eseidel-cq-sl', 'build', '--no-clean', '--no-update', '--build-style=both']" exit_code: 1 ERROR: Working directory has local commits, pass --force-clean to continue. Full output: http://queues.webkit.org/results/6951002 319504 9 msaboff 2010-12-09 09:20:01 -0800 Committed r73617: <http://trac.webkit.org/changeset/73617> 319515 10 msaboff 2010-12-09 09:40:58 -0800 Some problem with the checkin. The fix was first in <http://trac.webkit.org/changeset/73615> and then the change log was fixed in <http://trac.webkit.org/changeset/73617>. 319588 11 webkit.review.bot 2010-12-09 10:53:06 -0800 http://trac.webkit.org/changeset/73617 might have broken Leopard Intel Release (Tests) The following tests are not passing: inspector/styles-source-offsets.html 75981 2010-12-08 15:39:13 -0800 2010-12-08 20:28:31 -0800 Patch to protect from prior backtrack label don't get overwritten 50579-2.patch text/plain 3282 msaboff SW5kZXg6IEphdmFTY3JpcHRDb3JlL0NoYW5nZUxvZwo9PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBKYXZhU2NyaXB0 Q29yZS9DaGFuZ2VMb2cJKHJldmlzaW9uIDczNTU3KQorKysgSmF2YVNjcmlwdENvcmUvQ2hhbmdl TG9nCSh3b3JraW5nIGNvcHkpCkBAIC0xLDMgKzEsMTUgQEAKKzIwMTAtMTItMDggIE1pY2hhZWwg U2Fib2ZmICA8bXNhYm9mZkBhcHBsZS5jb20+CisKKyAgICAgICAgUmV2aWV3ZWQgYnkgTk9CT0RZ IChPT1BTISkuCisKKyAgICAgICAgQ2hhbmdlZCBzZXR0aW5nIG9mIGJhY2t0cmFjayBsYWJlbHMg dG8gbm90IG92ZXJ3cml0ZSBhIHByaW9yCisgICAgICAgIGxhYmVsLiAgV2hlcmUgbG9zaW5nIHBy aW9yIGxhYmUgd2hpY2ggdGhlbiByZXZlcnRlZCBiYWNrIHRvIAorICAgICAgICBuZXh0IGNoYXJh Y3RlciBsYWJlbC4KKyAgICAgICAgaHR0cHM6Ly9idWdzLndlYmtpdC5vcmcvc2hvd19idWcuY2dp P2lkPTUwNTc5CisKKyAgICAgICAgKiB5YXJyL1JlZ2V4SklULmNwcDoKKyAgICAgICAgKEpTQzo6 WWFycjo6UmVnZXhHZW5lcmF0b3I6OkJhY2t0cmFja0Rlc3RpbmF0aW9uOjpzZXRCYWNrdHJhY2tU b0xhYmVsKToKKwogMjAxMC0xMi0wOCAgT2xpdmVyIEh1bnQgIDxvbGl2ZXJAYXBwbGUuY29tPgog CiAgICAgICAgIFJldmlld2VkIGJ5IEdhdmluIEJhcnJhY2xvdWdoLgpJbmRleDogSmF2YVNjcmlw dENvcmUveWFyci9SZWdleEpJVC5jcHAKPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0gSmF2YVNjcmlwdENvcmUveWFy ci9SZWdleEpJVC5jcHAJKHJldmlzaW9uIDczNTQ5KQorKysgSmF2YVNjcmlwdENvcmUveWFyci9S ZWdleEpJVC5jcHAJKHdvcmtpbmcgY29weSkKQEAgLTU2MSw3ICs1NjEsOCBAQCBjbGFzcyBSZWdl eEdlbmVyYXRvciA6IHByaXZhdGUgTWFjcm9Bc3NlCiAgICAgICAgIAogICAgICAgICB2b2lkIHNl dEJhY2t0cmFja1RvTGFiZWwoTGFiZWwqIGJhY2t0cmFja1RvTGFiZWwpCiAgICAgICAgIHsKLSAg ICAgICAgICAgIG1fYmFja3RyYWNrVG9MYWJlbCA9IGJhY2t0cmFja1RvTGFiZWw7CisgICAgICAg ICAgICBpZiAoIW1fYmFja3RyYWNrVG9MYWJlbCkKKyAgICAgICAgICAgICAgICBtX2JhY2t0cmFj a1RvTGFiZWwgPSBiYWNrdHJhY2tUb0xhYmVsOwogICAgICAgICB9CiAgICAgICAgIAogICAgICAg ICB2b2lkIHNldEJhY2t0cmFja0p1bXBMaXN0KEp1bXBMaXN0KiBqdW1wTGlzdCkKSW5kZXg6IExh eW91dFRlc3RzL0NoYW5nZUxvZwo9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBMYXlvdXRUZXN0cy9DaGFuZ2VMb2cJ KHJldmlzaW9uIDczNTU3KQorKysgTGF5b3V0VGVzdHMvQ2hhbmdlTG9nCSh3b3JraW5nIGNvcHkp CkBAIC0xLDMgKzEsMTMgQEAKKzIwMTAtMTItMDggIE1pY2hhZWwgU2Fib2ZmICA8bXNhYm9mZkBh cHBsZS5jb20+CisKKyAgICAgICAgUmV2aWV3ZWQgYnkgTk9CT0RZIChPT1BTISkuCisKKyAgICAg ICAgQWRkZWQgdGVzdCB0byB2ZXJpZnkgcHJvcGVyIG9wZXJhdGlvbiBvZiBiYWNrdHJhY2sgbGFi ZWxzLgorICAgICAgICBodHRwczovL2J1Z3Mud2Via2l0Lm9yZy9zaG93X2J1Zy5jZ2k/aWQ9NTA1 NzkKKworICAgICAgICAqIGZhc3QvcmVnZXgvcGFyZW50aGVzZXMtZXhwZWN0ZWQudHh0OgorICAg ICAgICAqIGZhc3QvcmVnZXgvc2NyaXB0LXRlc3RzL3BhcmVudGhlc2VzLmpzOgorCiAyMDEwLTEy LTA4ICBNYXJ0aW4gUm9iaW5zb24gIDxtcm9iaW5zb25AaWdhbGlhLmNvbT4KIAogICAgICAgICBS ZXBsYWNlIHNvbWUgR1RLKyB0ZXN0IHJlc3VsdHMgYWZ0ZXIgcjczNTQ4LgpJbmRleDogTGF5b3V0 VGVzdHMvZmFzdC9yZWdleC9wYXJlbnRoZXNlcy1leHBlY3RlZC50eHQKPT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0g TGF5b3V0VGVzdHMvZmFzdC9yZWdleC9wYXJlbnRoZXNlcy1leHBlY3RlZC50eHQJKHJldmlzaW9u IDczNTQ5KQorKysgTGF5b3V0VGVzdHMvZmFzdC9yZWdleC9wYXJlbnRoZXNlcy1leHBlY3RlZC50 eHQJKHdvcmtpbmcgY29weSkKQEAgLTMwLDYgKzMwLDcgQEAgUEFTUyByZWdleHAyMy5leGVjKCc8 aHRtbCB4bWxucz0iaHR0cDovLwogUEFTUyByZWdleHAyNC5leGVjKCcxMjMnKSBpcyBudWxsCiBQ QVNTIHJlZ2V4cDI1LmV4ZWMoJ3RoaXMgaXMgYSB0ZXN0JykgaXMgWyd0aGlzJywndGhpcycsdW5k ZWZpbmVkXQogUEFTUyByZWdleHAyNS5leGVjKCchdGhpcyBpcyBhIHRlc3QnKSBpcyBudWxsCitQ QVNTIHJlZ2V4cDI2LmV4ZWMoJ2FhYScpIGlzIFsnYWFhJyx1bmRlZmluZWQsdW5kZWZpbmVkXQog UEFTUyAnSGkgQm9iJy5tYXRjaCgvKFJvYil8KEJvYil8KFJvYmVydCl8KEJvYmJ5KS8pIGlzIFsn Qm9iJyx1bmRlZmluZWQsJ0JvYicsdW5kZWZpbmVkLHVuZGVmaW5lZF0KIFBBU1Mgc3VjY2Vzc2Z1 bGx5UGFyc2VkIGlzIHRydWUKIApJbmRleDogTGF5b3V0VGVzdHMvZmFzdC9yZWdleC9zY3JpcHQt dGVzdHMvcGFyZW50aGVzZXMuanMKPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQotLS0gTGF5b3V0VGVzdHMvZmFzdC9yZWdl eC9zY3JpcHQtdGVzdHMvcGFyZW50aGVzZXMuanMJKHJldmlzaW9uIDczNTQ5KQorKysgTGF5b3V0 VGVzdHMvZmFzdC9yZWdleC9zY3JpcHQtdGVzdHMvcGFyZW50aGVzZXMuanMJKHdvcmtpbmcgY29w eSkKQEAgLTc3LDYgKzc3LDkgQEAgdmFyIHJlZ2V4cDI1ID0gL15ccyooXCp8W1x3XC1dKykoXGJ8 JCk/Lwogc2hvdWxkQmUoInJlZ2V4cDI1LmV4ZWMoJ3RoaXMgaXMgYSB0ZXN0JykiLCAiWyd0aGlz JywndGhpcycsdW5kZWZpbmVkXSIpOwogc2hvdWxkQmVOdWxsKCJyZWdleHAyNS5leGVjKCchdGhp cyBpcyBhIHRlc3QnKSIpOwogCit2YXIgcmVnZXhwMjYgPSAvYShiKShhKil8YWFhLzsKK3Nob3Vs ZEJlKCJyZWdleHAyNi5leGVjKCdhYWEnKSIsICJbJ2FhYScsdW5kZWZpbmVkLHVuZGVmaW5lZF0i KTsKKwogc2hvdWxkQmUoIidIaSBCb2InLm1hdGNoKC8oUm9iKXwoQm9iKXwoUm9iZXJ0KXwoQm9i YnkpLykiLCAiWydCb2InLHVuZGVmaW5lZCwnQm9iJyx1bmRlZmluZWQsdW5kZWZpbmVkXSIpOwog CiB2YXIgc3VjY2Vzc2Z1bGx5UGFyc2VkID0gdHJ1ZTsK