AddOverflow seems non-deterministic

[ek0]

Version and Platform (required):

• Binary Ninja Version: 5.4.9584-dev Personal (9e1eeb9a)
• Edition: Non-Commercial
• OS: Windows
• OS Version: Windows 11
• CPU Architecture: x64

Bug Description:
Take the following C++ code built with MSVC:

void Foo() {
  {
    binja::Ref<binja::LowLevelILFunction> llil =
        new binja::LowLevelILFunction{arch};

    auto id =
        llil->AddOverflow(4, llil->Const(4, 0xFFFFFFFF), llil->Const(4, 1));
    auto insn = llil->GetExpr(id);
    ASSERT_EQ(insn.operation, LLIL_ADD_OVERFLOW);

    auto ovf1 = insn.As<LLIL_ADD_OVERFLOW>();
    auto left1 = ovf1.GetLeftExpr();
    auto right1 = ovf1.GetRightExpr();
    binja::LogWarn("[BN-BUG] First AddOverflow sub-expressions:");
    binja::LogWarn(
        "[BN-BUG]   left:  exprIdx=%zu op=%d size=%zu val=%lld",
        left1.exprIndex, static_cast<int>(left1.operation), left1.size,
        static_cast<long long>(left1.As<LLIL_CONST>().GetConstant()));
    binja::LogWarn(
        "[BN-BUG]   right: exprIdx=%zu op=%d size=%zu val=%lld",
        right1.exprIndex, static_cast<int>(right1.operation), right1.size,
        static_cast<long long>(right1.As<LLIL_CONST>().GetConstant()));
  }

  {
    binja::Ref<binja::LowLevelILFunction> llil =
        new binja::LowLevelILFunction{arch};

    auto const_a = llil->Const(4, 0xFFFFFFFF);
    auto const_b = llil->Const(4, 1);
    auto id = llil->AddOverflow(4, const_a, const_b);
    auto insn = llil->GetExpr(id);
    ASSERT_EQ(insn.operation, LLIL_ADD_OVERFLOW);

    auto ovf1 = insn.As<LLIL_ADD_OVERFLOW>();
    auto left1 = ovf1.GetLeftExpr();
    auto right1 = ovf1.GetRightExpr();
    binja::LogWarn("[BN-BUG] First AddOverflow sub-expressions:");
    binja::LogWarn(
        "[BN-BUG]   left:  exprIdx=%zu op=%d size=%zu val=%lld",
        left1.exprIndex, static_cast<int>(left1.operation), left1.size,
        static_cast<long long>(left1.As<LLIL_CONST>().GetConstant()));
    binja::LogWarn(
        "[BN-BUG]   right: exprIdx=%zu op=%d size=%zu val=%lld",
        right1.exprIndex, static_cast<int>(right1.operation), right1.size,
        static_cast<long long>(right1.As<LLIL_CONST>().GetConstant()));
  }
}

Running it as a plugin will give the following (you need a binary view open, it can be empty):

[Default] [BN-BUG] First AddOverflow sub-expressions:
[Default] [BN-BUG]   left:  exprIdx=0 op=18 size=4 val=1
[Default] [BN-BUG]   right: exprIdx=0 op=18 size=4 val=1
[Default] [BN-BUG] First AddOverflow sub-expressions:
[Default] [BN-BUG]   left:  exprIdx=1 op=18 size=4 val=1
[Default] [BN-BUG]   right: exprIdx=0 op=18 size=4 val=4294967295

It is unclear why the first snippet is using the same expression index as both operand when the line of code is:

auto id =
        llil->AddOverflow(4, llil->Const(4, 0xFFFFFFFF), llil->Const(4, 1));
    auto insn = llil->GetExpr(id);

You can switch the ASSERT_EQ with regular asserts. This has been ripped out of a bn-test unit test.

[bdash]

Thanks so much for the detailed report!

binaryninja-api/lowlevelilinstruction.cpp

Lines 3542 to 3545 in 0a62658

	ExprId LowLevelILFunction::AddOverflow(size_t size, ExprId left, ExprId right, const ILSourceLocation& loc)
	{
	return AddExprWithLocation(LLIL_ADD_OVERFLOW, loc, size, left, right);
	}

binaryninja-api/lowlevelil.cpp

Lines 361 to 362 in 0a62658

	ExprId LowLevelILFunction::AddExprWithLocation(BNLowLevelILOperation operation, uint64_t addr, uint32_t sourceOperand,
	size_t size, uint32_t flags, ExprId a, ExprId b, ExprId c, ExprId d)

The bug here is that the call to AddExprWithLocation is missing the flags parameter, so the operands end up in the wrong arguments (left in flags, right in a). Since b is omitted, it defaults to zero. I'm guessing this should pass 0 for flags like most of the other expression functions on LowLevelILFunction.

The different results are due to the sub-expressions being created in different orders with your two examples, and how that interacts with the default value for the second operand being 0.