Spooked by a corrupt initrd image

Halloween is approaching. It is apt I have a scary tale to tell.

I left my laptop on in the sun, on a surface with poor conductivity. As I opened it, I glimpsed it complaining of heat exhaustion before it powered off. (That’s happened to me before, too!) I let it cool off, but on booting Ubuntu, a terrifying message was all that appeared on the screen:

Error 16: Inconsistent filesystem structure

Uh oh. Did I lose everything? What haven’t I backed up lately? Indeed, what have I backed up lately?

I searched online for the error message, and took heart when others reported no data loss in various forums. Running fsck was suggested, though in at least one case they resorted to reinstalling the OS. No way I’m doing that!

My first instinct was to dust off my USB DVD writer and burn a Ubuntu rescue CD. This turned out to be unnecessary, but at least I was reassured when I used it to mount the Linux partition and found my files intact. Firing up fsck had no effect: I was still defeated by the same error message.

Playing with the GRUB command-line (by pressing “c” instead of selecting an kernel to boot) showed that the initrd image was corrupted, as selecting the newest image with the “initrd” command triggered the same error message.

The solution was easy. Boot up an older kernel, then download a fresh copy of the initrd image by running:

$ sudo apt-get install --reinstall linux-image-2.6.32-25-generic

Shameless plugs

Better the head of a chicken than the tail of an ox. This Chinese proverb captures entrepreneurial thoughts I’ve long harboured. It’s a common affliction around my neck of the woods.

Unfortunately, I’m disinclined to abandon my cushy job to work my fingers to the bone for an uncertain reward. My dreams are likely doomed to remain dreams.

To compensate, I’m living vicariously through friends who are being their own boss. I’m devoting this post to them; may it contribute at least an iota to their success.

China Luxury Travel Network (CLTN.net)

Ethan lived on the ground floor of my apartment at Stanford. Early in my degree, he finished his Masters, in financial mathematics I think. I’m uncertain because we rarely chatted about school! I’m sure his latest venture will succeed, and not just because he’s capable.

I was in Ottawa for a conference in '03. I skipped half of it to hang out with Ethan, who gave me a tour of the city where he grew up, which became challenging when a widespread blackout hit the region. On top of all this, I had FedExed a visa document to his parent’s house (which I needed to return to the US), and he went out of his way to deliver it to me.

A few years later, I was in China on vacation, mainly because I wanted to see the Guangzhou Trade Fair. I met up with Ethan. I thought we’d do little more than catch up over a meal. Well, we did chat over dinner: Ethan had worked in Hong Kong’s finance sector for a while, and was now living off savings while exploring China. I was still a starving student.

But then Ethan took us to a health spa in Shenzhen which was cheaper yet far more luxurious than the hotels we had been considering. For about $20 a day I got massages, food, spas, haircuts, movies, a place to sleep, etc. I never thought I’d get a pedicure in my life, but because it was effectively free, I had to try it.

Then in Hong Kong, we crashed at his place, which saved a lot of money. He took us on a whirlwind shopping and eating tour. Soon after, we had to part ways, but not before he showed us a website offering discounted rates at hotels in Guangzhou. We got a great deal at a great hotel across the street from the trade fair. At the check-in counter, the guy in front of us was livid when he learned how little we were paying.

He offered to take me on a tour of China after the trade fair was over, but I declined. I deeply regret my decision. What’s a few weeks of missed grad school? Ethan spoke three or more Chinese languages. He knew where to go. He had contacts everywhere. Clearly, the China luxury travel business is perfect for him.

Embrace

Rahul lived a few apartments away from me in grad school. He mysteriously vanished one year. I heard later it was because he was “saving babies”. This raised yet more questions! Wasn’t he an engineer?

Certain problematic births are far less problematic when an incubator is available. Unfortunately, the cost of typical incubators often places them beyond the reach of poor remote villages, contributing to higher infant mortality. Rahul helped design a vastly cheaper incubator, and hopes to eventually supply one wherever babies are born.

Total Phase

I met Kumaran through his wife. I was a Teaching Assistant for an introductory computer science class she was taking. Kumaran wanted to meet partly because he wanted help recruiting people for his company. I was of no help: at the time, my engineer friends were already employed, and they were busy recruiting people themselves!

