Bug 220357 – unexpected minimumInputSize in setupDisjunctionOffsets for regexp engine(yarr)

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[raycp]

first of all, the poc is shown as below:
```
function main() {
    let v30 = '4{4294967294}0'
    const v32 = RegExp(v30);
}
main();
```

which will cause the crash in `debug` version of jsc and it won't happen in `release` version of jsc
```
$ ./WebKitBuild/Debug/bin/jsc poc.js
ASSERTION FAILED: minimumInputSize != UINT_MAX
../../Source/JavaScriptCore/yarr/YarrPattern.cpp(937) : JSC::Yarr::ErrorCode JSC::Yarr::YarrPatternConstructor::setupDisjunctionOffsets(JSC::Yarr::PatternDisjunction*, unsigned int, unsigned int, unsigned int&)
[1]    2098538 abort      ./WebKitBuild/Debug/bin/jsc

$ ./WebKitBuild/Release/bin/jsc poc.js
```

the call stack is show as below:
```
#1  0x00007ffff2236859 in __GI_abort () at abort.c:79
#2  0x00005555555d5fff in CRASH_WITH_INFO(...) () at DerivedSources/ForwardingHeaders/wtf/Assertions.h:713
#3  0x00007ffff67430cd in JSC::Yarr::YarrPatternConstructor::setupDisjunctionOffsets (this=0x7fffffffc950, disjunction=0x7fffef9afed8, initialCallFrameSize=0, initialInputPosition=0, callFrameSize=@0x7fffffffc914: 32767) at ../../Source/JavaScriptCore/yarr/YarrPattern.cpp:937
#4  0x00007ffff674318d in JSC::Yarr::YarrPatternConstructor::setupOffsets (this=0x7fffffffc950) at ../../Source/JavaScriptCore/yarr/YarrPattern.cpp:951
#5  0x00007ffff66d480c in JSC::Yarr::YarrPattern::compile (this=0x7fffffffca60, patternString=...) at ../../Source/JavaScriptCore/yarr/YarrPattern.cpp:1131
#6  0x00007ffff66d4a68 in JSC::Yarr::YarrPattern::YarrPattern (this=0x7fffffffca60, pattern=..., flags=..., error=@0x7fffef9fcc5a: JSC::Yarr::ErrorCode::NoError) at ../../Source/JavaScriptCore/yarr/YarrPattern.cpp:1151
#7  0x00007ffff6332ae4 in JSC::RegExp::finishCreation (this=0x7fffef9fcc48, vm=...) at ../../Source/JavaScriptCore/runtime/RegExp.cpp:170
#8  0x00007ffff6332d78 in JSC::RegExp::createWithoutCaching (vm=..., patternString=..., flags=...) at ../../Source/JavaScriptCore/runtime/RegExp.cpp:207
#9  0x00007ffff633b707 in JSC::RegExpCache::lookupOrCreate (this=0x7fffef9d0000, patternString=..., flags=...) at ../../Source/JavaScriptCore/runtime/RegExpCache.cpp:42
#10 0x00007ffff6332dd1 in JSC::RegExp::create (vm=..., patternString=..., flags=...) at ../../Source/JavaScriptCore/runtime/RegExp.cpp:213
#11 0x00007ffff633cf59 in JSC::regExpCreate (globalObject=0x7fffaf5fa068, newTarget=..., patternArg=..., flagsArg=...) at ../../Source/JavaScriptCore/runtime/RegExpConstructor.cpp:249
#12 0x00007ffff633d540 in JSC::constructRegExp (globalObject=0x7fffaf5fa068, args=..., callee=0x7fffef9fcba8, newTarget=...) at ../../Source/JavaScriptCore/runtime/RegExpConstructor.cpp:309
#13 0x00007ffff633d77d in JSC::callRegExpConstructor (globalObject=0x7fffaf5fa068, callFrame=0x7fffffffce70) at ../../Source/JavaScriptCore/runtime/RegExpConstructor.cpp:334
#14 0x00007fffaf8ff027 in ?? ()
#15 0x00007fffffffcf10 in ?? ()
#16 0x00007ffff4dc9db1 in llint_op_call () at /home/raycp/Desktop/WebKit/Source/JavaScriptCore/llint/LowLevelInterpreter.asm:1092
#17 0x0000000000000000 in ?? ()
```

