RaBiGeTe MT

Multi-threaded version of RaBiGeTe with GUI (Windows only)

Cristiano fecit anno Domini MMXI

Index


Updates

Date Ver Description
2013-12-19 2.0.0 Added the 64-bit version.
Improved the scalability of some tests on multi-core CPU (currently: partition, peak, windowed autoc. and DFT).
Added several random walk based tests (including two 2-D versions).
Changed the peak test and added a "multi-block" version.
Changed the partition test and increased the block size from 12 to 13 bits.
Increased the block size for the windowed autocorrelation test from 31 bits to unlimited.
Increased the block size for the permutation test from 12 to 32 bits.
Replaced SL test for the overall p-values with the stronger binomial test.
Added some tests in the "Graph" page.
Added a list control to disable and hide the unwanted tests in the "Parameters" page and to change the display order in the tables.
Added a control to automatically sort the p-values in the tables when the testing phase ends.
Added a control to set the row height of the tables.
Added some tooltips to explain the meaning of the test parameters.
Improved the parameter checking for some tests to run with very short sequences.
Improved the responsiveness of the GUI during the testing phase.
The sorting of the table in the "Table" page is now much faster.
Removed the overall values in the main table and in the "Pearson" table.
Removed the "Auto len" checkbox.
Removed the "Extended output" checkbox of the block and gap distance test.
Starting from the next version, RaBiGeTe will be able to load the preferences saved by an earlier version.
Improved the updating speed of the table during the testing phase.
The file with the results now contains all the pages of the GUI.
Fixed memory allocation and deallocation when a big amount of memory is required.
Many minor improvements.
2011-11-02 1.1.0 Added the ability to use a DLL to get the bits or the numbers to test.
Definitely discarded the parameter n for the Maurer's test (in v1.0.0 it was disabled and unused).
Added some information about the running time.
Changed some error messages.
2011-10-28 1.0.0 First release.

What RaBiGeTe does

With RaBiGeTe you can test a random or pseudo-random bit or number generator to see whether it has the characteristics expected in a true random generator.

For those who are familiar with the old version of RaBiGeTe, this version includes the following improvements:
  1. the bits to test can be obtained from a user supplied DLL;
  2. support for multi-core systems;
  3. this version is a classical Windows program with the standard controls (it no longer runs in a DOS window);
  4. added new table and graph for the result;
  5. added new tests;
  6. this version comes with some sets of ready to use test parameters;
  7. you can save your own presets.
