bugGNU Octave - Bugs: bug #35679, median (rand (1,1,1,3), 4)...

 
 

bug #35679: median (rand (1,1,1,3), 4) segmentation fault

Submitted by:  None
Submitted on:  Thu 01 Mar 2012 03:34:01 PM UTC  
 
Category: InterpreterSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Segfault, Bus Error, etc.
Status: FixedAssigned to: Jordi Gutiérrez Hermoso <jordigh>
Originator Name: Originator Email: -unavailable-
Open/Closed: ClosedRelease: 3.6.1
Operating System: Any

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission Jump to the original submission)

Wed 07 Mar 2012 05:05:00 AM UTC, comment #17:

Okay, pushed the fix on stable:

http://hg.savannah.gnu.org/hgweb/octave/rev/3d4bea9accd7

Perhaps make a 3.6.2 release in a month or so?

Jordi Gutiérrez Hermoso <jordigh>
Project AdministratorIn charge of this item.
Wed 07 Mar 2012 03:21:51 AM UTC, comment #16:

Could you please add some tests for the cases that were failing for you and then push a changeset to the stable branch?

Thanks.

John W. Eaton <jwe>
Project Administrator
Wed 07 Mar 2012 01:26:12 AM UTC, comment #15:

jwe's patch works for me on all the cases I tried. I don't know why I was having trouble with it earlier. Push it to the stable branch?

Jordi Gutiérrez Hermoso <jordigh>
Project AdministratorIn charge of this item.
Tue 06 Mar 2012 10:17:43 PM UTC, comment #14:

Could this bug affect the correctness of median() results in other cases (garbage results could be worse than a crash)?

Anonymous
Tue 06 Mar 2012 08:04:12 PM UTC, comment #13:

In n.length(ns), n is an idx_vector, and idx_vector::length does take an argument and it is not optional.

In idx_vector::length, the argument is supposed to be the dimension of the object that the index vector is applied to. So if, for example, the index_vector object represents a colon index, the length method will return the dimension.

John W. Eaton <jwe>
Project Administrator
Tue 06 Mar 2012 07:30:45 PM UTC, comment #12:

