compileMakeRope does not emit necessary bounds checks
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 15 Apr 2014 23:33:11 +0000 (23:33 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 15 Apr 2014 23:33:11 +0000 (23:33 +0000)
https://bugs.webkit.org/show_bug.cgi?id=130684
<rdar://problem/16398388>

Reviewed by Oliver Hunt.

Add string length bounds checks in a bunch of places. We should never allow a string
to have a length greater than 2^31-1 because it's not clear that the language has
semantics for it and because there is code that assumes that this cannot happen.

Also add a bunch of tests to that effect to cover the various ways in which this was
previously allowed to happen.

* dfg/DFGOperations.cpp:
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::compileMakeRope):
* ftl/FTLLowerDFGToLLVM.cpp:
(JSC::FTL::LowerDFGToLLVM::compileMakeRope):
* runtime/JSString.cpp:
(JSC::JSRopeString::RopeBuilder::expand):
* runtime/JSString.h:
(JSC::JSString::create):
(JSC::JSRopeString::RopeBuilder::append):
(JSC::JSRopeString::RopeBuilder::release):
(JSC::JSRopeString::append):
* runtime/Operations.h:
(JSC::jsString):
(JSC::jsStringFromRegisterArray):
(JSC::jsStringFromArguments):
* runtime/StringPrototype.cpp:
(JSC::stringProtoFuncIndexOf):
(JSC::stringProtoFuncSlice):
(JSC::stringProtoFuncSubstring):
(JSC::stringProtoFuncToLowerCase):
* tests/stress/make-large-string-jit-strcat.js: Added.
(foo):
* tests/stress/make-large-string-jit.js: Added.
(foo):
* tests/stress/make-large-string-strcat.js: Added.
* tests/stress/make-large-string.js: Added.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@167336 268f45cc-cd09-0410-ab3c-d52691b4dbfc

12 files changed:
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGOperations.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp
Source/JavaScriptCore/runtime/JSString.cpp
Source/JavaScriptCore/runtime/JSString.h
Source/JavaScriptCore/runtime/Operations.h
Source/JavaScriptCore/runtime/StringPrototype.cpp
Source/JavaScriptCore/tests/stress/make-large-string-jit-strcat.js [new file with mode: 0644]
Source/JavaScriptCore/tests/stress/make-large-string-jit.js [new file with mode: 0644]
Source/JavaScriptCore/tests/stress/make-large-string-strcat.js [new file with mode: 0644]
Source/JavaScriptCore/tests/stress/make-large-string.js [new file with mode: 0644]

index 4b62264..f0d8988 100644 (file)
@@ -1,3 +1,46 @@
+2014-04-15  Filip Pizlo  <fpizlo@apple.com>
+
+        compileMakeRope does not emit necessary bounds checks
+        https://bugs.webkit.org/show_bug.cgi?id=130684
+        <rdar://problem/16398388>
+
+        Reviewed by Oliver Hunt.
+        
+        Add string length bounds checks in a bunch of places. We should never allow a string
+        to have a length greater than 2^31-1 because it's not clear that the language has
+        semantics for it and because there is code that assumes that this cannot happen.
+        
+        Also add a bunch of tests to that effect to cover the various ways in which this was
+        previously allowed to happen.
+
+        * dfg/DFGOperations.cpp:
+        * dfg/DFGSpeculativeJIT.cpp:
+        (JSC::DFG::SpeculativeJIT::compileMakeRope):
+        * ftl/FTLLowerDFGToLLVM.cpp:
+        (JSC::FTL::LowerDFGToLLVM::compileMakeRope):
+        * runtime/JSString.cpp:
+        (JSC::JSRopeString::RopeBuilder::expand):
+        * runtime/JSString.h:
+        (JSC::JSString::create):
+        (JSC::JSRopeString::RopeBuilder::append):
+        (JSC::JSRopeString::RopeBuilder::release):
+        (JSC::JSRopeString::append):
+        * runtime/Operations.h:
+        (JSC::jsString):
+        (JSC::jsStringFromRegisterArray):
+        (JSC::jsStringFromArguments):
+        * runtime/StringPrototype.cpp:
+        (JSC::stringProtoFuncIndexOf):
+        (JSC::stringProtoFuncSlice):
+        (JSC::stringProtoFuncSubstring):
+        (JSC::stringProtoFuncToLowerCase):
+        * tests/stress/make-large-string-jit-strcat.js: Added.
+        (foo):
+        * tests/stress/make-large-string-jit.js: Added.
+        (foo):
+        * tests/stress/make-large-string-strcat.js: Added.
+        * tests/stress/make-large-string.js: Added.
+
 2014-04-15  Julien Brianceau  <jbriance@cisco.com>
 
         Remove invalid sh4 specific code in JITInlines header.
