One of the failing test discussed in the question was coded for the purpose. It could be useful to validate that code using a known-good pseudo-random source (the output of SHA-256 for incremental values qualifies). If it failed too often, the code would need a fix! The test's definition is complex, for example in 2.7.4 (2) defining how to count the number of occurrences of the pattern searched, and an error could have crept.
But I fail to imagine an error giving what's observed, and (after fixing an issue about the definition of the incomplete gamma function that had no influence for the reference test case, and a typo of mine in one count) I confirm that the question's P-values match the question's counts.
With these results (especially the second test case, with a P-value < 1/9830), at least one of the following must hold:
- the generator's output is quite distinguishable from random (my guess);
- that's a serious case of bad luck (how bad depends strongly on among how many tests the failing cases shown have been picked, see below);
- the question's counts are somewhat wrong in a strange, irregular way;
- the math in the reference is seriously bad (but I guess that would be known).
Importantly: it appears that the test is run with many patterns. In that case, the P-value threshold considered a failure should be lowered (like, divided by the number of tests); or best, the P-values should be aggregated. For aggregation, we could use Fisher's method. In theory that requires the tests to be considered independent, which would be the case if a sample RNG output is never tested with multiple patterns. Practitioners occasionally are not so careful, but that seldom is a game-changer.
Note: The reference only skims at the issue of choosing P-value thresholds (noted $\alpha$), and does not tell how to decide if the overall result of multiple tests is pass or fail. It even makes highly misleading statements on how to interpret P-values, like the second of these three sentences at end of section 1.1.5 (emphasis mine):
An $\alpha$ of 0.001 indicates that one would expect one sequence in 1000 sequences to be rejected by the test if the sequence was random. For a P-value ≥ 0.001, a sequence would be considered to be random with a confidence of 99.9%. For a P-value < 0.001, a sequence would be considered to be nonrandom with a confidence of 99.9%.
The question rightly observes
Most interestingly, when I increase the block size by a factor of 10 (800,000 random bytes: N=8, M=800000) I get only good results on all patterns.
Especially if the generator tested is an unconditioned TRNG (see below), that would match a failure mode where the generator locally has repeating patterns, but these evolve over time.
If the source of the data tested is an unconditioned TRNG, and unless the supplier of that thing guarantees in a contract with severe penalties that no conditioning is necessary to pass any kind of test (which would be a foolish move), then failing a RNG test should be considered normal. Correspondingly, submitting this output for validation by a lab should be considered a procedural mistake: these tests are intended to test if a RNG is distinguishable from random, and unconditioned TRNGs often are!
On the other hand, if what's tested is the output of a PRNG seeded with the TRNG (as would be typical for a black-box test), and the test fails, that's indicative of (both) an extremely poor/defective PRNG and a failure of the TRNG.
Unconditioned TRNGs typically have defects, often subtle, dependent on manufacturing variations and environmental conditions. The design engineer has to factor that in. The output of an unconditioned TRNG should be used (exclusively when in operational mode):
- to monitor failure of the unconditioned TRNG; the monitoring's goal is ensure that the source delivers some entropy, above some designed-in limit, without raising false alarms.
- and to feed a PRNG, which results are used (not the TRNG's unconditioned output).
Further, if that PRNG is not a CSPRNG (which is typical of hardware PRNGs, often a variation around LFSR), for some critical usages the output of the PRNG should be the input of a good CSPRNG (it is often considered OK to directly use the hardware PRNG for more mundane things, like massive DPA countermeasures).
It is easy to turn a passable TRNG into a good RNG that passes all standard test. What's hard is to make monitoring that demonstrably detect failure on the field and acts accordingly, but does not falsely detect failure under normal use. True failure could be because attackers do all sort of nasty things: under/overvoltage, heat or evaporation of a liquefied gas to reduce the entropy rate of the RNG source, or superimposed clock/glitches on the power supply (and more) in an attempt to control the TRNG source and make it near deterministic. Sometime the adversary is only Murphy's law (perhaps in the form of poor contacts, long wires, unclean power supply, insufficient decoupling, manufacturing defect) but succeeds just as well.
Note: I heard a tale about a then inexperienced hardware manufacturer proposing an IC with module initially specified as a directly usable TRNG that always work; then found to sometime fail a test; and hastily replaced by a conditioned TRNG, with no access to the unconditioned TRNG specified. That reportedly made it difficult to properly monitor the TRNG: the only sound option would have been to break the conditioning, but the tale ends without clear indication that this was achieved and deployed.