Null-pointer dereference
Description
In many functions, for example in unsafe_evaluate_multiply_add, the context is assigned from one of the arguments similarly to the following snippet:
Builder* ctx = left.context ? left.context : to_mul.context;The pointer ctx is then used later, sometimes only in some branches. When both left and to_mul are constants, it can happen that both their contexts are the null pointer, leading to issues should the pointer be dereferenced later. In many cases, this should not occur normally, as only constant bigfield elements should have a null-pointer context, and, for example, the method operator* would not call unsafe_evaluate_multiply_add if both factors are constant.
However, there are also cases in which a null-pointer dereference can occur. One example is the function msub_div, an extract of whose implementation we show below:
template <typename Builder, typename T>
bigfield<Builder, T> bigfield<Builder, T>::msub_div(const std::vector<bigfield>& mul_left, const std::vector<bigfield>& mul_right, const bigfield& divisor, const std::vector<bigfield>& to_sub, bool enable_divisor_nz_check)
{
Builder* ctx = divisor.context;
// ...
bool products_constant = true;
// ...
// Compute the sum of products
for (size_t i = 0; i < num_multiplications; ++i) {
const native mul_left_native(uint512_t(mul_left[i].get_value() % modulus_u512).lo);
const native mul_right_native(uint512_t(mul_right[i].get_value() % modulus_u512).lo);
product_native += (mul_left_native * -mul_right_native);
products_constant = products_constant && mul_left[i].is_constant() && mul_right[i].is_constant();
}
// Compute the sum of to_sub
native sub_native(0);
bool sub_constant = true;
for (const auto& sub : to_sub) {
sub_native += (uint512_t(sub.get_value() % modulus_u512).lo);
sub_constant = sub_constant && sub.is_constant();
}
// ...
// If everything is constant, then we just return the constant
if (sub_constant && products_constant && divisor.is_constant()) {
return bigfield(ctx, uint256_t(result_value.lo.lo));
}
// Create the result witness
bigfield result = create_from_u512_as_witness(ctx, result_value.lo);
// ...
}As can be seen here, the ctx pointer is taken directly from divisor.context. Thus, if divisor is a constant, this could be the null pointer. There then is a separate branch that returns early, for the case of constant arguments. But it is only taken if all the arguments are constants, so this will not be used if divisor is a constant but one of the summands or factors is not. In that case, create_from_u512_as_witness will be called with a null pointer as ctx. However, in the HasPlookup<Builder> case, that function will dereference ctx:
template <typename Builder, typename T>
bigfield<Builder, T> bigfield<Builder, T>::create_from_u512_as_witness(Builder* ctx,
const uint512_t& value,
const bool can_overflow,
const size_t maximum_bitlength)
{
// ...
if constexpr (HasPlookup<Builder>) {
// ...
ctx->create_big_add_gate({ limb_1.witness_index,
limb_2.witness_index,
limb_3.witness_index,
prime_limb.witness_index,
shift_1,
shift_2,
shift_3,
-1,
0 },
true);
// ...
} else {
return bigfield(witness_t(ctx, fr(limbs[0] + limbs[1] * shift_1)),
witness_t(ctx, fr(limbs[2] + limbs[3] * shift_1)),
can_overflow,
maximum_bitlength);
}
}Thus, calling msub_div with a constant divisor and at least one other argument nonconstant will cause a null-pointer dereference in create_from_u512_as_witness (at least in the HasPlookup<Builder> case), leading to undefined behavior and most likely a crash.
The following test case demonstrates the crash:
static void test_zellic_ctx_crash()
{
auto builder = Builder();
fq_ct witness_one = fq_ct::create_from_u512_as_witness(&builder, uint256_t(1));
fq_ct constant_one(1);
info("\nwitness_one:");
for (size_t limb_index = 0; limb_index < 4 ; limb_index++) {
info("Limb ", limb_index, ": ", witness_one.binary_basis_limbs[limb_index]);
}
info("Prime limb: ", witness_one.prime_basis_limb);
info("Context: ", witness_one.context);
info("is_constant: ", witness_one.is_constant());
info("\nconstant_one:");
for (size_t limb_index = 0; limb_index < 4 ; limb_index++) {
info("Limb ", limb_index, ": ", constant_one.binary_basis_limbs[limb_index]);
}
info("Prime limb: ", constant_one.prime_basis_limb);
info("Context: ", constant_one.context);
info("is_constant: ", constant_one.is_constant());
fq_ct::msub_div({witness_one}, {witness_one}, constant_one, {witness_one}, true);
bool result = CircuitChecker::check(builder);
EXPECT_EQ(result, true);
}When the call to msub_div is replaced by
fq_ct::msub_div({witness_one}, {witness_one}, witness_one, {witness_one}, true);or
fq_ct::msub_div({constant_one}, {constant_one}, constant_one, {constant_one}, true);the test case succeeds as expected. However, the version above, where the divisor is constant but the summand and factors are not, crashes:
% ./build/bin/stdlib_primitives_tests '--gtest_filter=stdlib_bigfield/1.zellicctxcrash'
Running main() from /home/user/aztec-packages/barretenberg/cpp/build/_deps/gtest-src/googletest/src/gtest_main.cc
Note: Google Test filter = stdlib_bigfield/1.zellicctxcrash
[==========] Running 1 test from 1 test suite.
[----------] Global test environment set-up.
[----------] 1 test from stdlib_bigfield/1, where TypeParam = bb::UltraCircuitBuilder_<bb::UltraArith<bb::field<bb::Bn254FrParams> > >
[ RUN ] stdlib_bigfield/1.zellicctxcrash
In create_from_u512_as_witness, ctx=0x7ffe9694d7b0
witness_one:
Limb 0: { 0x0000000000000000000000000000000000000000000000000000000000000001 < 0x00000000000000000000000000000000000000000000000fffffffffffffffff }
Limb 1: { 0x0000000000000000000000000000000000000000000000000000000000000000 < 0x00000000000000000000000000000000000000000000000fffffffffffffffff }
Limb 2: { 0x0000000000000000000000000000000000000000000000000000000000000000 < 0x00000000000000000000000000000000000000000000000fffffffffffffffff }
Limb 3: { 0x0000000000000000000000000000000000000000000000000000000000000000 < 0x0000000000000000000000000000000000000000000000000003ffffffffffff }
Prime limb: 0x0000000000000000000000000000000000000000000000000000000000000001
Context: 0x7ffe9694d7b0
is_constant: 0
constant_one:
Limb 0: { 0x0000000000000000000000000000000000000000000000000000000000000001 < 0x0000000000000000000000000000000000000000000000000000000000000002 }
Limb 1: { 0x0000000000000000000000000000000000000000000000000000000000000000 < 0x0000000000000000000000000000000000000000000000000000000000000001 }
Limb 2: { 0x0000000000000000000000000000000000000000000000000000000000000000 < 0x0000000000000000000000000000000000000000000000000000000000000001 }
Limb 3: { 0x0000000000000000000000000000000000000000000000000000000000000000 < 0x0000000000000000000000000000000000000000000000000000000000000001 }
Prime limb: 0x0000000000000000000000000000000000000000000000000000000000000001
Context: 0
is_constant: 1
In create_from_u512_as_witness, ctx=0
zsh: segmentation fault ./build/bin/stdlib_primitives_testsImpact
Dereferencing a null pointer is undefined behavior, so it can result in incorrect computation or most likely a crash.
Recommendations
In the case of msub_div and other functions with the analogous problem, we recommend to take the context passed as an argument to other functions from an argument that has a non--null-pointer context, similarly to how it is done in unsafe_evaluate_multiply_add or internal_div. We have not done an exhaustive search for functions with this problem, so we recommend to review the code for cases analogous to msub_div.
In general, we recommend to assert that the context pointer is not the null pointer before using it, to prevent undefined behavior and obtain an error that is easier to debug.