[Bug report] `buildLookupTable` triggers integer UB at 63/64-bit output widths on LP64

[CCYJ1014]

I would like to report a reproducible undefined-behavior bug in HElib's public buildLookupTable(...) helper when the caller requests top-end output widths on this LP64 build.

The issue affects both:

• unsigned output mode: sign_out == 0, beginning at nbits_out == 63
• signed two's-complement output mode: sign_out == 1, beginning at nbits_out == 64

On the checked-out HElib revision, buildLookupTable(...) implements its output bounds and mask with host-word-sized 1L / 1UL expressions even though nbits_out is exposed as a general public bit width.

Summary

buildLookupTable(...) exposes nbits_out as a public parameter and documents that outputs are "truncated to nbits_out bits", but it does not reject these top-end widths on this LP64 build.

In the checked-out implementation:

• unsigned output mode computes:

largest_value = (1L << nbits_out) - 1;
...
uvalue &= ((1UL << nbits_out) - 1UL);

• signed output mode computes:

largest_value = (1L << (nbits_out - 1)) - 1;
smallest_value = -(1L << (nbits_out - 1));
...
uvalue &= ((1UL << nbits_out) - 1UL);

On this LP64 build (long / unsigned long are 64 bits), the boundary behavior is:

• nbits_out = 62, sign_out = 0: control case succeeds
• nbits_out = 63, sign_out = 0: UBSan reports signed overflow in (1L << 63) - 1
• nbits_out = 63, sign_out = 1: control case succeeds
• nbits_out = 64, sign_out = 0: UBSan reports full-width shifts in both the unsigned-mode bound computation and the output mask
• nbits_out = 64, sign_out = 1: UBSan reports signed-boundary overflow / negation and the later full-width output-mask shift

These reproductions use a valid BGV context whose slot degree is large enough to hold 64 packed bits.

I reproduced the issue with:

• nbits_in = 1
• scale_in = 0
• scale_out = 0
• m = 257, p = 5, giving ea_degree = 256

That context avoids the separate "slot too small" confounder, so the failure is isolated to the bit-width arithmetic inside buildLookupTable(...).

Environment

• HElib checked-out revision: 3e337a66a91a92d49de6a9505340826b0eb71081
• OS: Linux x86_64
• ABI / word size: LP64 (sizeof(long) == 8, sizeof(unsigned long) == 8, CHAR_BIT == 8)
• Compiler: Clang 14.0.0
• Sanitizers: AddressSanitizer and UndefinedBehaviorSanitizer
• Linked libraries: system NTL and GMP

Representative build command:

clang++-14 -std=c++17 -g -O1 -fno-omit-frame-pointer \
  -fsanitize=address,undefined \
  -I /tmp/helib-system-headers-v1 \
  -I HElib/dependencies/json \
  -I HElib/include \
  -I build-helib-sys-asan3/src \
  fuzz/helib_buildlookuptable_nbits_probe.cpp \
  -L build-helib-sys-asan3/lib \
  -Wl,-rpath,/home/sht/agent-fuzzing/build-helib-sys-asan3/lib \
  build-helib-sys-asan3/lib/libhelib.a \
  -lntl -lgmp -lpthread -ldl -lm \
  -o fuzz/bin/helib_buildlookuptable_nbits_probe

Minimal reproduction

#include <functional>
#include <iostream>
#include <vector>

#include <helib/Context.h>
#include <helib/EncryptedArray.h>
#include <helib/tableLookup.h>

int main(int argc, char** argv)
{
  long nbits_out = 64;
  long sign_out = 0;
  long m = 257;
  long p = 5;

  if (argc > 1)
    nbits_out = std::stol(argv[1]);
  if (argc > 2)
    sign_out = std::stol(argv[2]);
  if (argc > 3)
    m = std::stol(argv[3]);
  if (argc > 4)
    p = std::stol(argv[4]);

  auto context = helib::ContextBuilder<helib::BGV>()
                     .m(m)
                     .p(p)
                     .r(1)
                     .bits(200)
                     .c(2)
                     .build();

  const helib::EncryptedArray& ea = context.getEA();
  std::vector<helib::zzX> table;

  std::cout << "ea_degree=" << ea.getDegree() << '\n';
  std::cout << "about to call buildLookupTable"
            << " nbits_out=" << nbits_out
            << " sign_out=" << sign_out << std::endl;

  helib::buildLookupTable(table,
                          [](double x) { return x; },
                          1,   // nbits_in
                          0,   // scale_in
                          0,   // sign_in
                          nbits_out,
                          0,   // scale_out
                          sign_out,
                          ea);

  std::cout << "table_size=" << table.size() << std::endl;
  return 0;
}

