Repository: simple-crypto/SCALib (language: python)

Issue:
Error in loopy_bp when mixing Signle and Multi Vars
**Describe the bug**
When having a graph as in the example loopy bp panics. The Problem occurs if more than 1 AND factor share the same single variable. Happens also with OR (but thats just a rewritten AND). But XOR works fine. So it seems to be a Problem with AND specifically

**To Reproduce**

```
import os
import scalib.attacks

os.environ["RUST_BACKTRACE"]="full"

nc = 256
n_exec = 2

fg = scalib.attacks.FactorGraph(f'''
    NC {nc}

    VAR SINGLE A
    VAR MULTI B
    VAR MULTI AnB
    VAR MULTI C
    VAR MULTI AnC

    PROPERTY A_and_B: AnB = A & B
    PROPERTY A_and_C: AnC = A & C
''',)

bp = scalib.attacks.BPState(fg,n_exec)

bp.bp_loopy(10,True)
```

**Observed behavior**
```
thread '<unnamed>' panicked at /home/flm/.cargo/registry/src/index.crates.io-6f17d22bba15001f/ndarray-0.15.6/src/zip/mod.rs:251:5:
Zip: Producer dimension mismatch, expected: [2, 256], got: [1, 256]
stack backtrace:
   0:     0x7f41e2c5b8f6 - std::backtrace_rs::backtrace::libunwind::trace::hbee8a7973eeb6c93
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/../../backtrace/src/backtrace/libunwind.rs:104:5
   1:     0x7f41e2c5b8f6 - std::backtrace_rs::backtrace::trace_unsynchronized::hc8ac75eea3aa6899
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/../../backtrace/src/backtrace/mod.rs:66:5
   2:     0x7f41e2c5b8f6 - std::sys_common::backtrace::_print_fmt::hc7f3e3b5298b1083
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/sys_common/backtrace.rs:68:5
   3:     0x7f41e2c5b8f6 - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::hbb235daedd7c6190
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/sys_common/backtrace.rs:44:22
   4:     0x7f41e2c80720 - core::fmt::rt::Argument::fmt::h76c38a80d925a410
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/core/src/fmt/rt.rs:142:9
   5:     0x7f41e2c80720 - core::fmt::write::h3ed6aeaa977c8e45
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/core/src/fmt/mod.rs:1120:17
   6:     0x7f41e2c5981f - std::io::Write::write_fmt::h78b18af5775fedb5
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/io/mod.rs:1810:15
   7:     0x7f41e2c5b6d4 - std::sys_common::backtrace::_print::h5d645a07e0fcfdbb
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/sys_common/backtrace.rs:47:5
   8:     0x7f41e2c5b6d4 - std::sys_common::backtrace::print::h85035a511aafe7a8
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/sys_common/backtrace.rs:34:9
   9:     0x7f41e2c5cda7 - std::panicking::default_hook::{{closure}}::hcce8cea212785a25
  10:     0x7f41e2c5cb09 - std::panicking::default_hook::hf5fcb0f213fe709a
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/panicking.rs:292:9
  11:     0x7f41e2c5d238 - std::panicking::rust_panic_with_hook::h095fccf1dc9379ee
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/panicking.rs:779:13
  12:     0x7f41e2c5d112 - std::panicking::begin_panic_handler::{{closure}}::h032ba12139b353db
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/panicking.rs:657:13
  13:     0x7f41e2c5bdf6 - std::sys_common::backtrace::__rust_end_short_backtrace::h9259bc2ff8fd0f76
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/sys_common/backtrace.rs:171:18
  14:     0x7f41e2c5ce70 - rust_begin_unwind
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/panicking.rs:645:5
  15:     0x7f41e0be7715 - core::panicking::panic_fmt::h784f20a50eaab275
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/core/src/panicking.rs:72:14
  16:     0x7f41e1bdfc4f - ndarray::zip::zip_dimension_check::h5a2c08dbb6c5f09d
                               at /home/flm/.cargo/registry/src/index.crates.io-6f17d22bba15001f/ndarray-0.15.6/src/zip/mod.rs:251:5
  17:     0x7f41e1be717b - ndarray::zip::Zip<(P1,),D>::and::h8664d4aca791476f
                               at /home/flm/.cargo/registry/src/index.crates.io-6f17d22bba15001f/ndarray-0.15.6/src/zip/mod.rs:681:17
  18:     0x7f41e1f0a6b6 - scalib::sasca::bp_compute::Distribution::multiply_inner::h6d1c7ec7ca575786
                               at /home/flm/01-dev/SCALib/src/scalib_ext/scalib/src/sasca/bp_compute.rs:200:25
  19:     0x7f41e1f07c29 - scalib::sasca::bp_compute::Distribution::multiply_norm::hbd49a929d1ab0ee8
                               at /home/flm/01-dev/SCALib/src/scalib_ext/scalib/src/sasca/bp_compute.rs:147:9
  20:     0x7f41e16eb5c8 - scalib::sasca::belief_propagation::BPState::propagate_var_t_single::h756628e4e013b1df
                               at /home/flm/01-dev/SCALib/src/scalib_ext/scalib/src/sasca/belief_propagation.rs:268:13
  21:     0x7f41e16edf1f - scalib::sasca::belief_propagation::BPState::propagate_var_to::hef96ff5718a3964a
                               at /home/flm/01-dev/SCALib/src/scalib_ext/scalib/src/sasca/belief_propagation.rs:375:13
  22:     0x7f41e16edc07 - scalib::sasca::belief_propagation::BPState::propagate_var::h223b44349652b080
                               at /home/flm/01-dev/SCALib/src/scalib_ext/scalib/src/sasca/belief_propagation.rs:331:9
  23:     0x7f41e16ee06a - scalib::sasca::belief_propagation::BPState::propagate_all_vars::ha1c0f332930993c8
                               at /home/flm/01-dev/SCALib/src/scalib_ext/scalib/src/sasca/belief_propagation.rs:387:13
  24:     0x7f41e16ee13b - scalib::sasca::belief_propagation::BPState::propagate_loopy_step::h8d16b4fcdff77d40
                               at /home/flm/01-dev/SCALib/src/scalib_ext/scalib/src/sasca/belief_propagation.rs:396:13
  25:     0x7f41e0c90555 - scalib_py::factor_graph::BPState::propagate_loopy_step::{{closure}}::h484cc0490cb3322c
                               at /home/flm/01-dev/SCALib/src/scalib_ext/scalib-py/src/factor_graph.rs:414:13
  26:     0x7f41e0d669c6 - scalib_py::ConfigWrapper::on_worker::{{closure}}::{{closure}}::h769220a385589a79
                               at /home/flm/01-dev/SCALib/src/scalib_ext/scalib-py/src/lib.rs:80:45
  27:     0x7f41e0cb1c0e - rayon_core::thread_pool::ThreadPool::install::{{closure}}::h9d35fea78a86d928
                               at /home/flm/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.11.0/src/thread_pool/mod.rs:110:40
  28:     0x7f41e0c60a94 - rayon_core::registry::Registry::in_worker_cold::{{closure}}::{{closure}}::h3f2ac09a8505d3ae
                               at /home/flm/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.11.0/src/registry.rs:541:21
  29:     0x7f41e0bfbfec - rayon_core::job::JobResult<T>::call::{{closure}}::h8b5206494ca09609
                               at /home/flm/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.11.0/src/job.rs:218:41
  30:     0x7f41e0d52091 - <core::panic::unwind_safe::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once::h6247c795f1bd5f93
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/core/src/panic/unwind_safe.rs:272:9
  31:     0x7f41e0c10e32 - std::panicking::try::do_call::h36ea7a8b1de623ce
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/panicking.rs:552:40
  32:     0x7f41e0c14bab - __rust_try
  33:     0x7f41e0c0e481 - std::panicking::try::h7863fb99a79ece6e
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/panicking.rs:516:19
  34:     0x7f41e0c0bd56 - std::panic::catch_unwind::h9889b49549c21074
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/panic.rs:142:14
  35:     0x7f41e0cdb028 - rayon_core::unwind::halt_unwinding::hf74fc60e6c34e4d4
                               at /home/flm/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.11.0/src/unwind.rs:17:5
  36:     0x7f41e0bf9c64 - rayon_core::job::JobResult<T>::call::h6541ca2651e93f32
                               at /home/flm/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.11.0/src/job.rs:218:15
  37:     0x7f41e0c05680 - <rayon_core::job::StackJob<L,F,R> as rayon_core::job::Job>::execute::h35b21fbc3e581e46
                               at /home/flm/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.11.0/src/job.rs:120:32
  38:     0x7f41e2bf95eb - rayon_core::job::JobRef::execute::hb38b92637b9b250b
                               at /home/flm/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.11.0/src/job.rs:64:9
  39:     0x7f41e2bdbee0 - rayon_core::registry::WorkerThread::execute::h540faff4860bc97a
                               at /home/flm/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.11.0/src/registry.rs:874:9
  40:     0x7f41e2bdbc22 - rayon_core::registry::WorkerThread::wait_until_cold::h1b3c90d5c5a91f81
                               at /home/flm/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.11.0/src/registry.rs:820:17
  41:     0x7f41e2bdb9fb - rayon_core::registry::WorkerThread::wait_until::h0a81a6536389ad3b
                               at /home/flm/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.11.0/src/registry.rs:803:13
  42:     0x7f41e2bdc48a - rayon_core::registry::main_loop::he6832d6ac7d799f7
                               at /home/flm/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.11.0/src/registry.rs:948:5
  43:     0x7f41e2bd7a96 - rayon_core::registry::ThreadBuilder::run::hb1e9feb7d07ba1eb
                               at /home/flm/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.11.0/src/registry.rs:54:18
  44:     0x7f41e2bd7eed - <rayon_core::registry::DefaultSpawn as rayon_core::registry::ThreadSpawn>::spawn::{{closure}}::hfd173b30673950b0
                               at /home/flm/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.11.0/src/registry.rs:99:20
  45:     0x7f41e2c0a406 - std::sys_common::backtrace::__rust_begin_short_backtrace::h708984f15ba69bfd
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/sys_common/backtrace.rs:155:18
  46:     0x7f41e2c0652d - std::thread::Builder::spawn_unchecked_::{{closure}}::{{closure}}::hbbc7b6fa06a26254
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/thread/mod.rs:529:17
  47:     0x7f41e2bdcd51 - <core::panic::unwind_safe::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once::h8e20dbccca081a18
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/core/src/panic/unwind_safe.rs:272:9
  48:     0x7f41e2be6e51 - std::panicking::try::do_call::hd988cc33899ee7c1
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/panicking.rs:552:40
  49:     0x7f41e2beaa2b - __rust_try
  50:     0x7f41e2be6c32 - std::panicking::try::hffec1554f08d2d7a
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/panicking.rs:516:19
  51:     0x7f41e2c05ed7 - std::panic::catch_unwind::h0416af050e66c9e8
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/panic.rs:142:14
  52:     0x7f41e2c05ed7 - std::thread::Builder::spawn_unchecked_::{{closure}}::h854fdd75187a7a37
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/thread/mod.rs:528:30
  53:     0x7f41e2be745f - core::ops::function::FnOnce::call_once{{vtable.shim}}::h8f4007ce750a169b
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/core/src/ops/function.rs:250:5
  54:     0x7f41e2c5fa15 - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::h12de4fc57affb195
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/alloc/src/boxed.rs:2015:9
  55:     0x7f41e2c5fa15 - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::h3c619f45059d5cf1
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/alloc/src/boxed.rs:2015:9
  56:     0x7f41e2c5fa15 - std::sys::unix::thread::Thread::new::thread_start::hbac657605e4b7389
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/sys/unix/thread.rs:108:17
  57:     0x7f4204d60ea7 - start_thread
  58:     0x7f4204b27a2f - clone
  59:                0x0 - <unknown>
---------------------------------------------------------------------------
PanicException                            Traceback (most recent call last)
Cell In[3], line 29
     14 fg = scalib.attacks.FactorGraph(f'''
     15     NC {nc}
     16 
   (...)
     24     PROPERTY A_and_C: AnC = A & C
     25 ''',)
     27 bp = scalib.attacks.BPState(fg,n_exec)
---> 29 bp.bp_loopy(10,True)

File ~/.local/lib/python3.8/site-packages/scalib/attacks/factor_graph.py:322, in BPState.bp_loopy(self, it, initialize_states, clear_beliefs)
    320 if initialize_states:
    321     self._inner.propagate_all_vars(get_config(), clear_beliefs)
--> 322 self._inner.propagate_loopy_step(it, get_config(), clear_beliefs)

PanicException: Zip: Producer dimension mismatch, expected: [2, 256], got: [1, 256]
```

