bos/attoparsec — pull request #63 by basvandijk (2014-05-15 12:26:46+00:00)
Title: Protect against DoS attacks in the double and number parsers

This protects against attackers submitting numbers with huge exponents like `1e1000000000` which will allocate an Integer that will fill up all space and crash your program.

Benchmark results:

Before (with scientific-0.2.0.2):

```
dist/build/attoparsec-benchmarks/attoparsec-benchmarks numbers
warming up
estimating clock resolution...
mean is 1.385885 us (640001 iterations)
found 4208 outliers among 639999 samples (0.7%)
3684 (0.6%) high severe
estimating cost of a clock call...
mean is 36.05057 ns (12 iterations)
found 1 outliers among 12 samples (8.3%)
1 (8.3%) high severe

benchmarking numbers/Text/no power/double
mean: 1.789861 us, lb 1.782588 us, ub 1.798735 us, ci 0.950
std dev: 40.92927 ns, lb 33.95569 ns, ub 49.22321 ns, ci 0.950
found 7 outliers among 100 samples (7.0%)
7 (7.0%) high mild
variance introduced by outliers: 16.136%
variance is moderately inflated by outliers

benchmarking numbers/Text/no power/number
mean: 658.1771 ns, lb 655.2508 ns, ub 661.6399 ns, ci 0.950
std dev: 16.35886 ns, lb 13.93333 ns, ub 19.79895 ns, ci 0.950
found 9 outliers among 100 samples (9.0%)
8 (8.0%) high mild
1 (1.0%) high severe
variance introduced by outliers: 18.988%
variance is moderately inflated by outliers

benchmarking numbers/Text/no power/rational
mean: 867.8670 ns, lb 863.3896 ns, ub 875.8339 ns, ci 0.950
std dev: 29.99400 ns, lb 19.81676 ns, ub 52.06509 ns, ci 0.950
found 4 outliers among 100 samples (4.0%)
3 (3.0%) high severe
variance introduced by outliers: 30.660%
variance is moderately inflated by outliers

benchmarking numbers/Text/no power/scientific
mean: 1.389188 us, lb 1.384693 us, ub 1.394222 us, ci 0.950
std dev: 24.29212 ns, lb 21.04810 ns, ub 29.11669 ns, ci 0.950
found 1 outliers among 100 samples (1.0%)
variance introduced by outliers: 10.382%
variance is moderately inflated by outliers

benchmarking numbers/Text/positive power/double
mean: 1.872370 us, lb 1.866655 us, ub 1.878635 us, ci 0.950
std dev: 30.66353 ns, lb 27.10545 ns, ub 36.11944 ns, ci 0.950
found 1 outliers among 100 samples (1.0%)
variance introduced by outliers: 9.417%
variance is slightly inflated by outliers

benchmarking numbers/Text/positive power/number
mean: 893.9521 ns, lb 885.4376 ns, ub 917.9299 ns, ci 0.950
std dev: 66.96130 ns, lb 19.56682 ns, ub 140.9303 ns, ci 0.950
found 4 outliers among 100 samples (4.0%)
2 (2.0%) high mild
2 (2.0%) high severe
variance introduced by outliers: 67.674%
variance is severely inflated by outliers

benchmarking numbers/Text/positive power/rational
mean: 1.018756 us, lb 1.008953 us, ub 1.039642 us, ci 0.950
std dev: 70.54975 ns, lb 40.04130 ns, ub 138.9483 ns, ci 0.950
found 4 outliers among 100 samples (4.0%)
3 (3.0%) high mild
1 (1.0%) high severe
variance introduced by outliers: 64.581%
variance is severely inflated by outliers

benchmarking numbers/Text/positive power/scientific
mean: 1.417434 us, lb 1.411348 us, ub 1.425701 us, ci 0.950
std dev: 36.10782 ns, lb 27.88290 ns, ub 49.84465 ns, ci 0.950
found 5 outliers among 100 samples (5.0%)
3 (3.0%) high mild
2 (2.0%) high severe
variance introduced by outliers: 19.037%
variance is moderately inflated by outliers

benchmarking numbers/Text/negative power/double
mean: 1.949823 us, lb 1.943062 us, ub 1.957260 us, ci 0.950
std dev: 36.31832 ns, lb 31.48645 ns, ub 44.75378 ns, ci 0.950
found 2 outliers among 100 samples (2.0%)
2 (2.0%) high mild
variance introduced by outliers: 11.351%
variance is moderately inflated by outliers

benchmarking numbers/Text/negative power/number
mean: 901.2251 ns, lb 897.8305 ns, ub 904.8267 ns, ci 0.950
std dev: 18.00321 ns, lb 15.96391 ns, ub 20.33880 ns, ci 0.950
found 5 outliers among 100 samples (5.0%)
5 (5.0%) high mild
variance introduced by outliers: 13.233%
variance is moderately inflated by outliers

benchmarking numbers/Text/negative power/rational
mean: 1.104231 us, lb 1.059707 us, ub 1.282165 us, ci 0.950
std dev: 435.0459 ns, lb 16.72614 ns, ub 953.2309 ns, ci 0.950
found 1 outliers among 100 samples (1.0%)
1 (1.0%) high severe
variance introduced by outliers: 98.901%
variance is severely inflated by outliers

benchmarking numbers/Text/negative power/scientific
mean: 2.002639 us, lb 1.994584 us, ub 2.021817 us, ci 0.950
std dev: 60.12069 ns, lb 31.92064 ns, ub 123.4070 ns, ci 0.950
found 2 outliers among 100 samples (2.0%)
1 (1.0%) high severe
variance introduced by outliers: 24.828%
variance is moderately inflated by outliers

benchmarking numbers/ByteString/no power/double
mean: 1.474630 us, lb 1.469304 us, ub 1.481843 us, ci 0.950
std dev: 31.30102 ns, lb 24.52956 ns, ub 47.86533 ns, ci 0.950
found 3 outliers among 100 samples (3.0%)
2 (2.0%) high mild
1 (1.0%) high severe
variance introduced by outliers: 14.220%
variance is moderately inflated by outliers

benchmarking numbers/ByteString/no power/number
mean: 453.8184 ns, lb 452.1310 ns, ub 456.5568 ns, ci 0.950
std dev: 10.77711 ns, lb 7.547833 ns, ub 18.46812 ns, ci 0.950
found 2 outliers among 100 samples (2.0%)
1 (1.0%) high severe
variance introduced by outliers: 17.102%
variance is moderately inflated by outliers

benchmarking numbers/ByteString/no power/rational
mean: 587.5115 ns, lb 585.1111 ns, ub 590.9007 ns, ci 0.950
std dev: 14.45448 ns, lb 11.17672 ns, ub 22.34739 ns, ci 0.950
found 4 outliers among 100 samples (4.0%)
3 (3.0%) high mild
1 (1.0%) high severe
variance introduced by outliers: 18.068%
variance is moderately inflated by outliers

benchmarking numbers/ByteString/no power/scientific
mean: 1.073893 us, lb 1.070596 us, ub 1.078112 us, ci 0.950
std dev: 19.07358 ns, lb 15.50738 ns, ub 25.30646 ns, ci 0.950
found 3 outliers among 100 samples (3.0%)
2 (2.0%) high mild
1 (1.0%) high severe
variance introduced by outliers: 10.401%
variance is moderately inflated by outliers

benchmarking numbers/ByteString/positive power/double
mean: 1.501396 us, lb 1.494834 us, ub 1.516830 us, ci 0.950
std dev: 48.65814 ns, lb 26.21426 ns, ub 99.69970 ns, ci 0.950
found 2 outliers among 100 samples (2.0%)
1 (1.0%) high severe
variance introduced by outliers: 27.749%
variance is moderately inflated by outliers

benchmarking numbers/ByteString/positive power/number
mean: 530.0334 ns, lb 528.1457 ns, ub 532.0617 ns, ci 0.950
std dev: 10.03770 ns, lb 9.046443 ns, ub 11.25548 ns, ci 0.950
variance introduced by outliers: 11.373%
variance is moderately inflated by outliers

benchmarking numbers/ByteString/positive power/rational
mean: 684.3536 ns, lb 681.7858 ns, ub 687.4235 ns, ci 0.950
std dev: 14.34521 ns, lb 12.10794 ns, ub 18.34627 ns, ci 0.950
found 2 outliers among 100 samples (2.0%)
2 (2.0%) high mild
variance introduced by outliers: 14.200%
variance is moderately inflated by outliers

benchmarking numbers/ByteString/positive power/scientific
mean: 957.2075 ns, lb 953.6807 ns, ub 960.9852 ns, ci 0.950
std dev: 18.77402 ns, lb 16.80774 ns, ub 21.33972 ns, ci 0.950
variance introduced by outliers: 12.314%
variance is moderately inflated by outliers

benchmarking numbers/ByteString/negative power/double
mean: 1.658359 us, lb 1.652376 us, ub 1.665012 us, ci 0.950
std dev: 32.19721 ns, lb 28.12926 ns, ub 38.27164 ns, ci 0.950
found 1 outliers among 100 samples (1.0%)
variance introduced by outliers: 12.299%
variance is moderately inflated by outliers

benchmarking numbers/ByteString/negative power/number
mean: 580.0369 ns, lb 577.5277 ns, ub 582.9065 ns, ci 0.950
std dev: 13.73976 ns, lb 11.98741 ns, ub 16.20520 ns, ci 0.950
variance introduced by outliers: 17.098%
variance is moderately inflated by outliers

benchmarking numbers/ByteString/negative power/rational
mean: 774.7915 ns, lb 772.1097 ns, ub 777.7998 ns, ci 0.950
std dev: 14.59381 ns, lb 12.62714 ns, ub 17.01120 ns, ci 0.950
found 5 outliers among 100 samples (5.0%)
5 (5.0%) high mild
variance introduced by outliers: 11.366%
variance is moderately inflated by outliers

benchmarking numbers/ByteString/negative power/scientific
mean: 1.518987 us, lb 1.513694 us, ub 1.524776 us, ci 0.950
std dev: 28.41254 ns, lb 25.20542 ns, ub 33.38271 ns, ci 0.950
variance introduced by outliers: 11.357%
variance is moderately inflated by outliers
```