index 332f1f2..0563317 100644 (file)
@@ -968,6 +968,11 @@ JSCell* JIT_OPERATION operationMakeRope2(ExecState* exec, JSString* left, JSStri
 {
     VM& vm = exec->vm();
     NativeCallFrameTracer tracer(&vm, exec);
+    
+    if (static_cast<int32_t>(left->length() + right->length()) < 0) {
+        throwOutOfMemoryError(exec);
+        return 0;
+    }
 
     return JSRopeString::create(vm, left, right);
 }
@@ -977,6 +982,14 @@ JSCell* JIT_OPERATION operationMakeRope3(ExecState* exec, JSString* a, JSString*
     VM& vm = exec->vm();
     NativeCallFrameTracer tracer(&vm, exec);
 
+    Checked<int32_t, RecordOverflow> length = a->length();
+    length += b->length();
+    length += c->length();
+    if (length.hasOverflowed()) {
+        throwOutOfMemoryError(exec);
+        return 0;
+    }
+
     return JSRopeString::create(vm, a, b, c);
 }
 
index f384d77..c92ff69 100644 (file)
@@ -2793,12 +2793,28 @@ void SpeculativeJIT::compileMakeRope(Node* node)
         m_jit.storePtr(TrustedImmPtr(0), JITCompiler::Address(resultGPR, JSRopeString::offsetOfFibers() + sizeof(WriteBarrier<JSString>) * i));
     m_jit.load32(JITCompiler::Address(opGPRs[0], JSString::offsetOfFlags()), scratchGPR);
     m_jit.load32(JITCompiler::Address(opGPRs[0], JSString::offsetOfLength()), allocatorGPR);
+    if (!ASSERT_DISABLED) {
+        JITCompiler::Jump ok = m_jit.branch32(
+            JITCompiler::GreaterThanOrEqual, allocatorGPR, TrustedImm32(0));
+        m_jit.breakpoint();
+        ok.link(&m_jit);
+    }
     for (unsigned i = 1; i < numOpGPRs; ++i) {
         m_jit.and32(JITCompiler::Address(opGPRs[i], JSString::offsetOfFlags()), scratchGPR);
-        m_jit.add32(JITCompiler::Address(opGPRs[i], JSString::offsetOfLength()), allocatorGPR);
+        speculationCheck(
+            Uncountable, JSValueSource(), nullptr,
+            m_jit.branchAdd32(
+                JITCompiler::Overflow,
+                JITCompiler::Address(opGPRs[i], JSString::offsetOfLength()), allocatorGPR));
     }
     m_jit.and32(JITCompiler::TrustedImm32(JSString::Is8Bit), scratchGPR);
     m_jit.store32(scratchGPR, JITCompiler::Address(resultGPR, JSString::offsetOfFlags()));
+    if (!ASSERT_DISABLED) {
+        JITCompiler::Jump ok = m_jit.branch32(
+            JITCompiler::GreaterThanOrEqual, allocatorGPR, TrustedImm32(0));
+        m_jit.breakpoint();
+        ok.link(&m_jit);
+    }
     m_jit.store32(allocatorGPR, JITCompiler::Address(resultGPR, JSString::offsetOfLength()));
     
     switch (numOpGPRs) {
index 84bc0ea..3631ae5 100644 (file)
@@ -2943,7 +2943,10 @@ private:
         LValue length = m_out.load32(kids[0], m_heaps.JSString_length);
         for (unsigned i = 1; i < numKids; ++i) {
             flags = m_out.bitAnd(flags, m_out.load32(kids[i], m_heaps.JSString_flags));
-            length = m_out.add(length, m_out.load32(kids[i], m_heaps.JSString_length));
+            LValue lengthAndOverflow = m_out.addWithOverflow32(
+                length, m_out.load32(kids[i], m_heaps.JSString_length));
+            speculate(Uncountable, noValue(), 0, m_out.extractValue(lengthAndOverflow, 1));
+            length = m_out.extractValue(lengthAndOverflow, 0);
         }
         m_out.store32(
             m_out.bitAnd(m_out.constInt32(JSString::Is8Bit), flags),
index 16a546e..00f05f5 100644 (file)
@@ -38,6 +38,7 @@ void JSRopeString::RopeBuilder::expand()
 {
     ASSERT(m_index == JSRopeString::s_maxInternalRopeLength);
     JSString* jsString = m_jsString;
+    RELEASE_ASSERT(jsString);
     m_jsString = jsStringBuilder(&m_vm);
     m_index = 0;
     append(jsString);
index bf13758..da1be1c 100644 (file)
@@ -1,7 +1,7 @@
 /*
  *  Copyright (C) 1999-2001 Harri Porten (porten@kde.org)
  *  Copyright (C) 2001 Peter Kelly (pmk@post.com)
- *  Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
+ *  Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2014 Apple Inc. All rights reserved.
  *
  *  This library is free software; you can redistribute it and/or
  *  modify it under the terms of the GNU Library General Public
@@ -123,7 +123,8 @@ namespace JSC {
         static JSString* create(VM& vm, PassRefPtr<StringImpl> value)
         {
             ASSERT(value);
-            size_t length = value->length();
+            int32_t length = value->length();
+            RELEASE_ASSERT(length >= 0);
             size_t cost = value->cost();
             JSString* newString = new (NotNull, allocateCell<JSString>(vm.heap)) JSString(vm, value);
             newString->finishCreation(vm, length, cost);
@@ -228,15 +229,21 @@ namespace JSC {
             {
             }
 
-            void append(JSString* jsString)
+            bool append(JSString* jsString)
             {
                 if (m_index == JSRopeString::s_maxInternalRopeLength)
                     expand();
+                if (static_cast<int32_t>(m_jsString->length() + jsString->length()) < 0) {
+                    m_jsString = 0;
+                    return false;
+                }
                 m_jsString->append(m_vm, m_index++, jsString);
+                return true;
             }
 
             JSRopeString* release()
             {
+                RELEASE_ASSERT(m_jsString);
                 JSRopeString* tmp = m_jsString;
                 m_jsString = 0;
                 return tmp;
@@ -286,6 +293,7 @@ namespace JSC {
         {
             m_fibers[index].set(vm, this, jsString);
             m_length += jsString->m_length;
+            RELEASE_ASSERT(static_cast<int32_t>(m_length) >= 0);
             setIs8Bit(is8Bit() && jsString->is8Bit());
         }
 
index a72e9bc..21527f6 100644 (file)
@@ -38,13 +38,13 @@ ALWAYS_INLINE JSValue jsString(ExecState* exec, JSString* s1, JSString* s2)
 {
     VM& vm = exec->vm();
 
-    unsigned length1 = s1->length();
+    int32_t length1 = s1->length();
     if (!length1)
         return s2;
-    unsigned length2 = s2->length();
+    int32_t length2 = s2->length();
     if (!length2)
         return s1;
-    if ((length1 + length2) < length1)
+    if ((length1 + length2) < 0)
         return throwOutOfMemoryError(exec);
 
     return JSRopeString::create(vm, s1, s2);
@@ -54,9 +54,13 @@ ALWAYS_INLINE JSValue jsString(ExecState* exec, const String& u1, const String&
 {
     VM* vm = &exec->vm();
 
-    unsigned length1 = u1.length();
-    unsigned length2 = u2.length();
-    unsigned length3 = u3.length();
+    int32_t length1 = u1.length();
+    int32_t length2 = u2.length();
+    int32_t length3 = u3.length();
+    
+    if (length1 < 0 || length2 < 0 || length3 < 0)
+        return throwOutOfMemoryError(exec);
+    
     if (!length1)
         return jsString(exec, jsString(vm, u2), jsString(vm, u3));
     if (!length2)
@@ -64,9 +68,9 @@ ALWAYS_INLINE JSValue jsString(ExecState* exec, const String& u1, const String&
     if (!length3)
         return jsString(exec, jsString(vm, u1), jsString(vm, u2));
 
-    if ((length1 + length2) < length1)
+    if ((length1 + length2) < 0)
         return throwOutOfMemoryError(exec);
-    if ((length1 + length2 + length3) < length3)
+    if ((length1 + length2 + length3) < 0)
         return throwOutOfMemoryError(exec);
 
     return JSRopeString::create(exec->vm(), jsString(vm, u1), jsString(vm, u2), jsString(vm, u3));
@@ -77,15 +81,10 @@ ALWAYS_INLINE JSValue jsStringFromRegisterArray(ExecState* exec, Register* strin
     VM* vm = &exec->vm();
     JSRopeString::RopeBuilder ropeBuilder(*vm);
 
-    unsigned oldLength = 0;
-
     for (unsigned i = 0; i < count; ++i) {
         JSValue v = strings[-static_cast<int>(i)].jsValue();
-        ropeBuilder.append(v.toString(exec));
-
-        if (ropeBuilder.length() < oldLength) // True for overflow
+        if (!ropeBuilder.append(v.toString(exec)))
             return throwOutOfMemoryError(exec);
-        oldLength = ropeBuilder.length();
     }
 
     return ropeBuilder.release();
@@ -97,15 +96,10 @@ ALWAYS_INLINE JSValue jsStringFromArguments(ExecState* exec, JSValue thisValue)
     JSRopeString::RopeBuilder ropeBuilder(*vm);
     ropeBuilder.append(thisValue.toString(exec));
 
-    unsigned oldLength = 0;
-
     for (unsigned i = 0; i < exec->argumentCount(); ++i) {
         JSValue v = exec->argument(i);
-        ropeBuilder.append(v.toString(exec));
-
-        if (ropeBuilder.length() < oldLength) // True for overflow
+        if (!ropeBuilder.append(v.toString(exec)))
             return throwOutOfMemoryError(exec);
-        oldLength = ropeBuilder.length();
     }
 
     return ropeBuilder.release();
index ee28ea1..a3d55f9 100644 (file)
@@ -762,6 +762,7 @@ EncodedJSValue JSC_HOST_CALL stringProtoFuncIndexOf(ExecState* exec)
     unsigned pos = 0;
     if (!a1.isUndefined()) {
         int len = thisJSString->length();
+        RELEASE_ASSERT(len >= 0);
         if (a1.isUInt32())
             pos = std::min<uint32_t>(a1.asUInt32(), len);
         else {
@@ -916,6 +917,7 @@ EncodedJSValue JSC_HOST_CALL stringProtoFuncSlice(ExecState* exec)
         return throwVMTypeError(exec);
     String s = thisValue.toString(exec)->value(exec);
     int len = s.length();
+    RELEASE_ASSERT(len >= 0);
 
     JSValue a0 = exec->argument(0);
     JSValue a1 = exec->argument(1);
@@ -1227,6 +1229,7 @@ EncodedJSValue JSC_HOST_CALL stringProtoFuncSubstring(ExecState* exec)
     JSValue a0 = exec->argument(0);
     JSValue a1 = exec->argument(1);
     int len = jsString->length();
+    RELEASE_ASSERT(len >= 0);
 
     double start = a0.toNumber(exec);
     double end;
@@ -1264,6 +1267,7 @@ EncodedJSValue JSC_HOST_CALL stringProtoFuncToLowerCase(ExecState* exec)
     int sSize = s.length();
     if (!sSize)
         return JSValue::encode(sVal);
+    RELEASE_ASSERT(sSize >= 0);
 
     StringImpl* ourImpl = s.impl();
     RefPtr<StringImpl> lower = ourImpl->lower();
diff --git a/Source/JavaScriptCore/tests/stress/make-large-string-jit-strcat.js b/Source/JavaScriptCore/tests/stress/make-large-string-jit-strcat.js
new file mode 100644 (file)
index 0000000..a6aeb1d
--- /dev/null
@@ -0,0 +1,24 @@
+// Like make-large-string-jit.js, but tests MakeRope with three arguments and op_strcat
+// in the DFG and FTL JITs.
+
+var s = "s";
+
+function foo(a, b) {
+    return "t" + a + b;
+}
+
+noInline(foo);
+
+for (var i = 0; i < 100000; ++i)
+    foo("a", "b");
+
+try {
+    for (var i = 0; i < 31; ++i)
+        s = foo(s, s);
+    print("Should not have gotten here.");
+    print("String length: " + s.length);
+    throw "Should not have gotten here.";
+} catch (e) {
+    if (e.message != "Out of memory")
+        throw "Wrong error: " + e;
+}
diff --git a/Source/JavaScriptCore/tests/stress/make-large-string-jit.js b/Source/JavaScriptCore/tests/stress/make-large-string-jit.js
new file mode 100644 (file)
index 0000000..8ee8847
--- /dev/null
@@ -0,0 +1,23 @@
+// Like make-large-string.js, but tests MakeRope with two arguments in the DFG and FTL JITs.
+
+var s = "s";
+
+function foo(a, b) {
+    return a + b;
+}
+
+noInline(foo);
+
+for (var i = 0; i < 100000; ++i)
+    foo("a", "b");
+
+try {
+    for (var i = 0; i < 31; ++i)
+        s = foo(s, s);
+    print("Should not have gotten here.");
+    print("String length: " + s.length);
+    throw "Should not have gotten here.";
+} catch (e) {
+    if (e.message != "Out of memory")
+        throw "Wrong error: " + e;
+}
diff --git a/Source/JavaScriptCore/tests/stress/make-large-string-strcat.js b/Source/JavaScriptCore/tests/stress/make-large-string-strcat.js
new file mode 100644 (file)
index 0000000..f101228
--- /dev/null
@@ -0,0 +1,12 @@
+var s = "s";
+
+try {
+    for (var i = 0; i < 31; ++i)
+        s = "t" + s + s;
+    print("Should not have gotten here.");
+    print("String length: " + s.length);
+    throw "Should not have gotten here.";
+} catch (e) {
+    if (e.message != "Out of memory")
+        throw "Wrong error: " + e;
+}
diff --git a/Source/JavaScriptCore/tests/stress/make-large-string.js b/Source/JavaScriptCore/tests/stress/make-large-string.js
new file mode 100644 (file)
index 0000000..c3ad773
--- /dev/null
@@ -0,0 +1,12 @@
+var s = "s";
+
+try {
+    for (var i = 0; i < 31; ++i)
+        s = s + s;
+    print("Should not have gotten here.");
+    print("String length: " + s.length);
+    throw "Should not have gotten here.";
+} catch (e) {
+    if (e.message != "Out of memory")
+        throw "Wrong error: " + e;
+}