Collecting entropy from device_attach() times.

[Mariusz Gromada]

W dniu 2012-09-25 11:05, Ben Laurie pisze:

>> I created dummy driver which was registering three dummy drivers, so it
>> was provoking three device_attach() calls on every kldload. Mariusz
>> verified the observations and there was no correlation between the
>> times.
>
> Sorry to those that are bored, but ... what was the methodology?
>


Ok, finally I had enough time to write something more.

Try not to think about this data as a sequence of numbers a1, a2, ..., 
an, but rather as a sequence of random variables X(w,1), X(w,2), 
...,X(w,n) – in general X(w,t) where 'w' is something similar to random 
event (something unpredictable) and 't' is time. In mathematics X(w,t) 
is called a stochastic process (or random process / time series). In our 
case 'w' may be interpreted as a particular machine, 't' will simply 
identify the sequence number of each device attach, then X(w,t) will be 
entropy suspected part of the final device attach time (measured in some 
units).

Our task is to check if there are any autocorrelations in the X(w,t) 
process, which means checking if there are any dependencies between 
random variables X(w,t1) and X(w,t2) where t1 < t2.

It is possible to do this using some formal statistical test (i.e.: 
Durbin–Watson test, Autocorrelation Random Number Test).

I received form Pawel one portion of real data - 2081 observations 
coming from just one realization of the process. Checking 
autocorrelations requires data from many realizations of the process: in 
this case Nx2081, where each realization from 1 to N should start from 
the same beginning.

But for dummy data we did something (With Pawel) for X(w,1), X(w,2), 
X(w,3) - there were generated many realizations. Finally no 
autocorrelations were observed.

Summarizing:
1. We proved that data comes from uniform distribution (KS test)
2. We proved that there was no autocorrelation in the stochastic process 
consisted of 3 subsequent device attaches
3. We did graphical analysis, where typical noise was identified for 
much more than 3 device attaches.

What else could be done:
1. Proving that there is no autocorrelations between X(w,t1) and X(w,t2) 
where t1 < t2.
2. Confirming results for some other architectures and devices, which 
means confirming results for X(w1,t), X(w2, t), ...

Regards,
Mariusz