Re: [ft-devel] Outline n_points are int16 so overflow is possible because missing check

[mpsuzuki]

Hi,

Sorry for my lated reply to your important suggestion.

On Thu, 25 Jun 2009 16:59:30 +0200 (CEST)
Werner LEMBERG <address@hidden> wrote:

>
>> I want to report bug in handling huge (in number of points) glyphs.
>> (I can provide such generated font on request, don't sending to list
>> as it has 1.2MB)
>
>Thanks for the report.  Please send this font to me.
>
>> If you create Type1 (could apply also to different types) font with
>> more than 32767 points in one glyph outline->n_points will wrap
>> around 16bits to -32768 in t1_builder_add_point and start corrupting
>> memory.

I think you pointed out an issue caused by the type
definition of `n_points' in include/freetype/ftimage.h:

  typedef struct  FT_Outline_
  {
    short       n_contours;      /* number of contours in glyph        */
    short       n_points;        /* number of points in the glyph      */

    FT_Vector*  points;          /* the outline's points               */
    char*       tags;            /* the points flags                   */
    short*      contours;        /* the contour end points             */

    int         flags;           /* outline masks                      */

  } FT_Outline;

As you can created a Type1 glyph description including 64k 
control points, future version of FT2 is expected to have
larger types for n_contours, n_points and contours.

I checked the font format specifications roughly and estimated
the maximum number of points.

Adobe Type1 CharStrings:
        According to "Adobe Type 1 Font Format", Charstring
        length for a single glyph is limited to 64k octets.
        The operators `hvcurveto' and `vhcurveto' take 4
        operands to add 3 points. Considering the requirement
        of `closepath' and `endchar', the possible maximum
        number of the points in a glyph would be estimated as
                ( ( 65535 - 2 ) x 3/5 ) = 39318
        It is greater than 0x7FFF.

Adobe Type2 CharStrings:
        According to Adobe TechNote 5177, Charstring length
        for a single glyph is limited to 64k octets, and
        the maximum stack depth is 48.
        `hlineto' and `vlineto' in Adobe Type2 Charstring
        draw a zig-zag line by a serie of steggered height
        and width, so short line segment can be coded by
        single operand. Thus, 1 operator and 47 operands
        can define 46 points. The estimated maximum number
        of the points in a glyph would be
                ( ( 65535 - 2 ) x 46/48 ) = 62790.
        It is greater than 0x7FFF.

TrueType:
        TrueType instruction permits to write a looping
        structure in a font program, so it is impossible to
        estimate the maximum number of the points by its
        syntax and the length of glyph description.

        In the header of an entry in `glyf' table, there
        is an array of the point indices that collects
        the ending point of each contours. The element of
        the array is declared as unsigned 16-bit. So, it
        might be reasonable to assume the maximum number
        of the points in a single glyph as 65535. Also
        the `maxp' table has the entries of the maximum
        number of the points for simple and composite glyphs,
        and their type is unsigned 16-bit. It is greater
        than 0x7FFF.

        However, some TrueType instructions (SRP0, SRP1,
        SRP2) take the point index as unsigned 32-bit.
        I'm not sure if TrueType bytecode interpreter
        should truncate 32-bit point index (as current
        FT2) or should return any error. I will ask it
        to ISO/IEC 14496-22 editors.

PFR:
        According to PFR 1.3 specification, PFR header
        has an entry to declare the maximum length of
        any (simple/composite) glyph, pfrHeader.gpsMaxSize,
        its type is unsigned 16-bit.
        To specify the points in PFR glyph description
        program, there are 3 ways: by unsigned 8-bit point
        index (the indexed points should be predefined in
        the header), by signed 16-bit absolute position,
        by signed 8-bit relative position.
        The operators `hvCurveTo' and `vhCurveTo' can add
        3 points by 4 octet operands. Considering the
        one octet for EndGlyph operator, the maximum number
        of points in PFR by can be estimated as:
                ( ( 65535 - 1 ) x 3 / 5 ) = 39320.
        It is greater than 0x7FFF.

That's all for existing supports of outline font formats in
FreeType2. It seems that "unsigned short" can cover.

BTW, the path construction of Adobe PostScript language
restricts the number of points to 1500 (so, PS Type3 font
has this limitation). It's far smaller than font description
languages in above. About SVG, yet I couldn't find such
clarified limitation.

>          IMHO check for this limitation needs to be added to
>> FT_GlyphLoader_CheckPoints function.

I agree. How do you think following patch?

diff --git a/include/freetype/ftimage.h b/include/freetype/ftimage.h
index 171f1b3..524d2e8 100644
--- a/include/freetype/ftimage.h
+++ b/include/freetype/ftimage.h
@@ -364,6 +364,9 @@ FT_BEGIN_HEADER
 
   } FT_Outline;
 
