From f94d63b3b84fde4a2a9004ba0afc6693f5ba4916 Mon Sep 17 00:00:00 2001 From: J08nY Date: Sat, 30 Jan 2021 18:30:55 +0100 Subject: Add performance monitoring and a few improvements to Mod. --- .github/workflows/perf.yml | 63 +++++++++++++++++++++++++++++++++++++++++++++ .gitignore | 1 + Makefile | 8 +++++- README.md | 4 ++- docs/index.rst | 6 ++++- pyecsca/ec/mod.py | 28 ++++++++++++-------- setup.py | 2 +- test/ec/perf_formula.py | 43 +++++++++++++++++++++++++++++++ test/ec/perf_mod.py | 64 ++++++++++++++++++++++++++++++++++++++++++++++ test/ec/perf_mult.py | 41 +++++++++++++++++++++++++++++ test/ec/utils.py | 58 +++++++++++++++++++++++++++++++++++++++++ 11 files changed, 303 insertions(+), 15 deletions(-) create mode 100644 .github/workflows/perf.yml create mode 100755 test/ec/perf_formula.py create mode 100755 test/ec/perf_mod.py create mode 100755 test/ec/perf_mult.py diff --git a/.github/workflows/perf.yml b/.github/workflows/perf.yml new file mode 100644 index 0000000..b4a2693 --- /dev/null +++ b/.github/workflows/perf.yml @@ -0,0 +1,63 @@ +name: Perf + +on: [push, pull_request] + +env: + LLVM_CONFIG: /usr/bin/llvm-config-10 + PS_PACKAGES: libps4000 libps5000 libps6000 + GMP_PACKAGES: libgmp-dev libmpfr-dev libmpc-dev + OTHER_PACKAGES: swig gcc libpcsclite-dev llvm-10 libllvm10 llvm-10-dev + +jobs: + perf: + runs-on: ubuntu-20.04 + strategy: + matrix: + python-version: [3.8, 3.9] + gmp: [0, 1] + env: + PYTHON: ${{ matrix.python-version }} + USE_GMP: ${{ matrix.gmp }} + steps: + - uses: actions/checkout@v2 + with: + submodules: true + - uses: actions/cache@v2 + with: + path: ~/.cache/pip + key: pip-${{ runner.os }}-${{ matrix.gmp }}-${{ matrix.python-version }}-${{ hashFiles('setup.py') }} + restore-keys: | + pip-${{ runner.os }}-${{ matrix.gmp }}-${{ matrix.python-version }}- + pip-${{ runner.os }}-${{ matrix.gmp }}- + pip-${{ runner.os }}- + - name: Setup Python ${{ matrix.python-version }} + uses: actions/setup-python@v2 + with: + python-version: ${{ matrix.python-version }} + - name: Add picoscope repository + run: | + curl "https://labs.picotech.com/debian/dists/picoscope/Release.gpg.key" | sudo apt-key add + sudo echo "deb https://labs.picotech.com/debian/ picoscope main" | sudo tee /etc/apt/sources.list.d/picoscope.list + sudo apt-get update + - name: Install system dependencies + run: | + sudo apt-get install -y $PS_PACKAGES $OTHER_PACKAGES + if [ $USE_GMP == 1 ]; then sudo apt-get install -y $GMP_PACKAGES; fi + - name: Install picoscope bindings + run: | + git clone https://github.com/colinoflynn/pico-python && cd pico-python && python setup.py install && cd .. + git clone https://github.com/picotech/picosdk-python-wrappers && cd picosdk-python-wrappers && python setup.py install && cd .. + - name: Install dependencies + run: | + python -m pip install -U pip setuptools wheel + if [ $USE_GMP == 1 ]; then pip install -e ".[picoscope_sdk, picoscope_alt, chipwhisperer, smartcard, gmp, test, dev]"; fi + if [ $USE_GMP == 0 ]; then pip install -e ".[picoscope_sdk, picoscope_alt, chipwhisperer, smartcard, test, dev]"; fi + - name: Perf + run: | + make perf + - name: Archive perf results + uses: actions/upload-artifact@v2 + with: + name: perf-results + path: + .perf \ No newline at end of file diff --git a/.gitignore b/.gitignore index 65292a0..7aefd0d 100644 --- a/.gitignore +++ b/.gitignore @@ -1,6 +1,7 @@ /*.trs pyecsca.egg-info +.perf/ .coverage .mypy_cache/ /.pytest_cache/ diff --git a/Makefile b/Makefile index c22cf87..9acd9c6 100644 --- a/Makefile +++ b/Makefile @@ -7,6 +7,8 @@ sca.test_sampling sca.test_target sca.test_test sca.test_trace sca.test_traceset TESTS = ${EC_TESTS} ${SCA_TESTS} +PERF_SCRIPTS = test/ec/perf_mod.py test/ec/perf_formula.py test/ec/perf_mult.py + test: nose2 -s test -E "not slow and not disabled" -C -v ${TESTS} @@ -28,6 +30,10 @@ codestyle: codestyle-all: flake8 --ignore=E501,F405,F403,F401,E126 pyecsca test +perf: ${PERF_SCRIPTS} + mkdir -p .perf + echo $^ | env DIR=".perf" xargs -n 1 python + doc-coverage: interrogate -vv -nmps -e pyecsca/ec/std/.github/ -f 55 pyecsca @@ -35,4 +41,4 @@ docs: $(MAKE) -C docs apidoc $(MAKE) -C docs html -.PHONY: test test-plots test-all typecheck typecheck-all codestyle codestyle-all doc-coverage docs \ No newline at end of file +.PHONY: test test-plots test-all typecheck typecheck-all codestyle codestyle-all perf doc-coverage docs diff --git a/README.md b/README.md index 429e28d..f8cd057 100644 --- a/README.md +++ b/README.md @@ -66,6 +66,8 @@ It also supports working with [Riscure](https://www.riscure.com) Inspector trace - [parameterized](https://github.com/wolever/parameterized) - [flake8](https://flake8.pycqa.org/) - [coverage](https://coverage.readthedocs.io/) + - [interrogate](https://interrogate.readthedocs.io/) + - [pyinstrument](https://github.com/joerick/pyinstrument/) ### Docs @@ -78,7 +80,7 @@ It also supports working with [Riscure](https://www.riscure.com) Inspector trace MIT License - Copyright (c) 2018-2020 Jan Jancar + Copyright (c) 2018-2021 Jan Jancar Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal diff --git a/docs/index.rst b/docs/index.rst index 76c201d..4ec985c 100644 --- a/docs/index.rst +++ b/docs/index.rst @@ -105,6 +105,8 @@ Testing - mypy_ - flake8_ - coverage_ + - interrogate_ + - pyinstrument_ Docs ---- @@ -118,7 +120,7 @@ License MIT License - Copyright (c) 2018-2020 Jan Jancar + Copyright (c) 2018-2021 Jan Jancar Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal @@ -165,6 +167,8 @@ this support is very appreciated. .. _mypy: http://mypy-lang.org/ .. _flake8: https://flake8.pycqa.org/ .. _coverage: https://coverage.readthedocs.io/ +.. _interrogate: https://interrogate.readthedocs.io/ +.. _pyinstrument: https://github.com/joerick/pyinstrument/ .. _sphinx: https://www.sphinx-doc.org/ .. _sphinx-autodoc-typehints: https://pypi.org/project/sphinx-autodoc-typehints/ .. _nbsphinx: https://nbsphinx.readthedocs.io/ diff --git a/pyecsca/ec/mod.py b/pyecsca/ec/mod.py index cfe0748..cb9ef7e 100644 --- a/pyecsca/ec/mod.py +++ b/pyecsca/ec/mod.py @@ -8,7 +8,7 @@ dispatches to the implementation chosen by the runtime configuration of the libr import random import secrets from functools import wraps, lru_cache -from typing import Type, Dict +from typing import Type, Dict, Any from public import public from sympy import Expr, FF @@ -119,6 +119,8 @@ _mod_classes: Dict[str, Type] = {} @public class Mod(object): """An element x of ℤₙ.""" + x: Any + n: Any def __new__(cls, *args, **kwargs): if cls != Mod: @@ -131,10 +133,6 @@ class Mod(object): selected_class = next(iter(_mod_classes.keys())) return _mod_classes[selected_class].__new__(_mod_classes[selected_class], *args, **kwargs) - def __init__(self, x, n): - self.x = x - self.n = n - @_check def __add__(self, other): return self.__class__((self.x + other.x) % self.n, self.n) @@ -241,7 +239,8 @@ class RawMod(Mod): return object.__new__(cls) def __init__(self, x: int, n: int): - super().__init__(x % n, n) + self.x = x % n + self.n = n def inverse(self): if self.x == 0: @@ -344,7 +343,8 @@ class Undefined(Mod): return object.__new__(cls) def __init__(self): - super().__init__(None, None) + self.x = None + self.n = None def __add__(self, other): raise NotImplementedError @@ -447,7 +447,8 @@ class SymbolicMod(Mod): return object.__new__(cls) def __init__(self, x: Expr, n: int): - super().__init__(x, n) + self.x = x + self.n = n @_symbolic_check def __add__(self, other): @@ -539,6 +540,10 @@ class SymbolicMod(Mod): if has_gmp: + @lru_cache + def _is_prime(x) -> bool: + return gmpy2.is_prime(x) + @public class GMPMod(Mod): """An element x of ℤₙ. Implemented by GMP.""" @@ -549,7 +554,8 @@ if has_gmp: return object.__new__(cls) def __init__(self, x: int, n: int): - super().__init__(gmpy2.mpz(x % n), gmpy2.mpz(n)) + self.x = gmpy2.mpz(x % n) + self.n = gmpy2.mpz(n) def inverse(self): if self.x == 0: @@ -565,7 +571,7 @@ if has_gmp: def is_residue(self): """Whether this element is a quadratic residue (only implemented for prime modulus).""" - if not gmpy2.is_prime(self.n): + if not _is_prime(self.n): raise NotImplementedError if self.x == 0: return True @@ -579,7 +585,7 @@ if has_gmp: Uses the `Tonelli-Shanks `_ algorithm. """ - if not gmpy2.is_prime(self.n): + if not _is_prime(self.n): raise NotImplementedError if self.x == 0: return GMPMod(0, self.n) diff --git a/setup.py b/setup.py index fa90ccd..0ece313 100644 --- a/setup.py +++ b/setup.py @@ -48,7 +48,7 @@ setup( "chipwhisperer": ["chipwhisperer"], "smartcard": ["pyscard"], "gmp": ["gmpy2"], - "dev": ["mypy", "flake8", "interrogate"], + "dev": ["mypy", "flake8", "interrogate", "pyinstrument"], "test": ["nose2", "parameterized", "coverage"], "doc": ["sphinx", "sphinx-autodoc-typehints", "nbsphinx"] } diff --git a/test/ec/perf_formula.py b/test/ec/perf_formula.py new file mode 100755 index 0000000..9e651ae --- /dev/null +++ b/test/ec/perf_formula.py @@ -0,0 +1,43 @@ +#!/usr/bin/env python +import click + +from pyecsca.ec.mod import has_gmp +from pyecsca.ec.params import get_params +from pyecsca.misc.cfg import TemporaryConfig +from utils import Profiler + + +@click.command() +@click.option("-p", "--profiler", type=click.Choice(("py", "c")), default="py") +@click.option("-m", "--mod", type=click.Choice(("python", "gmp")), default="gmp" if has_gmp else "python") +@click.option("-o", "--operations", type=click.INT, default=5000) +@click.option("-d", "--directory", type=click.Path(file_okay=False, dir_okay=True), default=None, envvar="DIR") +def main(profiler, mod, operations, directory): + with TemporaryConfig() as cfg: + cfg.ec.mod_implementation = mod + p256 = get_params("secg", "secp256r1", "projective") + coords = p256.curve.coordinate_model + add = coords.formulas["add-2016-rcb"] + dbl = coords.formulas["dbl-2016-rcb"] + click.echo(f"Profiling {operations} {p256.curve.prime.bit_length()}-bit doubling formula executions...") + one_point = p256.generator + with Profiler(profiler, directory, f"formula_dbl2016rcb_p256_{operations}_{mod}"): + for _ in range(operations): + one_point = dbl(p256.curve.prime, one_point, **p256.curve.parameters)[0] + click.echo(f"Profiling {operations} {p256.curve.prime.bit_length()}-bit addition formula executions...") + other_point = p256.generator + with Profiler(profiler, directory, f"formula_add2016rcb_p256_{operations}_{mod}"): + for _ in range(operations): + one_point = add(p256.curve.prime, one_point, other_point, **p256.curve.parameters)[0] + ed25519 = get_params("other", "Ed25519", "extended") + ecoords = ed25519.curve.coordinate_model + dblg = ecoords.formulas["mdbl-2008-hwcd"] + click.echo(f"Profiling {operations} {ed25519.curve.prime.bit_length()}-bit doubling formula executions (with assumption)...") + eone_point = ed25519.generator + with Profiler(profiler, directory, f"formula_mdbl2008hwcd_ed25519_{operations}_{mod}"): + for _ in range(operations): + dblg(ed25519.curve.prime, eone_point, **ed25519.curve.parameters) + + +if __name__ == "__main__": + main() diff --git a/test/ec/perf_mod.py b/test/ec/perf_mod.py new file mode 100755 index 0000000..37cf41b --- /dev/null +++ b/test/ec/perf_mod.py @@ -0,0 +1,64 @@ +#!/usr/bin/env python +import click + +from pyecsca.ec.mod import Mod, has_gmp +from pyecsca.misc.cfg import TemporaryConfig +from utils import Profiler + + +@click.command() +@click.option("-p", "--profiler", type=click.Choice(("py", "c")), default="py") +@click.option("-m", "--mod", type=click.Choice(("python", "gmp")), default="gmp" if has_gmp else "python") +@click.option("-o", "--operations", type=click.INT, default=100000) +@click.option("-d", "--directory", type=click.Path(file_okay=False, dir_okay=True), default=None, envvar="DIR") +def main(profiler, mod, operations, directory): + with TemporaryConfig() as cfg: + cfg.ec.mod_implementation = mod + n = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff + a = Mod(0x11111111111111111111111111111111, n) + b = Mod(0xbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb, n) + click.echo(f"Profiling {operations} {n.bit_length()}-bit modular inverse...") + with Profiler(profiler, directory, f"mod_256b_inverse_{operations}_{mod}"): + for _ in range(operations): + a.inverse() + click.echo(f"Profiling {operations} {n.bit_length()}-bit modular square root...") + with Profiler(profiler, directory, f"mod_256b_sqrt_{operations}_{mod}"): + for _ in range(operations): + a.sqrt() + click.echo(f"Profiling {operations} {n.bit_length()}-bit modular multiply...") + c = a + with Profiler(profiler, directory, f"mod_256b_multiply_{operations}_{mod}"): + for _ in range(operations): + c = c * b + click.echo(f"Profiling {operations} {n.bit_length()}-bit constant modular multiply...") + c = a + with Profiler(profiler, directory, f"mod_256b_constmultiply_{operations}_{mod}"): + for _ in range(operations): + c = c * 48006 + click.echo(f"Profiling {operations} {n.bit_length()}-bit modular square...") + c = a + with Profiler(profiler, directory, f"mod_256b_square_{operations}_{mod}"): + for _ in range(operations): + c = c**2 + click.echo(f"Profiling {operations} {n.bit_length()}-bit modular add...") + c = a + with Profiler(profiler, directory, f"mod_256b_add_{operations}_{mod}"): + for _ in range(operations): + c = c + b + click.echo(f"Profiling {operations} {n.bit_length()}-bit modular subtract...") + c = a + with Profiler(profiler, directory, f"mod_256b_subtract_{operations}_{mod}"): + for _ in range(operations): + c = c - b + click.echo(f"Profiling {operations} {n.bit_length()}-bit modular quadratic residue checks...") + with Profiler(profiler, directory, f"mod_256b_isresidue_{operations}_{mod}"): + for _ in range(operations): + a.is_residue() + click.echo(f"Profiling {operations} {n.bit_length()}-bit modular random...") + with Profiler(profiler, directory, f"mod_256b_random_{operations}_{mod}"): + for _ in range(operations): + Mod.random(n) + + +if __name__ == "__main__": + main() diff --git a/test/ec/perf_mult.py b/test/ec/perf_mult.py new file mode 100755 index 0000000..2ec82b0 --- /dev/null +++ b/test/ec/perf_mult.py @@ -0,0 +1,41 @@ +#!/usr/bin/env python +import click + +from pyecsca.ec.mod import has_gmp +from pyecsca.ec.mult import LTRMultiplier +from pyecsca.ec.params import get_params +from pyecsca.misc.cfg import TemporaryConfig +from utils import Profiler + + +@click.command() +@click.option("-p", "--profiler", type=click.Choice(("py", "c")), default="py") +@click.option("-m", "--mod", type=click.Choice(("python", "gmp")), default="gmp" if has_gmp else "python") +@click.option("-o", "--operations", type=click.INT, default=50) +@click.option("-d", "--directory", type=click.Path(file_okay=False, dir_okay=True), default=None, envvar="DIR") +def main(profiler, mod, operations, directory): + with TemporaryConfig() as cfg: + cfg.ec.mod_implementation = mod + p256 = get_params("secg", "secp256r1", "projective") + coords = p256.curve.coordinate_model + add = coords.formulas["add-2016-rcb"] + dbl = coords.formulas["dbl-2016-rcb"] + mult = LTRMultiplier(add, dbl) + click.echo(f"Profiling {operations} {p256.curve.prime.bit_length()}-bit scalar multiplication executions...") + one_point = p256.generator + with Profiler(profiler, directory, f"mult_ltr_rcb_p256_{operations}_{mod}"): + for _ in range(operations): + mult.init(p256, one_point) + one_point = mult.multiply(0x71a55e0c1abb3a0e069419e0f837bc195f1b9545e69fc51e53c4d48d7fea3b1a) + # ed25519 = get_params("other", "Ed25519", "extended") + # ecoords = ed25519.curve.coordinate_model + # dblg = ecoords.formulas["mdbl-2008-hwcd"] + # click.echo(f"Profiling {operations} {ed25519.curve.prime.bit_length()}-bit doubling formula executions (with assumption)...") + # eone_point = ed25519.generator + # with Profiler(profiler) as pr: + # for _ in range(operations): + # dblg(ed25519.curve.prime, eone_point, **ed25519.curve.parameters) + + +if __name__ == "__main__": + main() diff --git a/test/ec/utils.py b/test/ec/utils.py index 67a9cc0..6429ac9 100644 --- a/test/ec/utils.py +++ b/test/ec/utils.py @@ -1,5 +1,12 @@ +import pstats +import sys + +from pathlib import Path +from subprocess import run, PIPE, DEVNULL from itertools import product from functools import reduce +from pyinstrument import Profiler as PyProfiler +from cProfile import Profile as cProfiler def slow(func): @@ -10,3 +17,54 @@ def slow(func): def cartesian(*items): for cart in product(*items): yield reduce(lambda x, y: x + y, cart) + + +class Profiler(object): + def __init__(self, prof_type, output_directory, benchmark_name): + self._prof = PyProfiler() if prof_type == "py" else cProfiler() + self._prof_type = prof_type + self._root_frame = None + self._state = None + self._output_directory = output_directory + self._benchmark_name = benchmark_name + + def __enter__(self): + self._prof.__enter__() + self._state = "in" + return self + + def __exit__(self, exc_type, exc_val, exc_tb): + self._prof.__exit__(exc_type, exc_val, exc_tb) + if self._prof_type == "py": + self._root_frame = self._prof.last_session.root_frame() + self._state = "out" + self.output() + self.save() + + def save(self): + if self._state != "out": + raise ValueError + if self._output_directory is None or self._benchmark_name is None: + return + git_commit = run(["git", "rev-parse", "--short", "HEAD"], stdout=PIPE, stderr=DEVNULL).stdout.strip().decode() + git_dirty = run(["git", "diff", "--quiet"], stdout=DEVNULL, stderr=DEVNULL).returncode != 0 + version = git_commit + ("-dirty" if git_dirty else "") + output_path = Path(self._output_directory) / (self._benchmark_name + ".csv") + with output_path.open("a") as f: + f.write(f"{version},{'.'.join(map(str, sys.version_info[:3]))},{self.get_time()}\n") + + def output(self): + if self._state != "out": + raise ValueError + if self._prof_type == "py": + print(self._prof.output_text(unicode=True, color=True)) + else: + self._prof.print_stats("cumtime") + + def get_time(self): + if self._state != "out": + raise ValueError + if self._prof_type == "py": + return self._root_frame.time() + else: + return pstats.Stats(self._prof).total_tt -- cgit v1.2.3-70-g09d2