bugThe FreeType Project - Bugs: bug #47114, Infinite loops in gray_render_line

 
 

You are not allowed to post comments on this tracker with your current authentication level.

bug #47114: Infinite loops in gray_render_line

Submitter:  None
Submitted:  Thu 11 Feb 2016 04:01:26 AM UTC
   
 
Severity:  3 - Normal Item Group:  Crash
Status:  Confirmed Privacy:  Public
Assigned to:  podtelez Open/Closed:  Open
Planned Release:  2.6.4

Jump to the original submission

Tue 15 Mar 2016 02:49:29 AM UTC, comment #31: 

I've responsibly reverted to the old implementation until I fix the overflow on line 969.

My gut feeling is that you'll find lines 1239,1247,1255,1256 next. Let's see.

Alexei Podtelezhnikov <podtelez>
Group Member
Mon 14 Mar 2016 06:50:54 PM UTC, comment #30: 

The 64-bit version does not reveal any bugs, but it does not
go much further than before.
It's hard for me to judge how more coverage is potentially possible here. Maybe you could improve the target function some more,
of maybe you could supply interesting samples.
attached is another coverage dump (from clang.llvm.org/docs/SanitizerCoverage.html)



(file #36636)

Kostya Serebryany <kcc>
Group Member
Sun 13 Mar 2016 11:35:46 AM UTC, comment #29: 

I can confirm this (it took me a while to compile FreeType in 32bit mode – my openSuSE box doesn't come with proper 32bit .pc files for pkgconfig, and it's a pain to compile HarfBuzz without them, so I disabled it).

All three problems occur in the new implementation of `gray_render_line', AFAICS.

Alexei?

Werner LEMBERG <wl>
Group administrator
Sun 13 Mar 2016 12:22:46 AM UTC, comment #28: 

That's only on 32-bit, btw.
64-bit running fine.

Kostya Serebryany <kcc>
Group Member
Sun 13 Mar 2016 12:11:44 AM UTC, comment #27: 

With the recent changes if first prints a bunch of int oevrflows,
like this:
src/smooth/ftgrays.c:969:35: runtime error: signed integer overflow: -52253144 * 172 cannot be represented in type 'long'
src/smooth/ftgrays.c:1003:46: runtime error: signed integer overflow: -52253144 * 256 cannot be represented in type 'long'

Then it hangs here:
    #5 0x8428ed3 in gray_set_cell src/smooth/ftgrays.c:626:19
    #6 0x8428ed3 in gray_render_line src/smooth/ftgrays.c:1028
    #7 0x8426acd in gray_line_to src/smooth/ftgrays.c:1306:5
    #8 0x81d6cd3 in FT_Outline_Decompose src/base/ftoutln.c:165:21
    #9 0x842580d in gray_convert_glyph_inner src/smooth/ftgrays.c:1903:15
    #10 0x842154c in gray_convert_glyph src/smooth/ftgrays.c:2006:17
    #11 0x842154c in gray_raster_render src/smooth/ftgrays.c:2141
    #12 0x81dc124 in FT_Outline_Render src/base/ftoutln.c:646:15
    #13 0x81dc9c0 in FT_Outline_Get_Bitmap src/base/ftoutln.c:687:12
    #14 0x816d218 in LLVMFuzzerTestOneInput

Example input (in base64):
UyFU/yJMIQC2JyoAJiEn/ytU/ABNIScAIbUnKiIl

Kostya Serebryany <kcc>
Group Member
Sat 12 Mar 2016 10:49:45 PM UTC, comment #26: 

Thanks for the explanations.

I've slightly modified `rasterfuzzer.cc' to get more coverage, please test.

Werner LEMBERG <wl>
Group administrator
Sat 12 Mar 2016 07:30:35 AM UTC, comment #25: 

(that's experimental coverage report, we are still trying to figure out the UI part).

Green indicates the beginning of a covered basic block.
Red -- non covered.
Yellow -- an edge (comparison) that is always either true or false.

So, the most interesting here are red lines in the functions that
have green lines -- we don't execute those lines.

Kostya Serebryany <kcc>
Group Member
Sat 12 Mar 2016 07:23:22 AM UTC, comment #24: 

Thanks.  However, I have difficulties to understand the explanations.

What do the colors green, red, and yellow indicate?  This isn't documented at all in the clang link...

Werner LEMBERG <wl>
Group administrator
Fri 11 Mar 2016 12:09:09 AM UTC, comment #23: 

The fuzzer stops producing interesting coverage almost instantly,
both on 64- and 32-bit build.

I've attached a coverage report (see http://clang.llvm.org/docs/SanitizerCoverage.html#sancov-tool).
Maybe you could tell what's missing.

(file #36600)

Kostya Serebryany <kcc>
Group Member
Mon 07 Mar 2016 03:44:10 PM UTC, comment #22: 

There are plenty of dot and cross products to overflow even with the limited outline dimensions on 32-bit platforms. Please find those.

A reasonable input size is about 200 bytes. Going larger is the same as repeating.

Alexei Podtelezhnikov <podtelez>
Group Member
Mon 07 Mar 2016 07:37:49 AM UTC, comment #21: 

Well, rasterfuzzer.cc needs to be expanded; maybe Alexei can work on this – it is intentionally very simple, without providing big code coverage.  It was just meant as a starter to check the most serious overflows in both the B/W and gray rasterizer.

The expected input size is basically irrelevant; the input data simply gets reinterpreted as a points array.

For the moment, it is probably sufficient to run the fuzzer manually for a few minutes :-)

Werner LEMBERG <wl>
Group administrator
Mon 07 Mar 2016 07:20:22 AM UTC, comment #20: 

From the first quick run the target looks boring -- the coverage stops growing almost instantly.
- How much different logic is expected there?
- Do you have any sample inputs?
- what is the expected sizes of the inputs?

(Will make more experiments in ~ 1 week).

Kostya Serebryany <kcc>
Group Member
Mon 07 Mar 2016 06:46:11 AM UTC, comment #19: 

Looks good, thanks!   With some quick tests, I wasn't able to trigger the sanitizer running `rasterfuzzer.cc'.

Kostya, Ben, it seems that you could now start using this file :-)

I'm now closing this issue.

Werner LEMBERG <wl>
Group administrator
Mon 07 Mar 2016 05:03:34 AM UTC, comment #18: 

Let's see how things improve after this commit.

Alexei Podtelezhnikov <podtelez>
Group Member
Wed 02 Mar 2016 08:17:49 AM UTC, comment #17: 

Sounds reasonable.  Will you have a look?

Werner LEMBERG <wl>
Group administrator
Tue 01 Mar 2016 02:51:32 PM UTC, comment #16: 

We have a realistic limit onthe bitmaps that we produce, which is 32767x32767 = 1Gb. So I suggest that we outright reject outlines that exceed ±2097088 (in 26.6 fixed point) in FT_Ouline_Get_Bitmap. We are talking about 16 inch letters on 2000 dpi printers. I think this is reasonable and should cover the bulk of the overflows. Perhaps there are other function that need this limit.

Then we can look at the remaining overflows more carefully.


Alexei Podtelezhnikov <podtelez>
Group Member
Tue 01 Mar 2016 08:44:46 AM UTC, comment #15: 

Thanks for the input file.  I've made it more C++ (please check!) and added it to the ftfuzzer directory in FreeType; it tests both the gray and mono rasterizers.  Later on it should be refined, e.g., by constructing more than a single outline, having a larger target buffer, etc.

I can easily reproduce the overflow and shift errors by using an arbitrary binary directory as input (attached is a sample file); however, I don't have time currently to work on this issue.

Alexei, can you afford some time for this issue?

I'm reopening the issue.

(file #36517)

Werner LEMBERG <wl>
Group administrator
Tue 01 Mar 2016 01:51:53 AM UTC, comment #14: 

I've made a quick-n-dirty fuzz target for FT_Outline_Get_Bitmap
(attached) and indeed it hangs almost instantly.

    #5 0x70e083 in gray_set_cell src/smooth/ftgrays.c:634:10
    #6 0x70e083 in gray_render_line src/smooth/ftgrays.c:1028
    #7 0x70c7a3 in gray_line_to src/smooth/ftgrays.c:1306:5
    #8 0x539c06 in FT_Outline_Decompose src/base/ftoutln.c:165:21
    #9 0x70baf7 in gray_convert_glyph_inner src/smooth/ftgrays.c:1902:15
    #10 0x708fc3 in gray_convert_glyph src/smooth/ftgrays.c:2005:17
    #11 0x708fc3 in gray_raster_render src/smooth/ftgrays.c:2140
    #12 0x53d49b in FT_Outline_Render src/base/ftoutln.c:640:15
    #13 0x53d49b in FT_Outline_Get_Bitmap src/base/ftoutln.c:681
    #14 0x4e4b7d in LLVMFuzzerTestOneInput


ubsan prints lots of stuff:
src/smooth/ftgrays.c:1291:9: runtime error: left shift of negative value -8867864493558781852
src/smooth/ftgrays.c:1292:9: runtime error: left shift of negative value -693208218122896854
src/smooth/ftgrays.c:1306:32: runtime error: left shift of 7216742023680857627 by 2 places cannot be represented in type 'FT_Pos' (aka 'long')
src/smooth/ftgrays.c:1306:50: runtime error: left shift of negative value -7482078255484648629
src/smooth/ftgrays.c:931:15: runtime error: signed integer overflow: -8026520052695672724 - 1422030173183975824 cannot be represented in type 'long'
src/smooth/ftgrays.c:932:15: runtime error: signed integer overflow: 6965175125480508716 - -2772832872491587416 cannot be represented in type 'long'
src/smooth/ftgrays.c:935:19: runtime error: left shift of negative value -10831378408170264
src/smooth/ftgrays.c:969:24: runtime error: signed integer overflow: 8998193847829903068 * 168 cannot be represented in type 'long'
src/smooth/ftgrays.c:969:35: runtime error: signed integer overflow: -8708736075737455484 * 144 cannot be represented in type 'long'
src/smooth/ftgrays.c:980:29: runtime error: signed integer overflow: 8998193847829903068 * 256 cannot be represented in type 'long'
src/smooth/ftgrays.c:984:22: runtime error: signed integer overflow: -8708736075737455484 * 256 cannot be represented in type 'long'
src/smooth/ftgrays.c:991:29: runtime error: signed integer overflow: 8998193847829903068 * 256 cannot be represented in type 'long'
src/smooth/ftgrays.c:992:29: runtime error: signed integer overflow: 8998193847829903068 * 256 cannot be represented in type 'long'
src/smooth/ftgrays.c:992:46: runtime error: signed integer overflow: -8708736075737455484 * 256 cannot be represented in type 'long'
src/smooth/ftgrays.c:994:22: runtime error: signed integer overflow: 8998193847829903068 * 256 cannot be represented in type 'long'

Some of these may be causing the hangs.

(file #36516)

Kostya Serebryany <kcc>
Group Member
Mon 29 Feb 2016 11:19:54 PM UTC, comment #13: 

And yes, I agree this is very good idea!

Kostya Serebryany <kcc>
Group Member
Mon 29 Feb 2016 11:01:04 PM UTC, comment #12: 

You can go with a command line switch or with a separate file.
I usually prefer separate files -- this makes matters simpler.
Once you have the target file in git I'll be able to hook it to
the bot (allow me 2-3 days). But please test the setting locally,
the libFuzzer workflow is pretty simple (llvm.org/docs/LibFuzzer.html).

Kostya Serebryany <kcc>
Group Member
Sat 27 Feb 2016 09:38:01 AM UTC, comment #11: 

A very good idea IMHO!  I wonder how this could be implemented: More code to `ftfuzzer.cc', to be controlled with command line switches?  A separate `ftrenderfuzzer.cc' file?

Ben, what do you suggest?

Werner LEMBERG <wl>
Group administrator
Thu 25 Feb 2016 01:58:04 PM UTC, comment #10: 

I wonder if this code can be used in the fuzzer, by-passing all the font parsing. This way we could potentially stress test both smooth and b/w rasterizer separately. Werner, please comment.

Alexei Podtelezhnikov <podtelez>
Group Member
Wed 24 Feb 2016 12:19:13 AM UTC, comment #9: 

Attached is some C source that reproduces the infinite loop by calling FT_Outline_Get_Bitmap rather than an internal API.

The supplied points contain some large values. These large values were the result of applying a transformation matrix to a glyph outline where the matrix had large values that were the result of the overflow in Skia.

(file #36447)

David lattimore <dml>
Tue 23 Feb 2016 10:25:35 PM UTC, comment #8: 
David lattimore <dml>
Tue 23 Feb 2016 03:36:38 AM UTC, comment #7: 

Thanks for that. I'm still investigating, but at this stage it looks like another integer overflow. This time in Skia.

David lattimore <dml>
Wed 17 Feb 2016 03:39:40 AM UTC, comment #6: 

See this commit. I am still curious to see what it takes to generate 56,000-point lines. Please provide the test case eventually.

Alexei Podtelezhnikov <podtelez>
Group Member
Fri 12 Feb 2016 02:40:58 PM UTC, comment #5: 

Never mind. You have 64-bit long and 32-bit int, much like I do.

Alexei Podtelezhnikov <podtelez>
Group Member
Fri 12 Feb 2016 02:24:57 PM UTC, comment #4: 

It is very possible that there are more than one bug in this report. I will make TArea unconditionally long, but still I am curious so please bear with me. To get int there, if PIXEL_BITS is 8, you must have UINT_MAX different from 0xFFFFU, i.e. you int is not 32 bits. Yet you say that it overflows and your long is 64 bits. What kind of environment is that?

What are your UINT_MAX, ULONG_MAX, sizeof(int), sizeof(long)?

Alexei Podtelezhnikov <podtelez>
Group Member
Fri 12 Feb 2016 12:02:46 AM UTC, comment #3: 

Sorry about the anonymous post. I didn't think to create an account until after I'd posted.

I haven't changed PIXEL_BITS from it's default. I'm not sure why there's such a long line segment. Possibly a bug in Skia, or my code. Or it's also possible it's just the input document supplied by the user that specified a large value. But I don't have access to that document.

From one of the Skia stack frames, it looks like it's trying to produce a bitmap for a glyph that is 1x1. At least the bitmap passed to FT_Outline_Get_Bitmap is 1x1. My guess would be that there's another integer overflow happening somewhere. Although quite how we overflow with such a small bitmap, I don't know. Perhaps if there's code that's doing fixed-point division by a value very close to 0, that could cause an overflow. Just guesses.

In case it's of interest, here's a backtrace of how it got to gray_render_line:

gray_render_line
gray_line_to
FT_Outline_Decompose
gray_convert_glyph_inner
gray_convert_glyph
gray_raster_render
FT_Outline_Render.part.11
FT_Outline_Get_Bitmap
SkScalerContext_FreeType_Base::generateGlyphImage()
SkScalerContext_FreeType::generateImage()
SkScalerContext::getImage()
SkGlyphCache::findImage()
...
SkDraw::drawPosText()
SkCanvas::onDrawPosTextH()

David lattimore <dml>
Thu 11 Feb 2016 08:48:36 PM UTC, comment #2: 

The easy and correct solution is to just use long for TArea as suggested, because TPos and TCoord are not shy about it. I wonder why int was even considered for TArea.

Regrdless, that is quite a line segment of some 53 thousand pixels. Wow! Or somebody changed PIXEL_BITS. What was the motivation? Hopefully, the anonymous reporter will check back.


Alexei Podtelezhnikov <podtelez>
Group Member
Thu 11 Feb 2016 06:20:59 AM UTC, comment #1: 

Alexei, please have a look!

Werner LEMBERG <wl>
Group administrator
Thu 11 Feb 2016 04:01:26 AM UTC, original submission:  

The function gray_render_line can go into an infinite loop. I've observed this in a production system that is using FreeType. I've been somewhat restricted in the information I've been able to get from the core files where this has happened since gcc optimizes out most of the variables, so they don't show up in gdb. So I don't know what glyph it's trying to draw nor at what scale. I was however able to get some of the arguments that were passed to gray_render_line and was able to reproduce the problem by passing these same values.

If ras.x = 0, ras.y = 0 and I pass to_x = 14418112 and to_y = 14418032, I get the infinite loop.

The code requires ex1==ex2 and ey1==ey2 concurrently for the loop to terminate. The following is a printout of these values for some relevant iterations of the loop.

prod=-1757343744 ex1=56319 ey1=56318 ex2=56320 ey2=56320
prod=1933672448 ex1=56320 ey1=56318 ex2=56320 ey2=56320
prod=-1757364224 1=56320 ey1=56319 ex2=56320 ey2=56320
prod=1933651968 ex1=56321 ey1=56319 ex2=56320 ey2=56320
prod=-1757384704 ex1=56321 ey1=56320 ex2=56320 ey2=56320
prod=1933631488 ex1=56322 ey1=56320 ex2=56320 ey2=56320
prod=-1757405184 ex1=56322 ey1=56321 ex2=56320 ey2=56320

As you can see, ex1 reached ex2 and then passed it just before ey1 reached ey2.

This appears to be due to an integer overflow in the variable prod which is only 32 bits whereas most of the other variables are long. If I change prod to a long, the function terminates normally.

Hopefully that's enough to go off. Sorry I don't have a repro using a public API.

Anonymous

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attached Files
file #36636:  raster-cov-2.html added by kcc (1MiB - text/html)
file #36600:  raster-cov.html added by kcc (1MiB - text/html)
file #36516:  ft_overflow.c added by kcc (1KiB - text/x-csrc)
file #36447:  ft_overflow.c added by dml (1008B - text/x-csrc)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by kcc (Posted a comment)
  • -email is unavailable- added by podtelez
  • -email is unavailable- added by dml (Posted a comment)
  • -email is unavailable- added by podtelez (Posted a comment)
  • -email is unavailable- added by wl (Posted a comment)
  • -email is unavailable- added by dml
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

     

    Follow 20 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2016-03-14 kcc Attached File- Added raster-cov-2.html, #36636
    2016-03-13 wl StatusFixed Confirmed
        Open/ClosedClosed Open
        SummaryInfinite loop in gray_render_line Infinite loops in gray_render_line
    2016-03-11 kcc Attached File- Added raster-cov.html, #36600
    2016-03-07 wl StatusConfirmed Fixed
        Open/ClosedOpen Closed
    2016-03-01 wl Attached File- Added 2778 - embedded font without hmtx table.pdf, #36517
        StatusFixed Confirmed
        Open/ClosedClosed Open
    2016-03-01 kcc Attached File- Added ft_overflow.c, #36516
    2016-02-25 podtelez Carbon-Copy- Added -email is unavailable-
    2016-02-24 dml Attached File- Added ft_overflow.c, #36447
    2016-02-17 podtelez StatusNone Fixed
        Open/ClosedOpen Closed
        Planned ReleaseNone 2.6.4
    2016-02-11 wl Assigned toNone podtelez
    2016-02-11 dml Carbon-Copy- Added dml
    2016-02-11 dml Carbon-CopyRemoved -email is unavailable- -
    2016-02-11 dml Carbon-Copy- Added -email is unavailable-

    Back to the top

    Powered by Savane 3.13-cf05.
    Corresponding source code