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

 
 

bug #51589: crash on regexp

Submitter:  None
Submitted:  Thu 27 Jul 2017 12:08:33 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Segfault, Bus Error, etc.
Status:  Wont Fix Assigned to:  None
Originator Name:  Marcin Mleczko Originator Email:  -email is unavailable-
Open/Closed:  * Closed Release:  * 4.2.1
Operating System:  * GNU/Linux Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

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>
Group 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>
Group 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


 -- [S, E, TE, M, T, NM, SP] = regexp (STR, PAT)
 -- [...] = regexp (STR, PAT, "OPT1", ...)
     Regular expression string matching.  (See note about stack
     limitations near end of help.)

     Search for PAT in STR and return the positions and substrings of
     any matches, or empty values if there are none.
[snip]

     NOTE: Pattern searches are done with a recursive function
     which can overflow the stack when there are high numbers
     of matches found.  For example:

         regexp (repmat ('a', 1, 1e5), '(a)+');

     Consider constructing pattern searches that reduce the
     number of matches, such as using set complement, then
     further process the return variables with successive
     searches.


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


1) record stack pointer (SP), clear working variable memory space
2) parse code and run
3) if fault or cntrl-C signal, rewind stack pointer (to SP), toss working memory
4) no error, move working variable memory to global variable memory


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>
Group 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:


octave:31> fid=fopen("oc.txt",'r');
octave:32> text = char (fread (fid, "uchar")');
octave:33> fclose(fid);
octave:34> [S, E, TE, M, T, NM, SP] = regexp (text, '(Step)'); %break into 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:


octave:11> [S, E, TE, M, T, NM, SP] = regexp (subject, pattern);
octave:12> M
M =
{
  [1,1] = aaa
}
octave:13> T
T =
{
  [1,1] =
  {
    [1,1] = aa
    [1,2] = a
  }

}


but anything larger produces


octave:15> [S, E, TE, M, T, NM, SP] = regexp (subject, pattern);
error: out of memory or dimension too large for Octave's index type


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:


octave:1> subject = repmat ('a', 1, 3);
octave:2> pattern = '(a)+';
octave:3> [S, E, TE, M, T, NM, SP] = regexp (subject, pattern);
octave:4> M
M =
{
  [1,1] = aaa
}
octave:5> T
T =
{
  [1,1] =
  {
    [1,1] = a
  }

}


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


a (now search for aa)
aa (now search for aaa)
aaa (now search for aaaa)
aaaa
aaaaa
aaaaaa
aaaaaaa


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.


fid=fopen("oc.txt",'r');
text = char (fread (fid, "uchar")');
fclose(fid);


A better plan of attack would be something like this


fid = fopen ("oc.txt", "r");
data = zeros (1e3, 11);  # Choose something large
cnt = 1;

while (ischar (text = fgets (fid)))
  ## Check text for your condition.
  ## strcmp, strfind, regexp, etc. might be possibilities
  ## Simple check to ignore text entries
  if (isletter (text(1)))
    continue;
  endif

  ## Otherwise, assume data just gets added to array
  data(cnt++, :) = sscanf (text, "%f").';
  if (cnt == rows (data))
    data = resize (data, [2*cnt, 11]);  # Grow array occasionally,
  endif

endwhile

fclose (fid);
## Remove unused elements
data = resize (data, [cnt, 11]);


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

Rik <rik5>
Group 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>
Group Member
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:


fprintf(stderr, "buffer length: %d\n", buffer.length());
//fprintf(stderr, "c_str: %s\n", buffer.c_str());
fprintf(stderr, "idx: %lu\n", idx);
        int matches = pcre_exec (re, nullptr, buffer.c_str (),
                                 buffer.length (), idx,
                                 (idx ? PCRE_NOTBOL : 0),
                                 ovector, (subpatterns+1)*3);


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.,


    pcre_fullinfo (re, nullptr, PCRE_INFO_CAPTURECOUNT,  &subpatterns);


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:


subject = repmat ('a', 1, 1e5);  ## a very long string of aaaa...
pattern = '(a)+';
[S, E, TE, M, T, NM, SP] = regexp (subject, pattern)


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>
Group Member
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


'(?:[+-]?\d*\.\d*e[+-]\d*\s*)*'


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.


x = dlmread ("oc.txt", "\t", 2, 0);



Rik <rik5>
Group 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 Files:
   
   
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
  • -email is unavailable- added by sebald (Posted a comment)
  • -email is unavailable- added by mtmiller (Posted a comment)
  • -email is unavailable- added by rik5 (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 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2017-07-28 sebald Attached File- Added octave-regexp_stack_overflow-djs2017jul28.patch, #41367
    2017-07-28 rik5 StatusNone Wont Fix
        Open/ClosedOpen Closed
    2017-07-27 None Attached File- Added crash-octave.zip, #41360

    Back to the top

    Powered by Savane 3.13-758e.
    Corresponding source code