LMN Algorithm

The LMN Algorithm can compute models for functions with Fourier spectra concentrated on the low degrees [LMN93], [ODon14] and part of the PUFMeter [GFS19] PUF testing toolbox.

The attack requires access to a number of uniformly random challenge-response pairs (CRPs). Depending on the amount of provided CRPs and the type of function provided, the results may have, with certain probability, a guaranteed accuracy. (For more details, we refer the reader to the PAC learning framework [ODon14].)

Example Usage

To run the attack, CRP data of the PUF token under attack is required. Such data can be obtained through experiments on real hardware, or using a simulation. In this example, we use the pypuf Arbiter PUF simulator and configure it to use feature vectors as inputs rather than challenge vectors by setting transform='id':

>>> import pypuf.simulation, pypuf.io
>>> puf = pypuf.simulation.ArbiterPUF(n=32, transform="id", seed=1)
>>> challenges = pypuf.io.random_inputs(n=32, N=2000, seed=2)
>>> crps = pypuf.io.ChallengeResponseSet(challenges, puf.val(challenges))

To run the attack, we need to decide how many levels of Fourier coefficients we want to approximate. There are \(n\) levels, the \(i\)-th level has \(\binom{n}{i}\) coefficients. The run time of the attack is linear in the number of coefficients. With the steeply increasing run time, in practice, degree 1 and degree 2 are reasonable choices. Increasing the degree further will not only lead to high requirements on computation time, but may actually worsen the predictive accuracy, as more coefficients need to be approximated.

>>> import pypuf.attack
>>> attack = pypuf.attack.LMNAttack(crps, deg=1)
>>> model = attack.fit()

The model accuracy can be measured using the pypuf accuracy metric pypuf.metrics.accuracy().

>>> import pypuf.metrics
>>> pypuf.metrics.similarity(puf, model, seed=4)
array([0.95])

API

class pypuf.attack.LMNAttack(crps: ChallengeResponseSet, deg: int = 1)

__init__(crps: ChallengeResponseSet, deg: int = 1) → None

Given a list of function values of a function \(f: \{-1,1\}^n \to \mathbb{R}\), an approximation of the Fourier spectrum of the underlying function can be computed.

The approximation is guaranteed to be correct, if the list contains all function values and the degree equals \(n\), shown here using the Boolean AND function:

>>> import numpy as np
>>> import pypuf.io, pypuf.attack
>>> challenges = 1 - 2 * np.array([[0, 0], [0, 1], [1, 0], [1, 1]])
>>> responses_and = 1 - 2 * np.array([[0], [0], [0], [1]])
>>> crps_and = pypuf.io.ChallengeResponseSet(challenges, responses_and)
>>> (1 - pypuf.attack.LMNAttack(crps_and, 2).fit().eval(challenges)) // 2
array([[0.],
       [0.],
       [0.],
       [1.]], dtype=float32)

If additionally the responses are from \(\{-1,1\}\), then the sum of squares of the Fourier coefficients equals 1, as illustrated here using the majority vote function:

>>> challenges = 1 - 2 * np.array([[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]])
>>> responses_maj = 1 - 2 * np.array([[0], [0], [0], [1], [0], [1], [1], [1]])
>>> crps_maj = pypuf.io.ChallengeResponseSet(challenges, responses_maj)
>>> exp = pypuf.attack.LMNAttack(crps_maj, 3).fit().expansion
>>> exp
array([[ 0. ,  0.5,  0.5,  0.5,  0. ,  0. ,  0. , -0.5]], dtype=float32)
>>> np.sum(exp**2)
1.0

fit() → FourierSimulation: Runs the attack configured in this attack object. The obtained model is stored as model() property and provided as return value.

property model: Simulation: The model that was obtained running the fit() method, None if fit() was not run yet.