Nerderati

The Wonders and Simplicity of Redis Sets

2010-02-26T18:22:05Z

If you were to apply a bijective function to each letter in each word of a language (e.g. English), how many pre-existing words would you obtain in the resulting image?

Since that’s a pretty convoluted way of explaining things, let’s try a more concrete example.

We’ll take the well-known rot13 substitution cipher (a simple example of a bijection between the set of letters in the English alphabet and itself), and apply it to every letter in a chosen word. For most words, the result will be non-sensical gibberish. There does exist, however, a subset of valid English words that map into other valid English words.

Example:

rot13('sync') = 'flap'

How many of these words exist? To answer this, I wrote a small Python script that loads up the words in my system dictionary into a Redis set. Another set of the rot13′ed words is then stored, and the set intersection of the original and transformed words is calculated:



import redis
def encode(word):

    return word.encode(‘rot13′)
def cleanup():

    db.delete(‘eng’)

    db.delete(‘eng-rot13′)
if __name__ == “__main__”:

    count = 0

    db = redis.Redis()

    cleanup()
    for line in open(‘/usr/share/dict/words’, ‘r’):

        count += 1

        db.sadd(‘eng’, line)

        db.sadd(‘eng-rot13′, encode(line))

        if (count % 10000 == 0):

            print “Loaded %d words so far” % count
    db.sinterstore(‘eng-intersect’, ‘eng’, ‘eng-rot13′)

    msg = “English dictionary contains %d words, and %d rot13′ed words”

    print  msg % (db.scard(‘eng’), db.scard(‘eng-rot13′))

    print “Cardinality of intersection: %d ” % db.scard(‘eng-intersect’)

    cleanup()

After a simple cardinality check, we have our answer: 256 words^[1].

The great part about this little script is that nearly everything is done natively in Redis – the only thing Python is needed for is loading the words into the database, and the implementation of the bijective function that we wish to apply.

This is a very contrived example, but the ease with which I was able to map my thought process to code was fantastic. No need to think about tables, rows or joins – just sets, and operations on sets. The simplicity of it is almost shocking.

Pretty neat, eh?

[1] This result does not discard any single letter words (e.g. “a”), which will always trivially map into another letter when using rot13.

Shebang

2010-01-31T07:04:45Z

An explanation of the shebang^[1], and what it means when included in a script:

#!/path/to/interpreter -flags

Means

“This file is not My Words, but My Commandment to you, System. You must travel along this Path. At the end, you will find an Interpreter. You will pass unto him these Flags, and he will help you to understand My Biddings. You will do this, for I have execution permissions on this file.”

From the bowels of Reddit.

