Re: [Qemu-devel] [PATCH for-2.6 12/14] qemu-img: In 'map', use QDict to generate JSON output

[Fam Zheng <famz@redhat.com>]

On Mon, 11/23 22:42, Eric Blake wrote:
> On 11/23/2015 10:22 PM, Fam Zheng wrote:
> > +++ b/tests/qemu-iotests/122.out
> > @@ -49,12 +49,13 @@ read 65536/65536 bytes at offset 4194304
> >  64 KiB, X ops; XX:XX:XX.X (XXX YYY/sec and XXX ops/sec)
> >  read 65536/65536 bytes at offset 8388608
> >  64 KiB, X ops; XX:XX:XX.X (XXX YYY/sec and XXX ops/sec)
> > -[{ "start": 0, "length": 65536, "depth": 0, "zero": false, "data": true},
> > -{ "start": 65536, "length": 4128768, "depth": 0, "zero": true, "data": false},
> > -{ "start": 4194304, "length": 65536, "depth": 0, "zero": false, "data": true},
> > -{ "start": 4259840, "length": 4128768, "depth": 0, "zero": true, "data": false},
> > -{ "start": 8388608, "length": 65536, "depth": 0, "zero": false, "data": true},
> > -{ "start": 8454144, "length": 4128768, "depth": 0, "zero": true, "data": false}]
> > +[{"length": 65536, "start": 0, "zero": false, "depth": 0, "data": true}
> 
> ...but the output shows that QDict output is tied to internal hashing
> and therefore different than first-in-first-out creation order.
> JSON-wise, it's still valid.  But are we guaranteed that our hashing is
> stable?  If so, is that something an attacker could attempt to exploit
> as a Denial of Service, by intentionally creating predictable
> collisions?  [I'm guessing not, as the denial of service is mainly an
> issue if a user can degrade performance of typical lookups from nominal
> O(1) to O(n) by supplying LOTS of user-provided input, but the keys we
> output in JSON are generally under our control via .json files and not
> something where the user is dynamically creating lots of keys - but
> still worth asking.]

Interesting question.

I think creating a lot of colliding keys is possible, for example by creating a
huge set of options in the same level, or maybe just by providing a large
invalid 'json:' pseudo file name.

I wonder how QMP would handle this, because it also needs to parse json into
QObject.

> And if it is not stable, then will our test break
> when someone else's system hashes differently than yours?

We are using a deterministic hash function in qdict_put_obj, tdb_hash, so this
order is stable.

Fam