Interesting Stuff

Hells yeah! The Internet Corporation for Assigned Names and Numbers, the group in charge of domain registrars (who are in charge of keeping track of who owns what domain names) changed some boring policies, and my personal work indirectly affected the entire Internet. →

You may remember in November 2005 when I wrote about [1] the Sony/BMG rootkit scandal. To summarize: they put software on their music CDs that, when run in a computer, automatically installed files you couldn’t detect (this was the rootkit part) that acted a lot like malware, and screwed with your CD-ROM drivers so that if you tried to uninstall it, you could no longer use your CD-ROM drive. The intended purpose was to run DRM software that kept you from copying your CDs, and to hide this software so you couldn’t uninstall it. However, the rootkit could also be exploited by others, so that any malicious software (if installed in the right place) would go completely undetected by any antivirus program you might be running. It was nasty stuff. Sony eventually recalled the CDs and offered to give out software to remove the rootkit if you gave them your name, address, phone number, and a bunch of other information. In the meantime, the FTC ruled that the software was illegal, and Sony paid out millions of dollars in class-action lawsuits.

Why do I bring this up, I hear you ask? Well, it seems that Sony can’t let this idea die: earlier this week it was revealed that Sony is trying a similar thing with their new USB flash drives. Again, this software automatically installs a rootkit on your computer, and again this rootkit can be easily exploited by any other software to hide files on your machine. I suspect this will end similarly, with a recall and a class-action lawsuit, assuming this gets as far in the media as the last rootkit did (I hope the media picks up on this).

I remember back in the day when Sony was a great company, and I really liked them. Things seem to have changed significantly since Howard Stringer became CEO of the company (which happened about 9 months before the first rootkit scandal was born). These days, I’m really dismayed with them. I’m now going to start boycotting Sony products (which shouldn’t be too hard, since I don’t buy much from them anyway).

[1] Only half the links in my old post still work. Sorry about that. Does anyone have any good ideas for how to avoid this problem in the future?

This weekend I went to Defcon 0xF with psifer and inferno0069, and it was a blast.

• I stopped at Arby’s for lunch on the way there. I wanted two roast beef sandwiches and a small fries, the total of which came to $7.63. I then looked at their menu, and saw they still do the “5 items for $5.95” thing. So I canceled my original order and instead got two roast beef sandwiches with cheese, a medium fries, potato cakes, and a small shake. My new total: a mere $6.44. I ate about half this food, and threw the rest out. This doesn’t seem like a good business model to me, since I’m giving them less money and taking more of their food (half of which was wasted).
• On the way there, I passed the exit for Zzyzx Road. I also drove past signs for Death Valley, which was kinda cool.
• In order to raise money to help combat AIDS in Africa, the Hacker Foundation was selling red T-shirts which said
  

  HAXO(RED)

  on the front. I wanted to get one, but they were already sold out of my size. Another shirt was too nerdy even for me: it read “chown -R us ./base” Dorks!

• I became a member of the EFF! They had a wonderful panel that covered all kinds of things they’re doing. Unfortunately, this weekend a new law was passed that makes warrantless wiretapping legal, which is something the EFF has been fighting since 2005. I’m not sure how this will fit in with a ruling last year that said that warrantless wiretapping is unconstitutional, but this is certainly a dark day for freedom.
• I watched macdaddyfrosh, mtbg, and magicpacket valiantly lose at Hacker Jeopardy. but I won a T-shirt from Hack A Day.
• Mike Andrews was there incognito, but I recognized him and talked to him for a bit. He might come to give a talk at my office at some point.
• I entered the lockpicking contest and picked 15 of the easier locks (so I finished the contest in the middle of the pack with 71 out of ≈300 points). I’m pretty proud of myself, since I had never picked a lock with “real” tools before the con (though I have raked Masterlocks with a safety pin and street sweeper bristle).
• Bruce Schneier held a Q&A session! That’s right: Bruce “I am a security fucking god” Schneier. [1] It was as amazing as I had hoped. That guy is so cool. I should point out that his blog has an RSS feed on LiveJournal, to which you can subscribe.
• There were several talks this year discussing the influence the hacker community has on mainstream perception of stuff, which was pretty cool. Besides the annual “internet wars overview,” there was a talk which reviewed the recent cyberwar waged against Estonia by the Russian mob. DarkTangent himself (creater of both Defcon and the Black Hat security conventions) gave his account of the infamous Ciscogate scandal. Jennifer Granick (author of that article) also gave a talk about legal case studies; she is leaving her work at Stanford next month to join the EFF. There was also a talk about the effect that the locksport community has had on improving lock mechanisms.
• There were so many amazing talks, I’m not going to discuss them all. but here’s a list of some of the cooler topics that were discussed: encrypted VoiP clients, timing attacks for botnets, digital forensics, social engineering and NLP, stopping jerks online, the basics of hardware hacking, and XSS in social networks.
• Michelle Madigan was found to be an undercover reporter (link includes video of the incident) with a secret camera. She was outed from the conference. I wasn’t there when she was caught, but I did hear about it later that day. Press at Defcon are fine when they wear their press badges, but Michelle was apparently trying to covertly get anyone at the con to admit to a felony on her secret camera so she could do a shock report on the horrible, criminal hackers at the con (I don’t think there were many criminals there, but some reporters seem to have a penchant for fabricating stories/threats to get ratings).
• I saw an OLPC XO-1 (more information on Wikipedia). It’s smaller than I expected, but the keyboard is child-sized, which makes sense. The screen is very readable (but very small). The touchpad/stylus area is pleasantly large, though.