+#define FT_OUTLINE_CONTOURS_MAX SHRT_MAX /* must be synchronized to FT_Outline 
*/
+#define FT_OUTLINE_POINTS_MAX   SHRT_MAX /* must be synchronized to FT_Outline 
*/
+
 
   /*************************************************************************/
   /*                                                                       */

diff --git a/src/base/ftgloadr.c b/src/base/ftgloadr.c
index ab52621..ac0010d 100644
--- a/src/base/ftgloadr.c
+++ b/src/base/ftgloadr.c
@@ -218,6 +218,9 @@
     {
       new_max = FT_PAD_CEIL( new_max, 8 );
 
+      if ( new_max > FT_OUTLINE_POINTS_MAX )
+        return FT_Err_Array_Too_Large;
+
       if ( FT_RENEW_ARRAY( base->points, old_max, new_max ) ||
            FT_RENEW_ARRAY( base->tags,   old_max, new_max ) )
         goto Exit;
@@ -246,6 +249,10 @@
     if ( new_max > old_max )
     {
       new_max = FT_PAD_CEIL( new_max, 4 );
+
+      if ( new_max > FT_OUTLINE_CONTOURS_MAX )
+        return FT_Err_Array_Too_Large;
+
       if ( FT_RENEW_ARRAY( base->contours, old_max, new_max ) )
         goto Exit;
 


>>                                      But there could be another
>> problem with local overflow in:
>>
>> #define FT_GLYPHLOADER_CHECK_P( _loader, _count )                    \
>>    ( (_count) == 0 || (int)((_loader)->base.outline.n_points    +    \
>>                             (_loader)->current.outline.n_points +    \
>>                             (_count)) <= (int)(_loader)->max_points )
>>
>> In some cases sum could be also done in shorts then widened to int
>> and not detecting overflow, so it will not call
>> FT_GlyphLoader_CheckPoints.

I'm not sure the scenario you discussed is for 16-bit
systems, or a (possible-but-irregular) implementation 
of 32-bit system, but, at least, an overflow would be
overlooked on 16-bit systems.

I've checked the Embedded Linux Kernel System (ELKS,
16-bit kernel based on Linux) by Bruce's C compiler (bcc),

        (int) ( (short) 0x7FFF + (short) 0x7FFF ) < 0x7FFF

is true. On 32-bit Linux kernel with gcc, it is false.
Therfore, a cast to larger type before summation is
required. How do you think of following patch?


diff --git a/include/freetype/internal/ftgloadr.h 
b/include/freetype/internal/ftgloadr.h
index 548481a..588304b 100644
--- a/include/freetype/internal/ftgloadr.h
+++ b/include/freetype/internal/ftgloadr.h
@@ -121,15 +121,15 @@ FT_BEGIN_HEADER
                               FT_UInt         n_contours );
 
 
-#define FT_GLYPHLOADER_CHECK_P( _loader, _count )                    \
-   ( (_count) == 0 || (int)((_loader)->base.outline.n_points    +    \
-                            (_loader)->current.outline.n_points +    \
-                            (_count)) <= (int)(_loader)->max_points )
-
+#define FT_GLYPHLOADER_CHECK_P( _loader, _count )            \
+   ( (_count) == 0 || ((_loader)->base.outline.n_points    + \
+                       (_loader)->current.outline.n_points + \
+                       (unsigned long)(_count)) <= (_loader)->max_points )
+
-#define FT_GLYPHLOADER_CHECK_C( _loader, _count )                     \
-  ( (_count) == 0 || (int)((_loader)->base.outline.n_contours    +    \
-                           (_loader)->current.outline.n_contours +    \
-                           (_count)) <= (int)(_loader)->max_contours )
+#define FT_GLYPHLOADER_CHECK_C( _loader, _count )             \
+  ( (_count) == 0 || ((_loader)->base.outline.n_contours    + \
+                      (_loader)->current.outline.n_contours + \
+                      (unsigned long)(_count)) <= (_loader)->max_contours )
 
 #define FT_GLYPHLOADER_CHECK_POINTS( _loader, _points,_contours )      \
   ( ( FT_GLYPHLOADER_CHECK_P( _loader, _points )   &&                  \

I guess, casting `_count' to unsigned long is sufficient
to make C compilers to calculate both sides as unsigned
long.

>> Maybe better solution would be completely remove this limitation by
>> changing all these shorts to ints and actually increase speed on
>> most platforms (unfortunately - this would need to be done on many
>> places look at contours array).
>
>IIRC, Toshiya's fixes take care of this problem too.

I agree. Even if replacing by int is too much, replacing
by unsigned short is expected. I will check the impact of
the change. But, before all, I wish your comment for the
proposed overflow checks in above for quick fix.

Regards,
mpsuzuki