A funny race-condition based RNG...

[Chris M. Thomasson]

For fun, I was thinking about the effect of certain race-conditions, and
decided to see what happens if I made a random bit generator based on
multi-threading race-conditions alone. Here is a little program I wrote
that generates random 1024-bit numbers, and a busted fetch-and-add impl...:
____________________________________________
#include <thread>
#include <atomic>
#include <cstdio>

#define THREADS 7

static std::atomic<unsigned int> g_racer(0);


void racer(unsigned int n)
{
for (unsigned int i = 0; i < n; ++i)
{
// Race infested fetch-and-add op
unsigned int r = g_racer.load(std::memory_order_relaxed);
r = r + 1;
g_racer.store(r, std::memory_order_relaxed);
}
}


unsigned int get_rand_bit(unsigned int n)
{
std::thread t[THREADS];

for (unsigned int i = 0; i < THREADS; ++i)
{
t[i] = std::thread(racer, n);
}

for (unsigned int i = 0; i < THREADS; ++i)
{
t[i].join();
}

unsigned int r = g_racer.load(std::memory_order_relaxed);

return r & 1;
}


void display_rand_bits(unsigned int n)
{
std::printf("%u Race-Condition Bits\n"
"____________________________________________\n",
n
);

for (unsigned int i = 0; i < n; ++i)
{
unsigned int r = get_rand_bit(1000000);
std::printf("%u", r);
if (! ((i + 1) % 64)) std::printf("\n");
std::this_thread::yield();
}

std::printf("\n____________________________________________\n");
}


int main()
{
display_rand_bits(1024);

return 0;
}
____________________________________________


Does this program work for you? If so, can you please show me some of
the outputs you get? Thanks. FWIW, I notice I seem to get better results
when the system is busy doing something else...



FWIW, here are a couple of outputs I get:


1024 Race-Condition Bits
____________________________________________
0111111111110111000011101111001100101011010111111011101001100010
0010100110111111010110101100100111010101110111000110110000111110
0110011111101100001010000101111110001101000110101000010101000001
1110010101011100111101100001000001101011111100101100101110001101
0100011000000110011011101100011000000001110110011111010001001000
1001111011111100000011100011101000011101010010111111011110010001
1101101100010011110001110010010111000111110101110110100000001101
0100111110100101100101000010011010100011011010001010110001101011
1001110001000111011100001101011001100101100010010011000011001010
1001000101000110011100000111010011010111001110010101000011000001
0001111100000011100000001100100111000000010100101110000111001011
0000101001100010011010010110001000011111110000101100110100101000
1100101111010011000010100101010000000011000000000011101001111001
1001001011110101001000110010010101010111011010000000000110100110
0110100110001000111011101000110001011010011110000111010111111111
1000010111000011011010111000111000011000001010101111100110111000

____________________________________________



1024 Race-Condition Bits
____________________________________________
1101011000111010011001110000000110000000111011100110010111110011
0001110010100010111101101100101001100001100001111110110011111101
1000111100010001100001111011010100111000000101101101110101010111
0111001011000111101101001110010111010000111110100111000110001111
0110011111111011111011000100010010110000100100111110001010100000
0110101101100101110100000111001000110101110000010100001000100000
1000111100101111100110101001000010010011011100001010000101110011
0001000001000010010110111101000011000010110001010101111110010011
0111011000111000111011111000110100001101110000010100010101110001
0001111110110000110111001010111111101111010011001111100111001101
1111000000100000110000001100001000111011000010101111110010000001
0000101101101100100010010001000101011111000011001101000110010111
0110000100010111111101001110111101111100101000111101101101111000
0100100100111011001000010100111100011111100000101001110011010100
1010011000101010101010111010000110100101110001100010010110101000
0111011011000100111000101010101111010110110010101111010110000000

____________________________________________



