×

A visual analysis method of randomness for classifying and ranking pseudo-random number generators. (English) Zbl 1484.62028

Summary: The development of new pseudo-random number generators (PRNGs) has steadily increased over the years. Commonly, PRNGs’ randomness is “measured” by using statistical pass/fail suite tests, but the question remains, which PRNG is the best when compared to others. Existing randomness tests lack means for comparisons between PRNGs, since they are not quantitatively analysing. It is, therefore, an important task to analyze the quality of randomness for each PRNG, or, in general, comparing the randomness property among PRNGs. In this paper, we propose a novel visual approach to analyze PRNGs randomness allowing for a ranking comparison concerning the PRNGs’ quality. Our analysis approach is applied to ensembles of time series which are outcomes of different PRNG runs. The ensembles are generated by using a single PRNG method with different parameter settings or by using different PRNG methods. We propose a similarity metric for PRNG time series for randomness and apply it within an interactive visual approach for analyzing similarities of PRNG time series and relating them to an optimal result of perfect randomness. The interactive analysis leads to an unsupervised classification, from which respective conclusions about the impact of the PRNGs’ parameters or rankings of PRNGs on randomness are derived. We report new findings using our approach in a study of randomness for state-of-the-art numerical PRNGs such as LCG, PCG, SplitMix, Mersenne Twister, and RANDU as well as chaos-based PRNG families such as \(K\)-Logistic map and \(K\)-Tent map with varying parameter \(K\).

MSC:

