CVE-2018-0777 Code Motion

-
CVE-2018-0777 Code Motion

PoC

function opt(arr, start, end) {
    for (let i = start; i < end; i++) {
        if (i === 10) {
            i += 0;  // <<-- (a)
        }
        arr[i] = 2.3023e-320;
    }
}

function main() {
    let arr = new Array(100);
    arr.fill(1.1);

    for (let i = 0; i < 1000; i++)
        opt(arr, 0, 3);

    opt(arr, 0, 100000);
}

main();

//https://github.com/Microsoft/ChakraCore/commit/14c752b66f43ee6ecc8dd2f7f9d5378f6a91638e

IR

这是 lower 之后的部分 IR:

  Line   6: arr[i] = 2.3023e-320;
  Col    9: ^
                       StatementBoundary  #4                                  #001d 


 GLOBOPT INSTR:                        BoundCheck     0 <= s18(s9).i32                        #001d  Bailout: #001d (BailOutOnArrayAccessHelperCall)


                       TEST           s18(s9).i32, s18(s9).i32                #
                       JNSB           $L18                                    #
$L19: [helper]                                                                #
                       CALL           SaveAllRegistersAndBailOut.u64          #001d  Bailout: #001d (BailOutOnArrayAccessHelperCall)
                       JMP            $L15                                    #
$L18:                                                                         #


 GLOBOPT INSTR:     [s6[NativeFloatArray_NoMissingValues][seg: s21][segLen: s22][><].var+s18(s9).i32].var = StElemI_A  s19(s5).f64 #001d  Bailout: #001d (BailOutConventionalNativeArrayAccessOnly | BailOutOnArrayAccessHelperCall)


    [s21.u64+s18(s9).i32*8+24].f64 = MOVSD  s19(s5).f64                       #

检查 i >= 0 之后就直接赋值, 没有检查 i 的上界是否小于 arr 的 length, 从而达到 OOB 的效果.

需要研究的是什么条件导致了上界检查的移除.

Chakra 中的循环优化

因为循环在流图中会成环, 为了处理环形依赖, 就有了 Prepass 机制(自然循环具有唯一的循环头, 且一定收敛), 先对整个循环进行一个初步的分析, 在二次分析时, 首先 Merge PrePass 的信息, 然后进行循环体分析.

在循环中很常见的一个优化就是不变量外提 (LICM): 将循环过程不变的语句或表达式外提取循环体外. 例如在 lower 之后, 数组赋值操作被拆分成多条指令, 例如:

  • Array 类型检查 (BailOnNotArray)
  • Array head 及 head length (LdIndir)
  • 赋值下标与 head length 的判断 (BoundCheck)

存放这块检查代码的位置在 Chakra 内部称为 LandingPad, 就是循环执行前的入口基本块. 它们都可能被外提, 但满足的条件不同:

  • 前两种需要满足的条件是: 检查循环中 Array 类型, head, head length 不变. 这里是类似于 Type Inference 的优化, 如果实际类型不符就 Kill 掉有关信息, 在 TurboFan 中就出现过 Kill 失误导致类型混淆的例子

  • BoundCheck 外提需要满足的条件是 {数组下标上界 <= arr.length && 下标下界 >= 0}

    • 根据相对边界 (RelativeBound) 计算上下界, 也就是 [start, end - 1]
    • 没有相对边界的情况下根据归纳变量 (InductionVariable) 计算上下界, 最大循环次数 = (end - start ) / i 的最小递增幅度; 归纳变量的初值是下界, 上界 = 下界 + (最大循环次数 -1) * 归纳变量的最大递增幅度
    • 脑洞: 这里用下界去计算上界, 会不会有什么问题???

具体问题, 具体分析

结合 PoC 来看, 它的优化也应该分为两个阶段.

