nameandnature

The Cursed Computer Iceberg Meme

This is fun if you’re a computer geek.
(tags: history culture programming computers)

---

Originally posted at Name and Nature. You can comment there (where there are currently comments) or here.

What We Can Learn from the Paris Attacks (Without Ignoring the Elephant in the Room)

Yep, this is more or less what I think.
(tags: paris terrorism islam islamism religion politics)

What is emotional labor?

A term that once described jobs where being friendly and cheerful was seen as part of the job has apparently been co-opted to mean “someone expects me to do something”.
(tags: emotion labour work relationships)

Guide to software developer job advertisements: andrewducker

Seems legit.
(tags: software software-engineering jobs adverts careers)

My first 10 day Vipassana retreat

Not *my* retreat. Some bloke’s. It’s an interesting article about the experience though.
(tags: meditation buddhism mindfulness retreat)

An alias for when you really need it done…

I’m totally setting this up.
(tags: funny computers unix sudo)

The Deadlock Empire

A nice little web game where you try to break a threaded program by executing a critical section in two threads at once. It’s pretty neat.
(tags: programming threads concurrency locks game)

---

Originally posted at Name and Nature. You can comment there. There are currently comments.

BBC News – Leaked letter shows ISPs and government at war

Dave wants a scheme were people uncheck a box to get pr0n described as "default on" filtering, allowing him to claim victory without the ISPs changing what they’re doing.
(tags: politics pornograpy porn censorship internet david-cameron)

David Cameron’s crusade against images of child abuse has a whiff of politics – Editorials – Voices – The Independent

What is Dave up to? The Independent identifies it as a clever bit of politics.
(tags: pornography politics porn censorship internet david-cameron)

12 Silly Things People Believe About Computers | Terminally Incoherent

(tags: computers it support funny)

Victory Lap for Ask Patents – Joel on Software

"There are a lot of people complaining about lousy software patents these days. I say, stop complaining, and start killing them. It took me about fifteen minutes to stop a crappy Microsoft patent from being approved. Got fifteen minutes? You can do it too."
(tags: prior-art software patents)

---

Originally posted at Name and Nature. You can comment there. There are currently comments.

This is an article about the sort of thing I spend my days doing. Usually, I can't talk about that, for reasons of commercial confidentiality, however, this particular case is completely unrelated to anything my employer sells, so I should be OK. I've tried to explain things sufficiently well that someone non-technical can get it. Hopefully it's not too dull or incomprehensible.

First, we need some technical background...

The Naming of the Parts

A graph is a bunch of things connected by lines. The CDC Snog Graph is an example of what I mean. The things (representing people, in this case) are known as vertices or nodes, and the lines (representing joyous sharing experiences of some sort, in this case) are known as edges.

The lines on the Snog Graph don't have a direction, so we call it an undirected graph. If you add a direction to each edge, you get a directed graph, which we can represent by putting arrows on the lines. Friendship on Facebook can be represented as an undirected graph (where the nodes are people and the edges mean "is friends with"), because all friendships are mutual, but LiveJournal friendships need a directed graph to represent them, since I can be your friend without you being mine, and vice versa.

A graph is cyclic if there's a way to walk along edges starting at one node (following the arrows if the edges are directed) and get back to that node again without walking the same edge more than once. The Snog Graph is cyclic, as is the graph of friendships on a Facebook or LJ (trivially so on LJ, where it's possible to friend yourself. Regular dancers might consider how this applies to their graph, vis-a-vis people who consider avoiding other dancers an optional extra). Graphs where you cannot do this are called acyclic.

Usenet news: you tell kids today that, and they don't believe you

Usenet is an electronic discussion system which pre-dates all this newfangled World Wide Web nonsense. It distributes messages which are known as articles. It has some desirable features that web-based discussion forums often lack, like comment threading and remembering what you've already read. These days, people think Usenet is owned by Google, but in fact it's a distributed system, with no central server (another advantage over LJ). When you want to talk to Usenet without using Google, you run a client program on your own machine, which talks to your local server. Your local server forwards your article to servers it knows about, which then forward it to servers they know about, and so on (the path of an article through the servers forms a directed acyclic graph, in fact). When you want to read other people's articles, your client program fetches them from your local server.

Each article is posted to one or more groups, which are like communities on LJ. Note that, unlike LJ, the same article can be posted to more than one group without having to cut and paste it: the same article exists in each group it is cross-posted to.

On each server, articles have a number within each group. The first article to arrive in a group has number 1, the second article number 2, and so on. Cross-posted articles have more than one number, one for each group the article appears in.