This version runs under Windows only and includes the following tests:
  1. AMLS (my test based on the M. Mitzenmacher's AMLS);
  2. Blocks and gaps (an improved version of the FIPS-140 Runs test);
  3. Blocks and gaps distance;
  4. Collision (my improved version);
  5. Coupon collector (as described by Knuth);
  6. Cumulative sum (NIST test);
  7. DFT (my 1-D and 2-D spectral test);
  8. Linear complexity;
  9. Long blocks (NIST BlockFrequency test);
  10. Maurer (my improved version of the Maurer's universal statistical test);
  11. Non overlapping template matching (my improved version of the NIST test);
  12. Overlapping entropy (NIST test);
  13. Overlapping template matching (corrected version of the NIST test);
  14. Partition (as described by Knuth, also called "Poker test");
  15. Peak (corrected and improved version of the NIST DFT test);
  16. Permutation (as described by Knuth);
  17. Random walk (1-D and 2-D versions);
  18. Rank (my vastly improved version of the NIST test);
  19. Runs (a stronger and generalized version of the runs up'n'down test);
  20. Serial (NIST test);
  21. Serial two-bit (FIPS-140);
  22. Short blocks (my stronger version of the FIPS-140 poker and monobit tests);
  23. Weight;
  24. Windowed autocorrelation (which includes the "plain" autocorrelation test).
RaBiGeTe is highly configurable along with the test parameters. You can enable the tests you like and you can change the test parameters using the intuitive GUI.

If you just want to see what RaBiGeTe is, you can go to the download section to download the "Minimalist version". Then unzip the archive in a folder of your choice; run RaBiGeTe_MT_x86_XP.exe and press the "Start" button on the lower right corner of the window.

info RaBiGeTe doesn't write neither in the registry nor in any other part of the operating system, it only writes 3 files in the same executable directory: the output file (its default name is "_RaBiGeTe.txt"), "prefs.bin" and "presets.ini". If you use the DFT test or the PEAK test, RaBiGeTe will also create a file called "FFTWwisdom_f".
When you no longer need RaBiGeTe, just delete its folder.

Quick start

You must first prepare the data to test. There are two way to do that: to save the output of your generator in a file or to write a DLL which outputs the numbers to test.
In both cases, you should write the name of the file to test or the DLL to use in the edit "File(s) to test or DLL to use". RaBiGeTe converts the content of the edit control to lower case and it searches the string ".dll". If that string is found, then RaBiGeTe will consider the file as a DLL. So, if you want to use an input file with the data to test, you should avoid names like "PRNG.DLL.dat" or "Bits from dll 'myrng.dll'".

- The input file

You should save in one or more files the bits (or numbers) to test. If there are several files to test (not necessarily of the same size), you must use the wildcard like '*' or '?'. For example, if you want to test "bits01", "bits02", ..., "bits99" located in the "C:\random bits" directory, pick one of those files using the file picker control "File(s) to test or DLL to use", then manually change the text in: "C:\random bits\bits??" or "C:\random bits\bits*" (in the latter case, it will be tested also the files called, for example, "bits_rnd2_00", ..., "bits_rnd2_99").
The program will load the files in alphabetical order (the file "bits10" comes before of the file "bits9", so the files should be named: "bits09", "bits10").
If the files are smaller than the expected size, RaBiGeTe will show an error message and the results are calculated using the bits loaded before the error.

- Using a DLL

In the download section you find the source code of a sample DLL that you can customize for your generator.
The DLL should export 4 functions, but only the first is mandatory (the names must not be changed):

unsigned long RND_GetUL(void)
returns a 32-bit number to test; if you have a bit generator, you must concatenate 32 bits to form an unsigned long
char *RND_GetName(void)
returns the name of the generator
char *RND_GetDesc(void)
returns the description of the generator
char *RND_GetOutFileName(void)
returns the name that RaBiGeTe will use to create the output file. If NULL or an empty string is returned, then the default name "_RaBiGeTe.txt" will be used.
The name and the description of the generator are written in the output file.
warn Your DLL is loaded (and hence initialized) when you press the "Start" button (to start the testing phase) and it is freed as soon as the testing phase ends. In other words, if your generator has an initialization phase, it is initialized every time you start the testing phase (and not only when you run RaBiGeTe).

- How to test

  1. Go to the download section to download the appropriate zip files;
  2. unzip the archive in a folder of your choice;
  3. run RaBiGeTe_MT.exe;
  4. pick the file to test or the DLL to load using the "File to test or DLL to use" control;
  5. choose a preset (I suggest the one named "Good'n'fast" for a preliminary testing);
  6. set the sequence length and the number of sequences to test (if you want to test all the bits in the input file(s), write "0" in the edit "Seq. len." and change the edit "Seq. to test");
  7. click the button "Start" or press the "Enter" key.
RaBiGeTe starts to test the input file or the DLL and it shows the p-values obtained from the tests.
info When a DLL is used, the GUI is not updated while RaBiGeTe collects the bits from the DLL; if the generator is slow, the GUI will freeze.

Each test is a thread which runs on one CPU core. If you enable n tests, the program will create n threads, but there will be only a limited number of concurrent threads, the others threads will be in an efficient wait state.
The maximum number of concurrent threads can be chosen in the "Prefs" page. I suggest to set this value to the number of the cores (but you can try any value in the allowed range).
If you want to stop the test, press "Del" on the keyboard (wait for RaBiGeTe to finish testing the current sequence).
Once RaBiGeTe has finished, look at the main table, at the "Pearson" table and at the "Graph". You would also take a look at the "Messages" page just to check any error condition.


Program description

RaBiGeTe is based on a tabbed control with six pages.
If you click the header of a table, the numeric or alphanumeric values in the clicked column will be sorted.

- Parameters page

In this page there are the settings for the tests. Here, you can enable/disable the tests, you can change all the test parameters, the file to test or the DLL to use, the sequence length and the number of sequences to test.

info Before to start the testing phase, RaBiGeTe checks the parameters range; if the chosen range falls outside the allowed range, the test will be disabled; if the chosen range is wider than the allowed range, RaBiGeTe narrows the range.

warn Some tests may output many p-values. For those tests (like "AutoWnd" and "NOTM") there is an additional control in the "Parameters" page which helps in reducing the number of calculated p-values.

When you choose the "Save on exit" preset, RaBiGeTe will save the test parameters on exit (without the need to press the "Save" button).
When you see the word "step" in the name of a parameter, zero is not allowed, but you can use positive or negative values. In the latter case, the parameter will be multiplied by 2^-step. For example, in the image you see the test "AutoWnd" (windowed autocorrelation test) with Dmin = 1 bit and Dstep = -1. This means that the parameter D will be: 1 bit, 2 bit, 4 bit, 8 bit and so on.

Parameters tab


- Table page

In this page it is showed the test progress and the result.
If you want to stop the testing, just press "Del" on the keyboard. RaBiGeTe will stop when all the tests are performed on the current sequence (the program won't break immediately).
"KS" means the Kolmogorov-Smirnov test, "AD" means the Anderson-Darling test and "Bino" is the binomial test.

pvals: number of the valid p-values.
pv min: smallest p-value in the row.
pv max: biggest p-value in the row.

The sample image shows "20" under "pvals" for the rows: 1, 2, ...; it means that 20 sequences have been tested (bad practice, but this is just an example; try to test at least 50 sequences).
You also see "138" in the rows "KS", "AD" and "Bino" under "pvals"; it means that there are 138 valid rows with the tests ("AMLS 2", "AMLS 8", ...).
The KS test of the p-values in the row 1 (test "AMLS 2") from column 1 to 20 is 0.2375, while the AD test of the same p-values is 0.3929 and the binomial test is 0.8398.

The KS test of the 138 p-values in the column "KS" is 0.7347, while the AD test of the same p-values is 0.8357 and the p-value for the binomial test is 0.9988.
The KS test of the 138 p-values in the column "AD" is 0.4532, while the AD test of the same p-values is 0.4685 and the p-value for the binomial test is 0.9777.

Let ns be the number of the sequences tested so far. When a p-value obtained from a test is lesser than 0.01/ns or bigger than 1 - 0.01/ns, that p-value is reported in the columns "pv min" or "pv max" using the red color. It doesn't necessarily mean that there is a problem, it is just an indication to catch your attention.

Table tab warnThe calculation of the "blue p-values" for the KS and the AD tests is affected by errors. Usually there are 2 exact significant figures, hence it should not be a problem.
In case of doubt, when you see a low KS or AD p-value, take the p-values for the "Bino" (binomial) test into account (they are exact).
Table short Some tests (like the Maurer's Universal test) need a variable (and unpredictable) number of bits.
When the needed bits are not available, RaBiGeTe shows "short" to indicate that the bits sequence is too short. The image shows "short" in the row 10 for the 4-th sequence and the valid p-values count is 19 (in the column "pvals").

Table failure The image shows a typical output when a weak generator is tested.
When a sequence is really bad, some tests may not be able to calculate the related p-value; in this case, that p-value is reported as "fail" and RaBiGeTe will shows "WARNING! Big failure" on the top left corner of the table.
When it happens, there is probably no reason to keep testing; if you want to stop the testing, just press the "Del" key on the keyboard. When all the tests on the current sequence will end, RaBiGeTe will stop testing.
warn Although extremely unlikely, theoretically, the label "fail" may be reported for a single p-value of just one test, hence "WARNING! Big failure" does not necessarily mean that the generator is really bad. However, when we see a result like this, there is no doubt that the generator is really flawed.

- Pearson page

Pearson tab This page shows the p-values related to the Pearson's chi-square test.

The number of bins is calculated as the square root (rounded up) of the number of sequences tested. The bins are numbered from 1 to n and are showed in the column 1, 2, ..., n. Each bin contains the p-values in the interval [(b-1)/n, b/n), where b is the bin number.
The expected number of the p-values in each bin is showed in the column "Exp", while the count of the p-values in each bin is showed in the column 1, 2, ..., n.
The reported p-value for each test (showed in the rows 1, 2, ...) is the probability that the calculated chi-square is bigger than an uniformly distributed random variate.

- Graph page

This page is divided into two parts.
The graph shows the distribution of the ordered p-values obtained from each sub-test; there are two points (one point for KS and one point for AD) for each valid sub-test in the "Table" and in the "Pearson" pages.
When a good generator is tested, the points shouldn't be too far from the black ideal line. The "numerical distance" from the ideal line is given in the left side of the page.
The table shows the p-values for some statistical tests. The columns "KS" and "AD" refer to the respectives columns of the "Table" page.

The critical values for the tests in this table have been obtained by simulation (which took 1535 hours of CPU time on an Intel i7-4770 and 4.66*10^13 double precision high quality pseudo-random numbers have been generated).
Any p-value less than 10^-5 is reported as "< 0.00001" and any p-value greater than 0.99999 is reported as "> 0.99999".
When there are only three sub-tests (three rows in the "Table" page), the tests SW, CC and AV will output the same p-values.
Graph tab
KS Kolmogorov-Smirnov
AD Anderson-Darling
SL straight line
CM Cramer-von Mises
SW Shapiro-Wilk
CC Pearson's correlation coefficient
AV absolute value correlation coefficient

- Messages page

Messages tab This page shows any kind of message (infos, warnings and errors).

When the testing phase ends, this page shows some information about the testing times.
In this example, you can see that the CPU time taken by all the tests is 3 minutes and 17 seconds, while the running time of the testing phase is just 55 seconds. This happens when RaBiGeTe runs in a multi-core system.
You can also see that the CPU load during the testing phase was 44.5% (equivalent to 3.56 fully loaded cores of an i7-4770 CPU).

- Preferences page

In this page the user can change the basic behavior of RaBiGeTe.

Prefs tab

Disable and hide / Display order: if you don't like some tests, you just need to mark the unwanted test using the corresponding checkbox; the checked tests will not appear in the "Parameters" page (and they will be disabled).
The same list control is used to determine the display order of the tests in the tables. To change the display order, select a row in the list and use the "Up" and "Down" buttons to move the row. With the "Sort" button the tests will be alphabetically sorted.

Running priority: if you are starting a long testing phase, you may want to assign the idle priority to RaBiGeTe so that you can use your PC for other tasks.

Concurrent threads: RaBiGeTe creates one threads for each enabled test to take advantage from a multi-core CPU. I suggest to set this value to the number of the cores in your CPU, but you can try any value in the allowed range.

P-value digits: it's the number of the decimal digits that RaBiGeTe uses to show the p-values (the calculations are always done in full precision).

Auto sort p-values: when the testing phase ends, the p-values in the tables can be automatically sorted (you can always click the column header to sort the tables as you like).

Tables row height: row height of the tables in the pages "Table" and "Pearson".


Download

Starting from version 2.0.0, a 64-bit version of RaBiGeTe is available. I strongly suggest to use it (if you have a 64-bit operating system) when you need to run a memory-demanding test (like the DFT test with many rows).

Note: if you are upgrading from version 1.0.0 or 1.1.0, please, delete the file "prefs.bin" in the RaBiGeTe folder.

- Minimalist version

If you just want to see what RaBiGeTe is, you can choose this ready to use minimalist version.
Unpack, run the exe and press "Start" (or press "Enter" on the keyboard). That's it.

2013-12-19: minimalist (3,3 MB).

- Data files

You need these files only if you want to use the related tests.

2013-12-19: data files for tests: Coupon, Collision and RandomWalk (874 kB).

2013-12-19: data file for the Partition test (23 MB).

- Runtime libraries

RaBiGeTe needs the files: msvcp110.dll and msvcr110.dll; you may already have them installed.

2013-12-19: runtime libraries (598 kB).

Alternatively, you can install the "Visual C++ Redistributable Packages for Visual Studio 2012" from this link:
http://www.microsoft.com/en-us/download/details.aspx?id=30679

- Executables

These packages contain:
  1. executable;
  2. FFTW DLL for the DFT-based tests (this DLL is necessary even if you don't use these tests);
  3. presets file;
2013-12-19: 32-bit version for Windows XP tested on XP SP3 (2,7 MB).

2013-12-19: 64-bit version tested on Windows 7 SP1 (3,8 MB).

2013-12-19: 32-bit version tested on Windows 7 SP1 (2,7 MB).

- Sample DLL source code

These packages contain the Visual Studio project files for the DLL that RaBiGeTe can use to test your generator (you don't need a DLL if you use a data file with the numbers to test).

2011-11-02: 32-bit project files for Visual Studio 2008 Express Edition (10 kB).

2013-12-19: 32 and 64-bit project files for Visual Studio 2012 Express Edition (20 kB).


Feedback

Please, send your suggestions here.