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

 
 

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

Submitter:  None
Submitted:  Thu 01 Mar 2012 03:34:01 PM UTC
   
 
Category:  Interpreter Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Segfault, Bus Error, etc.
Status:  Fixed Assigned to:  jordigh
Originator Name:  Originator Email:  -email is unavailable-
Open/Closed:  * Closed Release:  * 3.6.1
Operating System:  * Any Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

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

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>
Group Member
Wed 07 Mar 2012 03:21:51 AM UTC, comment #17: 

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>
Group administrator
Wed 07 Mar 2012 01:26:12 AM UTC, comment #16: 

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>
Group Member
Tue 06 Mar 2012 10:17:43 PM UTC, comment #15: 

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 #14: 

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>
Group administrator
Tue 06 Mar 2012 07:30:45 PM UTC, comment #13: 

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


octave_idx_type ns = dv(dim);

octave_idx_type nn = n.length (ns);

dv(dim) = std::min (nn, ns);
dv.chop_trailing_singletons ();
dim = std::min (dim, dv.length ());


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.


median (rand (1,1,1,3), 4)


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


median (rand (1,1,1,4), 4)


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


median (rand (1,1,1,3,2), 4)


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.


octave_idx_type nn = n.length (ns);


I think this should be rewritten to


octave_idx_type nn = n.length ();


which compiles and works for me.

Rik <rik5>
Group administrator
Tue 06 Mar 2012 06:24:35 PM UTC, comment #12: 

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>
Group administrator
Tue 06 Mar 2012 05:26:53 PM UTC, comment #11: 

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>
Group Member
Tue 06 Mar 2012 05:12:01 PM UTC, comment #10: 

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.


octave_idx_type stride = 1;

for (int i = 0; i < dim; i++)
  stride *= dv(i);


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>
Group administrator
Tue 06 Mar 2012 02:33:09 PM UTC, comment #9: 

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>
Group Member
Fri 02 Mar 2012 10:58:08 PM UTC, comment #8: 

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>
Group Member
Fri 02 Mar 2012 05:06:40 PM UTC, comment #7: 

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

Rik <rik5>
Group administrator
Fri 02 Mar 2012 10:06:41 AM UTC, comment #6: 

It seems fixed on 3.6.0 by your patch.

Marco

Marco Caliari <caliari>
Group Member
  Spam posted by 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>
Group 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>
Group administrator
Thu 01 Mar 2012 04:08:59 PM UTC, comment #2: 

I got this...

Jordi Gutiérrez Hermoso <jordigh>
Group Member
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)


median (rand (1,1,1,3), 4)


Anonymous

 

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

Attach Files:
   
   
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
  • -email is unavailable- added by jwe (Updated the item)
  • -email is unavailable- added by caliari (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by jordigh (Posted a comment)
  • -email is unavailable- added by None (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 7 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2012-03-07 jordigh StatusPatch Submitted Fixed
        Open/ClosedOpen Closed
    2012-03-06 jwe Attached File- Added diffs.txt, #25275
    2012-03-01 rik5 Attached File- Added median.cset, #25235
        StatusConfirmed Patch Submitted
    2012-03-01 jordigh StatusNone Confirmed
        Assigned toNone jordigh

    Back to the top

    Powered by Savane 3.13-caa5.
    Corresponding source code