Archive for August 2011

GNU screen / Bash: start commands in interactive sessions

I run nearly everything from the terminal, including my mail client (mutt), music player (cmus), custom simulation software (Python/Matlab/C), and some hacked together daemon-like mail and server scripts—my browser (Firefox) is the only always-on GUI application. Thus, GNU screen is an essential tool in my workflow, since it allows for easy multiplexing and detaching of sessions.

One of its many features is the ability to start multiple sessions and automatically run commands in each of them. This isn't necessary for my server and workstation, since I just run screen persistently. However, my MacBook Pro is a different story, and not having to start up each program individually is a great convenience. The canonical way to do so is through creation of an alternate screenrc

# $HOME/.screen/startuprc
source $HOME/.screenrc
screen -t cmus 0 cmus
screen -t mutt 1 mutt
screen -t bash 2
screen -t custom_title 9 custom_script.sh

and to then invoke screen -c ~/.screen/startuprc.

This works great with stable programs like cmus and mutt, but I oftentimes need to restart my hacked together scripts, maybe after a crash or if I just want to tweak the code. Unfortunately, as set up, once an automatically started program finishes running, screen (correctly) exits the session. Starting up a new session each time can get a bit old.

The easiest solution I found was to create a custom Bash rcfile for each program, which would first source ~/.bashrc and then run the command at hand (e.g. custom_script.sh). This way, an interactive Bash session remains after exiting the program.

# $HOME/.screen/startuprc
source $HOME/.screenrc
screen -t cmus 0 bash --rcfile $HOME/.screen/cmus_rcfile
screen -t mutt 1 bash --rcfile $HOME/.screen/mutt_rcfile
screen -t bash 2
screen -t custom_title 9 bash --rcfile $HOME/.screen/custom_script_rcfile

This is almost sufficient, but there's still one quirk left. Because Bash is running the script from an rcfile, it doesn't store the command in its history buffer. A minor thing, to be sure, but it means I can't use the four-keystroke sequence ctrl-C, <up>, <enter> to restart programs. Luckily, Bash provides a means of deliberately inserting commands into history without running them, so the simple addition of history -s "command" to the appropriate rcfile fixes that:

# $HOME/.screen/custom_script_rcfile
custom_script.sh
history -s "custom_script.sh"

And that's it! I'd love to hear if anyone has come up with a more elegant solution. For now though, the above provides everything I need, and is relatively simple to setup. Happy hacking!

Mindhack – Mental math pseudo-random number generators

Human minds are great for many things, but picking random numbers is not one of them1. At one point, these sorts of cognitive biases were used to support arguments for determinism, to the point where some experimental psychologists even undertook to train subjects to produce statistically random-looking output2. Determinism is beyond the scope of this post, but in keeping with the spirit of the last, we'll be looking at simple mathematical tricks to generate pseudo-random numbers.

DISCLAIMER: These techniques are not suitable for practical applications, and especially not any serious cryptography. I am not an expert in the field, and have just been playing with these ideas in my spare time.

Background

Computer programs often need quasi-random numbers for everything from scientific simulations to cryptography; unfortunately, true randomness is difficult to extract, and usually limited in quantity. However, not all applications require the same level of randomness: cryptography needs to protect against a dedicated human adversary, and so has the greatest need for numbers being actually random3, while scientific simulations only require that the numbers look indistinguishable from random ones by certain statistical tests, but need lots of them as quickly as possible, even if they aren't quite as "random".

To fill those niches, mathematicians and computer scientists have developed a wide range of different pseudo random number generators (PRNG), each with their pluses and minuses. What exactly are PRNGs? Simply put, they're sets of mathematical rules for deterministically producing random-looking output. Because they are deterministic, they require an initial seed number, and always produce the same output for the same seed4. However, to most humans who aren't statisticians or cryptanalysts, they're sufficiently good.

Here, we present three simple PRNG algorithms, implementations of the Lehmer PRNG5, that you can carry around in the back of your head for when you need to wow an audience with your ability to randomise, . For the record, I am not to be held liable if you lose all of your friends, stutter at interviews, or get hit by a bus because you're too busy updating your internal PRNG.

Lehmer PRNG

First some (skippable) maths: given a large prime p, a multiplier m, and a seed number x_0, a Lehmer PRNG can be defined by the recursive function x_{n+1} = m \cdot x_n \mod p 6. By a judicious choice of m, the series \{x_i\} does not repeat for a long time, ideally going through all of the integers from 1 to p-1 7. The output stream is then some function of the current state x_i. For computer programs p, m are usually chosen for ease of binary computation. Furthermore, computers can handle far bigger numbers than most of us mere humans can—the historically popular choice8 2^{31} -1 is a lovely number, but I'd hate to be trying to divide by it in my head. Luckily, there are lots of primes, and good choices make it far easier to do modular arithmetic in decimal notation, reducing everything to basic addition/multiplication on the digits. Furthermore, instead of taking the bit parity or least/most significant bit, we instead use the unit's digit for the output stream.

