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.