[Qemu-devel] [PATCH v2 0/4] json-streamer: Fix up code to limit nesting and size

[Qemu-devel] [PATCH v2 0/4] json-streamer: Fix up code to limit nesting and size

[Markus Armbruster]

Ugh, I almost dropped this on the floor.  I think it should go into
2.5, and I plan to take it through my tree.  If you disagree, please
speak up.

We limit nesting depth and input size to defend against input
triggering excessive heap or stack memory use (commit 29c75dd
json-streamer: limit the maximum recursion depth and maximum token
count).  This limiting is flawed in multiple ways.  Fix it up some.

Not yet fixed: this JSON parser is an absurd memory hog; see last
patch.

v2:
* Trivially rebased, R-bys retained
* PATCH 3: Fix a nearby comment typo [Eric]
* PATCH 4: Simplify make_nest() slightly
* PATCH 5: Commit message tweaked

Markus Armbruster (4):
  json-streamer: Apply nesting limit more sanely
  json-streamer: Don't crash when input exceeds nesting limit
  check-qjson: Add test for JSON nesting depth limit
  json-streamer: Limit number of tokens in addition to total size

 qobject/json-streamer.c | 10 ++++++----
 tests/check-qjson.c     | 25 +++++++++++++++++++++++++
 2 files changed, 31 insertions(+), 4 deletions(-)

-- 
2.4.3

[Qemu-devel] [PATCH v2 1/4] json-streamer: Apply nesting limit more sanely

[Markus Armbruster]

The nesting limit from commit 29c75dd "json-streamer: limit the
maximum recursion depth and maximum token count" applies separately to
braces and brackets.  This makes no sense.  Apply it to their sum,
because that's actually a measure of recursion depth.

Signed-off-by: Markus Armbruster <armbru@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
---
 qobject/json-streamer.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/qobject/json-streamer.c b/qobject/json-streamer.c
index 1b2f9b1..dced2c7 100644
--- a/qobject/json-streamer.c
+++ b/qobject/json-streamer.c
@@ -64,8 +64,7 @@ static void json_message_process_token(JSONLexer *lexer, QString *token, JSONTok
          parser->bracket_count == 0)) {
         goto out_emit;
     } else if (parser->token_size > MAX_TOKEN_SIZE ||
-               parser->bracket_count > MAX_NESTING ||
-               parser->brace_count > MAX_NESTING) {
+               parser->bracket_count + parser->brace_count > MAX_NESTING) {
         /* Security consideration, we limit total memory allocated per object
          * and the maximum recursion depth that a message can force.
          */
-- 
2.4.3

[Qemu-devel] [PATCH v2 2/4] json-streamer: Don't crash when input exceeds nesting limit

[Markus Armbruster]

We limit nesting depth and input size to defend against input
triggering excessive heap or stack memory use (commit 29c75dd
json-streamer: limit the maximum recursion depth and maximum token
count).  However, when the nesting limit is exceeded,
parser_context_peek_token()'s assertion fails.

Broken in commit 65c0f1e "json-parser: don't replicate tokens at each
level of recursion".

To reproduce stuff 1025 open braces or brackets into QMP.

Fix by taking the error exit instead of the normal one.

Reported-by: Eric Blake <eblake@redhat.com>
Signed-off-by: Markus Armbruster <armbru@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
---
 qobject/json-streamer.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/qobject/json-streamer.c b/qobject/json-streamer.c
index dced2c7..2bd22a7 100644
--- a/qobject/json-streamer.c
+++ b/qobject/json-streamer.c
@@ -68,13 +68,14 @@ static void json_message_process_token(JSONLexer *lexer, QString *token, JSONTok
         /* Security consideration, we limit total memory allocated per object
          * and the maximum recursion depth that a message can force.
          */
-        goto out_emit;
+        goto out_emit_bad;
     }
 
     return;
 
 out_emit_bad:
-    /* clear out token list and tell the parser to emit and error
+    /*
+     * Clear out token list and tell the parser to emit an error
      * indication by passing it a NULL list
      */
     QDECREF(parser->tokens);
-- 
2.4.3

[Qemu-devel] [PATCH v2 3/4] check-qjson: Add test for JSON nesting depth limit

[Markus Armbruster]

This would have prevented the regression mentioned in the previous
commit.

Signed-off-by: Markus Armbruster <armbru@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
---
 tests/check-qjson.c | 25 +++++++++++++++++++++++++
 1 file changed, 25 insertions(+)

diff --git a/tests/check-qjson.c b/tests/check-qjson.c
index 1cfffa5..61e9bfb 100644
--- a/tests/check-qjson.c
+++ b/tests/check-qjson.c
@@ -1484,6 +1484,30 @@ static void unterminated_literal(void)
     g_assert(obj == NULL);
 }
 
