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
