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

On Sun, Mar 9, 2014 at 1:15 AM, Xidorn Quan <quanxunzhen@gmail.com> wrote:
> 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.

The counter-style fallback algorithm is basically identical to the
existing font fallback algorithm, which suffers from the same
potential problem.  I don't think this needs to be addressed
specially; implementations are allowed to fail due to resource
constraints.

> 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.

Same deal here - the existing unicode-range descriptor on @font-face
suffers from the identical problem.

~TJ

Received on Monday, 10 March 2014 21:21:29 UTC