1024 Race-Condition Bits
____________________________________________
1011101010101011101010100000011110001010011010000001110101101000
1000110111100111100000110111000011101000000111001010111111111000
0000100110110010111110100111110001110010110100111000011110000101
1110110010111001100010000100011011001111101010010111011111000010
0001010010100010010110110100010000110110101010110100101001111010
0101011101111010101100101111110110000011101001110010110100111010
1000101011111111100011111110001010010000101110011111101001100010
1110111110001011000011000110100110110101100110000001101100001000
0101110100001001010111110001110110110000110101101101100101110101
0011101000110010001000010000111110011100000011010101001110010011
0100010000101000101001000000100110100001000000111100111010101001
0100101011110010010101011010111100000011100111010100110001101111
1100010000010000001001110010110100110110110001010100011100011101
1110110101111100101011001111100111011001111110111100011101100011
0111100000111010101110111110001000100111101010010100011110101100
0000011110101000110010110001000101010111100110001011011000100011

____________________________________________


;^D

[Brett Dong]

On 9/3/16 9:56 AM, Chris M. Thomasson wrote:
> For fun, I was thinking about the effect of certain race-conditions, and
> decided to see what happens if I made a random bit generator based on
> multi-threading race-conditions alone. Here is a little program I wrote
> that generates random 1024-bit numbers, and a busted fetch-and-add impl...:
> ____________________________________________

On my machine:

1024 Race-Condition Bits
____________________________________________
1101110000110101000000001010000101011100001010001100011110001111
1011000100101010001000101001100100011001110111100110010010000111
0011101011000010010100001011010101111001111101100110101000110100
1110101011001101100001010111011000101001100110001001110101001100
1000000100011010100111011111100000010000111011100011110111110110
0101110001111010010011010101001000111111110010101100110111000011
1001101111000010000101010010111101110101111100001011110101111011
0011010101010000011010010110100001100110111010100010011101000011
1000011001011101100101001000100100001000001111111010001101010000
1011000000111011011111111111110010110110011000010001111011010000
1000010111110011001111010111111011000010100100011100100111110010
0011100001011001101110010010101010101111100010110100001111000011
0110111101001010101100011110001011011101110110000101100110111001
1010011010110101101011110010100011001001100110000110000010000000
1011001010100000100010000011101010111000011100100011010001011011
0100111101101110100010110010011111110101100000011011100100111011

____________________________________________

[Brett Dong]

I modified the implementation a little bit:

1. Create the same amount of threads to the number of physical threads
local hardware actually has. This makes the program run much faster on
my dual core 4-thread CPU.

2. Measure the time elapsed to calculate how many bits are generated per
second.

______________________________________________________________________
#include <iostream>
#include <thread>
#include <atomic>
#include <time.h>

#ifdef __MACH__
#include <sys/time.h>
/* clock_gettime is not implemented on OSX
http://stackoverflow.com/questions/5167269/clock-gettime-alternative-in-mac-os-x
*/
#define CLOCK_REALTIME 0
int clock_gettime(int /*clk_id*/, timespec* t)
{
timeval now;
int rv = gettimeofday(&now, NULL);
if (rv)
return rv;
t->tv_sec = now.tv_sec;
t->tv_nsec = now.tv_usec * 1000;
return 0;
}
#endif

unsigned int threads_count;

static std::atomic<unsigned int> g_racer(0);

void racer(unsigned int n)
{
for (unsigned int i = 0; i < n; ++i)
{
// Race infested fetch-and-add op
unsigned int r = g_racer.load(std::memory_order_relaxed);
r = r + 1;
g_racer.store(r, std::memory_order_relaxed);
}
}

unsigned int get_rand_bit(unsigned int n)
{

std::thread *t = new std::thread[threads_count];
for (unsigned int i = 0; i < threads_count; ++i)

t[i] = std::thread(racer, n);

for (unsigned int i = 0; i < threads_count; ++i)
t[i].join();
delete[] t;
return (g_racer.load(std::memory_order_relaxed)) & 1;
}

void display_rand_bits(unsigned int n)
{
// std::clock() gives CPU time, not wall clock time
timespec start, finish;
std::cout << n << " Race-Condition Bits" << std::endl;
std::cout << "____________________________________________" <<
std::endl;
clock_gettime(CLOCK_REALTIME, &start);

for (unsigned int i = 0; i < n; ++i)
{

std::cout << get_rand_bit(1000000);
if (! ((i + 1) % 64)) std::cout << std::endl;
std::this_thread::yield();
}

clock_gettime(CLOCK_REALTIME, &finish);
std::cout << "____________________________________________" <<
std::endl;
double elapsed = (finish.tv_sec - start.tv_sec);
elapsed += (finish.tv_nsec - start.tv_nsec) / 1000000000.0;
std::cout << "averagely " << n * 1.0 / elapsed << " bits per
second" << std::endl;
}