Article numbers differ between servers, because the order of arrival depends on the path the article has taken to reach the server, but since your client program only talks to your local Usenet server, it usually refers to articles by their number (there's also a unique string of letters and numbers which identifies the article, which is how servers know which ones they've seen already, but that's not important right now). Remembering which articles you have read is then just a matter of storing some ranges of numbers for each group (so your client might remember that you have read articles 1-100,243-299 and 342-400, say).

The problem

We wanted to de-commission a Usenet server and move its articles to another server. The servers run different and incompatible software, so the most obvious way to get articles from one server to another is to post them like a client or another server would.

The new server is supposed to be a drop-in replacement for the old one, so we can't change the numbers or the existing client programs will get confused and think you've read articles you haven't, or vice versa. So you can't just grab all the articles from the old server any old how and post them to the new one, because they'll be jumbled up. Unfortunately, the old server has no way of directly telling us the precise order that articles arrived in, though it will tell us article numbers within each group.

"Aha!", we think. Since the order of arrival matters, we'll grab the articles in order from one group on the old server, post them in that order on the new server, and move on to the next group, where we'll do the same, and so on until we've done all the groups.

This idea is ruined by cross-posts, because they have more than one article number associated with them. If a cross-posted article is number 10 in one group and number 3 in another, you'd better post the first 9 articles to the first group, the first 2 to the second group, and then you can make the cross-post. But maybe there's a cross-post to a third group in those 9 articles, so you'll need to get that group up to date before you can post one of those. How do you work out what order to post the articles in?

Obscure Unix tools to the rescue

You might have guessed that the wibbling about graphs wasn't entirely tangential to all this. You can draw a graph of the problem. Each article is a node. For each group, connect each article to the one with the next number up by a directed edge (in this case, the direction of the arrow means "must be posted before"). You've drawn yourself a directed acyclic (since the article numbers only increase) graph. The cross-posted articles are then nodes with more than one edge coming into them.

One of the wizards at work realised this, and also pointed out that there's a standard Unix tool for converting such graphs into a list of nodes whose order preserves the order implied by the arrows, a procedure which is known as a topological sort. The tool's called tsort. From there, it's just a matter of representing each article in the way tsort understands. When you do that, tsort gives you an order in which you can post the articles from the old server to the new server so they'll be given the same numbers on the new server as they had on the old one.

In which I'm not as knowledgeable as the wizards

The way I thought of to do it was to write my own program. You pick a group, and start trying to post articles from the old to the new server in article number order. If they're not cross-posted, you just keep going. When you hit a cross-posted article, you switch to each group it is cross-posted to in turn, and try to post all the articles before the cross-post to each of those groups. If while you're doing that, you hit another cross-post, you remember where you got up to and do exactly the same thing with the groups that second cross-post is posted to, and when you've done that, you switch back to the groups for the first cross-post. I had a working version of this at about the same time as someone pointed out that tsort does the job :-)

(Aside for the techies: this can be done using recursion. It looks like this is pretty much equivalent to one of the ways of doing a topological sort, namely the depth-first search mentioned on the Wikipedia page).

So I learned about topological sorts by re-inventing one. Most of the problems I deal with aren't in fact cases of well-known problems (although I would say that if I was merely bad at recognising the fact, wouldn't I?), but when they are, recognising that can save a lot of time.

And that's what I do when I'm not on holiday.

Some of you might have played with emulators which let your PC pretend to be the classic computers of your youth (the BBC Micro, Acorn Electron, Commodore 64 and so on). The emulators work by simulating the processors in those machines on your PC, so you end up with Chuckie Egg running on a virtual BBC Micro running on a PC running on whatever the underlying physics of the universe happen to be.

robhu found a puzzle based on a similar idea. The International Conference on Functional Programming have an annual contest. Last year's was particularly fun:

In 1967, during excavation for the construction of a new shopping center in Monroeville, Pennsylvania, workers uncovered a vault containing a cache of ancient scrolls. Most were severely damaged, but those that could be recovered confirmed the existence of a secret society long suspected to have been active in the region around the year 200 BC... Among the documents found intact in the Monroeville collection was a lengthy codex, written in no known language and inscribed with superhuman precision.

You're given the codex, and the specification for a processor used by the Cult of the Bound Variable. Once you've written an emulator for that processor, you're off (unless, like me, you write the emulator in a few hours and spend half a day corrupting the files from the contest website with your editor and wondering why it isn't working). There's an ancient Unix system, complete with ancient spam, and various puzzles which I've not had a chance to look at yet.

According to reports on the contest, lots of people tried to write the emulator in high level languages where it ran like treacle. A C implementation like mine (which may count as a spoiler for people who want to do it themselves) without any namby-pamby array bounds checking nonsense works fast enough that you can't tell you're not talking to a real ancient Unix system. There's life in the C language yet.