Total Phase’s biggest hit is a USB protocol analyzer, an invaluable tool when developing USB products. Kumaran loves being an engineer designing for engineers. They never bothered advertising since engineers tend to use logic to determine purchases, and their products are better and cheaper than those of their competitors. I saw parallels when I read about the HP200A, an audio oscillator that was profitable because it was the best and the cheapest.

Disc Eraser

My cousin Wade designed a simple tool to render CDs and DVDs unreadable. An easy motion etches deep parallel scratches into the media: Freddy Krueger for discs. Quick and safe. No batteries. No electricity. The disc stays in one piece, ready for recycling.

He used to work on hard drive platters at IBM (before they sold the division to Hitachi) so he knows what he’s doing. He verified his claims with AcoDisc, a data recovery company. After a single application of the Disc Eraser to a CD, the data was deemed unrecoverable.

I don’t burn much, let alone anything confidential, so it’s not something I need. However, I’m grateful for a sample he gave me: as a kind of therapy, I savagely mutilate CDs I receive as junk mail.

Bump

Dave was yet another electrical engineering student in my neighbourhood during grad school. I never would have guessed he would join the dark side and become a Pointy-haired Boss of a startup. Seriously though, I like tech companies with an engineer at the helm. And Dave’s hair is not pointy.

Years ago, a friend once pointed out that two people in the same room cannot easily get their laptops to talk to each other. Sure, there’s Bluetooth, ad-hoc wireless networking, and other hacks, but he was right: even now, it’s easiest for one party to verbally ask for contact details of the other. This is somehow troubling.

I remember a light-hearted news report I watched once, which described a gadget in Japan. You’d enter a few personal details, and carry it around. It would alert you if someone of the opposite sex nearby had the same gadget and had similar interests to you. What became of this? Couldn’t they do something like this so you would never have to spell out someone’s email address or type in a phone number?

Enter Bump, an app for iPhone and Android that attacks this problem in a cute way. Both sides run the app, then lightly bump their phones together to swap contact details, or other data. No physical contact is actually needed as the phones just have to be close enough, but smashing your fists together is more macho!

Millinery Kestralia

Kestrel lives a few streets away, which benefits me greatly because she is a good chef and a keen gardener. She also loves making hair accessories, and recently started selling them. Each handcrafted piece is unique and beautiful, like their creator.

Moore's Treadmill

Early in my PhD, I told my advisor I had implemented a particular cryptographic algorithm with a tolerable running time. It wasn’t that fast, but I figured within 2 years, microchips would be twice as powerful, so my code might be practical even on handheld devices.

He replied: "No. Then they’ll halve the power consumption to double the battery life." Or they’ll want to run it on yet smaller devices. Laptops, phones, smart cards. I still had plenty of work to do.

For me, user interfaces are trapped on the same treadmill.

Less is more

Not so long ago, my desktop had a 14-inch CRT display, a lonely and lowly processor clocked at 200MHz, a few gigs of hard disk space, and a 14.4k net connection. The dearth of screen real estate favoured spartan user interfaces, the CPU struggled unless tools were quick and nimble, and the cramped conditions of the hard disk and net connection favoured good things in small packages.

For example, when the time came to take sides in the text editor holy war, I chose vi because it would only take several minutes to grab a few hundred kilobytes. Emacs was over 6 megabytes.

Now I often work at a PC sporting multiple cores, each over 20 times faster than my old workhorse. I have multiple monitors, each so large that I turn my head to look at different parts of a screen. Network latency is low, and bandwidth is high.

Yet I remain minmalist. Indeed, I keep finding new ways to trim the fat, despite having ample space. For instance, my first web browser had big buttons and a plethora of bars: title bar, menu bar, bookmarks bar, status bar, location bar, etc. Today, even though I can afford extra fluff, my primary browser shows little apart from the webpage: a bar for tabs (itself a space-saving measure over multiple windows), a single textbox, and a handful of buttons.

I chose my style partly because I’m a programmer to the bone: my drive to automate, simplify, and optimize carries over from coding to real life. However, there is a more compelling reason.

