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

[Petr Kobalíček]

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? Is
HB_CLOSURE_MAX_STAGES
here to enforce hard limit?

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?

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

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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.freedesktop.org/archives/harfbuzz/attachments/20180726/6bde51ac/attachment.html>