NIST 800-90B /Non-IID track - min-entropy result > 8 for 8-bit symbol I'm conducting an analyisis of noise sources based on the NIST 800-90B Non-IID track.
Accordingly, I applied the non-iidmain.py script on a datarecord, which delivered the following output:

reading 1000000 bytes of data
Read in file ../some_data_rec.bin, 1000000 bytes long.
Dataset: 1000000 8-bit symbols, 256 symbols in alphabet.
Output symbol values: min = 0, max = 255

Running entropic statistic estimates:
- Most Common Value Estimate: p(max) = 0.00424421, min-entropy = 7.88029
- Collision Estimate: p(max) = 0.0119504, min-entropy = 6.3868
- Markov Estimate (map 6 bits): p(max) = 9.06705e-222, min-entropy = 5.73662
- Compression Estimate: p(max) = 0.00790364, min-entropy = 6.98327
- t-Tuple Estimate: p(max) = 0.006, min-entropy = 7.38082
- LRS Estimate: p(max) = 0.00389867, min-entropy = 8.0028
....


What I am wondering is the output for the LRS Estimate which delivers a min-entropy of 8.0028.
The symbols in alphabet are defined at 256 i.e. one byte.
So how is it possible a single symbol at one byte/8 bit is able to deliver more entropy than it is able to describe?
I expected the maximum entropy value for one byte should be 8 bit?
There are three separate reasonable questions here.


What does LRS Estimate mean?
Does the software compute it correctly?
Are stupid entropy estimation tools like this useful for your goal?


The setting is that we hypothesize specific families of generating processes for the data that came out of a black box.  The families of generating processes are all quite simple-minded.  For example:


A gremlin in the black box rolls a 256-sided die with unknown face probabilities $p_i$ independently for each octet in the string.
A gremlin in the black box emits outputs from unknown states by a hidden Markov model with unknown emission probabilities $e_i$ and transition probabilities $t_{ij}$.


Each of these models has a certain measure of min-entropy that is determined by the choices of parameters, such as the $p_i$.  The NIST tool, like any other entropy estimation tool, estimates the min-entropy by fitting parameters and evaluating or estimating an upper bound on the min-entropy in the specific case of the model with the parameters it fit.  Obviously 8.0028 is an upper bound on the min-entropy of an octet.  How do we get there?

To address (1), what the LRS Estimate means, the LRS estimator posits a generating process something like this:


A gremlin inside the black box has a hat with $d$ strings of varying lengths on it, the $i^{\mathit{th}}$ string having $n_i$ copies.  It shuffles the hat and draws a string out to add to the output; then it repeats.


The estimator works by guessing a few strings that might be in the hat based on repeating and nonrepeating contiguous substrings in the data, and uses the frequency of those strings as an estimate for the probability that they will occur.  (The complete details of the computation are in NIST SP800 90A, §6.3.6.)  From those probabilities it yields an estimate of the min-entropy using the standard $-\max_i \log p_i$ formula.

It doesn't consider all contiguous substrings in the output (there is a combinatorial explosion of them), so it ignores some of the probability space and thus slightly underestimates the probability of each substring it does consider, which has the effect of slightly overestimating the min-entropy—which would explain why it seems to produce an entropy rate of just over eight bits per octet.

Now, to address (2), does the software implement it correctly?  That's a question for codereviews.se, and maybe for stats.se if you want to make sure that the posited model and the estimator for the probabilities is sensible and what was intended by NIST.

Finally, to address (3), whether this is useful for your goal, the answer is not very.  It will detect certain families of patterns in your data, if those patterns appear.  High estimates like the LRS Estimate in your sample are not useful: they just mean that this particular pattern didn't appear.  Low estimates suggest that someone at NIST who wasn't even thinking about your particular noise source could predict its output with pretty good chances of success.  That's usually bad sign.  So don't worry about the slightly >8-bits-per-octet estimate for LRS: worry about the ~5-bits-per-octet estimate with a Markov model!  Does your device alternate between internal states with somewhat more predictable emission probabilities?

What you really need to do is study the physics of the object in question from an adversary's perspective, and try to find the best way to predict the output knowing how your particular noise source works.  Then compute the entropy of that model.  If it's higher than all of the NIST estimates, either you had a lucky sample or someone at NIST who doesn't even know what you're working on was better at studying your noise source than you are.