One pair choice is p=59, m=6 9. Because 60 \equiv 1 \mod 59, each iteration is a simple matter of multiplying the ones digit by 6 and adding the tens digit. To illustrate, a sequence starting from 17 would continue 43, 22, 14, 25, 32, 15, 31, 9, 54, 29,..., and taking just the unit's digit, that turns into 3, 2, 4, 5, 2, 5, 1, 9, 4, 9, which looks pretty random. Naturally, since the modulus is only 59, the sequence repeats itself every 58 iterations. Also, the numbers 9 and 0 are slightly less well-represented in the stream than the others. In most everyday contexts neither would be a problem—unless your friends have a habit of forcing you to spit out hundreds of random numbers and then running statistical analysis10, and if that's the case, I suggest you find new friends. However, there are other, slightly harder to compute pairs if you want a bit more.

Next up is p=101, m=50. Because p=101, this construction has the advantage that the sequence goes from 1 to 100, making the distribution of the output stream uniform over 1 to 10 and providing a longer period. The choice of multiplier also simplifies computation: if the current state x_i is even, the next number x_{i+1} = 101 - \frac{x_i}{2}, and if odd, x_{i+1} = 50 - \frac{x_i-1}{2}. Not as nice as the previous example, but still not bad.

If you have far too much time on your hands, you might consider an even larger prime to increase the period. For example, the pair p=1999, m=20. Unlike the previous two examples, the period of this Lehmer PRNG isn't actually the full 1998, but rather "only" 999. While another choice of multiplier would give a better answer, 20 has the advantage of making computing far simpler. Besides, it's fairly likely that you'll make a math error before getting to 999 that'll put you in the other group of 999 anyways. For the calculation, first break up x_i = 100 a_i + b_i, where $a_i, b_i$ are two digit numbers. Then x_{i+1} = 20\cdot b_i + a_i. Or equivalently, take the smallest two digits, multiply them by 2 and shift them to the left one place, and then add the larger two digits. Some mental gymnastics required, but still do-able.

Visual analysis of (p=1999, m=20)

Visual analysis of (p=1999, m=20). Bitmap image generated by linking pixel brightness to the values of output stream. 9 corresponds to white, 0 to black, and shades of grey to everything in between.

And of course, there are an infinite number of primes, so if none of the above suits your fancy, pick another. For ease of computation, I've found it best to choose primes close to k \cdot 10^n, because with those you can simplify the arithmetic as we've done above. However, the sky's the limit.

Seeding your internal PRNG

No, I'm not talking metaphorically (though the referenced article does propose a good idea). Now that you have an internal PRNG, you'll have to start worrying about the initial values. Luckily, unlike a computer, you have the entire world around you, and there are lots of options. Maybe look at the seconds hand on a clock, count the number of clouds in the sky, or just throw some dice. Just add the values to the current state, and voila, you've jumped to a completely different section in the output stream. This is especially suggested if you use the (1999,20) Lehmer PRNG, because otherwise you'll always be stuck on only 999 of the possible states.

Indeed, for those of you who aren't happy with the idea of trying to forever keep a 2-4 digit number in your head, you can just use these methods as transformations of common numbers, a substitution cipher for numbers to make them seem more random. Just think of the date/time whenever someone asks you for a random number, use it as your current state, and give the next iteration to as many digits as required. Won't quite be random, but it's probably still more than enough. Happy number crunching!


As an aside, some parapsychologists (both cranks and more reputable researchers, like the Global Consciousness Project) believe that it's possible for people to mentally influence random numbers through quantum effects. I'm not going give my opinion on the validity of those claims, but if you use these PRNGs, because it's completely deterministic, you're safe from their influence!

  1. Wagenaar, W. A. Generation of random sequences by human subjects: A critical survey of literature. Psychological Bulletin, 77, 65-72 (1972) (URI).
  2. Neuringer, A. Can People Behave "Randomly?": The Role of Feedback. Journal of Experimental Psychology, 115, 62-75 (1986).
  3. For crypto, either true random numbers from an external source or specialised cryptographically secure PRNGs are needed. Cryptographically secure PRNG algorithms tend to be far too complicated for mental math, though I was really intrigued by Blum Blum Shub.
  4. That PRNGs always produce the same output for the same seed is exploited by stream ciphers for encryption.
  5. I had wanted to do a Linear Feedback Shift Register as well, but unfortunately those don't work well in base 10, since 10 isn't prime.
  6. I'm simplifying the maths deliberately; Lehmer PRNGs are actually a slightly larger class of methods.
  7. m needs to have high multiplicative order modulo p, and \{x_i\} = \{i\in \mathbb{R}: 1\le i \le p-1\} when p is a primitive root.
  8. Park, S.K. & Miller, K.W. Random number generators: good ones are hard to find. Comm. of the ACM 31, 1192-1201 (1998) (URI).
  9. Thanks to an online post a while back by the late Professor Marsaglia. Unfortunately, I can't seem to readily find the reference anymore. Edit: found by courtesy of Josh Jordan.
  10. It's actually extremely easy to cryptanalyse Lehmer PRNGs, given the right tools, which is why they shouldn't be used for anything secure.

