"Научный аспект №2-2019" - Технические науки

Quality of generation of pseudorandom numbers in the systems of simulation modeling OpenGPSS, GPSS\World and AnyLogic

Нұрғамиден Нұрбек Ерденұлы – магистрант кафедры Информационно-вычислительных систем Карагандинского экономического университета Казпотребсоюза.

Тен Татьяна Леонидовна – доктор технических наук, профессор кафедры Информационно-вычислительных систем Карагандинского экономического университета Казпотребсоюза.

Смирнов Леонид Сергеевич – магистрант, кафедры Информационно-вычислительных систем Карагандинского экономического университета Казпотребсоюза.

Аннотация: Статья посвящена качеству определения генерации псевдослучайных последовательностей в различных системах моделирования, моделирующего посредством графического статистического теста Diehard. Который поможет объяснить, какая из систем генерации предоставляет собой лучшую систему среди проверяемых в сравнительном анализе. Один из современных методов анализа операции сложных систем - использование симуляционного моделирования. Для выполнения повторяющегося компьютерного стохастического моделирования используются события, полученные от псевдогенераторов случайных чисел. Следовательно, качество псевдослучайных последовательностей имеет большое значение при получении достоверных результатов.

Abstract: Article is devoted to determination quality of generation of the pseudorandom sequences in the different systems of simulation modeling through the graphic statistical Diehard test. Which will help to explain what of the systems of generation provides itself(himself) the best system among tested in the comparative analysis. One of the modern methods of the analysis of operation of difficult systems is use of simulation modeling. For carrying out the repeating computer running of stochastic models the events received from pseudorandom number generators are used. Therefore, the quality of the pseudorandom sequences is of great importance when obtaining authentic results.

Ключевые слова: Тестирование Diehard, генерация псевдослучайных чисел, симуляцонное моделирование, OpenGPSS,\World, AnyLogic.

Keywords: Testing of Diehard, generation of pseudorandom numbers, simulation modeling, OpenGPSS, GPSS\World, AnyLogic.

In article the modern systems of simulation modeling OpenGPSS, GPSS World and AnyLogic which work with the discrete models are considered. The systems of simulation support operation with a large number of probable distributions - from Bernoulli to Veybul: 29 distributions in OpenGPSS, in the help of AnyLogic are described 29 distributions, 24 distributions in GPSS World. All types of distributions are built on uniform distribution which quality is estimated further.

ы вд л ч йны л д в льн й

For today there are many graphic and statistical tests for check of the pseudorandom sequences. Among statistical tests the following is widely used: NIST, TEST-U01, CRYPT-X, The pLab Project, Diehard, ENT similar. In operation application of a test set of Diehard (the author of George Marsaglia) for three systems of simulation modeling is considered.

For each environment of simulation own small program in the appropriate language (GPSS or Java) which allows to receive big selection of pseudorandom numbers with uniform distribution was written. Further, by means of the software package of Diehard which binary files are taken from the website http://stat.fsu.edu/pub/diehard/ the analysis of the sequences of numbers for each system of simulation separately is made.

н л б н г б д в н я

For all practical experiments one computer of the class Intel Core Duo with the processor of 2,1 GHz and a random access memory of 2 GB, the Windows XP SP3 operating system was used. Experiments were put on the systems of simulation of upcoming versions: OpenGPSS 1.2.1.0 (1.2.2.0), GPSS World 5.2.2. and AnyLogic 6.4.1. All experiments were made over the pseudorandom number generator No. 1, with the following initial offsets: 300 (OpenGPSS), 200 (GPSS World) and 100 (AnyLogic).

б ни в д н я выч л льн г эк м н в м м д л в н я

For the system of simulation GPSS World in case of small quantity of numbers (up to 4 million numbers) the Diehard program gives an error message: "run-time error F6501: Read (file name) - end of file encountered". It occurs on the test No. 2 "Swaps which are crossed" though in the text of the test it is written that it processes the sequence from one million 32-bit numbers twice.

