Bug 63290 – Stack overflow with enormous SVG filter

• Component: SVG
• Status: RESOLVED FIXED

[Tim Horton]

There's a recursive call in RenderSVGResourceFilterPrimitive::determineFilterPrimitiveSubregion which blows the stack when it encounters an SVG filter with many, many chained operations.

Open the attached SVG in a filter-enabled build of Safari, and witness a crash.

There's a truncated backtrace in a comment at the bottom of the SVG.

[Tim Horton]

Created attachment 98403 [details]
Repro

[Lucas Forschler]

<rdar://problem/9666703>

[Justin Schuh]

Any reason this is tagged as a security bug? It's just stack exhaustion, which means the process terminates on the exception with no possibility of exploit.

[Tim Horton]

(In reply to comment #3)
> Any reason this is tagged as a security bug? It's just stack exhaustion, which means the process terminates on the exception with no possibility of exploit.

No particular reason; I know little about what is actually exploitable (or at least, I'm still gaining a sense of this) and was told "better to be safe than sorry", so I went for it. If it's not, then there's no reason not to switch it out to the SVG component instead.

[Justin Schuh]

No problem. I'll just shuffle the flags then.

[Said Abou-Hallawa]

The same cash happens also in FireFox.

The SVG looks like this:

<svg xmlns="http://www.w3.org/2000/svg">
<defs>
    <filter id="asdf">
    <feGaussianBlur stdDeviation="1.0" />
    <feGaussianBlur stdDeviation="1.0" />

    ... many the same feGaussianBlur FilterEffect

    <feGaussianBlur stdDeviation="1.0" />
    </filter>
</defs>
<rect x="10px" y="10px" width="20px" height="20px" filter="url(#asdf)"/>
</svg>

Since non of the feGaussianBlur defines its input FilterEffect, the previous feGaussianBlur is considered to be the input expect for the first one, the SourceGraphic is considered to be the input.  So basically, a very deep tree is built for this bogus svg which acts exactly like a linked list in this case.

I tried fixing this bug by cutting off the recursion in the function RenderSVGResourceFilterPrimitive::determineFilterPrimitiveSubregion() which fixes the crash.  But I got another crash in FilterEffect::apply() because it has the same kind of recursion and it might need similar cut off.

I think the cleanest way to fix this bug is cut off creating the FilterEffect tree from the the beginning when the svg is loaded instead of creating a very deep tree and then try to cut off traversing it in many places.

[Dean Jackson]

(In reply to comment #6)
> I tried fixing this bug by cutting off the recursion in the function RenderSVGResourceFilterPrimitive::determineFilterPrimitiveSubregion() which fixes the crash.  But I got another crash in FilterEffect::apply() because it has the same kind of recursion and it might need similar cut off.
> 
> I think the cleanest way to fix this bug is cut off creating the FilterEffect tree from the the beginning when the svg is loaded instead of creating a very deep tree and then try to cut off traversing it in many places.

I think you're right, as long as I understand what you're suggesting :)

We should have a limit on the depth of our graph (or length of the chain in this case). We actually have them in other places, like the maximum amount of the blur radius.

So, not creating the FilterEffects and just marking the Filter as invalid is fine with me. What we can't do is remove the actual filter elements from the tree, because they still need to be visible in the DOM even if they are broken.

[Dean Jackson]

Also, I think we can make the limit pretty small for now. 100 links?

I can imagine a pretty complicated graph, but wide rather than deep. Anything deeper than 100 is getting pretty intense.

(I'm sure this comment will come back to haunt me when we're replicating huge Photoshop files with lots of layers and effects)

[Dirk Schulze]

(In reply to comment #8)
> Also, I think we can make the limit pretty small for now. 100 links?
> 
> I can imagine a pretty complicated graph, but wide rather than deep. Anything deeper than 100 is getting pretty intense.
> 
> (I'm sure this comment will come back to haunt me when we're replicating huge Photoshop files with lots of layers and effects)

Just a correction to the text above, there is no recursion, it is just a deep tree. As Dean says, you can have the same issue with a wide tree. We create the dependency tree immediately, so we should be able to scan how many filter primitives are in the tree and erase it if it has too many. Some operations probably should have a weight.

[Said Abou-Hallawa]

Created attachment 238488 [details]
Patch

[Said Abou-Hallawa]

Created attachment 238506 [details]
Patch

[Dirk Schulze]

Ok, the patch is too big for the review tool. Likely too big for commit bot as well. I would suggest that you generate the filter chain with JS instead of checking in such a huge test.

I wonder if you don't want to return early in the SVGFilterBuilder already. IMO, in most cases the filter doesn't do anything meaningful at all if you limit the size. So why not just check the size of the map all filter effects are stored to and clear it if there are too many filter effects?

[Dean Jackson]

(In reply to comment #12)
> Ok, the patch is too big for the review tool. Likely too big for commit bot as well. I would suggest that you generate the filter chain with JS instead of checking in such a huge test.
> 
> I wonder if you don't want to return early in the SVGFilterBuilder already. IMO, in most cases the filter doesn't do anything meaningful at all if you limit the size. So why not just check the size of the map all filter effects are stored to and clear it if there are too many filter effects?

I agree with Dirk on both points here.

[Said Abou-Hallawa]

Created attachment 238583 [details]
Patch

[Said Abou-Hallawa]

I did what Dirk and Dean suggested.

-- I return early from RenderSVGResourceFilter::buildPrimitives() if the number of children is greater than 10000 nodes.  There is no point in creating such FilterEffect in this case.  Checking the number of children nodes rather than checking the height of the FilterEffect tree saves us from doing two things. (1) traversing the FilterEffect tree till some maximum depth. (2) avoiding building a tree which is most likely to have no use at the end.

-- The test file was changed to be dynamically include many FilterEffect filters in the SVG.

[Dirk Schulze]

Comment on attachment 238583 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=238583&action=review

> Source/WebCore/rendering/svg/RenderSVGResourceFilter.cpp:81
> +    const unsigned maxCountChildNdes = 10000;
> +    if (filterElement().countChildNodes() >= maxCountChildNdes)
> +        return nullptr;

You could add 100,000 nodes and none contributes to the actual filter chain. The actual filter tree is build in RenderSVGResourceFilter::buildPrimitives. After running the for loop, we know which effects are connected with each other. Currently we don't clean up the builder map though. Only way to know is to go through builder->lastEffect and count the effects recursively after running RenderSVGResourceFilter::buildPrimitives. A trivial way (probably not the best way) is to add a method to FilterEffects that gets a number, increases the number and calls all child filter effects with the same method and you get an actual number at the end.

Out of curiosity, why did you chose 10k nodes? IMO it could be 500 or less. After all, most filter effects causes a significant amount of computing cycles on their own.

> LayoutTests/ChangeLog:12
> +        * svg/filters/svg-deeply-nested-crash-expected.txt: Added.
> +        * svg/filters/svg-deeply-nested-crash.html: Added.

Test looks good to me.

[Brent Fulgham]

Comment on attachment 238583 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=238583&action=review

>> Source/WebCore/rendering/svg/RenderSVGResourceFilter.cpp:81
>> +        return nullptr;
> 
> You could add 100,000 nodes and none contributes to the actual filter chain. The actual filter tree is build in RenderSVGResourceFilter::buildPrimitives. After running the for loop, we know which effects are connected with each other. Currently we don't clean up the builder map though. Only way to know is to go through builder->lastEffect and count the effects recursively after running RenderSVGResourceFilter::buildPrimitives. A trivial way (probably not the best way) is to add a method to FilterEffects that gets a number, increases the number and calls all child filter effects with the same method and you get an actual number at the end.
> 
> Out of curiosity, why did you chose 10k nodes? IMO it could be 500 or less. After all, most filter effects causes a significant amount of computing cycles on their own.

It sounds like your concern is that this arbitrary cutoff here will needlessly prevent building the filter chain if the SVG document has thousands of nodes, but only a small number of filter-related nodes. Do I understand what you are saying?

As for the second section that suggests traversing the filter elements and building the chain before calculating the node count (or depth): won't we be back to the same problem where we exceed stack depth? Or are you suggesting keeping a running count of filter effect depth and breaking out early when we determine we've hit our limit?

[Said Abou-Hallawa]

Created attachment 238614 [details]
Patch

[Said Abou-Hallawa]

Created attachment 238630 [details]
Patch

[Dirk Schulze]

Comment on attachment 238630 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=238630&action=review

Looks good. Just some smaller snippets.

> Source/WebCore/platform/graphics/filters/FilterEffect.cpp:113
> +        depth = std::max(depth, in->depthOfEffectInputs());

Just a little misunderstanding I suppose. Not the depth matters, but the amount of effects matters. So just sum up all effects.

> Source/WebCore/rendering/svg/RenderSVGResourceFilter.h:90
> +    const unsigned s_maxCountOfInputEffects = 200; // maximum number of input effects regardless whether they are connected to a filter's lastEffect or not

Please use sentences as comments with periods. Move the comment a line up before the constant. Also, can't it be static constant? You already use s_.

[Said Abou-Hallawa]

(In reply to comment #20)
> (From update of attachment 238630 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=238630&action=review
> 
> Looks good. Just some smaller snippets.
> 
> > Source/WebCore/platform/graphics/filters/FilterEffect.cpp:113
> > +        depth = std::max(depth, in->depthOfEffectInputs());
> 
> Just a little misunderstanding I suppose. Not the depth matters, but the amount of effects matters. So just sum up all effects.
I am not sure I understand your point here.  Summing up all the effects will get us the total number of effects in the filter tree.  But we already have a cut off condition on the total number of effects in the filter map to be < 200.  Why do we need to limit the number of the used effects by the filter to be < 100?  I thought we care about the depth because it represents how much complex the filter composition will be.  But the total number of effects used by the filter does not reveal this information.
> 
> > Source/WebCore/rendering/svg/RenderSVGResourceFilter.h:90
> > +    const unsigned s_maxCountOfInputEffects = 200; // maximum number of input effects regardless whether they are connected to a filter's lastEffect or not
> 
> Please use sentences as comments with periods. Move the comment a line up before the constant. Also, can't it be static constant? You already use s_.

[Dean Jackson]

Comment on attachment 238630 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=238630&action=review

>>> Source/WebCore/platform/graphics/filters/FilterEffect.cpp:113
>>> +        depth = std::max(depth, in->depthOfEffectInputs());
>> 
>> Just a little misunderstanding I suppose. Not the depth matters, but the amount of effects matters. So just sum up all effects.
> 
> I am not sure I understand your point here.  Summing up all the effects will get us the total number of effects in the filter tree.  But we already have a cut off condition on the total number of effects in the filter map to be < 200.  Why do we need to limit the number of the used effects by the filter to be < 100?  I thought we care about the depth because it represents how much complex the filter composition will be.  But the total number of effects used by the filter does not reveal this information.

What Dirk is saying is that only active effects will be added to the map. So, we could have less than 200 children in the <filter> but only 80 of them are connected into the chain/graph. Now, when we come to actually process the overall effect, each one of those in the map will contribute to the result, so it is the total number here that counts rather than the maximum depth.

For example, I could have 150 separate feColorMatrix elements, all manipulating the SourceGraphic, and then combined with feMerge. The maximum depth is 2, but we've got more than 100 effects.


<filter>
  <feColorMatrix in="SourceGraphic" out="output1" type="matrix" values="0.001 0 0 0 0 0 0.001 0 0 0 0 0 0.001 0 0 0 0 0 0.001 0"/>
  <feColorMatrix in="SourceGraphic" out="output2" type="matrix" values="0.001 0 0 0 0 0 0.001 0 0 0 0 0 0.001 0 0 0 0 0 0.001 0"/>
  <feColorMatrix in="SourceGraphic" out="output3" type="matrix" values="0.001 0 0 0 0 0 0.001 0 0 0 0 0 0.001 0 0 0 0 0 0.001 0"/>
  <feColorMatrix in="SourceGraphic" out="output4" type="matrix" values="0.001 0 0 0 0 0 0.001 0 0 0 0 0 0.001 0 0 0 0 0 0.001 0"/>
...
  <feMerge>
    <feMergeNode in="out1"/>
    <feMergeNode in="out2"/>
    <feMergeNode in="out3"/>
    <feMergeNode in="out4"/>
    ...
  </feMerge>
</filter>

>>> Source/WebCore/rendering/svg/RenderSVGResourceFilter.h:90
>>> +    const unsigned s_maxCountOfInputEffects = 200; // maximum number of input effects regardless whether they are connected to a filter's lastEffect or not
>> 
>> Please use sentences as comments with periods. Move the comment a line up before the constant. Also, can't it be static constant? You already use s_.
> 
> 

I think this, and s_maxDepthOfInputEffects, should just be file static in the .cpp. No need to put them on the class.

[Said Abou-Hallawa]

Created attachment 238693 [details]
Patch

[Dean Jackson]

Comment on attachment 238693 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=238693&action=review

> Source/WebCore/ChangeLog:20
> +        -- Do not build a filter if its has more than 200 FilterEffect's in its map.

Typo: its -> it
Typo: FilterEffects

> Source/WebCore/ChangeLog:22
> +        -- Discard a filter after it has more than 100 FilterEffect's in its tree.

Typo: FilterEffects

> Source/WebCore/platform/graphics/filters/FilterEffect.cpp:116
> +unsigned FilterEffect::numberOfEffectInputsRecursive() const
> +{
> +    unsigned size = m_inputEffects.size();
> +    unsigned count = 0;
> +    for (unsigned i = 0; i < size; ++i) {
> +        FilterEffect* in = m_inputEffects.at(i).get();
> +        count += in->numberOfEffectInputsRecursive();
> +    }
> +    return count + 1;
> +}

This isn't quite right.  e.g. feFlood and feTurbulence don't have any input effects, so we need to return 0 if the m_inputEffects.size() is 0.

But also, this could count the same effect multiple times - it could be the input to more than one later step. Doing this properly is a bit tricky :( I'll make another comment down where we might be able to count properly (in RenderSVGResourceFilter.cpp).

> Source/WebCore/rendering/svg/RenderSVGResourceFilter.cpp:181
> -    if (!lastEffect)
> +    if (!lastEffect || lastEffect->numberOfEffectInputsRecursive() > maxNumberOfEffectInputsRecursive)

OK, so we have to recursively count the input effects without duplicates. Luckily the builder has a map of all the named inputs and effect references, so it already has this information, but we just need to get it to expose it.

I think you should add this to SVGFilterBuilder. You'd keep a HashSet<RefPtr<FilterEffect>> that is added to in appendEffectToEffectReferences, and then a method to expose totalNumberOfInputs() or something like that. It would be the size of that set, plus the named inputs (size of m_namedEffects), plus the built-in effects (m_builtInEffects). 

You should double check that appendEffectToEffectReferences is not called for the named or built-in effects though. If it is, then we just need the size of our new set.

[Said Abou-Hallawa]

(In reply to comment #24)
> (From update of attachment 238693 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=238693&action=review
> 
> > Source/WebCore/platform/graphics/filters/FilterEffect.cpp:116
> > +unsigned FilterEffect::numberOfEffectInputsRecursive() const
> > +{
> > +    unsigned size = m_inputEffects.size();
> > +    unsigned count = 0;
> > +    for (unsigned i = 0; i < size; ++i) {
> > +        FilterEffect* in = m_inputEffects.at(i).get();
> > +        count += in->numberOfEffectInputsRecursive();
> > +    }
> > +    return count + 1;
> > +}
> 
> This isn't quite right.  e.g. feFlood and feTurbulence don't have any input effects, so we need to return 0 if the m_inputEffects.size() is 0.
>

Why do we have to return 0 in this case?  Should not we return 1 for feFlood and feTurbulence?  And I think this what is going to return according to your suggested solution below.

> But also, this could count the same effect multiple times - it could be the input to more than one later step. Doing this properly is a bit tricky :( I'll make another comment down where we might be able to count properly (in RenderSVGResourceFilter.cpp).
> 
> > Source/WebCore/rendering/svg/RenderSVGResourceFilter.cpp:181
> > -    if (!lastEffect)
> > +    if (!lastEffect || lastEffect->numberOfEffectInputsRecursive() > maxNumberOfEffectInputsRecursive)
> 
> OK, so we have to recursively count the input effects without duplicates. Luckily the builder has a map of all the named inputs and effect references, so it already has this information, but we just need to get it to expose it.
> 
> I think you should add this to SVGFilterBuilder. You'd keep a HashSet<RefPtr<FilterEffect>> that is added to in appendEffectToEffectReferences, and then a method to expose totalNumberOfInputs() or something like that. It would be the size of that set, plus the named inputs (size of m_namedEffects), plus the built-in effects (m_builtInEffects). 

Why should we count (size of m_namedEffects)? I think we should not. These filters are exactly the same

<filter id="ShiftAndBlur">
  <feOffset dx="10" dy="10" />
  <feGaussianBlur stdDeviation="8.0" />
</filter>

And

<filter id="ShiftAndBlur">
  <feOffset in='SourceGraphic' result='ef1' dx="10" dy="10" />
  <feGaussianBlur in='ef1' result='ef2' stdDeviation="8.0" />
</filter>

But with the first filter (size of m_namedEffects) = 0 and with the second filter (size of m_namedEffects) = 2.

> 
> You should double check that appendEffectToEffectReferences is not called for the named or built-in effects though. If it is, then we just need the size of our new set.

Yes appendEffectToEffectReferences is called from one place which is RenderSVGResourceFilter::buildPrimitives() with only a newly created effect.

But I am not sure if we need to keep HashSet<RefPtr<FilterEffect>> and add to it in appendEffectToEffectReferences().  I think this does not give us the information we need starting from the lastEffect.

How about this solution:

unsigned FilterEffect::collectEffects(const FilterEffect*effect, HashSet<const FilterEffect*>& allEffects)
{
    allEffects.add(effect);
    unsigned size = effect->numberOfEffectInputs();
    for (unsigned i = 0; i < size; ++i) {
        FilterEffect* in = effect->inputEffect(i);
        collectEffects(in, allEffects);
    }
    return allEffects.size();
}

unsigned FilterEffect::totalNumberOfEffectInputs() const
{
    HashSet<const FilterEffect*> allEffects;
    return collectEffects(this, allEffects);
}

And the caller will look like this:

if (!lastEffect || lastEffect->totalNumberOfEffectInputs() > maxtotalNumberOfEffectInputs)

[Dean Jackson]

(In reply to comment #25)
> But I am not sure if we need to keep HashSet<RefPtr<FilterEffect>> and add to it in appendEffectToEffectReferences().  I think this does not give us the information we need starting from the lastEffect.
> 
> How about this solution:
> 
> unsigned FilterEffect::collectEffects(const FilterEffect*effect, HashSet<const FilterEffect*>& allEffects)
> {
>     allEffects.add(effect);
>     unsigned size = effect->numberOfEffectInputs();
>     for (unsigned i = 0; i < size; ++i) {
>         FilterEffect* in = effect->inputEffect(i);
>         collectEffects(in, allEffects);
>     }
>     return allEffects.size();
> }
> 
> unsigned FilterEffect::totalNumberOfEffectInputs() const
> {
>     HashSet<const FilterEffect*> allEffects;
>     return collectEffects(this, allEffects);
> }
> 
> And the caller will look like this:
> 
> if (!lastEffect || lastEffect->totalNumberOfEffectInputs() > maxtotalNumberOfEffectInputs)

I like this idea!!

[Said Abou-Hallawa]

Created attachment 238892 [details]
Patch

[Dean Jackson]

Comment on attachment 238892 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=238892&action=review

Looks great. Minor comments. Upload a new patch and we'll land this!!

> Source/WebCore/platform/graphics/filters/FilterEffect.cpp:107
> +unsigned FilterEffect::collectEffects(const FilterEffect*effect, HashSet<const FilterEffect*>& allEffects)

This could be a static function just in this file, not in the class.

> Source/WebCore/platform/graphics/filters/FilterEffect.h:82
> +    static unsigned collectEffects(const FilterEffect*, HashSet<const FilterEffect*>&);

No need for this if we just declare it in the .cpp.

> LayoutTests/ChangeLog:13
> +        Test if an SVG filter with deeply nested tree of FilterEffects can be loaded
> +        with no crash.  Make sure other valid filters can still be referenced by SVG 
> +        drawing elements.
> +
> +        * svg/filters/svg-deeply-nested-crash-expected.txt: Added.
> +        * svg/filters/svg-deeply-nested-crash.html: Added.

Now we should have one more test that is the <200 but >100 case.

[Said Abou-Hallawa]

Created attachment 238973 [details]
Patch

[WebKit Commit Bot]

Comment on attachment 238973 [details]
Patch

Clearing flags on attachment: 238973

Committed r174137: <http://trac.webkit.org/changeset/174137>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Said Abou-Hallawa]

*** Bug 50749 has been marked as a duplicate of this bug. ***