The patch works for me. Quoting the troublesome part of the code (with JWE's fix):

As I understand it, the code is attempting to limit the number of items to look up either to the number of elements along the selected dimension OR the number of elements requested to be returned. When median is called it needs either 1 return value if the number of elements is odd or 2 values if the number of elements is even.

This squares with the observed behavior.

fails because std::min (3,1) = 1 and this sets dv(dim) to 1 which then causes this dimension to be removed by chop_trailing_singletons. After that, stride is calculated incorrectly because dim is too large.

The counter-example

works because median requests the two values 2:3 in order to average them to form the median. In this case std::min (4,2) = 2 and the dimension stays in place.

A second counter-example also works

In this case, chop_trailing_singletons can't remove dimension 4 because it is protected by dimension 5 which is greater than 1.

So I think JWE's patch solves the problem by restricting the stride calculation to what remains of the dimension vector.

As a last aside, the prototype for the length() function takes void as an argument. I found the following code confusing because I thought ns was somehow involved and it isn't.

I think this should be rewritten to

which compiles and works for me.

Rik <rik5>
Project Administrator
Tue 06 Mar 2012 06:24:35 PM UTC, comment #11:

The attached patch seemed to fix the problem for me, at least for the examples I tried. Could you try it and tell me what cases it does not fix?

(file #25275)

John W. Eaton <jwe>
Project Administrator
Tue 06 Mar 2012 05:26:53 PM UTC, comment #10:

Yes, I found that too, but in certain cases (e.g. the even case) the computation of the stride is incorrect (too large) even with your patch and still goes past the end, reading uninitialised data.

Moreover, it doesn't make sense to chop the singletons immediately after reading the dimension vector. The reason they're chopped is for the benefit of the m array. I think the problem is ultimately in the computation of the stride.

Unfortunately, I'm having difficulty understanding the algorithm that Jaroslav had in mind here, so I still cannot figure out how to fix it. But I'm still working on it.

Jordi Gutiérrez Hermoso <jordigh>
Project AdministratorIn charge of this item.
Tue 06 Mar 2012 05:12:01 PM UTC, comment #9:

It's possible that there is more to the issue, but the trimming of singleton dimensions was definitely being done in the wrong place. When I single stepped through the code what I discovered was that the variable stride was getting set to an incorrect value. Backtracking, I found that stride was being set incorrectly in this loop.

The problem is not with this code itself, but with the fact that dim was based on the original size of the dimension vector dv and not the current size, which may be smaller thanks to chop_singleton_dimensions(). The for loop was overstepping the actual bounds of dv and indexing into some unknown region of memory which resulted in a crazy value for stride.

Separately, I too noticed that in the original code any odd value for the number of elements produces a segfault while any even value is acceptable.

Rik <rik5>
Project Administrator
Tue 06 Mar 2012 02:33:09 PM UTC, comment #8:

I'm still working on this. I'm almost convinced that Rik's patch isn't correct. As I see it, there appear to be outstanding problems if taking the median of 2n instead of 2n+1 things. I'm still investigating...

Jordi Gutiérrez Hermoso <jordigh>
Project AdministratorIn charge of this item.
Fri 02 Mar 2012 10:58:08 PM UTC, comment #7:

Thanks for waiting for me Rik.

I'll be a bit busy this weekend, but I do want to look over this and a few other bugs and patches on Monday.

Jordi Gutiérrez Hermoso <jordigh>
Project AdministratorIn charge of this item.
Fri 02 Mar 2012 05:06:40 PM UTC, comment #6:

Thanks Marco. I'll let Jordi review it too and if he likes it he can commit it.

Rik <rik5>
Project Administrator
Fri 02 Mar 2012 10:06:41 AM UTC, comment #5:

It seems fixed on 3.6.0 by your patch.

Marco

Marco Caliari <caliari>
Project Member
 Spam posted by an anonymous
Thu 01 Mar 2012 08:26:58 PM UTC, comment #4:

I've attached a patch against the stable branch of Octave that fixes the problem for me. I would like some confirmatory testing before I commit it.

(file #25235)

Rik <rik5>
Project Administrator
Thu 01 Mar 2012 06:57:01 PM UTC, comment #3:

This bug came into being between 3.2.4 and 3.4.0 when the backend of median was changed to use the C++ function nth_element.

Rik <rik5>
Project Administrator
Thu 01 Mar 2012 04:08:59 PM UTC, comment #2:

I got this...

Jordi Gutiérrez Hermoso <jordigh>
Project AdministratorIn charge of this item.
Thu 01 Mar 2012 03:37:53 PM UTC, comment #1:

Sorry, for mingw (Windows) the octave version was 3.6.0. For Linux and cygwin, 3.6.1. In all cases I got the infamous "panic -- stopping myself" blurb

Anonymous
Thu 01 Mar 2012 03:34:01 PM UTC, original submission:

Very easy to reproduce, in Linux, Cygwin and Windows (mingw)

Anonymous

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach File(s):
   
   
Comment:
   

Attached Files
file #25275:  diffs.txt added by jwe (257B - text/plain)
file #25235:  median.cset added by rik5 (1KiB - application/octet-stream)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by jwe (Updated the item)
  • -unavailable- added by caliari (Posted a comment)
  • -unavailable- added by rik5 (Posted a comment)
  • -unavailable- added by jordigh (Posted a comment)
  • -unavailable- added by None (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 7 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Wed 07 Mar 2012 05:05:00 AM UTCjordighStatusPatch Submitted=>Fixed
      Open/ClosedOpen=>Closed
    Tue 06 Mar 2012 06:24:35 PM UTCjweAttached File-=>Added diffs.txt, #25275
    Thu 01 Mar 2012 08:26:58 PM UTCrik5Attached File-=>Added median.cset, #25235
      StatusConfirmed=>Patch Submitted
    Thu 01 Mar 2012 04:08:59 PM UTCjordighStatusNone=>Confirmed
      Assigned toNone=>jordigh

    Back to the top


    Powered by Savane 3.1-cleanup1