+static char *make_nest(char *buf, size_t cnt)
+{
+    memset(buf, '[', cnt - 1);
+    buf[cnt - 1] = '{';
+    buf[cnt] = '}';
+    memset(buf + cnt + 1, ']', cnt - 1);
+    buf[2 * cnt] = 0;
+    return buf;
+}
+
+static void limits_nesting(void)
+{
+    enum { max_nesting = 1024 }; /* see qobject/json-streamer.c */
+    char buf[2 * (max_nesting + 1) + 1];
+    QObject *obj;
+
+    obj = qobject_from_json(make_nest(buf, max_nesting));
+    g_assert(obj != NULL);
+    qobject_decref(obj);
+
+    obj = qobject_from_json(make_nest(buf, max_nesting + 1));
+    g_assert(obj == NULL);
+}
+
 int main(int argc, char **argv)
 {
     g_test_init(&argc, &argv, NULL);
@@ -1519,6 +1543,7 @@ int main(int argc, char **argv)
     g_test_add_func("/errors/invalid_array_comma", invalid_array_comma);
     g_test_add_func("/errors/invalid_dict_comma", invalid_dict_comma);
     g_test_add_func("/errors/unterminated/literal", unterminated_literal);
+    g_test_add_func("/errors/limits/nesting", limits_nesting);
 
     return g_test_run();
 }
-- 
2.4.3

[Qemu-devel] [PATCH v2 4/4] json-streamer: Limit number of tokens in addition to total size

[Markus Armbruster]

