diff options
| author | J08nY | 2024-04-12 18:30:42 +0200 |
|---|---|---|
| committer | J08nY | 2024-04-12 18:30:42 +0200 |
| commit | 32180b7c1666fe7291aeb2ede3e54281baf8579e (patch) | |
| tree | fc6495fddf3c955290fb17f06784a3572cd6ba04 | |
| parent | 4029227ea98ed051a5d03b730a2fe04c5b6d4ef7 (diff) | |
| download | pyecsca-notebook-32180b7c1666fe7291aeb2ede3e54281baf8579e.tar.gz pyecsca-notebook-32180b7c1666fe7291aeb2ede3e54281baf8579e.tar.zst pyecsca-notebook-32180b7c1666fe7291aeb2ede3e54281baf8579e.zip | |
Proper eval script.
| -rw-r--r-- | re/eval.py | 428 | ||||
| -rw-r--r-- | re/zvp.ipynb | 260 | ||||
| -rw-r--r-- | requirements.txt | 3 |
3 files changed, 507 insertions, 184 deletions
@@ -1,6 +1,9 @@ from matplotlib import pyplot as plt +from matplotlib import colormaps import numpy as np -from scipy.stats import bernoulli +import xarray as xr +import seaborn as sns +from scipy.stats import bernoulli, binom from tqdm.notebook import tqdm, trange from pyecsca.misc.utils import TaskExecutor @@ -8,20 +11,44 @@ from pyecsca.misc.utils import TaskExecutor errs = (0, 0.1, 0.2, 0.3, 0.4, 0.5) majs = (1, 3, 5, 7, 9, 11) -nums = (4, 10, 20, 40, 60) -smpls = (1, 2, 3, 5, 10) +nums = (0, 4, 10, 20, 40, 60) +smpls = (1, 2, 3, 5, 10, 20) + +plasma = colormaps["plasma"] +viridis = colormaps["viridis"] +mako = sns.color_palette("mako", as_cmap=True) + + +def _bins_array(name): + return xr.DataArray(np.zeros((len(errs), len(majs))), dims=("err", "majority"), coords={"err": list(errs), "majority": list(majs)}, name=name) + + +def _bina_array(name): + return xr.DataArray(np.zeros((len(errs), len(errs), len(majs))), dims=("err_0", "err_1", "majority"), coords={"err_0": list(errs), "err_1": list(errs), "majority": list(majs)}, name=name) + + +def _binom_array(name): + return xr.DataArray(np.zeros((len(nums), len(smpls))), dims=("num", "sample"), coords={"num": list(nums), "sample": list(smpls)}, name=name) + def walk_symmetric(tree, err, majority, cfg): current = tree.root B = bernoulli(err) queries = 0 while not current.is_leaf: + response_map = {child.response: child for child in current.children} + dmap_index = current.dmap_index dmap_input = current.dmap_input dmap = tree.maps[dmap_index] true_response = dmap[cfg, dmap_input] + + if set(dmap.codomain) not in ({True, False}, {True, False, None}): + current = response_map[true_response] + continue + responses = [] - response = None + response = true_response for _ in range(majority): responses.append(true_response ^ B.rvs()) if responses.count(True) > (majority // 2): @@ -30,41 +57,34 @@ def walk_symmetric(tree, err, majority, cfg): if responses.count(False) > (majority // 2): response = False break - response_map = {child.response: child for child in current.children} current = response_map[response] queries += len(responses) return cfg in current.cfgs, len(current.cfgs), queries def _eval_symmetric(tree, cfg, errs, majs, num_tries): - correct_tries = np.zeros((len(errs), len(majs))) - precise_tries = np.zeros((len(errs), len(majs))) - amount_tries = np.zeros((len(errs), len(majs))) - query_tries = np.zeros((len(errs), len(majs))) - for i, err in enumerate(errs): - for j, majority in enumerate(majs): + correct_tries = _bins_array("correct") + precise_tries = _bins_array("precise") + amount_tries = _bins_array("amount") + query_tries = _bins_array("query") + + for err in errs: + for majority in majs: for _ in range(num_tries): + pos = {"err": err, "majority": majority} correct, amount, queries = walk_symmetric(tree, err, majority, cfg) - correct_tries[i, j] += correct - precise_tries[i, j] += (amount == 1) - amount_tries[i, j] += amount - query_tries[i, j] += queries + correct_tries.loc[pos] += correct + precise_tries.loc[pos] += (amount == 1) + amount_tries.loc[pos] += amount + query_tries.loc[pos] += queries return correct_tries, precise_tries, amount_tries, query_tries - -def eval_tree_symmetric(cfgs, build_tree, num_trees, num_tries, num_cores): - correct_tries = np.zeros((len(errs), len(majs))) - precise_tries = np.zeros((len(errs), len(majs))) - amount_tries = np.zeros((len(errs), len(majs))) - query_tries = np.zeros((len(errs), len(majs))) - trees = [] - with TaskExecutor(max_workers=num_cores) as pool: - for i in range(num_trees): - # Build the trees - pool.submit_task((i,), build_tree, cfgs) - for (i,), future in tqdm(pool.as_completed(), total=len(pool.tasks), desc="Building trees", smoothing=0): - trees.append(future.result()) +def eval_tree_symmetric1(cfgs, trees, num_tries, num_cores): + correct_tries = _bins_array("correct") + precise_tries = _bins_array("precise") + amount_tries = _bins_array("amount") + query_tries = _bins_array("query") with TaskExecutor(max_workers=num_cores) as pool: for i, tree in enumerate(trees): @@ -77,13 +97,24 @@ def eval_tree_symmetric(cfgs, build_tree, num_trees, num_tries, num_cores): precise_tries += p_tries amount_tries += a_tries query_tries += q_tries - total = num_trees * num_tries * len(cfgs) + total = len(trees) * num_tries * len(cfgs) correct_rate = (correct_tries * 100) / total precise_rate = (precise_tries * 100) / total amount_rate = amount_tries / total query_rate = query_tries / total - return correct_rate[...,::-1], precise_rate[...,::-1], amount_rate[...,::-1], query_rate[...,::-1] + return correct_rate, precise_rate, amount_rate, query_rate + + +def eval_tree_symmetric(cfgs, build_tree, num_trees, num_tries, num_cores): + trees = [] + with TaskExecutor(max_workers=num_cores) as pool: + for i in range(num_trees): + # Build the trees + pool.submit_task((i,), build_tree, cfgs) + for (i,), future in tqdm(pool.as_completed(), total=len(pool.tasks), desc="Building trees", smoothing=0): + trees.append(future.result()) + return eval_tree_symmetric1(cfgs, trees, num_tries, num_cores) def walk_asymmetric(tree, err_0, err_1, majority, cfg): @@ -92,12 +123,19 @@ def walk_asymmetric(tree, err_0, err_1, majority, cfg): B1 = bernoulli(err_1) queries = 0 while not current.is_leaf: + response_map = {child.response: child for child in current.children} + dmap_index = current.dmap_index dmap_input = current.dmap_input dmap = tree.maps[dmap_index] true_response = dmap[cfg, dmap_input] + + if set(dmap.codomain) not in ({True, False}, {True, False, None}): + current = response_map[true_response] + continue + responses = [] - response = None + response = true_response for _ in range(majority): responses.append(true_response ^ (B1.rvs() if true_response else B0.rvs())) if responses.count(True) > (majority // 2): @@ -106,43 +144,35 @@ def walk_asymmetric(tree, err_0, err_1, majority, cfg): if responses.count(False) > (majority // 2): response = False break - response_map = {child.response: child for child in current.children} current = response_map[response] queries += len(responses) return cfg in current.cfgs, len(current.cfgs), queries def _eval_asymmetric(tree, cfg, errs, majs, num_tries): - correct_tries = np.zeros((len(errs), len(errs), len(majs))) - precise_tries = np.zeros((len(errs), len(errs), len(majs))) - amount_tries = np.zeros((len(errs), len(errs), len(majs))) - query_tries = np.zeros((len(errs), len(errs), len(majs))) + correct_tries = _bina_array("correct") + precise_tries = _bina_array("precise") + amount_tries = _bina_array("amount") + query_tries = _bina_array("query") - for i, err_0 in enumerate(errs): - for j, err_1 in enumerate(errs): - for k, majority in enumerate(majs): + for err_0 in errs: + for err_1 in errs: + for majority in majs: for _ in range(num_tries): + pos = {"err_0": err_0, "err_1": err_1, "majority": majority} correct, amount, queries = walk_asymmetric(tree, err_0, err_1, majority, cfg) - correct_tries[i, j, k] += correct - precise_tries[i, j, k] += (amount == 1) - amount_tries[i, j, k] += amount - query_tries[i, j, k] += queries + correct_tries.loc[pos] += correct + precise_tries.loc[pos] += (amount == 1) + amount_tries.loc[pos] += amount + query_tries.loc[pos] += queries return correct_tries, precise_tries, amount_tries, query_tries -def eval_tree_asymmetric(cfgs, build_tree, num_trees, num_tries, num_cores): - correct_tries = np.zeros((len(errs), len(errs), len(majs))) - precise_tries = np.zeros((len(errs), len(errs), len(majs))) - amount_tries = np.zeros((len(errs), len(errs), len(majs))) - query_tries = np.zeros((len(errs), len(errs), len(majs))) - - trees = [] - with TaskExecutor(max_workers=num_cores) as pool: - for i in range(num_trees): - # Build the trees - pool.submit_task((i,), build_tree, cfgs) - for (i,), future in tqdm(pool.as_completed(), total=len(pool.tasks), desc="Building trees", smoothing=0): - trees.append(future.result()) +def eval_tree_asymmetric1(cfgs, trees, num_tries, num_cores): + correct_tries = _bina_array("correct") + precise_tries = _bina_array("precise") + amount_tries = _bina_array("amount") + query_tries = _bina_array("query") with TaskExecutor(max_workers=num_cores) as pool: for i, tree in enumerate(trees): @@ -155,7 +185,7 @@ def eval_tree_asymmetric(cfgs, build_tree, num_trees, num_tries, num_cores): precise_tries += p_tries amount_tries += a_tries query_tries += q_tries - total = num_trees * num_tries * len(cfgs) + total = len(trees) * num_tries * len(cfgs) correct_rate = (correct_tries * 100) / total precise_rate = (precise_tries * 100) / total @@ -164,18 +194,34 @@ def eval_tree_asymmetric(cfgs, build_tree, num_trees, num_tries, num_cores): return correct_rate, precise_rate, amount_rate, query_rate -def walk_binomial(tree, num, smpl, majority, cfg): +def eval_tree_asymmetric(cfgs, build_tree, num_trees, num_tries, num_cores): + trees = [] + with TaskExecutor(max_workers=num_cores) as pool: + for i in range(num_trees): + # Build the trees + pool.submit_task((i,), build_tree, cfgs) + for (i,), future in tqdm(pool.as_completed(), total=len(pool.tasks), desc="Building trees", smoothing=0): + trees.append(future.result()) + return eval_tree_asymmetric1(cfgs, trees, num_tries, num_cores) + + +def walk_binomial(tree, num, smpl, cfg): current = tree.root B = binom(num, 0.5) queries = 0 while not current.is_leaf: + response_map = {child.response: child for child in current.children} + dmap_index = current.dmap_index dmap_input = current.dmap_input dmap = tree.maps[dmap_index] true_response = dmap[cfg, dmap_input] + if dmap_input == "category": # ZVP/EPA special-case + current = response_map[true_response] + continue + responses = [true_response + B.rvs() - (num // 2) for _ in range(smpl)] mean = np.mean(responses) - response_map = {child.response: child for child in current.children} closest = min(response_map, key=lambda value: abs(value-mean)) current = response_map[closest] queries += smpl @@ -183,35 +229,28 @@ def walk_binomial(tree, num, smpl, majority, cfg): def _eval_binomial(tree, cfg, nums, smpls, num_tries): - correct_tries = np.zeros((len(nums), len(smpls))) - precise_tries = np.zeros((len(nums), len(smpls))) - amount_tries = np.zeros((len(nums), len(smpls))) - query_tries = np.zeros((len(nums), len(smpls))) + correct_tries = _binom_array("correct") + precise_tries = _binom_array("correct") + amount_tries = _binom_array("correct") + query_tries = _binom_array("correct") - for i, num in enumerate(nums): - for j, smpl in enumerate(smpls): + for num in nums: + for smpl in smpls: for _ in range(num_tries): + pos = {"num": num, "sample": smpl} correct, amount, queries = walk_binomial(tree, num, smpl, cfg) - correct_tries[i, j] += correct - precise_tries[i, j] += (amount == 1) - amount_tries[i, j] += amount - query_tries[i, j] += queries + correct_tries.loc[pos] += correct + precise_tries.loc[pos] += (amount == 1) + amount_tries.loc[pos] += amount + query_tries.loc[pos] += queries return correct_tries, precise_tries, amount_tries, query_tries -def eval_tree_binomial(cfgs, build_tree, num_trees, num_tries, num_cores) - correct_tries = np.zeros((len(nums), len(smpls))) - precise_tries = np.zeros((len(nums), len(smpls))) - amount_tries = np.zeros((len(nums), len(smpls))) - query_tries = np.zeros((len(nums), len(smpls))) - - trees = [] - with TaskExecutor(max_workers=num_cores) as pool: - for i in range(num_trees): - # Build the trees - pool.submit_task((i,), build_tree, cfgs) - for (i,), future in tqdm(pool.as_completed(), total=len(pool.tasks), desc="Building trees", smoothing=0): - trees.append(future.result()) +def eval_tree_binomial1(cfgs, trees, num_tries, num_cores): + correct_tries = _binom_array("correct") + precise_tries = _binom_array("precise") + amount_tries = _binom_array("amount") + query_tries = _binom_array("query") with TaskExecutor(max_workers=num_cores) as pool: for i, tree in enumerate(trees): @@ -224,78 +263,75 @@ def eval_tree_binomial(cfgs, build_tree, num_trees, num_tries, num_cores) precise_tries += p_tries amount_tries += a_tries query_tries += q_tries - total = num_trees * num_tries * len(cfgs) + total = len(trees) * num_tries * len(cfgs) correct_rate = (correct_tries * 100) / total precise_rate = (precise_tries * 100) / total amount_rate = amount_tries / total query_rate = query_tries / total return correct_rate, precise_rate, amount_rate, query_rate - -def query_rate_symmetric(query_rate): - fig, ax = plt.subplots() - im = ax.imshow(query_rate.T, cmap="plasma") - cbar_ax = fig.add_axes((0.85, 0.15, 0.04, 0.69)) - cbar = fig.colorbar(im, cax=cbar_ax) - cbar.ax.set_ylabel("Oracle query rate", rotation=-90, va="bottom") - - ax.set_xticks(np.arange(len(errs)), labels=errs) - ax.set_yticks(np.arange(len(majs)), labels=reversed(majs)) - ax.set_xlabel("error probability") - ax.set_ylabel("majority vote") - for i in range(len(errs)): - for j in range(len(majs)): - text = ax.text(i, j, f"{query_rate[i, j]:.1f}", - ha="center", va="center", color="white" if i - j <= 2 else "black") - return fig +def eval_tree_binomial(cfgs, build_tree, num_trees, num_tries, num_cores): + trees = [] + with TaskExecutor(max_workers=num_cores) as pool: + for i in range(num_trees): + # Build the trees + pool.submit_task((i,), build_tree, cfgs) + for (i,), future in tqdm(pool.as_completed(), total=len(pool.tasks), desc="Building trees", smoothing=0): + trees.append(future.result()) + return eval_tree_binomial1(cfgs, trees, num_tries, num_cores) + + +def _text_color(value, vmax, vmin, threshold): + return "white" if (value - vmin) < (vmax - vmin) * threshold else "black" -def success_rate_symmetric(correct_rate, baseline): + +def _plot_symmetric(rate, cmap, name, unit, xticks, xlabel, yticks, ylabel, color_threshold, vmin=None, vmax=None, baseline=None): fig, ax = plt.subplots() - im = ax.imshow(correct_rate.T, vmin=0, cmap="viridis") + im = ax.imshow(rate.T, cmap=cmap, origin="lower", vmin=vmin, vmax=vmax) cbar_ax = fig.add_axes((0.85, 0.15, 0.04, 0.69)) cbar = fig.colorbar(im, cax=cbar_ax) - cbar.ax.set_ylabel("Success rate", rotation=-90, va="bottom") - cbar.ax.axhline(baseline, color="red", linestyle="--") + cbar.ax.set_ylabel(name, rotation=-90, va="bottom") + if baseline: + cbar.ax.axhline(baseline, color="red", linestyle="--") + vmin = np.min(rate) if vmin is None else vmin + vmax = np.max(rate) if vmin is None else vmin - ax.set_xticks(np.arange(len(errs)), labels=errs) - ax.set_yticks(np.arange(len(majs)), labels=reversed(majs)) - ax.set_xlabel("error probability") - ax.set_ylabel("majority vote") - for i in range(len(errs)): - for j in range(len(majs)): - c_rate = correct_rate[i, j] - text = ax.text(i, j, f"{c_rate:.1f}%", - ha="center", va="center", color="white" if c_rate < 80 else "black") + ax.set_xticks(np.arange(len(xticks)), labels=xticks) + ax.set_yticks(np.arange(len(yticks)), labels=yticks) + ax.set_xlabel(xlabel) + ax.set_ylabel(ylabel) + for i in range(len(xticks)): + for j in range(len(yticks)): + value = rate[i, j] + text = ax.text(i, j, f"{value:.1f}{unit}", + ha="center", va="center", color=_text_color(value, vmax, vmin, color_threshold)) return fig +def query_rate_symmetric(query_rate): + return _plot_symmetric(query_rate, mako, "Oracle query rate (%)", "%", errs, "error probability", majs, "majority vote", 0.5) + + +def success_rate_symmetric(correct_rate, baseline=None): + return _plot_symmetric(correct_rate, viridis, "Success rate (%)", "%", errs, "error probability", majs, "majority vote", 0.8, vmin=0, vmax=100, baseline=baseline) + + +def amount_rate_symmetric(amount_rate): + return _plot_symmetric(amount_rate, plasma, "Result size", "", errs, "error probability", majs, "majority vote", 0.5) + + def precise_rate_symmetric(precise_rate): - fig, ax = plt.subplots() - im = ax.imshow(precise_rate.T, vmin=0, cmap="viridis") - cbar_ax = fig.add_axes((0.85, 0.15, 0.04, 0.69)) - cbar = fig.colorbar(im, cax=cbar_ax) - cbar.ax.set_ylabel("Precision", rotation=-90, va="bottom") - - ax.set_xticks(np.arange(len(errs)), labels=errs) - ax.set_yticks(np.arange(len(majs)), labels=reversed(majs)) - ax.set_xlabel("error probability") - ax.set_ylabel("majority vote") - for i in range(len(errs)): - for j in range(len(majs)): - p_rate = precise_rate[i, j] - text = ax.text(i, j, f"{p_rate:.1f}%", - ha="center", va="center", color="white" if p_rate < 80 else "black") - return fig + return _plot_symmetric(precise_rate, viridis, "Precision", "", errs, "error probability", majs, "majority vote", 0.8, vmin=0, vmax=100) def success_rate_vs_query_rate_symmetric(query_rate, correct_rate): fig, ax = plt.subplots() ax.grid() - for i, err in enumerate(errs): - qrs = query_rate[i, :] - crs = correct_rate[i, :] + for err in errs: + qrs = query_rate.sel(err=err) + crs = correct_rate.sel(err=err) ax.scatter(qrs, crs, label=f"error = {err}") ax.set_xlabel("oracle queries") ax.set_ylabel("success rate") @@ -306,9 +342,9 @@ def success_rate_vs_query_rate_symmetric(query_rate, correct_rate): def success_rate_vs_majority_symmetric(correct_rate): fig, ax = plt.subplots() ax.grid() - for i, err in enumerate(errs): - crs = correct_rate[i, :] - ax.plot(list(reversed(majs)), crs, label=f"error = {err}") + for err in errs: + crs = correct_rate.sel(err=err) + ax.plot(list(majs), crs, label=f"error = {err}") ax.set_xlabel("majority vote") ax.set_ylabel("success rate") ax.set_xticks(majs) @@ -325,14 +361,14 @@ def query_rate_asymmetric(query_rate_b): for col in range(3): ax = axs[row, col] level = row * 3 + col - im = ax.imshow(query_rate_b[::-1,:,level], cmap="plasma", vmin=vmin, vmax=vmax) + query_rate_level = query_rate_b.isel(majority=level) + im = ax.imshow(query_rate_level.T, cmap=mako, vmin=vmin, vmax=vmax, origin="lower") ax.set_xticks(np.arange(len(errs)), labels=errs) - ax.set_yticks(np.arange(len(errs)), labels=list(reversed(errs))) + ax.set_yticks(np.arange(len(errs)), labels=errs) for i in range(len(errs)): for j in range(len(errs)): - q = query_rate_b[i, len(errs) - j - 1, level] - q_rate = f"{q:.0f}" - text = ax.text(i, j, q_rate, ha="center", va="center", color="white" if q < (vmax - vmin)//2 else "black") + q_rate = query_rate_level[i, j] + text = ax.text(i, j, f"{q_rate:.0f}", ha="center", va="center", color=_text_color(q_rate, vmax, vmin, 0.5)) ax.set_xlabel("$e_1$") ax.set_ylabel("$e_O$") ax.set_title(majs[level]) @@ -350,14 +386,14 @@ def success_rate_asymmetric(correct_rate_b, baseline): for col in range(3): ax = axs[row, col] level = row * 3 + col - im = ax.imshow(correct_rate_b[::-1,:,level], cmap="viridis", vmin=0, vmax=100) + correct_rate_level = correct_rate_b.isel(majority=level) + im = ax.imshow(correct_rate_level.T, cmap=viridis, vmin=0, vmax=100, origin="lower") ax.set_xticks(np.arange(len(errs)), labels=errs) - ax.set_yticks(np.arange(len(errs)), labels=list(reversed(errs))) + ax.set_yticks(np.arange(len(errs)), labels=errs) for i in range(len(errs)): for j in range(len(errs)): - c = correct_rate_b[i, len(errs) - j - 1, level] - c_rate = f"{c:.0f}%" - text = ax.text(i, j, c_rate, ha="center", va="center", color="white" if c < 50 else "black") + c_rate = correct_rate_level[i, j] + text = ax.text(i, j, f"{c_rate:.0f}%", ha="center", va="center", color=_text_color(c_rate, 100, 0, 0.5)) ax.set_xlabel("$e_1$") ax.set_ylabel("$e_O$") ax.set_title(majs[level]) @@ -366,7 +402,36 @@ def success_rate_asymmetric(correct_rate_b, baseline): cbar_ax = fig.add_axes((0.9, 0.10, 0.02, 0.84)) cbar = fig.colorbar(im, cax=cbar_ax) cbar.ax.set_ylabel("Success rate", rotation=-90, va="bottom") - cbar.ax.axhline(baseline, color="red", linestyle="--") + if baseline: + cbar.ax.axhline(baseline, color="red", linestyle="--") + return fig + + +def amount_rate_asymmetric(amount_rate_b): + fig, axs = plt.subplots(nrows=2, ncols=3, sharex="col", sharey="row") + vmin = np.min(amount_rate_b) + vmax = np.max(amount_rate_b) + + for row in range(2): + for col in range(3): + ax = axs[row, col] + level = row * 3 + col + amount_rate_level = amount_rate_b.isel(majority=level) + im = ax.imshow(amount_rate_level.T, cmap=plasma, vmin=vmin, vmax=vmax, origin="lower") + ax.set_xticks(np.arange(len(errs)), labels=errs) + ax.set_yticks(np.arange(len(errs)), labels=errs) + for i in range(len(errs)): + for j in range(len(errs)): + a_rate = amount_rate_level[i, j] + text = ax.text(i, j, f"{a_rate:.0f}", ha="center", va="center", color=_text_color(a_rate, vmax, vmin, 0.5)) + ax.set_xlabel("$e_1$") + ax.set_ylabel("$e_O$") + ax.set_title(majs[level]) + fig.set_size_inches((10,6)) + fig.tight_layout(h_pad=1.5, rect=(0, 0, 0.9, 1)) + cbar_ax = fig.add_axes((0.9, 0.10, 0.02, 0.84)) + cbar = fig.colorbar(im, cax=cbar_ax) + cbar.ax.set_ylabel("Result size", rotation=-90, va="bottom") return fig @@ -376,14 +441,14 @@ def precise_rate_asymmetric(precise_rate_b): for col in range(3): ax = axs[row, col] level = row * 3 + col - im = ax.imshow(precise_rate_b[::-1,:,level], cmap="viridis", vmin=0, vmax=100) + precise_rate_level = precise_rate_b.isel(majority=level) + im = ax.imshow(precise_rate_level.T, cmap=viridis, vmin=0, vmax=100, origin="lower") ax.set_xticks(np.arange(len(errs)), labels=errs) - ax.set_yticks(np.arange(len(errs)), labels=list(reversed(errs))) + ax.set_yticks(np.arange(len(errs)), labels=errs) for i in range(len(errs)): for j in range(len(errs)): - p = precise_rate_b[i, len(errs) - j - 1, level] - p_rate = f"{p:.0f}%" - text = ax.text(i, j, p_rate, ha="center", va="center", color="white" if p < 80 else "black") + p_rate = precise_rate_level[i, j] + text = ax.text(i, j, f"{p_rate:.0f}%", ha="center", va="center", color=_text_color(p_rate, 100, 0, 0.5)) ax.set_xlabel("$e_1$") ax.set_ylabel("$e_O$") ax.set_title(majs[level]) @@ -399,9 +464,9 @@ def success_rate_vs_majority_asymmetric(correct_rate_b): fig, ax = plt.subplots() ax.grid() crs_accumulated = {} - for i, err_0 in enumerate(errs): - for j, err_1 in enumerate(errs): - crs = correct_rate_b[i, j, :] + for err_0 in errs: + for err_1 in errs: + crs = correct_rate_b.sel(err_0=err_0, err_1=err_1) total_err = round(err_0 + err_1, 1) l = crs_accumulated.setdefault(total_err, []) l.append(crs) @@ -418,56 +483,89 @@ def success_rate_vs_majority_asymmetric(correct_rate_b): def query_rate_binomial(query_rate): fig, ax = plt.subplots() - im = ax.imshow(query_rate.T, cmap="plasma") + im = ax.imshow(query_rate.T, cmap=mako, origin="lower") cbar_ax = fig.add_axes((0.85, 0.15, 0.04, 0.69)) cbar = fig.colorbar(im, cax=cbar_ax) cbar.ax.set_ylabel("Oracle query rate", rotation=-90, va="bottom") + + vmin = np.min(query_rate) + vmax = np.max(query_rate) ax.set_xticks(np.arange(len(nums)), labels=nums) - ax.set_yticks(np.arange(len(smpls)), labels=reversed(smpls)) + ax.set_yticks(np.arange(len(smpls)), labels=smpls) ax.set_xlabel("binom n") ax.set_ylabel("samples") for i in range(len(nums)): for j in range(len(smpls)): - text = ax.text(i, j, f"{query_rate[i, j]:.1f}", - ha="center", va="center", color="white" if i - j <= 2 else "black") + q_rate = query_rate[i, j] + text = ax.text(i, j, f"{q_rate:.1f}", + ha="center", va="center", color=_text_color(q_rate, vmax, vmin, 0.5)) return fig def success_rate_binomial(correct_rate, baseline): fig, ax = plt.subplots() - im = ax.imshow(correct_rate.T, vmin=0, cmap="viridis") + im = ax.imshow(correct_rate.T, vmin=0, cmap=viridis, origin="lower") cbar_ax = fig.add_axes((0.85, 0.15, 0.04, 0.69)) cbar = fig.colorbar(im, cax=cbar_ax) cbar.ax.set_ylabel("Success rate", rotation=-90, va="bottom") - cbar.ax.axhline(baseline, color="red", linestyle="--") + if baseline: + cbar.ax.axhline(baseline, color="red", linestyle="--") + + vmin = 0 + vmax = np.max(correct_rate) ax.set_xticks(np.arange(len(nums)), labels=nums) - ax.set_yticks(np.arange(len(smpls)), labels=reversed(smpls)) + ax.set_yticks(np.arange(len(smpls)), labels=smpls) ax.set_xlabel("binom n") ax.set_ylabel("samples") for i in range(len(nums)): for j in range(len(smpls)): c_rate = correct_rate[i, j] text = ax.text(i, j, f"{c_rate:.1f}%", - ha="center", va="center", color="white" if c_rate < 80 else "black") + ha="center", va="center", color=_text_color(c_rate, vmax, vmin, 0.8)) + return fig + + +def amount_rate_binomial(amount_rate): + fig, ax = plt.subplots() + im = ax.imshow(amount_rate.T, cmap=plasma, origin="lower") + cbar_ax = fig.add_axes((0.85, 0.15, 0.04, 0.69)) + cbar = fig.colorbar(im, cax=cbar_ax) + cbar.ax.set_ylabel("Result size", rotation=-90, va="bottom") + + vmin = np.min(amount_rate) + vmax = np.max(amount_rate) + + ax.set_xticks(np.arange(len(nums)), labels=nums) + ax.set_yticks(np.arange(len(smpls)), labels=smpls) + ax.set_xlabel("binom n") + ax.set_ylabel("samples") + for i in range(len(nums)): + for j in range(len(smpls)): + a_rate = amount_rate[i, j] + text = ax.text(i, j, f"{a_rate:.1f}", + ha="center", va="center", color=_text_color(a_rate, vmax, vmin, 0.5)) return fig def precise_rate_binomial(precise_rate): fig, ax = plt.subplots() - im = ax.imshow(precise_rate.T, vmin=0, cmap="viridis") + im = ax.imshow(precise_rate.T, vmin=0, cmap=viridis, origin="lower") cbar_ax = fig.add_axes((0.85, 0.15, 0.04, 0.69)) cbar = fig.colorbar(im, cax=cbar_ax) cbar.ax.set_ylabel("Precision", rotation=-90, va="bottom") + + vmin = 0 + vmax = np.max(precise_rate) ax.set_xticks(np.arange(len(nums)), labels=nums) - ax.set_yticks(np.arange(len(smpls)), labels=reversed(smpls)) + ax.set_yticks(np.arange(len(smpls)), labels=smpls) ax.set_xlabel("binom n") ax.set_ylabel("samples") for i in range(len(nums)): for j in range(len(smpls)): p_rate = precise_rate[i, j] text = ax.text(i, j, f"{p_rate:.1f}%", - ha="center", va="center", color="white" if p_rate < 80 else "black") + ha="center", va="center", color=_text_color(p_rate, vmax, vmin, 0.8)) return fig diff --git a/re/zvp.ipynb b/re/zvp.ipynb index e3728c9..881cdf9 100644 --- a/re/zvp.ipynb +++ b/re/zvp.ipynb @@ -17,6 +17,7 @@ " - [Computing ZVP points](#Computing-ZVP-points)\n", " - [Remapping](#Remapping)\n", " - [Distinguishing map and distinguishing tree building](#Distinguishing-map-and-distinguishing-tree-building)\n", + " - [Evaluation](#Evaluation)\n", " - [Miscellaneous analysis](#Miscellaneous-analysis)\n" ] }, @@ -30,6 +31,7 @@ "import io\n", "import numpy as np\n", "import pandas as pd\n", + "import holoviews as hv\n", "import random\n", "import tabulate\n", "import pickle\n", @@ -38,6 +40,7 @@ "import tempfile\n", "import sys\n", "import re\n", + "from matplotlib import pyplot as plt\n", "from sympy import FF, ZZ, sympify, symbols, Poly\n", "from contextlib import contextmanager\n", "from importlib import import_module, invalidate_caches\n", @@ -65,6 +68,14 @@ "from pyecsca.misc.cfg import getconfig\n", "from pyecsca.misc.utils import TaskExecutor\n", "\n", + "from eval import (eval_tree_symmetric1, eval_tree_asymmetric1, eval_tree_binomial1,\n", + " success_rate_symmetric, success_rate_asymmetric, success_rate_binomial,\n", + " query_rate_symmetric, query_rate_asymmetric, query_rate_binomial,\n", + " amount_rate_symmetric, amount_rate_asymmetric, amount_rate_binomial,\n", + " precise_rate_symmetric, precise_rate_asymmetric, precise_rate_binomial,\n", + " success_rate_vs_majority_symmetric, success_rate_vs_majority_asymmetric,\n", + " success_rate_vs_query_rate_symmetric)\n", + "\n", "\n", "# Allow to use \"spawn\" multiprocessing method for function defined in a Jupyter notebook.\n", "# https://neuromancer.sk/article/35\n", @@ -82,7 +93,10 @@ " yield getattr(module, func.__name__)\n", " sys.path.remove(directory)\n", "\n", - "spawn_context = multiprocessing.get_context(\"spawn\")" + "spawn_context = multiprocessing.get_context(\"spawn\")\n", + "\n", + "%matplotlib ipympl\n", + "hv.extension(\"bokeh\")" ] }, { @@ -307,7 +321,7 @@ "metadata": {}, "outputs": [], "source": [ - "load_expanded = False\n", + "load_expanded = True\n", "\n", "formula_classes = [AdditionFormula, DoublingFormula]\n", "formula_groups = {}\n", @@ -672,7 +686,37 @@ " remapped_hit_point_map[cfg] = hit_map\n", " remapped_count_point_map[cfg] = count_map\n", " remapped_position_point_map[cfg] = position_map\n", - " print(f\"Remapped {mapped} points for {coord_name}.\")" + " print(f\"{coord_name}: Remapped.\")" + ] + }, + { + "cell_type": "markdown", + "id": "07755fca-07cd-4384-8581-64e701659361", + "metadata": {}, + "source": [ + "You can now store the (or load the previously computed) remmapped maps." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "95c3693b-166c-4515-9153-e3e00d222835", + "metadata": {}, + "outputs": [], + "source": [ + "with open(\"remapped.pickle\", \"wb\") as f:\n", + " pickle.dump((remapped_hit_point_map, remapped_count_point_map, remapped_position_point_map), f)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "3914501e-269c-4a88-ba5b-ad3c6dd28cfb", + "metadata": {}, + "outputs": [], + "source": [ + "with open(\"remapped.pickle\", \"rb\") as f:\n", + " remapped_hit_point_map, remapped_count_point_map, remapped_position_point_map = pickle.load(f)" ] }, { @@ -687,11 +731,40 @@ { "cell_type": "code", "execution_count": null, + "id": "236d40a0-7a9c-48a0-b932-a0dfe1110a8c", + "metadata": {}, + "outputs": [], + "source": [ + "cfgs = set()\n", + "for coord_name, coords in model.coordinates.items():\n", + " cfgs.update(product(*formula_groups[coords]))\n", + "\n", + "param_categories = {\n", + " \"a=-1\": [\"projective-1\"],\n", + " \"a=-3\": [\"projective-3\", \"jacobian-3\", \"xyzz-3\"],\n", + " \"a=0\": [\"jacobian-0\"],\n", + " \"generic\": [\"jacobian\", \"projective\", \"modified\", \"xyzz\", \"xz\"],\n", + " \"b=0\": [\"w12-0\"]\n", + "}\n", + "cfg_categories = {}\n", + "for name, coord_names in param_categories.items():\n", + " category_cfgs = set()\n", + " for coord_name in coord_names:\n", + " coords = model.coordinates[coord_name]\n", + " category_cfgs.update(filter(lambda cfg: cfg[0].coordinate_model == coords and cfg[1].coordinate_model == coords, cfgs))\n", + " cfg_categories[name] = category_cfgs\n", + "category_map = {cfg: {\"category\": name} for name, category_cfgs in cfg_categories.items() for cfg in category_cfgs}\n", + "dmap_categories = Map.from_io_maps(cfgs, category_map)" + ] + }, + { + "cell_type": "code", + "execution_count": null, "id": "db1ffe84-f58e-465c-b417-ad1d563c8377", "metadata": {}, "outputs": [], "source": [ - "dmap_remapped = Map.from_io_maps(set(remapped_hit_point_map.keys()), remapped_hit_point_map) " + "dmap_remapped = Map.from_io_maps(cfgs, remapped_hit_point_map)" ] }, { @@ -702,9 +775,9 @@ "outputs": [], "source": [ "from copy import deepcopy\n", - "dmap_copy = deepcopy(dmap_remapped)\n", - "dmap_copy.deduplicate()\n", - "print(f\"Points before: {len(dmap_remapped.mapping)} points after deduplication: {len(dmap_copy.mapping)}.\")" + "dmap_dedup = deepcopy(dmap_remapped)\n", + "dmap_dedup.deduplicate()\n", + "print(f\"Rows before: {len(dmap_remapped.mapping)}, rows after deduplication: {len(dmap_dedup.mapping)}.\")" ] }, { @@ -724,7 +797,8 @@ }, "outputs": [], "source": [ - "tree_remapped = Tree.build(dmap_copy.cfgs, dmap_copy)" + "tree_categories = Tree.build(cfgs, dmap_categories)\n", + "tree_remapped = tree_categories.expand(dmap_dedup)" ] }, { @@ -751,6 +825,73 @@ ] }, { + "cell_type": "code", + "execution_count": null, + "id": "c3571008-1898-41e0-87d5-848707345d62", + "metadata": {}, + "outputs": [], + "source": [ + "print(tree_remapped.render_basic())" + ] + }, + { + "cell_type": "markdown", + "id": "eff08e04-20bc-4fc7-978d-9cbfc06179b6", + "metadata": {}, + "source": [ + "### Evaluation" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "3ef78642-fe65-46c7-8233-11dc43525991", + "metadata": {}, + "outputs": [], + "source": [ + "correct_rate, precise_rate, amount_rate, query_rate = eval_tree_symmetric1(cfgs, [tree_remapped], num_tries=100, num_cores=30)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "3bef547e-7c8e-4ec4-a842-75889cf6acd9", + "metadata": {}, + "outputs": [], + "source": [ + "success_rate_symmetric(correct_rate, None).savefig(\"zvp_re_success_rate_symmetric.pdf\", bbox_inches=\"tight\")\n", + "precise_rate_symmetric(precise_rate).savefig(\"zvp_re_precise_rate_symmetric.pdf\", bbox_inches=\"tight\")\n", + "query_rate_symmetric(query_rate).savefig(\"zvp_re_query_rate_symmetric.pdf\", bbox_inches=\"tight\")\n", + "amount_rate_symmetric(amount_rate).savefig(\"zvp_re_amount_rate_symmetric.pdf\", bbox_inches=\"tight\")\n", + "success_rate_vs_query_rate_symmetric(query_rate, correct_rate).savefig(\"zvp_re_scatter_symmetric.pdf\", bbox_inches=\"tight\")\n", + "success_rate_vs_majority_symmetric(correct_rate).savefig(\"zvp_re_plot_symmetric.pdf\", bbox_inches=\"tight\")" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "064e76e9-a299-4a5c-ae44-adfe07d86901", + "metadata": {}, + "outputs": [], + "source": [ + "correct_rate_b, precise_rate_b, amount_rate_b, query_rate_b = eval_tree_asymmetric1(cfgs, [tree_remapped], num_tries=100, num_cores=30)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "fa23ea1b-2b95-4f22-b237-bd4d75980681", + "metadata": {}, + "outputs": [], + "source": [ + "success_rate_asymmetric(correct_rate_b, None).savefig(\"zvp_re_success_rate_asymmetric.pdf\", bbox_inches=\"tight\")\n", + "precise_rate_asymmetric(precise_rate_b).savefig(\"zvp_re_precise_rate_asymmetric.pdf\", bbox_inches=\"tight\")\n", + "query_rate_asymmetric(query_rate_b).savefig(\"zvp_re_query_rate_asymmetric.pdf\", bbox_inches=\"tight\")\n", + "amount_rate_asymmetric(amount_rate_b).savefig(\"zvp_re_amount_rate_asymmetric.pdf\", bbox_inches=\"tight\")\n", + "success_rate_vs_majority_asymmetric(correct_rate_b).savefig(\"zvp_re_plot_asymmetric.pdf\", bbox_inches=\"tight\")" + ] + }, + { "cell_type": "markdown", "id": "27f4be08-76fd-437a-bde7-8579b38fc686", "metadata": {}, @@ -765,7 +906,18 @@ "metadata": {}, "outputs": [], "source": [ - "dmap_count = Map.from_io_maps(set(remapped_count_point_map.keys()), remapped_count_point_map)" + "dmap_count = Map.from_io_maps(cfgs, remapped_count_point_map)\n", + "dmap_count.deduplicate()" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "764b6dec-f1d5-4e8f-8585-b35d9261b1ca", + "metadata": {}, + "outputs": [], + "source": [ + "print(dmap_count.describe())" ] }, { @@ -777,7 +929,7 @@ }, "outputs": [], "source": [ - "tree_count = Tree.build(set(remapped_count_point_map.keys()), dmap_count)" + "tree_count = tree_categories.expand(dmap_count)" ] }, { @@ -787,17 +939,20 @@ "metadata": {}, "outputs": [], "source": [ - "dmap_position = Map.from_io_maps(set(remapped_position_point_map.keys()), remapped_position_point_map)" + "dmap_position = Map.from_io_maps(cfgs, remapped_position_point_map)\n", + "dmap_position.deduplicate()" ] }, { "cell_type": "code", "execution_count": null, "id": "db92360c-cb96-4382-8255-d7773772b07d", - "metadata": {}, + "metadata": { + "scrolled": true + }, "outputs": [], "source": [ - "tree_position = Tree.build(set(remapped_position_point_map.keys()), dmap_position)" + "tree_position = tree_categories.expand(dmap_position)" ] }, { @@ -816,6 +971,29 @@ ] }, { + "cell_type": "code", + "execution_count": null, + "id": "d0566c3d-fb55-496b-aeb3-17b674d32ca2", + "metadata": {}, + "outputs": [], + "source": [ + "correct_rate_c, precise_rate_c, amount_rate_c, query_rate_c = eval_tree_binomial1(cfgs, [tree_count], num_tries=100, num_cores=30)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "1eedce32-a74a-4baf-a5ab-a08cd8b96a6e", + "metadata": {}, + "outputs": [], + "source": [ + "success_rate_binomial(correct_rate_c, None).savefig(\"zvp_re_success_rate_binomial.pdf\", bbox_inches=\"tight\")\n", + "precise_rate_binomial(precise_rate_c).savefig(\"zvp_re_precise_rate_binomial.pdf\", bbox_inches=\"tight\")\n", + "query_rate_binomial(query_rate_c).savefig(\"zvp_re_query_rate_binomial.pdf\", bbox_inches=\"tight\")\n", + "amount_rate_binomial(amount_rate_c).savefig(\"zvp_re_amount_rate_binomial.pdf\", bbox_inches=\"tight\")" + ] + }, + { "cell_type": "markdown", "id": "e50daa23-25b8-4970-a69b-e31d8b000204", "metadata": {}, @@ -866,8 +1044,8 @@ "metadata": {}, "outputs": [], "source": [ - "dmap_fset = Map.from_sets(set(fset_map.keys()), fset_map)\n", - "dmap_fset_nonhomo = Map.from_sets(set(fset_nonhomo_map.keys()), fset_nonhomo_map)" + "dmap_fset = Map.from_sets(cfgs, fset_map)\n", + "dmap_fset_nonhomo = Map.from_sets(cfgs, fset_nonhomo_map)" ] }, { @@ -877,8 +1055,8 @@ "metadata": {}, "outputs": [], "source": [ - "tree_fset = Tree.build(set(fset_map.keys()), dmap_fset)\n", - "tree_fset_nonhomo = Tree.build(set(fset_nonhomo_map.keys()), dmap_fset_nonhomo)" + "tree_fset = Tree.build(cfgs, dmap_fset)\n", + "tree_fset_nonhomo = Tree.build(cfgs, dmap_fset_nonhomo)" ] }, { @@ -1064,7 +1242,53 @@ { "cell_type": "code", "execution_count": null, - "id": "cbabc614-f571-4c92-a3f3-f201388a5606", + "id": "a1302155-930c-4131-a66e-bb035c90a54d", + "metadata": {}, + "outputs": [], + "source": [ + "s = sum(dmap_remapped.mapping[dmap_remapped.mapping == True].count(axis=0))\n", + "print(s/len(dmap_remapped.mapping.columns))" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "f12ab1ab-8e1e-419d-a765-e601bf82ae93", + "metadata": {}, + "outputs": [], + "source": [ + "dcnp = dmap_count.mapping.to_numpy()\n", + "\n", + "flat = dcnp[dcnp > 0]\n", + "flat" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "e72bf8bd-336f-4dc6-925f-b3d959824ae1", + "metadata": {}, + "outputs": [], + "source": [ + "counts, bins = np.histogram(flat, bins=np.arange(256), density=True)\n", + "print(counts, bins)\n", + "print(len(counts))\n", + "plt.stairs(counts, bins)\n", + "plt.show()" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "391b2ce7-5785-4492-8fa5-7b10dbcd8d09", + "metadata": {}, + "outputs": [], + "source": [] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "59333254-f01c-49fb-9bf2-6ca8403a516a", "metadata": {}, "outputs": [], "source": [] diff --git a/requirements.txt b/requirements.txt index 9ccbfdd..ec3f51b 100644 --- a/requirements.txt +++ b/requirements.txt @@ -1,4 +1,5 @@ pyecsca pyecsca-codegen jupyter -tabulate
\ No newline at end of file +tabulate +seaborn |