Run the unsigned case:

ASAN_OPTIONS=detect_leaks=0 UBSAN_OPTIONS=print_stacktrace=1 \
stdbuf -o0 -e0 ./fuzz/bin/helib_buildlookuptable_nbits_probe 64 0 257 5

Representative output:

ea_degree=256
about to call buildLookupTable nbits_out=64 sign_out=0
/home/sht/agent-fuzzing/HElib/src/tableLookup.cpp:164:25: runtime error: shift exponent 64 is too large for 64-bit type 'long'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /home/sht/agent-fuzzing/HElib/src/tableLookup.cpp:164:25 in
/home/sht/agent-fuzzing/HElib/src/tableLookup.cpp:194:21: runtime error: shift exponent 64 is too large for 64-bit type 'unsigned long'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /home/sht/agent-fuzzing/HElib/src/tableLookup.cpp:194:21 in
table_size=2

Run the signed case:

ASAN_OPTIONS=detect_leaks=0 UBSAN_OPTIONS=print_stacktrace=1 \
stdbuf -o0 -e0 ./fuzz/bin/helib_buildlookuptable_nbits_probe 64 1 257 5

Representative output:

ea_degree=256
about to call buildLookupTable nbits_out=64 sign_out=1
/home/sht/agent-fuzzing/HElib/src/tableLookup.cpp:161:45: runtime error: signed integer overflow: -9223372036854775808 - 1 cannot be represented in type 'long'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /home/sht/agent-fuzzing/HElib/src/tableLookup.cpp:161:45 in
/home/sht/agent-fuzzing/HElib/src/tableLookup.cpp:162:22: runtime error: negation of -9223372036854775808 cannot be represented in type 'long'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /home/sht/agent-fuzzing/HElib/src/tableLookup.cpp:162:22 in
/home/sht/agent-fuzzing/HElib/src/tableLookup.cpp:194:21: runtime error: shift exponent 64 is too large for 64-bit type 'unsigned long'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /home/sht/agent-fuzzing/HElib/src/tableLookup.cpp:194:21 in
table_size=2

Control case:

ASAN_OPTIONS=detect_leaks=0 UBSAN_OPTIONS=print_stacktrace=1 \
stdbuf -o0 -e0 ./fuzz/bin/helib_buildlookuptable_nbits_probe 63 1 257 5

Representative output:

ea_degree=256
about to call buildLookupTable nbits_out=63 sign_out=1
table_size=2

Unsigned near-boundary control / failure split:

ASAN_OPTIONS=detect_leaks=0 UBSAN_OPTIONS=print_stacktrace=1 \
stdbuf -o0 -e0 ./fuzz/bin/helib_buildlookuptable_nbits_probe 62 0 257 5

ASAN_OPTIONS=detect_leaks=0 UBSAN_OPTIONS=print_stacktrace=1 \
stdbuf -o0 -e0 ./fuzz/bin/helib_buildlookuptable_nbits_probe 63 0 257 5

Representative output:

ea_degree=256
about to call buildLookupTable nbits_out=62 sign_out=0
table_size=2

ea_degree=256
about to call buildLookupTable nbits_out=63 sign_out=0
/home/sht/agent-fuzzing/HElib/src/tableLookup.cpp:164:39: runtime error: signed integer overflow: -9223372036854775808 - 1 cannot be represented in type 'long'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /home/sht/agent-fuzzing/HElib/src/tableLookup.cpp:164:39 in
table_size=2

Actual behavior

