Limit the nesting depth of the Json parser

The parser is recursive and too deeply nested json would
cause it to exhaust the available stack space leading to
crashes.

We now abort parsing with a DeepNesting parse error if the
document is too deeply nested. The current nesting limit
is set to 1024, which should be more then enough for any
real JSON data set.

Change-Id: I4adea3fd727149f7342536d73cf4530361a0a3a1
Reviewed-by: Jamey Hicks <jamey.hicks@nokia.com>
Reviewed-by: Denis Dzyubenko <denis.dzyubenko@nokia.com>

4 files changed, 107 insertions, 4 deletions

diff --git a/src/corelib/json/qjsondocument.h b/src/corelib/json/qjsondocument.h
index c67899192c..bdb171c3cb 100644
--- a/src/corelib/json/qjsondocument.h
+++ b/src/corelib/json/qjsondocument.h
@@ -68,7 +68,8 @@ struct Q_CORE_EXPORT QJsonParseError
         IllegalEscapeSequence,
         IllegalUTF8String,
         UnterminatedString,
-        MissingObject
+        MissingObject,
+        DeepNesting
     };
 
     QString    errorString() const;
diff --git a/src/corelib/json/qjsonparser.cpp b/src/corelib/json/qjsonparser.cpp
index 6706f12b24..5372bc0a7a 100644
--- a/src/corelib/json/qjsonparser.cpp
+++ b/src/corelib/json/qjsonparser.cpp
@@ -58,6 +58,8 @@ static int indent = 0;
 #define DEBUG if (1) ; else qDebug()
 #endif
 
+static const int nestingLimit = 1024;
+
 QT_BEGIN_NAMESPACE
 
 // error strings for the JSON parser
@@ -73,6 +75,7 @@ QT_BEGIN_NAMESPACE
 #define JSONERR_STR_UTF8    QT_TRANSLATE_NOOP("QJsonParseError", "invalid UTF8 string")
 #define JSONERR_UTERM_STR   QT_TRANSLATE_NOOP("QJsonParseError", "unterminated string")
 #define JSONERR_MISS_OBJ    QT_TRANSLATE_NOOP("QJsonParseError", "object is missing after a comma")
+#define JSONERR_DEEP_NEST   QT_TRANSLATE_NOOP("QJsonParseError", "too deeply nested document")
 
 /*!
     \class QJsonParseError
@@ -84,6 +87,26 @@ QT_BEGIN_NAMESPACE
 */
 
 /*!
+    \enum QJsonParseError::ParseError
+
+    This enum describes the type of error that occurred during the parsing of a JSON document.
+
+    \value NoError                  No error occured
+    \value UnterminatedObject       An object is not correctly terminated with a closing curly bracket
+    \value MissingNameSeparator     A comma separating different items is missing
+    \value UnterminatedArray        The array is not correctly terminated with a closing square bracket
+    \value MissingValueSeparator    A colon separating keys from values inside objects is missing
+    \value IllegalValue             The value is illegal
+    \value TerminationByNumber      The input stream ended while parsing a number
+    \value IllegalNumber            The number is not well formed
+    \value IllegalEscapeSequence    An illegal escape sequence occurred in the input
+    \value IllegalUTF8String        An illegal UTF8 sequence occurred in the input
+    \value UnterminatedString       A string wasn't terminated with a quote
+    \value MissingObject            An object was expected but couldn't be found
+    \value DeepNesting              The JSON document is too deeply nested for the parser to parse it
+*/
+
+/*!
   Returns the human-readable message appropriate to the reported JSON parsing error.
  */
 QString QJsonParseError::errorString() const
@@ -126,6 +149,9 @@ QString QJsonParseError::errorString() const
     case MissingObject:
         sz = JSONERR_MISS_OBJ;
         break;
+    case DeepNesting:
+        sz = JSONERR_DEEP_NEST;
+        break;
     }
 #ifndef QT_BOOTSTRAPPED
     return QCoreApplication::translate("QJsonParseError", sz);
@@ -137,7 +163,7 @@ QString QJsonParseError::errorString() const
 using namespace QJsonPrivate;
 
 Parser::Parser(const char *json, int length)
-    : head(json), json(json), data(0), dataLength(0), current(0), lastError(QJsonParseError::NoError)
+    : head(json), json(json), data(0), dataLength(0), current(0), nestingLevel(0), lastError(QJsonParseError::NoError)
 {
     end = json + length;
 }
