Very low compression speed of optimal mode on repetitive data

[KirillKryukov]

blzpack's "optimal" mode slows down ~ 1000 times when used for compressing repetitive data.

Posted as separate issue, because:

1. I found how to trigger the slowdown. Just use repetitive data, e.g., a long sequence of the same byte.

2. This can be used to construct denial-of-service attack on a system that uses BriefLZ's "optimal" mode.

Previous issue #11 was about unpredictable slowdown, this issue is about predictable and reliable slowdown on repetitive data, which can be used to attack systems depending on BriefLZ.

This chart shows compression speed of different modes of blzpack, using repetitive (mainly single byte repeat) data of varying sizes (data size shown on the x-axis):

The one dropping to the bottom is the "optimal" mode.

The main issues is a combination of these factors:

1. A user using blzpack may have no idea that this slowdown is possible.
2. There is a tendency among compressor users to use the strongest level available, in this case "optimal".
3. Slowdown is an order of 1000 times compared to expected speed, which is indistinguishable from being frozen (on sufficiently large data, within realistic waiting time). Hence the potential to use it as DOS attack.
4. Slowdown happens on particularly constructed data, which is different from normally used data. Therefore the user may be unaware of the issue after testing blzpack on his data.

Some of the the possible solutions:

1. Remove the "optimal" mode entirely.
2. Fix the "optimal" mode to remove slowdown (though it might become not optimal anymore).
3. Document the potential DOS-attack in the readme. (a half-measure, because users may still miss this warning).

This is not meant in any negative way, and otherwise I enjoy blzpack, so just I want to help making it safer for potential users. Thanks!

[jibsen]

Sorry about the delay.

I largely agree with your concerns about the worst-case behavior of the optimal level. But I feel it provides both an interesting data point and a useful option for off-line compression, so I would like to keep it available.

In retrospect I could have made it a separate function in the API to distinguish it more.

Fix the "optimal" mode to remove slowdown (though it might become not optimal anymore).

This is essentially what level 9 does; it is the same algorithm, but limited to avoid the worst-case behavior.

This is not meant in any negative way, and otherwise I enjoy blzpack, so just I want to help making it safer for potential users. Thanks!

I am happy you raised the issue and welcome the discussion!