Index out of bounds error in belief propagation

[vvasseur]

Describe the bug An index out of bounds error occurs during belief propagation. This error is triggered when setting a constant sum constraint as a public variable in the factor graph definition.

To Reproduce

from scalib.attacks import FactorGraph, BPState
import numpy as np

np.random.seed(0)

def normalize_distr(x):
    return x / x.sum(axis=-1, keepdims=True)

def make_distri(nc, n):
    return normalize_distr(np.random.randint(1, 10000000, (n, nc)).astype(np.float64))

nc = 256
g = f"""
NC {nc}
PUB SINGLE s
VAR MULTI a0
VAR MULTI a1
VAR MULTI a2
PROPERTY s = a0 + a1 + a2
"""

n = 1
fg = FactorGraph(g)
bp = BPState(fg, n, {"s": 42})

bp.set_evidence("a0", make_distri(nc, n))
bp.set_evidence("a1", make_distri(nc, n))
bp.set_evidence("a2", make_distri(nc, n))

bp.bp_loopy(2, True)

Observed behavior The script crashes with the following error:

thread '<unnamed>' panicked at 'index out of bounds: the len is 2 but the index is 2', scalib/src/sasca/belief_propagation.rs:806:22
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Traceback (most recent call last):
  File "~/sca/bug.py", line 33, in <module>
    bp.bp_loopy(2, True)
  File "~/sca/pyenv/lib/python3.12/site-packages/scalib/attacks/factor_graph.py", line 326, in bp_loopy
    self._inner.propagate_loopy_step(it, get_config(), clear_beliefs)
pyo3_runtime.PanicException: index out of bounds: the len is 2 but the index is 2

Additional observations

1. This error only occurs when setting the constant constraint as a public variable (in this case, PUB SINGLE). There is no problem if s is defined as a VAR SINGLE and set_evidence is used with a distribution containing all zeros except for one 1.
2. When using two terms a0, a1 instead of three, there is no error but the constraint does not seem to be taken into account at all.

Environment:

• OS: Arch Linux
  • Python version: Python 3.12.4
  • numpy version: 1.26.4
  • SCALib version: 0.5.8
  • How did you install SCALib? PyPI
  • What CPU do you use? 12th Gen Intel i7-1265U

[cassiersg]

Hello and thanks for the bug report.

I wrote a fix in #171 . Before merging it, I'd like to be sure that it also fixes the other issues you identified. Could you provide example scripts for these ?

[vvasseur]

Thanks for looking into this so quickly.

Here is a script showing the other issue I mentioned:

from scalib.attacks import FactorGraph, BPState
import numpy as np

nc = 256
g_pub = f"""
NC {nc}
PUB SINGLE s
VAR MULTI a0
VAR MULTI a1
PROPERTY s = a0 + a1
"""

g_var = f"""
NC {nc}
VAR SINGLE s
VAR MULTI a0
VAR MULTI a1
PROPERTY s = a0 + a1
"""

n = 1
fg_pub = FactorGraph(g_pub)
fg_var = FactorGraph(g_var)

bp_pub = BPState(fg_pub, n, {"s": 42})
bp_pub.set_evidence("a0", np.array([[1.0 if i == 41 else 0.0 for i in range(nc)]]))

bp_var = BPState(fg_var, n)
bp_var.set_evidence("s", np.array([1.0 if i == 42 else 0.0 for i in range(nc)]))
bp_var.set_evidence("a0", np.array([[1.0 if i == 41 else 0.0 for i in range(nc)]]))

bp_pub.bp_loopy(100, True)
bp_var.bp_loopy(100, True)

print("PUB:", np.argmax(bp_pub.get_distribution("a1")))
print("VAR:", np.argmax(bp_var.get_distribution("a1")))

This script runs on version 0.5.8 (pre-fix). With only two variables (a0 and a1), there is no out of bounds error. But there is still an issue:

PUB: 255
VAR: 1

The VAR version correctly identifies 1 as the most likely value for a1 (since 41 + 1 = 42), while the PUB version incorrectly suggests 255.

[cassiersg]

Thanks! That other bug is fixed. I'll merge the PR and have a release before the end of the month.