when i finished analysis of the bug, i found that the root cause code is in `setupDisjunctionOffsets` function belong to the yarr engine. the code caused the crash is `ASSERT(minimumInputSize != UINT_MAX)`. The regexp pattern's(`'4{4294967294}0'`) length is `0xffffffff` after setupAlternativeOffsets function call, which means `minimumInputSize` equal to `0xffffffff`. But in the assert code, it can't allow `minimumInputSize` equal to `0xffffffff`, so it goes crash.
```
    // yarr/YarrPattern.cpp: 911
		ErrorCode setupDisjunctionOffsets(PatternDisjunction* disjunction, unsigned initialCallFrameSize, unsigned initialInputPosition, unsigned& callFrameSize)
    {
        if (UNLIKELY(!isSafeToRecurse()))
            return ErrorCode::TooManyDisjunctions;

        if ((disjunction != m_pattern.m_body) && (disjunction->m_alternatives.size() > 1))
            initialCallFrameSize += YarrStackSpaceForBackTrackInfoAlternative;

        unsigned minimumInputSize = UINT_MAX;
        unsigned maximumCallFrameSize = 0;
        bool hasFixedSize = true;
        ErrorCode error = ErrorCode::NoError;

        for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {
            PatternAlternative* alternative = disjunction->m_alternatives[alt].get();
            unsigned currentAlternativeCallFrameSize;
            error = setupAlternativeOffsets(alternative, initialCallFrameSize, initialInputPosition, currentAlternativeCallFrameSize);
            if (hasError(error))
                return error;
            minimumInputSize = std::min(minimumInputSize, alternative->m_minimumSize);
            maximumCallFrameSize = std::max(maximumCallFrameSize, currentAlternativeCallFrameSize);
            hasFixedSize &= alternative->m_hasFixedSize;
            if (alternative->m_minimumSize > INT_MAX)
                m_pattern.m_containsUnsignedLengthPattern = true;
        }
        
        ASSERT(minimumInputSize != UINT_MAX);
        ASSERT(maximumCallFrameSize >= initialCallFrameSize);

        disjunction->m_hasFixedSize = hasFixedSize;
        disjunction->m_minimumSize = minimumInputSize;
        disjunction->m_callFrameSize = maximumCallFrameSize;
        callFrameSize = maximumCallFrameSize;
        return error;
    }
```

the `minimumInputSize` can equal to `0xffffffff` may break the assumption of `jit`, and i think it may cause serious security problem.

so i report the bug

[Radar WebKit Bug Importer]

<rdar://problem/72849845>

[Radar WebKit Bug Importer]

<rdar://problem/72849867>

[raycp]

hello??

[Michael Saboff]

Created attachment 421660 [details]
Patch

[EWS]

Committed r273594: <https://commits.webkit.org/r273594>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 421660 [details].

[Keith Miller]

Comment on attachment 421660 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=421660&action=review

> JSTests/stress/regexp-max-size.js:36
> +function testMaxBMPRegExp() {
> +    let patt = '\u{1234}{4294967294}X';
> +    const re = RegExp(patt, 'u');
> +    return "\u{1234}\u{1234}X".match(re);
> +}
> +
> +function testTooBigBMPRegExp() {
> +    let patt = '\u{1234}{4294967294}\u{4567}';
> +    const re = RegExp(patt, 'u');
> +    return "\u{1234}\u{1234}\u{4567}".match(re);
> +}
> +
> +function testMaxNonBMPRegExp() {
> +    let patt = '\u{10234}{2147483646}\u{10100}';
> +    const re = RegExp(patt, 'u');
> +    return "\u{10234}\u{10234}\u{10100}".match(re);
> +}
> +
> +function testTooBigNonBMPRegExp() {
> +    let patt = '\u{10234}{2147483646}\u{10100}';
> +    const re = RegExp(patt, 'u');
> +    return "\u{10234}\u{10234}\u{10100}".match(re);
> +}
> +

None of these are called.

[Michael Saboff]

(In reply to Keith Miller from comment #6)
> Comment on attachment 421660 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=421660&action=review
> 
> > JSTests/stress/regexp-max-size.js:36
> > +function testMaxBMPRegExp() {
> > +    let patt = '\u{1234}{4294967294}X';
> > +    const re = RegExp(patt, 'u');
> > +    return "\u{1234}\u{1234}X".match(re);
> > +}
> > +
> > +function testTooBigBMPRegExp() {
> > +    let patt = '\u{1234}{4294967294}\u{4567}';
> > +    const re = RegExp(patt, 'u');
> > +    return "\u{1234}\u{1234}\u{4567}".match(re);
> > +}
> > +
> > +function testMaxNonBMPRegExp() {
> > +    let patt = '\u{10234}{2147483646}\u{10100}';
> > +    const re = RegExp(patt, 'u');
> > +    return "\u{10234}\u{10234}\u{10100}".match(re);
> > +}
> > +
> > +function testTooBigNonBMPRegExp() {
> > +    let patt = '\u{10234}{2147483646}\u{10100}';
> > +    const re = RegExp(patt, 'u');
> > +    return "\u{10234}\u{10234}\u{10100}".match(re);
> > +}
> > +
> 
> None of these are called.

You're right.  iCopy/paste error.  Fixing now and will post an updated patch.