After (with scientific-0.3.1.0):
```
dist/build/attoparsec-benchmarks/attoparsec-benchmarks numbers
warming up
estimating clock resolution...
mean is 1.411744 us (640001 iterations)
found 5000 outliers among 639999 samples (0.8%)
4367 (0.7%) high severe
estimating cost of a clock call...
mean is 36.13514 ns (13 iterations)
found 3 outliers among 13 samples (23.1%)
1 (7.7%) high mild
2 (15.4%) high severe

benchmarking numbers/Text/no power/double
mean: 1.891598 us, lb 1.884279 us, ub 1.900180 us, ci 0.950
std dev: 40.62361 ns, lb 34.34593 ns, ub 48.39674 ns, ci 0.950
found 6 outliers among 100 samples (6.0%)
6 (6.0%) high mild
variance introduced by outliers: 14.238%
variance is moderately inflated by outliers

benchmarking numbers/Text/no power/number
mean: 1.749780 us, lb 1.741842 us, ub 1.759167 us, ci 0.950
std dev: 44.19361 ns, lb 37.70409 ns, ub 54.52050 ns, ci 0.950
found 2 outliers among 100 samples (2.0%)
2 (2.0%) high mild
variance introduced by outliers: 19.020%
variance is moderately inflated by outliers

benchmarking numbers/Text/no power/rational
mean: 781.0500 ns, lb 778.4765 ns, ub 784.5049 ns, ci 0.950
std dev: 15.24479 ns, lb 11.89594 ns, ub 19.92520 ns, ci 0.950
found 9 outliers among 100 samples (9.0%)
2 (2.0%) high mild
7 (7.0%) high severe
variance introduced by outliers: 12.307%
variance is moderately inflated by outliers

benchmarking numbers/Text/no power/scientific
mean: 1.227013 us, lb 1.206786 us, ub 1.278288 us, ci 0.950
std dev: 152.6173 ns, lb 57.04502 ns, ub 287.9761 ns, ci 0.950
found 7 outliers among 100 samples (7.0%)
3 (3.0%) high mild
4 (4.0%) high severe
variance introduced by outliers: 85.253%
variance is severely inflated by outliers

benchmarking numbers/Text/positive power/double
mean: 2.105823 us, lb 2.095827 us, ub 2.123078 us, ci 0.950
std dev: 65.49106 ns, lb 43.92357 ns, ub 116.4552 ns, ci 0.950
found 4 outliers among 100 samples (4.0%)
2 (2.0%) high mild
2 (2.0%) high severe
variance introduced by outliers: 26.733%
variance is moderately inflated by outliers

benchmarking numbers/Text/positive power/number
mean: 2.107771 us, lb 2.053178 us, ub 2.280509 us, ci 0.950
std dev: 434.0323 ns, lb 60.62918 ns, ub 949.8332 ns, ci 0.950
found 8 outliers among 100 samples (8.0%)
6 (6.0%) high mild
2 (2.0%) high severe
variance introduced by outliers: 94.667%
variance is severely inflated by outliers

benchmarking numbers/Text/positive power/rational
mean: 1.035741 us, lb 1.029471 us, ub 1.055477 us, ci 0.950
std dev: 51.80368 ns, lb 19.73631 ns, ub 114.3537 ns, ci 0.950
found 4 outliers among 100 samples (4.0%)
3 (3.0%) high severe
variance introduced by outliers: 48.439%
variance is moderately inflated by outliers

benchmarking numbers/Text/positive power/scientific
mean: 1.365859 us, lb 1.329112 us, ub 1.490467 us, ci 0.950
std dev: 294.3282 ns, lb 26.91353 ns, ub 662.9092 ns, ci 0.950
found 5 outliers among 100 samples (5.0%)
2 (2.0%) high mild
3 (3.0%) high severe
variance introduced by outliers: 94.696%
variance is severely inflated by outliers

benchmarking numbers/Text/negative power/double
mean: 2.119322 us, lb 2.113097 us, ub 2.126303 us, ci 0.950
std dev: 33.64836 ns, lb 29.14649 ns, ub 40.34632 ns, ci 0.950
found 2 outliers among 100 samples (2.0%)
2 (2.0%) high mild
variance introduced by outliers: 8.498%
variance is slightly inflated by outliers

benchmarking numbers/Text/negative power/number
mean: 2.228222 us, lb 2.158715 us, ub 2.415129 us, ci 0.950
std dev: 537.5291 ns, lb 229.4374 ns, ub 1.099815 us, ci 0.950
found 6 outliers among 100 samples (6.0%)
6 (6.0%) high severe
variance introduced by outliers: 95.753%
variance is severely inflated by outliers

benchmarking numbers/Text/negative power/rational
mean: 1.069922 us, lb 1.066466 us, ub 1.076305 us, ci 0.950
std dev: 23.44179 ns, lb 15.08887 ns, ub 43.98265 ns, ci 0.950
found 3 outliers among 100 samples (3.0%)
2 (2.0%) high mild
1 (1.0%) high severe
variance introduced by outliers: 15.167%
variance is moderately inflated by outliers

benchmarking numbers/Text/negative power/scientific
mean: 1.741258 us, lb 1.734370 us, ub 1.749195 us, ci 0.950
std dev: 37.68357 ns, lb 32.72869 ns, ub 46.29251 ns, ci 0.950
found 1 outliers among 100 samples (1.0%)
variance introduced by outliers: 15.146%
variance is moderately inflated by outliers

benchmarking numbers/ByteString/no power/double
mean: 1.389954 us, lb 1.386567 us, ub 1.393604 us, ci 0.950
std dev: 18.13338 ns, lb 15.78126 ns, ub 21.17526 ns, ci 0.950
found 3 outliers among 100 samples (3.0%)
3 (3.0%) high mild
variance introduced by outliers: 6.550%
variance is slightly inflated by outliers

benchmarking numbers/ByteString/no power/number
mean: 1.455928 us, lb 1.451455 us, ub 1.460966 us, ci 0.950
std dev: 24.26540 ns, lb 20.84635 ns, ub 29.70448 ns, ci 0.950
found 4 outliers among 100 samples (4.0%)
4 (4.0%) high mild
variance introduced by outliers: 9.437%
variance is slightly inflated by outliers

benchmarking numbers/ByteString/no power/rational
mean: 522.5731 ns, lb 521.3363 ns, ub 523.8765 ns, ci 0.950
std dev: 6.495382 ns, lb 5.766371 ns, ub 7.378443 ns, ci 0.950

benchmarking numbers/ByteString/no power/scientific
mean: 994.6173 ns, lb 990.7924 ns, ub 999.3210 ns, ci 0.950
std dev: 21.67678 ns, lb 18.16483 ns, ub 27.46960 ns, ci 0.950
found 5 outliers among 100 samples (5.0%)
4 (4.0%) high mild
1 (1.0%) high severe
variance introduced by outliers: 15.158%
variance is moderately inflated by outliers

benchmarking numbers/ByteString/positive power/double
mean: 1.411828 us, lb 1.407454 us, ub 1.416960 us, ci 0.950
std dev: 24.27396 ns, lb 20.34750 ns, ub 30.54015 ns, ci 0.950
found 4 outliers among 100 samples (4.0%)
4 (4.0%) high mild
variance introduced by outliers: 10.360%
variance is moderately inflated by outliers

benchmarking numbers/ByteString/positive power/number
mean: 1.433854 us, lb 1.428346 us, ub 1.440225 us, ci 0.950
std dev: 30.24958 ns, lb 25.95767 ns, ub 35.31358 ns, ci 0.950
found 7 outliers among 100 samples (7.0%)
7 (7.0%) high mild
variance introduced by outliers: 14.210%
variance is moderately inflated by outliers

benchmarking numbers/ByteString/positive power/rational
mean: 626.1842 ns, lb 624.1383 ns, ub 628.5882 ns, ci 0.950
std dev: 11.43712 ns, lb 9.589302 ns, ub 13.95354 ns, ci 0.950
found 5 outliers among 100 samples (5.0%)
5 (5.0%) high mild
variance introduced by outliers: 11.326%
variance is moderately inflated by outliers

benchmarking numbers/ByteString/positive power/scientific
mean: 868.9857 ns, lb 865.5069 ns, ub 872.9627 ns, ci 0.950
std dev: 19.09100 ns, lb 16.45889 ns, ub 22.59966 ns, ci 0.950
found 5 outliers among 100 samples (5.0%)
5 (5.0%) high mild
variance introduced by outliers: 15.171%
variance is moderately inflated by outliers

benchmarking numbers/ByteString/negative power/double
mean: 1.487104 us, lb 1.469714 us, ub 1.530977 us, ci 0.950
std dev: 128.4095 ns, lb 30.39439 ns, ub 229.8438 ns, ci 0.950
found 7 outliers among 100 samples (7.0%)
5 (5.0%) high mild
2 (2.0%) high severe
variance introduced by outliers: 73.821%
variance is severely inflated by outliers

benchmarking numbers/ByteString/negative power/number
mean: 1.538987 us, lb 1.532906 us, ub 1.546600 us, ci 0.950
std dev: 34.59099 ns, lb 28.61052 ns, ub 46.39670 ns, ci 0.950
found 6 outliers among 100 samples (6.0%)
5 (5.0%) high mild
1 (1.0%) high severe
variance introduced by outliers: 16.106%
variance is moderately inflated by outliers

benchmarking numbers/ByteString/negative power/rational
mean: 675.4157 ns, lb 672.4198 ns, ub 679.3538 ns, ci 0.950
std dev: 17.50496 ns, lb 14.19622 ns, ub 25.68052 ns, ci 0.950
found 1 outliers among 100 samples (1.0%)
1 (1.0%) high severe
variance introduced by outliers: 19.974%
variance is moderately inflated by outliers

benchmarking numbers/ByteString/negative power/scientific
mean: 1.356450 us, lb 1.351215 us, ub 1.364934 us, ci 0.950
std dev: 33.69237 ns, lb 23.74270 ns, ub 58.98339 ns, ci 0.950
found 5 outliers among 100 samples (5.0%)
4 (4.0%) high mild
1 (1.0%) high severe
variance introduced by outliers: 18.987%
variance is moderately inflated by outliers
```

The `number` parser has worsened significantly because of:

```diff
- D (fromInteger c / 10 ^ negate e)
+ D (Sci.toRealFloat s)
```

However this change is needed for the following reasons:

* `fromInteger c / 10 ^ negate e` will more easily overflow
* `Sci.toRealFloat s` has DoS protection.

Additionally, we might want to deprecate the `number` parser and `Data.Attoparsec.Number` in favour of scientific.

The `double` parser has worsened a bit but that's because of the DoS protection. I'm not sure how to improve it.

Please do try to replicate these benchmarks.