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

Issue:
Run rust tests
run `cargo test` when doing `make test` and in CI.


Discussion / hints:
and also run examples

Fix patch:
diff --git a/CHANGELOG.rst b/CHANGELOG.rst
index 9687d02b..acd5e00e 100644
--- a/CHANGELOG.rst
+++ b/CHANGELOG.rst
@@ -5,6 +5,8 @@ Changelog
 Not released
 ------------
 
+* Fix bug in ``rank_estimation``.
+
 v0.5.0 (2023/02/08)
 -------------------
 
diff --git a/examples/aes_simulation/README.rst b/examples/README.rst
similarity index 86%
rename from examples/aes_simulation/README.rst
rename to examples/README.rst
index 11b75978..f8d8feed 100644
--- a/examples/aes_simulation/README.rst
+++ b/examples/README.rst
@@ -1,15 +1,18 @@
-Simulated unprotected AES examples
-==================================
+SCALib examples
+===============
+
+Simulated unprotected AES
+-------------------------
 
 This directory contains an example of attack against an simple AES
 implementation leaking with an HW model and with Gaussian noise addition. We
 note that this code can simply be reused for a real implementation by replacing
 the simulated traces by real measurements. The example can simply be executed
-by running `main.py` with:
+by running `aes_simulation.py` with:
 
 .. code-block::
 
-    python3 main.py
+    python3 aes_simulation.py
 
 
 The simulations goes in multiple steps: 
diff --git a/examples/aes_simulation/main.py b/examples/aes_simulation.py
similarity index 99%
rename from examples/aes_simulation/main.py
rename to examples/aes_simulation.py
index 4611faa6..10932075 100644
--- a/examples/aes_simulation/main.py
+++ b/examples/aes_simulation.py
@@ -6,7 +6,8 @@
 from utils import sbox, gen_traces
 import numpy as np
 
-if __name__ == "__main__":
+
+def main():
     nc = 256
     npoi = 2
 
@@ -134,3 +135,7 @@
     print("")
     print(f"        {lrmin} < {lr} < {lrmax}")
     print("")
+
+
+if __name__ == "__main__":
+    main()
diff --git a/examples/aes_simulation/utils.py b/examples/utils.py
similarity index 100%
rename from examples/aes_simulation/utils.py
rename to examples/utils.py
diff --git a/pyproject.toml b/pyproject.toml
index 33f96612..77ae087a 100644
--- a/pyproject.toml
+++ b/pyproject.toml
@@ -21,6 +21,7 @@ addopts = [
 testpaths = [
     "tests",
     "scalib",
+    "examples",
 ]
 
 [tool.cibuildwheel]
diff --git a/src/scalib_ext/ranklib/Cargo.toml b/src/scalib_ext/ranklib/Cargo.toml
index eeb625e7..35245b7b 100644
--- a/src/scalib_ext/ranklib/Cargo.toml
+++ b/src/scalib_ext/ranklib/Cargo.toml
@@ -2,7 +2,7 @@
 name = "ranklib"
 version = "0.1.0"
 authors = ["Gaëtan Cassiers <gaetan.cassiers@uclouvain.be>"]
-edition = "2018"
+edition = "2021"
 
 [features]
 ntl = []
diff --git a/src/scalib_ext/ranklib/src/lib.rs b/src/scalib_ext/ranklib/src/lib.rs
index 5ef6f3be..d72ecc67 100644
--- a/src/scalib_ext/ranklib/src/lib.rs
+++ b/src/scalib_ext/ranklib/src/lib.rs
@@ -31,8 +31,8 @@ pub struct RankEstimation {
 }
 impl RankEstimation {
     pub fn new(min: f64, est: f64, max: f64) -> Self {
-        debug_assert!(min <= est);
-        debug_assert!(est <= max);
+        debug_assert!(min <= est, "{min:?} {est:?} {max:?}");
+        debug_assert!(est <= max, "{min:?} {est:?} {max:?}");
         Self { min, est, max }
     }
     pub fn contains(&self, rank: f64) -> bool {
@@ -260,7 +260,9 @@ pub mod tests {
                 );
                 assert_eq!(rank_est.min, rank_est.max);
                 assert!(rank_est.contains(rank));
-                let rank_est = method.rank_accuracy(&*costs, &*key, 1.1, Some(1)).unwrap();
+                let rank_est = method
+                    .rank_accuracy(&*costs, &*key, 1.1, Some(1), 1 << 10)
+                    .unwrap();
                 assert_eq!(rank_est.min, rank_est.max);
                 assert!(rank_est.contains(rank));
             }
@@ -271,6 +273,7 @@ pub mod tests {
         key: &[usize],
         merge: usize,
         nb_bin: usize,
+        acc_req: f64,
     ) -> Result<(), RankError> {
         let rank = RankProblem::new(costs, key)?.naive_rank();
         for method in RANKING_METHODS {
@@ -286,8 +289,22 @@ pub mod tests {
                 key,
                 method
             );
-            let rank_est = method.rank_accuracy(costs, key, 1.9, Some(merge))?;
-            assert!(rank_est.max / rank_est.min < 2.0);
+            let rank_est = method.rank_accuracy(costs, key, 1.0, Some(merge), 1 << 10)?;
+            assert!(
+                rank_est.contains(rank),
+                "rank: {}, rank_est: {:?}, merge: {}, nb_bin: {}, costs: {:?}, key: {:?} method: {:?}",
+                rank,
+                rank_est,
+                merge,
+                nb_bin,
+                costs,
+                key,
+                method
+            );
+            assert!(
+                rank_est.max / rank_est.min <= acc_req,
+                "{rank_est:?} {acc_req:?}"
+            );
         }
         return Ok(());
     }
@@ -301,7 +318,7 @@ pub mod tests {
                         "Simple Testcase merge={}, nb_bin={}, key: {:?}",
                         merge, nb_bin, key
                     );
-                    let _ = rank2_vs_naive(&costs, &key, merge, nb_bin);
+                    let _ = rank2_vs_naive(&costs, &key, merge, nb_bin, 2.0);
                 }
             }
         }