On this LP64 build, buildLookupTable(...) first reaches UB at:

• nbits_out == 63 in unsigned output mode
• nbits_out == 64 in signed output mode

At nbits_out == 64, both modes also reach the later full-width 1UL << nbits_out mask expression.

The reproducer uses a valid BGV context whose slot degree is already large enough for 64 output bits, so the observed UB is not a consequence of insufficient slot capacity.

Expected behavior

If buildLookupTable(...) does not intend to support these host-word-width boundary cases on this LP64 build, it should reject them explicitly before any full-width shift or signed-boundary arithmetic is evaluated.

If these widths are intended to be supported, the implementation should use arithmetic, bound, and intermediate representations capable of representing the requested output domain, with explicit full-width handling for the output mask.

Impact

This is a public API boundary bug in a helper used to build table-lookup data for encrypted computation.

An honest caller can request top-end output widths through documented public parameters and trigger undefined behavior in the library on a valid high-degree BGV context on this LP64 build.

I have not yet established a downstream wrong-result case from the returned table, but under recovering UBSan the current implementation evaluates invalid shifts and signed overflow and then continues to return a table.

Cause analysis

On this LP64 build, buildLookupTable(...) treats nbits_out as a general public bit width, but the implementation computes the output bounds and mask with host-word-sized long / unsigned long expressions.

The boundary cases differ slightly:

• in unsigned mode, the full 63-bit output range 0 .. 2^63 - 1 still fits within the nonnegative range of long on this build, but the current expression (1L << 63) - 1 constructs that bound through arithmetic for which UBSan reports signed overflow. At nbits_out == 63, the problem is not a shift count equal to the host width; under this Clang/C++17 build, UBSan reports the subsequent subtraction in (1L << 63) - 1 as the overflowing operation;

• unsigned 64-bit output requires the range 0 .. 2^64 - 1, which cannot be represented by the signed long bound used here, while both 1L << 64 and the later 1UL << 64 mask are full-width invalid shifts;

• signed 64-bit output has a representable target range on this LP64 build, but the current endpoint construction

  largest_value = (1L << (nbits_out - 1)) - 1;
  smallest_value = -(1L << (nbits_out - 1));

reaches the signed boundary through subtraction / negation that UBSan reports as overflow, and the same full-width mask expression is evaluated later.

Concretely, the implementation uses:

largest_value = (1L << nbits_out) - 1;
...
uvalue &= ((1UL << nbits_out) - 1UL);

for unsigned mode, and:

largest_value = (1L << (nbits_out - 1)) - 1;
smallest_value = -(1L << (nbits_out - 1));

for signed mode.

The public header documents that outputs are truncated to nbits_out bits and only warns that each slot must be large enough to hold that many bits. It does not document any host-word restriction excluding the first failing widths observed here (63 in unsigned mode and 64 in signed mode), or otherwise constrain nbits_out to a range that makes these host-word computations safe.

Relevant source locations

• include/helib/tableLookup.h

  • buildLookupTable(...) public declaration: lines 59-94
  • GitHub blob:
    

    HElib/include/helib/tableLookup.h

    Lines 59 to 94 in 3e337a6

    	* The buildLookupTable function builds a lookup table T, which can be
    	* used in conjunction with the tableLookup function above. The size of
    	* T will be 2^{nbits_in}. For every signed integer x with bit-size
    	* 'nbits_in', we will have
    	* T[x] = f(x * 2^{scale_in}) * 2^{-scale_out}),
    	* rounded to the nearest integer and truncated to 'nbits_out' bits.
    	* The bits are packed inside the slots, so it is assumed that each
    	* slot has enough room to fit these many bits. (Otherwise we only
    	* keep as many low-order bits as fit in a slot.)
    	*
    	* SATURATED ARITHMETIC:
    	* Applications of f that return a result that is too large to represent
    	* in the output format will be converted to the maximum representable
    	* value. Similarly, Applications of f that return a result that is too
    	* small will be converted to the minimal representable value. (This
    	* applies also to applications of f that return infinites, NaNs will
    	* just be mapped to zero.) For this to work correctly, you should be
    	* working with standard IEEE arithmetic...which will be the case on
    	* almost all platforms.
    	*
    	* EXAMPLE:
    	*
    	* buildLookupTable(T, [](double x){ return 1/x;},
    	* nbits_in, scale_in, nbits_out, scale_out, sign_out, ea)
    	*
    	* will build a lookup table for inversion.
    	**/
    	void buildLookupTable(std::vector<zzX>& T, // encoded result is returned in T
    	std::function<double(double)> f,
    	long nbits_in, // number of precision bits
    	long scale_in, // scaling factor
    	long sign_in, // 1: 2's complement signed, 0: unsigned
    	long nbits_out,
    	long scale_out,
    	long sign_out,
    	const EncryptedArray& ea);