62F07 Statistical ranking and selection procedures
62H30 Classification and discrimination; cluster analysis (statistical aspects)
62M10 Time series, auto-correlation, regression, etc. in statistics (GARCH)
65C10 Random number generation in numerical analysis
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] W. Aigner, S. Miksch, H. Schumann, C. Tominski, Visualization of Time-Oriented Data, Springer Publishing Company, Incorporated, first ed., ISBN 0857290789, 2011.
[2] A.B. Alencar, F.V. Paulovich, R. Minghim, M.G. de Andrade Filho, M.C.F. de Oliveira, Similarity-based visualization of time series collections: an application to analysis of streamflows, in: 2008 12th International Conference Information Visualisation, IEEE, 280-286, 2008.
[3] Bailey, D. H.; Borwein, J. M.; Brent, R. P.; Reisi, M., Reproducibility in computational science: a case study: randomness of the digits of Pi, Exp. Math., 26, 3, 298-305 (2017) · Zbl 1426.11133
[4] F. Barbosa, A. Vidal, F. Mello, Machine learning for cryptographic algorithm identification, J. Inf. Secur. Cryptogr. (Enigma) 3(1) (2016) 3.
[5] Borg, I.; Groenen, P., Modern Multidimensional Scaling: Theory and Applications (2005), Springer · Zbl 1085.62079
[6] R. Bost, R.A. Popa, S. Tu, S. Goldwasser, Machine learning classification over encrypted data, in: NDSS, vol. 4324, 4325, 2015.
[7] Bratley, P.; Fox, B.; Schrage, L., A Guide to Simulation (1987), Springer Verlag: Springer Verlag New York
[8] Eichenauer, J.; Lehn, J., A non-linear congruential pseudo random number generator, Statistische Hefte, 27, 1, 315-326 (1986) · Zbl 0607.65001
[9] Fan, F.; Wang, G., Learning from pseudo-randomness with an artificial neural network-does god play pseudo-dice?, IEEE Access, 6, 22987-22992 (2018)
[10] François, M.; Grosges, T.; Barchiesi, D.; Erra, R., Pseudo-random number generator based on mixing of three chaotic maps, Commun. Nonlinear Sci. Numer. Simul., 19, 4, 887-895 (2014) · Zbl 1457.65005
[11] Ganz, R. E., The decimal expansion of π)is not statistically random, Exp. Math., 23, 2, 99-104 (2014) · Zbl 1294.62253
[12] Garg, P., Cryptanalysis of simplified data encryption standard using genetic algorithm, Am. J. Netw. Commun., 4, 3, 32 (2015)
[13] R. Gilad-Bachrach, N. Dowlin, K. Laine, K. Lauter, M. Naehrig, J. Wernsing, Cryptonets: applying neural networks to encrypted data with high throughput and accuracy, in: International Conference on Machine Learning, 2016, pp. 201-210.
[14] S.W. Golomb, et al., Shift Register Sequences, Aegean Park Press, 1967. · Zbl 0267.94022
[15] González, C.; Larrondo, H.; Rosso, O., Statistical complexity measure of pseudorandom bit generators, Physica A, 354, 281-300 (2005)
[16] Han, M.; Xi, J.; Xu, S.; Yin, F.-L., Prediction of chaotic time series based on the recurrent predictor neural network, IEEE Trans. Signal Process., 52, 12, 3409-3416 (2004) · Zbl 1373.62463
[17] M.C. Hao, U. Dayal, D.A. Keim, T. Schreck, Importance-Driven Visualization Layouts for Large Time Series Data, in: J.T. Stasko (Ed.), IEEE Symposium on Information Visualization (InfoVis 2005), Minneapolis, MN, USA, October 23-25, 2005, 203-210, ISBN 0-7803-9464-X, 2005.
[18] Harrower, M.; Brewer, C. A., ColorBrewer.org: an online tool for selecting colour schemes for maps, Cartogr. J., 40, 1, 27-37 (2003)
[19] H.C. Heien, M. Rahman, Revisiting the Digits of [pi] and Their Randomness (Ph.D. thesis), Minnesota State University, Mankato, 2005.
[20] D.D. Hosfelt, Automated detection and classification of cryptographic algorithms in binary programs through machine learning, CoRR abs/1503.01186, http://arxiv.org/abs/1503.01186.
[21] Hu, H.; Liu, L.; Ding, N., Pseudorandom sequence generator based on the Chen chaotic system, Comput. Phys. Commun., 184, 3, 765-768 (2013)
[22] Huang, A., Hacking the Xbox: An Introduction to Reverse Engineering (2003), No Starch Press: No Starch Press San Francisco
[23] A. Jäschke, F. Armknecht, Unsupervised Machine Learning on Encrypted Data, in: C. Cid, M.J. Jacobson Jr. (Eds.), Selected Areas in Cryptography - SAC 2018, 2019, pp. 453-478. · Zbl 1447.94046
[24] D. Knuth, The art of computer programming, vol. 2 (third ed.): Seminumerical Algorithms, Addison Wesley Longman Publishing Co., Inc., Boston, MA, USA, ISBN 0-201-89684-2, 1997. · Zbl 0895.68055
[25] Lamberti, P.; Martin, M.; Plastino, A.; Rosso, O., Intensive entropic non-triviality measure, Physica A, 334, 1, 119-131 (2004)
[26] P. L’Ecuyer, R. Simard, TestU01: A C Library for Empirical Testing of Random Number Generators, ACM Trans. Math. Softw. 33 (4) (2007) 22:1-22:40. · Zbl 1365.65008
[27] Leung, H.; Lo, T.; Wang, S., Prediction of noisy chaotic time series using an optimal radial basis function neural network, IEEE Trans. Neural Networks, 12, 5, 1163-1172 (2001)
[28] López-Ruiz, R.; Mancini, H.; Calbet, X., A statistical measure of complexity, Phys. Lett. A, 209, 5, 321-326 (1995)
[29] Luby, M.; Luby, M., Pseudorandomness and Cryptographic Applications, Princeton Computer Science Notes (1996), Princeton University Press: Princeton University Press Princeton · Zbl 0849.94017
[30] Machicao, J.; Bruno, O., Improving the pseudo-randomness properties of chaotic maps using deep-zoom, Chaos, 27, 53116 (2017) · Zbl 1452.65011
[31] J. Machicao, O.M. Bruno, M.S. Baptista, Zooming into chaos for a fast, light and reliable cryptosystem, 2020.
[32] Machicao, J.; Marco, A.; Bruno, O. M., Chaotic encryption method based on life-like cellular automata, Expert Syst. Appl., 39, 12626-12635 (2012)
[33] Markowsky, G., The sad history of random bits, J. Cyber Secur. Mobility, 3, 1-24 (2014)
[34] G. Marsaglia, The Marsaglia random number CDROM, with the DIEHARD battery of tests of randomness.http://www.stat.fsu.edu/pub/diehard, 1998.
[35] Matsumoto, M.; Nishimura, T., Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Trans. Model. Comput. Simul., 8, 3-30 (1998) · Zbl 0917.65005
[36] Metropolis, N.; Ulam, S., The Monte Carlo method, J. Am. Stat. Assoc., 44, 247, 335-341 (1949) · Zbl 0033.28807
[37] Micco, L. D.; Larrondo, H. A.; Plastino, A.; Rosso, O. A., Quantifiers for randomness of chaotic pseudo-random number generators, Philos. Trans. R. Soc. A, 367, 1901, 3281-3296 (2009) · Zbl 1185.37071
[38] MIT Student Information Processing Board (SIPB), One billion digits of π)https://stuff.mit.edu/afs/sipb/contrib/pi/, 2019.
[39] M.E. O’Neill, PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation, Tech. Rep. HMC-CS-2014-0905, Harvey Mudd College, Claremont, CA, 2014.
[40] Öztürk, I.; Kiliç, R., A novel method for producing pseudo random numbers from differential equation-based chaotic systems, Nonlinear Dyn., 80, 3, 1147-1157 (2015)
[41] Peinado, A.; Fúster-Sabater, A., Generation of pseudorandom binary sequences by means of linear feedback shift registers (LFSRs) with dynamic feedback, Math. Comput. Model., 57, 11-12, 2596-2604 (2013)
[42] Radwan, A. G.; AbdElHaleem, S. H.; Abd-El-Hafiz, S. K., Symmetric encryption algorithms using chaotic and non-chaotic generators: a review, J. Adv. Res., 7, 2, 193-208 (2016)
[43] Rukhin, A.; Soto, J.; Nechvatal, J.; Smid, M., NIST Special Publication 800-22: a statistical test suite for random number generator for criptographic applications (2001), National Institute of Standards and Technology: National Institute of Standards and Technology Gaithersburg, MD, USA, (Tech. Rep.)
[44] Skanderova, L.; Řehoř, A., Comparison of pseudorandom numbers generators and chaotic numbers generators used in differential evolution, (Zelinka, I.; Suganthan, P. N.; Chen, G.; Snasel, V.; Abraham, A.; Rössler, O., Nostradamus 2014: Prediction, Modeling and Analysis of Complex Systems (2014), Springer International Publishing: Springer International Publishing Cham), 111-121 · Zbl 1317.65139
[45] Spillman, R.; Janssen, M.; Nelson, B.; Kepner, M., Use of a genetic algorithm in the cryptanalysis of simple substitution ciphers, Cryptologia, 17, 1, 31-44 (1993)
[46] G.L. Steele, D. Lea, C.H. Flood, Fast splittable pseudorandom number generators, in: Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications - OOPSLA’ 14, ACM Press, 453-472, 2014.
[47] I. Vattulainen, K. Kankaala, J. Saarinen, T. Ala-Nissila, A comparative study of some pseudorandom number generators, Computer Physics Communications 86 (3) (1995) 209-226, ISSN 0010-4655. · Zbl 0873.65004
[48] J. Walker, A pseudorandom number sequence test program.http://www.fourmilab.ch/random/, 1998.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.