[1] Yes, he’s so awesome that even his tmesis gets tmesis. [2]
[2] I admit, I’ve been looking for an excuse to use the word “tmesis” for a while now.

Yesterday evening, John, Jacob (though not Jingleheimer-Schmidt) and I had a bull shoot for an hour and a half. We started out with John proposing a memory caching system which was intended to make garbage collection and blocking irrelevant. From there, the conversation natuarally progressed to online algorithms, cache-oblivious algorithms, religion, free will, consciousness, Searle’s Chinese Room argument, Chalmers’ Zombie Planet argument, qualia, logic-based representations of object-oriented programming, the lambda calculus, machine learning, finite discrete universes, quines, the Gödel processor, complexity theory, the No Free Lunch theorems, and probably some other topics that I’m forgetting. It was fantastic.

However, this, along with a couple other conversations this week, have showed me just how much I have forgotten since college. I couldn’t remember the phrase “competitive analysis” when we discussed online algorithms. I couldn’t come up with a representation of linked lists that supported the head and tail functions in the lambda calculus, and worse, I mixed up the S and K combinators and couldn’t even give the definition for what turned out to be the S combinator. Last week I mixed up pipelining and instruction-level parallelism, and couldn’t come up with the phrase, “speculative execution.” Last week at lunch I couldn’t come up with the formal definition of temperature (something about the kinetic energy of the molecules relative to each other and maybe the amplitude of the interatomic vibrations within the molecules, but what do you do if you have a singe atom?). Today I couldn’t explain why (if?) bending a piece of metal makes it harder but more brittle, or why bending a polymer makes it more maleable (though in my defense, I could explain the difference between stress and strain, and what a polymer is as well as a bunch of examples of polymers). I remember why the X combinator is important, but can’t give the definition for it or the Y combinator. Yesterday I realized that something I was working with was a metric space, but couldn’t remember anything useful about metric spaces (I got as far as knowing that the triangle inequality holds, but I didn’t remember anything else). I can no longer use LaGrange multipliers to optimize a quantity subject to a constraint (you need the two to have parallel tangents at the extrema, but I don’t remember how to find the slopes of these tangents). Last week I forgot the name of Topological Sort, let alone how it works (something related to DFS, but that’s all I came up with).

Now that I’m writing this, I’m noticing all sorts of other things that I used to know but can’t quite remember (how Java does garbage collection, queen-asking continuations in Roman Keycard Blackwood, how the telephone lab in Baby Stems worked). It’s scary to realize how much I’ve already forgotten, and know that I’m only going to forget more things from here on out. Does anyone want to have a refresher session? If so, post your questions (or answers) here!

I think that I’m going to give up trying to solve the Hat Problem, though I’ve come pretty far (for background, see my original description and its follow-up post). I’ve now solved the N=5 version (with surprising results!), and gotten a pretty good framework around the problem: My final analysis of the Hat Problem, including a reduction to the Minimum Dominating Set problem, source code for a better program to search for solutions, and an optimal strategy for N=5 →

Yesterday, I wrote about the Hat Problem. I figured out some more late last night, but haven’t had a chance to post until now. I cancelled my brute-force program because I figured out the solution to the 4-person version: have 1 person pass all the time, and have the other 3 people pretend it’s the 3-person problem. I know this because I got an upper bound on the best strategy: with N people, you can never do better than winning N out of N+1 times (so the solutions based on Hamming codes are always optimal). If you add up all the non-pass responses over all possible hat configurations, you need an equal number of correct and incorrect answers (otherwise, the chances that your own hat is red are not independent of the colors of everyone else’s hat, and probability is broken). The best you can bunch up the wrong answers is to have everyone guess wrong at the same time, and the best you can spread out the right answers is to have each right answer in its own hat configuration. So, for every time the group loses, you can have at most N wins, and the best chances you can ever get are N in N+1.

