620667 - MMgc should unlink safely

Status: RESOLVED FIXED

(Tamarin Graveyard :: Garbage Collection (mmGC), enhancement, P3)

Description

[Rob Winchell]

This was identified by the RIM security audit
https://bugzilla.qnx.com/show_bug.cgi?id=81100

Problem:
Description: 

The Flash heap (MMGc) does not unlink items from a number of linked lists
safely. The following methods contain unsafe unlinking:

REALLY_INLINE void GCAlloc::RemoveFromFreeList(GCBlock *b)
REALLY_INLINE void GCAlloc::RemoveFromSweepList(GCBlock *b)
void GCAlloc::UnlinkChunk(GCBlock *b)
void GCHeap::RemoveBlock(HeapBlock *block, bool release)
REALLY_INLINE void* FixedAlloc::InlineAllocSansHook(size_t size,
FixedMallocOpts opts)
void FixedAlloc::FreeChunk(FixedBlock* b)

Impact:

Increases the exploitability of memory corruption issues.

How to Reproduce:

N/A Found through code review

Recommendation:

Safe unlinking should be implemented, as in the following example. The
following method (copied directly from code) does not implement safe unlinking:

REALLY_INLINE void GCAlloc::RemoveFromFreeList(GCBlock *b)
        {
                GCAssert(m_firstFree == b || b->prevFree != NULL);
                if ( m_firstFree == b )
                        m_firstFree = b->nextFree;
                else
                        b->prevFree->nextFree = b->nextFree;

                if (b->nextFree)
                        b->nextFree->prevFree = b->prevFree;
                b->nextFree = b->prevFree = NULL;
        }

The following code implements safe unlinking:

REALLY_INLINE void GCAlloc::RemoveFromFreeList(GCBlock *b)
        {

                if( b->prevFree && b->prevFree->nextFree != b)
                        die();//must crash all threads using heap immediately

                if( b->nextFree && b-> nextFree->prevFree != b)
                        die();


                GCAssert(m_firstFree == b || b->prevFree != NULL);
                if ( m_firstFree == b )
                        m_firstFree = b->nextFree;
                else
                        b->prevFree->nextFree = b->nextFree;

                if (b->nextFree)
                        b->nextFree->prevFree = b->prevFree;
                b->nextFree = b->prevFree = NULL;
        }


Note:

CVSS = 9.3
(AV:N/AC:M/Au:N/C:C/I:C/A:C/E:ND/RL:ND/RC:ND/CDP:ND/TD:ND/CR:ND/IR:ND/AR:ND)

Comment 1

[Rob Winchell]

Note: We don't have access to QNX Bugzilla (that I know of).

Comment 2

[Lars T Hansen]

This method is on the hot path of the memory allocator in the Flash Player.  The patch would add at least four loads, four comparisons, and four conditional branches to every memory allocation, at a time when we're trying to make the memory allocator faster.  A patch along these lines will not be accepted into MMgc, nor are we interested in addressing this theoretical security problem.

Comment 3

[Tommy Reilly]

My feedback to Rob was similar except I thought it would be okay to do this for the block level lists where we aren't on the critical path, I agree that for the FixedAlloc and GCAlloc lists this won't fly.   And I wouldn't do it for security reasons and I wouldn't make this a "security bug".  I was thinking that if we could we could possibly have the crash reports more likely to indicate the source of the problem, for example we could sniff the freelist for a double free and crash in a specific way that meant double free.

Comment 4

[Lars T Hansen]

Obviously if it's the block list and not the primary free list then the performance impact is lower.

That said I don't see why the assertions being proposed here are any different from the hundreds or thousands of assertions that are in the VM, a large subset of which are checking critical invariants (memory invariants, security invariants).  Is QNX proposing that those assertions should also be made active in release builds?

If there's an actual bug that causes the proposed assertions to trigger then that bug should be fixed.  We do not want debug code to run in release builds.

Comment 5

[Lars T Hansen]

The integrity checks in the suggested change have been factored out as assertions, see bug #626588.

Comment 6

[Lars T Hansen]

If we're going to go anywhere with this we're going to need a suitable "die" function.

GCHeap::Abort is clearly not appropriate, as it unwinds the stack of enterFrames; in principle that code might try to reenter the allocator.

VMPI_abort and VMPI_exit probably work but both would take the browser down if the plugin runs in the browser.  (VMPI_exit is actually a little dodgy because it might run atexit handlers.)

In principle we would like to terminate orderly and as little as possible (a GCAlloc failure could take down the one player, whereas a GCHeap or FixedMalloc failure would have to take down everything) but it's not clear we can do that in all cases without a lot of protocol; what if we're in some call-out from the browser and it's expecting a reply?

Comment 7

[Tommy Reilly]

There's a genuine risk of hiding bugs from ourselves unless "die" has some kind of send feedback to Adobe feature.   I can see how on OS allocator would want this and would just terminate the program if it happened.  We aren't an OS though and if this happens in the wild our only way to know about it is to crash.   Therefore I think the only suitable implementation for die is to crash (force a deref of null or something).

Comment 8

[Lars T Hansen]

abort would do, then.

Comment 9

[Rob Winchell]

Attachment: patch for safe unlinking (incomplete)

Does not address GCHeap::RemoveBlock(...) or FixedAlloc::InlineAllocSansHook(...)

Comment 10

[Tommy Reilly]

Comment on attachment 510318 [details] [diff] [review]
patch for safe unlinking (incomplete)

Can we cut the number of calls to VMPI_abort in half and combine the two if clause?   Otherwise looks fine.  For the record I think there's zero value in this change and hope submitting unjustifiable changes to appease external folks doesn't become standard practice.

Comment 11

[Lars T Hansen]

I hereby request SR on this change before it lands.

If asked I would SR- this patch as it stands because it removes useful asserts.  You can argue that the subsequent abort will catch the problem, but the subsequent abort does not necessarily have the same informational value as an assert.

(+1 on reducing the number of calls to VMPI_abort in the source, though no big deal.)

Comment 12

[Rob Winchell]

Attachment: Updated patch based on Lars and Tommy feedback

Comment 13

[Tommy Reilly]

I think you need to type lar's name in to the superreview field

Comment 14

[Dan Smith]

Declassifying:  changes are adding additional run-time checks rather than correcting a known exploit.

Comment 15

[Tommy Reilly]

Attachment: one more spot

This should be uncontroversial b/c the block is already guarded by if(IsFull(b)) and so isn't on the hotpath.

Comment 16

[Tamarin Bot]

changeset: 6053:a17c304ed8cb
user:      Tommy Reilly <[e-mail]>
summary:   Bug 620667 - Safe unlink from freeblock list when it gets full (r=lhansen)

http://hg.mozilla.org/tamarin-redux/rev/a17c304ed8cb