Unfortunately, in the binary file the simulation environments since the read and write only of the text file is supported do not allow to generate directly data. We can receive the finite file only for two steps: the first - creation of the text file from 4 million lines, in every line one number which is written by the text, and the second - the translation of the text file in binary.

The normal program of generation of the sequence in GPSS World in the text file at first even for 40 thousand numbers lasts 2 hours. And only after modification of the program on GPSS, generation of such file occurs in 2 minutes. The matter is that the unit of opening of the OPEN file long works. Therefore, it is not necessary to cause it every time for each transacts, and it is necessary to transfer to a separate hour GENERATE, OPEN, ADVANCE, CLOSE and TERMINATE segment thereby having caused once for all program.

For the system of simulation OpenGPSS the text file is received in 30 minutes.

The intermediate text file occupies 46 MB. Then 3 minutes are spent for conversion in the necessary binary file of 15 MB in size by means of the VisualBasic-scenario.

Each test on an output creates special number of p-value of an interval [0, 1]. Results of the made experiments are given in table 1. Quantity of the generated numbers for each system of simulation - 4 million. In the table "+" means that a test is passed (if p-value belongs to a segment [0,025; 0,975]), and "-" - a test is not passed.

Table 1. Quantity of the generated numbers for each system of simulation.

	Test	OpenGPSS		GPSS World		AnyLogic
	Birthday Spacings	0,359018	+	1	-	0,431397	+
	Overlapping Permutations	1,000000	-	0,060425	+	0,008494	-
	Ranks of matrices	0,950574/ 0,991835/ 0,999961	+/-/-	0,413445/ 0,536567/ 0,097624	+/+/+	0,382749/ 0,342521/ 0,249165	+/+/+
	The bitstream test	0,805974*	+	1,000000	-	0,482539	+
	Monkey tests	1,000000	-	0,585412*	+	0,494274*	+
	Count the 1's	1,000000	-	1,000000/ 0,495902*	-/+	0,558042*/ 0,587793	+/+
	Parking Lot Test	0,979816	-	0,751581	+	0,221977	+
	Minimum Distance Test	0,992231	-	0,545258	+	0,506258	+
	Random Spheres Test	0,173505	+	0,162508	+	0,27834	+
0	The Squeeze Test	1,000000	-	0,475504	+	0,985307	-
1	Overlapping Sums Test	0,919356	+	0,681207	+	0,899422	+
2	Runs Test	0,312858	+	0,548301*	+	0,549636*	+
3	The Craps Test (for no of wins/ for throws/ game)	0,406554/ 1,000000	/-	0,214467/ 0,807587	/+	0,343878/ 0,396355	/+

All thirteen tests of this packet were completely used. But of course passing (or not passings) is not enough tests to accept or reject a hypothesis of randomness of a data stream. Tests of Diehard create on an output of number of p-value which are uniformly distributed in the range of [0, 1] if an input flow of numbers really accidental. We check our "zero" hypothesis about an input flow through the statistical significance by Pearson's criterion (criterion "Chi-square"). Pearson's criterion requires many implementations, and tests of everything 13 therefore we use all p-value values from the resultant file, their about 240 there. Results of calculations for criterion are shown in table 2.

Table 2. Check of a statistical hypothesis about randomness of a data stream.

Pseudorandom number generator (PNG)	The number of the passed tests from Diehard set	Criterion Pearson ("Chi-square")		Analysis of result
Pseudorandom number generator (PNG)	The number of the passed tests from Diehard set	Received	Tabular	Analysis of result
OpenGPSS	5	90	36,2	Accidental cannot read a flow
GPSS World	10	29,45	36,2	Accidental can read a flow
AnyLogic	11	28,17	36,2	Accidental can read a flow

Ул чш н Ч в м м д л в н я OpenGPSS

The first option of improving of PNG is use of the built-in PNG from Oracle DBMS. Operation with a system package of dbms_random consists of the job initial offset for PNG and receiving the following number. At the same time the packet which is built already in Oracle is widely used that is big advantage. Here it is necessary to refer impossibility to receive the current offset to shortcomings.