@@ -318,6 +344,11 @@ void Parser::ParsedObject::insert(uint offset) {
 
 bool Parser::parseObject()
 {
+    if (++nestingLevel > nestingLimit) {
+        lastError = QJsonParseError::DeepNesting;
+        return false;
+    }
+
     int objectOffset = reserveSpace(sizeof(QJsonPrivate::Object));
     BEGIN << "parseObject pos=" << objectOffset << current << json;
 
@@ -369,6 +400,8 @@ bool Parser::parseObject()
 
     DEBUG << "current=" << current;
     END;
+
+    --nestingLevel;
     return true;
 }
 
@@ -407,9 +440,15 @@ bool Parser::parseMember(int baseOffset)
 bool Parser::parseArray()
 {
     BEGIN << "parseArray";
+
+    if (++nestingLevel > nestingLimit) {
+        lastError = QJsonParseError::DeepNesting;
+        return false;
+    }
+
     int arrayOffset = reserveSpace(sizeof(QJsonPrivate::Array));
 
-    QVarLengthArray<QJsonPrivate::Value> values;
+    QVarLengthArray<QJsonPrivate::Value, 64> values;
 
     if (!eatSpace()) {
         lastError = QJsonParseError::UnterminatedArray;
@@ -453,6 +492,8 @@ bool Parser::parseArray()
 
     DEBUG << "current=" << current;
     END;
+
+    --nestingLevel;
     return true;
 }
 
diff --git a/src/corelib/json/qjsonparser_p.h b/src/corelib/json/qjsonparser_p.h
index 8085edb2e0..2025f43e38 100644
--- a/src/corelib/json/qjsonparser_p.h
+++ b/src/corelib/json/qjsonparser_p.h
@@ -75,7 +75,7 @@ public:
 
         Parser *parser;
         int objectPosition;
-        QVarLengthArray<uint> offsets;
+        QVarLengthArray<uint, 64> offsets;
 
         inline QJsonPrivate::Entry *entryAt(int i) const {
             return reinterpret_cast<QJsonPrivate::Entry *>(parser->data + objectPosition + offsets[i]);
@@ -101,6 +101,7 @@ private:
     char *data;
     int dataLength;
     int current;
+    int nestingLevel;
     QJsonParseError::ParseError lastError;
 
     inline int reserveSpace(int space) {
diff --git a/tests/auto/corelib/json/tst_qtjson.cpp b/tests/auto/corelib/json/tst_qtjson.cpp
index 84913f9289..00810889bb 100644
--- a/tests/auto/corelib/json/tst_qtjson.cpp
+++ b/tests/auto/corelib/json/tst_qtjson.cpp
@@ -127,6 +127,7 @@ private Q_SLOTS:
     void valueEquals();
 
     void bom();
+    void nesting();
 private:
     QString testDataDir;
 };
@@ -1924,5 +1925,64 @@ void TestQtJson::bom()
     QVERIFY(error.error == QJsonParseError::NoError);
 }
 
+void TestQtJson::nesting()
+{
+    // check that we abort parsing too deeply nested json documents.
+    // this is to make sure we don't crash because the parser exhausts the
+    // stack.
+
+    const char *array_data =
+            "[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[["
+            "[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[["
+            "[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[["
+            "[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[["
+            "[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[["
+            "[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[["
+            "[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[["
+            "[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[["
+            "]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]"
+            "]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]"
+            "]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]"
+            "]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]"
+            "]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]"
+            "]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]"
+            "]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]"
+            "]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]";
+
+    QByteArray json(array_data);
+    QJsonParseError error;
+    QJsonDocument doc = QJsonDocument::fromJson(json, &error);
+
+    QVERIFY(!doc.isNull());
+    QVERIFY(error.error == QJsonParseError::NoError);
+
+    json.prepend("[");
+    json.append("]");
+    doc = QJsonDocument::fromJson(json, &error);
+
+    QVERIFY(doc.isNull());
+    QVERIFY(error.error == QJsonParseError::DeepNesting);
+
+    json = QByteArray("true ");
+
+    for (int i = 0; i < 1024; ++i) {
+        json.prepend("{ \"Key\": ");
+        json.append(" }");
+    }
+
+    doc = QJsonDocument::fromJson(json, &error);
+
+    QVERIFY(!doc.isNull());
+    QVERIFY(error.error == QJsonParseError::NoError);
+
+    json.prepend("[");
+    json.append("]");
+    doc = QJsonDocument::fromJson(json, &error);
+
+    QVERIFY(doc.isNull());
+    QVERIFY(error.error == QJsonParseError::DeepNesting);
+
+}
+
 QTEST_MAIN(TestQtJson)
 #include "tst_qtjson.moc"