[Gnash-commit] [bug #39385] boost/variant/detail/visitation_impl.hpp:207: ... Assertion `false' failed.

[Bastiaan Jacques]

URL:
  <http://savannah.gnu.org/bugs/?39385>

                 Summary: boost/variant/detail/visitation_impl.hpp:207: ...
Assertion `false' failed.
                 Project: Gnash - The GNU Flash player
            Submitted by: bjacques
            Submitted on: Mon 01 Jul 2013 02:19:19 PM CEST
                Category: core
                Severity: 6 - Security
                 Release: master
                  Status: Confirmed
                 Privacy: Public
             Assigned to: None
             Open/Closed: Open
         Discussion Lock: Any

    _______________________________________________________

Details:

Please see downstream report:
https://bugzilla.redhat.com/show_bug.cgi?id=924339

The abort can be reproduced reliably by starting Gnash with the noted
arguments, omitting the ones relating to embedding Gnash.

Although a boost assertion fails, I quickly realised that some sort of memory
corruption is happening, leading to Boost balking on an invalid variant state.
The source of the problem appears to be sortIndexed() (Array_as.cpp), but an
inspection of the array that was being sorted yielded no sources of invalid
memory.

In this case, an array is being sorted using a scripted comparator. I soon
discovered that replacing the comparator prevented the problem altogether. The
offending comparator reads as follows:

static function $sortRandom(a, b) {
            return((randomInteger(0, 1) ? 1 : -1));
        }
        static function randomInteger(min, max) {
            return(min + Math.floor(Math.random() * ((max + 1) - min)));
        }


Unfortunately, C++ requires that the comparator be modeled after 'strict weak
ordering'. If this requirement is not fulfilled, corruption problems appear
(see e.g.
http://schneide.wordpress.com/2010/11/01/bug-hunting-fun-with-stdsort/).

In this case, this Flash movie's author's intention is that the array is
randomized rather than sorted, and obviously the comparator written does not
follow any ordering model.

The bug can be reduced to this testcase:


function randomComparator(a, b) {
   return Math.random() < 0.5 ? -1 : 1;
}
Array(1,2,3,4).sort(randomComparator, Array.RETURNINDEXEDARRAY);


(If the second argument is omitted, the bug does not appear.)

For reference I looked at Spidermonkey, where a custom implementation of
MergeSort is used for scripted comparators, which is evidently insensitive to
badly written comparators.

In Gnash, the author of the array sorting code seems to have been aware of
this problem, where in one of the two sorting methods in Array_as.cpp it is
noted that:


    // Invalid comparator can lead to undefined behaviour,
    // including invalid memory access and infinite loops.


The author seems to have worked around this issue by employing
std::list::sort(), which does not seem to exhibit detectable memory problems
when using a nonconforming comparator. (ISO/IEC
14882 nonetheless states that std::list::sort()'s comparator must also meet
the strict weak ordering model.)

In the case of this bug the codepath leads to a different sorting function,
which uses std::sort().

It seems to me that the quick fix here is to alter the second sorting function
to also use std::list::sort(). In the long run we should consider rolling our
own sort algorithm, so that we can guarantee memory safety, if not useful
results, with nonconforming comparators.

Opinions are of course welcome.




    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?39385>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/