Independent implementation on the given formalizations belongs to other methods of improving of PNG:

the linear congruent X_n+imethod = (aX_n + c) mod m;
square congruent X_n+i method = (dX_n²+aX_n+c) of mod m;
the generator on the basis of combining by addition on mod 232 two generators: the delaying Fibonacci generator Xn = Хn-99 Хn-33 mod 232 and the generator on the basis of the work with transfer of Yn = 30903 Yn-1 carry mod 216;
generator of the M-sequences;
Mersen's curl.

At the same time modifications of the linear congruent method are possible:

the expanded congruent generator - Hp = 213 (Hp-1 + Hp-2 + Hp-3) mod (232 - 5);
algorithm "Marsaglia-Multicarry" (George Marsagliya);
algorithm "xor-shift" (George Marsagliya);
algorithm of Bluema-Bluema-Shuba;
the generator on the basis of the work with transfer
Хn * (2111111111 Hp-4 + 1492 Hp-3 + 1778 Hp-2 4 5115 Hp-1) carry mod 232;
the generator on the basis of the work with transfer of Xn = a Xn-1 to mod 232 sap.

For improving of quality of the generated sequence it is decided to use the linear congruent method with different values a, m and with for the widespread libraries and programming languages given in table 3.

Table 3. Examples of the linear congruent method.

Source	m	a	c	Bits
ANSI С: Open Watcom, Digital Mars, Metroweiks, IBM VisualAge C/C++	2³²	1103515245	12345	16..30
Apple CarbonLib	2³¹-1	16807	0	0..31
Borland C/C++	2³²	22695477	1	0..30
Borland Delphi, Virtual Pascal	2³²	134775813	1	0..31
glibc (using in GCC)	2³²	1103515245	12345	0..30
GNU Compiler Collection	2³²	69069	5	16..30
LC53 from the Forth programming language	2³²-5	2³²- 333333333	0	0..31
Microsoft Visual Basic (version 6 below)	2²⁴	1140671485	12820163	023
Microsoft Visual/Quick C/C++	2³²	214013	2531011	16..30
Donald Knuth’s MMIX	2^M	6364136223846793005	1442695040888963407	0..63
MS Fortran	2³¹-l	48271	0	0..31
Numerical Recipes	2³²	1664525	1013904223	0..31
Random class in Java API	2⁴⁸	25214903917	11	16..47
RtlUniform from Native API	2³¹-l	2147483629	2147483587	0..31
VAX's MTH\$RANDOM (old version of glibc library)	2³²	69069	1	0..31

After changeover of an algorithm of generation of random numbers, we receive the following running of the battery of tests of Diehard (table 4) in the new version of system of simulation OpenGPSS 1.2.2.0.

Table 4. The reduced results of passing of tests of DIEHARD.

PNG	test No. from the Diehard battery													In total it is passed
PNG	1	2	3	4	5	6	7	8	9	10	11	12	13	In total it is passed
1. ANSI С	-	+	-/-/-	-	-	+	-	-	-	-	-	+	-/-	3
2. Apple CarbonLib	-	+	+/+/+	-	+	+	+	+	+	+	+	+	+/+	11
3. Borland C/C++	-	+	-/-/-	-	+	+	-	-	-	-	-	+	-/-	4
4. Borland Delphi, Virtual Pascal	-	+	+/+/-	-	+	+	-	-	-	-	-	+	-/-	4
5. glibc	-	+	-/-/-	-	+	+	-	-	-	-	-	+	-/-	4
6. GNU Compiler Collection	-	-	-/-/-	-	+	+	-	-	-	-	-	+	-/-	2
7. LC53	-	+	+/+/+	-	+	+	-	-	-	-	-	+	-/-	5
8. Microsoft Visual Basic	!	-	-/-/-	-	-	+	-	-	-	-	-	+	-/-	2
9. Microsoft Visual/Quick C/C++	-	-	-/-/-	-	+	-	-	-	-	-	-	+	-/-	2
10.MMDC Дональда Кнута	+	+	-/-/+	-	+	+	-	-	-	-	-	+	-/-	6
11. MS Fortran	+	+	+/+/+	-	+	+	+	+	+	+	+	+	+/+	12
12. Numerical Recipes	-	+	+/+/-	-	+	+	-	-	-	-	-	+	-/-	4
13. Random class in Java API	-	-	-/-/-	-	+	-	-	-	-	-	-	+	-/-	2
14. RtlUniform from Native API	-	-	+/+/-	-	-	-	-	-	-	-	+	-	+/+	2
15. VAX's MTH\$ RANDOM	-	+	+/+/-	-	+	+	-	-	-	-	-	+	-/-	2
16. Пакет dbms.random из Oracle XE	-	+	+/+/+	+	+	+	+	+	+	+	+	+	+/+	12

