bugGNU Octave - Bugs: bug #51589, crash on regexp

 
 

bug #51589: crash on regexp

Submitted by:  None
Submitted on:  Thu 27 Jul 2017 12:08:33 PM UTC  
 
Category: Octave FunctionSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Segfault, Bus Error, etc.
Status: Wont FixAssigned to: None
Originator Name: Marcin MleczkoOriginator Email: -unavailable-
Open/Closed: ClosedRelease: 4.2.1
Operating System: GNU/Linux

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)

Mon 31 Jul 2017 11:30:17 PM UTC, comment #15:

I pushed your documentation fix on to the stable branch (http://hg.savannah.gnu.org/hgweb/octave/rev/d396866fa7d8) and then merged it to the development branch. I removed the reference to the limitation note from the first line of the function. The first line should be just a short description of the function and this would cause the documentation for regexp to differ from all other Octave functions.

Rik <rik5>
Project Administrator
Fri 28 Jul 2017 06:50:52 PM UTC, comment #14:

Changeset attached. The point of adding the extra sentence at the start of help is to hopefully avoid more bug reports.

(file #41367)

Dan Sebald <sebald>
Fri 28 Jul 2017 05:29:42 PM UTC, comment #13:

Better documentation is always welcome. Do you want to make a cset to apply?

Rik <rik5>
Project Administrator
Fri 28 Jul 2017 05:05:04 PM UTC, comment #12:

Yeah, it's unfortunate this routine is so fragile. Should we put a note up front in the regexp help about this? Something like

A segfault/stack-overflow is such a bad thing because the session history is lost. I'm wondering if there is a way we could protect the stack from overflowing (doesn't sound like). One thing I've often wondered is if Octave processing could have a level of protection against this sort of thing, whether it is seg-faults or cntrl-C whereby it unwinds the stack or "local" memory. That is, something like

Big change of course, a bit OS-like, but perhaps more graceful.

Dan Sebald <sebald>
Fri 28 Jul 2017 04:14:13 PM UTC, comment #11:

It seems like there have been enough suggestions offered that there is a way to code around this, and that the full issue lies upstream with PCRE. I'm going to close this report.

Rik <rik5>
Project Administrator
Fri 28 Jul 2017 05:42:29 AM UTC, comment #10:

@Dan
you are perfectly right assuming that I'm searching for everything that matches exponential notation numbers. The reason I am not searching for the string 'Step' is that it is rather special to this file and not general purpose. Imagin a similar file where the block headers are prety randomly formated text and there is no easy way to define a fitting mach on them. (Yes, that's ugly and I admitt that my example does not do a particularly good job at exposing this aspect of the problem.) But you guys just gave me the idea of searching for everything that does not match exponential notation numbers. This should come closer to the general aplicability I need and reduce the number of machtes.
@Rik
<<Neither Matlab nor Octave is exceptionally good at text processing.>>
I alwasy wondered why thats the case... ;-)

@ all
Thank you for your effort to look into this. You are doing a great job...

Anonymous
Fri 28 Jul 2017 04:57:21 AM UTC, comment #9:

The method that Rik suggests is often how I do processing on a formatted file of the sort you have.

However, one should still be able to make use of regexp() by thinking more in terms of parring down starting with bigger hunks. I think the issue is that the regexp construct you've used gets way too many hits and therefore the recursion is too high that stack overflow occurs. It looks like you are searching for everything that matches exponential notation numbers. Instead, try thinking of ways to reduce the number of "hits".

For example, this regexp() will first produce the blocks:

The SP should contain all the text between the "Step" in the file. Loop through the SP and then use regexp() again to find maybe all individual lines. Then toss out the line that doesn't have the exponential floating point numbers. Then pick the first and last exp-floating point lines.

There are probably a half dozen uses of expressions keeping and/or discarding content, etc. that should get what you want. Experiment a bit I guess.

Dan Sebald <sebald>
Fri 28 Jul 2017 04:14:22 AM UTC, comment #8:

