Sign in to follow this  
Followers 0
czardas

Random Timing

29 posts in this topic

For $i = 0 to 100
    $a = TimerInit()
    $n = Random(1, 1000000, 1)
    ConsoleWrite(TimerDiff($a) &@CRLF)
Next

I ran the above test and got strange results. I generally got two different values and occasionally a few odd discrepancies. I was wondering if you get the same results, and what might cause this, apart from memory usage discrepancies. Why do I get two distinct values? :graduated:

Share this post


Link to post
Share on other sites



Doesn't Random() use time or something as seed? Time changes so it sorta makes sense. I guess. I don't know.

Intel Q9550 @ 3.4 GHz

0.017769831885343
0.002108285138939
0.002108285138939
0.001807101547662
0.001807101547662
0.001807101547662
0.001807101547662
0.001505917956385
0.001505917956385
0.001807101547662
0.001505917956385
0.001807101547662
0.001505917956385
0.001505917956385
0.001807101547662
0.001505917956385
0.001807101547662
0.001505917956385
0.001505917956385
0.001807101547662
0.001505917956385
0.001807101547662
0.001505917956385
0.001505917956385
0.00572248823426301
0.001505917956385
0.001505917956385
0.001807101547662
0.001505917956385
0.001505917956385
0.001807101547662
0.001807101547662
0.001807101547662
0.001505917956385
0.001807101547662
0.001807101547662
0.001505917956385
0.001505917956385
0.001505917956385
0.001807101547662
0.001807101547662
0.001807101547662
0.001505917956385
0.001505917956385
0.001807101547662
0.001505917956385
0.001505917956385
0.001505917956385
0.001505917956385
0.002108285138939
0.001807101547662
0.001505917956385
0.001505917956385
0.001505917956385
0.001505917956385
0.001505917956385
0.001807101547662
0.001505917956385
0.001807101547662
0.001807101547662
0.001505917956385
0.001807101547662
0.001505917956385
0.001505917956385
0.001505917956385
0.001505917956385
0.001807101547662
0.001505917956385
0.001807101547662
0.001505917956385
0.001807101547662
0.001505917956385
0.001505917956385
0.001505917956385
0.001807101547662
0.001807101547662
0.001807101547662
0.001505917956385
0.001807101547662
0.001505917956385
0.001807101547662
0.001505917956385
0.001505917956385
0.001807101547662
0.001505917956385
0.001807101547662
0.001505917956385
0.001505917956385
0.001807101547662
0.001807101547662
0.001807101547662
0.001807101547662
0.001505917956385
0.001505917956385
0.001807101547662
0.001807101547662
0.001505917956385
0.001505917956385
0.001505917956385
0.001807101547662
0.001505917956385

Share this post


Link to post
Share on other sites

#3 ·  Posted (edited)

There are four fuctions in the For loop that may be responsible, but I was assuming (although probably the wrong assumption) that the Random function would have the most influence. I find it quite confusing.

Edit

It also appears that it makes no difference what maximum random value I use, however the two values do not always appear in the same order (even when using the same max random value). I'm happy with it anyway, even though I don't understand it. :graduated:

Edited by czardas

Share this post


Link to post
Share on other sites

Wait, remove the Random and the difference is still there. I think this is just the normal AutoIt fluctuation thingy. It happens no matter what you do, it's probably some caching mechanism. It's noticeable everywhere.

Also, I've a feeling that Random() is pretty much the same now as earlier, look at F_Random in script_math.cpp and mt19937ar-cok.cpp in the released source.

Share this post


Link to post
Share on other sites

I don't think you get usable results if you put TimerInit(), TimerDiff(), and especially ConsoleWrite() inside the loop. Take the time outside the loop, and repeat that loop to look for variation:

For $a = 1 To 10
    $iTimer = TimerInit()
    For $i = 1 To 100
        $n = Random(1, 1000000, 1)
    Next
    ConsoleWrite(TimerDiff($iTimer) & @CRLF)
Next

ConsoleWrite(@LF & "----------------------" & @LF & @LF)

For $a = 1 To 10
    $iTimer = TimerInit()
    For $i = 1 To 100
        ;$n = Random(1, 1000000, 1)
    Next
    ConsoleWrite(TimerDiff($iTimer) & @CRLF)
Next

Results:

>Running:(3.3.6.1):C:\Program Files\AutoIt3\autoit3.exe "C:\Temp\Test1.au3"    
0.18493970602409
0.168177799133689
0.156234940474278
0.266304795721244
0.152673035260068
0.152463511423938
0.18242541999053
0.152952400374908
0.153860336998138
0.154349225949108

----------------------