Technological advances mean my laptop can handle tasks that once required a desktop. But the laptop screen is even smaller than my old monitor. The net connection can be spotty, especially via tethering or a smartphone WiFi hotspot. The CPU often underclocks to save battery, and moreover, I fritter away cycles on fripperies such as visual effects: I’m a Compiz plugin junkie. I therefore encounter the same problems I faced over a decade ago.

A Voyage to Lilliput

Beyond laptops, we have netbooks, tablets, and smartphones. The world is getting smaller. Being a geek means I’ll attempt text editing, gaming, programming, etc. even as devices keep shrinking, bringing new user interfaces challenges. My current extreme case is my Nexus One, with its 3.7 inch display and no keyboard.

Rather than work on the phone directly, I ssh to a more powerful computer via ConnectBot.

In the past I praised Bash one-liners. Shelling in from a smartphone drove me to appreciate Bash one-letter aliases. I’ve grown accustomed to using them on all computers. Some favourites:

alias c=cd
alias ..="cd .."
alias v=vim
alias g=git
alias l="ls -CF --color=auto"
alias s=sudo
alias k=colormake
alias rm='echo mv to /tmp instead'

(The "rm" alias trains me to avoid this command. See "Accidents Will Happen" in The UNIX-HATERS Handbook.)

Editing is unpleasant but bearable. In these circumstances, I feel Vim’s single-letter commands work in its favour, as does its modal nature. Also double-tapping the terminal brings up an "Esc" button, which suits Vim beautifully.

I don’t intend to code from my phone often as it’s like eating with tweezers. Though for fun, I followed through a suggestion in my last post and developed a J one-liner to sum the primes less than 100 using only a ConnectBox session on my phone. Soon I had:

   +/p:i.p:^:(_1)100
1060
   +/i.&.(p:^:_1)100    NB. Cooler version.
