[HarfBuzz] HB_CLOSURE_MAX_STAGES (was: harfbuzz: Branch 'master')

[Behdad Esfahbod]

On Thu, Jul 26, 2018 at 7:39 AM, Petr Kobalíček <kobalicek.petr at gmail.com>
wrote:

> I initially thought that this was to prevent an infinite recursion of
> contextual lookups.
>
> I'm working with OpenType myself (not harfbuzz) and this is something that
> I think is not clarified in the specification. Can a contextual
> substitution invoke another contextual substitution and recurse?
>

Yes it can.



> Is HB_CLOSURE_MAX_STAGES here to enforce hard limit?
>

No.  But neighboring HB_MAX_NESTING_LEVEL does that.  Currently set to 6.

The font Noto Nastaliq Urdu uses nested recursive lookups extensively.


> To write a bit more about it. I thought that contextual lookup has
> basically 3 parts:
>
>   - backtrack sequence
>   - input sequence
>   - lookahead sequence
>
> I would imagine that "input" sequence would be pretty short, like one
> character most of the time, and the lookup applied if we have a match would
> only consist of "input sequence". So the question is, does it make sense to
> apply another contextual lookup to just the isolated "input sequence" in
> case we had a match?
>

Yes.


> Do you guys here know any material that would further explain how such
> cases of GSUB should be correctly handled?
>

How HarfBuzz does it is my best understanding of how it should be done (not
necessarily how Microsoft does it, but compatible-enough).


> Best,
> Petr.
>
>
> On Thu, Jul 26, 2018 at 9:06 AM, Richard Wordingham <
> richard.wordingham at ntlworld.com> wrote:
>
>> On Tue, 24 Jul 2018 16:31:50 +0000 (UTC)
>> behdad at kemper.freedesktop.org (Behdad Esfahbod) wrote:
>>
>> The following change bothers me:
>>
>> >  src/hb-ot-layout-common-private.hh |    7 +++++++
>> >  src/hb-ot-layout.cc                |    5 ++++-
>> >  2 files changed, 11 insertions(+), 1 deletion(-)
>> >
>> > New commits:
>> > commit 85646fdadb2f102333485e07425361795b4e0412
>> > Author: Garret Rieger <grieger at google.com>
>> > Date:   Mon Jul 23 15:37:18 2018 -0700
>> >
>> >     [subset] Limit the iterations of the closure algorithm.
>> >     Prevents O(n^2) run times.
>> >
>> > diff --git a/src/hb-ot-layout-common-private.hh
>> > b/src/hb-ot-layout-common-private.hh index 21caf9e9..7ff0dbeb 100644
>> > --- a/src/hb-ot-layout-common-private.hh
>> > +++ b/src/hb-ot-layout-common-private.hh
>> > @@ -41,6 +41,13 @@
>> >  #ifndef HB_MAX_CONTEXT_LENGTH
>> >  #define HB_MAX_CONTEXT_LENGTH        64
>> >  #endif
>> > +#ifndef HB_CLOSURE_MAX_STAGES
>> > +/*
>> > + * The maximum number of times a lookup can be applied during
>> > shaping.
>> > + * Used to limit the number of iterations of the closure algorithm.
>> > + */
>> > +#define HB_CLOSURE_MAX_STAGES        8
>> > +#endif
>>
>> I presume that this is intended to prevent a denial of service attack,
>> at the cost of trashing a subset font.
>>
>> In non-malicious use, how is the victim supposed to detect that and
>> then how he needs to change HarfBuzz or his font?  Does he have to read
>> all the text using the subset font simply to detect a problem?  How
>> does one test that a font does not hit this limit?  Does one have to
>> iterate over the power set of the supported characters for each
>> script?  That's O(2^n) - impossible to do!
>>
>> The description of HB_CLOSURE_MAX_STAGES is completely wrong.  I was
>> initially alarmed because I have lookups that are invoked in more than
>> 8 places in substitution subtables.  A more accurate, but still not
>> perfect, definition, would be 'the maximum number of times lookup can
>> change a bit of text'.
>>
>> A limit of 8 does not strike me as obviously generous.  Some contextual
>> changes can ripple through a string, and I would not be totally
>> surprised to find that 8+1 or more lookups act on some irreducible
>> strings in my Da Lekh font.  The consolations are that there are
>> probably shorter paths to create the resultant glyphs from the input
>> set, and one iteration will often process several lookups in the
>> correct sequence.
>>
>> Richard.
>> _______________________________________________
>> HarfBuzz mailing list
>> HarfBuzz at lists.freedesktop.org
>> https://lists.freedesktop.org/mailman/listinfo/harfbuzz
>>
>
>
> _______________________________________________
> HarfBuzz mailing list
> HarfBuzz at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/harfbuzz
>
>


-- 
behdad
http://behdad.org/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.freedesktop.org/archives/harfbuzz/attachments/20180730/61a28baf/attachment-0001.html>