[1]: Shebang (#!)

Macro Humanity

2010-01-12T01:18:42Z

It’s not often that I come across an essayist that completely blows me away, but Nick Bostrom has done just that.

I came across his name for the first time while browsing the latest Hacker News submissions, under the link-baited submission title: Why I Hope the Search for Extraterrestrial Life Finds Nothing. Needless to say, I was intrigued, and the comments on the HN page were encouraging.

After a few cursory credential checks¹ to confirm that the author wasn’t a complete nut job (quite the opposite, actually – see the footnote), I took the time to sit down and read the essay.

Here is a short excerpt:

What could be more fascinating than discovering life that had evolved entirely independently of life here on Earth? Many people would [...] find it heartening to learn that we are not entirely alone in this vast cold cosmos.
But I hope that our Mars probes will discover nothing. It would be good news if we find Mars to be completely sterile. Dead rocks and lifeless sands would lift my spirit.

Where Are They? [pdf]

I won’t go into any of the finer details – for that, you should read Professor Bostrom’s elegantly written article – but If you’ve ever heard of the Fermi Paradox or pondered over the murky details of the Anthropic Principle, I highly recommend reading the article I’ve linked to above. These topics may have been discussed ad nauseam in many corners of the web, Professor Bostrom’s thoughts and insights are trully a breath of fresh air.

[1] Professor Bostrom has quite the resumé, including a Wikipedia page, two published books, dozens of published articles in well respected journals, and is currently the director of The Future of Humanity Institute at Oxford University. In other news, I now feel more inadequate than ever.

Redis Memory Monitoring – Python Edition

2010-01-05T04:58:05Z

A few hours ago, Salvatore Sanfilippo (the lead developer of Redis), tweeted a little Ruby script to interactively estimate the memory usage of a running redis-server instance:



require ‘rubygems’

require ‘redis’
def main(opts={})

    r = Redis.new(opts)

    um = 0

    while true do

        newum = r.info[:used_memory]

        if newum != um && um != 0

            diff = newum.to_i-um.to_i

            puts “#{um} bytes (#{diff} difference)”

        end

        um = newum

        sleep 1

    end

end
main

I’ve been experimenting with a Python+Redis combination (with redis-py) for data analysis on a few side projects lately, and a simple script like this can come in handy when you want to make sure you’re not doing something completely stupid with Redis that gobbles up all of the allocated memory. And yes, I’ve been guilty of doing that on a few occasions.

Converting the script from Ruby to Python (with some additional logic for command line option parsing) is very straightforward:



#!/usr/bin/env python
import redis

from optparse import OptionParser

from time import sleep
def options():

    parser = OptionParser()

    parser.add_option(“–host”, default=”localhost”)

    parser.add_option(“–port”, type=”int”, default=6379)

    return parser.parse_args()
if __name__ == ‘__main__’:

    (opts, args) = options()

    r = redis.Redis(host=opts.host, port=opts.port)

    um = 0
    while True:

        newum = r.info()['used_memory']

        if newum != um and um != 0:

            print(‘%d bytes (%d difference)’) % (um, newum – um)

        um = newum

        sleep(1)

Once again, git and GitHub make this kind of collaborative development almost too easy.

ConFoo You Too

2009-12-15T07:11:19Z

While a bit late, I’m extremely happy to announce that I have been selected as a speaker for the ConFoo.ca Conference to be held in Montréal at the beginning of March, 2010.

I attended this conference last year when it known as PHPQuébec, and had a fantastic time; the sessions as well as the speakers were excellent, as were the hallway conversations with other conference attendees.

Along with the change in name, the focus of the conference itself has shifted from being PHP-centric to something more language and technology agnostic, with sessions on .NET development, Python tricks & idioms, databases and a host of other topics. The list of sessions and speakers should make any developer worth his salt giddy with anticipation.

The talk I will be presenting is entitled A Web Framework for People Who Hate Frameworks, and focuses on Lithium, one of my most recent endeavours with CakePHP core alumni @nateabele and @gwoo. You can read more about the talk I’ll be giving on the session page, and for all those who will not be attending ConFoo 2010 I encourage you to visit #li3 or #li3-core on irc.freenode.net, and ask us why Lithium is making waves in the web framework world.

New Design, New Engine

2009-11-29T02:05:02Z

As some of you may have noticed, I recently changed the design of Nerderati.

While I quite liked the last design — Charcoal — I wanted something lighter, and that put more emphasis on the content. Moreover, I had made the decision to switch from Habari, to Wordpress.

Habari is a fantastic blogging engine. It’s design & architecture is particularly well done, and is how WordPress should have been done in the first place. Their community is both active and knowledgeable, having put out three minor releases since I had started Nerderati last year, as well as releasing a great deal of plugins.

So why the hell would I switch to WordPress, of all things?

I realized that I was eternally attempting to tinker with Habari; A plugin incompatibility here, an issue with the media browser there, and a sprinkling of minor missing features. While every problem I had experienced was minor and should be expected for relatively new (and pre-1.0 release) software, they were additional psychological barriers between me and posting new articles.

Then, I had an epiphany: I was looking at my blog from the perspective of a Developer, instead of a User. WordPress’ internals might not sit well with me on a technical front, but who cares? I’m not developing for it. I’m not designing for it. I sure as hell don’t have the time to be continually tinkering with a blog engine (and I have no interest whatsoever in blog engines, not just WordPress). I have no doubt that Habari will one day compete toe-to-toe with WordPress feature-wise, but that’s not today.

So I decided to apply my normal work philosophy, and use the best available tool for the job at hand. And as soon as I stopped thinking of it from a developer point of view, the choice was obvious.

I just have to make sure to never look at the source code of this damned thing.

The PHP 5.3 Y-Combinator

2009-12-09T03:14:48Z

One trick that seems to be all the rage these days is to show off fancy results from functional languages in their imperative counterparts. Now, I love functional languages; OCaml/Haskell/Erlang give me a programmer hard-on that imperative languages can only dream of. In that vein, I present to you a very clever implementation of the y-combinator in PHP 5.3 that Nate Abele came up with a few nights ago while we were discussing fixed-point combinators over instant messenger:



«?php

function Y($F) {

    return current(array(function($f) {

        return $f($f);

    }))->__invoke(function($f) use ($F) {

        return $F(function($x) use ($f) {

            return $f($f)->__invoke($x);

        });

    });

}

?»

(see the original Twitter post)

Sexy, right?

If you’re keen on fooling around with the gist, your first challenge is to implement a memoized-version of the above y-combinator. Your second (which will take you significantly longer), is to come up with a valid reason to actually use this in in production code.

Hello, World

2009-12-09T03:21:41Z

When a programmer takes his/her first steps in a new language, the first example program he/she codes (or skips over) is usually the prototypical “Hello, world”, or a variant thereof. I thought I might run through a few of the classical “Hello, world” examples from programming languages that I find interesting.

This first example is from Factor, an example of a concatenative (as opposed to applicative) language:

I’m trying to find more reasons to toy with Factor, simply because it is such a huge departure from the programming languages I’ve used in the past. Some of the interesting features:

A postfix syntax
Stack-based
Classes can be predicate and union based

The next is from Haskell, my favourite functional programming language:

My favourite Turing-complete joke language, LOLCODE:

As a crazy side note, it appears that the Turing completeness of LOLCODE was in part proven by using it to create a Brain Fuck interpreter (where BF has already been proven to be Turing complete).
That’s fairly mind-blowing to me, especially considering that BF is pretty much as incomprehensible as it gets (by design), and LOLCODE syntax is based off of subtitles from funny cat pictures.

Fortran which is still heavily used in high performance computing, benchmarking and scientific analysis (e.g. computational physics) due to it’s extremely stable and robust floating point arithmetic and floating point exception handling. I still wouldn’t touch it with a ten-foot pole these days, however.

Got any favourite languages that aren’t “mainstream”? Let me know in the comments.

The Meritocracy of Open Source

2009-11-27T17:10:44Z

In democracies, power is held by the citizens. The problem with this (at least in terms of open source software) is that, by and large, people are dumb.

The root of the problem lies in the fact that many people approach code in a selfish, rather than Utilitarian, manner. Of course, this is a non-issue in circumstances when you are writing code that will never be released to the public. But for those of us that do work and contribute to open source codebases, utilitarianism is a smart (and thankfully prominent) modus operandi. If the core developers of some popular web frameworks started adding classes and methods in their respective codebases to properly parse Flickr LOLCODE, I’m sure a few concerned voices would be heard.

Open Source is not a Democracy. It’s a Meritocracy.

Plato seemed to have addressed this issue in his famous Socractic diaologue of The Republic, suggesting that the ideal form of government was one formed of philosopher-kings. If we disregard the pompous title of ‘philosopher-king’, Plato’s idealized form of government is quite similar to how most open source projects are managed. Core members are not elected by the community. Rather, they are appointed to their position based on their qualifications, and are tasked with governing in such a manner that will yield the greatest good for the greatest number of people. This resembles most open source organizational methods quite well¹.

As such, I’ve come to this conclusion: Open Source is not a Democracy. It’s a Meritocracy. There are no political parties, campaigns or lies and promises. Instead, a person is judged entirely by the code that they write, and the relative usefulness of the later to the community at large. No one is ‘elected’ into an open source team. You get invited, usually (and hopefully) on the basis of your individual merit and perceived dedication to the project.

And the crazy part? This actually works. Open source produces some fantastic software. Much of the internet and the web runs on open source stacks, and those numbers don’t seem to be dropping anytime soon. Add to that the incredible advances that have been made in the last decade in open source desktop and so-called ‘enterprise’ software, and the above conclusion is undeniable.

Is a Meritocracy the best philosophy under which we should write code? Perhaps not. But I can’t think of anything better.

If it ain’t broke, don’t fix it.

^[1] The only exception that I know of is FreeBSD, where they hold elections for the core team every two years. This (surprisingly) seems to work extremely well for them.

Hacking Hotel Wifi With an SQL Injection

2009-12-05T22:21:23Z

After attending & speaking at CakeFest 2009 in Berlin, Germany, I decided to take a week off and explore the city. Since the hotel that I had been lodged in for the conference had free Wifi, I assumed that this was the norm in mid-range to high-end hotels in and around Berlin. And, as you may have noticed from the title of this post, it seems as if I was mistaken.

Crazy prices

There’s no way in hell I was going to pay 69€ for the five days that I was staying at that hotel. So, like any good free loader, I first checked the other available networks that I could connect to.

The Intrigue

After a bit of recon on signal strength with iStumbler, I tried to connect to the only other moderately strong network that wouldn’t make me stab my own eyes out.

Available networks

It turned out to be another managed Wifi from the hotel across the street, but these guys offered a ‘Free’ connection in addition to their ‘Business’ connection (which was about as crazily priced as the one I was trying to desperately avoid paying), the difference being some bullshit options like not actively blocking VPN ports and prioritized traffic. Oh well, free is still better than nothing. Plus, I thought, I could always just tunnel whatever ports & services I needed.

The Turn

Of course, that would have been too easy. To actually use their free Wifi, you needed to input your room number, as well as the name of the person who registered the room in the first place. Seems that this particular establishment didn’t like the idea of letting people not actually staying at the hotel using their ‘free’ wifi.

After trying a few random room numbers and gibberish names to verify that data validation was actually being performed on the server-side, I figured I had nothing to lose by trying a few standard SQL injections to see if I could bypass the whole process.

On first blush I thought that this error message meant that my attempts were in vain, since the application seemed to be escaping my input and determined that no relative of Bobby Tables was currently in room 228.

The Revelation

However, I know how developers can sometimes be lazy, and this lazyness sometimes manifests itself in slightly incorrect error messages. So I tried a different room number.

And lo and behold, success!

I wasn’t going to be downloading torrents with a 200mb/50mb daily transfer limit, but it was good enough to check emails and do the occasional git pull on some projects.

It Shouldn’t Be This Easy

Sometimes I wonder how any web developer worth his salt can overlook such a simple SQL injection vulnerability, especially one that is both well documented and easy to protect against. Worse, I’m pretty sure that this application was developed for multiple hotel locations, which means this brain dead attack vector exists in all of those spots.

Now, I only tried this attack on the ‘Free’ wifi, but you can see all the trouble that could be caused by performing this same process on the ‘Business’ wifi option, which would have billed the room occupant at the end of his stay. I wouldn’t like to be the desk clerk when that person checked out of the hotel.

With tools like SQL Inject Me available at the click of a button, it’s never been easier to test (and hack) forms for a variety of simple injection vulnerabilities. Couple that with any half-decent developer who can figure out a few details about the internal structure of your application, and you’re just asking for trouble by not sanitizing your input.

But at least I didn’t have to pay for wifi.