Changeset 31388

Timestamp:

2008-03-27 23:41:17 (5 months ago)

Author:

mrowe@apple.com

Message:

2008-03-27 Darin Adler <darin@apple.com>

Reviewed by Mark Rowe.

<rdar://problem/5826236> Regular expressions with large nested repetition counts can have their
compiled length calculated incorrectly.

• pcre/pcre_compile.cpp: (multiplyWithOverflowCheck): (calculateCompiledPatternLength): Check for overflow when dealing with nested repetition counts and bail with an error rather than returning incorrect results.

2008-03-27 Mark Rowe <mrowe@apple.com>

Reviewed by Adam Roben.

Tests for <rdar://problem/5826236> Regular expressions with large nested repetition counts can have their
compiled length calculated incorrectly.

• fast/js/regexp-overflow-expected.txt:
• fast/js/resources/regexp-overflow.js:

Location:

trunk

Files:

• JavaScriptCore/ChangeLog (modified) (1 diff)
• JavaScriptCore/pcre/pcre_compile.cpp (modified) (4 diffs)
• LayoutTests/ChangeLog (modified) (1 diff)
• LayoutTests/fast/js/regexp-overflow-expected.txt (modified) (1 diff)
• LayoutTests/fast/js/resources/regexp-overflow.js (modified) (1 diff)

trunk/JavaScriptCore/ChangeLog

@@ +1 @@
+2008-03-27  Darin Adler  <darin@apple.com>
+
+        Reviewed by Mark Rowe.
+
+        <rdar://problem/5826236> Regular expressions with large nested repetition counts can have their
+        compiled length calculated incorrectly.
+
+        * pcre/pcre_compile.cpp:
+        (multiplyWithOverflowCheck):
+        (calculateCompiledPatternLength): Check for overflow when dealing with nested repetition counts
+        and bail with an error rather than returning incorrect results.
+
 2008-03-26  Mark Rowe  <mrowe@apple.com>
 

trunk/JavaScriptCore/pcre/pcre_compile.cpp

@@ -1986 +1986 @@
 }
 
+static inline int multiplyWithOverflowCheck(int a, int b)
+{
+    if (!a || !b)
+        return 0;
+    if (a > MAX_PATTERN_SIZE / b)
+        return -1;
+    return a * b;
+}
+
 static int calculateCompiledPatternLength(const UChar* pattern, int patternLength, JSRegExpIgnoreCaseOption ignoreCase,
     CompileData& cd, ErrorCode& errorcode)
@@ -1992 +2001 @@
      amount of store required to hold the compiled code. This does not have to be
      perfect as long as errors are overestimates. */
-    
+
+    if (patternLength > MAX_PATTERN_SIZE) {
+        errorcode = ERR16;
+        return -1;
+    }
+
     int length = 1 + LINK_SIZE;      /* For initial BRA plus length */
     int branch_extra = 0;
@@ -2414 +2428 @@
                  bracket set. */
                 
+                int repeatsLength;
                 if (minRepeats == 0) {
                     length++;
-                    if (maxRepeats > 0) length += (maxRepeats - 1) * (duplength + 3 + 2 * LINK_SIZE);
+                    if (maxRepeats > 0) {
+                        repeatsLength = multiplyWithOverflowCheck(maxRepeats - 1, duplength + 3 + 2 * LINK_SIZE);
+                        if (repeatsLength < 0) {
+                            errorcode = ERR16;
+                            return -1;
+                        }
+                        length += repeatsLength;
+                        if (length > MAX_PATTERN_SIZE) {
+                            errorcode = ERR16;
+                            return -1;
+                        }
+                    }
                 }
                 
