Bug 120802 – [CSS Shapes] Heap-buffer-overflow in WebCore::ShapeInterval<float>::subtractShapeIntervals

• Status: RESOLVED
• Resolution: FIXED
• Component: CSS

[Hans Muller]

The attached test caused a crash when run with a bounds checker, see https://code.google.com/p/chromium/issues/detail?id=285788.

The source of the problem are several assignments like this: 

static void subtractShapeIntervals(const ShapeIntervals& a, const ShapeIntervals& b, ShapeIntervals& result) 
{ 
    ... 
    const_iterator aNext = a.begin(); 
    const_iterator bNext = b.begin(); 
    ShapeInterval<T> aValue = *aNext; 
    ShapeInterval<T> bValue = *bNext; 

    while (aNext != a.end() && bNext != b.end()) { 
        if (bValue.contains(aValue))
            aValue = *++aNext; // BAD 
        ...
    } 
.... 
} 

Although the LHS of the assignments aren't used when the corresponding iterator has reached its end, the expression still dereferences an invalid address (a.end() in this case). 

The loop has been rewritten; we do not dereference the aNext or bNext iterators without checking the end condition.

[Hans Muller]

Created attachment 210670 [details]
Test case.

[Hans Muller]

Created attachment 210673 [details]
Patch

[Darin Adler]

Comment on attachment 210673 [details]
Patch

The coding style here is awkward. The names “a/b increment” are not so good. I would call them shouldIncrementA/B instead. Also, the logic seems unnecessarily twisted. I have to read it over and over again to be sure it’s right. Might be worth another look to see if we can make the logic clearer. I think we could probably make a version that uses expressions like *aNext++ and eliminates the local variables that would be a lot less confusing.

[Hans Muller]

(In reply to comment #3)
> (From update of attachment 210673 [details])
> The coding style here is awkward. The names “a/b increment” are not so good. I would call them shouldIncrementA/B instead. Also, the logic seems unnecessarily twisted. I have to read it over and over again to be sure it’s right. Might be worth another look to see if we can make the logic clearer. I think we could probably make a version that uses expressions like *aNext++ and eliminates the local variables that would be a lot less confusing.

I used aIncrement and bIncrement instead of names that make more sense as English, to emphasize the relationship between aValue, aNext, and aIncrement.  I agree that the logic is difficult to follow (it's better than it once was, if that's any consolation).  I will take another crack and making it clearer (and hopefully a little shorter) in another patch.

Thanks for the review.

[WebKit Commit Bot]

Comment on attachment 210673 [details]
Patch

Clearing flags on attachment: 210673

Committed r155354: <http://trac.webkit.org/changeset/155354>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Hans Muller]

(In reply to comment #3)
> (From update of attachment 210673 [details])
> The coding style here is awkward. The names “a/b increment” are not so good. I would call them shouldIncrementA/B instead. Also, the logic seems unnecessarily twisted. I have to read it over and over again to be sure it’s right. Might be worth another look to see if we can make the logic clearer. I think we could probably make a version that uses expressions like *aNext++ and eliminates the local variables that would be a lot less confusing.

I took a run at this. The loop isn't simple enough to just use expressions like *aNext++ so I tried moving the fussy logic about safely managing a mutable interval value per iterator to a separate class:

class SubtractShapeIntervalsIterator {
public:
    SubtractShapeIntervalsIterator (const ShapeIntervals& intervals)
        : m_intervals(intervals)
        , m_nextInterval(intervals.begin())
    {
        if (!m_intervals.isEmpty())
            m_value = *m_nextInterval;
    }

    const_iterator shapeIntervalsIterator() const 
    { 
        return m_nextInterval; 
    }

    bool isEnd() const 
    { 
        return m_intervals.isEmpty() || m_nextInterval == m_intervals.end(); 
    }

    void next()
    {
        if (!m_intervals.isEmpty() && ++m_nextInterval != m_intervals.end())
            m_value = *m_nextInterval;
    }

    ShapeInterval& value()
    {
        ASSERT(!m_intervals.empty() && m_nextInterval != m_intervals.end());
        return m_value;
    }

private: 
    const ShapeIntervals& m_intervals;
    const_iterator m_nextInterval;
    ShapeInterval m_value;
};

Rewriting the loop in terms of this private class makes it a little shorter, but sadly I don't think it's simpler or even more readable.

while(!aIterator.isEnd() && !bIterator.isEnd()) {
    if (bIterator.value().contains(aIterator.value())) {
        aIterator.next();
    } else if (aIterator.value().contains(bIterator.value())) {
        if (bIterator.value().x1() > aIterator.value().x1())
            result.push_back(ShapeInterval<T>(aIterator.value().x1(), bIterator.value().x1()));
        if (aIterator.value().x2() > bIterator.value().x2())
            aIterator.value().setX1(bIterator.value().x2());
        else 
            aIterator.next();
        bIterator.next();
    } else if (aIterator.value().overlaps(bIterator.value())) {
        if (aIterator.value() < bIterator.value()) {
            result.push_back(ShapeInterval<T>(aIterator.value().x1(), bIterator.value().x1()));
            aIterator.next();
        } else {
            aIterator.value().setX1(bIterator.value().x2());
            bIterator.next();
        }
    } else {
        if (aIterator.value() < bIterator.value()) {
            result.push_back(aIterator.value());
            aIterator.next();
        }
        else
            bIterator.next();
    }
}

if (!aIterator.isEnd()) {
    result.push_back(aIterator.value());
    result.insert(result.end(), aIterator.shapeIntervalsIterator() + 1, a.end());
}