Compiled with rustextension(... , debug=True) in setup.py

**Expected behavior**
Not panic

**Environment (please complete the following information):**
- OS: GNU/Linux 11 (bullseye)
- Python version: 3.8
- numpy version: 1.23.5
- SCALib version: 0.5.7.dev22+g0cd4430.d20240304
- How did you install SCALib? Compiled with rustextension(... , debug=True) in setup.py
- What CPU do you use? 2x Intel(R) Xeon(R) Gold 5317



Discussion / hints:
this graph I tried as a workaround shows the same behaviour
```
ID=np.arange(nc,dtype=np.uint32)
fg = scalib.attacks.FactorGraph(f'''
    NC {nc}

    TABLE ID

    VAR SINGLE A
    VAR SINGLE A2
    VAR MULTI B
    VAR MULTI AnB
    VAR MULTI C
    VAR MULTI AnC

    PROPERTY A2 = ID[A]
    PROPERTY A_and_B: AnB = A2 & B
    PROPERTY A_and_C: AnC = A & C
''',{'ID':ID})
```
It also happens with XOR Factors, but only if the variables are initilized with set_evidence
I tracked down the problem to be fixable by an explicit broadcast in
https://github.com/simple-crypto/SCALib/blob/0cd443027eb5809f3978bdedc0641f0015a41c47/src/scalib_ext/scalib/src/sasca/bp_compute.rs#L199
```
(true, _, DistrRepr::Full(ref mut v)) => {
    let dim = v.dim();
    azip!(v, d.broadcast(dim).unwrap()).for_each(|v, d| {
        *v = *v * *d;
    });
}
```

