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

[Richard Wordingham]

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.