[Bug report] BE2 bigintfxd unsigned reverse loops wrap and access out of bounds at the full-width boundary

Library Questions
1

Hi OpenFHE team,

I would like to report a memory-safety bug family in the optional BE2 fixed-width big-integer backend (MATHBACKEND=2 / WITH_BE2).

Summary

The bigintfxd backend contains several reverse loops that use an unsigned index (size_t or usint) together with a condition of the form:

i >= lower_bound

When lower_bound == 0, the iteration at i == 0 is followed by i--, which wraps to the maximum unsigned value. The loop condition then remains true, and the next array access uses an out-of-bounds index.

I confirmed this dynamically on OpenFHE 1.5.1 built with:

  • MATHBACKEND=2
  • WITH_BE2=ON
  • clang 14
  • AddressSanitizer and UndefinedBehaviorSanitizer

Using values whose m_MSB reaches the entire fixed limb array, I reproduced out-of-bounds behavior in multiple public methods:

  1. GetInternalRepresentation(): stack-buffer-underflow after the loop index wraps from 0 to SIZE_MAX
  2. ConvertToDouble(): unsigned wraparound in (m_nSize - i - 1) followed by an invalid read
  3. Add(): stack-buffer-underflow in the full-width operand copy loop when adding 1 to a full-width sparse value
  4. Mul(): the public multiply path reaches the same bug in the private helper MulByUintToInt()

So this is not just a theoretical code pattern. At least four public or publicly reachable methods can be driven into real out-of-bounds behavior under BE2.

The four paths above were dynamically reproduced. AddEq() and ConvertToLongDouble() contain the same unsafe index pattern and are included below as source-confirmed additional affected paths; I did not dynamically exercise those two methods in this report.

The default OpenFHE build is not directly affected because:

  • WITH_BE2 defaults to OFF
  • MATHBACKEND defaults to 4

Environment

  • OpenFHE version: 1.5.1
  • Local source revision used for reproduction: ed361af22049007db2107e7c69bcff209e8c420d
  • Configuration: MATHBACKEND=2, WITH_BE2=ON
  • OS: Linux x86_64
  • Compiler: clang 14.0.0
  • Sanitizers: AddressSanitizer, UndefinedBehaviorSanitizer

Representative build command:

cmake -S . -B build-be2-asan \
  -DMATHBACKEND=2 \
  -DWITH_BE2=ON \
  -DCMAKE_BUILD_TYPE=Debug \
  -DBUILD_UNITTESTS=OFF \
  -DBUILD_EXAMPLES=OFF \
  -DBUILD_BENCHMARKS=OFF \
  -DWITH_OPENMP=OFF \
  -DCMAKE_CXX_FLAGS='-fsanitize=address,undefined -fno-omit-frame-pointer -g -O0'

cmake --build build-be2-asan -j

Minimal reproduction

The reproducer below constructs a BE2 BigInteger whose binary width equals BigIntegerBitLength, so the value occupies the entire fixed limb array.

It then calls individual methods by mode:

  • get-internal-repr
  • convert-to-double
  • add
  • mul
#include "math/hal/bigintfxd/ubintfxd.h"

#include <iostream>
#include <string>

using bigintfxd::BigInteger;

static BigInteger MakeFullWidthValue() {
    return BigInteger::FromBinaryString(std::string(BigIntegerBitLength, '1'));
}