• src/tableLookup.cpp

  • buildLookupTable(...): lines 139-198
  • signed largest_value / smallest_value: lines 160-162
  • unsigned largest_value: line 164
  • output mask: line 194
  • GitHub blob:
    

    HElib/src/tableLookup.cpp

    Lines 139 to 198 in 3e337a6

    	void buildLookupTable(std::vector<zzX>& T, // encoded result is returned in T
    	std::function<double(double)> f,
    	long nbits_in, // number of precision bits
    	long scale_in, // scaling factor
    	long sign_in, // 1: 2's complement signed, 0: unsigned
    	long nbits_out,
    	long scale_out,
    	long sign_out,
    	const EncryptedArray& ea)
    	{
    	HELIB_TIMER_START;
    	// tables of size > 2^{16} are not supported
    	assertTrue(nbits_in <= 16, "tables of size > 2^{16} are not supported");
    	long sz = 1L << nbits_in;
    	T.resize(sz);
    	double pow2_scale_in = pow2_double(scale_in); // 2^{nbits_in}
    	double pow2_neg_scale_out = pow2_double(-scale_out); // 2^{-nbits_out}
    	// Compute the largest and smallest values that can be in T
    	long largest_value, smallest_value;
    	if (sign_out) { // values in T are encoded in 2's complement
    	largest_value = (1L << (nbits_out - 1)) - 1;
    	smallest_value = -(1L << (nbits_out - 1));
    	} else { // values in T are all non-negative
    	largest_value = (1L << nbits_out) - 1;
    	smallest_value = 0;
    	}
    	for (long i = 0; i < sz; i++) { // Compute the entries of T
    	long x;
    	if (sign_in) { // indexes into T are in 2's complement
    	long sign_bit = (1L << (nbits_in - 1)) & i;
    	x = i - 2 * sign_bit;
    	} else
    	x = i; // indexes into T are all non-negative
    	// Compute the value that should go in the table as rounded double
    	double scaled_x = double(x) * pow2_scale_in;
    	double y = round(f(scaled_x) * pow2_neg_scale_out);
    	// saturated arithmetic (set to smallest or largest values)
    	// NOTE: this should work fine even if y is an infinity
    	long value;
    	if (std::isnan(y))
    	value = 0;
    	else if (y > largest_value)
    	value = largest_value;
    	else if (y < smallest_value)
    	value = smallest_value;
    	else
    	value = y;
    	// convert to unsigned and mask to nbits_out bits
    	unsigned long uvalue = value;
    	uvalue &= ((1UL << nbits_out) - 1UL); // keep only bottom nbits_out bits
    	packConstant(T[i], uvalue, nbits_out, ea);
    	}
    	}

Suggested direction

Two defensible fixes appear possible:

• reject unsupported host-word-width boundary cases explicitly on this LP64 build; or
• implement the bound calculations and output mask with arithmetic and bound types that can represent the requested output domain, then define the supported full-width signed/unsigned semantics explicitly. If these widths are intended to be supported, that work needs to cover not only the bound and full-width mask computations but also the intermediate representation: in particular, the full unsigned 64-bit output domain cannot be represented by the current signed long value intermediate.

Any rejection threshold should ideally be derived from the width and range of the actual host types rather than hard-coded as 63 / 64.

Reported by Jiang Chao, Beijing University of Posts and Telecommunications