1. LoopPrePass

  1. GlobOpt::TrackIntSpecializedAddSubConstant 函数用于处理某个变量加减一个常量的情况; 当某个变量的 Value 与其 landingPadValue 一致时, 那么会将该变量添加到 inductionVariables 中

    也就是说该变量必须没有在其他地方被修改过, 例如: 如果出现 i = 10 的情况, 是不会贝添加到 inductionVariables 的 

                InductionVariable *inductionVariable;
            if(!inductionVariables->TryGetReference(sym->m_id, &inductionVariable))
            {
                // Only track changes in the current loop's prepass. In subsequent prepasses, the info is only being propagated
                // for use by the parent loop, so changes in the current loop have already been tracked.
                if(prePassLoop != currentBlock->loop)
                {
                    updateInductionVariableValueNumber = false;
                    break;
                }

                // Ensure that the sym is live in the landing pad, and that its value has not changed in an unknown way yet
                Value *const landingPadValue = currentBlock->loop->landingPad->globOptData.FindValue(sym);
                if(!landingPadValue || srcValueNumber != landingPadValue->GetValueNumber())
                {
                    updateInductionVariableValueNumber = false;
                    break;
                }
                inductionVariables->Add(
                    InductionVariable(sym, dstValue->GetValueNumber(), addSubConstantInfo->Offset()));
                break;
            }

  2. GlobOpt::TypeSpecializeIntDst 设置 IntBound

    Ps. 这段注释很重要. 

        const IntBounds *dstBounds = nullptr;
    if(addSubConstantInfo && !addSubConstantInfo->SrcValueIsLikelyConstant() && DoTrackRelativeIntBounds())
    {
        Assert(!ignoredIntOverflowForCurrentInstr);

        // Track bounds for add or sub with a constant. For instance, consider (b = a + 2). The value of 'b' should track that
        // it is equal to (the value of 'a') + 2. Additionally, the value of 'b' should inherit the bounds of 'a', offset by
        // the constant value.
        if(!valueType.IsInt() || !isValueInfoPrecise)
        {
            newMin = INT32_MIN;
            newMax = INT32_MAX;
        }
        dstBounds =
            IntBounds::Add(
                addSubConstantInfo->SrcValue(),
                addSubConstantInfo->Offset(),
                isValueInfoPrecise,
                IntConstantBounds(newMin, newMax),
                alloc);
    }

  3. GlobOpt::DetermineLoopCount 使用 IntBound (-0x80000000, 0x7ffffffe) 计算LoopCount. 生成LoopCount的条件是循环变量有相对边界 (在 2 中满足) 或者有常量边界且 {常量边界上界 < 0x7fffffff - 1 && 常量下界 > -0x80000000 + 1}

    TODO: 不明白需要常量边界做什么. 这部分代码太长, 还需要细读

    ChakraCore.dll!GlobOpt::DetermineLoopCount(Loop * const loop) Line 1387 C++ 
ChakraCore.dll!BasicBlock::MergePredBlocksValueMaps(GlobOpt * globOpt) Line 4865 C++
ChakraCore.dll!GlobOpt::OptBlock(BasicBlock * block) Line 491 C++
ChakraCore.dll!GlobOpt::ForwardPass() Line 407 C++