How does this help in the N=4 situation? We now know that best you can do is win 80% of the time. Moreover, there are 16 distinct hat configurations. Winning 13 of them would be more than 80%, so we must win fewer than that many. However, we can win 12 of them by reducing ourselves to the N=3 version, so we know that’s the optimal solution. For N=5, there are 32 distinct hat combinations, and the optimal strategy will win at least 24 and at most 26 of them (but I don’t know the exact answer). For N=6, the optimal strategy will win at least 48 and at most 54 of the 64 possible configurations. The brute-force method won’t finish within our lifetimes for N>4, so I can’t try that again. Any other ideas on how to progress? FWIW, I’ve found a second way to get 75% success when N=6.

(Edit: see part 3 for more on the problem)

I recently learned about The Hat Puzzle, which is a surprisingly tough little conundrum that goes like this:

N people walk into a room and a hat is placed on each person’s head. Each hat is either red or blue, and the chances that any given hat is red are 1 in 2. Each person can see the colours of everyone else’s hat, but not the colour of their own. While in the room with the hats, no one is allowed to communicate with each other in any way at all. Everyone is then lead into separate rooms, and asked the colour of his or her own hat. Each person can choose to answer or to pass. If at least one person answers correctly and no one answers incorrectly, the whole group wins. How do you maximize your chances of winning?

The naive solution (before entering the room, pick one person who will guess Red and have everyone else pass; chances of winning are 50%) seems easy enough, but there are more complicated solutions that do better. For instance, with 3 people, you can win 75% of the time: if your comrades have the same colour hat on, guess the other colour. If they have different colour hats, pass. The only time you lose is when everyone has the same colour hat. Note that a person who chooses to guess the colour of their hat is still wrong half the time (i.e. probability isn’t broken), but we’ve spread out the occurrences of correct answers and bunched all the wrong answers on top of each other. Apparently you can use Hamming Codes to win with odds N out of N+1 when N is 1 less than a power of 2, but I haven’t seen an explanation of how that works yet.

Apparently, this is an unsolved problem for all other N, though. I have written a Java program to use a brute force method to find the solutions, and it easily verified that the best you can do when N=3 is 75% (using the strategy described above). The problem with this brute force solution is that its running time is O(2^n * 3^(n*2^n)), which makes it rather unwieldy. I’ve started running the program to solve the N=4 case, and I hope it will finish by tomorrow afternoon. edit: I dramastically misunderestimated the time needed to run this program. It will hopefully be done by Thursday. I will not use it to find the solution for N=5.

As usual for subtle and tricky topics, the Wikipedia page is wrong in subtle and tricky ways (at least, it was when I wrote this), so don’t bother looking for more information there.

(Edit: I continue working on this in part 2)

This year, the Algorithms course at Mudd is using a new book, written by Dasgupta, Papadimitriou (the complexity theorist), and Vazirani (the quantum computing guy). You can view a July 2006 draft of the book, which actually looks pretty nice. It doesn’t cover all that I think an algorithms course should (in particular it handles the standard data structures cursorily at best), but it definitely skips the boring bits and goes right to the fun parts. It starts out with cryptography, then goes into matrix multiplication and the FFT (which sound boring, but are actually pretty neat problems). It even has a chapter on quantum computing!

I don’t think this will ever replace CLRS in terms of completeness, but it’s a lot more fun. Definitely worth a read if you’re looking for an algorithms textbook. and really, who isn’t looking for one these days?

(found while reading the current XKCD)

Java’s “random” number generator has some surprisingly simple patterns in it. Nearly all random number generators on computers are pseudo-random, meaning that they only seem random-ish and are not truly random (with some notable but impractical exceptions). This happens because computers themselves are deterministic and therefore inherently non-random. Most pseudo-random number generators these days use the previous “random” value as an input to create the new value, which will be used to create the next one after that (which is why plots like these are often used to evaluate the effectiveness of a PRNG: by plotting the current value with the previous one, you can see how much the values get scattered around the range of outputs). As an aside, I should note that plotting the same thing in 3-D (with the current value, the previous value, and the value before that as the 3 coordinates) can reveal other problems, such as the problems in Randu, an early PRNG. Anyway, because most PRNGs use their previous value to compute the next one, they will cycle after they get the same value twice. A good PRNG that generates n-bit numbers shouldn’t cycle until it has generated 2ⁿ of them. Java’s implementation appears to be much worse than this, which is disappointing. Come on, guys, you can do better! The cryptographically secure hash is my favourite, and I’m currently trying to prove that NC≠P using a variation of this. If it’s any consolation to Sun (the creators of Java), Matlab has similar problems.