Posts tagged ‘cs’

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!

So, today was the Systems test. Due to high levels of both serotonin and caffiene in my body, I went into the test with a weird I WILL TAKE THIS TEST LIKE IT’S NEVER BEEN TAKEN BEFORE sort of feeling. And perhaps it was just the sleep dep (last night I went to bed around 5:30, so my guess of 6:00 wasn’t too far off), but I think I did pretty well on the test. Systems is my favorite class, so I enjoy studying the material, even if I’m up to horrible hours of the morning doing so. But tonight I get to sleep! Oh frabjous day!

Let’s see… news… people recently discovered a new species of hominids in Indonesia. The weird thing is, this species only grew to be about 3 feet high, so the excavators have dubbed them hobbits. Nifty! (Original publication here)

Not a happy camper…

Sunday night, I went to bed at 3:00AM. Monday night, I went to bed at 4:30. We’ll see when I go to bed tonight, but I think that 6:00-7:00 is a realistic time, unfortunately. I’ve just gotten back from spending 9 straight hours in the CS department (10.5 if you count the Pomona CS department too), and because it was sunny when I went in, I was in a T-shirt and shorts. It’s now raining quite hard out. I am cold, wet, tired, stressed, frustrated (the mock ACM didn’t go as well as I had hoped), and have to study for a test. Systems is fascinating, but I don’t feel that I have a good handle on the material, and I’m still 50 pages behind in the reading (this is one of the few technical classes where you actually, really, seriously have to do the reading). So… yeah. I expect that starting Thursday night life will be good, but in the meantime, I might be a bit on edge.