I've tried pcre_dfa_exec(). Unfortunately, it isn't 100% compatible with pcre_exec(), i.e., Perl. And probably one of the few spots they differ is the '+'. It's strange, for length 3 input buffer, i.e., "aaa", it works:

but anything larger produces

The reason is that the number of matches returned by pcre_dfa_exec() is zero (i.e., non-valid dimension).

The "(a)" pattern seems to produce the same result for large input buffer size, but I'm just noticing now that pcre_exec is slightly different than the above result:

Well, I have no faith in switching to the pcre_dfa_exec() given the differences.

Dan Sebald <sebald>
Thu 27 Jul 2017 10:37:26 PM UTC, comment #7:

Stack overflow seems to fit the behavior. Here is some info on the stack usage:

http://pcre.org/original/doc/html/pcreapi.html#SEC22

http://pcre.org/original/doc/html/pcrestack.html

http://pcre.org/original/doc/html/pcretest.html

I don't see the pcretest utility on my system, so I can't test. But I think you are right, now that I read a little bit. The stack recursion is described in one of the above links. They use a "match()" recursion so that it can back out of where it was in some way. Because of all the a's, I suspect the recursion is going something like

and so on. I'm going to guess that match doesn't use much stack, but all it takes is to push as much as a return address and eventually the stack will overflow.

There is a comment in the documentation:

"
If PCRE has been compiled to use the heap instead of the stack for recursion, the value returned is the size of each block that is obtained from the heap.
"

Unfortunately, as I think PCRE is a library, that heap option is out of our control and instead done at the system level.

But, there may be an alternative function:

http://pcre.org/original/doc/html/pcrestack.html

pcre[16|32]_dfa_exec()

That might be the function we want, it only does recursion in limited circumstances... I'm about to leave for a few hours, perhaps you could investigate.

Dan Sebald <sebald>
Thu 27 Jul 2017 10:26:23 PM UTC, comment #6:

@Mike: If you want to research how to tune PCRE I'm fine with that. Otherwise, I'm fine with calling this an upstream issue in PCRE.

@Marcin: Neither Matlab nor Octave is exceptionally good at text processing. If you have lots and lots of data, and several different block identifiers, it is probably better to select a different tool such as Perl to pre-process the data.

I will say that the normal paradigm when dealing with large data is to work on it in small chunks. It may have been only a demonstration program, but loading an entire file as the attached script does is always going to be a problem.

A better plan of attack would be something like this

This still isn't particularly fast, but it's not prone to segfaults.

Rik <rik5>
Project Administrator
Thu 27 Jul 2017 09:41:31 PM UTC, comment #5:

Dan - the segmentation fault looks to me to be due to excessively large number of stack frames, i.e. overflow due to recursion.

On my system, my example first errors out around a length of 7923. I say around because it is not deterministic, at 7925 it crashes 100% of the time, at 7923 it crashes maybe 20% of the time.

If I then decrease the maximum stack size soft limit (ulimit -s), it crashes at a much smaller subject string size. It's about proportional, decrease the stack size limit by half, the subject string crash limit also halves.

So this goes back to the PCRE implementation which uses stack recursion in some way to deal with match groups, and the library has internal variables to set limits on the number of matches and the maximum recursion limit, but I haven't fully looked into what these tunable parameters do. These things are referred to in the PCRE docs, so I wouldn't jump to calling it a bug, but a tunable parameter that might need to be adjusted in how Octave uses PCRE.

Mike Miller <mtmiller>
Project Administrator
Thu 27 Jul 2017 09:31:46 PM UTC, comment #4:

Regardless of the application, this certainly looks like a bug. And best I can guess it is a PCRE bug. There are a few buffers constructed via OCTAVE_LOCAL_BUFFER and then passed into the prce_exec() routine:

but none of them are large working buffers, just small ones which accept returned offset values in the buffer.

Note some small variations on MM's example:

pattern = 'a+';

does not fail. And without the capture syntax (), the ovector size is one triple less, i.e.,

