Reference for sts-pylib
¶
The repository for sts-pylib
is available on GitHub,
and a demonstration of running these randomness tests
over the getrandbits()
method from Python’s random
module
is available on Kaggle.
This package wraps the statistical tests written in C from sts, the randomness testing suite created by the National Institute of Standards and Technology. Their suite is infact an implementation of the randomness tests they recommended in the SP800-22 paper 1—a copy is available on their website.
Note that their original suite was only accessible via their command-line interface. This package modifies the C code so that they can be used individually, i.e. providing a functional interface to the statistical tests.
- 1
National Institute of Standards and Technology <Andrew Rukhin, Juan Soto, James Nechvatal, Miles Smid, Elaine Barker, Stefan Leigh, Mark Levenson, Mark Vangel, David Banks, Alan Heckert, James Dray, San Vo, Lawrence E Bassham II>, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications”, Special Publication 800-22 Revision 1a, April 2010.
-
sts.
frequency
(epsilon)¶ Frequency (Monobit) statistical test for randomness
The focus of the test is the proportion of zeroes and ones for the entire sequence. The purpose of this test is to determine whether the number of ones and zeros in a sequence are approximately the same as would be expected for a truly random sequence. The test assesses the closeness of the fraction of ones to a half, that is, the number of ones and zeroes in a sequence should be about the same. All subsequent tests depend on the passing of this test.
- Parameters
epsilon (
List
[int
]) – The sequence of bits as generated by the RNG or PRNG being tested.- Return type
float
- Returns
p-value
-
sts.
block_frequency
(epsilon, M)¶ Frequency Within Block statistical test for randomness
The focus of the test is the proportion of ones within M-bit blocks. The purpose of this test is to determine whether the frequency of ones in an M-bit block is approximately M/2, as would be expected under an assumption of randomness. For block size M=1, this test degenerates to test 1, the Frequency (Monobit) test.
- Parameters
epsilon (
List
[int
]) – The sequence of bits as generated by the RNG or PRNG being tested.M (
int
) – The length of each block.
- Return type
float
- Returns
p-value
-
sts.
runs
(epsilon)¶ Runs statistical test for randomness
The focus of this test is the total number of runs in the sequence, where a run is an uninterrupted sequence of identical bits. A run of length k consists of exactly k identical bits and is bounded before and after with a bit of the opposite value. The purpose of the runs test is to determine whether the number of runs of ones and zeros of various lengths is as expected for a random sequence. In particular, this test determines whether the oscillation between such zeros and ones is too fast or too slow.
- Parameters
epsilon (
List
[int
]) – The sequence of bits as generated by the RNG or PRNG being tested.- Return type
float
- Returns
p-value
-
sts.
longest_run_of_ones
(epsilon)¶ Longest Run of Ones in a Block statistical test for randomness
The focus of the test is the longest run of ones within M-bit blocks. The purpose of this test is to determine whether the length of the longest run of ones within the tested sequence is consistent with the length of the longest run of ones that would be expected in a random sequence.
Note that an irregularity in the expected length of the longest run of ones implies that there is also an irregularity in the expected length of the longest run of zeroes. Therefore, only a test for ones is necessary.
- Parameters
epsilon (
List
[int
]) – The sequence of bits as generated by the RNG or PRNG being tested.- Return type
float
- Returns
p-value
-
sts.
rank
(epsilon)¶ Binary Matrix Rank statistical test for randomness
The focus of the test is the rank of disjoint sub-matrices of the entire sequence. The purpose of this test is to check for linear dependence among fixed length substrings of the original sequence.
Note that this test also appears in the DIEHARD battery of tests.
- Parameters
epsilon (
List
[int
]) – The sequence of bits as generated by the RNG or PRNG being tested.- Return type
float
- Returns
p-value
-
sts.
discrete_fourier_transform
(epsilon)¶ Discrete Fourier Transform (Spectral) statistical test for randomness
The focus of this test is the peak heights in the Discrete Fourier Transform of the sequence. The purpose of this test is to detect periodic features (i.e., repetitive patterns that are near each other) in the tested sequence that would indicate a deviation from the assumption of randomness. The intention is to detect whether the number of peaks exceeding the 95% threshold is significantly different than 5%.
- Parameters
epsilon (
List
[int
]) – The sequence of bits as generated by the RNG or PRNG being tested.- Return type
float
- Returns
p-value
-
sts.
non_overlapping_template_matchings
(epsilon, m)¶ Non-overlapping Template Matching statistical test for randomness
The focus of this test is the number of occurrences of pre-specified target strings. The purpose of this test is to detect generators that produce too many occurrences of a given non-periodic (aperiodic) pattern.
For this test (and for the Overlapping Template Matching test), an m-bit window is used to search for a specific m-bit pattern. If the pattern is not found, the window slides one bit position. If the pattern is found, the window is reset to the bit after the found pattern, and the search resumes.
- Parameters
epsilon (
List
[int
]) – The sequence of bits as generated by the RNG or PRNG being tested.m (
int
) – The length in bits of each template. The template is the target string.
- Return type
float
- Returns
p-value
-
sts.
overlapping_template_matchings
(epsilon, m)¶ Overlapping Template Matching statistical test for randomness
The focus of the Overlapping Template Matching test is the number of occurrences of pre-specified target strings. Both this test (and the Non-overlapping Template Matching test) use an m-bit window to search for a specific m-bit pattern. As with the Non-overlapping test, if the pattern is not found, the window slides one bit position. The difference between this test and the Non-overlapping test is that when the pattern is found, the window slides only one bit before resuming the search.
- Parameters
epsilon (
List
[int
]) – The sequence of bits as generated by the RNG or PRNG being tested.m (
int
) – The length in bits of the template—in this case, the length of the run of ones.
- Return type
float
- Returns
p-value
-
sts.
universal
(epsilon)¶ Maurer’s (Universal) statistical test for randomness
The focus of this test is the number of bits between matching patterns (a measure that is related to the length of a compressed sequence). The purpose of the test is to detect whether or not the sequence can be significantly compressed without loss of information. A significantly compressible sequence is considered to be non-random.
- Parameters
epsilon (
List
[int
]) – The sequence of bits as generated by the RNG or PRNG being tested.- Return type
float
- Returns
p-value
-
sts.
linear_complexity
(epsilon, M)¶ Linear Complexity statistical test for randomness
The focus of this test is the length of a linear feedback shift register (LFSR). The purpose of this test is to determine whether or not the sequence is complex enough to be considered random. Random sequences are characterized by longer LFSRs. An LFSR that is too short implies non-randomness.
- Parameters
epsilon (
List
[int
]) – The sequence of bits as generated by the RNG or PRNG being tested.M (
int
) – The length in bits of a block.
- Return type
float
- Returns
p-value
-
sts.
serial
(epsilon, m)¶ Serial statistical test for randomness
The focus of this test is the frequency of all possible overlapping m-bit patterns across the entire sequence. The purpose of this test is to determine whether the number of occurrences of the 2m-bit overlapping patterns is approximately the same as would be expected for a random sequence. Random sequences have uniformity; that is, every m-bit pattern has the same chance of appearing as every other m-bit pattern.
Note that for m = 1, the Serial test is equivalent to the Frequency test.
- Parameters
epsilon (
List
[int
]) – The sequence of bits as generated by the RNG or PRNG being tested.m (
int
) – The length in bits of each block.
- Return type
List
[float
]- Returns
p-values
-
sts.
approximate_entropy
(epsilon, m)¶ Approximate Entropy statistical test for randomness
As with the Serial test, the focus of this test is the frequency of all possible overlapping m-bit patterns across the entire sequence. The purpose of the test is to compare the frequency of overlapping blocks of two consecutive/adjacent lengths (m and m+1) against the expected result for a random sequence.
- Parameters
epsilon (
List
[int
]) – The sequence of bits as generated by the RNG or PRNG being tested.m (
int
) – The length of each block—in this case, the first block length used in the test. m+1 is the second block length used.
- Return type
float
- Returns
p-value
-
sts.
cumulative_sums
(epsilon, reverse=False)¶ Cumulative Sums (Cusum) statistical test for randomness
The focus of this test is the maximal excursion (from zero) of the random walk defined by the cumulative sum of adjusted (-1, +1) digits in the sequence. The purpose of the test is to determine whether the cumulative sum of the partial sequences occurring in the tested sequence is too large or too small relative to the expected behavior of that cumulative sum for random sequences. This cumulative sum may be considered as a random walk. For a random sequence, the excursions of the random walk should be near zero. For certain types of non-random sequences, the excursions of this random walk from zero will be large.
- Parameters
epsilon (
List
[int
]) – The sequence of bits as generated by the RNG or PRNG being tested.reverse (
bool
) – Use the backwards method, as opposed to the forward one.
- Return type
float
- Returns
p-value
-
sts.
random_excursions
(epsilon)¶ Random Excursions statistical test for randomness
The focus of this test is the number of cycles having exactly K visits in a cumulative sum random walk. The cumulative sum random walk is derived from partial sums after the (0,1) sequence is transferred to the appropriate (-1, +1) sequence. A cycle of a random walk consists of a sequence of steps of unit length taken at random that begin at and return to the origin. The purpose of this test is to determine if the number of visits to a particular state within a cycle deviates from what one would expect for a random sequence. This test is actually a series of eight tests (and conclusions), one test and conclusion for each of the states: -4, -3, -2, -1 and +1, +2, +3, +4.
- Parameters
epsilon (
List
[int
]) – The sequence of bits as generated by the RNG or PRNG being tested.- Return type
List
[float
]- Returns
p-values
-
sts.
random_excursions_variant
(epsilon)¶ Random Excursions Variant statistical test for randomness
The focus of this test is the total number of times that a particular state is visited (i.e., occurs) in a cumulative sum random walk. The purpose of this test is to detect deviations from the expected number of visits to various states in the random walk. This test is actually a series of eighteen tests (and conclusions), one test and conclusion for each of the states: -9, -8, …, -1 and +1, +2, …, +9.
- Parameters
epsilon (
List
[int
]) – The sequence of bits as generated by the RNG or PRNG being tested.- Return type
List
[float
]- Returns
p-values