Fix patch:
diff --git a/src/scalib_ext/scalib/src/sasca/bp_compute.rs b/src/scalib_ext/scalib/src/sasca/bp_compute.rs
index 0b953eb0..04e6aee7 100644
--- a/src/scalib_ext/scalib/src/sasca/bp_compute.rs
+++ b/src/scalib_ext/scalib/src/sasca/bp_compute.rs
@@ -197,6 +197,7 @@ impl Distribution {
                         self.value = DistrRepr::Full(d.map(|d| *d));
                     }
                     (true, _, DistrRepr::Full(ref mut v)) => {
+                        let d = d.broadcast(v.dim()).unwrap();
                         azip!(v, d).for_each(|v, d| {
                             *v = *v * *d;
                         });


Test patch:
diff --git a/tests/test_factorgraph.py b/tests/test_factorgraph.py
index dfec2d4a..fb787a32 100644
--- a/tests/test_factorgraph.py
+++ b/tests/test_factorgraph.py
@@ -1326,6 +1326,23 @@ def test_mix_single_multi():
             assert np.allclose(d, d2, rtol=1e-5, atol=1e-19)
 
 
+def test_mix_single_multi2():
+    graph = f"""
+        NC 16
+        VAR SINGLE A
+        VAR MULTI B
+        VAR MULTI AnB
+        VAR MULTI C
+        VAR MULTI AnC
+
+        PROPERTY A_and_B: AnB = A & B
+        PROPERTY A_and_C: AnC = A & C
+    """
+    fg = FactorGraph(graph)
+    bp = BPState(fg, 2)
+    bp.bp_loopy(3, initialize_states=True)
+
+
 def test_ADD5():
     for nc in [13, 256]:
         n = 10