ea_iid results are unstable

[sellicott]

Hi all, It seems like the permutation tests in the ea_iid program are pretty unstable. I can run the ea_iid on the same data file and come back with different results. Some of these results are unstable enough that it can change a passing result to a failing result on the same data file. For reference, the data I am running the tests on is composed of 1,000,000 8-bit samples per SP800-90B guidelines.

Background: I have been using the ea_iid program to test some raw data. Since I have a significant amount of data to go through, I wanted to script the test process in order to look at a summarized report. A few of the data files failed the tests, so I went back to look at them in greater detail. It so happened that when I ran ea_iid again directly, the tests passed. This made me very suspicious, so I ran a few more times logging the result each time. It seems like the results are usually relatively stable (within 1-2 counts), but every now and then a statistic will be significantly different from the other runs.

I presume the instability is due to using the Fisher-Yates shuffle algorithm, which is by it's nature unstable. It just seems odd that it's this variable. Here is my interpretation of the problem. The dataset I'm using is borderline on one of the permutation tests (over a set of 20 tests, the median was 9996); however, occasionally the Fisher-Yates shuffle smiles on the data and let's it pass.

Questions:

• Are the permutation test results expected to be this unstable?
• Would re-running the tests with a larger dataset help? If so, how much data extra data is needed?
• Are there any selftests for the ea_iid tests? It looks like the selftests are only performed on the ea_non_iid tests.
• If I have datasets like this, what is the proper procedure?

[joshuaehill]

• Yes, the permutation testing is non-deterministic.
• In general, for this test the more data, the more statistically meaningful the result is.
• The tests are non-deterministic, so known answer tests (the style of testing used here) isn't going to work.
• I suggest conducting many trials with different data sets from the same device / environmental conditions and looking at the pass rate of each of the tests. (The anticipated false positive rate is 1/1000, so if your failure rate is larger than this, this is evidence the source is not IID). You can create a statistical test under an assumed binomial distribution (n=the number of data sets you are using, p=1/1000) for each of the tests.

All that said, the hard part of going through the IID path is producing a technical argument that you expect the system to be IID. Most noise sources are not.

[sellicott]

Thank you for the fast reply!

A couple follow on questions:

• Is the p=1/1000 for the permutation tests as a whole, or for each subtest? What I am getting at, is it a problem to occasionally fail one of the many permutation tests as long as there is no repeat and the probability of it occurring is < 1/1000? Or do all of the tests, taken as a unit, need to pass with p = 1/1000?

• Does re-running the ea_iid tests on the same data multiple times and finding the mean/median statistic have any meaning? Would this indicate whether borderline cases are above/below the critical statistic?

  Thank you very much for your time/insights.

[joshuaehill]

• The p=1/1000 is the false positive rate for each test.
• I suppose rerunning the testing on that particular data set would tell you something more about that particular data set, but information about that particular data set isn't as interesting as better information about the underlying source. This testing is intended to tell us something about the underlying source, and to get better information on the source, you should really be using multiple distinct data samples.

[sellicott]

Thank you very much!