I'm lost in admiration for the people who produced the codex. It required writing a compiler backend targeting the fictional processor, and implementing various other languages on top of that, as well as coming up with the puzzles. I'm not sure how far I'll get with the puzzles before my ability or patience expires, as I'm a hacker rather than a computer scientist, but still, the thing is amazingly cool. It's a time sink for geeks, so I pass it on to those of you who, like me, will waste many days on it. Have fun.

Dear Lazyweb

I'd like some sort of house server thingy. scribb1e and I both have laptops, so we'd like somewhere to back-up important stuff. scribb1e has read the Pragmatic Programmer book and would like to keep her life under version control, which I think means Subversion here (not quite as good as Perforce, but free). I have the vague idea that we could connect something to the stereo and play my extensive collection of mp3z through it. We'd like the box to be more or less silent and quite small.

Possible candidates include the Mac Mini and the NSLU2, affectionately known as the Slug. With the Slug, I'd buy a big external drive onto which I would put a proper Linux distribution, as described on the web page. You don't seem to be able to buy small and quiet server boxes if you don't want to mess around with ordering the bits and building them yourself, which I don't.

The Mini's standard disk size is a bit small, but other than that it certainly does everything we want. However, it's somewhat pricey for a box we're not going to use interactively. The Slug is a lot cheaper but will require me to resurrect my Linux-fu (and if I want sound output, get into the sort of horrific kernel nargery that made jwz buy a Mac). I could buy the Slug and some networked other audio output thingy as I've heard you can get those these days, but I've no experience with them.

This must be a fairly common thing in other geek households. What have the rest of you done?

The recent change to LJ's URL formats seems to be part of an attempt to defend against one or more attacks which allow the attacker to steal another LJ user's credentials, gaining the ability to impersonate that user. The theft occurs when the victim visits a page on LiveJournal which contains some malicious Javascript inserted by the attacker (more technical details below for those that care).

What's been happening?

Slashdot linked to an article with some more details on the attacks. This article includes details supplied by the Bantown group (who live at bantown.com, a site you probably want to visit using lynx). Bantown have use these attacks to pwn LiveJournal quite comprehensively: the comments on the news entry contained comments from tens of different users with the same demand from Bantown. It's likely that these users all had their credentials stolen by Bantown.

I found a comment quoting an explanation of the vulnerability in an entry on lj_dev, but that entry has now been deleted. The quoted explanation is about a vulnerability which only applies to browsers based on Mozilla (so, Mozilla, Firefox and Netscape). The Bantowners claim that this is not the vulnerability they were using, as they have a vulnerability which affects all browsers. LJ recently patched a vulnerability which would do the job for all browsers, but it's possible there are other, similar, vulnerabilities in LJ's code. Or it's possible that the Bantown people are lying.

Is it fixed?

LJ went down for a while on Friday afternoon, and seems to have invalidated all existing cookies. However, bradfitz is keeping quieter than I'd like about whether the risks still exist and about what workarounds users can use while LJ's crack programmers are working on a fix. bradfitz's use of "soon" suggests that the URL change was part of further changes. These further changes aren't in place as I write this, which I think means that it's still possible to use whatever attack the Bantowners have been using to steal credentials, although it's not possible for an attacker to use an old set of credentials from logins before this afternoon.

Edited: LJ has now fixed this, so it's safe to turn Javascript on again.

What can we do about it?

For now, I'm running with No Script turned on, and using that to disable Javascript for all but trusted sites, of which LJ obviously isn't one. LJ's lack of communication about the risks to user data, and about possible workarounds, displays a worrying incompetence, as I've said elsewhere.

The Science Part

LJ uses cookies, small pieces of data stored by your web browser, as your credentials. When you log in to LJ, you get a cookie. From then on, your browser presents the cookie whenever it requests a page from LJ. LJ trusts you because you have the cookie, and lets you do things that only you should be able to do. The cookie can persist just until you close your browser, or longer if you've ticked the "remember me" option when you log in.

The attacks on LJ are cross-site scripting or XSS attacks. A Javascript running on a particular page can access the cookies for that page. Currently, any Javascript running on an LJ page can see your cookie, because the same cookie applies to the entire site. If an attacker can cause their own Javascript to run on a page supplied by LJ, they can steal that cookie and send it to a remote server that they own.

How might the attacker get their script onto LJ's pages? Well, LJ lets you submit HTML as entries, comments, and as your own styles, and then displays it on its pages. LJ attempts to sanitise the HTML you supply it, but if it doesn't do this correctly, the attacker has a way in. They can put their Javascript on the page, and visiting that page would then send your cookie to their server. Also, browsers based on Mozilla (such as Netscape and Firefox) allow stylesheet authors to embed Javascript in a CSS stylesheet, so the way LJ lets users reference their own external stylesheet is another security hole (although as I said above, it's possibly not the one that the Bantown people are using).

There's some more discussion of how this works (in amongst a lot of sarcasm) in this thread on jameth's journal.