aboutsummaryrefslogtreecommitdiff
path: root/analysis
diff options
context:
space:
mode:
authorJ08nY2025-04-16 12:32:45 +0200
committerJ08nY2025-04-16 12:32:45 +0200
commita286322501f2240e6f03352e3d916b218ec0d76f (patch)
tree3a6b257c87ad6760241ca16fd474ff9a14b5ff24 /analysis
parent595a9274ee2bf9b27ba67395c74a37d6ba0ff170 (diff)
downloadECTester-a286322501f2240e6f03352e3d916b218ec0d76f.tar.gz
ECTester-a286322501f2240e6f03352e3d916b218ec0d76f.tar.zst
ECTester-a286322501f2240e6f03352e3d916b218ec0d76f.zip
Diffstat (limited to 'analysis')
-rw-r--r--analysis/countermeasures/common.py297
-rw-r--r--analysis/countermeasures/distinguish.ipynb1510
-rw-r--r--analysis/countermeasures/formulas.ipynb666
-rw-r--r--analysis/countermeasures/probmaps.py78
-rw-r--r--analysis/countermeasures/simulate.ipynb265
-rw-r--r--analysis/countermeasures/simulate.py121
-rw-r--r--analysis/countermeasures/visualize.ipynb406
7 files changed, 0 insertions, 3343 deletions
diff --git a/analysis/countermeasures/common.py b/analysis/countermeasures/common.py
deleted file mode 100644
index 2d5cf0b..0000000
--- a/analysis/countermeasures/common.py
+++ /dev/null
@@ -1,297 +0,0 @@
-import multiprocessing
-import inspect
-import tempfile
-import sys
-import os
-from datetime import timedelta
-
-from contextlib import contextmanager
-from dataclasses import dataclass
-from functools import partial, cached_property, total_ordering
-from importlib import import_module, invalidate_caches
-from pathlib import Path
-from typing import Type, Any, Optional
-from enum import Enum
-
-from statsmodels.stats.proportion import proportion_confint
-
-from pyecsca.ec.params import DomainParameters, get_params
-from pyecsca.ec.mult import *
-from pyecsca.ec.countermeasures import GroupScalarRandomization, AdditiveSplitting, MultiplicativeSplitting, EuclideanSplitting, BrumleyTuveri
-
-
-spawn_context = multiprocessing.get_context("spawn")
-
-# Allow to use "spawn" multiprocessing method for function defined in a Jupyter notebook.
-# https://neuromancer.sk/article/35
-@contextmanager
-def enable_spawn(func):
- invalidate_caches()
- source = inspect.getsource(func)
- current_file_path = os.path.abspath(__file__)
- with open(current_file_path, 'r') as self, tempfile.NamedTemporaryFile(suffix=".py", mode="w") as f:
- f.write(self.read())
- f.write(source)
- f.flush()
- path = Path(f.name)
- directory = str(path.parent)
- sys.path.append(directory)
- module = import_module(str(path.stem))
- yield getattr(module, func.__name__)
- sys.path.remove(directory)
-
-
-@dataclass(frozen=True)
-@total_ordering
-class MultIdent:
- klass: Type[ScalarMultiplier]
- args: list[Any]
- kwargs: dict[str, Any]
- countermeasure: Optional[str] = None
-
- def __init__(self, klass: Type[ScalarMultiplier], *args, **kwargs):
- object.__setattr__(self, "klass", klass)
- object.__setattr__(self, "args", args if args is not None else [])
- if kwargs is not None and "countermeasure" in kwargs:
- object.__setattr__(self, "countermeasure", kwargs["countermeasure"])
- del kwargs["countermeasure"]
- object.__setattr__(self, "kwargs", kwargs if kwargs is not None else {})
-
- @cached_property
- def partial(self):
- func = partial(self.klass, *self.args, **self.kwargs)
- if self.countermeasure is None:
- return func
- if self.countermeasure == "gsr":
- return lambda *args, **kwargs: GroupScalarRandomization(func(*args, **kwargs))
- elif self.countermeasure == "additive":
- return lambda *args, **kwargs: AdditiveSplitting(func(*args, **kwargs))
- elif self.countermeasure == "multiplicative":
- return lambda *args, **kwargs: MultiplicativeSplitting(func(*args, **kwargs))
- elif self.countermeasure == "euclidean":
- return lambda *args, **kwargs: EuclideanSplitting(func(*args, **kwargs))
- elif self.countermeasure == "bt":
- return lambda *args, **kwargs: BrumleyTuveri(func(*args, **kwargs))
-
- def with_countermeasure(self, countermeasure: str | None):
- if countermeasure not in (None, "gsr", "additive", "multiplicative", "euclidean", "bt"):
- raise ValueError(f"Unknown countermeasure: {countermeasure}")
- return MultIdent(self.klass, *self.args, **self.kwargs, countermeasure=countermeasure)
-
- def __str__(self):
- name = self.klass.__name__.replace("Multiplier", "")
- args = ("_" + ",".join(list(map(str, self.args)))) if self.args else ""
- kwmap = {"recoding_direction": "recode",
- "direction": "dir",
- "width": "w"}
- kwargs = ("_" + ",".join(f"{kwmap.get(k, k)}:{v.name if isinstance(v, Enum) else str(v)}" for k,v in self.kwargs.items())) if self.kwargs else ""
- countermeasure = f"+{self.countermeasure}" if self.countermeasure is not None else ""
- return f"{name}{args}{kwargs}{countermeasure}"
-
- def __lt__(self, other):
- if not isinstance(other, MultIdent):
- return NotImplemented
- return str(self) < str(other)
-
- def __repr__(self):
- return str(self)
-
- def __hash__(self):
- return hash((self.klass, self.countermeasure, tuple(self.args), tuple(self.kwargs.keys()), tuple(self.kwargs.values())))
-
-
-@dataclass
-class MultResults:
- multiplications: list[set[int]]
- samples: int
- duration: Optional[float] = None
- kind: Optional[str] = None
-
- def merge(self, other: "MultResults"):
- self.multiplications.extend(other.multiplications)
- self.samples += other.samples
-
- def __len__(self):
- return self.samples
-
- def __iter__(self):
- yield from self.multiplications
-
- def __getitem__(self, i):
- return self.multiplications[i]
-
- def __str__(self):
- duration = timedelta(seconds=int(self.duration)) if self.duration is not None else ""
- kind = self.kind if self.kind is not None else ""
- return f"MultResults({self.samples},{duration},{kind})"
-
- def __repr__(self):
- return str(self)
-
-
-@dataclass
-class ProbMap:
- probs: dict[int, float]
- samples: int
- kind: Optional[str] = None
-
- def __len__(self):
- return len(self.probs)
-
- def __iter__(self):
- yield from self.probs
-
- def __getitem__(self, i):
- return self.probs[i]
-
- def keys(self):
- return self.probs.keys()
-
- def values(self):
- return self.probs.values()
-
- def items(self):
- return self.probs.items()
-
- def narrow(self, divisors: set[int]):
- self.probs = {k:v for k, v in self.probs.items() if k in divisors}
-
- def merge(self, other: "ProbMap") -> None:
- if self.kind != other.kind:
- raise ValueError("Merging ProbMaps of different kinds leads to unexpected results.")
- new_keys = set(self.keys()).union(other.keys())
- result = {}
- for key in new_keys:
- if key in self and key in other:
- result[key] = (self[key] * self.samples + other[key] * other.samples) / (self.samples + other.samples)
- elif key in self:
- result[key] = self[key]
- elif key in other:
- result[key] = other[key]
- self.probs = result
- self.samples += other.samples
-
- def enrich(self, other: "ProbMap") -> None:
- if self.samples != other.samples:
- raise ValueError("Enriching can only work on equal amount of samples (same run, different divisors)")
- if self.kind != other.kind:
- raise ValueError("Enriching ProbMaps of different kinds leads to unexpected results.")
- self.probs.update(other.probs)
-
-
-# All dbl-and-add multipliers from https://github.com/J08nY/pyecsca/blob/master/pyecsca/ec/mult
-window_mults = [
- MultIdent(SlidingWindowMultiplier, width=2, recoding_direction=ProcessingDirection.LTR),
- MultIdent(SlidingWindowMultiplier, width=3, recoding_direction=ProcessingDirection.LTR),
- MultIdent(SlidingWindowMultiplier, width=4, recoding_direction=ProcessingDirection.LTR),
- MultIdent(SlidingWindowMultiplier, width=5, recoding_direction=ProcessingDirection.LTR),
- MultIdent(SlidingWindowMultiplier, width=6, recoding_direction=ProcessingDirection.LTR),
- MultIdent(SlidingWindowMultiplier, width=2, recoding_direction=ProcessingDirection.RTL),
- MultIdent(SlidingWindowMultiplier, width=3, recoding_direction=ProcessingDirection.RTL),
- MultIdent(SlidingWindowMultiplier, width=4, recoding_direction=ProcessingDirection.RTL),
- MultIdent(SlidingWindowMultiplier, width=5, recoding_direction=ProcessingDirection.RTL),
- MultIdent(SlidingWindowMultiplier, width=6, recoding_direction=ProcessingDirection.RTL),
- MultIdent(FixedWindowLTRMultiplier, m=2**1),
- MultIdent(FixedWindowLTRMultiplier, m=2**2),
- MultIdent(FixedWindowLTRMultiplier, m=2**3),
- MultIdent(FixedWindowLTRMultiplier, m=2**4),
- MultIdent(FixedWindowLTRMultiplier, m=2**5),
- MultIdent(FixedWindowLTRMultiplier, m=2**6),
- MultIdent(WindowBoothMultiplier, width=2),
- MultIdent(WindowBoothMultiplier, width=3),
- MultIdent(WindowBoothMultiplier, width=4),
- MultIdent(WindowBoothMultiplier, width=5),
- MultIdent(WindowBoothMultiplier, width=6)
-]
-naf_mults = [
- MultIdent(WindowNAFMultiplier, width=2),
- MultIdent(WindowNAFMultiplier, width=3),
- MultIdent(WindowNAFMultiplier, width=4),
- MultIdent(WindowNAFMultiplier, width=5),
- MultIdent(WindowNAFMultiplier, width=6),
- MultIdent(BinaryNAFMultiplier, always=False, direction=ProcessingDirection.LTR),
- MultIdent(BinaryNAFMultiplier, always=False, direction=ProcessingDirection.RTL),
- MultIdent(BinaryNAFMultiplier, always=True, direction=ProcessingDirection.LTR),
- MultIdent(BinaryNAFMultiplier, always=True, direction=ProcessingDirection.RTL)
-]
-comb_mults = [
- MultIdent(CombMultiplier, width=2, always=True),
- MultIdent(CombMultiplier, width=3, always=True),
- MultIdent(CombMultiplier, width=4, always=True),
- MultIdent(CombMultiplier, width=5, always=True),
- MultIdent(CombMultiplier, width=6, always=True),
- MultIdent(CombMultiplier, width=2, always=False),
- MultIdent(CombMultiplier, width=3, always=False),
- MultIdent(CombMultiplier, width=4, always=False),
- MultIdent(CombMultiplier, width=5, always=False),
- MultIdent(CombMultiplier, width=6, always=False),
- MultIdent(BGMWMultiplier, width=2, direction=ProcessingDirection.LTR),
- MultIdent(BGMWMultiplier, width=3, direction=ProcessingDirection.LTR),
- MultIdent(BGMWMultiplier, width=4, direction=ProcessingDirection.LTR),
- MultIdent(BGMWMultiplier, width=5, direction=ProcessingDirection.LTR),
- MultIdent(BGMWMultiplier, width=6, direction=ProcessingDirection.LTR),
- MultIdent(BGMWMultiplier, width=2, direction=ProcessingDirection.RTL),
- MultIdent(BGMWMultiplier, width=3, direction=ProcessingDirection.RTL),
- MultIdent(BGMWMultiplier, width=4, direction=ProcessingDirection.RTL),
- MultIdent(BGMWMultiplier, width=5, direction=ProcessingDirection.RTL),
- MultIdent(BGMWMultiplier, width=6, direction=ProcessingDirection.RTL)
-]
-binary_mults = [
- MultIdent(LTRMultiplier, always=False, complete=True),
- MultIdent(LTRMultiplier, always=True, complete=True),
- MultIdent(LTRMultiplier, always=False, complete=False),
- MultIdent(LTRMultiplier, always=True, complete=False),
- MultIdent(RTLMultiplier, always=False, complete=True),
- MultIdent(RTLMultiplier, always=True, complete=True),
- MultIdent(RTLMultiplier, always=False, complete=False),
- MultIdent(RTLMultiplier, always=True, complete=False),
- MultIdent(CoronMultiplier)
-]
-other_mults = [
- MultIdent(FullPrecompMultiplier, always=False, complete=True),
- MultIdent(FullPrecompMultiplier, always=True, complete=True),
- MultIdent(FullPrecompMultiplier, always=False, complete=False),
- MultIdent(FullPrecompMultiplier, always=True, complete=False),
- MultIdent(SimpleLadderMultiplier, complete=True),
- MultIdent(SimpleLadderMultiplier, complete=False)
-]
-
-all_mults = window_mults + naf_mults + binary_mults + other_mults + comb_mults
-all_mults_with_ctr = [mult.with_countermeasure(ctr) for mult in all_mults for ctr in (None, "gsr", "additive", "multiplicative", "euclidean", "bt")]
-
-
-def powers_of(k, max_power=20):
- return [k**i for i in range(1, max_power)]
-
-def prod_combine(one, other):
- return [a * b for a, b in itertools.product(one, other)]
-
-small_primes = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
-medium_primes = [211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397]
-large_primes = [401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
-all_integers = list(range(1, 400))
-all_even = list(range(2, 400, 2))
-all_odd = list(range(1, 400, 2))
-all_primes = small_primes + medium_primes + large_primes
-
-divisor_map = {
- "small_primes": small_primes,
- "medium_primes": medium_primes,
- "large_primes": large_primes,
- "all_primes": all_primes,
- "all_integers": all_integers,
- "all_even": all_even,
- "all_odd": all_odd,
- "powers_of_2": powers_of(2),
- "powers_of_2_large": powers_of(2, 256),
- "powers_of_2_large_3": [i * 3 for i in powers_of(2, 256)],
- "powers_of_2_large_p1": [i + 1 for i in powers_of(2, 256)],
- "powers_of_2_large_m1": [i - 1 for i in powers_of(2, 256)],
- "powers_of_2_large_pmautobus": sorted(set([i + j for i in powers_of(2, 256) for j in range(-5,5) if i+j > 0])),
- "powers_of_3": powers_of(3),
-}
-divisor_map["all"] = list(sorted(set().union(*[v for v in divisor_map.values()])))
-
-
-def conf_interval(p: float, samples: int, alpha: float = 0.05) -> tuple[float, float]:
- return proportion_confint(round(p*samples), samples, alpha, method="wilson")
diff --git a/analysis/countermeasures/distinguish.ipynb b/analysis/countermeasures/distinguish.ipynb
deleted file mode 100644
index fdb3f6a..0000000
--- a/analysis/countermeasures/distinguish.ipynb
+++ /dev/null
@@ -1,1510 +0,0 @@
-{
- "cells": [
- {
- "cell_type": "markdown",
- "id": "e76983df-053b-450b-976c-295826248978",
- "metadata": {},
- "source": [
- "# Unraveling scalar mults and countermeasures"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "bc1528b8-61cd-4219-993f-e3f1ac79e801",
- "metadata": {},
- "outputs": [],
- "source": [
- "import pickle\n",
- "import itertools\n",
- "import glob\n",
- "import random\n",
- "import math\n",
- "\n",
- "from collections import Counter\n",
- "\n",
- "import numpy as np\n",
- "import pandas as pd\n",
- "from scipy.stats import binom, entropy\n",
- "from scipy.spatial import distance\n",
- "from tqdm.auto import tqdm, trange\n",
- "from anytree import PreOrderIter, Walker\n",
- "from matplotlib import pyplot as plt\n",
- "\n",
- "from pyecsca.ec.mult import *\n",
- "from pyecsca.misc.utils import TaskExecutor, silent\n",
- "from pyecsca.sca.re.tree import Map, Tree\n",
- "\n",
- "from common import *\n",
- "\n",
- "%matplotlib ipympl"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "4868c083-8073-453d-b508-704fcb6d6f2a",
- "metadata": {},
- "source": [
- "## Prepare\n",
- "Select *divisor name* to restrict the features. Select *kind* to pick the probmap source."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "ccb00342-3c48-49c9-bedf-2341e5eae3a2",
- "metadata": {},
- "outputs": [],
- "source": [
- "divisor_name = \"all\"\n",
- "kind = \"all\"\n",
- "allfeats = list(filter(lambda feat: feat not in (1,2,3,4,5), divisor_map[divisor_name]))"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "3dbac9be-d098-479a-8ca2-f531f6668f7c",
- "metadata": {},
- "outputs": [],
- "source": [
- "# Load\n",
- "try:\n",
- " with open(f\"{divisor_name}_{kind}_distrs.pickle\", \"rb\") as f:\n",
- " distributions_mults = pickle.load(f)\n",
- "except FileNotFoundError:\n",
- " with open(f\"all_{kind}_distrs.pickle\", \"rb\") as f:\n",
- " distributions_mults = pickle.load(f)\n",
- " for probmap in distributions_mults.values():\n",
- " probmap.narrow(allfeats)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "38c81e38-a37c-4e58-ac9e-927d14dad458",
- "metadata": {},
- "outputs": [],
- "source": [
- "allmults = list(distributions_mults.keys())\n",
- "nmults = len(allmults)\n",
- "nallfeats = len(allfeats)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "1f783baf-bc81-40c1-9282-e2dfdacfd17c",
- "metadata": {},
- "source": [
- "## Build dmap and tree"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "d161f3e8-6e39-47c1-a26f-23f910f3fe26",
- "metadata": {},
- "source": [
- "Select the n for building the tree."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "2307bf7c-4fac-489d-8527-7ddbf536a148",
- "metadata": {},
- "outputs": [],
- "source": [
- "nbuild = 10000\n",
- "alpha = 0.05"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "0b85fad7-392f-4701-9329-d75d39736bbb",
- "metadata": {},
- "outputs": [],
- "source": [
- "# Now go over all divisors, cluster based on overlapping CI for given n?\n",
- "io_map = {mult:{} for mult in allmults}\n",
- "for divisor in allfeats:\n",
- " prev_ci_low = None\n",
- " prev_ci_high = None\n",
- " groups = {}\n",
- " pvals = {}\n",
- " group = 0\n",
- " for mult, probmap in sorted(distributions_mults.items(), key=lambda item: -item[1][divisor]):\n",
- " # We are going from high to low p.\n",
- " pval = probmap[divisor]\n",
- " pvals[mult] = pval\n",
- " ci_low, ci_high = conf_interval(pval, nbuild, alpha)\n",
- " ci_low = max(ci_low, 0.0)\n",
- " ci_high = min(ci_high, 1.0)\n",
- " if (prev_ci_low is None and prev_ci_high is None) or prev_ci_low >= ci_high:\n",
- " g = groups.setdefault(f\"arbitrary{group}\", set())\n",
- " g.add(mult)\n",
- " group += 1\n",
- " else:\n",
- " g = groups.setdefault(f\"arbitrary{group}\", set())\n",
- " g.add(mult)\n",
- " prev_ci_low = ci_low\n",
- " prev_ci_high = ci_high\n",
- " \n",
- " #print(f\"Divisor: {divisor}, num groups: {group}\", end=\"\\n\\t\")\n",
- " #for g in groups.values():\n",
- " # print(len(g), end=\", \")\n",
- " #print()\n",
- " for group, mults in groups.items():\n",
- " mult_pvals = [pvals[mult] for mult in mults]\n",
- " group_pval_avg = np.mean(mult_pvals)\n",
- " group_pval_var = np.var(mult_pvals)\n",
- " group_pval_min = np.min(mult_pvals)\n",
- " group_pval_max = np.max(mult_pvals)\n",
- " for mult in mults:\n",
- " io_map[mult][divisor] = (group, group_pval_avg, group_pval_var, group_pval_min, group_pval_max)\n",
- "\n",
- "# then build dmap\n",
- "dmap = Map.from_io_maps(set(distributions_mults.keys()), io_map)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "06104104-b612-40e9-bc1d-646356a13381",
- "metadata": {},
- "outputs": [],
- "source": [
- "print(dmap.describe())"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "eb8672ca-b76b-411d-b514-2387b555f184",
- "metadata": {},
- "outputs": [],
- "source": [
- "# deduplicate dmap\n",
- "dmap.deduplicate()"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "ccba09b0-31c3-450b-af30-efaa64329743",
- "metadata": {},
- "outputs": [],
- "source": [
- "print(dmap.describe())"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "5735e7d4-149c-4184-96f7-dcfd6017fbad",
- "metadata": {},
- "outputs": [],
- "source": [
- "# build a tree\n",
- "with silent():\n",
- " tree = Tree.build(set(allmults), dmap)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "d41093df-32c4-450d-922d-5ad042539397",
- "metadata": {},
- "outputs": [],
- "source": [
- "print(tree.describe())"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "de577429-d87c-4967-be17-75cbb378860c",
- "metadata": {
- "scrolled": true
- },
- "outputs": [],
- "source": [
- "print(tree.render_basic())"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "437bcd9c-1da5-428a-a979-0835326777f3",
- "metadata": {},
- "source": [
- "## Simulate distinguishing using a tree\n",
- "We can now simulate distinguishing using the tree and how it behaves with increasing the number of samples per divisor collected."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "109ed95f-0949-4251-874f-9b87cfe97a00",
- "metadata": {},
- "outputs": [],
- "source": [
- "simulations = 1000\n",
- "\n",
- "for nattack in trange(100, 10000, 100):\n",
- " successes = 0\n",
- " pathiness = 0\n",
- " for i in range(simulations):\n",
- " true_mult = random.choice(allmults)\n",
- " probmap = distributions_mults[true_mult]\n",
- " node = tree.root\n",
- " while True:\n",
- " if node.is_leaf:\n",
- " break\n",
- " divisor = node.dmap_input\n",
- " prob = probmap[divisor]\n",
- " sampled_prob = binom(nattack, prob).rvs() / nattack\n",
- " best_child = None\n",
- " true_child = None\n",
- " best_group_distance = None\n",
- " #print(f\"Divisor: {divisor}, prob: {prob}, sampled: {sampled_prob}\")\n",
- " for child in node.children:\n",
- " if true_mult in child.cfgs:\n",
- " true_child = child\n",
- " group, group_pval_avg, group_pval_var, group_pval_min, group_pval_max = child.response\n",
- " group_distance = min(abs(sampled_prob - group_pval_min), abs(sampled_prob - group_pval_max))\n",
- " #print(f\"Child {group}, {group_pval_avg}\")\n",
- " if best_child is None or \\\n",
- " (group_distance < best_group_distance):\n",
- " best_child = child\n",
- " best_group_distance = group_distance\n",
- " if sampled_prob > group_pval_min and sampled_prob < group_pval_max:\n",
- " best_child = child\n",
- " break\n",
- " #print(f\"Best {best_child.response}\")\n",
- " if true_child is not None and true_child != best_child:\n",
- " pass\n",
- " #print(f\"Mistake! {prob}, {sampled_prob} true:{true_child.response}, chosen:{best_child.response}\")\n",
- " node = best_child\n",
- " if true_mult in node.cfgs:\n",
- " pathiness += 1\n",
- " #print(f\"Arrived: {true_mult in node.cfgs}\")\n",
- " if true_mult in node.cfgs:\n",
- " successes += 1\n",
- " print(f\"{nattack}: success rate {successes/simulations}, pathiness {pathiness/simulations}\")"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "308df683-952e-430a-b2bd-f19bcfb98b8e",
- "metadata": {},
- "source": [
- "## Simulate distinguishing using a distance metric\n",
- "\n",
- "We need to first select some features (divisors) from the set of all divisors that we will query\n",
- "the target with. This set should be the smallest (to not do a lot of queries) yet allow us to distinguish as\n",
- "much as possible."
- ]
- },
- {
- "cell_type": "markdown",
- "id": "62d2f2a2-495e-459d-b0e2-89c9a5973b1e",
- "metadata": {},
- "source": [
- "### Feature selection using trees + classification error\n",
- "\n",
- "We can reuse the clustering + tree building approach above and just take the inputs that the greedy tree building choses as the features. However, we can also use more conventional feature selection approaches."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "cc1a9956-bc8c-47cf-b6ec-093c6cf85c7d",
- "metadata": {
- "editable": true,
- "slideshow": {
- "slide_type": ""
- },
- "tags": []
- },
- "outputs": [],
- "source": [
- "from sklearn.base import BaseEstimator, ClassifierMixin\n",
- "from sklearn.utils.validation import validate_data, check_is_fitted\n",
- "from sklearn.utils.multiclass import unique_labels\n",
- "from scipy.special import logsumexp\n",
- "from sklearn.metrics import euclidean_distances, top_k_accuracy_score, make_scorer, accuracy_score\n",
- "\n",
- "\n",
- "class EuclidClassifier(ClassifierMixin, BaseEstimator):\n",
- " def __init__(self, *, nattack=100):\n",
- " self.nattack = nattack\n",
- "\n",
- " def fit(self, X, y):\n",
- " X, y = validate_data(self, X, y)\n",
- " if not np.logical_and(X >= 0, X <= 1).all():\n",
- " raise TypeError(\"Expects valid probabilities in X.\")\n",
- " self.classes_ = unique_labels(y)\n",
- " if len(self.classes_) != len(y):\n",
- " raise ValueError(\"Expects only one sample per class containing the binomial probabilities.\")\n",
- " self.X_ = X\n",
- " self.y_ = y\n",
- " return self\n",
- "\n",
- " def decision_function(self, X):\n",
- " check_is_fitted(self)\n",
- " X = validate_data(self, X, reset=False)\n",
- " distances = euclidean_distances(X / self.nattack, self.X_)\n",
- " return -distances\n",
- "\n",
- " def predict(self, X):\n",
- " check_is_fitted(self)\n",
- " X = validate_data(self, X, reset=False)\n",
- " distances = euclidean_distances(X / self.nattack, self.X_)\n",
- " closest = np.argmin(distances, axis=1)\n",
- " return self.classes_[closest]\n",
- "\n",
- "\n",
- "class BayesClassifier(ClassifierMixin, BaseEstimator):\n",
- " def __init__(self, *, nattack=100):\n",
- " self.nattack = nattack\n",
- "\n",
- " def fit(self, X, y):\n",
- " # X has (nmults = nsamples, nfeats)\n",
- " X, y = validate_data(self, X, y)\n",
- " if not np.logical_and(X >= 0, X <= 1).all():\n",
- " raise TypeError(\"Expects valid probabilities in X.\")\n",
- " self.classes_ = unique_labels(y)\n",
- " if len(self.classes_) != len(y):\n",
- " raise ValueError(\"Expects only one sample per class containing the binomial probabilities.\")\n",
- " self.X_ = X\n",
- " self.y_ = y\n",
- " return self\n",
- "\n",
- " def decision_function(self, X):\n",
- " check_is_fitted(self)\n",
- " X = validate_data(self, X, reset=False)\n",
- " # We have a uniform prior, so we can ignore it.\n",
- " probas = np.zeros((len(X), len(self.classes_)))\n",
- " for i, row in enumerate(X):\n",
- " p = binom(self.nattack, self.X_).logpmf(row)\n",
- " s = np.sum(p, axis=1)\n",
- " log_prob_x = logsumexp(s)\n",
- " res = np.exp(s - log_prob_x)\n",
- " probas[i, ] = res\n",
- " return probas\n",
- "\n",
- " def predict_proba(self, X):\n",
- " return self.decision_function(X)\n",
- "\n",
- " def predict(self, X):\n",
- " check_is_fitted(self)\n",
- " X = validate_data(self, X, reset=False)\n",
- " # We have a uniform prior, so we can ignore it.\n",
- " results = np.empty(len(X), dtype=self.classes_.dtype)\n",
- " for i, row in enumerate(X):\n",
- " p = binom(self.nattack, self.X_).logpmf(row)\n",
- " s = np.sum(p, axis=1)\n",
- " most_likely = np.argmax(s)\n",
- " results[i] = self.classes_[most_likely]\n",
- " return results\n",
- "\n",
- "\n",
- "def to_sklearn(mults_map: dict[MultIdent, ProbMap], feats: list[int]):\n",
- " nfeats = len(feats)\n",
- " nmults = len(mults_map)\n",
- " classes = np.arange(nmults, dtype=np.uint32)\n",
- " probs = np.zeros((nmults, nfeats), dtype=np.float64)\n",
- " mults = sorted(list(mults_map.keys()))\n",
- " for i, divisor in enumerate(feats):\n",
- " for j, mult in enumerate(mults):\n",
- " probmap = mults_map[mult]\n",
- " probs[j, i] = probmap[divisor]\n",
- " return probs, classes\n",
- "\n",
- "\n",
- "def make_instance(nattack: int,\n",
- " simulations: int,\n",
- " X,\n",
- " y,\n",
- " progress=False):\n",
- " nmults, nfeats = X.shape\n",
- " X_samp = np.zeros((simulations, nfeats), dtype=np.uint32)\n",
- " y_samp = np.zeros(simulations, dtype=np.uint32)\n",
- "\n",
- " r = trange(simulations) if progress else range(simulations)\n",
- " for i in r:\n",
- " if i < nmults and simulations >= nmults:\n",
- " j = i\n",
- " else:\n",
- " j = random.randrange(nmults)\n",
- " X_samp[i] = binom(nattack, X[j]).rvs()\n",
- " y_samp[i] = j\n",
- " return X_samp, y_samp\n",
- "\n",
- "\n",
- "def evaluate_classifier(nattack: int,\n",
- " simulations: int,\n",
- " X,\n",
- " y,\n",
- " classifier,\n",
- " scorer):\n",
- " classifier.set_params(nattack=nattack)\n",
- " classifier.fit(X, y)\n",
- " X_samp, y_samp = make_instance(nattack, simulations, X, y)\n",
- " return scorer(classifier, X_samp, y_samp)\n",
- "\n",
- "\n",
- "def average_rank_score(y_true, y_pred, labels=None):\n",
- " y_true = np.asarray(y_true)\n",
- " y_pred = np.asarray(y_pred)\n",
- " \n",
- " n_samples, n_classes = y_pred.shape\n",
- " if labels is not None:\n",
- " labels = np.asarray(labels)\n",
- " if len(labels) != n_classes:\n",
- " raise ValueError()\n",
- " label_indexes = np.searchsorted(labels, y_true)\n",
- " indexes = np.where(labels[label_indexes] == y_true, label_indexes, -1)\n",
- " else:\n",
- " indexes = y_true\n",
- " true_scores = y_pred[np.arange(n_samples), indexes]\n",
- " \n",
- " counts_higher = np.sum(y_pred > true_scores[:, None], axis=1)\n",
- " \n",
- " ranks = counts_higher + 1\n",
- " \n",
- " return ranks.mean()\n",
- "\n",
- "X = np.array([[0.7, 0.7, 0.1], [0.3, 0.7, 0.1], [0.2, 0.5, 0.1], [0.1, 0.1, 0.4]])\n",
- "y = np.array([1, 2, 3, 4])\n",
- "\n",
- "euc = EuclidClassifier(nattack=100).fit(X, y)\n",
- "label = euc.predict(np.array([20, 50, 10]).reshape(1, -1))\n",
- "dec = euc.decision_function(np.array([[20, 50, 10], [70, 60, 20]]))\n",
- "print(label)\n",
- "print(dec)\n",
- "\n",
- "clf = BayesClassifier(nattack=100).fit(X, y)\n",
- "label = clf.predict(np.array([20, 50, 10]).reshape(1, -1))\n",
- "ps = clf.predict_proba(np.array([20, 50, 10]).reshape(1, -1))\n",
- "print(label)\n",
- "print(ps)\n",
- "\n",
- "\n",
- "acc = top_k_accuracy_score(np.array([3, 1]),\n",
- " euc.decision_function(np.array([[20, 50, 10], [70, 60, 20]])),\n",
- " labels = [1, 2, 3, 4],\n",
- " k=1)\n",
- "print(acc)\n",
- "acc = top_k_accuracy_score(np.array([3, 1]),\n",
- " clf.predict_proba(np.array([[20, 50, 10], [70, 60, 20]])),\n",
- " labels = [1, 2, 3, 4],\n",
- " k=1)\n",
- "print(acc)\n",
- "\n",
- "avg = average_rank_score(np.array([2, 0]),\n",
- " euc.decision_function(np.array([[20, 50, 10], [70, 60, 20]])))\n",
- "print(avg)\n",
- "avg = average_rank_score(np.array([3, 1]),\n",
- " euc.decision_function(np.array([[20, 50, 10], [70, 60, 20]])),\n",
- " labels = [1, 2, 3, 4])\n",
- "print(avg)\n",
- "\n",
- "accuracy_scorer = make_scorer(\n",
- " top_k_accuracy_score,\n",
- " greater_is_better=True,\n",
- " response_method=(\"decision_function\", \"predict_proba\"),\n",
- ")\n",
- "\n",
- "#accuracy_scorer.__str__ = lambda self: \"Accuracy\"\n",
- "\n",
- "top_5_scorer = make_scorer(\n",
- " top_k_accuracy_score,\n",
- " greater_is_better=True,\n",
- " response_method=(\"decision_function\", \"predict_proba\"),\n",
- " k=5\n",
- ")\n",
- "\n",
- "#top_5_scorer.__str__ = lambda self: \"Top-5 accuracy\"\n",
- "\n",
- "top_10_scorer = make_scorer(\n",
- " top_k_accuracy_score,\n",
- " greater_is_better=True,\n",
- " response_method=(\"decision_function\", \"predict_proba\"),\n",
- " k=10\n",
- ")\n",
- "\n",
- "#top_10_scorer.__str__ = lambda self: \"Top-10 accuracy\"\n",
- "\n",
- "avg_rank_scorer = make_scorer(\n",
- " average_rank_score,\n",
- " greater_is_better=False,\n",
- " response_method=(\"decision_function\", \"predict_proba\"),\n",
- ")\n",
- "\n",
- "#avg_rank_scorer.__str__ = lambda self: \"Average rank\""
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "a9fae775-797f-4efe-ac28-d83a8c905372",
- "metadata": {},
- "outputs": [],
- "source": [
- "class FeatureSelector:\n",
- " def __init__(self,\n",
- " allfeats: list[int],\n",
- " mults: dict[MultIdent, ProbMap],\n",
- " num_workers: int):\n",
- " self.allfeats = allfeats\n",
- " self.mults = mults\n",
- " self.num_workers = num_workers\n",
- "\n",
- " def prepare(self, nattack: int):\n",
- " self.nattack = nattack\n",
- "\n",
- " def select(self, nfeats: int, startwith: list[int] = None) -> list[int]:\n",
- " pass\n",
- "\n",
- "class FeaturesByClassification(FeatureSelector):\n",
- " def __init__(self,\n",
- " allfeats: list[int],\n",
- " mults: dict[MultIdent, ProbMap],\n",
- " num_workers: int,\n",
- " simulations: int,\n",
- " classifier,\n",
- " scorer):\n",
- " super().__init__(allfeats, mults, num_workers)\n",
- " self.simulations = simulations\n",
- " self.classifier = classifier\n",
- " self.scorer = scorer\n",
- "\n",
- "class RandomFeatures(FeaturesByClassification):\n",
- "\n",
- " def __init__(self,\n",
- " allfeats: list[int],\n",
- " mults: dict[MultIdent, ProbMap],\n",
- " num_workers: int,\n",
- " simulations: int,\n",
- " classifier,\n",
- " scorer,\n",
- " retries: int):\n",
- " super().__init__(allfeats, mults, num_workers, simulations, classifier, scorer)\n",
- " self.retries = retries\n",
- " \n",
- " def _select_random(self, nfeats: int, startwith: list[int] = None) -> list[int]:\n",
- " if startwith is None:\n",
- " startwith = []\n",
- " toselect = nfeats - len(startwith)\n",
- " if toselect > 0:\n",
- " available_feats = list(filter(lambda feat: feat not in startwith, self.allfeats))\n",
- " selected = random.sample(available_feats, toselect)\n",
- " return startwith + selected\n",
- " elif toselect < 0:\n",
- " return random.sample(startwith, nfeats)\n",
- " else:\n",
- " return startwith\n",
- "\n",
- " def select(self, nfeats: int, startwith: list[int] = None) -> tuple[list[int], float]:\n",
- " with TaskExecutor(max_workers=self.num_workers) as pool:\n",
- " feat_map = []\n",
- " for i in range(self.retries):\n",
- " feats = self._select_random(nfeats, startwith)\n",
- " X, y = to_sklearn(self.mults, feats)\n",
- " feat_map.append(feats)\n",
- " pool.submit_task(i,\n",
- " evaluate_classifier,\n",
- " self.nattack, self.simulations,\n",
- " X, y, self.classifier, self.scorer)\n",
- " best_score = None\n",
- " best_feats = None\n",
- " for i, future in tqdm(pool.as_completed(), total=len(pool.tasks), desc=\"retries\", leave=False):\n",
- " score = future.result()\n",
- " #print(i, feat_map[i], score)\n",
- " if best_score is None or score > best_score:\n",
- " best_score = score\n",
- " best_feats = feat_map[i]\n",
- " return best_feats, best_score\n",
- "\n",
- "\n",
- "class GreedyFeatures(FeaturesByClassification):\n",
- "\n",
- " def select(self, nfeats: int, startwith: list[int] = None) -> tuple[list[int], float]:\n",
- " if startwith is None:\n",
- " startwith = []\n",
- " toselect = nfeats - len(startwith)\n",
- " if toselect < 0:\n",
- " raise ValueError(\"No features to select.\")\n",
- " available_feats = list(filter(lambda feat: feat not in startwith, self.allfeats))\n",
- " current = list(startwith)\n",
- " with TaskExecutor(max_workers=self.num_workers) as pool:\n",
- " while toselect > 0:\n",
- " for feat in available_feats:\n",
- " feats = current + [feat]\n",
- " X, y = to_sklearn(self.mults, feats)\n",
- " pool.submit_task(feat,\n",
- " evaluate_classifier,\n",
- " self.nattack, self.simulations,\n",
- " X, y, self.classifier, self.scorer)\n",
- " best_score = None\n",
- " best_feat = None\n",
- " for feat, future in tqdm(pool.as_completed(), total=len(pool.tasks), leave=False):\n",
- " score = future.result()\n",
- " if best_score is None or score > best_score:\n",
- " best_score = score\n",
- " best_feat = feat\n",
- " current.append(best_feat)\n",
- " toselect -= 1\n",
- " return current, best_score\n",
- "\n",
- "\n",
- "def feature_search(feat_range, nattack_range, selector, restarts=False):\n",
- " if isinstance(feat_range, int):\n",
- " feat_range = [feat_range]\n",
- " if isinstance(nattack_range, int):\n",
- " nattack_range = [nattack_range]\n",
- " results = {}\n",
- " for nattack in tqdm(nattack_range, desc=\"nattack\", smoothing=0):\n",
- " selector.prepare(nattack)\n",
- " feats = []\n",
- " for nfeats in tqdm(feat_range, desc=\"nfeats\", leave=False):\n",
- " feats, score = selector.select(nfeats, [] if restarts else feats)\n",
- " results[(nattack, nfeats)] = feats\n",
- " print(f\"{nattack},{nfeats}: {feats}, {score}\")\n",
- " return results"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "f1c0bebe-c519-4241-a163-63613b929db2",
- "metadata": {},
- "outputs": [],
- "source": [
- "def plot_performance(classifier, scorer, simulations, feature_map, mults, num_workers = 30):\n",
- " scores = {}\n",
- " with TaskExecutor(max_workers=num_workers) as pool:\n",
- " for (nattack, nfeats), feats in feature_map.items():\n",
- " X, y = to_sklearn(mults, feats)\n",
- " pool.submit_task((nattack, nfeats),\n",
- " evaluate_classifier,\n",
- " nattack, simulations, X, y, classifier, scorer)\n",
- " for (nattack, nfeats), future in tqdm(pool.as_completed(), desc=\"Evaluating\", leave=False, total=len(pool.tasks)):\n",
- " score = future.result()\n",
- " scores[(nattack, nfeats)] = score\n",
- "\n",
- " x_coords = [k[0] for k in scores.keys()]\n",
- " y_coords = [k[1] for k in scores.keys()]\n",
- " \n",
- " x_unique = sorted(set(x_coords))\n",
- " y_unique = sorted(set(y_coords))\n",
- "\n",
- " heatmap_data = np.zeros((len(y_unique), len(x_unique)))\n",
- " \n",
- " for (x, y), score in scores.items():\n",
- " x_index = x_unique.index(x)\n",
- " y_index = y_unique.index(y)\n",
- " heatmap_data[y_index, x_index] = score\n",
- "\n",
- " x_mesh, y_mesh = np.meshgrid(x_unique, y_unique)\n",
- " \n",
- " plt.pcolormesh(x_mesh, y_mesh, heatmap_data, cmap='viridis', shading='auto')\n",
- " plt.colorbar(label='Score')\n",
- "\n",
- " for i in range(len(y_unique)):\n",
- " for j in range(len(x_unique)):\n",
- " plt.text(x_unique[j], y_unique[i], f'{heatmap_data[i, j]:.2f}', ha='center', va='center', color='white' if heatmap_data[i, j] < 0.4 else \"black\")\n",
- " \n",
- " x_contour, y_contour = np.meshgrid(np.linspace(min(x_unique), max(x_unique), 100), \n",
- " np.linspace(min(y_unique), max(y_unique), 100))\n",
- " z_contour = x_contour * y_contour\n",
- " \n",
- " contour = plt.contour(x_contour, y_contour, z_contour, levels=[100, 200, 300, 400, 500, 600, 700, 800, 900, 1000], colors='white', zorder=4)\n",
- " plt.clabel(contour, inline=True, fontsize=10)\n",
- " \n",
- " plt.xticks(ticks=x_unique, labels=x_unique)\n",
- " plt.yticks(ticks=y_unique, labels=y_unique)\n",
- " plt.xlabel('nattack')\n",
- " plt.ylabel('nfeats')\n",
- " plt.title(f'{scorer._score_func.__name__}{scorer._kwargs} ({classifier.__class__.__name__})')\n",
- " plt.show()"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "beb5720a-f793-4ad9-ad27-1bd943bb325b",
- "metadata": {
- "scrolled": true
- },
- "outputs": [],
- "source": [
- "feats_in_tree = Counter()\n",
- "for node in PreOrderIter(tree.root):\n",
- " if node.is_leaf:\n",
- " continue\n",
- " feats_in_tree[node.dmap_input] += 1\n",
- "feats_in_tree = set(feats_in_tree.keys())"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "6e3260c9-c0fa-4828-a749-4d34499abacf",
- "metadata": {},
- "outputs": [],
- "source": [
- "simulations = 500\n",
- "retries = 500\n",
- "nattack = range(50, 350, 50)\n",
- "nfeats = range(1, 11)\n",
- "num_workers = 30\n",
- "\n",
- "euclid_classifier = EuclidClassifier()\n",
- "tree_random_subsets = RandomFeatures(sorted(feats_in_tree), distributions_mults, num_workers,\n",
- " simulations, euclid_classifier, top_5_scorer, retries)\n",
- "\n",
- "selected_euclid_fromtree = feature_search(nfeats, nattack, tree_random_subsets, restarts=True)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "0b6a1a5b-82dd-44d4-82dc-83b16ac5bc82",
- "metadata": {},
- "outputs": [],
- "source": [
- "plot_performance(euclid_classifier, top_5_scorer, 500, selected_euclid_fromtree, distributions_mults)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "f16a5868-e92c-4b84-9f19-664627d9848a",
- "metadata": {},
- "source": [
- "## Simulate distinguishing using a Bayes classifier\n",
- "\n",
- "We need to first select some features (divisors) from the set of all divisors that we will query\n",
- "the target with. This set should be the smallest (to not do a lot of queries) yet allow us to distinguish as\n",
- "much as possible.\n",
- "\n",
- "Then, we can build a true Bayes classifier. Since our features are conditionally independent (when conditioned on the class label) in our case naive Bayes == non-naive Bayes. We examine four feature selection algorithms:\n",
- " - Feature selection by pre-selection using tree-building and final selection by random subsets + classification error.\n",
- " - Feature selection via greedy classification error.\n",
- " - Feature selection via mRMR (maximal relevance, minimal redundancy) using mutual information.\n",
- " - Feature selection via JMI (Joint Mutual Information)."
- ]
- },
- {
- "cell_type": "markdown",
- "id": "ed81e076-9ccb-445d-ada9-384b73efb2c5",
- "metadata": {},
- "source": [
- "### Feature selection using trees + classification error\n",
- "\n",
- "We can reuse the clustering + tree building approach above and just take the inputs that the greedy tree building choses as the features. However, we can also use more conventional feature selection approaches."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "1f24b323-3604-4e34-a880-9dfd611fb245",
- "metadata": {
- "scrolled": true
- },
- "outputs": [],
- "source": [
- "feats_in_tree = Counter()\n",
- "for node in PreOrderIter(tree.root):\n",
- " if node.is_leaf:\n",
- " continue\n",
- " feats_in_tree[node.dmap_input] += 1\n",
- "feats_in_tree = set(feats_in_tree.keys())"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "f1052222-ad32-4e25-97ca-851cc42bf546",
- "metadata": {},
- "outputs": [],
- "source": [
- "simulations = 500\n",
- "retries = 500\n",
- "nattack = range(50, 350, 50)\n",
- "nfeats = range(1, 11)\n",
- "num_workers = 30\n",
- "\n",
- "bayes_classifier = BayesClassifier()\n",
- "tree_random_subsets = RandomFeatures(sorted(feats_in_tree), distributions_mults, num_workers,\n",
- " simulations, bayes_classifier, top_5_scorer, retries)\n",
- "\n",
- "selected_bayes_fromtree = feature_search(nfeats, nattack, tree_random_subsets, restarts=True)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "b7d1f703-5dc6-4c00-b739-11b47205ed75",
- "metadata": {},
- "outputs": [],
- "source": [
- "plot_performance(bayes_classifier, top_5_scorer, 500, bay, distributions_mults)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "6df03e89-d517-4243-bbfb-a5f52de24bb1",
- "metadata": {},
- "source": [
- "### Feature selection via greedy classification\n",
- "We can also use the classifier itself for feature selection. We iterate over all the divisors to pick the first feature with the best classifier results in simulation. Then we iteratively add features to it."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "6e4c2313-83b0-43f8-80d6-14c39be0d9ec",
- "metadata": {},
- "outputs": [],
- "source": [
- "simulations = 500\n",
- "nattack = range(50, 350, 50)\n",
- "nfeats = range(1, 11)\n",
- "num_workers = 30\n",
- "\n",
- "bayes_classifier = BayesClassifier()\n",
- "greedy = GreedyFeatures(sorted(feats_in_tree), distributions_mults, num_workers,\n",
- " simulations, bayes_classifier, top_5_scorer)\n",
- "\n",
- "selected_bayes_greedy_fromtree = feature_search(nfeats, nattack, greedy, restarts=False)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "86f6a319-a61c-41f2-9a7a-561691884198",
- "metadata": {},
- "outputs": [],
- "source": [
- "plot_performance(bayes_classifier, top_5_scorer, 500, selected_bayes_greedy_fromtree, distributions_mults)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "69ce91fa-7475-41f1-a3ed-bc4dd97d44d6",
- "metadata": {
- "scrolled": true
- },
- "outputs": [],
- "source": [
- "simulations = 500\n",
- "nattack = range(10, 210, 10)\n",
- "nfeats = range(1, 16)\n",
- "num_workers = 30\n",
- "\n",
- "bayes_classifier = BayesClassifier()\n",
- "greedy = GreedyFeatures(allfeats, distributions_mults, num_workers,\n",
- " simulations, bayes_classifier, top_5_scorer)\n",
- "\n",
- "selected_bayes_greedy_fromall = feature_search(nfeats, nattack, greedy, restarts=False)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "54e58342-f2d8-42e9-ae63-0f0349efc8eb",
- "metadata": {},
- "outputs": [],
- "source": [
- "plot_performance(bayes_classifier, top_5_scorer, 500, gre, distributions_mults)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "ea3e2f00-9bdf-4014-9c1e-85fa48304ef3",
- "metadata": {},
- "outputs": [],
- "source": [
- "from sklearn.metrics import confusion_matrix, ConfusionMatrixDisplay\n",
- "\n",
- "nattack = 50\n",
- "nfeats = 5\n",
- "simulations = 20000\n",
- "bayes = BayesClassifier(nattack=nattack)\n",
- "X, y = to_sklearn(distributions_mults, selected_bayes_greedy_fromall[(nattack, nfeats)])\n",
- "bayes.fit(X, y)\n",
- "\n",
- "X_samp, y_samp = make_instance(nattack, simulations, X, y, progress=True)\n",
- "fig, ax = plt.subplots(figsize=(12,8))\n",
- "disp = ConfusionMatrixDisplay.from_predictions(y_samp, bayes.predict(X_samp), ax=ax, normalize=\"true\", include_values=False, xticks_rotation=\"vertical\")\n",
- "\n",
- "ticks = []\n",
- "labs = []\n",
- "kls = None\n",
- "for i, mult in enumerate(sorted(list(distributions_mults.keys()))):\n",
- " if kls is None or kls != mult.klass:\n",
- " ticks.append(i)\n",
- " labs.append(mult.klass.__name__)\n",
- " kls = mult.klass\n",
- "ax.set_xticks(ticks, labs)\n",
- "ax.set_yticks(ticks, labs)\n",
- "ax.set_xticks([], minor=True)\n",
- "ax.set_yticks([], minor=True);"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "7c030a1c-c13d-401a-bcdb-212c064681e4",
- "metadata": {},
- "source": [
- "### Feature selection via mRMR using mutual information"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "cd769175-c188-411c-af36-2973e7a0ffd1",
- "metadata": {},
- "outputs": [],
- "source": [
- "def mutual_information(class_priors, p_ci_list, n):\n",
- " \"\"\"\n",
- " Compute mutual information I(X; Y) for a binomial feature with given class parameters.\n",
- " \n",
- " Args:\n",
- " class_priors (np.array): P(Y=c), shape (num_classes,)\n",
- " p_ci_list (np.array): Binomial parameters [p_{c,i}] for each class c, shape (num_classes,)\n",
- " n (int): Number of trials in binomial distribution\n",
- " \n",
- " Returns:\n",
- " float: Mutual information I(X; Y)\n",
- " \"\"\"\n",
- " num_classes = len(class_priors)\n",
- " \n",
- " # Precompute all PMFs across x and classes\n",
- " x_values = np.arange(0, n + 1)[:, None] # (n+1, 1)\n",
- " pmfs = binom.pmf(x_values, n, p_ci_list[None, :]) # Shape: (n+1, num_classes)\n",
- " \n",
- " # Compute joint probabilities P(Y=c) * P(X=x | Y=c)\n",
- " # Multiply class_priors (shape C) with each row of pmfs (each x has shape (C,))\n",
- " # class_priors[None, :] becomes (1, C), so broadcasting works.\n",
- " joint_probs = pmfs * class_priors[None, :]\n",
- " \n",
- " # Compute P(X=x) for all x\n",
- " px = np.sum(joint_probs, axis=1)\n",
- "\n",
- " # Compute H(Y|X):\n",
- " h_ygx = 0.0\n",
- "\n",
- " for x_idx in range(n + 1):\n",
- " current_px = px[x_idx]\n",
- " \n",
- " if current_px < 1e-9: # Skip negligible probabilities\n",
- " continue\n",
- " \n",
- " cond_probs = joint_probs[x_idx] / current_px # P(Y=c | X=x)\n",
- " \n",
- " # Compute entropy H(Y|X=x) using scipy's entropy function\n",
- " h_x = entropy(cond_probs, base=2)\n",
- " \n",
- " h_ygx += current_px * h_x\n",
- " \n",
- " # Prior entropy H(Y)\n",
- " h_y = entropy(class_priors, base=2)\n",
- "\n",
- " return h_y - h_ygx\n",
- "\n",
- "\n",
- "def mutual_information_between_features(class_priors, p_ci_i, p_ci_j, n):\n",
- " \"\"\"\n",
- " Compute mutual information between two features X_i and X_j.\n",
- " \n",
- " Parameters:\n",
- " class_priors (array): Prior probabilities of each class. Shape: (num_classes,)\n",
- " p_ci_i (array): Binomial parameters for feature i across classes. Shape: (num_classes,)\n",
- " p_ci_j (array): Binomial parameters for feature j across classes. Shape: (num_classes,)\n",
- " n (int): Number of trials for the binomial distribution.\n",
- " \n",
- " Returns:\n",
- " float: Mutual information I(X_i; X_j)\n",
- " \"\"\"\n",
- " num_classes = len(class_priors)\n",
- " x_vals = np.arange(0, n + 1) # Possible values of features\n",
- " \n",
- " ### Compute marginal distributions P(Xi=x), P(Xj=y) ###\n",
- " # PMF for feature i across all classes\n",
- " pmf_i_per_class = binom.pmf(x_vals[:, None], n, p_ci_i[None, :])\n",
- " px_i = np.sum(pmf_i_per_class * class_priors[None, :], axis=1)\n",
- " entropy_xi = entropy(px_i, base=2) if not np.allclose(px_i, 0.0) else 0.0\n",
- " \n",
- " # PMF for feature j across all classes\n",
- " pmf_j_per_class = binom.pmf(x_vals[:, None], n, p_ci_j[None, :])\n",
- " px_j = np.sum(pmf_j_per_class * class_priors[None, :], axis=1)\n",
- " entropy_xj = entropy(px_j, base=2) if not np.allclose(px_j, 0.0) else 0.0\n",
- " \n",
- " ### Compute joint distribution P(Xi=x, Xj=y) ###\n",
- " joint_xy = np.zeros((n + 1, n + 1))\n",
- " \n",
- " for c in range(num_classes):\n",
- " pmf_i_c = binom.pmf(x_vals, n, p_ci_i[c])\n",
- " pmf_j_c = binom.pmf(x_vals, n, p_ci_j[c])\n",
- " \n",
- " # Outer product gives joint PMF for class c\n",
- " outer = np.outer(pmf_i_c, pmf_j_c)\n",
- " joint_xy += class_priors[c] * outer\n",
- " \n",
- " # Compute entropy of the joint distribution\n",
- " epsilon = 1e-10 # To avoid log(0) issues\n",
- " non_zero = (joint_xy > epsilon)\n",
- " entropy_joint = -np.sum(joint_xy[non_zero] * np.log2(joint_xy[non_zero]))\n",
- " \n",
- " ### Mutual Information ###\n",
- " mi = entropy_xi + entropy_xj - entropy_joint\n",
- " \n",
- " return mi\n",
- "\n",
- "\n",
- "def conditional_mutual_info(class_priors, XJ_params, XK_params, n):\n",
- " \"\"\"\n",
- " Compute I(XK; Y | XJ) using vectorization with broadcasting.\n",
- " \n",
- " Args:\n",
- " XJ_params (array): p_{c,J} for all classes c.\n",
- " XK_params (array): p_{c,K} for all classes c.\n",
- " class_priors (array): P(Y=c) for all classes c.\n",
- " n (int): Number of trials in the binomial distribution.\n",
- "\n",
- " Returns:\n",
- " float: Conditional mutual information I(XK; Y | XJ).\n",
- " \"\"\"\n",
- " K = len(class_priors)\n",
- " x_values = np.arange(n + 1)\n",
- "\n",
- " # Precompute PMFs for each class\n",
- " P_XJ_giv_Y = binom.pmf(x_values[:, None], n, XJ_params) \n",
- " P_XK_giv_Y = binom.pmf(x_values[:, None], n, XK_params) \n",
- "\n",
- " P_XJ_T = P_XJ_giv_Y.T # Shape: (K, n+1)\n",
- " P_XK_T = P_XK_giv_Y.T\n",
- "\n",
- " ######################################################################\n",
- " ### Compute H(Y | XJ) ###############################################\n",
- " ######################################################################\n",
- "\n",
- " # Calculate P(XJ=xj) for all xj\n",
- " P_XJ_total = np.dot(class_priors, P_XJ_T)\n",
- "\n",
- " # Numerators of posterior probabilities P(Y=c | XJ=xj)\n",
- " numerators_YgXJ = class_priors[:, None] * P_XJ_T \n",
- "\n",
- " valid_mask = P_XJ_total > 1e-9\n",
- " posterior_YgXJ = np.zeros_like(numerators_YgXJ, dtype=float)\n",
- " posterior_YgXJ[:, valid_mask] = (\n",
- " numerators_YgXJ[:, valid_mask] / \n",
- " P_XJ_total[valid_mask]\n",
- " )\n",
- "\n",
- " log_p = np.log2(posterior_YgXJ + 1e-9) \n",
- " entropy_terms_HYgXJ = -np.sum(\n",
- " posterior_YgXJ * log_p, \n",
- " axis=0,\n",
- " where=(posterior_YgXJ > 1e-9)\n",
- " )\n",
- " \n",
- " H_Y_given_XJ = np.dot(P_XJ_total, entropy_terms_HYgXJ)\n",
- "\n",
- " ######################################################################\n",
- " ### Compute H(Y | XJ, XK) ###########################################\n",
- " ######################################################################\n",
- "\n",
- " # Broadcast to compute joint PMF P(XJ=xj, XK=xk | Y=c)\n",
- " P_XJ_giv_Y_T = P_XJ_T[..., None] # Shape: (K, n+1, 1)\n",
- " P_XK_giv_Y_T = P_XK_T[:, None, :] # Shape: (K, 1, n+1)\n",
- "\n",
- " joint_pmf_conditional = (\n",
- " P_XJ_giv_Y_T * \n",
- " P_XK_giv_Y_T\n",
- " ) # Shape: (K, n+1, n+1)\n",
- "\n",
- " numerators = class_priors[:, None, None] * joint_pmf_conditional \n",
- "\n",
- " denominators = np.sum(numerators, axis=0) # Shape: (n+1, n+1)\n",
- "\n",
- " valid_mask_3d = (denominators > 1e-9)[None, ...] # Expand for class dimension\n",
- "\n",
- " # Compute posterior probabilities using broadcasting and where\n",
- " posterior_YgXJXK = numerators / denominators[None, ...]\n",
- " posterior_YgXJXK = np.where(valid_mask_3d, posterior_YgXJXK, 0.0)\n",
- "\n",
- " log_p_joint = np.log2(posterior_YgXJXK + 1e-9) \n",
- " entropy_terms_HYgXJXK = -np.sum(\n",
- " posterior_YgXJXK * log_p_joint,\n",
- " axis=0, # Sum over classes (axis 0 is K)\n",
- " where=(posterior_YgXJXK > 1e-9),\n",
- " )\n",
- "\n",
- " H_Y_given_XJXK = np.sum(denominators * entropy_terms_HYgXJXK)\n",
- "\n",
- " ######################################################################\n",
- " ### Compute CMI #####################################################\n",
- " ######################################################################\n",
- "\n",
- " cmi = H_Y_given_XJ - H_Y_given_XJXK\n",
- "\n",
- " return max(cmi, 0.0) "
- ]
- },
- {
- "cell_type": "markdown",
- "id": "03acb79a-040e-4bc7-a235-fd80dd72addb",
- "metadata": {},
- "source": [
- "#### Relevance and redundancy\n",
- "First, lets pre-compute the relevance and redundancy metrics for mRMR (also used in JMI). We assume a uniform class prior."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "6a1ec802-7e8e-4ac1-beb8-72b6e14e5a6c",
- "metadata": {},
- "outputs": [],
- "source": [
- "def compute_priors(nmults: int):\n",
- " return np.full(nmults, 1/nmults, dtype=np.float64)\n",
- "\n",
- "def compute_probs(feats: list[int], mults_map: dict[MultIdent, ProbMap]):\n",
- " probs, _ = to_sklearn(mults_map, feats)\n",
- " return probs.T\n",
- "\n",
- "def compute_relevance(feats: list[int], priors, probs, nattack: int):\n",
- " relevance = np.zeros(nallfeats, dtype=np.float64)\n",
- " for i, divisor in enumerate(tqdm(feats)):\n",
- " mi = mutual_information(priors, probs[i, ], nattack)\n",
- " relevance[i] = mi\n",
- " return relevance\n",
- "\n",
- "def compute_redundancy(feats: list[int], priors, probs, nattack: int, num_workers: int = 30):\n",
- " nallfeats = len(feats)\n",
- " redundancy = np.zeros((nallfeats, nallfeats), dtype=np.float64)\n",
- " with TaskExecutor(max_workers=num_workers) as pool:\n",
- " for i in trange(nallfeats):\n",
- " for j in range(nallfeats):\n",
- " if i < j:\n",
- " continue\n",
- " pool.submit_task((i, j),\n",
- " mutual_information_between_features,\n",
- " priors, probs[i, ], probs[j, ], nattack)\n",
- " for (i, j), future in pool.as_completed():\n",
- " mi = future.result()\n",
- " redundancy[i][j] = mi\n",
- " redundancy[j][i] = mi\n",
- " return redundancy"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "4e14ed9b-56af-4b36-9615-0bcee45e4b40",
- "metadata": {},
- "outputs": [],
- "source": [
- "nattack = 100\n",
- "\n",
- "priors = compute_priors(nmults)\n",
- "probs = compute_probs(allfeats, distributions_mults)\n",
- "relevance = compute_relevance(allfeats, priors, probs, nattack)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "7a49f7b0-f9cf-4862-8638-0b4ba5dd4f07",
- "metadata": {},
- "outputs": [],
- "source": [
- "redundancy = compute_redundancy(allfeats, priors, probs, nattack)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "95e0b366-188f-4c65-b92c-e9b9587a8083",
- "metadata": {},
- "source": [
- "Store the relevance and redundancy arrays."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "d64cf0a1-a83f-4837-8113-5de536fb0f09",
- "metadata": {},
- "outputs": [],
- "source": [
- "with open(\"relevance.pickle\", \"wb\") as f:\n",
- " pickle.dump(relevance, f)\n",
- "with open(\"redundancy.pickle\", \"wb\") as f:\n",
- " pickle.dump(redundancy, f)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "d3223edc-f3b2-4137-bc1f-75e311ff075e",
- "metadata": {},
- "outputs": [],
- "source": [
- "class MRMRFeatures(FeatureSelector):\n",
- " def __init__(self,\n",
- " allfeats: list[int],\n",
- " mults: dict[MultIdent, ProbMap],\n",
- " num_workers: int):\n",
- " self.allfeats = allfeats\n",
- " self.mults = mults\n",
- " self.num_workers = num_workers\n",
- "\n",
- " def prepare(self, nattack: int):\n",
- " self.nattack = nattack\n",
- "\n",
- " def select(self, nfeats: int, startwith: list[int] = None) -> list[int]:\n",
- " pass\n",
- "\n",
- "\n",
- "\n",
- "def mrmr_selection(relevance, redundancy, nfeats):\n",
- " \"\"\"\n",
- " Select top features using mRMR.\n",
- " \n",
- " Returns:\n",
- " indices of selected features.\n",
- " \"\"\"\n",
- " selected_indices = []\n",
- " remaining_indices = list(range(nallfeats))\n",
- " \n",
- " # Initialize by selecting the most relevant feature\n",
- " first_feature_idx = np.argmax(relevance)\n",
- " selected_indices.append(first_feature_idx)\n",
- " remaining_indices.remove(first_feature_idx)\n",
- " \n",
- " while len(selected_indices) < nfeats:\n",
- " candidates_scores = []\n",
- " \n",
- " for candidate in remaining_indices:\n",
- " # Compute mRMR score: relevance - average redundancy with selected features\n",
- " current_relevance = relevance[candidate]\n",
- " \n",
- " avg_red = 0.0\n",
- " if len(selected_indices) > 0:\n",
- " sum_red = np.sum(redundancy[candidate][selected_indices])\n",
- " avg_red = sum_red / len(selected_indices)\n",
- " \n",
- " score = current_relevance - avg_red\n",
- " candidates_scores.append(score)\n",
- " \n",
- " # Select the candidate with highest score\n",
- " best_candidate_idx = remaining_indices[np.argmax(candidates_scores)]\n",
- " selected_indices.append(best_candidate_idx)\n",
- " remaining_indices.remove(best_candidate_idx)\n",
- " \n",
- " return selected_indices"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "5604d599-ef63-49fc-a7c8-65fa90c15620",
- "metadata": {},
- "outputs": [],
- "source": [
- "selected_mrmr = [allfeats[i] for i in mrmr_selection(relevance, redundancy, nfeats=15)]"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "37cce925-8479-43e9-ad0c-b1d42be4991c",
- "metadata": {},
- "outputs": [],
- "source": [
- "mrmrs = {}\n",
- "for nfeats in trange(1, 41, 1):\n",
- " f = [allfeats[i] for i in mrmr_selection(relevance, redundancy, nfeats=nfeats)]\n",
- " for nattack in range(5, 105, 5):\n",
- " mrmrs[(nattack, nfeats)] = f\n",
- "\n",
- "bayes_classifier = BayesClassifier()\n",
- "plot_performance(bayes_classifier, avg_rank_scorer, 2000, mrmrs, distributions_mults)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "2a8bef1c-800b-453b-b239-29ea1481213b",
- "metadata": {},
- "outputs": [],
- "source": [
- "plt.close()"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "a12b75cd-3c62-4b87-a7df-f0c5f7748386",
- "metadata": {},
- "source": [
- "### Feature selection via JMI"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "d8b3f827-baef-49c2-af60-0be74ff0efa2",
- "metadata": {},
- "outputs": [],
- "source": [
- "def jmi_selection(features_params_list, class_priors, n_trials, relevance, nfeats):\n",
- " \"\"\"\n",
- " Select top features using JMI.\n",
- " \n",
- " Returns:\n",
- " indices of selected features.\n",
- " \"\"\"\n",
- " selected_indices = []\n",
- " remaining_indices = list(range(nallfeats))\n",
- " \n",
- " # Initialize by selecting the most relevant feature\n",
- " first_feature_idx = np.argmax(relevance)\n",
- " selected_indices.append(first_feature_idx)\n",
- " remaining_indices.remove(first_feature_idx)\n",
- " \n",
- " while len(selected_indices) < nfeats:\n",
- " candidates_scores = []\n",
- " \n",
- " for candidate in tqdm(remaining_indices):\n",
- " # Compute mRMR score: relevance - average redundancy with selected features\n",
- " current_relevance = relevance[candidate]\n",
- " \n",
- " sum_cmi = 0.0\n",
- " for selected in selected_indices:\n",
- " XJ_params = features_params_list[selected]\n",
- " XK_params = features_params_list[candidate]\n",
- " \n",
- " cmi_val = conditional_mutual_info(\n",
- " class_priors=class_priors,\n",
- " XJ_params=XJ_params,\n",
- " XK_params=XK_params,\n",
- " n=n_trials\n",
- " )\n",
- " sum_cmi += cmi_val\n",
- " avg_cmi = sum_cmi / len(selected_indices)\n",
- " score = current_relevance + avg_cmi\n",
- " candidates_scores.append(score)\n",
- " \n",
- " # Select the candidate with highest score\n",
- " best_candidate_idx = remaining_indices[np.argmax(candidates_scores)]\n",
- " selected_indices.append(best_candidate_idx)\n",
- " remaining_indices.remove(best_candidate_idx)\n",
- " \n",
- " return selected_indices"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "216a22d8-f27f-4584-8769-bd575ed538b1",
- "metadata": {},
- "outputs": [],
- "source": []
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "6739192e-879a-4862-b862-6a8fc3939b73",
- "metadata": {},
- "outputs": [],
- "source": [
- "nattack = 100\n",
- "selected_jmi = [allfeats[i] for i in jmi_selection(probs, priors, nattack, relevance, nfeats=40)]"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "7c65b785-0131-4d41-9131-b519bf446803",
- "metadata": {},
- "outputs": [],
- "source": [
- "selected_jmi"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "899dd2fa-409a-4e6c-aa13-f2d6b0088627",
- "metadata": {},
- "outputs": [],
- "source": [
- "mrmrs[(100,5)]"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "9a894db6-0e4d-49c6-b259-cc9bd28e8c8f",
- "metadata": {},
- "outputs": [],
- "source": [
- "jmis = {}\n",
- "for nfeats in range(1, 6, 1):\n",
- " f = selected_jmi[:nfeats]\n",
- " for nattack in range(5, 105, 5):\n",
- " jmis[(nattack, nfeats)] = f\n",
- "\n",
- "bayes_classifier = BayesClassifier()\n",
- "plot_performance(bayes_classifier, avg_rank_scorer, 2000, jmis, distributions_mults)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "4c29cc75-7bee-47d0-b0cb-c0f5a7ec5da0",
- "metadata": {},
- "outputs": [],
- "source": [
- "plt.close()"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "c5598117-4c54-4721-9fc5-68432fb8e230",
- "metadata": {},
- "outputs": [],
- "source": []
- }
- ],
- "metadata": {
- "kernelspec": {
- "display_name": "Python 3 (ipykernel)",
- "language": "python",
- "name": "python3"
- },
- "language_info": {
- "codemirror_mode": {
- "name": "ipython",
- "version": 3
- },
- "file_extension": ".py",
- "mimetype": "text/x-python",
- "name": "python",
- "nbconvert_exporter": "python",
- "pygments_lexer": "ipython3",
- "version": "3.12.3"
- }
- },
- "nbformat": 4,
- "nbformat_minor": 5
-}
diff --git a/analysis/countermeasures/formulas.ipynb b/analysis/countermeasures/formulas.ipynb
deleted file mode 100644
index edac069..0000000
--- a/analysis/countermeasures/formulas.ipynb
+++ /dev/null
@@ -1,666 +0,0 @@
-{
- "cells": [
- {
- "cell_type": "markdown",
- "id": "672213e3-f426-4113-b5b6-304002474ce3",
- "metadata": {},
- "source": [
- "# Formula analysis\n",
- "\n",
- "This notebook analyzes behavior of formulas from the EFD in various exceptional cases, such as operating on the point at infinity or the all zero point they sometimes degenerate into."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 2,
- "id": "09d92ba3-ede4-40c3-a061-a9c328e26fb5",
- "metadata": {},
- "outputs": [],
- "source": [
- "import io\n",
- "import json\n",
- "\n",
- "from pprint import pprint\n",
- "import tabulate\n",
- "from IPython.display import HTML, display\n",
- "\n",
- "from pyecsca.ec.params import load_params_ecgen\n",
- "from pyecsca.ec.coordinates import AffineCoordinateModel\n",
- "from pyecsca.ec.model import ShortWeierstrassModel\n",
- "from pyecsca.ec.point import Point\n",
- "from pyecsca.ec.mod import mod\n",
- "from pyecsca.ec.error import UnsatisfiedAssumptionError\n",
- "from pyecsca.misc.cfg import TemporaryConfig"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 3,
- "id": "5155a3ab-fd65-4add-ac3d-413de337c849",
- "metadata": {},
- "outputs": [],
- "source": [
- "model = ShortWeierstrassModel()\n",
- "affine_coords = AffineCoordinateModel(model)\n",
- "\n",
- "curve_data = b\"\"\"[{\n",
- " \"field\": {\n",
- " \"p\": \"0x57880ae612d14d33afd0c965938ac1ba44824036cea5d4a1699a9f44000fb273\"\n",
- " },\n",
- " \"a\": \"0x55d376d1fbcc919da841bb13352d4e419ac85a100fb806014bed884db5916399\",\n",
- " \"b\": \"0x21e27f7a065039ee59fd6b12c33d96709642aa6ac3738bd4f66fc663c79a19f8\",\n",
- " \"order\": \"0x57880ae612d14d33afd0c965938ac1b91f16808ee875095bafed41e136ca7bfe\",\n",
- " \"subgroups\": [\n",
- " {\n",
- " \"x\": \"0x407d5c52d9ad6f25bd7ff25f07804b4e4ebd4f5c992eafeb8c92e33f81e73b85\",\n",
- " \"y\": \"0x4b92eefcfa7c5e295c7e649801b83649156974064a8649f9a94f915754bd2183\",\n",
- " \"order\": \"0x57880ae612d14d33afd0c965938ac1b91f16808ee875095bafed41e136ca7bfe\",\n",
- " \"cofactor\": \"0x1\",\n",
- " \"points\": [\n",
- " {\n",
- " \"x\": \"0x2571326cc99fe050bfe1a6a02ea635c56504e49d122152fd281761748a0501d9\",\n",
- " \"y\": \"0x0000000000000000000000000000000000000000000000000000000000000000\",\n",
- " \"order\": \"0x2\"\n",
- " },\n",
- " {\n",
- " \"x\": \"0x266a5c5927e4f6feec30a9f3e2acb535657f365e1a24c1bb0b0d9158a7668639\",\n",
- " \"y\": \"0x49c431e2a2704efb4b193e0fa26c60f815eaf195f712befd53b7bafb72b98488\",\n",
- " \"order\": \"0x2bc405730968a699d7e864b2c9c560dc8f8b4047743a84add7f6a0f09b653dff\"\n",
- " }\n",
- " ]\n",
- " }\n",
- " ]\n",
- "}]\"\"\"\n",
- "curve_json = json.loads(curve_data)[0]\n",
- "p = int(curve_json[\"field\"][\"p\"], 16)\n",
- "order2_aff = Point(affine_coords,\n",
- " x=mod(int(curve_json[\"subgroups\"][0][\"points\"][0][\"x\"], 16), p),\n",
- " y=mod(int(curve_json[\"subgroups\"][0][\"points\"][0][\"y\"], 16), p))\n",
- "orderbig_aff = Point(affine_coords,\n",
- " x=mod(int(curve_json[\"subgroups\"][0][\"points\"][1][\"x\"], 16), p),\n",
- " y=mod(int(curve_json[\"subgroups\"][0][\"points\"][1][\"y\"], 16), p))\n",
- "\n",
- "def allzero(pt):\n",
- " return all(value == 0 for value in pt.coords.values())\n",
- "\n",
- "def affine(pt):\n",
- " try:\n",
- " pt.to_affine()\n",
- " except Exception:\n",
- " return False\n",
- " return True\n",
- "\n",
- "def on_curve(curve, pt):\n",
- " try:\n",
- " return curve.is_on_curve(pt)\n",
- " except Exception:\n",
- " return False\n",
- "\n",
- "def eval_test(expected, out, curve):\n",
- " return (expected.equals_homog(out) if expected is not None else \"Undefined\", allzero(out), affine(out), on_curve(curve, out), out)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 4,
- "id": "e045a4cf-97db-4a2f-a191-582987f6473d",
- "metadata": {},
- "outputs": [
- {
- "name": "stdout",
- "output_type": "stream",
- "text": [
- "Skipping jacobian-3, unsatisfied assumption\n",
- "Skipping jacobian-0, unsatisfied assumption\n",
- "Skipping projective-1, unsatisfied assumption\n",
- "Skipping projective-3, unsatisfied assumption\n",
- "Skipping w12-0, unsatisfied assumption\n",
- "Skipping xyzz-3, unsatisfied assumption\n"
- ]
- }
- ],
- "source": [
- "results_add = {}\n",
- "results_dbl = {}\n",
- "\n",
- "with TemporaryConfig() as cfg:\n",
- " cfg.ec.unsatisfied_formula_assumption_action = \"ignore\"\n",
- " for coords_name, coords in model.coordinates.items():\n",
- " try:\n",
- " params = load_params_ecgen(io.BytesIO(curve_data), coords_name, infty=False)\n",
- " except UnsatisfiedAssumptionError:\n",
- " print(f\"Skipping {coords_name}, unsatisfied assumption\")\n",
- " continue\n",
- " results_add[coords_name] = {}\n",
- " results_dbl[coords_name] = {}\n",
- " infty = params.curve.neutral\n",
- " order2 = order2_aff.to_model(coords, params.curve)\n",
- " orderbig = orderbig_aff.to_model(coords, params.curve)\n",
- " orderbig_neg = params.curve.affine_negate(orderbig_aff).to_model(coords, params.curve)\n",
- " orderbig2 = params.curve.affine_double(orderbig_aff).to_model(coords, params.curve)\n",
- " r1_aff = params.curve.affine_random()\n",
- " r1 = r1_aff.to_model(coords, params.curve)\n",
- " r2_aff = params.curve.affine_add(order2_aff, r1_aff)\n",
- " r2 = r2_aff.to_model(coords, params.curve)\n",
- " zeros = Point(coords, **{var: mod(0, p) for var in coords.variables})\n",
- "\n",
- " adds = set(formula for formula in coords.formulas.values() if formula.shortname == \"add\")\n",
- " dbls = set(formula for formula in coords.formulas.values() if formula.shortname == \"dbl\")\n",
- " for add in adds:\n",
- " res = {}\n",
- " results_add[coords_name][add.name] = res\n",
- " # P + P = ?\n",
- " PpP = add(p, orderbig, orderbig, **params.curve.parameters)[0]\n",
- " # P + infty = ?\n",
- " PpInfty = add(p, orderbig, infty, **params.curve.parameters)[0]\n",
- " InftypP = add(p, infty, orderbig, **params.curve.parameters)[0]\n",
- " # ord2 + ord2 = ?\n",
- " O2pO2 = add(p, order2, order2, **params.curve.parameters)[0]\n",
- " # P + Q = infty\n",
- " EqInfty1 = add(p, orderbig, orderbig_neg, **params.curve.parameters)[0]\n",
- " EqInfty2 = add(p, orderbig_neg, orderbig, **params.curve.parameters)[0]\n",
- " # P + zeros = ?\n",
- " PpZeros = add(p, orderbig, zeros, **params.curve.parameters)[0]\n",
- " ZerospP = add(p, zeros, orderbig, **params.curve.parameters)[0]\n",
- " # P1 + P2 = ord2\n",
- " PpQord2 = add(p, r1, r2, **params.curve.parameters)[0]\n",
- " res[\"PpP\"] = eval_test(orderbig2, PpP, params.curve)\n",
- " res[\"PpInfty\"] = eval_test(orderbig, PpInfty, params.curve)\n",
- " res[\"InftypP\"] = eval_test(orderbig, InftypP, params.curve)\n",
- " res[\"O2pO2\"] = eval_test(infty, O2pO2, params.curve)\n",
- " res[\"EqInfty1\"] = eval_test(infty, EqInfty1, params.curve)\n",
- " res[\"EqInfty2\"] = eval_test(infty, EqInfty2, params.curve)\n",
- " res[\"PpZeros\"] = eval_test(None, PpZeros, params.curve)\n",
- " res[\"ZerospP\"] = eval_test(None, ZerospP, params.curve)\n",
- " res[\"PpQord2\"] = eval_test(order2, PpQord2, params.curve)\n",
- " for dbl in dbls:\n",
- " res = {}\n",
- " results_dbl[coords_name][dbl.name] = res\n",
- " O2twice = dbl(p, order2, **params.curve.parameters)[0]\n",
- " Inftytwice = dbl(p, infty, **params.curve.parameters)[0]\n",
- " Zerostwice = dbl(p, zeros, **params.curve.parameters)[0]\n",
- " res[\"O2twice\"] = eval_test(infty, O2twice, params.curve)\n",
- " res[\"Inftytwice\"] = eval_test(infty, Inftytwice, params.curve)\n",
- " res[\"Zerostwice\"] = eval_test(None, Zerostwice, params.curve)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "847be8ca-6bed-47ff-b809-37d5e9b7b80a",
- "metadata": {
- "cell_style": "width: 700px; word-wrap: break-word;",
- "editable": true,
- "slideshow": {
- "slide_type": ""
- },
- "tags": []
- },
- "source": [
- "## Results (add)\n",
- " - `P + P = ?`: Two behavior classes, complete formulas (RCB) and incomplete formulas.\n",
- " For the complete, the result is correct, can be made affine and is on curve.\n",
- " For the incomplete formulas the result is zeros, not affine and not on the curve.\n",
- " - `P + infty = P` and `infty + P = P`: Four behavior classes, **for some the order matters**:\n",
- " most of the `madd`s and `zadd`s. This is because they have an assumption `Z2 = 1`. Some\n",
- " `madd`s fail the same in both cases.\n",
- " > Not correct, zeros, not affine, not on curve\n",
- " \n",
- " > Correct, not zeros, affine, on curve\n",
- " \n",
- " > Not correct, not zeros, affine, not on curve\n",
- " \n",
- " > Not correct, not zeros, not affine, not on curve\n",
- " - `Ord2 + Ord2 = infty`: Two behavior classes. Either correct behavior or zeros. Correct behavior for four fomulas on projective coords:\n",
- " `add-2002-bj, add-2007-bl, add-2015-rcb, madd-2015-rcb`\n",
- " - `P + -P = infty` and `-P + P = infty`: All correct, no zeros, no affine, on curve.\n",
- " - `zeros + P = ?` and `P + zeros = ?`: Three behavior classes, in one, the zeros propagate, in another the formula makes up an affine point\n",
- " that is not zeros but is not on the curve. In the final class, the formula makes up some point that is neither zeros, nor affine nor on the curve.\n",
- " - `P + Q = Ord2`: The exceptional case for (otherwise complete) RCB formulas."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 5,
- "id": "d0928c16-9688-4d65-a559-5895d1b7c85b",
- "metadata": {
- "editable": true,
- "slideshow": {
- "slide_type": ""
- },
- "tags": []
- },
- "outputs": [
- {
- "data": {
- "text/html": [
- "<table>\n",
- "<thead>\n",
- "<tr><th>Coords </th><th>Formula </th><th>Test </th><th>Correct? </th><th>Zeros? </th><th>Affine? </th><th>On curve? </th></tr>\n",
- "</thead>\n",
- "<tbody>\n",
- "<tr><td>projective</td><td>madd-2015-rcb </td><td>PpP </td><td>True </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>madd-2015-rcb </td><td>PpInfty </td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>madd-2015-rcb </td><td>InftypP </td><td>True </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>madd-2015-rcb </td><td>O2pO2 </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>madd-2015-rcb </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>madd-2015-rcb </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>madd-2015-rcb </td><td>PpZeros </td><td>Undefined </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>madd-2015-rcb </td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>madd-2015-rcb </td><td>PpQord2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-2007-bl </td><td>PpP </td><td>True </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-2007-bl </td><td>PpInfty </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-2007-bl </td><td>InftypP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-2007-bl </td><td>O2pO2 </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-2007-bl </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-2007-bl </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-2007-bl </td><td>PpZeros </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-2007-bl </td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-2007-bl </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>madd-1998-cmo </td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>madd-1998-cmo </td><td>PpInfty </td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>madd-1998-cmo </td><td>InftypP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>madd-1998-cmo </td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>madd-1998-cmo </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>madd-1998-cmo </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>madd-1998-cmo </td><td>PpZeros </td><td>Undefined </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>madd-1998-cmo </td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>madd-1998-cmo </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-1998-cmo </td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-1998-cmo </td><td>PpInfty </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-1998-cmo </td><td>InftypP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-1998-cmo </td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-1998-cmo </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-1998-cmo </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-1998-cmo </td><td>PpZeros </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-1998-cmo </td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-1998-cmo </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>mmadd-1998-cmo</td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>mmadd-1998-cmo</td><td>PpInfty </td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>mmadd-1998-cmo</td><td>InftypP </td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>mmadd-1998-cmo</td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>mmadd-1998-cmo</td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>mmadd-1998-cmo</td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>mmadd-1998-cmo</td><td>PpZeros </td><td>Undefined </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>mmadd-1998-cmo</td><td>ZerospP </td><td>Undefined </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>mmadd-1998-cmo</td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-2015-rcb </td><td>PpP </td><td>True </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-2015-rcb </td><td>PpInfty </td><td>True </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-2015-rcb </td><td>InftypP </td><td>True </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-2015-rcb </td><td>O2pO2 </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-2015-rcb </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-2015-rcb </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-2015-rcb </td><td>PpZeros </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-2015-rcb </td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-2015-rcb </td><td>PpQord2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-2002-bj </td><td>PpP </td><td>True </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-2002-bj </td><td>PpInfty </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-2002-bj </td><td>InftypP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-2002-bj </td><td>O2pO2 </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-2002-bj </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-2002-bj </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-2002-bj </td><td>PpZeros </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-2002-bj </td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-2002-bj </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-1998-cmo-2</td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-1998-cmo-2</td><td>PpInfty </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-1998-cmo-2</td><td>InftypP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-1998-cmo-2</td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-1998-cmo-2</td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-1998-cmo-2</td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>add-1998-cmo-2</td><td>PpZeros </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-1998-cmo-2</td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>add-1998-cmo-2</td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>modified </td><td>add-2009-bl </td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>add-2009-bl </td><td>PpInfty </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>add-2009-bl </td><td>InftypP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>add-2009-bl </td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>add-2009-bl </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>modified </td><td>add-2009-bl </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>modified </td><td>add-2009-bl </td><td>PpZeros </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>add-2009-bl </td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>add-2009-bl </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>modified </td><td>add-1998-cmo-2</td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>add-1998-cmo-2</td><td>PpInfty </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>add-1998-cmo-2</td><td>InftypP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>add-1998-cmo-2</td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>add-1998-cmo-2</td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>modified </td><td>add-1998-cmo-2</td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>modified </td><td>add-1998-cmo-2</td><td>PpZeros </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>add-1998-cmo-2</td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>add-1998-cmo-2</td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>modified </td><td>mmadd-2009-bl </td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>mmadd-2009-bl </td><td>PpInfty </td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>mmadd-2009-bl </td><td>InftypP </td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>mmadd-2009-bl </td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>mmadd-2009-bl </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>modified </td><td>mmadd-2009-bl </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>modified </td><td>mmadd-2009-bl </td><td>PpZeros </td><td>Undefined </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>mmadd-2009-bl </td><td>ZerospP </td><td>Undefined </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>mmadd-2009-bl </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>modified </td><td>madd-2009-bl </td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>madd-2009-bl </td><td>PpInfty </td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>madd-2009-bl </td><td>InftypP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>madd-2009-bl </td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>madd-2009-bl </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>modified </td><td>madd-2009-bl </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>modified </td><td>madd-2009-bl </td><td>PpZeros </td><td>Undefined </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>madd-2009-bl </td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>madd-2009-bl </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>xyzz </td><td>mmadd-2008-s </td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>xyzz </td><td>mmadd-2008-s </td><td>PpInfty </td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>xyzz </td><td>mmadd-2008-s </td><td>InftypP </td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>xyzz </td><td>mmadd-2008-s </td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>xyzz </td><td>mmadd-2008-s </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xyzz </td><td>mmadd-2008-s </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xyzz </td><td>mmadd-2008-s </td><td>PpZeros </td><td>Undefined </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>xyzz </td><td>mmadd-2008-s </td><td>ZerospP </td><td>Undefined </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>xyzz </td><td>mmadd-2008-s </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>xyzz </td><td>add-2008-s </td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>xyzz </td><td>add-2008-s </td><td>PpInfty </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>xyzz </td><td>add-2008-s </td><td>InftypP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>xyzz </td><td>add-2008-s </td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>xyzz </td><td>add-2008-s </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xyzz </td><td>add-2008-s </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xyzz </td><td>add-2008-s </td><td>PpZeros </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>xyzz </td><td>add-2008-s </td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>xyzz </td><td>add-2008-s </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>xyzz </td><td>madd-2008-s </td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>xyzz </td><td>madd-2008-s </td><td>PpInfty </td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>xyzz </td><td>madd-2008-s </td><td>InftypP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>xyzz </td><td>madd-2008-s </td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>xyzz </td><td>madd-2008-s </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xyzz </td><td>madd-2008-s </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xyzz </td><td>madd-2008-s </td><td>PpZeros </td><td>Undefined </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>xyzz </td><td>madd-2008-s </td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>xyzz </td><td>madd-2008-s </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>add-2001-b </td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-2001-b </td><td>PpInfty </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-2001-b </td><td>InftypP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-2001-b </td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-2001-b </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>add-2001-b </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>add-2001-b </td><td>PpZeros </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-2001-b </td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-2001-b </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1986-cc </td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1986-cc </td><td>PpInfty </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1986-cc </td><td>InftypP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1986-cc </td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1986-cc </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1986-cc </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1986-cc </td><td>PpZeros </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1986-cc </td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1986-cc </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-cmo-2</td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-cmo-2</td><td>PpInfty </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-cmo-2</td><td>InftypP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-cmo-2</td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-cmo-2</td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-cmo-2</td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-cmo-2</td><td>PpZeros </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-cmo-2</td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-cmo-2</td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2004-hmv </td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2004-hmv </td><td>PpInfty </td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2004-hmv </td><td>InftypP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2004-hmv </td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2004-hmv </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2004-hmv </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2004-hmv </td><td>PpZeros </td><td>Undefined </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2004-hmv </td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2004-hmv </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>add-2007-bl </td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-2007-bl </td><td>PpInfty </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-2007-bl </td><td>InftypP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-2007-bl </td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-2007-bl </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>add-2007-bl </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>add-2007-bl </td><td>PpZeros </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-2007-bl </td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-2007-bl </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>zadd-2007-m </td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>zadd-2007-m </td><td>PpInfty </td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>zadd-2007-m </td><td>InftypP </td><td>False </td><td>False </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>zadd-2007-m </td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>zadd-2007-m </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>zadd-2007-m </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>zadd-2007-m </td><td>PpZeros </td><td>Undefined </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>zadd-2007-m </td><td>ZerospP </td><td>Undefined </td><td>False </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>zadd-2007-m </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2007-bl </td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2007-bl </td><td>PpInfty </td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2007-bl </td><td>InftypP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2007-bl </td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2007-bl </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2007-bl </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2007-bl </td><td>PpZeros </td><td>Undefined </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2007-bl </td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2007-bl </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>mmadd-2007-bl </td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>mmadd-2007-bl </td><td>PpInfty </td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>mmadd-2007-bl </td><td>InftypP </td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>mmadd-2007-bl </td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>mmadd-2007-bl </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>mmadd-2007-bl </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>mmadd-2007-bl </td><td>PpZeros </td><td>Undefined </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>mmadd-2007-bl </td><td>ZerospP </td><td>Undefined </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>mmadd-2007-bl </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2008-g </td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2008-g </td><td>PpInfty </td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2008-g </td><td>InftypP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2008-g </td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2008-g </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2008-g </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2008-g </td><td>PpZeros </td><td>Undefined </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2008-g </td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd-2008-g </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-hnm </td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-hnm </td><td>PpInfty </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-hnm </td><td>InftypP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-hnm </td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-hnm </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-hnm </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-hnm </td><td>PpZeros </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-hnm </td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-hnm </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-cmo </td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-cmo </td><td>PpInfty </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-cmo </td><td>InftypP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-cmo </td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-cmo </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-cmo </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-cmo </td><td>PpZeros </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-cmo </td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>add-1998-cmo </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>madd </td><td>PpP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd </td><td>PpInfty </td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd </td><td>InftypP </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd </td><td>O2pO2 </td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd </td><td>EqInfty1</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>madd </td><td>EqInfty2</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>madd </td><td>PpZeros </td><td>Undefined </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd </td><td>ZerospP </td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>madd </td><td>PpQord2 </td><td>False </td><td>False </td><td>True </td><td>True </td></tr>\n",
- "</tbody>\n",
- "</table>"
- ],
- "text/plain": [
- "<IPython.core.display.HTML object>"
- ]
- },
- "metadata": {},
- "output_type": "display_data"
- }
- ],
- "source": [
- "table = [[\"Coords\", \"Formula\", \"Test\", \"Correct?\", \"Zeros?\", \"Affine?\", \"On curve?\"]]\n",
- "test_filter = None\n",
- "groups = {}\n",
- "for coords_name, vals in results_add.items():\n",
- " for name, formula in vals.items():\n",
- " for k, v in formula.items():\n",
- " if test_filter is None or k in test_filter:\n",
- " item = (v[0], v[1], v[2], v[3])\n",
- " group = groups.setdefault(item, set())\n",
- " group.add(name + \"-\" + k + \"-\" + coords_name)\n",
- " table.append((coords_name, name, k, v[0], v[1], v[2], v[3]))\n",
- "if test_filter is not None:\n",
- " for group, formulas in groups.items():\n",
- " print(group)\n",
- " for f in sorted(formulas):\n",
- " print(f\"\\t{f}\")\n",
- "display(HTML(tabulate.tabulate(table, tablefmt=\"html\", headers=\"firstrow\")))"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "f8d713ed-7f06-4457-a921-1be0e9dddac3",
- "metadata": {},
- "source": [
- "## Results (dbl)\n",
- " - `2 * Ord2 = infty`: All correct, no zeros, no affine, on curve.\n",
- " - `2 * infty = infty`: Three behavior classes: Some formulas are correct and return infty.\n",
- " Some make up some affine point that is not zeros and not on curve.\n",
- " Some return zeros.\n",
- " - `2 * zeros = ?`: Two behavior classes, the zeros either propagate or become the infty."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 29,
- "id": "2d74db05-0606-4e54-87e0-c7fe0cbb5519",
- "metadata": {},
- "outputs": [
- {
- "data": {
- "text/html": [
- "<table>\n",
- "<thead>\n",
- "<tr><th> </th><th>Formula </th><th>Test </th><th>Correct? </th><th>Zeros? </th><th>Affine? </th><th>On curve? </th></tr>\n",
- "</thead>\n",
- "<tbody>\n",
- "<tr><td>projective</td><td>mdbl-2007-bl </td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>mdbl-2007-bl </td><td>Inftytwice</td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>mdbl-2007-bl </td><td>Zerostwice</td><td>Undefined </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>dbl-2015-rcb </td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>dbl-2015-rcb </td><td>Inftytwice</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>dbl-2015-rcb </td><td>Zerostwice</td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>dbl-1998-cmo </td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>dbl-1998-cmo </td><td>Inftytwice</td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>dbl-1998-cmo </td><td>Zerostwice</td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>dbl-2007-bl </td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>dbl-2007-bl </td><td>Inftytwice</td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>dbl-2007-bl </td><td>Zerostwice</td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>dbl-1998-cmo-2</td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>projective</td><td>dbl-1998-cmo-2</td><td>Inftytwice</td><td>False </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>projective</td><td>dbl-1998-cmo-2</td><td>Zerostwice</td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>dbl-2009-bl </td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>modified </td><td>dbl-2009-bl </td><td>Inftytwice</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>modified </td><td>dbl-2009-bl </td><td>Zerostwice</td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>mdbl-2009-bl </td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>modified </td><td>mdbl-2009-bl </td><td>Inftytwice</td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>mdbl-2009-bl </td><td>Zerostwice</td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>modified </td><td>dbl-1998-cmo-2</td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>modified </td><td>dbl-1998-cmo-2</td><td>Inftytwice</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>modified </td><td>dbl-1998-cmo-2</td><td>Zerostwice</td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>xyzz </td><td>mdbl-2008-s-1 </td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xyzz </td><td>mdbl-2008-s-1 </td><td>Inftytwice</td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>xyzz </td><td>mdbl-2008-s-1 </td><td>Zerostwice</td><td>Undefined </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xyzz </td><td>dbl-2008-s-1 </td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xyzz </td><td>dbl-2008-s-1 </td><td>Inftytwice</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xyzz </td><td>dbl-2008-s-1 </td><td>Zerostwice</td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>dbl-1998-cmo </td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>dbl-1998-cmo </td><td>Inftytwice</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>dbl-1998-cmo </td><td>Zerostwice</td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>dbl-1986-cc </td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>dbl-1986-cc </td><td>Inftytwice</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>dbl-1986-cc </td><td>Zerostwice</td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>dbl-2007-bl </td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>dbl-2007-bl </td><td>Inftytwice</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>dbl-2007-bl </td><td>Zerostwice</td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>dbl-1998-cmo-2</td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>dbl-1998-cmo-2</td><td>Inftytwice</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>dbl-1998-cmo-2</td><td>Zerostwice</td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>dbl-1998-hnm </td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>dbl-1998-hnm </td><td>Inftytwice</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>dbl-1998-hnm </td><td>Zerostwice</td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>mdbl-2007-bl </td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>jacobian </td><td>mdbl-2007-bl </td><td>Inftytwice</td><td>False </td><td>False </td><td>True </td><td>False </td></tr>\n",
- "<tr><td>jacobian </td><td>mdbl-2007-bl </td><td>Zerostwice</td><td>Undefined </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xz </td><td>dbl-2002-bj-3 </td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xz </td><td>dbl-2002-bj-3 </td><td>Inftytwice</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xz </td><td>dbl-2002-bj-3 </td><td>Zerostwice</td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>xz </td><td>dbl-2002-bj </td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xz </td><td>dbl-2002-bj </td><td>Inftytwice</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xz </td><td>dbl-2002-bj </td><td>Zerostwice</td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>xz </td><td>dbl-2002-it-2 </td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xz </td><td>dbl-2002-it-2 </td><td>Inftytwice</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xz </td><td>dbl-2002-it-2 </td><td>Zerostwice</td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>xz </td><td>dbl-2002-it </td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xz </td><td>dbl-2002-it </td><td>Inftytwice</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xz </td><td>dbl-2002-it </td><td>Zerostwice</td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "<tr><td>xz </td><td>dbl-2002-bj-2 </td><td>O2twice </td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xz </td><td>dbl-2002-bj-2 </td><td>Inftytwice</td><td>True </td><td>False </td><td>False </td><td>True </td></tr>\n",
- "<tr><td>xz </td><td>dbl-2002-bj-2 </td><td>Zerostwice</td><td>Undefined </td><td>True </td><td>False </td><td>False </td></tr>\n",
- "</tbody>\n",
- "</table>"
- ],
- "text/plain": [
- "<IPython.core.display.HTML object>"
- ]
- },
- "metadata": {},
- "output_type": "display_data"
- }
- ],
- "source": [
- "table = [[\"Formula\", \"Test\", \"Correct?\", \"Zeros?\", \"Affine?\", \"On curve?\"]]\n",
- "test_filter = None\n",
- "groups = {}\n",
- "for coords_name, vals in results_dbl.items():\n",
- " for name, formula in vals.items():\n",
- " for k, v in formula.items():\n",
- " if test_filter is None or k in test_filter:\n",
- " item = (v[0], v[1], v[2], v[3])\n",
- " group = groups.setdefault(item, set())\n",
- " group.add(name + \"-\" + k + \"-\" + coords_name)\n",
- " table.append((coords_name, name, k, v[0], v[1], v[2], v[3]))\n",
- "if test_filter is not None:\n",
- " for group, formulas in groups.items():\n",
- " print(group)\n",
- " for f in sorted(formulas):\n",
- " print(f\"\\t{f}\")\n",
- "display(HTML(tabulate.tabulate(table, tablefmt=\"html\", headers=\"firstrow\")))"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "9194ed95-4aeb-4aeb-bf8f-b8e0c1f1f987",
- "metadata": {},
- "outputs": [],
- "source": []
- }
- ],
- "metadata": {
- "kernelspec": {
- "display_name": "Python 3 (ipykernel)",
- "language": "python",
- "name": "python3"
- },
- "language_info": {
- "codemirror_mode": {
- "name": "ipython",
- "version": 3
- },
- "file_extension": ".py",
- "mimetype": "text/x-python",
- "name": "python",
- "nbconvert_exporter": "python",
- "pygments_lexer": "ipython3",
- "version": "3.12.3"
- }
- },
- "nbformat": 4,
- "nbformat_minor": 5
-}
diff --git a/analysis/countermeasures/probmaps.py b/analysis/countermeasures/probmaps.py
deleted file mode 100644
index 0ad13a3..0000000
--- a/analysis/countermeasures/probmaps.py
+++ /dev/null
@@ -1,78 +0,0 @@
-import sys
-import pickle
-import itertools
-import glob
-
-from pyecsca.misc.utils import TaskExecutor
-from tqdm.auto import tqdm
-
-from common import *
-
-
-def divides_any(l: int, small_scalars: set[int]) -> bool:
- for s in small_scalars:
- if s%l==0:
- return True
- return False
-
-
-def process_small_scalars(scalar_results: MultResults, divisors: set[int]) -> ProbMap:
- result = {}
- for divisor in divisors:
- count = 0
- for smult in scalar_results.multiplications:
- if divides_any(divisor, smult):
- count += 1
- result[divisor] = count / scalar_results.samples
- return ProbMap(result, scalar_results.samples, scalar_results.kind)
-
-
-def load_chunk(fname: str, divisors: set[int], kind: str) -> dict[MultIdent, ProbMap]:
- with open(fname, "rb") as f:
- multiples = {}
- while True:
- try:
- mult, distr = pickle.load(f)
- multiples[mult] = distr
- except EOFError:
- break
- res = {}
- for mult, results in multiples.items():
- results.kind = kind
- res[mult] = process_small_scalars(results, divisors)
- return res
-
-
-if __name__ == "__main__":
- distributions_mults = {}
- bits = 256
- num_workers = int(sys.argv[1]) if len(sys.argv) > 1 else 32
- divisor_name = sys.argv[2] if len(sys.argv) > 2 else "all"
- kind = sys.argv[3] if len(sys.argv) > 3 else "precomp+necessary"
- use_init = (sys.argv[4].lower() == "true") if len(sys.argv) > 4 else True
- use_multiply = (sys.argv[5].lower() == "true") if len(sys.argv) > 5 else True
- files = sorted(glob.glob(f"multiples_{bits}_{kind}_{'init' if use_init else 'noinit'}_{'mult' if use_multiply else 'nomult'}_chunk*.pickle"))
-
- selected_divisors = divisor_map[divisor_name]
-
- with TaskExecutor(max_workers=num_workers) as pool:
- for fname in files:
- pool.submit_task(fname,
- load_chunk,
- fname, selected_divisors, kind)
- for fname, future in tqdm(pool.as_completed(), total=len(pool.tasks), smoothing=0):
- if error := future.exception():
- print(f"Error {fname}, {error}")
- continue
- new_distrs = future.result()
- for mult, prob_map in new_distrs.items():
- if mult in distributions_mults:
- distributions_mults[mult].merge(prob_map)
- else:
- distributions_mults[mult] = prob_map
- for mult, prob_map in distributions_mults.items():
- print(f"Got {prob_map.samples} for {mult}.")
-
- # Save
- with open(f"{divisor_name}_{kind}_distrs.pickle", "wb") as f:
- pickle.dump(distributions_mults, f)
diff --git a/analysis/countermeasures/simulate.ipynb b/analysis/countermeasures/simulate.ipynb
deleted file mode 100644
index 67ed0e4..0000000
--- a/analysis/countermeasures/simulate.ipynb
+++ /dev/null
@@ -1,265 +0,0 @@
-{
- "cells": [
- {
- "cell_type": "markdown",
- "id": "805d746e-610b-4d40-80d2-a8080a993f96",
- "metadata": {},
- "source": [
- "# Simulating EPA-RE using points of low-order"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "b4386513-cc14-434b-a748-2863f8657452",
- "metadata": {},
- "outputs": [],
- "source": [
- "import pickle\n",
- "import itertools\n",
- "import glob\n",
- "\n",
- "import matplotlib\n",
- "import matplotlib.pyplot as plt\n",
- "import numpy as np\n",
- "\n",
- "from collections import Counter\n",
- "\n",
- "from pathlib import Path\n",
- "from random import randint, randbytes\n",
- "from typing import Type, Any\n",
- "\n",
- "from bs4 import BeautifulSoup\n",
- "from tqdm.auto import tqdm, trange\n",
- "\n",
- "from pyecsca.ec.params import DomainParameters, get_params\n",
- "from pyecsca.ec.mult import *\n",
- "from pyecsca.sca.re.rpa import multiples_computed\n",
- "from pyecsca.misc.utils import TaskExecutor\n",
- "\n",
- "from common import *"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "5b156d2a-7345-47f8-a76e-71a7d2be9d22",
- "metadata": {},
- "source": [
- "## Initialize"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "a660e3ac-401b-47a0-92de-55afe63c420a",
- "metadata": {},
- "outputs": [],
- "source": [
- "print(len(all_mults))"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "a95b27fc-96a9-41b5-9972-dc8386ed386d",
- "metadata": {},
- "outputs": [],
- "source": [
- "print(len(all_mults_with_ctr))"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "07bc266d-35eb-4f6d-bdba-e9f6f66827f1",
- "metadata": {},
- "outputs": [],
- "source": [
- "# Needs imports on the inside to be spawn enabled to save memory.\n",
- "\n",
- "def get_general_multiples(bits: int, samples: int = 1000) -> MultResults:\n",
- " from random import randint\n",
- " results = []\n",
- " for _ in range(samples):\n",
- " big_scalar = randint(1, 2**bits)\n",
- " results.append({big_scalar})\n",
- " return MultResults(results, samples)\n",
- "\n",
- "def get_general_n_multiples(bits: int, n: int, samples: int = 1000) -> MultResults:\n",
- " from random import randint\n",
- " results = []\n",
- " for _ in range(samples):\n",
- " smult = set()\n",
- " for i in range(n):\n",
- " b = randint(1,256)\n",
- " smult.add(randint(2**b,2**(b+1)))\n",
- " results.append(smult)\n",
- " return MultResults(results, samples)\n",
- "\n",
- "def get_small_scalar_multiples(mult: MultIdent,\n",
- " params: DomainParameters,\n",
- " bits: int,\n",
- " samples: int = 100,\n",
- " use_init: bool = True,\n",
- " use_multiply: bool = True,\n",
- " seed: bytes | None = None,\n",
- " kind: str = \"precomp+necessary\") -> MultResults:\n",
- " from pyecsca.sca.re.rpa import multiples_computed\n",
- " import random\n",
- " \n",
- " results = []\n",
- " if seed is not None:\n",
- " random.seed(seed)\n",
- "\n",
- " # If no countermeasure is used, we have fully random scalars.\n",
- " # Otherwise, fix one per chunk.\n",
- " if mult.countermeasure is None:\n",
- " scalars = [random.randint(1, 2**bits) for _ in range(samples)]\n",
- " else:\n",
- " one = random.randint(1, 2**bits)\n",
- " scalars = [one for _ in range(samples)]\n",
- "\n",
- " for scalar in scalars:\n",
- " # Use a list for less memory usage.\n",
- " results.append(list(multiples_computed(scalar, params, mult.klass, mult.partial, use_init, use_multiply, kind=kind)))\n",
- " return MultResults(results, samples)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "8c5e9543-8447-4362-b9e2-c896d71f69a9",
- "metadata": {},
- "source": [
- "## Prepare"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "4d5c7f10-618f-4612-b594-81d1607b0d1d",
- "metadata": {},
- "outputs": [],
- "source": [
- "category = \"secg\"\n",
- "curve = \"secp256r1\"\n",
- "kind = \"precomp+necessary\"\n",
- "use_init = True\n",
- "use_multiply = True\n",
- "params = get_params(category, curve, \"projective\")\n",
- "num_workers = 20\n",
- "bits = params.order.bit_length()\n",
- "samples = 100\n",
- "selected_mults = all_mults"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "3aaf712e-5b97-4390-8dd4-e1db1dfe36a2",
- "metadata": {},
- "source": [
- "## Run\n",
- "Run this cell as many times as you want. It will write chunks into files."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "84359084-4116-436c-92cd-d43fdfeca842",
- "metadata": {},
- "outputs": [],
- "source": [
- "multiples_mults = {}\n",
- "chunk_id = randbytes(4).hex()\n",
- "with TaskExecutor(max_workers=num_workers, mp_context=spawn_context) as pool, enable_spawn(get_small_scalar_multiples) as target:\n",
- " for mult in selected_mults:\n",
- " for countermeasure in (None, \"gsr\", \"additive\", \"multiplicative\", \"euclidean\", \"bt\"):\n",
- " mwc = mult.with_countermeasure(countermeasure)\n",
- " pool.submit_task(mwc,\n",
- " target,\n",
- " mwc, params, bits, samples, seed=chunk_id, kind=kind, use_init=use_init, use_multiply=use_multiply)\n",
- " for mult, future in tqdm(pool.as_completed(), desc=\"Computing small scalar distributions.\", total=len(pool.tasks)):\n",
- " print(f\"Got {mult}.\")\n",
- " if error := future.exception():\n",
- " print(\"Error!\", error)\n",
- " continue\n",
- " res = future.result()\n",
- " if mult not in multiples_mults:\n",
- " multiples_mults[mult] = res\n",
- " else:\n",
- " # Accumulate\n",
- " multiples_mults[mult].merge(res)\n",
- "\n",
- " # Handle the enable_spawn trick that messes up class modules.\n",
- " for k, v in multiples_mults.items():\n",
- " v.__class__ = MultResults\n",
- " v.__module__ = \"common\"\n",
- "\n",
- "# Save\n",
- "with open(f\"multiples_{bits}_{'init' if use_init else 'noinit'}_{'mult' if use_multiply else 'nomult'}_chunk{chunk_id}.pickle\",\"wb\") as h:\n",
- " for mult, res in multiples_mults.items():\n",
- " pickle.dump((mult, res), h)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "b4471a1d-fdc3-4be7-bd61-5ddd22180b41",
- "metadata": {},
- "source": [
- "### Load\n",
- "**Beware**, the following load with try to load all chunks into memory, that will be very large.\n",
- "\n",
- "You probably dont want to run this."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "3d291832-b0c7-4c3a-9989-22079e4e0f53",
- "metadata": {},
- "outputs": [],
- "source": [
- "multiples_mults = {}\n",
- "for fname in glob.glob(f\"multiples_{bits}_{'init' if use_init else 'noinit'}_{'mult' if use_multiply else 'nomult'}_chunk*.pickle\"):\n",
- " with open(fname, \"rb\") as f:\n",
- " while True:\n",
- " try:\n",
- " mult, vals = pickle.load(f)\n",
- " if mult not in multiples_mults:\n",
- " multiples_mults[mult] = vals\n",
- " else:\n",
- " multiples_mults[mult].merge(vals)\n",
- " except EOFError:\n",
- " break"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "11b447f2-71ab-417e-a856-1724788cfc91",
- "metadata": {},
- "outputs": [],
- "source": []
- }
- ],
- "metadata": {
- "kernelspec": {
- "display_name": "Python 3 (ipykernel)",
- "language": "python",
- "name": "python3"
- },
- "language_info": {
- "codemirror_mode": {
- "name": "ipython",
- "version": 3
- },
- "file_extension": ".py",
- "mimetype": "text/x-python",
- "name": "python",
- "nbconvert_exporter": "python",
- "pygments_lexer": "ipython3",
- "version": "3.12.3"
- }
- },
- "nbformat": 4,
- "nbformat_minor": 5
-}
diff --git a/analysis/countermeasures/simulate.py b/analysis/countermeasures/simulate.py
deleted file mode 100644
index 7a0d4b0..0000000
--- a/analysis/countermeasures/simulate.py
+++ /dev/null
@@ -1,121 +0,0 @@
-#!/usr/bin/env python
-# coding: utf-8
-
-# # Simulating EPA-RE using points of low-order
-
-
-import pickle
-import itertools
-import glob
-import random
-import sys
-import time
-import os
-
-import matplotlib
-import matplotlib.pyplot as plt
-import numpy as np
-
-from collections import Counter
-
-from pathlib import Path
-from random import randint, randbytes, shuffle
-from typing import Type, Any, Tuple
-
-from bs4 import BeautifulSoup
-from tqdm.auto import tqdm, trange
-
-from pyecsca.ec.params import DomainParameters, get_params
-from pyecsca.ec.mult import *
-from pyecsca.sca.re.rpa import multiples_computed
-from pyecsca.misc.utils import TaskExecutor
-
-from common import *
-
-
-def get_general_multiples(bits: int, samples: int = 1000) -> MultResults:
- from random import randint
- results = []
- for _ in range(samples):
- big_scalar = randint(1, 2**bits)
- results.append({big_scalar})
- return MultResults(results, samples)
-
-
-def get_general_n_multiples(bits: int, n: int, samples: int = 1000) -> MultResults:
- from random import randint
- results = []
- for _ in range(samples):
- smult = set()
- for i in range(n):
- b = randint(1,256)
- smult.add(randint(2**b,2**(b+1)))
- results.append(smult)
- return MultResults(results, samples)
-
-
-def get_small_scalar_multiples(mult: MultIdent,
- params: DomainParameters,
- bits: int,
- samples: int = 1000,
- use_init: bool = True,
- use_multiply: bool = True,
- seed: bytes | None = None,
- kind: str = "precomp+necessary") -> Tuple[MultResults, float]:
-
- duration = -time.perf_counter()
- results = []
- if seed is not None:
- random.seed(seed)
-
- # If no countermeasure is used, we have fully random scalars.
- # Otherwise, fix one per chunk.
- if mult.countermeasure is None:
- scalars = [random.randint(1, 2**bits) for _ in range(samples)]
- else:
- one = random.randint(1, 2**bits)
- scalars = [one for _ in range(samples)]
-
- for scalar in scalars:
- # Use a list for less memory usage.
- results.append(list(multiples_computed(scalar, params, mult.klass, mult.partial, use_init, use_multiply, kind=kind)))
- duration += time.perf_counter()
- return MultResults(results, samples, duration=duration, kind=kind)
-
-
-if __name__ == "__main__":
- category = "secg"
- curve = "secp256r1"
- params = get_params(category, curve, "projective")
- num_workers = int(sys.argv[1]) if len(sys.argv) > 1 else 32
- bits = params.order.bit_length()
- samples = int(sys.argv[2]) if len(sys.argv) > 2 else 100
- kind = sys.argv[3] if len(sys.argv) > 3 else "precomp+necessary"
- use_init = (sys.argv[4].lower() == "true") if len(sys.argv) > 4 else True
- use_multiply = (sys.argv[5].lower() == "true") if len(sys.argv) > 5 else True
- selected_mults = all_mults
- shuffle(selected_mults)
-
- if (scratch := os.getenv("SCRATCHDIR")) is not None:
- outdir = Path(scratch)
- else:
- outdir = Path.cwd()
-
- print(f"Running on {num_workers} cores, doing {samples} samples.")
-
- chunk_id = randbytes(6).hex()
- with TaskExecutor(max_workers=num_workers) as pool:
- for mult in selected_mults:
- for countermeasure in (None, "gsr", "additive", "multiplicative", "euclidean", "bt"):
- mwc = mult.with_countermeasure(countermeasure)
- pool.submit_task(mwc,
- get_small_scalar_multiples,
- mwc, params, bits, samples, use_init=use_init, use_multiply=use_multiply, seed=chunk_id, kind=kind)
- for mult, future in tqdm(pool.as_completed(), desc="Computing small scalar distributions.", total=len(pool.tasks), smoothing=0):
- if error := future.exception():
- print("Error", mult, error)
- raise error
- res = future.result()
- print(f"Got {mult} in {res.duration}.")
- with (outdir / f"multiples_{bits}_{kind}_{'init' if use_init else 'noinit'}_{'mult' if use_multiply else 'nomult'}_chunk{chunk_id}.pickle").open("ab") as f:
- pickle.dump((mult, res), f)
diff --git a/analysis/countermeasures/visualize.ipynb b/analysis/countermeasures/visualize.ipynb
deleted file mode 100644
index 709e566..0000000
--- a/analysis/countermeasures/visualize.ipynb
+++ /dev/null
@@ -1,406 +0,0 @@
-{
- "cells": [
- {
- "cell_type": "markdown",
- "id": "52a95c74-8fc0-4021-a8e9-8587ff6f1d9e",
- "metadata": {},
- "source": [
- "# Visualizing prob-maps"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "3232df80-2a65-47ce-bc77-6a64f44d2404",
- "metadata": {},
- "outputs": [],
- "source": [
- "import pickle\n",
- "import itertools\n",
- "import glob\n",
- "import gc\n",
- "\n",
- "import matplotlib\n",
- "import matplotlib.pyplot as plt\n",
- "import numpy as np\n",
- "\n",
- "from tqdm.auto import tqdm, trange\n",
- "from statsmodels.stats.proportion import proportion_confint\n",
- "\n",
- "from pyecsca.ec.mult import *\n",
- "from pyecsca.misc.utils import TaskExecutor\n",
- "\n",
- "from common import *\n",
- "\n",
- "%matplotlib ipympl"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "4273bd5e-0ec6-4e5c-b63e-74cc325a8ece",
- "metadata": {},
- "source": [
- "## Setup\n",
- "Setup some plotting and the computations of prob-maps out of the small scalar data and divisors."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "e89e66dc-4a9b-4320-8612-a8fa9af04b69",
- "metadata": {},
- "outputs": [],
- "source": [
- "# Setup the ticks and colors deterministically.\n",
- "mult_klasses = sorted(list(set(map(lambda mult: mult.klass, all_mults))), key=lambda klass: klass.__name__)\n",
- "mult_kwarg_map = {klass: 0 for klass in mult_klasses}\n",
- "mult_cm_map = {mult: 0 for mult in all_mults}\n",
- "mult_colors = matplotlib.cm.tab20(range(len(mult_klasses)))\n",
- "mult_styles = ['-', '--', '-.', ':', (5, (10, 3)), (0, (5, 1)), (0, (3, 1, 1, 1, 1, 1)), (0, (3, 1, 1, 1)), (0, (1, 1)), (0, (3, 10, 1, 10))]\n",
- "mult_markers = [None, \"o\", \"+\", \"*\", \"^\", \"s\"]\n",
- "colors = {}\n",
- "styles = {}\n",
- "markers = {}\n",
- "for mult in all_mults:\n",
- " color = mult_colors[mult_klasses.index(mult.klass) % len(mult_colors)]\n",
- " style = mult_styles[mult_kwarg_map[mult.klass] % len(mult_styles)]\n",
- " mult_kwarg_map[mult.klass] += 1\n",
- " for cm in (None, \"gsr\", \"additive\", \"multiplicative\", \"euclidean\", \"bt\"):\n",
- " mwc = mult.with_countermeasure(cm)\n",
- " colors[mwc] = color\n",
- " styles[mwc] = style\n",
- " markers[mwc] = mult_markers[mult_cm_map[mult] % len(mult_markers)]\n",
- " mult_cm_map[mult] += 1\n",
- "\n",
- "majticks = np.arange(0, 1, 0.1)\n",
- "minticks = np.arange(0, 1, 0.05)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "2596562f-8a6a-4a25-ae82-a6b9562d8a40",
- "metadata": {},
- "source": [
- "## Divisors\n",
- "The cell below contains some interesting divisors for distinguishing scalarmults."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "bab2a086-8b3d-4e76-bf5c-46ea2b617708",
- "metadata": {},
- "outputs": [],
- "source": [
- "from common import divisor_map\n",
- "for d, ds in divisor_map.items():\n",
- " print(f\"{d:<27}\", ds[:3], \"...\", ds[-1:])"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "638f8634-1f6e-4844-a796-096611dfbac2",
- "metadata": {},
- "outputs": [],
- "source": [
- "bits = 256\n",
- "num_workers = 28"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "8b008248-a0aa-41fa-933c-f325f8eec31b",
- "metadata": {},
- "source": [
- "## Configuration\n",
- "Select the mults you want to compute the prob-maps for here as well as a set of divisors. It is good to set `all` here, compute the prob-maps for all the divisors, save them and they continue with visualizing them on subsets of divisors."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "4d2a0f19-8275-4db8-b3fc-c930d8ba2177",
- "metadata": {},
- "outputs": [],
- "source": [
- "selected_mults = all_mults\n",
- "divisor_name = \"all\"\n",
- "kind = \"precomp+necessary\"\n",
- "showci = False\n",
- "selected_divisors = divisor_map[divisor_name]"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "19d986ab-5fe7-4dd6-b5b5-4e75307217d6",
- "metadata": {},
- "outputs": [],
- "source": [
- "# Optionally, load\n",
- "with open(f\"{divisor_name}_{kind}_distrs.pickle\", \"rb\") as f:\n",
- " distributions_mults = pickle.load(f)"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "ef5b7a43-74b4-4e72-a3a1-955e175f5297",
- "metadata": {},
- "source": [
- "Now, go over all the divisor sets and visualize them (without the combs) into PNGs in the graphs/ directory."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "5ccc28f6-3994-4a0d-8639-2f6df4dddd26",
- "metadata": {},
- "outputs": [],
- "source": [
- "for mult, probmap in distributions_mults.items():\n",
- " for divisor in sorted(divisor_map[divisor_name]):\n",
- " if divisor not in probmap.probs:\n",
- " print(f\"Missing {mult}, {divisor}\")\n",
- " if probmap.kind is not None and probmap.kind != kind:\n",
- " print(\"Bad kind! Did you forget to load?\")"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "9b6f169b-07b3-4b27-ba36-8b90418cd072",
- "metadata": {},
- "source": [
- "## Plots (nocomb)\n",
- "Let's visualize all the divisor groups while looking at the multipliers and countermeasures except the comb-like ones."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "906b5d78-b3a4-4cbb-8051-092d411ba735",
- "metadata": {},
- "outputs": [],
- "source": [
- "for divisor_name in divisor_map:\n",
- " plot_mults = list(filter(lambda mult: mult in distributions_mults and mult.klass not in (CombMultiplier, BGMWMultiplier), all_mults_with_ctr))\n",
- " print(divisor_name, \"nocomb\")\n",
- " plot_divisors = sorted(divisor_map[divisor_name])\n",
- " L = len(plot_divisors)\n",
- " N = len(plot_mults)\n",
- " x = list(range(L))\n",
- " \n",
- " fig = plt.figure(figsize=(L/4+10, 24))\n",
- " ax = plt.subplot(111)\n",
- " \n",
- " vals = np.zeros((N, L))\n",
- " n_samples = 0\n",
- " for i, mult in enumerate(plot_mults):\n",
- " probmap = distributions_mults[mult]\n",
- " y_values = [probmap[l] for l in plot_divisors]\n",
- " vals[i,] = y_values\n",
- " ax.plot(x, y_values,\n",
- " color=colors[mult],\n",
- " linestyle=styles[mult],\n",
- " marker=markers[mult],\n",
- " label=str(mult) if mult.countermeasure is None else \"_nolegend_\")\n",
- " if showci:\n",
- " cis = [conf_interval(p, probmap.samples) for p in y_values]\n",
- " ci_low = [ci[0] for ci in cis]\n",
- " ci_high = [ci[1] for ci in cis]\n",
- " ax.fill_between(x, ci_low, ci_high, color=\"black\", alpha=0.1)\n",
- " n_samples += probmap.samples\n",
- " \n",
- " ax.set_title(f\"{divisor_name} ({kind})\\nSamples: \" + str(n_samples//N))\n",
- " \n",
- " #var = np.var(vals, axis=0)\n",
- " #ax.plot(x, var / np.max(var), label=\"cross-mult variance (normalized)\", ls=\"--\", lw=2, color=\"black\")\n",
- " \n",
- " ax.set_xlabel(\"divisors\")\n",
- " ax.set_ylabel(\"error probability\")\n",
- " ax.set_yticks(majticks)\n",
- " ax.set_yticks(minticks, minor=True)\n",
- " ax.set_xticks(x, plot_divisors, rotation=90)\n",
- " \n",
- " ax.grid(axis=\"y\", which=\"major\", alpha=0.7)\n",
- " ax.grid(axis=\"y\", which=\"minor\", alpha=0.3)\n",
- " ax.grid(axis=\"x\", alpha=0.7)\n",
- " plt.tight_layout()\n",
- " box = ax.get_position()\n",
- " ax.set_position([box.x0, box.y0, box.width * 0.9, box.height])\n",
- " \n",
- " ax.legend(loc='center left', bbox_to_anchor=(1, 0.5))\n",
- "\n",
- " fig.savefig(f\"graphs/{kind}-kind/{divisor_name}-nocomb{'+ci' if showci else ''}.pdf\");\n",
- " plt.close()"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "4068e7d0-addb-45d0-ba87-e572d4c82fbd",
- "metadata": {},
- "source": [
- "## Plots (allmults)\n",
- "Now, lets also do plots with allmults for all divisor groups."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "9b9aa7a8-0d9d-4ce3-a936-8ced2948f562",
- "metadata": {},
- "outputs": [],
- "source": [
- "for divisor_name in divisor_map:\n",
- " plot_mults = list(filter(lambda mult: mult in distributions_mults, all_mults_with_ctr))\n",
- " print(divisor_name, \"allmults\")\n",
- " plot_divisors = sorted(divisor_map[divisor_name])\n",
- " L = len(plot_divisors)\n",
- " N = len(plot_mults)\n",
- " x = list(range(L))\n",
- " \n",
- " fig = plt.figure(figsize=(L/4+10, 26))\n",
- " ax = plt.subplot(111)\n",
- " \n",
- " vals = np.zeros((N, L))\n",
- " n_samples = 0\n",
- " for i, mult in enumerate(plot_mults):\n",
- " probmap = distributions_mults[mult]\n",
- " y_values = [probmap[l] for l in plot_divisors]\n",
- " vals[i,] = y_values\n",
- " ax.plot(x, y_values,\n",
- " color=colors[mult],\n",
- " linestyle=styles[mult],\n",
- " marker=markers[mult],\n",
- " label=str(mult) if mult.countermeasure is None else \"_nolegend_\")\n",
- " if showci:\n",
- " cis = [conf_interval(p, probmap.samples) for p in y_values]\n",
- " ci_low = [ci[0] for ci in cis]\n",
- " ci_high = [ci[1] for ci in cis]\n",
- " ax.fill_between(x, ci_low, ci_high, color=\"black\", alpha=0.1)\n",
- " n_samples += probmap.samples\n",
- " \n",
- " ax.set_title(f\"{divisor_name} ({kind})\\nSamples(avg): \" + str(n_samples//N))\n",
- " \n",
- " #var = np.var(vals, axis=0)\n",
- " #ax.plot(x, var / np.max(var), label=\"cross-mult variance (normalized)\", ls=\"--\", lw=2, color=\"black\")\n",
- " \n",
- " ax.set_xlabel(\"divisors\")\n",
- " ax.set_ylabel(\"error probability\")\n",
- " ax.set_yticks(majticks)\n",
- " ax.set_yticks(minticks, minor=True)\n",
- " ax.set_xticks(x, plot_divisors, rotation=90)\n",
- " \n",
- " ax.grid(axis=\"y\", which=\"major\", alpha=0.7)\n",
- " ax.grid(axis=\"y\", which=\"minor\", alpha=0.3)\n",
- " ax.grid(axis=\"x\", alpha=0.7)\n",
- " plt.tight_layout()\n",
- " box = ax.get_position()\n",
- " ax.set_position([box.x0, box.y0, box.width * 0.9, box.height])\n",
- " \n",
- " ax.legend(loc='center left', bbox_to_anchor=(1, 0.5))\n",
- "\n",
- " fig.savefig(f\"graphs/{kind}-kind/{divisor_name}-allmults{'+ci' if showci else ''}.pdf\")\n",
- " plt.close()"
- ]
- },
- {
- "cell_type": "markdown",
- "id": "df2e236a-4540-4677-a7f1-563c4cc37a3e",
- "metadata": {},
- "source": [
- "## Interactive plot\n",
- "Below you can choose a concrete divisor set and visualize it with all the mults, or just some to your liking."
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "b464865d-b169-446e-a9e7-0cead699aee1",
- "metadata": {},
- "outputs": [],
- "source": [
- "#divisor_name = \"powers_of_2_large\"\n",
- "divisor_name = \"feature\"\n",
- "plot_mults = list(filter(lambda mult: mult in distributions_mults, all_mults_with_ctr))\n",
- "#plot_divisors = (61, 65, 111, 165, 1536, 12288) \n",
- "plot_divisors = (55, 65, 165, 248, 3072)\n",
- "L = len(plot_divisors)\n",
- "N = len(plot_mults)\n",
- "x = list(range(L))\n",
- "\n",
- "fig = plt.figure(figsize=(L/4+15, 24))\n",
- "ax = plt.subplot(111)\n",
- "\n",
- "vals = np.zeros((N, L))\n",
- "n_samples = 0\n",
- "for i, mult in enumerate(plot_mults):\n",
- " probmap = distributions_mults[mult]\n",
- " y_values = [probmap[l] for l in plot_divisors]\n",
- " vals[i,] = y_values\n",
- " ax.plot(x, y_values,\n",
- " color=colors[mult],\n",
- " linestyle=styles[mult],\n",
- " marker=markers[mult],\n",
- " label=str(mult) if mult.countermeasure is None else \"_nolegend_\")\n",
- " if showci:\n",
- " cis = [conf_interval(p, probmap.samples) for p in y_values]\n",
- " ci_low = [ci[0] for ci in cis]\n",
- " ci_high = [ci[1] for ci in cis]\n",
- " ax.fill_between(x, ci_low, ci_high, color=\"black\", alpha=0.1)\n",
- " n_samples += probmap.samples\n",
- "\n",
- "ax.set_title(f\"{divisor_name} ({kind})\\nSamples(avg): \" + str(n_samples//N))\n",
- "\n",
- "#var = np.var(vals, axis=0)\n",
- "#ax.plot(x, var / np.max(var), label=\"cross-mult variance (normalized)\", ls=\"--\", lw=2, color=\"black\")\n",
- "\n",
- "ax.set_xlabel(\"divisors\")\n",
- "ax.set_ylabel(\"error probability\")\n",
- "ax.set_yticks(majticks)\n",
- "ax.set_yticks(minticks, minor=True)\n",
- "ax.set_xticks(x, plot_divisors, rotation=90)\n",
- "\n",
- "ax.grid(axis=\"y\", which=\"major\", alpha=0.7)\n",
- "ax.grid(axis=\"y\", which=\"minor\", alpha=0.3)\n",
- "ax.grid(axis=\"x\", alpha=0.7)\n",
- "plt.tight_layout()\n",
- "box = ax.get_position()\n",
- "ax.set_position([box.x0, box.y0, box.width * 0.7, box.height])\n",
- "\n",
- "# Put a legend to the right of the current axis\n",
- "ax.legend(loc='center left', bbox_to_anchor=(1, 0.5))\n",
- "plt.show()"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": null,
- "id": "d68f0bfc-cdf1-4891-b0e5-0b6d1b02ded7",
- "metadata": {},
- "outputs": [],
- "source": []
- }
- ],
- "metadata": {
- "kernelspec": {
- "display_name": "Python 3 (ipykernel)",
- "language": "python",
- "name": "python3"
- },
- "language_info": {
- "codemirror_mode": {
- "name": "ipython",
- "version": 3
- },
- "file_extension": ".py",
- "mimetype": "text/x-python",
- "name": "python",
- "nbconvert_exporter": "python",
- "pygments_lexer": "ipython3",
- "version": "3.12.3"
- }
- },
- "nbformat": 4,
- "nbformat_minor": 5
-}