returns subpatters=0.

pattern = '(a)';

does not fail. It returns a very large number of cells, i.e., 'a', 'a', 'a', etc., but doesn't crash. To me, this seems more memory intensive than pattern '(a)+', which groups all the 'a's together in one string.

pattern = '(?:a)+'

surprisingly does fail. This is supposed to be non-remembering capture and is suggested if the capturing version has too much of a performance hit.

Also, the call to pcre_exec() fails immediately, with no jump in system memory.

MM's example fails at 8441 for the length of "aaaaa...a". That doesn't seem particularly large.

So there seems like a bug in PCRE, due to large array size, but not related to running out of memory.

Probably the best thing to do would be write a very short C program that replicates this "aaaa...a" example and submit to PCRE as a bug report.

Dan Sebald <sebald>
Thu 27 Jul 2017 07:24:27 PM UTC, comment #3:

Well Rik, not entirelly...

...the file I need to parse is a bit more complicated. It consists of several blocks of data following one another in a single file. Each block has a header of serveral linse of text and many records of data. These are organized in several columns. Have a look at line 1505, 3008 or 4511 in oc.txt to see some of the other block headers.

The goal I am trying to achieve is to parse this type of file into some kind of data structure which octave can handle. As far as I know, neither octave nor Matlab has any kind of function, which would offer an easy way to parse a multi block file with arbitrary formated headers for each block. Please let me know if I'm wrong and there is such a way.

As the headers vary as well as the number of records (lines) per block vary as well, I figured that the most flexible way is to find the first and the last data point in every block and separate them tha way. This is what that regexp is supposed to do. It's the best I could come up with...

I am pretty aware that using regexp for this porpose is quite heavy handed (the data in oc.txt is only a really tiny example. Real data files have many more blocks whith each block having many more records with way more columns. Data file size can exceed 1GiB easily.) So if you know some better way to achieve this I'd be happy to know...

Thanks

Anonymous
Thu 27 Jul 2017 05:42:33 PM UTC, comment #2:

Yeah I can easily reproduce this crash with a pathological test case like the following:

It might be possible to experiment with the pcre settings on limiting recursion to see if that helps, to avoid a segfault, but I don't know what impact that has on performance or getting the results that the user wanted.

Mike Miller <mtmiller>
Project Administrator
Thu 27 Jul 2017 05:25:02 PM UTC, comment #1:

Confirmed, but I used gdb to check and the segfault is coming from libpcre, rather than Octave. Is there a better pattern to use to accomplish what you want? The pattern

creates a capture-block which may or may not match because of the ending asterisk. The capture buffer has to be allocated out of dynamic memory because it doesn't know in advance what it will find in the text. In this case, it looks like there are over 80,000 matches and probably more than 1M of memory required. That is exceptionally large.

It seems like this is just a tab-separated data file with the first two lines being a text header. If you just want to read the data in to Octave this would be easier.

Rik <rik5>
Project Administrator
Thu 27 Jul 2017 12:08:33 PM UTC, original submission:

Octave crashes when executing grgexp(). To reproduce the problem, run script in attached archive. May by similar to bug #45031 and bug #29438 (both closed)

Marcin

Anonymous

 

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

Attach File(s):
   
   
Comment:
   

Attached Files
file #41360:  crash-octave.zip added by None (239KiB - application/zip)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by sebald (Posted a comment)
  • -unavailable- added by mtmiller (Posted a comment)
  • -unavailable- added by rik5 (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 4 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Fri 28 Jul 2017 06:50:52 PM UTCsebaldAttached File-=>Added octave-regexp_stack_overflow-djs2017jul28.patch, #41367
    Fri 28 Jul 2017 04:14:13 PM UTCrik5StatusNone=>Wont Fix
      Open/ClosedOpen=>Closed
    Thu 27 Jul 2017 12:08:33 PM UTCNoneAttached File-=>Added crash-octave.zip, #41360

    Back to the top


    Powered by Savane 3.1-cleanup1