8 files changed, 95 insertions, 11 deletions

diff --git a/.gitignore b/.gitignore
index 2896e11..b57dd7d 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,5 +1,6 @@
 /*.trs
 
+pyecsca.egg-info
 .coverage
 .mypy_cache/
 /.pytest_cache/
diff --git a/Pipfile b/Pipfile
index 1cc3913..c545fd7 100644
--- a/Pipfile
+++ b/Pipfile
@@ -22,4 +22,4 @@ parameterized = "*"
 asn1crypto = "*"
 
 [requires]
-python_version = "3.7"
+python_version = "3.8"
diff --git a/pyecsca/ec/context.py b/pyecsca/ec/context.py
index 02f724c..9ec22f5 100644
--- a/pyecsca/ec/context.py
+++ b/pyecsca/ec/context.py
@@ -1,4 +1,5 @@
 import ast
+from abc import ABCMeta, abstractmethod
 from contextvars import ContextVar, Token
 from copy import deepcopy
 from typing import List, Tuple, Optional, Union, MutableMapping, Any, ContextManager
@@ -91,14 +92,19 @@ class FormulaAction(Action):
 
 @public
 class Context(object):
+    __metaclass__ = ABCMeta
+
+    @abstractmethod
     def _log_formula(self, formula: Formula, *points: Point, **inputs: Mod):
-        raise NotImplementedError
+        ...
 
+    @abstractmethod
     def _log_operation(self, op: CodeOp, value: Mod):
-        raise NotImplementedError
+        ...
 
+    @abstractmethod
     def _log_result(self, point: Point, **outputs: Mod):
-        raise NotImplementedError
+        ...
 
     def _execute(self, formula: Formula, *points: Point, **params: Mod) -> Tuple[Point, ...]:
         if len(points) != formula.num_inputs:
diff --git a/pyecsca/sca/__init__.py b/pyecsca/sca/__init__.py
index 159d402..6a6b163 100644
--- a/pyecsca/sca/__init__.py
+++ b/pyecsca/sca/__init__.py
@@ -2,6 +2,7 @@ from .align import *
 from .combine import *
 from .edit import *
 from .filter import *
+from .match import *
 from .process import *
 from .sampling import *
 from .test import *
diff --git a/pyecsca/sca/match.py b/pyecsca/sca/match.py
new file mode 100644
index 0000000..ba69026
--- /dev/null
+++ b/pyecsca/sca/match.py
@@ -0,0 +1,37 @@
+"""
+This module provides functions for matching a pattern within a trace to it.
+"""
+import numpy as np
+from scipy.signal import find_peaks
+from public import public
+from typing import List
+
+from .process import normalize
+from .edit import trim
+from .trace import Trace
+
+
+@public
+def match_pattern(trace: Trace, pattern: Trace, threshold: float = 0.8) -> List[int]:
+    normalized = normalize(trace)
+    pattern_samples = normalize(pattern).samples
+    correlation = np.correlate(normalized.samples, pattern_samples, "same")
+    correlation = (correlation - np.mean(correlation)) / (np.max(correlation))
+    peaks, props = find_peaks(correlation, prominence=(threshold, None))
+    pairs = sorted(zip(peaks, props["prominences"]), key=lambda it: it[1], reverse=True)
+    half = len(pattern_samples) // 2
+    filtered_peaks: List[int] = []
+    for peak, prominence in pairs:
+        if not filtered_peaks:
+            filtered_peaks.append(peak - half)
+        else:
+            for other_peak in filtered_peaks:
+                if abs((peak - half) - other_peak) <= len(pattern_samples):
+                    break
+            else:
+                filtered_peaks.append(peak - half)
+    return filtered_peaks
+
+@public
+def match_part(trace: Trace, offset: int, length: int) -> List[int]:
+    return match_pattern(trace, trim(trace, offset, offset + length))
diff --git a/pyecsca/sca/trace_set/chipwhisperer.py b/pyecsca/sca/trace_set/chipwhisperer.py
index 21369d2..d9dcf3f 100644
--- a/pyecsca/sca/trace_set/chipwhisperer.py
+++ b/pyecsca/sca/trace_set/chipwhisperer.py
@@ -27,7 +27,7 @@ class ChipWhispererTraceSet(TraceSet):
         for type in types.keys():
             type_path = join(path, name + "_" + type + ".npy")
             if exists(type_path) and isfile(type_path):
-                types[type] = np.load(type_path)
+                types[type] = np.load(type_path, allow_pickle=True)
         return types
 
     def __read_config(self, path, name):
diff --git a/test/sca/test_match.py b/test/sca/test_match.py
new file mode 100644
index 0000000..9cbd284
--- /dev/null
+++ b/test/sca/test_match.py
@@ -0,0 +1,29 @@
+from unittest import TestCase
+
+import numpy as np
+
+from pyecsca.sca import Trace, match_pattern, match_part, pad
+from .utils import plot
+
+
+class MatchingTests(TestCase):
+
+    def test_simple_match(self):
+        pattern = Trace(None, None,
+                        np.array([1, 15, 12, -10, 0, 13, 17, -1, 0], dtype=np.dtype("i1")))
+        base = Trace(None, None, np.array(
+                [0, 1, 3, 1, 2, -2, -3, 1, 15, 12, -10, 0, 13, 17, -1, 0, 3, 1],
+                dtype=np.dtype("i1")))
+        filtered = match_part(base, 7, 9)
+        self.assertListEqual(filtered, [7])
+        plot(self, base=base, pattern=pad(pattern, (filtered[0], 0)))
+
+    def test_multiple_match(self):
+        pattern = Trace(None, None,
+                        np.array([1, 15, 12, -10, 0, 13, 17, -1, 0], dtype=np.dtype("i1")))
+        base = Trace(None, None, np.array(
+                [0, 1, 3, 1, 2, -2, -3, 1, 18, 10, -5, 0, 13, 17, -1, 0, 3, 1, 2, 5, 13, 8, -8, 1, 11, 15, 0, 1, 5, 2, 4],
+                dtype=np.dtype("i1")))
+        filtered = match_pattern(base, pattern, 0.9)
+        self.assertListEqual(filtered, [7, 19])
+        plot(self, base=base, pattern1=pad(pattern, (filtered[0], 0)), pattern2=pad(pattern, (filtered[1], 0)))
diff --git a/test/sca/utils.py b/test/sca/utils.py
index 1083b87..643ab68 100644
--- a/test/sca/utils.py
+++ b/test/sca/utils.py
@@ -1,24 +1,34 @@
 import matplotlib.pyplot as plt
 from unittest import TestCase
 from pyecsca.sca import Trace
-from os.path import join, exists
-from os import mkdir, getenv
+from os.path import join, exists, split
+from os import mkdir, getenv, getcwd
 
 
+force_plot = True
+
 def slow(func):
     func.slow = 1
     return func
 
+cases = {}
 
-def plot(case: TestCase, *traces: Trace):
-    if getenv("PYECSCA_TEST_PLOTS") is None:
+def plot(case: TestCase, *traces: Trace, **kwtraces: Trace):
+    if not force_plot and getenv("PYECSCA_TEST_PLOTS") is None:
         return
     fig = plt.figure()
     ax = fig.add_subplot(111)
     for i, trace in enumerate(traces):
         ax.plot(trace.samples, label=str(i))
+    for name, trace in kwtraces.items():
+        ax.plot(trace.samples, label=name)
     ax.legend(loc="best")
-    directory = join("test", "plots")
+    if split(getcwd())[1] == "test":
+        directory = "plots"
+    else:
+        directory = join("test", "plots")
     if not exists(directory):
         mkdir(directory)
-    plt.savefig(join(directory, case.id() + ".png"))
+    case_id = cases.setdefault(case.id(), 0) + 1
+    cases[case.id()] = case_id
+    plt.savefig(join(directory, case.id() + str(case_id) + ".png"))