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.

## 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.