php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login

go to bug id or search bugs for

Bug #22023 Non-termination problems with certain patterns.
Submitted: 2003-02-02 17:38 UTC Modified: 2003-02-03 15:31 UTC
From: cryo at tiscali dot dk Assigned:
Status: Not a bug Package: PCRE related
PHP Version: 4.3.1-dev, 5.0.0-dev OS: Mandrake 9.0 Linux
Private report: No CVE-ID: None
View Developer Edit
 [2003-02-02 17:38 UTC] cryo at tiscali dot dk 
This is most likely a bug in the PCRE library. It happens with certain patterns in a no-match situation. Consider the following pattern:

/AA(([^A]*A?[^A]+)+)AA/

The letter A doesn't matter. This allows the matching of 'AA' delimited strings, while still allowing single A's inside such strings. Note that /AA(.*)AA/ will not work, since it will just match the outermost enclosing of such a string. Now when matching for instance:

test AAthis is a test of some text insideAA end.

This works fine, and returns right away with preg_match or preg_replace alike. Also with ereg it works fine (without the / pattern delimiters of course). Now consider the similar string:

test AAthis is a test of some text inside end.

The delimiter at the end was removed. Now both preg_match and preg_replace time out after the maximum execution time of 30 seconds. ereg still works fine. The longer the text after the opening AA, the longer time it takes. This is long enough to never finish (within the allotted time), while shorter texts will make it finish after e.g. 20 seconds or so.

Patches

Pull Requests

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2003-02-03 03:34 UTC] sniper@php.net 
<?php

$foo = "test AAthis is a test of some text inside end.";

var_dump(preg_match("/AA(([^A]*A?[^A]+)+)AA/", $foo)); 

?>

This just hangs.
 [2003-02-03 15:31 UTC] iliaa@php.net 
Sorry, but your problem does not imply a bug in PHP itself.  For a
list of more appropriate places to ask for help using PHP, please
visit http://www.php.net/support.php as this bug system is not the
appropriate forum for asking support questions. 

Thank you for your interest in PHP.

This is indeed a bug, however it is not a PHP bug, but rather a bug in the PCRE library, which is not particular to the bundled PCRE library. If you use the PCRE's pcretest command to execute the regular expression shown by sniper@php.net you'll notice that the utility will also 'hang' indefinately consuming all avaliable CPU (unterminated loop?).
 [2003-02-03 16:02 UTC] cryo at tiscali dot dk 
Alright, after more careful study I reached the same conclusion. Also, it's hardly even a bug as such in PCRE but more a consequence of the NFA approach to regular expression matching that the library takes, allowing for a extremely high number of potential matches in patterns like the one I posted.
 
PHP Copyright © 2001-2024 The PHP Group
All rights reserved. 		Last updated: Sat Dec 21 16:01:28 2024 UTC