1060
   v=:[:+/i.&.(p:^:_1)  NB. Tacit verb definition.
   v 100
1060

J and I

For years, I’ve been meaning to investigate the APL programming language family. Months ago, I finally leafed through a few introductions to the new and improved APL known as J.

I liked what I saw. I enjoy paring down C code, but J makes my best efforts look as verbose as a legal contract. Introductory J examples are already cryptic enough to induce watering in the untrained eye. In the right hands, a J program can be compressed so densely that it threatens to collapse into a black hole of inscrutability.

I’ve heard about an obfuscated C tattoo, as well as a Lisp tattoo. They should have gotten J tattoos! Instead of Hello World or the Fibonacci sequence, why not sport a terse program that solves a Sudoku, or finds a QR decomposition of a matrix?

More generally, J appears to be ideal when source size matters most. For example, programming via a smartphone with a tiny screen and keyboard.

A day at play with J

J systems are freely available, but I reasoned I’d get a better feel for the language by writing my own interpreter. Thanks to J’s elegant design, I soon got the celebrated "mean=:+/%#" example working. That was enough to gain an appreciation (but also a little contempt) for J’s simple grammar, array handling, and above all, compact notation. A J symbol is worth a thousand machine words. See my J notes.

I kept picking at it for a while, but I think I’ll stop soon. It’d take substantial effort to implement types apart from doubles, not to mention error handling, memory management, arrays with axes of zero length, and fills.

Git repository: a primordial J interpreter.

The timeless beauty of shell scripts

Long ago, Doug McIlroy wrote: “This is the Unix philosophy: Write programs that do one thing and do it well. Write programs to work together. Write programs to handle text streams, because that is a universal interface.”

Years later, Rob Pike observed: “Those days are dead and gone and the eulogy was delivered by Perl.” His statement mostly stands, except Python is the new Perl.

I refuse to abandon the old ways. So when a friend pointed me to the intriguing Python Challenge, I avoided Python as much as I could. Instead, I used the Bash shell to string together special-purpose tools.

The FAQ states the purpose of the challenge is to “provide an entertaining way to explore the Python Programming Language”, and “demonstrate the great power of Python’s batteries”. However, I feel it is better suited for training shell script muscles: most of the problems are of the one-shot trivial variety that suit Unix tools.

A full-featured language is often overkill. Abraham Maslow’s quote comes to mind: “It is tempting, if the only tool you have is a hammer, to treat everything as if it were a nail.” I don’t mean to disparage Python, but I feel shell scripts are often overlooked and under-appreciated, especially as they are so accessible. Technically, you’re already shell programming when you run a program from the command-line. Why not learn a bit of Bash or similar, and increase the power available at your fingertips?

Brevity is the soul of wit

While general-purpose scripting languages have their place, judging by the posted solutions, for typical riddles in the Python Challenge, a short Python script is often outdone by a shorter still Bash incantation. In fact, in the first challenge you can stay in your shell. Did you know Bash natively handles (fixed-width precision) arithmetic? For example:

$ echo $((2**42))

Naturally, if arbitrary precision were needed, we could invoke a specialized tool:

$ echo 10^100 | bc

Humble Unix tools yield the most succint solution for several challenges. For example, a Caesar shift is probably terser with tr than any popular language:

$ tr a-z l-za-m

Or extracting lowercase letters from a file:

$ tr -cd a-z

When regular expressions are involved, even though the code may look similar, the old guard such as awk, sed, and grep that feature regularly in Bash scripts have an inherent advantage over Python (and Perl, PHP, Ruby, …). Python takes exponential time to match some regular expressions whereas the classic Unix tools take polynomial time to match the same expressions.

On the downside, Bash makes some tasks tiresome. I can’t think of an easy way to convert an decimal number to an ASCII character. This Bash FAQ suggests the cumbersome:

$ for a in 66 101 110; do printf \\$(printf '%03o' $a); done; echo

Another chore is repeating a character a given number of times. Other than a loop, perhaps the easiest hack is something like:

$ printf "%042d" 0 | tr 0 x

A tiny elegant Haskell solution exists for problem 14, thanks to the transpose function and the language’s concise notation for recursion and composition. A search revealed Bash fans often employ a simple but tedious Awk script for matrix transposition, suggesting a Bash solution is necessarily significantly longer.

Happily, these blemishes are dwarfed by the successes of the Unix philosophy. More than once, my script has been simpler and briefer than any other posted solution because the complexity is hidden within a tool that does one thing, and does it well. My proudest achievement is a one-liner to compute the look-and-say sequence [hint: uniq -c].

Chinese Input

Google Translate supplies a clumsy but straightforward means for entering Chinese characters with a US keyboard, especially for those learning the language. Simply type the English meaning, and copy the result. You can check the character is indeed the one you want by clicking on "Show romanization", or on the speaker icon to hear a synthesized reading.

However, sometimes I have a particular character in mind. A short-term solution is to use an online rendition of a traditional dictionary ordered by radical and stroke count, or a pinyin dictionary. Additional speed and convenience requires investment; one must learn one of the many fascinating methods for entering Chinese characters on a computer.

I’ve read that the Wubizixing input method is fastest, though as one might expect, it requires the most investment. Proficiency demands much practice with a suitably annotated keyboard.

For now, I’ve opted for the Wubihua method, which mimics how humans write characters. It may be slower, but it can be learned quickly. Also it applies when sending Chinese text messages on mobile phones.

I supplement Wubihua with a pinyin method, as I’m practically illiterate in Chinese.

Chinese input in Linux

To setup Chinese input methods in Ubuntu, I installed the scim and scim-pinyin packages, then modified my .xsession as follows. I prepended:

export XMODIFIERS="@im=SCIM"
export GTK_IM_MODULE="xim"

and appended:

scim -d

after which pressing Ctrl+Space toggles Chinese input.

"Stroke 5" is Wubihua mode. Stroke types are mapped to 5 keys along the bottom row. From right to left:

/: | (vertical; top-to-bottom)

.: \ (downwards left-to-right)

,: / (downwards right-to-left)

m: - (horizontal; left-to-right)

n: other stroke types, e.g: 乙

Perhaps one can remember this as follows: 乙 looks like a rotated N. A lowercase M takes more horizontal space than most letters, so it corresponds to the horizontal stroke. On the next two keys, the less-than and greater-than signs point left and right, so they correspond to the left and right downward strokes. Lastly, the stem of the question mark suggests a vertical stroke.

Although the pinyin method is found in the Simplified menu (智能拼音; "smart pinyin"), it also offers Traditional characters. I originally learned zhuyin (aka bopomofo), a more traditional pronounciation-based method for producing Traditional characters, but it is ill-suited for a US keyboard. Fortunately converting from zhuyin to pinyin is trivial.

Chinese to English

In a pinch, I’ll use Google Translate to learn Chinese phrases. However, browser plugins are much handier; see the Chrome Zhongwen extension and the Firefox Perapera-kun add-on.

Stack-smashing remains fun and profitable

Buffer overflows have long been a rich source of security vulnerabilities. Unfortunately, its popularity led to a family of knee-jerk reactions: W^X; Data Execution Prevention (DEP); the NX (No eXecute) bit; executable space protection.

As the terms suggest, code is divorced from data. For example, an operating system may forbid execution of any instructions lying in the stack. A simple buffer exploit now causes the program to halt, rather than execute injected code.

My knee-jerk counter-reaction was suspicion and hostility. Shouldn’t we be focusing on the causes of buffer overflow disease, and not its symptoms? Also, some of the most beautiful and fundamental results in computer science involve feeding a Turing machine to a Turing machine. Data is code and code is data.

Self-modifying code considered awesome

Self-modifying code is fascinating by virtue of its self-referential nature, but it is not just a pretty face: it has practical applications. Just-in-time compilation is perhaps the best-known example. However, I find it most useful for nested functions in C.

Thomas Breuel describes how a C compiler can be modified to allow nested function via trampolining. Briefly, for each nested function, we generate its code as usual, but we also add a local variable to the scope where it is defined: we add an array of bytes, whose contents are opcodes that simply rig a pointer to make it look like we’re in the current stack frame before jumping to the nested function.

Standard C code expecting a function pointer still works when passed a pointer to this array. When they call the function pointer, they jump to the array, where they run the stack-frame-rigging code before continuing on with the call. By magic, the code in the nested function executes within the desired scope. One pointer does the work of two.

Observe we require the array to be local and populated at runtime, because only then do we know the address of the current stack frame. We cannot setup this tomfoolery in advance. In other words, we must execute code we just placed on the stack.

Like duct tape, treating data as code deftly solves a host of problems. W^X and friends block this avenue, or at least make it less efficient. Breuel writes:

"There are, however, some architectures and/or operating systems that forbid a program to generate and execute code at runtime. We consider this restriction arbitrary and consider it poor hardware or software design. Implementations of programming languages such as FORTH, Lisp, or Smalltalk can benefit significantly from the ability to generate or modify code quickly at runtime."

Return-oriented programming

Hovav Shacham recently filled me in on return-oriented programming. I’m a fan. I now have more than gut feelings to support my stance. I can gloat and say "I told you so".

Return-oriented programming skirts around stupid restrictions via one level of indirection. Instead of putting code in the stack, we put pointers to the code in the stack. We choose to point at code that soon runs into a return instruction. On typical architectures, a return instruction increments the stack pointer before jumping to the address to which it points. Hence the stack pointer becomes a sort of indirect instruction pointer: we run a snippet of code until it hits a return statement, which causes us to run the next snippet of code, and so on.

Thus using a compromised stack, attackers cleverly glue together snippets of code in executable parts of memory, such as the BIOS or the standard C library. On popular systems there’s enough stuff to do anything. Tools for automating the process exist; namely, you can write source and have it compile to a sequence of cherry-picked memory addresses. It’s the return-to-libc attack on steroids.

I had hoped return-oriented programming could cut both ways; does it allow self-modifying code even in the presence of an NX bit? Sadly, on further reflection, return-oriented programming appears to have no legitimate uses. Arbitrary code execution is only possbile within the stack frame of a function we control, and, for example, we still have no means of adjusting the static link pointer when qsort() invokes our nested function. Hopefully I overlooked a sneaky trick.

In short, thanks to return-oriented programming, executable space protection is a minor inconvenience for the bad guys, and a major inconvenience for the good guys.