Posts tagged ‘computer science’

Defcon review

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.

Remembering all the things I forgot

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!

New Algorithms Text

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?

∃ a Problem with the PRNG in Java

(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 2n 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.

An Algorithms Question

Define a “hub” to be a vertex that shares an edge with every other vertex (such as the middle of a star graph, or any vertex in a complete graph). Suppose we have the adjacency matrix of an undirected, unweighted graph with V vertices (so our input has size V^2). Find an algorithm with running time o(V^2) that can determine whether a hub exists in the graph, or prove that no such algorithm exists. Note the use of little-o notation: the algorithm must be asymptotically faster than (big) O(V^2).

My bet is that no such algorithm exists, but I can’t figure out how to prove it.

I’ll be at Mudd tomorrow, btw.

Integer Factorisation program

I wrote an integer factorisation program (Java bytecode also available for those without a compiler) using an algorithm I just made up, and it works surprisingly well (significantly better than brute force, not nearly as good as the best-known algorithms out there today). Yes, it still has exponential running time, but I thought it was a neat idea.

A summary of the algorithm →

For all you computer security types

I’m sure all the CS people reading this (and maybe even some of the non-CS types!) are familiar with buffer overflow attacks, and know how to both protect against them and exploit them in other people’s code, or at least have a vague idea about how to do it. However, fewer people have heard of format string attacks. Here’s a fairly detailed explanation, but I’ll summarize:

If, in your C or C++ code, you write printf(foo) (where foo is typically a const char*), it will just print foo to the screen. The one exception here is when foo contains the percent sign, in which case it prints corresponding things from the stack. If there are more %’s in the string than there are other things in the stack frame, it will begin printing out previous parts of foo itself. If foo was defined as input from a clever yet malicious user, they can craft strings that do nasty things to your program. Most importantly, they can read from (using %08x) and even write to (using %n) arbitrary locations in memory. Given that, they can pretty much do anything they want on your machine. Nifty!

The simple and obvious way to avoid this attack is to change all instances of printf(foo) in your code to printf("%s", foo) instead. The less obvious but much better solution is to not code in C or C++ ever again, and instead use a modern, high-level language like Python or Java (or if you’re Michael and worry about the speed of your program, use an actual low-level language like Assembly).

Potpourri (and remember to vote!)

There is a fantastic tech talk about how to teach computer science to kids. Too often, they see the name and think it’s about programming, and are consequently turned off to the subject. This kiwi teaches CS without using a computer, but has all sorts of fun, hands-on activities for kids to do as they learn about sorting and compression algorithms, error-correcting codes, DFAs, and other parts of CS. If you ever need to inspire kids, this video is definitely worth a watch!

Speaking of videos to watch, check out this Dove commercial. I’ve gotta give them props for that.

On a newsier topic, Bush has begun to admit that the war in Iraq is going poorly and is starting to accept the parallels between this war and Vietnam. Might this be the beginning of someone in the Republican party taking a look at reality and then accepting responsibility for what they’ve screwed up? Not likely, but a man can dream, can’t he?

By the way, please, please register to vote (and then actually vote) in the elections on November 7. In California, you need to register (which can be done at your local DMV) by October 23 (this coming Monday). As John Stewart once quipped, “this country is run by extremists because moderates have shit to do.” However, voting doesn’t take up much of your time, and can help shape which direction the country will go, even if it’s still being run by extremists. No matter which parties/candidates you support, please vote. and please take 10 minutes and read up on the parties/candidates you plan to vote for, and make sure that they really do represent your interests; too often people are elected by an ignorant population that doesn’t realize what it’s doing. You want to vote for the communist party? That’s fine, so long as you know what they stand for and agree with it. You wanna vote for someone because the politicians tell you to? that’s not so good.

So learn about your favourite party, and then vote for them!

A bit too advanced…

I figured out the “answer” to my TeX question from yesterday—it’s undecidable! There is no way I can get my code to perform correctly and still finish up in a finite amount of time. The way to show this is similar to the proof that the halting problem is undecidable.

A quick sketch of the proof →

Yes, I’m a big computer nerd. Feel free to skip this post if you’re not interested in (La)TeX.
The TeXbook is incredibly neat! →