Denial of service when parsing JSON object with keys that have the same hash code

[plokhotnyuk]

Sub-quadratic decreasing of throughput when number of JSON object fields (with keys that have the same hash code) is increasing

On contemporary CPUs parsing of such JSON object (with a sequence of 100000 fields like below that is ~1.6Mb) can took more than 110 seconds for both Native and Jackson parsers:

{
"!!sjyehe":null,
"!!sjyeiF":null,
"!!sjyej'":null,
"!!sjyfIe":null,
"!!sjyfJF":null,
...
}

Below are results of the benchmark where size is a number of such fields:

[info] REMEMBER: The numbers below are just data. To gain reusable insights, you need to follow up on
[info] why the numbers are the way they are. Use profilers (see -prof, -lprof), design factorial
[info] experiments, perform baseline and negative tests that provide experimental control, make sure
[info] the benchmarking environment is safe on JVM/OS/HW level, ask for reviews from the domain experts.
[info] Do not assume the numbers tell you what you want them to tell.
[info] Benchmark                                 (size)  (value)   Mode  Cnt       Score       Error  Units
[info] ExtractFieldsBenchmark.readJson4sJackson       1     null  thrpt    5  602188.936 ± 27334.168  ops/s
[info] ExtractFieldsBenchmark.readJson4sJackson      10     null  thrpt    5  287870.015 ± 25355.040  ops/s
[info] ExtractFieldsBenchmark.readJson4sJackson     100     null  thrpt    5   17969.142 ±   536.239  ops/s
[info] ExtractFieldsBenchmark.readJson4sJackson    1000     null  thrpt    5     162.313 ±    24.082  ops/s
[info] ExtractFieldsBenchmark.readJson4sJackson   10000     null  thrpt    5       1.225 ±     0.208  ops/s
[info] ExtractFieldsBenchmark.readJson4sJackson  100000     null  thrpt    5       0.009 ±     0.001  ops/s
[info] ExtractFieldsBenchmark.readJson4sNative        1     null  thrpt    5  493786.994 ± 75575.494  ops/s
[info] ExtractFieldsBenchmark.readJson4sNative       10     null  thrpt    5  246570.296 ± 27087.279  ops/s
[info] ExtractFieldsBenchmark.readJson4sNative      100     null  thrpt    5   19075.474 ±  2888.108  ops/s
[info] ExtractFieldsBenchmark.readJson4sNative     1000     null  thrpt    5     185.121 ±     9.850  ops/s
[info] ExtractFieldsBenchmark.readJson4sNative    10000     null  thrpt    5       1.463 ±     0.202  ops/s
[info] ExtractFieldsBenchmark.readJson4sNative   100000     null  thrpt    5       0.008 ±     0.001  ops/s

json4s version

4.0.5

Scala version

2.13.8

JDK version

11+

Steps to reproduce

To run that benchmarks on your JDK:

1. Install latest version of sbt and/or ensure that it already installed properly:

sbt about

2. Clone jsoniter-scala repo:

git clone --depth 1 https://github.com/plokhotnyuk/jsoniter-scala.git

3. Enter to the cloned directory and checkout for the specific branch:

cd jsoniter-scala
git checkout json4s-DoS-by-hashmap-collisions-2

4. Run benchmarks:

sbt 'jsoniter-scala-benchmarkJVM/jmh:run -wi 1 -i 1 json4s'