0.00928889006843048
0.00880000111746046
0.00886984239617046
0.00866031856004045
0.00859047728133045
0.00859047728133045
0.00873015983875046
0.00873015983875046
0.00873015983875046
0.00859047728133045
+>10:42:07 AutoIT3.exe ended.rc:0

:graduated:


Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law

Share this post


Link to post
Share on other sites

I see what you're saying PsaltyDS. The reason for the test was because I was wondering if the Random function took longer to execute with larger numbers. So I tried stepping up in larger increments.

For $a = 100000 To 1000000 Step 100000
    $iTimer = TimerInit()
    For $i = 1 To 100
        $n = Random(1, $a, 1)
    Next
    ConsoleWrite(TimerDiff($iTimer) & @CRLF)
Next

ConsoleWrite(@LF & "----------------------" & @LF & @LF)

For $a = 100000 To 1000000 Step 100000
    $iTimer = TimerInit()
    For $i = 1 To 100
        ;$n = Random(1, $a, 1)
    Next
    ConsoleWrite(TimerDiff($iTimer) & @CRLF)
Next

Results

0.244723840599853
0.140520652764527
0.138844462075487
0.138565096960647
0.139123827190327
0.165384147985289
0.138844462075487
0.136888906271607
0.137727001616127
0.212596852393251

----------------------

0.0100571441342405
0.00949841390456049
0.00866031856004045
0.00866031856004045
0.00838095344520044
0.00838095344520044
0.00838095344520044
0.0469333392931224
0.0100571441342405
0.00838095344520044
+>17:11:55 AutoIT3.exe ended.rc:0

It seems that the time taken is not proportional to the size of the upper limit. That surprises me a little. :graduated:

Share this post


Link to post
Share on other sites

Deep in its little C++ heart, the randomizing function is probably working on an INT32 type regardless, and then just scaling it once to fit your desired limit.

:graduated:


Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law

Share this post


Link to post
Share on other sites

The version of the Mersenne Twister that I've seen always generates a 32 bit integer and then casts/truncates it when you need other types.

Share this post


Link to post
Share on other sites

#12 ·  Posted (edited)

I just hit the limit by changing the first line of the code to:

For $a = 10^307 To 10^308 Step 10^307

The results are about the same, but if you use any larger powers of 10, it freaks out. :graduated:

Thanks Richard, I'll try and get my head around that twister. It looks complicated.

Edited by czardas

Share this post


Link to post
Share on other sites

#13 ·  Posted (edited)

I have done some timing test in the past. ... But I'm not really getting what it is that your wondering about. (or try to test.)

Anyway. Some code I racked up that shows a way to get a relative precise indication on the relative speeds between commands.

Example output: (on P4, 2.4GHz)

$iQPF = 3579545
$iTimeLoop = 16384
[0] Base/TimerInit(0) = 9
[0] Base/TimerInit(0) = 0.00251428603356013
[0] ... = 0.00446984183744023
[1] TimerDiff(0) = 22
[1] TimerDiff(0) = 0.00614603252648032
[0] ... = 0.00726349298584038
[2] Random() = 14
[2] Random() = 0.0039111116077602
[0] ... = 0.00698412787100036
[3] Random(1, 0x7FFFFFFF, 1) = 26
[3] Random(1, 0x7FFFFFFF, 1) = 0.00726349298584038
[0] ... = 0.00949841390456049

