685520 - Vector.length = uint(Math.pow(2,27)) asserts in avmplusList

Status: RESOLVED FIXED

(Tamarin Graveyard :: Library, defect, P3)

Description

[Felix S. Klock II [:pnkfelix, :fklock]]

AS program "b.as":

  var l;

  l = uint(Math.pow(2,27) - 1);
  print(l);
  var a = new Vector.<int>()
  a.length = l;

  l = uint(Math.pow(2,27));
  print(l);
  var a = new Vector.<int>()
  a.length = l;

  print("Final: "+a.length);

(compiled above with no flags to asc, in case that matters later)

On 32-bit and 64-bit DebugDebugger shell (Mac OS X):

  134217727
  134217728
  Assertion failed: "((cap <= kListMaxLength))" ("/Users/fklockii/Dev/tamarin-redux/core/avmplusList-impl.h":125)

On 32-bit and 64-bit Release shell (Mac OS X):

  134217727
  134217728
  Final: 134217728

As a matter of principle, AVM assertions should represent conditions that cannot be reached via pure Actionscript unless the AVM is otherwise buggy.  So either there is a bug here in AVM, or some sort of exception should be thrown by the AS program in both Debug and Release modes.

[this may well be a dupe; I recall doing a survey of the state of things in spring/summer 2010 while looking into some OOM wonkiness with ByteArray length]

Comment 1

[Dan Smith]

Lars, can you investigate to ensure nothing bad is happening due to this assertion and generate an exception if appropriate.

Comment 2

[Felix S. Klock II [:pnkfelix, :fklock]]

(lars says this might be security issue)

Comment 3

[Lars T Hansen]

Fire drill.

I interpret the assertion as a precondition, ie, the caller must check that the length does not exceed the max.  It needs to be documented in the appropriate header file.

The problem is therefore in TypedVectorObject<TLIST>::set_length(uint32_t newLength), the only caller of set_capacity.   set_length does not validate that the length does not exceed the maximum and instead just passes it blindly to set_capacity.

There is a similar but different problem with ensureCapacityImpl().  Here we have:

        if (cap > kListMaxLength)
            MMgc::GCHeap::SignalObjectTooLarge();
        ....
        AvmAssert(cap <= kListMaxLength);

Clearly this code is correct and the assert is redundant.  However the rest of that functions results in invariants being broken:

        cap += (cap/4);

Consider this program, which does *not* abort:

  var l;

  l = 0x7FFFFFF;
  print(l);
  var a = new Vector.<int>()
  a.length = l;

  a.push(37);
  a.push(37);

The vector length is the maximum so the push() should fail.  However since the growth algorithm has allocated some slop it does not fail.  I don't know what the consequences are of that.

Comment 4

[Lars T Hansen]

To make this more interesting, consider the comments and code:

    // This effectively rules out any indices > 0x7FFFFFFF. To 
    // minimize possibilities of off-by-one errors, we also make
    // the maximum *length* positive.
    const uint32_t kListMaxLength = 0x7FFFFFF;

Hint: count the "F"s.

Comment 5

[Lars T Hansen]

Probably not a security problem, but not declassifying yet.

Several bugs here.

The first bug is the missing check on capacity in TypedVectorObject::set_length or in ListImpl::set_capacity.  IMO the check might as well be in the latter, since set_length is the only caller and it is not set up to handle a failure in any case.

The second bug is the lack of clamping on 'cap' in ensureCapacityImpl, or more generally, the confusion throughout the list code about "capacity" vs "length".  Several places we check that capacity does not exceed max length, but ensureCapacityImpl does not uphold that invariant.  Failure to do so allows the length to grow beyond the max length as demonstrated above.

The third bug is that kListMaxLength is 0x7FF_FFFF instead of 0x7FFF_FFFF.

IMO the right fix is to tie the max length and max capacity together and to rigorously enforce that no vector has higher capacity than the max capacity.  The problem with that approach is that 'capacity' is not stored but instead computed from the object size, and the object size may be larger than requested due to rounding in MMgc.

Thus the appropriate fix might be to enforce the length more rigorously and let capacity continue to be a vague notion, but I dislike that idea intensely.

Comment 6

[Lars T Hansen]

Attachment: Work in progress

Comment 7

[Lars T Hansen]

For there to be a security issue we would have to have a situation where we read or write outside the allocated space for the underlying List datum.

The List API uniformly uses uint32_t to represent indices, offsets, capacities, lengths, whatever.  So there's no problem with signedness being misinterpreted on this level.  There could be a problem in the vector code.  But so far as I can tell all vector code correctly guards accesses with a length check.  Ergo accesses are within bounds of the length.

