Finding Overflows with Simulation

I have built my largest program in Concrete and for large parts it works great, but there seem to be some problems I want to debug using Concrete’s simulation feature and especially the overflow detection. Now to my problem:

As part of the program, I compute the following:

b = a % np.array([1, 2, 3]).reshape([-1, 1, 1])

where a is an encrypted 2D matrix.

It works perfectly fine and produces the correct outputs. The values in the inpuset for the compilation are much larger than the input used for the computation. When I run the simulation and values of a are negative, I get the following warning for the above code-line:

WARNING at loc(…): overflow happened during addition in simulation

When I try to model a similar computation as a LookupTable I get the same warning:

table = fhe.LookupTable([i % 3 for i in range(0, 100)] + [i % 3 for i in range(-100, 0)]).

It seems to me that I always get the warning, when using negative inputs to LookupTables, but the documentation says that should work? My issue is, that I now get many warnings probably not relevant, and I have a hard time finding the real overflows.

Is there something I can do about that, or do I misunderstand something here?

Thank you so much for all the help in the forum!

Minimal example:

from concrete import fhe
import numpy as np

a = -np.random.randint(1, 10, (2, 2))
print(a)
print(a.shape)

table = fhe.LookupTable([i % 3 for i in range(0, 100)] + [i % 3 for i in range(-100, 0)])

def m(a):
    b = a % np.array([1, 2, 3]).reshape([-1, 1, 1])
    #b = table[a]
    return b


print("CLEAR")
b = m(a)
print(b)

print("FHE")
compiler = fhe.Compiler(m, {"a": "encrypted"})
inputset = [
    np.random.randint(-100, 100, (2, 2)) for _ in range(100)
]
circuit = compiler.compile(inputset, fhe_simulation=True, detect_overflow_in_simulation=True)
print(circuit)

b = circuit.simulate(a)
print(b)

Hello @hallojs ,

Thanks for reporting.

Indeed a table lookup on a negative signed integer will warn with a false positive overflow in addition operators. This is because the way we encode signed integers, basically we use the “padding” bit as the sign bit and before the table lookup we make a addition to “realign” the encoding. You can easily see it with the compiler_verbose_mode=True (with the following example that is your example that I simplified again).

from concrete import fhe
import numpy as np

table = fhe.LookupTable([i % 3 for i in range(0, 100)] + [i % 3 for i in range(-100, 0)])

def m(a):
    b = table[a]
    return b

compiler = fhe.Compiler(m, {"a": "encrypted"})
inputset = [
    np.random.randint(-100, 100) for _ in range(100)
]
fhe.Configuration
circuit = compiler.compile(inputset, compiler_verbose_mode=True, fhe_simulation=True, detect_overflow_in_simulation=True)

a = -np.random.randint(1, 10)
b = circuit.simulate(a)

print(f"Input: {a} Output: {b}")
// -----// IR Dump After FHEToTFHEScalar (fhe-to-tfhe-scalar) ('builtin.module' operation) //----- //
module {
  func.func @m(%arg0: !TFHE.glwe<sk?> {TFHE.OId = 0 : i32}) -> !TFHE.glwe<sk?> {
    %cst = arith.constant dense<"0x0000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000010000000000000002000000000000000000000000000000020000000000000000000000000000000100000000000000020000000000000000000000000000000100000000000000020000000000000000000000000000000100000000000000020000000000000000000000000000000100000000000000020000000000000000000000000000000100000000000000020000000000000000000000000000000100000000000000020000000000000000000000000000000100000000000000020000000000000000000000000000000100000000000000020000000000000000000000000000000100000000000000020000000000000000000000000000000100000000000000020000000000000000000000000000000100000000000000020000000000000000000000000000000100000000000000020000000000000000000000000000000100000000000000020000000000000000000000000000000100000000000000020000000000000000000000000000000100000000000000020000000000000000000000000000000100000000000000020000000000000000000000000000000100000000000000020000000000000000000000000000000100000000000000020000000000000000000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000000000000000000001000000000000000200000000000000"> : tensor<256xi64>
    %0 = "TFHE.encode_expand_lut_for_bootstrap"(%cst) {isSigned = true, outputBits = 2 : i32, polySize = 42 : i32} : (tensor<256xi64>) -> tensor<42xi64>
    %c128_i9 = arith.constant 128 : i9
    %1 = arith.extsi %c128_i9 : i9 to i64
    %c55_i64 = arith.constant 55 : i64
    %2 = arith.shli %1, %c55_i64 : i64
    %3 = "TFHE.add_glwe_int"(%arg0, %2) {TFHE.OId = 1 : i32} : (!TFHE.glwe<sk?>, i64) -> !TFHE.glwe<sk?>
    %4 = "TFHE.keyswitch_glwe"(%3) {TFHE.OId = 2 : i32, key = #TFHE.ksk<sk?, sk?, -1, -1>} : (!TFHE.glwe<sk?>) -> !TFHE.glwe<sk?>
    %5 = "TFHE.bootstrap_glwe"(%4, %0) {TFHE.OId = 2 : i32, key = #TFHE.bsk<sk?, sk?, -1, -1, -1, -1>} : (!TFHE.glwe<sk?>, tensor<42xi64>) -> !TFHE.glwe<sk?>
    return %5 : !TFHE.glwe<sk?>
  }
}

Sadly we loose the information and the addition make an unexpected warning…

I created this issue if you want to track the bug fix.

1 Like

Then a fix proposal that should land on main soon, then in nightlies in few days. Hope that will help you.

1 Like

Thank you for the fast reply and the nice explanation!

I track the issue on GitHub and will try the nightlies as soon as they are available. As I’m a bit under time pressure, I will try to find my overflow problems without the overflow detection meanwhile.

I have to say, I truly enjoy using Concrete!