#include <Timers.au3>
test()
Func test()
    Local $iQPF = __Timer_QueryPerformanceFrequency()
    Local $iTimeLoop = Int(2 ^ 14)
    Local $iMin = 0, $1 = 0, $2 = 0, $3 = 0
    _DebugOut('$iQPF', $iQPF) ;### Debug DebugOut.
    _DebugOut('$iTimeLoop', $iTimeLoop) ;### Debug DebugOut.

    $iMin = 0x7FFFFFFF
    For $i = 1 To $iTimeLoop
        $3 = time0($1, $2)
        If $iMin > $3 Then $iMin = $3
    Next
    _DebugOut('[0] Base/TimerInit(0)', $iMin) ;### Debug DebugOut.
    _DebugOut('[0] Base/TimerInit(0)', _Msec($iMin)) ;### Debug DebugOut.
    $3 = TimerInit()
    $3 = TimerDiff($3)
    _DebugOut('[0] ...', $3) ;### Debug DebugOut.

    $iMin = 0x7FFFFFFF
    For $i = 1 To $iTimeLoop
        $3 = time1($1, $2)
        If $iMin > $3 Then $iMin = $3
    Next
    _DebugOut('[1] TimerDiff(0)', $iMin) ;### Debug DebugOut.
    _DebugOut('[1] TimerDiff(0)', _Msec($iMin)) ;### Debug DebugOut.
    $3 = TimerInit()
    TimerInit()
    $3 = TimerDiff($3)
    _DebugOut('[0] ...', $3) ;### Debug DebugOut.

    $iMin = 0x7FFFFFFF
    For $i = 1 To $iTimeLoop
        $3 = time2($1, $2)
        If $iMin > $3 Then $iMin = $3
    Next
    _DebugOut('[2] Random()', $iMin) ;### Debug DebugOut.
    _DebugOut('[2] Random()', _Msec($iMin)) ;### Debug DebugOut.
    $3 = TimerInit()
    Random()
    $3 = TimerDiff($3)
    _DebugOut('[0] ...', $3) ;### Debug DebugOut.

    $iMin = 0x7FFFFFFF
    For $i = 1 To $iTimeLoop
        $3 = time3($1, $2)
        If $iMin > $3 Then $iMin = $3
    Next
    _DebugOut('[3] Random(1, 0x7FFFFFFF, 1)', $iMin) ;### Debug DebugOut.
    _DebugOut('[3] Random(1, 0x7FFFFFFF, 1)', _Msec($iMin)) ;### Debug DebugOut.
    $3 = TimerInit()
    Random(1, 0x7FFFFFFF, 1)
    $3 = TimerDiff($3)
    _DebugOut('[0] ...', $3) ;### Debug DebugOut.

EndFunc
Func _DebugOut($1='', $2='')
    If $2 Or Not IsString($2) Then $1 &= ' = ' & String($2)
    ConsoleWrite($1 & @CRLF)
EndFunc
Func _Msec($i1)
    Return $i1/__Timer_QueryPerformanceFrequency() * 1000
EndFunc
Func time0(ByRef $1, ByRef $2)
    $1 = TimerInit()
    $2 = TimerInit()
    Return $2-$1
EndFunc
Func time1(ByRef $1, ByRef $2)
    $1 = TimerInit()
    TimerDiff(0)
    $2 = TimerInit()
    Return $2-$1
EndFunc
Func time2(ByRef $1, ByRef $2)
    $1 = TimerInit()
    Random()
    $2 = TimerInit()
    Return $2-$1
EndFunc
Func time3(ByRef $1, ByRef $2)
    $1 = TimerInit()
    Random(1, 0x7FFFFFFF, 1)
    $2 = TimerInit()
    Return $2-$1
EndFunc
Exit

I'm not sure, but those INT output values should/could be more or less the same on other systems.

Not trying to hijack your topic czardas. But ... if I could get some output dumps from others I would appreciate it.

Edit1: (wraithdu output. Tnx)

