search

simple-crypto / SCALib

Side-Channel Analysis Library
GNU Affero General Public License v3.0
74 stars 19 forks source link

Generic factors don't work on exclusively single vars with n_exec > 1 #144

Closed F-Lehmann closed 3 months ago

F-Lehmann commented 9 months ago

Describe the bug Gereic factors throw an error when only working on Single Vars when n_exec > 1

To Reproduce

import os
import numpy as np
import itertools as it
import scalib.attacks

os.environ["RUST_BACKTRACE"]="full"

nc = 2
n_exec = 2

fg = scalib.attacks.FactorGraph(
    f'''
    NC {nc}

    VAR SINGLE A
    VAR SINGLE B
    VAR SINGLE C

    GENERIC SINGLE XOR

    PROPERTY XOR(A,B,C)
    ''',
)

def xor(a,b):
    return a ^ b

XOR = []
for a,b in it.product(range(nc),repeat=2):
    XOR.append([a,b,a^b])

bp = scalib.attacks.BPState(fg,n_exec,gen_factors={'XOR':scalib.attacks.GenFactor.sparse_functional(np.array(XOR,dtype=np.uint32))})
bp.bp_loopy(1,True)

Observed behavior

thread '<unnamed>' panicked at /home/flm/.cargo/registry/src/index.crates.io-6f17d22bba15001f/ndarray-0.15.6/src/dimension/mod.rs:361:5:
assertion failed: index < dim
stack backtrace:
   0:     0x7f46abeae2d6 - std::backtrace_rs::backtrace::libunwind::trace::hbee8a7973eeb6c93
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/../../backtrace/src/backtrace/libunwind.rs:104:5
   1:     0x7f46abeae2d6 - std::backtrace_rs::backtrace::trace_unsynchronized::hc8ac75eea3aa6899
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/../../backtrace/src/backtrace/mod.rs:66:5
   2:     0x7f46abeae2d6 - std::sys_common::backtrace::_print_fmt::hc7f3e3b5298b1083
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/sys_common/backtrace.rs:68:5
   3:     0x7f46abeae2d6 - <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:     0x7f46abed2550 - core::fmt::rt::Argument::fmt::h76c38a80d925a410
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/core/src/fmt/rt.rs:142:9
   5:     0x7f46abed2550 - core::fmt::write::h3ed6aeaa977c8e45
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/core/src/fmt/mod.rs:1120:17
   6:     0x7f46abeac28f - std::io::Write::write_fmt::h78b18af5775fedb5
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/io/mod.rs:1810:15
   7:     0x7f46abeae0b4 - std::sys_common::backtrace::_print::h5d645a07e0fcfdbb
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/sys_common/backtrace.rs:47:5
   8:     0x7f46abeae0b4 - std::sys_common::backtrace::print::h85035a511aafe7a8
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/sys_common/backtrace.rs:34:9
   9:     0x7f46abeaf787 - std::panicking::default_hook::{{closure}}::hcce8cea212785a25
  10:     0x7f46abeaf4e9 - std::panicking::default_hook::hf5fcb0f213fe709a
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/panicking.rs:292:9
  11:     0x7f46abeafc18 - std::panicking::rust_panic_with_hook::h095fccf1dc9379ee
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/panicking.rs:779:13
  12:     0x7f46abeafab9 - std::panicking::begin_panic_handler::{{closure}}::h032ba12139b353db
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/panicking.rs:649:13
  13:     0x7f46abeae7d6 - std::sys_common::backtrace::__rust_end_short_backtrace::h9259bc2ff8fd0f76
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/sys_common/backtrace.rs:171:18
  14:     0x7f46abeaf850 - rust_begin_unwind
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/panicking.rs:645:5
  15:     0x7f46ab2ce6c5 - core::panicking::panic_fmt::h784f20a50eaab275
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/core/src/panicking.rs:72:14
  16:     0x7f46ab2ce783 - core::panicking::panic::hb837a5ebbbe5b188
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/core/src/panicking.rs:144:5
  17:     0x7f46ab4a72b1 - ndarray::impl_methods::<impl ndarray::ArrayBase<S,D>>::slice_move::hf001cecba9eb9bdc
  18:     0x7f46ab466d46 - <core::iter::adapters::map::Map<I,F> as core::iter::traits::iterator::Iterator>::fold::h52fe3fbcfa865c75
  19:     0x7f46ab3efcf1 - <alloc::vec::Vec<T> as alloc::vec::spec_from_iter::SpecFromIter<T,I>>::from_iter::h0151e22b4a84fab1
  20:     0x7f46ab3d9e3c - scalib::sasca::belief_propagation::BPState::propagate_factor::h084c959fb01628c0
  21:     0x7f46ab3e05d2 - scalib::sasca::belief_propagation::BPState::propagate_loopy_step::hfb357cb84008d46c
  22:     0x7f46ab2e45aa - <rayon_core::job::StackJob<L,F,R> as rayon_core::job::Job>::execute::h54a39e42a2890d7d
  23:     0x7f46ab2ca663 - rayon_core::registry::WorkerThread::wait_until_cold::h0cb5c006910a6535
  24:     0x7f46abe86272 - rayon_core::registry::ThreadBuilder::run::h24054205afd460cf
  25:     0x7f46abe8c298 - std::sys_common::backtrace::__rust_begin_short_backtrace::ha9154974abccab37
  26:     0x7f46abe8c9d1 - core::ops::function::FnOnce::call_once{{vtable.shim}}::hde87593c29237eb7
  27:     0x7f46abeb23f5 - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::h12de4fc57affb195
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/alloc/src/boxed.rs:2015:9
  28:     0x7f46abeb23f5 - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::h3c619f45059d5cf1
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/alloc/src/boxed.rs:2015:9
  29:     0x7f46abeb23f5 - std::sys::unix::thread::Thread::new::thread_start::hbac657605e4b7389
                               at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/std/src/sys/unix/thread.rs:108:17
  30:     0x7f46d8207ea7 - start_thread
  31:     0x7f46d7fcea2f - clone
  32:                0x0 - <unknown>
---------------------------------------------------------------------------
PanicException                            Traceback (most recent call last)
Cell In[1], line 35
     32     XOR.append([a,b,a^b])
     34 bp = scalib.attacks.BPState(fg,n_exec,gen_factors={'XOR':scalib.attacks.GenFactor.sparse_functional(np.array(XOR,dtype=np.uint32))})
---> 35 bp.bp_loopy(1,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: assertion failed: index < dim

I belive the problem is in "src/scalib_ext/scalib/src/sasca/belief_propagation.rs:893" iterating over nmulti when that is wrong here.

Expected behavior Not panic

Environment (please complete the following information):

cassiersg commented 9 months ago

Thanks for reporting the bug !

For anybody looking to fix it: the issue seems to be that in function factor_gen_factor (https://github.com/simple-crypto/SCALib/blob/main/src/scalib_ext/scalib/src/sasca/belief_propagation.rs#L876), we always run a loop for i in 0..nmulti, while it should not be done when all the variables adjacent to the factor are SINGLE, in which case we should have only one iteration. This case can be detected using the factor.multi attribute.

The factor_gen_factor function should probably be refactored while doing so.

F-Lehmann commented 9 months ago

With your hint I wasa able to come up with a simple (but ugly) fix that works for me. I changed the loop to this: for i in 0..(if factor.multi {nmulti} else {1}) {