  Testability of digital ICs rely on the principle of controllability and
observability. Adopting conventional techniques like scan-chains open up
avenues for attacks, and hence cannot be adopted in a straight-forward manner
for security chips. Furthermore, testing becomes incredibly challenging for the
promising class of hardware security primitives, called PUFs, which offer
unique properties like unclonability, unpredictibility, uniformity, uniqueness,
and yet easily computable. However, the definition of PUF itself poses a
challenge on test engineers, simply because it has no golden response for a
given input, often called challenge. In this paper, we develop a novel test
strategy considering that the fabrication of a batch of $N>1$ PUFs is
equivalent to drawing random instances of Boolean mappings. We hence model the
PUFs as black-box Boolean functions of dimension $m\times1$, and show
combinatorially that random designs of such functions exhibit
correlation-spectra which can be used to characterize random and thus {\em
good} designs of PUFs. We first develop theoretical results to quantize the
correlation values, and subsequently the expected number of pairs of such
Boolean functions which should belong to a given spectra. In addition to this,
we show through extensive experimental results that a randomly chosen sample of
such PUFs also resemble the correlation-spectra property of the overall PUF
population. Interestingly, we show through experimental results on $50$ FPGAs
that when the PUFs are infected by faults the usual randomness tests for the
PUF outputs such as uniformity, fail to detect any aberration. However, the
spectral-pattern is clearly shown to get affected, which we demonstrate by
standard statistical tools. We finally propose a systematic testing framework
for the evaluation of PUFs by observing the correlation-spectra of the PUF
instances under test.