2. Normal Analysis

  1. GlobOpt::OptConstFoldBinary 进行二元运算指令中的常量折叠, 产生了 {i = 10}

    在这里打破了开头的重要假设, 继续优化一定会出现问题

  2. 接下来 merge 信息, ValueInfo::MergeLikelyIntValueInfo 中 IntBound(-0x80000000, 0x7ffffffe) 和 IntConstant(10) 合并得到 IntRange(-0x80000000, 0x7ffffffe), 导致丢弃了相对边界信息

    这里 IntConstant(10) 的使用方式显然是有问题的

  3. DetermineSymBoundOffsetOrValueRelativeToLandingPad 确定循环变量相对于 LandingPadValue 的offset. 此时 i 没有相对边界, 会直接取下界 (-0x80000000) 作为offset (相当于循环初值未知)

    ChakraCore.dll!GlobOpt::DetermineSymBoundOffsetOrValueRelativeToLandingPad(StackSym * const sym, const bool landingPadValueIsLowerBound, ValueInfo * const valueInfo, const IntBounds * const bounds, GlobOptBlockData * const landingPadGlobOptBlockData, int * const boundOffsetOrValueRef) Line 1272 C++
  ChakraCore.dll!GlobOpt::DetermineArrayBoundCheckHoistability(bool needLowerBoundCheck, bool needUpperBoundCheck, GlobOpt::ArrayLowerBoundCheckHoistInfo & lowerHoistInfo, GlobOpt::ArrayUpperBoundCheckHoistInfo & upperHoistInfo, const bool isJsArray, StackSym * const indexSym, Value * const indexValue, const IntConstantBounds & indexConstantBounds, StackSym * const headSegmentLengthSym, Value * const headSegmentLengthValue, const IntConstantBounds & headSegmentLengthConstantBounds, Loop * const headSegmentLengthInvariantLoop, bool & failedToUpdateCompatibleLowerBoundCheck, bool & failedToUpdateCompatibleUpperBoundCheck) Line 2839 C++
  ChakraCore.dll!GlobOpt::OptArraySrc(IR::Instr * * const instrRef) Line 14204 C++
  ChakraCore.dll!GlobOpt::OptInstr(IR::Instr * & instr, bool * isInstrRemoved) Line 2538 C++
  ChakraCore.dll!GlobOpt::OptBlock(BasicBlock * block) Line 537 C++
  ChakraCore.dll!GlobOpt::ForwardPass() Line 407 C++
  ChakraCore.dll!GlobOpt::Optimize() Line 222 C++
  ChakraCore.dll!Func::TryCodegen() Line 432 C++

  4. 比较 index(-0x80000000, 0x7fffffff) + offset(-0x80000000) < length(0, 0x7ffffff) 恒成立, 如果这里的 offset 不是错误的, 那么这个等式将不恒成立

                            // The info in the landing pad may be better than the info in the current block due to changes made to the
                        // index sym inside the loop. Check if the bound check we intend to hoist is unnecessary in the landing pad.
                        if(!ValueInfo::IsLessThanOrEqualTo(
                                hoistInfo.IndexValue(),
                                hoistInfo.IndexConstantBounds().LowerBound(),
                                hoistInfo.IndexConstantBounds().UpperBound(),
                                hoistInfo.HeadSegmentLengthValue(),
                                hoistInfo.HeadSegmentLengthConstantBounds().LowerBound(),
                                hoistInfo.HeadSegmentLengthConstantBounds().UpperBound(),
                                hoistInfo.Offset()))
                        { ...

  5. 外提 BoundCheck 

                if(!eliminatedUpperBoundCheck)
            {
                eliminatedUpperBoundCheck = true;

                ArrayUpperBoundCheckHoistInfo &hoistInfo = upperBoundCheckHoistInfo;
                if(hoistInfo.HasAnyInfo())
                {
                    BasicBlock *hoistBlock;
                    if(hoistInfo.CompatibleBoundCheckBlock())
                    {
                        hoistBlock = hoistInfo.CompatibleBoundCheckBlock();

                        TRACE_PHASE_INSTR(
                            Js::Phase::BoundCheckHoistPhase,
                            instr,
                            _u("Hoisting array upper bound check into existing bound check instruction in block %u\n"),
                            hoistBlock->GetBlockNum());
                        TESTTRACE_PHASE_INSTR(
                            Js::Phase::BoundCheckHoistPhase,
                            instr,
                            _u("Hoisting array upper bound check into existing bound check instruction\n"));
                    }
                    else
                    { ...

Root Cause

综上:

  • LoopPrePass 中 IntBound 有相对边界, 生成了 LoopCount
  • 正常分析中因为常量折叠 IntBound 被 merge 成了 IntRange, 失去相对边界, 使 offset 取到 -0x80000000, 导致分析认为 index < length, 从而不生成针对数组长度的检查. 而实际 i 的值可能超过 length

Patch

在 GlobOpt::OptConstFoldUnary 和 GlobOpt::OptConstFoldBinary 后添加了如下代码: 

+    for (Loop * loop = this->currentBlock->loop; loop; loop = loop->parent)
+    {
+        InductionVariable *iv = nullptr;
+        if (loop->inductionVariables && loop->inductionVariables->TryGetReference(dstSym->m_id, &iv))
+        {
+            iv->SetChangeIsIndeterminate();
+        }
+    }

InductionVariable 指归纳变量, 即循环中的 i 等; iv->SetChangeIsIndeterminate() 的意思是该归纳变量的改变不可被预判.

总结

形成这个 bug 的一个重要条件就是流图中具有环形依赖, 不管是哪个编译器, 多多少少都会有跟这个特性相关的 bug. 为了避免它带来的负面影响, 比如在 TurboFan 中如果遇到循环, 也有对应的算法来保证它的正确性. 但是即便如此也避免不了这些编译器中一些极其刁钻的 bug 出现.

 

Comments

  1. Ashley RosaDecember 26, 2019 at 4:54 AM

    Is your Binance account closed and unable to open? If you’re dealing with queries and troubles that create closing of the Binance account,you can always contact the team of elite professionals who are always at your support to assist you. Reaching them is the right decision as the team knows how to handle all queries and troubles in no time. You can call on Binance phone number which is always functional and users can have conversation with the team anytime for availing quality and result-driven solutions from the professionals.

    ReplyDelete
  2. Ashley RosaJanuary 29, 2020 at 4:54 AM

    Ledger comes with its own set of advantages and to take access of them can be availed if you know how to carry forward the processing of Ledger functioning. Withdrawing forked coins is a major error and to deal with such queries, you can always take help from the team of elite professionals who are there to guide you. Instead of worrying about issues, you can always take the help from the team via Ledger support number which is functional all the time for guidance

    ReplyDelete

Post a Comment

Popular posts from this blog

CVE-2017-5121 Escape Analysis

-
CVE-2017-5121 Escape Analysis PoC var func0 = function(f) { var o = { a: {}, b: { ba: {baa: 0, bab :[]}, bb: {}, bc: {bca: {bcaa: 0, bcab: 0, bcac: this}}, } }; o.b.bc.bca.bcab = 0; o.b.bb.bba = Object.toString(o.b.ba.bab); }; function g(){ while(true) func0(); } g(); Escape Analysis in V8 Analyze Source of Fields of Allocates: Traverse the IR graph(along Effect edge) to get the source of fields of Allocate void EscapeAnalysis::RunObjectAnalysis() { virtual_states_.resize(graph()->NodeCount()); ZoneDeque<Node*> queue(zone()); queue.push_back(graph()->start()); ZoneVector<Node*> danglers(zone()); while (!queue.empty()) { Node* node = queue.back(); queue.pop_back(); status_analysis_->SetInQueue(node->id(), false); if (Process(node)) { for (Edge edge : node->use_edges()) { Node* use = edge.from(); if (status_
Read more

Three UaFs when iterating through HTMLFormElement::associatedElements

-
First of all, lets look at CVE-2017-2460. It was reported in 2017-Jan-19. PoC: ================================================================= <script> function go() {   object.name = "foo";   input.autofocus = true;   output.appendChild(input);   form.submit(); } function eventhandler() {   for(var i=0;i<100;i++) {     var e = document.createElement("input");     form.appendChild(e);   } } </script> <body onload=go()> <form id="form"> <object id="object"> <output id="output">a</output> <input id="input" onfocus="eventhandler()"> ================================================================= Patch: @@ -506,7 +506,9 @@ bool HTMLObjectElement::appendFormData(FormDataList& encoding, bool)       if (name().isEmpty())           return false;  -    Widget* widget = pluginWidget();  +    // Use PluginLoadingPolicy::DoNotLoad here or
Read more