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