Sunday, December 5, 2010

Adventures in UNIX: Pipe buffer edge cases, half-open sockets

So yesterday I had a really neat idea: exposing pipe-based programs as network services. You could open a connection to a program, send it data, and the remote computer would put it through some predefined command and send it back. Then I realized that with IPv6, you could give each program its own IP address, and give them all names in the DNS, so that you'd have a perfectly usable system without using any higher-level protocols than DNS and TCP. Then I realized that this would be simple enough that you wouldn't even need to write any code to make this work - it's all doable with simple shell commands! (I was wrong about this last one, and that's the topic of this post.)

(By way of comparison: This is sort of an inversion of the Plan9 model of network computation. Instead of mounting a remote filesystem and piping it through a local program, you're piping local data through a remote program.)

Pipes are usually a one-way structure, but for this to work properly, I needed something a little more exotic. I need to be able to take output from a command, and pipe it back around to the beginning of the pipe, so that the pipe has a loop in it. If I could do that, I could combine netcat with any command, and that'd be a one-liner that implements a server. :D

So here's the first thing I tried.

Server:
mkfifo t
while true; do nc -l 127.0.0.1 9999 < t | tr a-z A-Z >> t; done
Client:
nc 127.0.0.1 9999 < testdata

In a perfect world, this would work! But here's where we get into the details of pipe buffers.

The first problem with this is in the server. When you use a pipe, data's actually buffered along the way, in the commands that are being piped. Normally, this is transparent, because the buffers are flushed out when the previous command exits. This doesn't work when you have a loop through a fifo, though! The data that's buffered in the tr command doesn't get flushed to the fifo until netcat exits, and so netcat never actually has the chance to send the tail end of the data. The only way I could think of to solve this was to write some code for the server - pretty disappointing, but probably necessary. (I'm not going to post that code here, because it's even messier than being a prototype should justify. >_>)

But that's not all - it turns out the client part is broken, for a completely different reason. When you give netcat an EOF (Ctrl-D), it doesn't know how to tell the remote side of the connection that there was an EOF. The server then doesn't have any way to know when to flush the buffers out and end the command, so the whole thing deadlocks waiting for more input that's never coming.

It turns out that TCP solves this problem; the bug is in netcat. With a TCP socket, you can close one direction of traffic, but keep using the other - for example, when you're done writing data to a socket, you can shut down the socket for writes, which signals to the remote side that you're done writing, and then read whatever the server sends back. This, unfortunately, required more code.

netpipe.py:
import sys
addr = sys.argv[1]

import select
def attempt_read(s, BUF_SIZE):
    if select.select([s], [], [], 0)[0]:
        return s.recv(BUF_SIZE)
    return ''

import socket
s = socket.create_connection((addr, 9999))

BUF_SIZE = 4096
buf = sys.stdin.read(BUF_SIZE)
while buf:
    s.sendall(buf)
    
    sys.stdout.write(attempt_read(s, BUF_SIZE))
    sys.stdout.flush()
    
    buf = sys.stdin.read(BUF_SIZE)

s.shutdown(socket.SHUT_WR)

buf = s.recv(BUF_SIZE)
while buf:
    sys.stdout.write(buf)
    sys.stdout.flush()
    buf = s.recv(BUF_SIZE)

(This is trivial enough that I'm planning to port it to C soon.)

Finally, some good news: this works perfectly! :D With this, you can open a connection and use it as a component in a pipe.

Wednesday, December 1, 2010

p2p DNS

Now that the US is considering forcing pirate domain names out of the DNS, one of the founders of The Pirate Bay is floating the idea of a p2p DNS alternative.

Okay, wow. This is an incredibly terrible idea.

I'll start with the obvious objections:

  • The DNS is meant to be authoritative
  • In a p2p system, you don't know who you can trust, because everybody else is just a peer. The DNS is completely useless if the results you get back aren't authoritative. Some people are proposing web-of-trust type solutions, or other idiocy. NO. Web-of-trust doesn't scale, and requires too much human maintenance to ever work. Even being able to compute some kind of transitive trust metric is an open research question, and then there's the so-far-intractable problem of picking a trust metric. Any answer you get from a p2p DNS system will be unreliable.
  • The DNS is meant to be reliable
  • DNS is meant to be a transparent layer, when you're using the Internet. It's something that you just sort of expect to work, and bad stuff happens when it doesn't. And the thing about p2p systems is, it's actually pretty near impossible to make any guarantees at all about their behavior. I've actually read a lot of papers about building distributed storage systems. And you know what? Nobody's ever actually managed to get anything better than a relatively weak statistical guarantee about any property of a p2p storage system. For the DNS, that's simply not good enough.
  • Performance
  • The DNS has pretty tight performance constraints, and p2p systems (for all their advantages) are extremely vulnerable to DoS attacks. It's pretty much inherent in their design - any p2p system will require a peer to have fairly complex communications with a lot of other untrusted peers. And, as many people have shown over the years, when you manage to take down the DNS with a (D)DoS attack, people tend to flip out.
  • Secure decentralized systems are HARD
  • Look, it's not like it's impossible for random people on the Internet to band together and write a program. It's not even that difficult; open source has proven that. What is hard is getting random people together to solve a fundamentally hard problem in computer science. Let me put it this way. If a well-respected professor of computer science were to propose a p2p DNS system, I would treat it with heavy skepticism. If Peter Sunde proposes it, and expects the Internet hivemind to just sort of blast through all the hard problems by sheer virtue of wanting torrents, then I just laugh. (And then, if it looks like people are taking him seriously, I write a blog post like this.)

There are some people whose first reaction to any data management problem is to try to stick it in a magic DHT and forget about it. In many cases it works - see BitTorrent, for example. A DHT will work in any application where you don't especially need data to be reliable or trustworthy; it's a perfect fit for BitTorrent peer exchange, where reliability is optional because the DHT is only a backup for the real tracker, and trustworthiness doesn't matter because the peers aren't trusted in the first place. For the DNS, though, a DHT is exactly the wrong solution.

It may be possible, someday, to fully decentralize the DNS. To do it will take some fundamental advances in computer science, though, and Peter Sunde isn't going to be able to make that happen by rallying the pirates to his cause.

Tuesday, November 30, 2010

Julian Assange is a Terrorist (and I mean that in a good way)

Politicians want to classify Julian Assange as a terrorist. Insane? Only at first glance.

I've been reading about something that Assange wrote a few years ago, which basically lays out his plans for Wikileaks. It's actually a pretty neat read. Summary: Assange sees today's American government as some kind of corporate conspiracy (can't argue there), and he wants to throw sand in the works of the conspiracy by increasing the cost of secret communication (without which any conspiracy dies). He intends to do this through random attacks on government secrecy, with the goal of forcing an expensive overreaction, which will end with governments being less secretive.

My first reaction: This dovetails perfectly with a blog post that I've been meaning to write (but will probably never get around to) about the tradeoff between trust and robustness in a networked system. It's actually a really cool tradeoff - trusting another entity in a decentralized system can be viewed as a dodgy optimization, which will usually work but occasionally crashes dramatically. (Bonus: the tradeoff even has a mathematical basis, in the FLP result!) Julian Assange is giving us a real-world demonstration of this principle, by poking at the relatively cosy relationships between governments and forcing them to shift into a less useful but more secure configuration.

My second reaction: You know how the .gov has been making a lot of noise about info-terrorists, even though they have no idea what that even means? DDoS kiddies are usually held up as an example of what to watch out for, but that stuff is so trivial that I'm surprised we waste our time talking about it. Julian Assange, on the other hand, is the real deal, and he's not even terribly sophisticated. He is using the power of the Internet, and the power of the (relatively) unrestricted flow of information, to do something radical to the state.

My third reaction: Oh, man. The government doesn't know how bad this could have been. If Wikileaks had wanted to publish this stuff anonymously, it wouldn't have been terribly difficult for them to do so. The technology already exists, and has for years; it's just a matter of using it effectively. They don't like their diplomatic cables being made public as it is; imagine how much it would suck for them to have a few thousand cables appearing every month, and to be completely unable to track where they were coming from. You know how I said that Assange wasn't terribly sophisticated? If he were, he'd be doing exactly what he's doing now - we'd just have no idea who he was.

Last reaction: I can't help but worry that Julian Assange is gearing up for a dramatic exit from this world. He is simultaneously making himself extremely visible, and making a lot of very powerful enemies. Wikileaks has already published an insurance file; that's not the sort of thing you do unless you expect to have a reason to use it. If Assange does end up assassinated, that may be all the proof we need that something like Wikileaks is desperately needed in today's world.

Monday, November 29, 2010

Rewind

So I read the Void Trilogy by Peter Hamilton a few weeks ago, and one of the subplots went like this: in a world of psychics, one young man has exceptionally powerful abilities. Throughout the books, he learns of increasingly incredible things he can do, until he realizes that he can turn back time itself. Specifically, he can think about any moment in his past that he can remember clearly, and rewind the universe back to that moment (but with all his memories intact). This is where things get a little bit nuts.

For the rest of the book, he tries to make everything right with the world, because he's that sort of character. It takes a terrible toll on his mind at times, but in the end, he lives a life such that there's nothing he wants to go back and fix, and he has reached fulfillment. Happy ending, right? And then he goes and, on his deathbed, gives the secret of turning back time to everybody else in his city - and this is where my brain implodes in dismay.

If zero people know how to turn back time, then things make sense, and history proceeds in a boring linear fashion. If one person knows how to turn back time, then things are still simple enough to wrap your head around, because you can trace a single thread of narrative throughout whatever they do - by designating them the "main character" in the story, the story makes sense. But if two or more people know the secret, then things get Terribly Complicated.

Here's one trivial example of how screwed up the universe would become: imagine a game of Rock-Paper-Scissors between two especially competitive people that know how to turn back time (Rewinders?). The entire universe would be locked in a loop until one of them got bored.

There are weird issues surrounding seniority. If two Rewinders are going back and forth on something, the winner is going to be the one that can go the farthest back - back to before the other one existed, perhaps. If we follow this train of thought, then the winner in any conflict is going to be whoever is the oldest.

On the flip side, there are weird edge cases around death. If I sneak up on someone and kill them before they can react, then that's it for them, I've won, no second chances. This is the only way I can see to break out of a loop without first going through the infinite regression tango, and giving the victory to the older person. A world full of Rewinders would have a lot of immortals trying to kill each other, really - sort of like The Highlander but with more mindfuck.

I'm not really going anywhere with this post. Honestly, I just thought it'd be fun to actually think through some of the consequences of a world with Rewinders. :D

Sunday, November 28, 2010

Diaspora!

So at the beginning of this summer, a group of NYU CS students started on a project to build a decentralized social network, and then made waves when they raised over $200,000 on kickstarter, a crowdsourced funding website. They then proceeded to disappear into a cave for the entire summer, which killed the buzz around Diaspora pretty effectively. Then they put the project up on Github, and people immediately jumped all over them for security flaws. (Personally, I would expect to find security holes about that magnitude for a project this young. You fix them, and you move on.)

If I had to give my opinion of the project, it's somewhere around "cautious optimism". I'm not a Ruby or a Rails fan, but there are worse languages/frameworks they could have used. I think they're striking a reasonable balance between developing in secret and developing in public. On the one hand, they promised to make everything 100% open source, but on the other hand, the open source development model is pathologically incapable of making design decisions, and for the initial stage of a project you're making nothing but. I definitely like that they're piggybacking on existing protocols.

Apparently, they were inspired by Eben Moglen's idea of a "freedom box", which makes me sort of nervous, actually. Nervous, because the idea is good in principle, but completely unworkable and sort of silly in practice. Yes, it would be useful if we all had physical control of our own social media profile, but this has tremendous implications for the reliability of the network as a whole - if my Internet connection goes down, to what extent do I disappear from the web? And, of course, I'm glossing over all the real difficulties with hosting a website on a residential Internet connection. Quite simply, our infrastructure isn't up to the job, and I don't expect that to ever change. So, I kind of hope that the Diaspora devs aren't going to waste too much time on this particular use case.

There are also a ton of fundamentally hard problems that they are going to run into, and while I remain optimistic that they're thinking about them, we won't really know how they handle them until the software is in a more complete state. For example: how do you handle security updates in a worldwide distributed system? There are already a ton of insecure Diaspora instances running around in the wild, that people brought up as soon as the code landed on Github, and the problem is going to get worse unless they do something about it.

Overall, I have high hopes for Diaspora, but it's simply too early to make a call about the project. I'm expecting it to advance rapidly, though, and we may be looking at a 1.0 release within a year. Whether or not it's a "Facebook-killer", like people want it to be, it has a lot of potential to be a useful tool.

Saturday, November 27, 2010

Wallet

I seem to have lost my wallet! It is fucking with my head like you wouldn't believe.

I have looked everywhere. I have looked everywhere at least twice. I've crawled on the ground looking underneath maybe half the furniture in this house. I've torn my room apart - I don't think there's a square inch in there that I haven't looked at today, except for maybe spots that you have to disassemble furniture to get to. I have taken all the cushions off of all the couches, I think. I've called the last place I saw the wallet, and since I came home straightaway after that and haven't really gone anywhere since, there are no leads there. I am this close to trying to figure out a tactful way to call up everybody that was here for Thanksgiving and asking if they walked off with my wallet. Like I said, fucking with my head.

Why am I freaking out so much? This is my first time losing my wallet, and I suppose my first time finding out just how much of a pain it is. If I can't find it before my flight on Sunday, I'm going to have to cancel my credit card and debit card, replace my insurance card, replace my Social Security card, replace my ORCA card (free bus rides, one of many Microsoft perks) so I can ride the bus to work. (By a sheer stroke of luck, I still have my driver's license; don't even ask. XD)

And then, I have to figure out how to keep this from ever happening again. Because, see, I can't just leave a problem like this alone, and deal with it when it comes up. I'm a pathological overthinker. My reaction when a hard drive fails is to create increasingly elaborate system of redundant storage, culminating in what I built earlier this month. My reaction to almost losing my cell phone is to keep multiple backups of all the data on it, just in case. Now that I've lost my wallet once, I'm not sure that I'll be able to ignore the possibility of it happening again - my brain just doesn't work that way. I don't know how I'll solve the problem of randomly losing things that I need to carry around everywhere I go, but I know that I'll be kind of agitated and jittery until I do - it's just how I'm wired.

My mom, bless her heart, tried to help - not by helping me look, but by trying to make me feel better about losing my wallet. Frankly, it just made things worse. She asked me to imagine the worst-case scenario; thanks for the completely generic advice! I definitely feel inclined to sit and listen to you, when I know that you're taking this far less seriously than I am! Plus, I know on an almost subconscious level that she's just trying to make me feel better, and that's not what I want. I don't want to feel better about it, and I don't want to sit down and think about "how bad could it really be". I want to find my goddamn wallet. If all your help means to me is that I have to act calmer while I'm searching frantically, then please, just stop trying.

Anyway, I haven't given up yet. I still have another day to try and figure out where it went. I am convinced that it's still in this house somewhere, and that's the most incredibly frustrating thing - it's so close, but I may not have enough time to find it! Still, I've got until my flight on Sunday. Once I get on the plane, then I'll give up, and start figuring out what all I need to replace. Until then, there's still hope.

Friday, November 26, 2010

The Science of Code

Found this blog post today via reddit. It has a really cool insight: The way people work with code is evolving into the same patterns that exist in the sciences today. At the one end you have the "physicists" - people that work with code on the lowest levels (either machine code, or algorithms, depending on your interpretation), and that can expect mathematical certainty. At the other end, you have code "biologists", that mostly work with whole organisms/programs, which are messy things, but which mostly work in mostly predictable ways.

There are a few neat consequences that you can pull out of the analogy. First, while wizards slinging machine code and novices putting scripts together are both "programmers", we probably need new designations for them, in the same way that you can't always lump physicists, chemists, and biologists together as scientists. Second, even though scripting is perceived as easier than low-level programming today, that could be because of the relative immaturity of the field, and not because it's inherently easier. See this comic, for example: physicists can look down on biologists, but biology is hard! Physics can be seen as the ultimate reductionism, and other sciences are simpler in terms of the physics they use, but harder precisely because they can't afford to reduce everything to that degree.

Higher-level programming languages, then, aren't just about simplification - they're also about specialization. (Maybe this is why domain specific languages (DSLs) are a big deal today? By creating a new language, you're jumping ahead of the existing languages in terms of specialization, which is akin to opening up a new field of study in our analogy.) By leaving some of the complexity of the lower levels behind, you're able to create new abstractions and concepts, which are interesting in and of themselves.

I think the analogy actually outstrips modern programming practices by a bit. If you want to write "organic" code, for instance, you need a specialized language like Erlang, since as far as I know it's the only language designed to handle failures of different parts of the program, and keep on running smoothly. Current languages mostly have the assumption that any fault is reason to terminate the program, because the whole thing should be 100% correct. From a physicists perspective, this is fine - if it's not 100% correct, you can't count on it doing anything right! I'm coming around to the "sloppy code" view the more I think about it, though.

The assumption that all code should be 100% correct is unreasonable in this day and age. It pains me to say it, because it goes against everything I've been taught (and quite a bit of what I've said in the past). All code is going to be a bit sloppy, simply because it's written by humans, and not by the faultless code-writing machines that those humans fancy themselves to be. What we need in the next generation of languages is more robust mechanisms for handling incorrect code; if we don't do that, we're not really designing languages to be used by human beings.