"[0] Base/TimerInit(0)" ... Ai, was afraid of that. (not the fixed bug part, but the zero value itself. Got to think about that some more.

+ fixed ignoring number zero in _debugout().

Edit2: Will/should probably open new topic on this. ...

Edited by MvGulik

"Straight_and_Crooked_Thinking" : A "classic guide to ferreting out untruths, half-truths, and other distortions of facts in political and social discussions."
"The Secrets of Quantum Physics" : New and excellent 2 part documentary on Quantum Physics by Jim Al-Khalili. (Dec 2014)

"Believing what you know ain't so" ...

Knock Knock ...
 

Share this post


Link to post
Share on other sites

#14 ·  Posted (edited)

Couple runs:

Intel Quad Q9550 @ 2.83 GHz

Win7 Ultimate x64

$iQPF = 2766972
$iTimeLoop = 16384
[0] Base/TimerInit(0)
[0] Base/TimerInit(0)
[0] ... = 0.00108421769356538
[1] TimerDiff(0) = 1
[1] TimerDiff(0) = 0.000361405897855128
[0] ... = 0.00108421769356538
[2] Random() = 1
[2] Random() = 0.000361405897855128
[0] ... = 0.00144562359142051
[3] Random(1, 0x7FFFFFFF, 1) = 3
[3] Random(1, 0x7FFFFFFF, 1) = 0.00108421769356538
[0] ... = 0.00216843538713077

$iQPF = 2766972
$iTimeLoop = 16384
[0] Base/TimerInit(0)
[0] Base/TimerInit(0)
[0] ... = 0.00108421769356538
[1] TimerDiff(0) = 1
[1] TimerDiff(0) = 0.000361405897855128
[0] ... = 0.00108421769356538
[2] Random() = 1
[2] Random() = 0.000361405897855128
[0] ... = 0.00108421769356538
[3] Random(1, 0x7FFFFFFF, 1) = 3
[3] Random(1, 0x7FFFFFFF, 1) = 0.00108421769356538
[0] ... = 0.00216843538713077
Edited by wraithdu

Share this post


Link to post
Share on other sites

#15 ·  Posted (edited)

I'm not really getting what it is that your wondering about. (or try to test.)

I'm trying to determine the value of Timing Attacks with programs that incorporate the Random function, and whether it has any effect or not. Edited by czardas

Share this post


Link to post
Share on other sites

Ok, not at home at cryptography. But using Autoit for that might not be the best choice.

Especially after seeing wraithdu output dump -> very low value. Making additional math with them riddled with a high uncertenties in those cases, if I'm correct.


"Straight_and_Crooked_Thinking" : A "classic guide to ferreting out untruths, half-truths, and other distortions of facts in political and social discussions."
"The Secrets of Quantum Physics" : New and excellent 2 part documentary on Quantum Physics by Jim Al-Khalili. (Dec 2014)

"Believing what you know ain't so" ...

Knock Knock ...
 

Share this post


Link to post
Share on other sites

#17 ·  Posted (edited)

It's a bit over my head too. It sounds like consistant timing with varied input is good. On the other hand, inconsistant timing with the same input would probably do the same trick. I'm baffled by it. :graduated:

Edited by czardas

Share this post


Link to post
Share on other sites

MvGulik, I meant to post this earlier:

AuthenticAMD 2.812 GHz

XP Pro x86

1st Run

$iQPF = 3579545
$iTimeLoop = 16384
[0] Base/TimerInit(0) = 6
[0] Base/TimerInit(0) = 0.00167619068904009
[0] ... = 0.00279365114840015
[1] TimerDiff(0) = 14
[1] TimerDiff(0) = 0.0039111116077602
[0] ... = 0.00530793718196028
[2] Random() = 7
[2] Random() = 0.0019555558038801
[0] ... = 0.00307301626324016
[3] Random(1, 0x7FFFFFFF, 1) = 10
[3] Random(1, 0x7FFFFFFF, 1) = 0.00279365114840015
[0] ... = 0.00419047672260022

2nd Run

$iQPF = 3579545
$iTimeLoop = 16384
[0] Base/TimerInit(0) = 6
[0] Base/TimerInit(0) = 0.00167619068904009
[0] ... = 0.00307301626324016
[1] TimerDiff(0) = 14
[1] TimerDiff(0) = 0.0039111116077602
[0] ... = 0.00502857206712026
[2] Random() = 7
[2] Random() = 0.0019555558038801
[0] ... = 0.00335238137808018
[3] Random(1, 0x7FFFFFFF, 1) = 10
[3] Random(1, 0x7FFFFFFF, 1) = 0.00279365114840015
[0] ... = 0.00419047672260022

Share this post


Link to post
Share on other sites

Anyone know why the QPF gets bigger with more speed?

$iQPF = 3320234
$iTimeLoop = 16384
[0] Base/TimerInit(0) = 0
[0] Base/TimerInit(0) = 0
[0] ... = 0.000903550773831001
[1] TimerDiff(0) = 1
[1] TimerDiff(0) = 0.000301183591277
[0] ... = 0.000903550773831001
[2] Random() = 1
[2] Random() = 0.000301183591277
[0] ... = 0.001204734365108
[3] Random(1, 0x7FFFFFFF, 1) = 3
[3] Random(1, 0x7FFFFFFF, 1) = 0.000903550773831001
[0] ... = 0.002108285138939

Share this post


Link to post
Share on other sites

#20 ·  Posted (edited)

Thanks for additional data dumps.

Anyone know why the QPF gets bigger with more speed?

Not to sure what you mean.

But ... after getting wraithdu results, I did a little digging around, as his result added some big ???.

As far I can tell.

The QPF (or QueryPerformanceFrequency for short) is CPU-type linked. And is not directly related to the CPU speed. Its a general measure unit that gives one count for every X clock cycles. How many clock cycles a single QPF is, is something that is determent by the CPU makers.

(This account for the biggest problem when timing something faster than a single QPF count. Which happened on wraithdu system. Returning zero on the first test case/loop. (see that is also the case on your system.)

There are some additional notes flouting around about QPF pittfalls in relation to CPU's that support power saving modes. But that is also in contradiction to what the MSDN page says about it, QPF being a constant. (?)

---

(ps: No additional data dumps needed anymore. At least not for me.)

Edited by MvGulik

"Straight_and_Crooked_Thinking" : A "classic guide to ferreting out untruths, half-truths, and other distortions of facts in political and social discussions."
"The Secrets of Quantum Physics" : New and excellent 2 part documentary on Quantum Physics by Jim Al-Khalili. (Dec 2014)

"Believing what you know ain't so" ...

Knock Knock ...
 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0