For the code to be safe the length is not guaranteed to be less than kMaxListLength but the length is guaranteed to be less than the capacity.  That problem resides entirely within the List code, since the Vector code does not update either length or capacity directly.

Allocation happens in ListHelper::LISTDATA::create.  All instances of that function correctly check for overflow on the request size.  All callers are instances of allocData.  Those correctly treat the capacity.  All callers of allocData seem OK as well.  Tentative conclusion is therefore that length <= capactity always, as desired.

Comment 8

[Lars T Hansen]

Attachment: Patch

This patch does it the hard way: It requires and maintains an invariant that length <= kListMaxLength always, and requires only that capacity >= length.

The alternative would be to introduce a field for capacity in the list structure, to have an exact value for that.  It would then have to be the case that that value is less than or equal to the capacity computed from the size of the object, so the additional field seems to have no utility in reducing complexity much.

This patch does not make the change from 0x7FFFFFF to 0x7FFFFFFF, but it anticipates it: with this patch, the code should remain correct when that change is made.

Comment 9

[Felix S. Klock II [:pnkfelix, :fklock]]

Comment on attachment 560177 [details] [diff] [review]
Patch

Review of attachment 560177 [details] [diff] [review]:
-----------------------------------------------------------------

R+

::: core/avmplusList-impl.h
@@ +300,5 @@
>      void ListImpl<T,ListHelper>::insert(uint32_t index, const T* args, uint32_t argc)
>      {
>          uint32_t const len = m_data->len;
> +
> +        // If m_data->len + argc overflows uint32_t then ensureCapacityExtra 

Nit: Trailing space here.

@@ +317,5 @@
>                  ListHelper::storeInEmpty(m_data, index + i, args[i]);
>          }
>  
> +        // No overflow check required for reasons stated above.
> +        set_length_with_check(m_data->len + argc);

Reading the comment and then the method call that follows made me realize that the names here are a little unfortunate, in that it'd be nice to distinguish clearly the "max-length checks" from "overflow checks."

(Or maybe just use the phrase "overflow guard" instead of "check" so that the reader's brain doesn't first think of overflow checks when reading the method invocation below.)

Having said that, I'm really at a loss to suggest something better that that while remaining concise.  So these can land as is.

@@ +353,5 @@
>              }
>          }
>  
> +        // No overflow check needed for reasons stated above.
> +        set_length_with_check(len + insertCount - deleteCount);

(see previous note regarding two occurrences of "check" here)

@@ +385,5 @@
>              ListHelper::store(m_data, insertPoint + i, value);
>          }
>  
> +        // No overflow check needed for reasons stated above.
> +        set_length_with_check(len + insertCount - deleteCount);

(see previous note regarding the two occurrences of "check" here)

::: core/avmplusList-inlines.h
@@ +40,5 @@
>  #ifndef __avmplus_List_inlines__
>  #define __avmplus_List_inlines__
> +
> +#ifndef UINT32_T_MAX
> +    #define UINT32_T_MAX (~uint32_t(0))

Nit: Uses different expression (with same eventual value) from definition in avmshell.h. I'd choose one expression to use in both places; I don't care which.  (Ideally we wouldn't duplicate the definition at all, but that's scope creep for this bug.)

::: core/avmplusList.h
@@ +332,5 @@
>                            const T* args = NULL);
>  
>          ~ListImpl();
>  
> +        // Set m_data->len from 'newlength', but if newlength exceeds the max 

Nit: trailing space here (there are others in the file, but lets not add new ones).

@@ +338,5 @@
> +        void set_length_with_check(uint32_t newlength);
> +
> +        // Set data->len from 'newlength', but if newlength exceeds the max
> +        // length then abort.
> +        void set_length_with_check(typename ListHelper::LISTDATA* data, uint32_t newlength);

Consider making this method a static member (as it doesn't manipulate state of 'this' and is non-virtual).

Comment 10

[Lars T Hansen]

I renamed as "set_length_guarded" and took you up on the other suggestions.

Comment 11

[Tamarin Bot]

changeset: 6594:0d3dea4cfe06
user:      Lars T Hansen <[e-mail]>
summary:   Fix 685520 - Vector.length = uint(Math.pow(2,27)) asserts in avmplusList (r=fklockii)

http://hg.mozilla.org/tamarin-redux/rev/0d3dea4cfe06

Comment 12

[Lars T Hansen]

Follow-up item for changing kMaxListLength filed as bug #687796.