A simple Chrome extension to remove external URL mangling by Facebook

Update 2012-12-09: Facebook changed their URI mangling code, so this probably won't work as written anymore. However, a similar scheme should still work if you take the time to read the FB source code to figure out how to remove the new mangling code. (I no longer actively use FB, so I haven't updated the extension).

One of the thing's that's been irritating me lately about Facebook is it's habit of mangling the URLs of all links going away from the site. The status bar displays the correct URL, for instance

http://www.xkcd.com/

but upon actually clicking the link, some clever javascript substitutes

http://www.facebook.com/l.php?u=http%3A%2F%2Fwww.xkcd.com%2F&h=IAQCKSgbY

which is on Facebook's server, but then immediately redirects the user to XKCD. Facebook is thus able to track the links clicked, which presumably lets them better personalise the News Feed content.

This shouldn't surprise anyone, as most (if not all) of the major Internet players do some sort of click tracking, and Facebook in particular is well known for its stance on privacy. I'm not too bothered about it from a privacy standpoint, as I choose to give away a lot more personal information to Facebook anyways. Indeed, other net giants Google and Yahoo use a similar technique for all of their search results1, and Bing is smart enough to track clicks without resorting to link mangling. Click tracking is an integral part of online advertising, and since I'm using free services, I won't fault a profit-making company for employing it.

However, the difference is that the Facebook's links don't work properly when copied and pasted from one browser instance to another2. They instead send you to a redirection page requiring a manual click through, which is all right every so often but irritating in repetition.

Facebook Redirection Page

Facebook Redirection Page

Luckily, modern browsers come with a wide array of tools, and in this post, I'll be using a simple Chrome extension3 to remove the link mangling, allowing me to copy and paste my links in peace. It also has the side effect of possibly keeping Facebook from tracking my external clicks, but that's another matter entirely4

I should warn you at this point that there will be some minimal amount of coding involved, but if you are using multiple browser instances, than I'll assume you're up to the task. First, you'll need to create a folder to contain the extension files, say FacebookLinkDeMangler. In that folder, create manifest.json as

// manifest.json
// Describes the extension & tells Chrome what scripts to run
{
  "name": "Facebook Link De-Mangler",
  "version": "0.1",
  "description": "Disables Facebook external link mangling",
  "content_scripts": [
    {
      "matches": ["*://*.facebook.com/*"],
      "js": ["jquery-1.6.2.min.js","main.js"],
      "all_frames": true
    }
  ]
}

The first couple of lines are just description; content_scripts is where actual instructions go. In this case, we're telling Chrome that for all pages on Facebook, run jquery-1.6.2.min.js and main.js.

Of course, those two files need to exist for the extension to function properly. First, go and grab yourself the latest version of JQuery, which is a free Javscript library enabling all sorts of cool tricks5. Then just create main.js:

function modifier()
{
// The following line is optional and will highlight all external links in yellow
$("a[href][onmousedown^='UntrustedLink.bootstrap']").css({'background-color': 'yellow'});
$("a[href][onmousedown^='UntrustedLink.bootstrap']").attr('onmousedown','');
}

intID = setInterval("modifier()",5000); 

All of Facebook's links that go to external pages call UntrustedLink.bootstrap in order to alter the URLs when the mouse is clicked on it. The modifier function gets rid of the onmousedown attribute, so the link remains unmangled. It runs every 5 seconds, which is necessary because page content loads dynamically in Facebook, and not just once.

And that's it; I told you the coding was minimal. Of course, the new extension needs to be loaded. To do that, go to the Google Chrome extensions manager. If there's a "+" next to "Developer Mode", you'll need to expand that. Then just "Load Unpacked Extension" and direct Chrome over to the folder you saved the files in (e.g. /path/to/FacebookLinkDeMangler). Now for the final step: copy and paste links from Facebook to your heart's content. That's all folks!

  1. To be fair, Google only mangles links when a user is logged in.
  2. I oftentimes have multiple instances of Chrome and Firefox running to be simultaneously signed in under different accounts.
  3. For those using Firefox, it should be trivial to write a similar script using Greasemonkey, though I haven't tested it myself.
  4. Facebook could also be doing something similar to what Bing does, and do remember that any time you visit a site that's enabled Facebook's Social Plugin, your visit is probably sent to their servers.
  5. If it's a later version of JQuery, the filename in manifest.json will obviously need to be updated to match.