Tuesday, March 9, 2010

Episode #85: Coincidence & Randomness

Ed Uses His Rod Serling Voice:

You unlock this door with the key of imagination. Beyond it is another dimension - a dimension of sound, a dimension of sight, a dimension of mind. You're moving into a land of both shadow and substance, of things and ideas. You've just crossed over into... the Command Line Zone.

It's funny how these little coincidences happen, almost as though they are stitched into the very fabric of the universe. Two completely unrelated people working on very different projects happen to identify a command line need at about exactly the same time. Each, unknowing of the other, sends in a question to the unassuming band of shell freaks at the CLKF blog.

The scene opens with an e-mail from Éireann, a kind reader who wanted to run a command at some random time within the next 24 hours. The command in question should send an e-mail blast to a group of recipients around the globe.

Less than 48 hours earlier, a friend of the blog had submitted an eerily similar question. In designing a Capture the Flag game, he needed to run a script every hour, but at a random time within that hour.

Was this a mere coincidence? Was it a sinister plot for world domination? Or, has someone's imagination and nostalgia for 1960's TV shows just gotten out of hand?

Our story gets even weirder. The CtF game master was surprised because his command to generate random timing fu was simply not behaving randomly enough. He had tried:

C:\> for /L %i in (1,0,2) do @cmd.exe /v:on /c for /F %f in ('set /a !random!%3600') do
@echo %f & ping -n 3 127.0.0.1 >nul
2905
2912
2918
2925
2932
2941

As a first step in creating the random delay timer, the CtF designer was trying to spit out a stream of pseudo-random numbers by invoking a FOR loop to run continuously, launching a cmd.exe to activate delayed environment variable expansion, kicking off a FOR /F loop that used a little shell math to create a random number between 0 and 3599 by applying modulo arithmetic (!random!%3600), and then introducing a 2-second delay by pinging localhost thrice. But those numbers on the output look decidely unrandom.

When I received his e-mail, I had a pretty good suspicion of what the culprit was. My friend had been stomping on his own entropy by launching the cmd.exe to turn on delayed variable expansion within his FOR /L loop for continuous execution. And, it gets even worse. To perform the "set /a" command inside of the single quotes ('), a FOR /F loop will launch another cmd.exe. So, each iteration of the FOR /F loop launches a cmd.exe, which uses a FOR /F loop to launch yet another cmd.exe to process the 'set /a' command. It's a double entropy stomper. But, even launching one cmd.exe can cause problems for your randomness. Consider this simplified example:

C:\> for /L %i in (1,0,2) do @cmd.exe /v:on /c set /a !random!%10
66666699999999999999999999999999999999333333333333333333333333333333336666666666
66666666666666666666669999999999999999999999999999999933333333333333333333333333
33333366666666666666666666666666666666999999999999999999999999999999992222

Those digits between one and ten change only every second or so. I immediately set out to create a fix. We've got to swap our invocation of delayed variable expansion (cmd.exe /v:on /c) and our FOR /L loop to make it run continuously. Otherwise, the constant launching of a shell dips back into our same old weak entropy pool each time it is invoked, which doesn't change fast enough on a Windows machine to give us satisfactory results. Let's check out the swap:
C:\> cmd.exe /v:on /c for /L %i in (1,0,2) do @set /a !random!%10
53443765137306108347857462987392509842433990177450065079938404591379539993991668
15958655065543980786504403929102313264126903224822440676335255418412842151910989

This result is much nicer, and significantly faster as we don't have to continuously launch a shell for each random number.

Now, let's apply it to the task at hand... running a script once per hour, at a random interval sometime in that hour. First off, we'll create a little dummy script, which will simply print out the date and time it was executed. Simply append to this script any other command(s) you'd want to run:

C:\> echo @echo ^%date^% ^%time^%> script.bat

Instead of running the script at a random time within each hour, I'm going to speed things up by running it at a random time each minute. The following command achieves our goal:

C:\> cmd.exe /v:on /c "for /L %i in (1,0,2) do @(set /a delay=!random!%60+1+1>nul
& set /a finish=60+1+1-!delay!>nul & echo script to run after !delay! pings
and then pause for !finish! pings & ping -n !delay! 127.0.0.1>nul &
script.bat & ping -n !finish! 127.0.0.1>nul)"
script to run after 21 pings and then pause for 41 pings
Fri 02/26/2010 13:42:21.89
script to run after 20 pings and then pause for 42 pings
Fri 02/26/2010 13:43:21.04
script to run after 28 pings and then pause for 34 pings
Fri 02/26/2010 13:44:29.20
script to run after 51 pings and then pause for 11 pings
Fri 02/26/2010 13:45:52.38