@@ -2426 +2452 @@
                 
                 else {
-                    length += (minRepeats - 1) * duplength;
-                    if (maxRepeats > minRepeats)   /* Need this test as maxRepeats=-1 means no limit */
-                        length += (maxRepeats - minRepeats) * (duplength + 3 + 2 * LINK_SIZE)
-                        - (2 + 2 * LINK_SIZE);
+                    repeatsLength = multiplyWithOverflowCheck(minRepeats - 1, duplength);
+                    if (repeatsLength < 0) {
+                        errorcode = ERR16;
+                        return -1;
+                    }
+                    length += repeatsLength;
+                    if (maxRepeats > minRepeats) { /* Need this test as maxRepeats=-1 means no limit */
+                        repeatsLength = multiplyWithOverflowCheck(maxRepeats - minRepeats, duplength + 3 + 2 * LINK_SIZE);
+                        if (repeatsLength < 0) {
+                            errorcode = ERR16;
+                            return -1;
+                        }
+                        length += repeatsLength - (2 + 2 * LINK_SIZE);
+                    }
+                    if (length > MAX_PATTERN_SIZE) {
+                        errorcode = ERR16;
+                        return -1;
+                    }
                 }
                 

trunk/LayoutTests/ChangeLog

@@ +1 @@
+2008-03-27  Mark Rowe  <mrowe@apple.com>
+
+        Reviewed by Adam Roben.
+
+        Tests for <rdar://problem/5826236> Regular expressions with large nested repetition counts can have their
+        compiled length calculated incorrectly.
+
+        * fast/js/regexp-overflow-expected.txt:
+        * fast/js/resources/regexp-overflow.js:
+
 2008-03-27  Brady Eidson  <beidson@apple.com>
 

trunk/LayoutTests/fast/js/regexp-overflow-expected.txt

@@ -13 +13 @@
 PASS /{([\D-\ca]]â€şÂ£Âµ+?)}|[[\B-\u00d4]√π- ]]]{0,3}/i.exec("B√π- ]]").toString() is "B√π- ]],"
 PASS /|[x\B-\u00b5]/i.exec("").toString() is ""
+PASS new RegExp(s); threw exception SyntaxError: Invalid regular expression: regular expression too large.
+PASS /(([ab]){30}){3360}/ threw exception SyntaxError: Invalid regular expression: regular expression too large.
+PASS /(([ab]){30}){0,3360}/ threw exception SyntaxError: Invalid regular expression: regular expression too large.
+PASS /(([ab]){30}){10,3360}/ threw exception SyntaxError: Invalid regular expression: regular expression too large.
+PASS /(([ab]){0,30}){3360}/ threw exception SyntaxError: Invalid regular expression: regular expression too large.
+PASS /(([ab]){0,30}){0,3360}/ threw exception SyntaxError: Invalid regular expression: regular expression too large.
+PASS /(([ab]){0,30}){10,3360}/ threw exception SyntaxError: Invalid regular expression: regular expression too large.
+PASS /(([ab]){10,30}){3360}/ threw exception SyntaxError: Invalid regular expression: regular expression too large.
+PASS /(([ab]){10,30}){0,3360}/ threw exception SyntaxError: Invalid regular expression: regular expression too large.
+PASS /(([ab]){10,30}){10,3360}/ threw exception SyntaxError: Invalid regular expression: regular expression too large.
+PASS /(([ab]){12})(([ab]){65535}){1680}(([ab]){38}){722}([ab]){27}/ threw exception SyntaxError: Invalid regular expression: regular expression too large.
 
 PASS successfullyParsed is true

trunk/LayoutTests/fast/js/resources/regexp-overflow.js

@@ -21 +21 @@
 shouldBe('/|[x\\B-\\u00b5]/i.exec("").toString()', '""');
 
+var s = "a";
+for (var i = 0; i < 17; i++)
+    s += s;
+
+shouldThrow('new RegExp(s);');
+
+shouldThrow('/(([ab]){30}){3360}/');
+shouldThrow('/(([ab]){30}){0,3360}/');
+shouldThrow('/(([ab]){30}){10,3360}/');
+shouldThrow('/(([ab]){0,30}){3360}/');
+shouldThrow('/(([ab]){0,30}){0,3360}/');
+shouldThrow('/(([ab]){0,30}){10,3360}/');
+shouldThrow('/(([ab]){10,30}){3360}/');
+shouldThrow('/(([ab]){10,30}){0,3360}/');
+shouldThrow('/(([ab]){10,30}){10,3360}/');
+shouldThrow('/(([ab]){12})(([ab]){65535}){1680}(([ab]){38}){722}([ab]){27}/');
+
 debug('');