[css-counter-styles] fallback depth should be limited

Hi,

I find that fallback may cause a significant performance issue when a
long chain is applied. If the length of fallback chain is M while
there is N numbers to be displayed, the worst computation time is at
least O(M * N). (In fact, the time for checking range has to be taken
into account as well, which is at least O(log R) in which R is the
number of ranges.) As a result, if an attacker construct a fallback
chain consists of 2,000 counter styles, and put 2,000 numbers which do
not fall into range of any of them, it will take the useragent several
seconds to figure out the final result.

Though it is possible to cache the corresponding counter style for
each range, the situation is more complex since fallback happens not
only when the ordinal is out of range, but also in some other cases,
such as too long representation for symbolic or additive counter
styles, which is hard to identify before actually doing the
computation for a specific ordinal.

For these reasons, I propose that, it should be allowed for impls to
limit the maximum depth of fallback chain to, for example, 5 or 10.
When the limit is exceeded, impl should be allowed to force a fallback
to decimal. Generally speaking, authors will not use such a long
fallback chain, therefore it is safe to apply this limitation.

In addition, it should also be noted in the spec that, the range-check
algorithm has to be implemented in O(log R), or it will be another
vulnerability of performance. Perhaps you would like to allow impls to
limit the number of ranges instead.

Regards,
Xidorn Quan

Received on Sunday, 9 March 2014 09:16:28 UTC