If you want to run the script randomly timed every hour, replace the two occurrences of 60 above with 3600 (60 seconds times 60 minutes). If you want to run at a random time once every 24 hour interval, replace 60 with 86400 (60 sec times 60 min times 24 hours).

So, what is this monstrosity of applied technology doing? First, we invoke cmd.exe to perform delayed variable expansion (cmd.exe /v:on /c) so we can let our variables change value as the command runs. Then, we start a FOR /L loop to run forever, counting between 1 and 2 in steps of zero. At each iteration of the loop, we turn off display of command (@). That's routine. Here's where things get more interesting.

We now use the set /a command to do some math, having it set the variable called "delay" to a random number modulo 60 (!random!%60). That'll give us a nice number between 0 and 59. But, why do I add 1 to it twice? Well, I'm going to later introduce delays using pings. To introduce an N second delay, I have to ping myself N+1 times. And, I'll introduce two delays: one before the script runs, and one after the script runs. See, we don't want to just run the command multiple times with a random delay between each run. If we did that, we might have the command run 18 times in one minute, just because our randomness returned a bunch of small numbers. Instead, we want it to run 18 times in 18 minutes, but at a random time within each minute. Therefore, we'll need to have a delay up front, followed by the script execution, followed by a delay for the rest of that minute. Each of those two delays will be implemented with pings, which each consuming 0 seconds for their first ping. I have to add one twice here to account for the two sets of pings gobbling up their first ping in almost no time.

After calculating my delay, I then calculate a finish number of pings by taking 60, adding 2, and subtracting !delay!. With all my math done, I simply display the number of pings before the script will run and after it runs. Finally, I then run the first pings, then the script, and the remaining pings. After all that, we loop.

You can put pretty much anything you want in script.bat. Unfortunately, sending e-mail at the command line is something that cmd.exe itself is not capable of doing using only built-in tools. You can run "start mailto:EmailAddress" at the command line, which invokes Outlook Express to send e-mail. But, it would require a user to hit the Send button. There are other tools for sending e-mail at the command line that rely on third party commands, described here.

Our random timing script invoker above is ugly, complex, but very effective. Such are the lessons in for cmd.exe in... the Command Line Zone.

Hal has all the time in the world

I can do a loop that's essentially the bash version of Ed's idea:

$ while :; do delay=$(($RANDOM % 60)); sleep $delay; date; sleep $((60 - $delay)); done
Tue Mar 2 11:07:55 PST 2010
Tue Mar 2 11:08:02 PST 2010
Tue Mar 2 11:09:43 PST 2010
...

Here I'm setting $delay to a random value between 0 and 59 then sleeping for that amount of time. I'm calling the date command in the middle of the loop so that you can more easily see the random time intervals, but you could substitute any commands here that you want. Finally, we sleep for the remainder of the time interval and then start the loop all over again.

This loop works fine for one-minute intervals and even one-hour intervals, but $RANDOM only ranges from 0 to 32767, so I'd have to do two calculations to cover an entire day-- pick a random hour between 0 and 24 for example, then pick a random time within that hour. Alternatively, we could just use the trick from Episode 58 to generate a larger random number:

while :; do 
delay=$((`head /dev/urandom | tr -dc 0-9 | sed s/^0*// | cut -c1-8` % 86400))
sleep $delay
/path/to/your/command
sleep $((86400 - $delay))
done