@@ -311,38 +328,42 @@ pub mod tests {
         key: Vec<usize>,
         nb_bin: usize,
         merge: usize,
+        acc: f64,
     }
     #[test]
     fn test_manycases() {
-        let _t = TestCase {
-            costs: vec![
-                vec![
-                    -256.0, -1.0, -16641.0, -1.0, -1.0, -1.0, -1.0, -189.0, 32511.0, -1.0, -1.0,
-                    -1.0, -1.0, -1.0, 4112.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -20481.0,
-                    -12113.0, 13039.0, 14135.0, 55.0,
-                ],
-                vec![13621.0, 13621.0, 13621.0, 13749.0, -4113.0],
-                vec![
-                    -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,
-                    -1.0, -1.0, -1.0,
-                ],
-            ],
-            key: vec![0, 0, 0],
-            nb_bin: 32,
-            merge: 1,
-        };
         let test_cases = vec![
+            TestCase {
+                costs: vec![
+                    vec![
+                        -256.0, -1.0, -16641.0, -1.0, -1.0, -1.0, -1.0, -189.0, 32511.0, -1.0,
+                        -1.0, -1.0, -1.0, -1.0, 4112.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,
+                        -20481.0, -12113.0, 13039.0, 14135.0, 55.0,
+                    ],
+                    vec![13621.0, 13621.0, 13621.0, 13749.0, -4113.0],
+                    vec![
+                        -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0,
+                        -1.0, -1.0, -1.0, -1.0,
+                    ],
+                ],
+                key: vec![0, 0, 0],
+                nb_bin: 32,
+                merge: 1,
+                acc: 20.0,
+            },
             TestCase {
                 costs: vec![vec![0.0, 0.0]],
                 key: vec![0],
                 nb_bin: 10,
                 merge: 1,
+                acc: 2.0,
             },
             TestCase {
                 costs: vec![vec![1.0, 0.0, 1.00001, 2.0]],
                 key: vec![0],
                 nb_bin: 4,
                 merge: 1,
+                acc: 2.0,
             },
             TestCase {
                 costs: vec![
@@ -353,29 +374,40 @@ pub mod tests {
                 key: vec![0, 0, 0],
                 nb_bin: 32,
                 merge: 1,
+                acc: 2.0,
             },
             TestCase {
                 costs: vec![vec![-1.0, 32511.0], vec![-1.0], vec![-1.0, 0.0, -26315.0]],
                 key: vec![0, 0, 0],
                 nb_bin: 32,
                 merge: 1,
+                acc: 2.0,
             },
             TestCase {
                 costs: vec![vec![0.0], vec![0.0], vec![2.0, 0.0, 1.0]],
                 key: vec![0, 0, 0],
                 nb_bin: 4,
                 merge: 1,
+                acc: 1.0,
+            },
+            TestCase {
+                costs: vec![vec![10.0, 0.0], vec![30.0, 0.0]],
+                key: vec![0, 0],
+                nb_bin: 4,
+                merge: 1,
+                acc: 2.0,
             },
             TestCase {
                 costs: vec![vec![10.0, 0.0], vec![30.0, 0.0], vec![13.0, 0.0, 12.0]],
                 key: vec![0, 0, 0],
                 nb_bin: 4,
                 merge: 1,
+                acc: 2.0,
             },
         ];
         for (i, case) in test_cases.into_iter().enumerate() {
             println!("Testcase {}", i);
-            let _ = rank2_vs_naive(&case.costs, &case.key, case.merge, case.nb_bin);
+            let _ = rank2_vs_naive(&case.costs, &case.key, case.merge, case.nb_bin, case.acc);
         }
     }
 }
diff --git a/src/scalib_ext/ranklib/src/rank.rs b/src/scalib_ext/ranklib/src/rank.rs
index cd868fec..9578204a 100644
--- a/src/scalib_ext/ranklib/src/rank.rs
+++ b/src/scalib_ext/ranklib/src/rank.rs
@@ -8,8 +8,11 @@ const MAX_NB_BINS: usize = 1 << 14;
 #[cfg(not(fuzzing))]
 const MAX_NB_BINS: usize = 1 << 29;
 
+fn cost2bin_f(cost: f64, bin_size: f64) -> f64 {
+    cost / bin_size
+}
 fn cost2bin(cost: f64, bin_size: f64) -> usize {
-    (cost / bin_size).round() as usize
+    cost2bin_f(cost, bin_size).round() as usize
 }
 
 /// A rank estimation problem.
@@ -222,21 +225,30 @@ fn rank_in_histogram<H: Histogram>(
     bin_size: f64,
     nb_subkeys: usize,
 ) -> RankEstimation {
-    // Values can be shifted by at most nb_subkeys*bin_size/2
-    let margin = ((nb_subkeys as f64) * bin_size) / 2.0;
-    let max_bound_cost = real_key_cost + margin;
-    let min_bound_cost = (real_key_cost - margin).max(0.0);
+    // Values can be shifted by at most nb_subkeys/2 bins.
+    // We add a small amount to compensate for rounding errors.
+    let margin = (nb_subkeys as f64) / 2.0 + 1e-20;
     let coefs = histo.coefs_f64();
     // bound by histo.len is needed due to greedy histogram growth
     let bin_real_key = std::cmp::min(coefs.len() - 1, cost2bin(real_key_cost, bin_size));
-    let bin_bound_max = std::cmp::min(coefs.len() - 1, cost2bin(max_bound_cost, bin_size));
-    let bin_bound_min = std::cmp::min(coefs.len() - 1, cost2bin(min_bound_cost, bin_size));
+    let bin_bound_max = std::cmp::min(
+        coefs.len() - 1,
+        (cost2bin_f(real_key_cost, bin_size) + margin).floor() as usize,
+    );
+    let bin_bound_min = std::cmp::min(
+        coefs.len() - 1,
+        (cost2bin_f(real_key_cost, bin_size) - margin).ceil() as usize,
+    );
+    debug_assert!(bin_bound_min <= bin_real_key);
+    debug_assert!(bin_real_key <= bin_bound_max);
     let sum_hist = |end| coefs[..end].iter().copied().sum::<f64>();
     // We must add one to the minimum rank to include the real key.
-    // It is already included in the est and the max.
+    let rank_min = 1.0 + sum_hist(bin_bound_min);
+    // It is already included in the max.
+    // For the est, it might not be included, if the real key is between the real bin and the max.
     return RankEstimation::new(
-        1.0 + sum_hist(bin_bound_min),
-        sum_hist(bin_real_key) + (coefs[bin_real_key] / 2.0).ceil(),
+        rank_min,
+        rank_min.max(sum_hist(bin_real_key) + (coefs[bin_real_key] / 2.0).ceil()),
         sum_hist(bin_bound_max + 1),
     );
 }
diff --git a/tox.ini b/tox.ini
index 1fbe27cf..c32fcdd9 100644
--- a/tox.ini
+++ b/tox.ini
@@ -13,6 +13,7 @@ setenv =
 deps =
     -r{toxinidir}/tests/requirements.txt
 commands =
+    cargo test --workspace --manifest-path {toxinidir}/src/scalib_ext/Cargo.toml
     pip freeze
     pytest {tty:--color=yes} {posargs}
 
@@ -25,6 +26,7 @@ deps = {[base]deps}
 commands = {[base]commands}
 package = wheel
 wheel_build_env = .pkg
+allowlist_externals = cargo
 
 [testenv:dev]
 description = Editable install with debug build.
@@ -65,5 +67,4 @@ commands =
     black {posargs} src/scalib tests examples
     cargo fmt --version
     cargo fmt --manifest-path src/scalib_ext/Cargo.toml --all -- {posargs}
-allowlist_externals = cargo
 


Test patch:
diff --git a/examples/test_examples.py b/examples/test_examples.py
new file mode 100644
index 00000000..0eabf124
--- /dev/null
+++ b/examples/test_examples.py
@@ -0,0 +1,14 @@
+"""
+Module only used by pytest.
+"""
+
+import pathlib
+import runpy
+
+
+def example_path(example_file):
+    return str(pathlib.Path(__file__).parent / example_file)
+
+
+def test_examples():
+    runpy.run_path(example_path("aes_simulation.py"))