Commit 29c75dd "json-streamer: limit the maximum recursion depth and
maximum token count" attempts to guard against excessive heap usage by
limiting total token size (it says "token count", but that's a lie).

Total token size is a rather imprecise predictor of heap usage: many
small tokens use more space than few large tokens with the same input
size, because there's a constant per-token overhead.

Tighten this up: limit the token count to 128Ki.

If you think 128Ki is too stingy: check-qjson's large_dict test eats a
sweet 500MiB on my machine to parse ~100K tokens.  Absurdly wasteful.

Signed-off-by: Markus Armbruster <armbru@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
---
 qobject/json-streamer.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/qobject/json-streamer.c b/qobject/json-streamer.c
index 2bd22a7..8752834 100644
--- a/qobject/json-streamer.c
+++ b/qobject/json-streamer.c
@@ -19,6 +19,7 @@
 #include "qapi/qmp/json-streamer.h"
 
 #define MAX_TOKEN_SIZE (64ULL << 20)
+#define MAX_TOKEN_COUNT (128ULL << 10)
 #define MAX_NESTING (1ULL << 10)
 
 static void json_message_process_token(JSONLexer *lexer, QString *token, JSONTokenType type, int x, int y)
@@ -64,6 +65,7 @@ static void json_message_process_token(JSONLexer *lexer, QString *token, JSONTok
          parser->bracket_count == 0)) {
         goto out_emit;
     } else if (parser->token_size > MAX_TOKEN_SIZE ||
+               qlist_size(parser->tokens) > MAX_TOKEN_COUNT ||
                parser->bracket_count + parser->brace_count > MAX_NESTING) {
         /* Security consideration, we limit total memory allocated per object
          * and the maximum recursion depth that a message can force.
-- 
2.4.3

Re: [Qemu-devel] [PATCH v2 4/4] json-streamer: Limit number of tokens in addition to total size

[Paolo Bonzini]

On 19/11/2015 16:29, Markus Armbruster wrote:
> Commit 29c75dd "json-streamer: limit the maximum recursion depth and
> maximum token count" attempts to guard against excessive heap usage by
> limiting total token size (it says "token count", but that's a lie).
> 
> Total token size is a rather imprecise predictor of heap usage: many
> small tokens use more space than few large tokens with the same input
> size, because there's a constant per-token overhead.
> 
> Tighten this up: limit the token count to 128Ki.
> 
> If you think 128Ki is too stingy: check-qjson's large_dict test eats a
> sweet 500MiB on my machine to parse ~100K tokens.

How much of this is freed before the start of the parse?

> Signed-off-by: Markus Armbruster <armbru@redhat.com>
> Reviewed-by: Eric Blake <eblake@redhat.com>
> ---
>  qobject/json-streamer.c | 2 ++
>  1 file changed, 2 insertions(+)
> 
> diff --git a/qobject/json-streamer.c b/qobject/json-streamer.c
> index 2bd22a7..8752834 100644
> --- a/qobject/json-streamer.c
> +++ b/qobject/json-streamer.c
> @@ -19,6 +19,7 @@
>  #include "qapi/qmp/json-streamer.h"
>  
>  #define MAX_TOKEN_SIZE (64ULL << 20)
> +#define MAX_TOKEN_COUNT (128ULL << 10)
>  #define MAX_NESTING (1ULL << 10)
>  
>  static void json_message_process_token(JSONLexer *lexer, QString *token, JSONTokenType type, int x, int y)
> @@ -64,6 +65,7 @@ static void json_message_process_token(JSONLexer *lexer, QString *token, JSONTok
>           parser->bracket_count == 0)) {
>          goto out_emit;
>      } else if (parser->token_size > MAX_TOKEN_SIZE ||
> +               qlist_size(parser->tokens) > MAX_TOKEN_COUNT ||

This is O(n^2).  I'd rather skip this patch, fix the memory hog and
possibly decrease MAX_TOKEN_SIZE a bit.

Paolo

>                 parser->bracket_count + parser->brace_count > MAX_NESTING) {
>          /* Security consideration, we limit total memory allocated per object
>           * and the maximum recursion depth that a message can force.
> 

Re: [Qemu-devel] [PATCH v2 4/4] json-streamer: Limit number of tokens in addition to total size

[Markus Armbruster]

Paolo Bonzini <pbonzini@redhat.com> writes:

> On 19/11/2015 16:29, Markus Armbruster wrote:
>> Commit 29c75dd "json-streamer: limit the maximum recursion depth and
>> maximum token count" attempts to guard against excessive heap usage by
>> limiting total token size (it says "token count", but that's a lie).
>> 
>> Total token size is a rather imprecise predictor of heap usage: many
>> small tokens use more space than few large tokens with the same input
>> size, because there's a constant per-token overhead.
>> 
>> Tighten this up: limit the token count to 128Ki.
>> 
>> If you think 128Ki is too stingy: check-qjson's large_dict test eats a
>> sweet 500MiB on my machine to parse ~100K tokens.
>
> How much of this is freed before the start of the parse?
>
>> Signed-off-by: Markus Armbruster <armbru@redhat.com>
>> Reviewed-by: Eric Blake <eblake@redhat.com>
>> ---
>>  qobject/json-streamer.c | 2 ++
>>  1 file changed, 2 insertions(+)
>> 
>> diff --git a/qobject/json-streamer.c b/qobject/json-streamer.c
>> index 2bd22a7..8752834 100644
>> --- a/qobject/json-streamer.c
>> +++ b/qobject/json-streamer.c
>> @@ -19,6 +19,7 @@
>>  #include "qapi/qmp/json-streamer.h"
>>  
>>  #define MAX_TOKEN_SIZE (64ULL << 20)
>> +#define MAX_TOKEN_COUNT (128ULL << 10)
>>  #define MAX_NESTING (1ULL << 10)
>>  
>>  static void json_message_process_token(JSONLexer *lexer, QString *token, JSONTokenType type, int x, int y)
>> @@ -64,6 +65,7 @@ static void json_message_process_token(JSONLexer *lexer, QString *token, JSONTok
>>           parser->bracket_count == 0)) {
>>          goto out_emit;
>>      } else if (parser->token_size > MAX_TOKEN_SIZE ||
>> +               qlist_size(parser->tokens) > MAX_TOKEN_COUNT ||
>
> This is O(n^2).  I'd rather skip this patch, fix the memory hog and
> possibly decrease MAX_TOKEN_SIZE a bit.

I can't see the square right now.  Anyway, O() is unchanged by my patch,
only n is more limited.  See also commit 65c0f1e, which claims to have
fixed the quadradic behavior.

Regardless, the memory consumption is still ridiculous, and we certainly
need to fix that.  Whether we can have one for 2.5 I don't know.

Even with a fix, this patch has some value.  As explained in the commit
message, "total token size is a rather imprecise predictor of heap
usage: many small tokens use more space than few large tokens with the
same input size, because there's a constant per-token overhead."  As
long as we limit input to limit memory use, we better use a limit that's
connected to actual memory use with reasonable accuracy  This patch
improves accuracy.

>>                 parser->bracket_count + parser->brace_count > MAX_NESTING) {
>>          /* Security consideration, we limit total memory allocated per object
>>           * and the maximum recursion depth that a message can force.

Re: [Qemu-devel] [PATCH v2 4/4] json-streamer: Limit number of tokens in addition to total size

[Paolo Bonzini]

On 20/11/2015 07:13, Markus Armbruster wrote:
>>> @@ -64,6 +65,7 @@ static void json_message_process_token(JSONLexer *lexer, QString *token, JSONTok
>>>           parser->bracket_count == 0)) {
>>>          goto out_emit;
>>>      } else if (parser->token_size > MAX_TOKEN_SIZE ||
>>> +               qlist_size(parser->tokens) > MAX_TOKEN_COUNT ||
>>
>> This is O(n^2).  I'd rather skip this patch, fix the memory hog and
>> possibly decrease MAX_TOKEN_SIZE a bit.
> 
> I can't see the square right now.

It's hidden in qlist_size:

static void qlist_size_iter(QObject *obj, void *opaque)
{
    size_t *count = opaque;
    (*count)++;
}

size_t qlist_size(const QList *qlist)
{
    size_t count = 0;
    qlist_iter(qlist, qlist_size_iter, &count);
    return count;
}

You process the whole list on every token, which makes it O(n^2) where n
is the token count.

Paolo

  Anyway, O() is unchanged by my patch,
> only n is more limited.  See also commit 65c0f1e, which claims to have
> fixed the quadradic behavior.
> 
> Regardless, the memory consumption is still ridiculous, and we certainly
> need to fix that.  Whether we can have one for 2.5 I don't know.
> 
> Even with a fix, this patch has some value.  As explained in the commit
> message, "total token size is a rather imprecise predictor of heap
> usage: many small tokens use more space than few large tokens with the
> same input size, because there's a constant per-token overhead."  As
> long as we limit input to limit memory use, we better use a limit that's
> connected to actual memory use with reasonable accuracy  This patch
> improves accuracy.
> 
>>>                 parser->bracket_count + parser->brace_count > MAX_NESTING) {
>>>          /* Security consideration, we limit total memory allocated per object
>>>           * and the maximum recursion depth that a message can force.
> 
> 

Re: [Qemu-devel] [PATCH v2 4/4] json-streamer: Limit number of tokens in addition to total size

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 1139 bytes --]

On 11/20/2015 01:50 AM, Paolo Bonzini wrote:
> 
> 
> On 20/11/2015 07:13, Markus Armbruster wrote:
>>>> @@ -64,6 +65,7 @@ static void json_message_process_token(JSONLexer *lexer, QString *token, JSONTok
>>>>           parser->bracket_count == 0)) {
>>>>          goto out_emit;
>>>>      } else if (parser->token_size > MAX_TOKEN_SIZE ||
>>>> +               qlist_size(parser->tokens) > MAX_TOKEN_COUNT ||
>>>
>>> This is O(n^2).  I'd rather skip this patch, fix the memory hog and
>>> possibly decrease MAX_TOKEN_SIZE a bit.
>>
>> I can't see the square right now.
> 
> It's hidden in qlist_size:
> 
> static void qlist_size_iter(QObject *obj, void *opaque)
> {
>     size_t *count = opaque;
>     (*count)++;
> }

Yuck - we don't track size independently?  Seems like it might make a
worthwhile addition, as well as convenience functions for efficiently
adding/removing a member at either end of the list.  (But we already
know that the QObject hierarchy is silly with some of the things it does).

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH v2 4/4] json-streamer: Limit number of tokens in addition to total size

[Paolo Bonzini]

On 20/11/2015 18:32, Eric Blake wrote:
> > static void qlist_size_iter(QObject *obj, void *opaque)
> > {
> >     size_t *count = opaque;
> >     (*count)++;
> > }
> 
> Yuck - we don't track size independently?  Seems like it might make a
> worthwhile addition,

Would you change your mind, if I told you that qlist_size is unused? :)

Paolo

Re: [Qemu-devel] [PATCH v2 4/4] json-streamer: Limit number of tokens in addition to total size

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 668 bytes --]

On 11/23/2015 07:27 AM, Paolo Bonzini wrote:
> 
> 
> On 20/11/2015 18:32, Eric Blake wrote:
>>> static void qlist_size_iter(QObject *obj, void *opaque)
>>> {
>>>     size_t *count = opaque;
>>>     (*count)++;
>>> }
>>
>> Yuck - we don't track size independently?  Seems like it might make a
>> worthwhile addition,
> 
> Would you change your mind, if I told you that qlist_size is unused? :)

Deleting dead code is a perfectly acceptable alternative to advertising
what should normally be an O(1) operation with an O(n) implementation. :)

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH v2 4/4] json-streamer: Limit number of tokens in addition to total size

[Markus Armbruster]

Eric Blake <eblake@redhat.com> writes:

> On 11/23/2015 07:27 AM, Paolo Bonzini wrote:
>> 
>> 
>> On 20/11/2015 18:32, Eric Blake wrote:
>>>> static void qlist_size_iter(QObject *obj, void *opaque)
>>>> {
>>>>     size_t *count = opaque;
>>>>     (*count)++;
>>>> }
>>>
>>> Yuck - we don't track size independently?  Seems like it might make a
>>> worthwhile addition,
>> 
>> Would you change your mind, if I told you that qlist_size is unused? :)
>
> Deleting dead code is a perfectly acceptable alternative to advertising
> what should normally be an O(1) operation with an O(n) implementation. :)

Well, "length of list" certainly isn't O(1) everywhere.  The Common Lisp
Hyperspec, for instance, gives an O(n) example implementation[*].
Generally just fine as long as callers are aware.


[*] http://www.lispworks.com/documentation/HyperSpec/Body/f_list_l.htm#list-length

Re: [Qemu-devel] [PATCH v2 0/4] json-streamer: Fix up code to limit nesting and size

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 1180 bytes --]

On 11/19/2015 08:29 AM, Markus Armbruster wrote:
> Ugh, I almost dropped this on the floor.  I think it should go into
> 2.5, and I plan to take it through my tree.  If you disagree, please
> speak up.

It sounds like a bug fix to me (avoiding core dumps due to
user-triggerable input) and on that ground, qualifies for hard freeze in
my books.

> 
> We limit nesting depth and input size to defend against input
> triggering excessive heap or stack memory use (commit 29c75dd
> json-streamer: limit the maximum recursion depth and maximum token
> count).  This limiting is flawed in multiple ways.  Fix it up some.
> 
> Not yet fixed: this JSON parser is an absurd memory hog; see last
> patch.
> 
> v2:
> * Trivially rebased, R-bys retained
> * PATCH 3: Fix a nearby comment typo [Eric]
> * PATCH 4: Simplify make_nest() slightly
> * PATCH 5: Commit message tweaked

Hmm, when the series is only 4/4, changes to PATCH 5 are suspect :)

At any rate, the changes look correct, and minor enough that keeping my
R-b was the right thing to do.

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH v2 0/4] json-streamer: Fix up code to limit nesting and size

[Markus Armbruster]

Eric Blake <eblake@redhat.com> writes:

> On 11/19/2015 08:29 AM, Markus Armbruster wrote:
>> Ugh, I almost dropped this on the floor.  I think it should go into
>> 2.5, and I plan to take it through my tree.  If you disagree, please
>> speak up.
>
> It sounds like a bug fix to me (avoiding core dumps due to
> user-triggerable input) and on that ground, qualifies for hard freeze in
> my books.
>
>> 
>> We limit nesting depth and input size to defend against input
>> triggering excessive heap or stack memory use (commit 29c75dd
>> json-streamer: limit the maximum recursion depth and maximum token
>> count).  This limiting is flawed in multiple ways.  Fix it up some.
>> 
>> Not yet fixed: this JSON parser is an absurd memory hog; see last
>> patch.
>> 
>> v2:
>> * Trivially rebased, R-bys retained
>> * PATCH 3: Fix a nearby comment typo [Eric]
>> * PATCH 4: Simplify make_nest() slightly
>> * PATCH 5: Commit message tweaked
>
> Hmm, when the series is only 4/4, changes to PATCH 5 are suspect :)

I can't count.  Subtract one from every patch number in the list above.

> At any rate, the changes look correct, and minor enough that keeping my
> R-b was the right thing to do.

Thanks!