int main()
{
threads_count = std::thread::hardware_concurrency();
std::cout << "Using " << threads_count << " threads" << std::endl;
display_rand_bits(1024);
return 0;
}
____________________________________________________________

My result:

Using 4 threads
1024 Race-Condition Bits
____________________________________________
0101010000111100110100001000111001110100111000100011110001000110
1100111100001111000100011011110100011100000101011100010111010011
1011010001100110111110111110111111000101011000000110101000010010
0110010000011000101000011010111100111100010010010011111110010110
0001010001110101101001000110101001010011100011100001011111010000
1110000010110011100000100010000111101111011001101011000101101011
0110110011111101100000001111010001010101100001101101000111010011
0100110110011110111101001100000000011101011110101011110001001000
1001101111111100010111000101101010100101011101111100100110100111
0110001101000101001101100001110110001011000010110000010100001011
0010010101001011101101101000100011110011000011110000011100111001
1000111110000010110011110011010111100101110110011011001110100101
1111001011001000110111010101000110000001100111110101100000111010
1001101101001001001111101100010000000001000011100110100110100000
0100100110110000010100010001000101001111111001010110110111000110
0111110110110101111101000101000001101010111111000000000001101101
____________________________________________
averagely 153.529 bits per second

[Öö Tiib]

On Saturday, 3 September 2016 04:56:08 UTC+3, Chris M. Thomasson wrote:
> For fun, I was thinking about the effect of certain race-conditions, and
> decided to see what happens if I made a random bit generator based on
> multi-threading race-conditions alone.

Note that people may miss the fun part and consider something
like that seriously. The '/dev/random' on Unix or 'CryptGenRandom' on
Windows likely work orders of magnitude faster.

[Chris M. Thomasson]

On 9/3/2016 1:17 AM, Brett Dong wrote:
> I modified the implementation a little bit:
>
> 1. Create the same amount of threads to the number of physical threads
> local hardware actually has. This makes the program run much faster on
> my dual core 4-thread CPU.
>
> 2. Measure the time elapsed to calculate how many bits are generated per
> second.

Thank you. :^)

So far this is modeling a fubar impl of fetch-and-add. I want to see if
I can get some detectable pattern differences in the bits if I model,
say exchange or compare-and-swap, and compare them to each other.
Humm... It would be really neat to take an educated guess at what atomic
primitive might of caused a race condition based on modeling its output
as a stream of bits. Might be fun, or a wild goose chase! Humm...

Thanks again! :^D

[Chris M. Thomasson]

Right on. I should have made that point clearer. Now, I did generate
some files based on multiple runs of the data and ran some *tests on
them. They did not do to all that great most of the time. However, when
the system was under load, doing something else, the results were much
better. It like you can see the load of a system, through the patterns a
race-condition generates. Almost like you can see how the system was
scheduling threads.

Humm... Could be interesting.

____
[*]:FWIW, here is a program I used to run some of the tests:

http://www.fourmilab.ch/random

It works pretty darn good.

[Chris M. Thomasson]

On 9/4/2016 1:53 PM, Chris M. Thomasson wrote:
> On 9/3/2016 1:17 AM, Brett Dong wrote:
>> I modified the implementation a little bit:
>>
>> 1. Create the same amount of threads to the number of physical threads
>> local hardware actually has. This makes the program run much faster on
>> my dual core 4-thread CPU.
>>
>> 2. Measure the time elapsed to calculate how many bits are generated per
>> second.
>
> Thank you. :^)
>
> So far this is modeling a fubar impl of fetch-and-add. I want to see if
> I can get some detectable pattern differences in the bits if I model,
> say exchange or compare-and-swap, and compare them to each other.
> Humm... It would be really neat to take an educated guess at what atomic
> primitive might of caused a race condition based on modeling its output
> as a stream of bits. Might be fun, or a wild goose chase! Humm...

The funny thing is that compare and swap might do a little better even
in fubar impl... lol. At least it will try to compare before it destroys
data-structure integrity?

;^)

I need to try this out.

[Chris M. Thomasson]