static BigInteger MakeFullWidthSparseValue() {
    return BigInteger::FromBinaryString(
        "1" + std::string(BigIntegerBitLength - 1, '0'));
}

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "usage: " << argv[0]
                  << " <get-internal-repr|convert-to-double|add|mul>" << std::endl;
        return 2;
    }

    const std::string mode = argv[1];

    if (mode == "get-internal-repr") {
        BigInteger value = MakeFullWidthValue();
        std::cout << "msb=" << value.GetMSB()
                  << " bitlength=" << BigIntegerBitLength << std::endl;
        std::cout << "about to call GetInternalRepresentation()" << std::endl;
        auto repr = value.GetInternalRepresentation();
        std::cout << "repr-prefix=" << repr.substr(0, 32) << std::endl;
        return 0;
    }

    if (mode == "convert-to-double") {
        BigInteger value = MakeFullWidthValue();
        std::cout << "msb=" << value.GetMSB()
                  << " bitlength=" << BigIntegerBitLength << std::endl;
        std::cout << "about to call ConvertToDouble()" << std::endl;
        auto converted = value.ConvertToDouble();
        std::cout << "converted=" << converted << std::endl;
        return 0;
    }

    if (mode == "add") {
        BigInteger value = MakeFullWidthSparseValue();
        std::cout << "msb=" << value.GetMSB()
                  << " bitlength=" << BigIntegerBitLength << std::endl;
        std::cout << "about to call Add() with a full-width sparse value plus 1"
                  << std::endl;
        auto sum = value.Add(BigInteger(1));
        std::cout << "sum-msb=" << sum.GetMSB() << std::endl;
        return 0;
    }

    if (mode == "mul") {
        BigInteger value = MakeFullWidthValue();
        std::cout << "msb=" << value.GetMSB()
                  << " bitlength=" << BigIntegerBitLength << std::endl;
        std::cout << "about to call Mul() with two full-width values" << std::endl;
        auto prod = value.Mul(value);
        std::cout << "prod-msb=" << prod.GetMSB() << std::endl;
        return 0;
    }

    std::cerr << "unknown mode: " << mode << std::endl;
    return 2;
}

For the default BE2 alias:

  • BigIntegerBitLength = 3500
  • integral_dtype = uint32_t
  • m_uintBitLength = 32
  • m_nSize = ceil(3500 / 32) = 110

With the all-ones binary string of length 3500, the resulting value has m_MSB = 3500, so:

ceilIntByUInt(m_MSB) = 110

This makes the problematic loop bound collapse to zero:

m_nSize - ceilIntByUInt(m_MSB) = 110 - 110 = 0

Expected behavior

These BE2 big-integer methods should not rely on unsigned reverse loops whose termination condition becomes i >= 0 when the active limb range reaches the front of the fixed array.

At minimum, a full-width value should not cause:

  • unsigned wraparound of the loop index
  • out-of-bounds reads
  • out-of-bounds writes
  • loss of normal loop termination before the resulting out-of-bounds access

Actual behavior

GetInternalRepresentation()

Running:

./repro get-internal-repr

produces:

msb=3500 bitlength=3500
about to call GetInternalRepresentation()
.../ubintfxd.h:1006:35: runtime error: index 18446744073709551615 out of bounds
...
ERROR: AddressSanitizer: stack-buffer-underflow
READ of size 4
    #0  ... BigIntegerFixedT<unsigned int, 3500u>::GetInternalRepresentation(...)

ConvertToDouble()

Running:

./repro convert-to-double

produces:

msb=3500 bitlength=3500
about to call ConvertToDouble()
.../ubintfxd.cpp:1559:39: runtime error: index 4294967295 out of bounds
...
ERROR: AddressSanitizer: SEGV on unknown address
READ memory access
    #0  ... BigIntegerFixedT<unsigned int, 3500u>::ConvertToDouble() const

Add()

Running:

./repro add

produces:

msb=3500 bitlength=3500
about to call Add() with a full-width sparse value plus 1
.../ubintfxd.cpp:229:27: runtime error: index 18446744073709551615 out of bounds
...
ERROR: AddressSanitizer: stack-buffer-underflow
READ of size 4
    #0  ... BigIntegerFixedT<unsigned int, 3500u>::Add(...)

Mul()

Running:

./repro mul

produces:

msb=3500 bitlength=3500
about to call Mul() with two full-width values
.../ubintfxd.cpp:1849:40: runtime error: index 18446744073709551615 out of bounds
...
ERROR: AddressSanitizer: stack-buffer-underflow
READ of size 4
    #0  ... BigIntegerFixedT<unsigned int, 3500u>::MulByUintToInt(...)
    #1  ... BigIntegerFixedT<unsigned int, 3500u>::Mul(...)

Impact

This is a real memory-safety issue in the optional BE2 backend.

The confirmed effects include:

  • out-of-bounds accesses outside the fixed internal limb array
  • reported as stack-buffer-underflow by ASan in the supplied stack-local reproducer
  • defined unsigned wraparound of loop indices, followed by undefined out-of-bounds array access
  • sanitizer-confirmed abnormal termination in public operations

