Apply a security patch for ICU regex. (http://bugs.icu-project.org/trac/ticke...

third_party/icu38/source/i18n/rematch.cpp

 /*
 **************************************************************************
-*   Copyright (C) 2002-2007 International Business Machines Corporation  *
+*   Copyright (C) 2002-2008 International Business Machines Corporation  *
 *   and others. All rights reserved.                                     *
 **************************************************************************
 */
 //
 //  file:  rematch.cpp    
 //
 //         Contains the implementation of class RegexMatcher,
 //         which is one of the main API classes for the ICU regular expression package.
 //
 
 #include "unicode/utypes.h"
 #if !UCONFIG_NO_REGULAR_EXPRESSIONS
 
 #include "unicode/regex.h"
 #include "unicode/uniset.h"
 #include "unicode/uchar.h"
 #include "unicode/ustring.h"
 #include "unicode/rbbi.h"
 #include "uassert.h"
 #include "cmemory.h"
 #include "uvector.h"
 #include "uvectr32.h"
 #include "regeximp.h"
 #include "regexst.h"
 
 // #include <malloc.h>        // Needed for heapcheck testing
 
 U_NAMESPACE_BEGIN
 
+// Limit the size of the back track stack, to avoid system failures caused
+//   by heap exhaustion.  Units are in 32 bit words, not bytes.
+// This value puts ICU's limits higher than most other regexp implementations,
+//  which use recursion rather than the heap, and take more storage per
+//  backtrack point.
+// This constant is _temporary_.  Proper API to control the value will added.
+//
+static const int32_t BACKTRACK_STACK_CAPACITY = 8000000;
+
 //-----------------------------------------------------------------------------
 //
 //   Constructor and Destructor
 //
 //-----------------------------------------------------------------------------
 RegexMatcher::RegexMatcher(const RegexPattern *pat)  { 
     fPattern           = pat;
     fPatternOwned      = NULL;
     fInput             = NULL;
     fTraceDebug        = FALSE;
     fDeferredStatus    = U_ZERO_ERROR;
     fStack             = new UVector32(fDeferredStatus); 
     fData              = fSmallData;
     fWordBreakItr      = NULL;
     if (pat==NULL) {
         fDeferredStatus = U_ILLEGAL_ARGUMENT_ERROR;
         return;
     }
     if (pat->fDataSize > (int32_t)(sizeof(fSmallData)/sizeof(int32_t))) {
         fData = (int32_t *)uprv_malloc(pat->fDataSize * sizeof(int32_t)); 
     }
     if (fStack == NULL || fData == NULL) {
         fDeferredStatus = U_MEMORY_ALLOCATION_ERROR;
+    } else {
+        fStack->setMaxCapacity(BACKTRACK_STACK_CAPACITY);
     }
-        
     reset(RegexStaticSets::gStaticSets->fEmptyString);
 }
 
 
 
 RegexMatcher::RegexMatcher(const UnicodeString &regexp, const UnicodeString &input,
                            uint32_t flags, UErrorCode &status) {
     UParseError    pe;
     fPatternOwned      = RegexPattern::compile(regexp, flags, pe, status);
     fPattern           = fPatternOwned;
     fTraceDebug        = FALSE;
     fDeferredStatus    = U_ZERO_ERROR;
     fStack             = new UVector32(status); 
     fData              = fSmallData;
     fWordBreakItr      = NULL;
     if (U_FAILURE(status)) {
         return;
     }
     if (fPattern->fDataSize > (int32_t)(sizeof(fSmallData)/sizeof(int32_t))) {
         fData = (int32_t *)uprv_malloc(fPattern->fDataSize * sizeof(int32_t)); 
     }
     if (fStack == NULL || fData == NULL) {
         status = U_MEMORY_ALLOCATION_ERROR;
+    } else {
+        fStack->setMaxCapacity(BACKTRACK_STACK_CAPACITY);
     }
     reset(input);
 }
 
 
 RegexMatcher::RegexMatcher(const UnicodeString &regexp, 
                            uint32_t flags, UErrorCode &status) {
     UParseError    pe;
     fTraceDebug        = FALSE;
     fDeferredStatus    = U_ZERO_ERROR;
     fStack             = new UVector32(status); 
     fData              = fSmallData;
     fPatternOwned      = RegexPattern::compile(regexp, flags, pe, status);
     fPattern           = fPatternOwned;
     fWordBreakItr      = NULL;
     if (U_FAILURE(status)) {
         return;
     }
 
     if (fPattern->fDataSize > (int32_t)(sizeof(fSmallData)/sizeof(int32_t))) {
         fData = (int32_t *)uprv_malloc(fPattern->fDataSize * sizeof(int32_t)); 
     }
     if (fStack == NULL || fData == NULL) {
         status = U_MEMORY_ALLOCATION_ERROR;
+    } else {
+        fStack->setMaxCapacity(BACKTRACK_STACK_CAPACITY);
     }
     reset(RegexStaticSets::gStaticSets->fEmptyString);
 }
 
 
 
 RegexMatcher::~RegexMatcher() {
     delete fStack;
     if (fData != fSmallData) {
         uprv_free(fData);
@@ skipping 892 matching lines @@
 //       in the opcode.  Execution of the engine continues with the state in
 //       the newly created stack frame
 //
 //       Note that reserveBlock() may grow the stack, resulting in the
 //       whole thing being relocated in memory.  
 //
 //--------------------------------------------------------------------------------
 inline REStackFrame *RegexMatcher::StateSave(REStackFrame *fp, int32_t savePatIdx, int32_t frameSize, UErrorCode &status) {
     // push storage for a new frame. 
     int32_t *newFP = fStack->reserveBlock(frameSize, status);
+    if (newFP == NULL) {
+        // Heap allocation error on attempted stack expansion.
+        // We need to return a writable stack frame, so just return the
+        //    previous frame.  The match operation will stop quickly
+        //    becuase of the error status, after which the frame will never
+        //    be looked at again.
+        return fp;
+    }
     fp = (REStackFrame *)(newFP - frameSize);  // in case of realloc of stack.
     
     // New stack frame = copy of old top frame.
     int32_t *source = (int32_t *)fp;
     int32_t *dest   = newFP;
     for (;;) {
         *dest++ = *source++;
         if (source == newFP) {
             break;
         }
     }
     
     fp->fPatIdx = savePatIdx;
     return (REStackFrame *)newFP;
 }
-    
-            
+
+
 //--------------------------------------------------------------------------------
 //
 //   MatchAt      This is the actual matching engine.
 //
 //--------------------------------------------------------------------------------
 void RegexMatcher::MatchAt(int32_t startIdx, UErrorCode &status) {
     UBool       isMatch  = FALSE;      // True if the we have a match.
 
     int32_t     op;                    // Operation from the compiled pattern, split into
     int32_t     opType;                //    the opcode
@@ skipping 1210 matching lines @@
 
 
 
         default:
             // Trouble.  The compiled pattern contains an entry with an
             //           unrecognized type tag.
             U_ASSERT(FALSE);
         }
 
         if (U_FAILURE(status)) {
+            isMatch = FALSE;
             break;
         }
     }
     
 breakFromLoop:
     fMatch = isMatch;
     if (isMatch) {
         fLastMatchEnd = fMatchEnd;
         fMatchStart   = startIdx;
         fMatchEnd     = fp->fInputIdx;
@@ skipping 16 matching lines @@
 }
 
 
 
 UOBJECT_DEFINE_RTTI_IMPLEMENTATION(RegexMatcher)
 
 U_NAMESPACE_END
 
 #endif  // !UCONFIG_NO_REGULAR_EXPRESSIONS