Fourier-Based Metrics (PUFMeter)

An advanced method to study Boolean functions is harmonic analysis, also known as Fourier analysis [ODon14]. It can give information about the properties, including learnability, of a given Boolean function. pypuf formalizes (noise-free) PUFs as Boolean functions and can compute some of the metrics used in PUFMeter [GFS19].

pypuf.metrics.influence(puf: Simulation, i: int, seed: int, N: int = 1000) → float

Approximates the influence of the \(i\)-th input bit on the output of the given PUF simulation.

For a Boolean function \(f:\{-1,1\}^n\to\{-1,1\}\), the influence of the \(i\)-th input coordinate is defined as the probability that the output of the function changes when the \(i\)-th input coordinate is changed, i.e.

\[\mathrm{Inf}_i(f) = \Pr_x \left[ f(x) \neq f(x^{\oplus i}) \right],\]

where \(x^{\oplus i}\) is the same as \(x\), but with the \(i\)-th input coordinate flipped.

The value of \(\mathrm{Inf}_i(f)\) is approximated on a sample of uniform random inputs to \(f\).

Ideally, all input bits have an influence of approximately 50% on the response of a PUF function. In contrast, the Arbiter PUF is known to have input bits with extremely high and low influences:

>>> import pypuf.simulation, pypuf.metrics
>>> puf = pypuf.simulation.ArbiterPUF(n=128, seed=1)
>>> pypuf.metrics.influence(puf, i=0, seed=2)
0.03
>>> pypuf.metrics.influence(puf, i=127, seed=3)
0.971

The Lightweight Secure PUF [MKP08] removed this flaw of the Arbiter PUF, but did not succeed in created a more secure PUF [WBMS19].

>>> pypuf.metrics.influence(pypuf.simulation.LightweightSecurePUF(n=128, k=1, seed=1), i=0, seed=2)
0.447
Parameters:

  • puf (pypuf.simulation.Simulation) – Function \(f\).

  • i (int) – The (zero-based) index of the coordinate whose influence will be approximated.

  • seed (int) – Determines the seed for the PRNG that generates the uniform random inputs to \(f\).

  • N (int) – The number of uniform random inputs that is used to approximate the influence.

Returns:

An approximation of the influence of the \(i\)-th input coordinate on the output of \(f\), i.e. \(\mathrm{Inf}_i(f)\).

Return type:

float

pypuf.metrics.noise_sensitivity(puf: Simulation, eps: float, seed: int, N: int = 1000) → float

The noise sensitivity captures how a function reacts to noisy inputs. Note that noise here refers to flipped input bits, i.e. is different from the usual notion of noise in the context of PUFs. Formally, the noise sensitivity of a Boolean function \(f\) at noise-level \(\varepsilon\) is defined as the probability that the output flips if each input bit is flipped with probability \(\varepsilon\) (independently). I.e.,

\[\mathrm{NS}_\varepsilon(f) = \Pr_x \left[ f(x) \neq f(x') \right],\]

where \(x'\) is a copy of \(x\), but each bit is flipped independently with probability \(\varepsilon\).

The noise sensitivity is approximated using a uniform random sample of inputs and corresponding with-probability-\(\varepsilon\)-flipped inputs to \(f\).

A low noise sensitivity of \(f\) indicates that further testing is required, as \(f\) may be close to a junta and thus susceptible to a modeling attack [GFS19].

Usually, it is interesting to compute the noise sensitivity for small \(\varepsilon\):

>>> import pypuf.simulation, pypuf.metrics
>>> puf = pypuf.simulation.ArbiterPUF(n=64, seed=1)
>>> pypuf.metrics.noise_sensitivity(puf, eps=.01, seed=2)
0.216
Parameters:

  • puf (pypuf.simulation.Simulation) – Function \(f\).

  • eps (float) – Noise-level \(\varepsilon\) of the inputs.

  • seed (int) – Determines the seed for the PRNG that generates the inputs to \(f\).

  • N (int) – The number of uniform random inputs that is used to approximate the noise sensitivity.

Returns:

The noise sensitivity of \(f\) at noise level \(\varepsilon\), i.e. \(\mathrm{NS}_\varepsilon(f)\).

Return type:

float

pypuf.metrics.total_influence(puf: Simulation, seed: int, N: int = 1000) → float

The total influence, also known as average sensitivity [ODon14], is the sum of all coordinate-wise influences as computed by influence(), i.e.

\[\mathrm{I}(f) = \sum_{i=1}^n \Pr_x \left[ f(x) \neq f(x^{\oplus i}) \right].\]

We hence have \(0 \leq \mathrm{I}(f) \leq n\).

The total influence can give information about the membership of the function \(f\) in certain classes and is used in PUFMeter to analyze PUFs with respect to modeling attacks [GFS19]. Low values of total influence are concerning as they indicate that a modeling attack using the LMN algorithm may be successful.

As an example, the total influence of the pypuf.simulation.ArbiterPUF and pypuf.simulation.PermutationPUF can be computed as follows:

>>> import pypuf.simulation, pypuf.metrics
>>> pypuf.metrics.total_influence(pypuf.simulation.ArbiterPUF(n=64, seed=1), seed=2)
19.358
>>> pypuf.metrics.total_influence(pypuf.simulation.PermutationPUF(n=64, k=1, seed=1), seed=2)
32.263...
Parameters:

  • puf (pypuf.simulation.Simulation) – Function \(f\).

  • seed (int) – Determines the seed for the PRNG that generates the uniform random inputs to \(f\).

  • N (int) – The number of uniform random inputs that is used to approximate the influence.

Returns:

An approximation of the total influence of \(f\), i.e. \(\mathrm{I}_i(f)\).

Return type:

float