I've modified the solution from Episode 58 slightly, including a sed command to strip off any leading zeroes from the result. Otherwise the random value we calculate may be interpreted as an octal number, which causes problems if there are any 8's or 9's elsewhere in the number. Let me demonstrate what I mean with a quick example using a hard-coded value that has a leading zero:

$ delay=$((09999999 % 86400))
bash: 09999999: value too great for base (error token is "09999999")

Actually, aside from the type of random loops we're doing here, this kind of random delay is also useful for scheduled tasks like cron jobs. For example, in larger enterprises you might have hundreds or thousands of machines that all need to do the same task at a regular interval. Often this task involves accessing some central server-- grabbing a config file or downloading virus updates for example. If a thousand machines all hit the server at exactly the same moment, you've got a big problem. So staggering the start times of these jobs across your enterprise by introducing a random delay is helpful. You could create a little shell script that just sleeps for a random time and then introduce it at the front of all your cron jobs like so:

0 * * * * /usr/local/bin/randsleeper; /path/to/regular/cronjob

The cron job will fire every hour, the "randsleeper" script will sleep for part of that time, and then your regular cron job will execute. This is a well-known old sysadmin trick.

Well that's my weekly effort to serve man. Let's see what Tim's got cooking.

Tim[e] is on my side

My loop is pretty much a clone of Hal's, and the explanation is very similar:

PS C:\> while (1) { $delay = (New-Object Random).next(1,60); Start-Sleep $delay;
Get-Date; Start-Sleep (60 - $delay) }

Saturday, February 27, 2010 9:55:45 PM
Saturday, February 27, 2010 9:56:47 PM
Saturday, February 27, 2010 9:58:05 PM
...

The variable $delay is set to a random number between 1 and 59, and unlike Ed, we have good entropy. To get a random number we need to use the .Net System.Random class. However, there is a bit of goofyness, the lower bound is inclusive, while the upper bound is exclusive. So if we wanted to get a random number between 1 and 6, like on a die, we would use a lower bound of 1 and an upper bound of 7. Why did they do it that way? I don't know, and I been asking that since the beginning of the Microsoft shells.

Once we have the delay, we sleep for that amount of time. After waking up from our nap, the date and time are displayed. Of course any command (or commands) can be used. Finally, we sleep for the balance of the minute. The infinite While loop ensures that the process starts over again.

To change our loop to execute a command every hour, all that needs to be done is change 60 to 3600. If we wanted it to execute daily we would change the upper bound to 86400, and we don't have Hal's problem with big numbers. We can use really big numbers, up to 2,147,483,647. If the command was to run after 2.1 billion seconds it would be the year 2078, long after all the computers we are using are dead.

Finally, Ed mentioned sending an email at the random interval. Sending email from the Windows shells is a pain. It isn't possible with cmd, but we can do it with PowerShell by using the .Net framework. The long version of the commands looks like this.

PS C:\> $emailFrom = "tim@domain.com"
PS C:\> $emailTo = "ed@domain.com"
PS C:\> $subject = "Mail"
PS C:\> $body = "How's it going?"
PS C:\> $smtpServer = "smtp.domain.com"
PS C:\> $smtp = new-object Net.Mail.SmtpClient($smtpServer)
PS C:\> $smtp.Send($emailFrom, $emailTo, $subject, $body)

We can condense it to one line for use in our fu.

PS C:\> (New-object Net.Mail.SmtpClient("smtp.domain.com")).Send("tim@domain.com",
"ed@domain.com", "Mail", "How's it going?")


If we wanted to send an email once every hour at a random time the command here is how we would do it.

PS C:\> while (1) { $delay = (New-Object Random).next(1,60); Start-Sleep $delay;
(New-object Net.Mail.SmtpClient("smtp.domain.com")).Send("tim@domain.com",
"ed@domain.com", "Mail", "How's it going?"); Start-Sleep (60 - $delay) }

That wraps it up for now, see you next week. Start-Sleep 604800