Source inspection also shows potential out-of-bounds writes in loop bodies that reuse the wrapped index, although the supplied sanitizer runs terminate at the preceding invalid reads.

For example, MulByUintToInt() uses the wrapped index for both a read from m_value[i] and a write to ans->m_value[i] inside the loop body. The first invalid read already makes execution undefined, so the out-of-bounds write is a source-confirmed risk rather than a separately observed sanitizer result.

This is configuration-specific because BE2 is not the default backend, but it is still part of the supported codebase and can be enabled through normal build options.

Cause analysis

The common cause is unsigned reverse iteration over a range that may start at index 0.

GetInternalRepresentation()

size_t ceilInt  = ceilIntByUInt(this->m_MSB);
size_t minIndex = static_cast<size_t>(m_nSize - ceilInt);

for (size_t i = m_nSize - 1; i >= minIndex; i--) {
    ret += std::to_string(m_value[i]);
}

When ceilInt == m_nSize, minIndex == 0, so the loop is effectively:

for (size_t i = 109; i >= 0; i--)

After the i == 0 iteration, i-- wraps to SIZE_MAX, the condition remains true, and the next m_value[i] access is out of bounds.

ConvertToDouble() / ConvertToLongDouble()

usint ceilInt = m_nSize - ceilIntByUInt(m_MSB);
for (usint i = 0; (m_nSize - i - 1) >= ceilInt; i++) {
    result += static_cast<double>(this->m_value[m_nSize - i - 1]) * power;
}

When ceilInt == 0, the condition is evaluated in unsigned arithmetic. After the last valid iteration, m_nSize - i - 1 wraps to a very large unsigned value instead of becoming negative, so the loop continues and indexes past the front of the array.

Add() / AddEq() / Mul() / MulByUintToInt()

Examples:

for (i = m_nSize - 1; i >= m_nSize - ceilIntB; i--)

for (size_t i = m_nSize - 1; i >= m_nSize - ceilInt; i--)

for (; i >= endVal; i--)

All of these become unsafe when the lower bound is 0.

In the Add(fullWidthSparse, 1) reproducer, ceilIntB == 1, so the first loop processes only the least-significant limb. Because no carry is produced, execution then enters the later copy loop for the remaining limbs of the full-width operand. There, ceilIntA == m_nSize, so the lower bound becomes 0 and the unsigned index wraps after the i == 0 iteration.

The trigger condition is straightforward:

lower_bound = m_nSize - ceilIntByUInt(m_MSB)

and for a full-width value:

ceilIntByUInt(m_MSB) = m_nSize
lower_bound = 0

OpenFHE already contains a nearby developer comment in Add() noting that this pattern appears to match previously fixed sign/unsigned loop bugs:

// DTS: TODO: verify that the sign/unsigned compare is valid here...

That comment is consistent with the dynamic crashes above.

The Mul() reproducer also exercises a result-overflow case. Even if that operation is unsupported and should be rejected for fixed-width arithmetic, it still must not cause out-of-bounds memory access.

Relevant source locations

Suggested direction

The underlying fix should be to remove unsigned reverse loops of the form:

for (i = end; i >= begin; i--)

when i is unsigned.

Safer options would be:

for (size_t off = 0; off < count; ++off) {
    size_t i = m_nSize - 1 - off;
    ...
}

For the forward loops in ConvertToDouble() / ConvertToLongDouble(), it would be safer to avoid unsigned subtraction in the loop condition and instead iterate by active limb count, for example:

const size_t count = ceilIntByUInt(m_MSB);
for (size_t off = 0; off < count; ++off) {
    const size_t i = m_nSize - 1 - off;
    ...
}

Because the same bug pattern appears in several methods, I think the best fix is a small, systematic cleanup of the affected BE2 loops rather than patching only one call site.

Question

Would you prefer a narrow fix for the currently confirmed call sites, or a broader BE2 audit for all unsigned reverse loops with lower bounds derived from ceilIntByUInt()?

Reported by Jiang Chao, Beijing University of Posts and Telecommunications

2

We are planning to remove backend 2 in the next major release (not v1.6, but probably v2.0). Does this bug affect backend 4, which is the main multiprecision backend in OpenFHE?