On 9/3/2016 5:24 AM, Öö Tiib wrote:

So far, AFAICT, there just may be a rather interesting property wrt this
"scheme". I am having some trouble understanding how there can be any
sort of "concrete set period" where the race-condition based "random"
numbers will "exactly repeat themselves", as in PRNGS. It sure seems to
want to be, irrational.

Humm...


Any thoughts?

[Öö Tiib]

Computer is specially designed to achieve repeatability of its work and
so your program causes seemingly random results because of other
I/O or programs consuming resources of computer when you run the
program (you move mouse, click keyboard, some packet is exchanged
with net, some multimedia is decoded by other program etc.).

[Chris M. Thomasson]

Right. I was wondering if there can ever be a set period, of perfect
repetitions wrt the output of the race-infested based fetch-and-add
scheme. Keep in mind that a simple "mouse move" can cause the system to
act in a sort of "unpredictable" nature wrt current load, and scheduler
state, so to speak. Humm... Imagine running this on n computers in a PC
bang, and dynamically comparing all of the results:

https://en.wikipedia.org/wiki/PC_bang

Does this sound like total non-sense, or just a little!?

;^o

[Öö Tiib]

Exactly, I wanted to say that its unpredictability is thanks to entropy
from I/O and other processes. It can be perfect cycle only when those
random factors are missing or are not random for some reason.

> Humm... Imagine running this on n computers in a PC
> bang, and dynamically comparing all of the results:
>
> https://en.wikipedia.org/wiki/PC_bang
>
> Does this sound like total non-sense, or just a little!?
>
> ;^o

You are interested in data science? Data science makes sense even when
data that is analyzed is bordering on meaningless. The skills can be
very useful. Otherwise I think that there are plenty of data easily
available whose analyzing can be more rewarding.

[Chris M. Thomasson]

FWIW, I am very interested in trying to find hidden meaning/patterns in
data, more than ever now because I am developing a fractal cipher and
need to improve my skills wrt performing cryptanalysis on its
ciphertexts. I have some ideas that may make cracking it easier, by I
need to hone my skills. Here is my google+ page:

https://plus.google.com/101799841244447089430

And an online example of one of my Fractal ciphers:

http://funwithfractals.atspace.cc/ffe

Here is some ciphertext generated with the default key:
____________________________________________________
0.15884937881165292 0.34886779843675064
0.11167540272577696 0.21975019886225045

C0 C9 EE 4F 08 1E 1A C3 04 2C B0 52 14 C8 BB 01 AE 98 FE 64 0A C1 B4 D3
63 02 96 17 AE 68 DA 9C F5 DD 33 50 0B F8 2B B1 E3 09 39 39 E0 A8 AC 33
98 CA 3A 82 D0 5F BF DD 9A 0C 8D 97 AE 0A 78 12 D4 FF 25 93 E5 FF 82 51
32 69 CE 23 80 FF 61 2B 5C 8A E7 25 44 DB 80 6B 10 DC A2 13 A5 DF A6 9C
40 16 37 78 CB FD C6 46 7C F5 EA 09 CA 04 09 8B 6F 39 94 38 5D ED 83 B7
7F 2D B9 0B 0F BD 60 86 69 44 4C 5B 3F F4 DB 31 BE B8 04 25 F1 74 29 25
03 7B E3 68 1B 44 5B 2B 1C 22 D7 FA 3A BE 47 04 52 94 D6
____________________________________________________

You can copy-and-paste the data between the lines into the ciphertext
box, and hit the decrypt button to see the message.

You should get the following in the Plaintext box:
____________________________________________________
This cipher is highly experimental, and is not ready to be used as a
real cipher until proper review has deemed it worthy to protect a human
life, or animal... ;^)
____________________________________________________

> Otherwise I think that there are plenty of data easily
> available whose analyzing can be more rewarding.

You have a very good point there. :^)

[Chris M. Thomasson]

This top-post is just to get the post over on sci.crypt. Maybe, there
just might be something to this...

https://groups.google.com/d/topic/comp.lang.c++/7u_rLgQe86k/discussion
(read all correspondence if interested...)

BTW, can you run this using c++11?

__________________________________________________________

[Chris M. Thomasson]

sorry about the other extraneous post on comp.lang.c++.