From the table it is visible that is most perspective to use algorithms "MS Fortran" and the built-in packet of dbms random. For them Pearson's criterion is also considered as it was already described earlier, and results are skidded in table 1.

Further all are implemented 15 PNG, at the same time the sensor "MS Fortran" is by default used. The generator from a packet of dbms_random is decided not to be used because of impossibility of its operation with several sensors at the same time. Now the user can make the PNG setup in the OpenGPSS system on the Setup page in the browser, having selected one of 15 generators given in table 1 of the list.

Table 5. Check of a statistical hypothesis about randomness of a data stream.

Pseudorandom number generator (PNG)	The number of the passed tests from Diehard set	Criterion Pearson ("Chi-square")		Analysis of result
Pseudorandom number generator (PNG)	The number of the passed tests from Diehard set	Received	Tabular	Analysis of result
OpenGPSS 1.2.1.0	5	90,00	36,2	Accidental cannot read a flow
OpenGPSS 1.2.2.0 MS Fortran	12	29,46	36,2	Accidental can read a flow
OpenGPSS 1.2.2.0 dbms_random	12	12,06	36,2	Accidental can read a flow

Список литературы

Тен Т.Л., Бейсенби М.А., Когай Г.Д., Парароцкая Н.Н. Модели и методы криптографической защиты информации распределенных сетей в усло-виях детерминированного хаоса. – Монография - М.: Издательская Тор-говая Компания «Наука-Бизнес-Паритет», 2014.– 213 с.
Харин Ю.С., Петлицкий А. И., Ярмола А.Н. Криптографические генераторы случайных и псевдослучайных последовательностей и методы их статистического тестирования. // Материалы XI Междунар. конф. «Комплексная защита информации». – Минск: Амалфея, 2007. – С. 226-230.
Иванов М.А., Чугунков И.В. Теория, применение и оценка качества генераторов псевдослучайных последовательностей. – М.: КУДИЦ-ОБРАЗ, 1990. – 240 с.
Тайлак Б.Е., Бейсенби М.А. Генерация псевдослучайных чисел на основе свойств хаотических систем. // Материалы III межд. научно-практической конф. «Информатизация общества». –Астана: ЕНУ имени Л.Н. Гумилева, 2012. – С. 112-127.
Герасименко В.А. Защита информации в автоматизированных системах об-работки данных. – М.: Энергоатомиздат, 1994. – 400 с.
Нечаев В.И. Элементы криптографии. Основы теории защиты информации. – М.: Высшая школа, 1999. – 109 с.
Бияшев Р.Г. Разработка и исследование методов сквозного повышения достоверности в системах обмена данными распределенных АСУ: дисс. докт. тех. наук: 05.13.06: защищена 09.10. 1985: утв. 28.03.1986 / Бияшев Рустем Гакашевич. – М., 1985. – 328 с.
Архангельская А. В., Запечников С. В. Характеристика и области эффективного применения методов поточного шифрования для защиты трафика в телекоммуникационных системах // Информационное противодействие угрозам терроризма: науч.-практ. журнал. –2005. –№4. –С.196-199.