Jacob’s Blog

I have just written a function in Haskell that will perform a binary search on a list of integers. Pass it your list, the value you’re searching for, default low and high (0 and n-1) and it will return for you the position of your value. I’m sure there are plenty of experienced Haskell coders that will tell me there’s a better way, but I haven’t heard from one yet.

binsearch :: [Int] -> Int -> Int -> Int -> Int -- list, value, low, high, return int
binsearch xs value low high
   | high < low       = -1
   | xs!!mid > value  = binsearch xs value low (mid-1)
   | xs!!mid < value  = binsearch xs value (mid+1) high
   | otherwise        = mid
   where
   mid = low + ((high - low) `div` 2)

Web browsers have been broken ever since their invention. There is a fatal flaw in every single web browser I’ve ever used, and I bet you’ve come across this flaw without realizing how serious it is. Sure, you may have felt some frustration, but it was likely undirected and you were unsure why you were angry (well, this is how I’ve felt over the years, anyway).

I’ve drawn a very simple diagram to explain how I browse the web:

The idea in the diagram is this: We start at page A and then visit the second page, B. From there, we go back to A (likely by hitting the back button) and then visit another link called C. From C, we will visit D. In our web browser’s history, this web browsing session is A -> C -> D. If you’re paying attention, you’ll notice that we are completely missing B from our browsing history. Don’t believe me? Try it. I should clarify that when I refer to the browser’s “history”, I am referring to what is generally a drop down menu coming from the back button. Opera, Firefox and Internet Explorer all behave this way.

Before the days of tabbed browsing, this type of behavior would drive me crazy. It is absurd that a browser would willingly forget massive history lists, when surely the user would intuitively assume that all pages they’ve visited in the past would be listed in the “back” button’s list. Of course, with today’s browsers, I virtually never run into this problem since I open nearly everything in a new tab. However, I’m occasionally still forced to use Internet Explorer 6, which suffers from having no tabbed browsing and no decent history list.

Why do no browsers portray the history as a tree, such as the one I’ve drawn above? Is it too hard to design a user interface that works well, or is there another reason? If anyone knows of a small, nearly-unheard-of browser that does actually represent browser history as a tree, I would love to know about it!

This image is from http://www.skype.com/allfeatures/subscriptions/#uscaSubscriptionTab.

I feel that commentary is unnecessary.

As you all surely know, I’m in a computer class this summer. Until a couple of days ago, I hadn’t been in Concordia’s computer labs since April. And since then, the powers that be here at the University changed something. When I noticed the change, it took me a good two days of pondering to figure it out. And when I did figure it out, I was blown away.

I’m not sure if a specific incident caused the change or not, but in the last few months, a major (yes, absolutely major) security flaw was fixed. I hadn’t even noticed this flaw was there until they changed the way the doors work. Then it all became clear. I will try my best to explain it here.

At Concordia – and probably every other college/university out there – Computer Science/Engineering students get special computer labs to themselves. I’m sure other departments do as well, actually. All of these computer labs are protected by secure doors. There are two ways to get in. The first is to use a key, which I expect only technicians and administration type people have. The second is what professors and students all tend to do. We all have a six-digit key that we can type into on a keypad on the door. It then beeps and unlocks itself for us. These keys are provided to us on a website (encs.concordia.ca) that we need a password to use. I think that’s pretty standard.

I’ll describe how the doors worked from September last year until April this year (possibly later, since I’m not sure exactly when the change occurred). As I mentioned briefly, the door codes are 6 digits long. Lets pretend, for this example, that the door code is 555876. If you were to walk up to the door and press a 5 on they keypad, you would get a green light and a happy beep. If you press a 5 after that, you would get a green light and a happy beep. If you continue pressing the keys correctly, after the sixth key you would get a long extended happy beep and green light, and could then go into the room. If, however, you pressed any of the keys incorrectly, you would get a red light and an angry beep. You would then have to start over and type in the code properly.

Do you see the flaw? I used these doors at least twice a week for eight months without realizing how awful this design is.

This has got to be the single worst lock design I have seen in my entire life. Most locks out there have flaws, but I’ve never seen anything this bad. (I know a lot of twist-style combination locks can be reduced from hundreds thousands of guesses to just a few thousand).

Now I’ll describe how they currently work. No matter what you press on the keypad, you will get a red light and an angry beep. If you put in the six correct digits, the door unlocks (you can imagine my original horror when I typed in the well-memorized code and got a bunch of angry beeps). If you put in just a single wrong digit, you won’t know until the door refuses to unlock after six key presses.

Just in case you don’t see how serious this was, I’ll outline how easy and trivial it used to be to break in to every single computer lab at Concordia. Here’s the algorithm for breaking into a door before April:

1. Walk up to a door when nobody is around (there are plenty of labs in empty, far-away-from-everything-else hallways)
2. Press the first digit.
3. Green light? Press the first digit again (we start by looking for 11XXXX).
4. Red beep from step 2? Press the second digit (we’re now looking for 12XXXX).
5. Repeat until you have all six, which shouldn’t take long.

I could be wrong about the next bit, so read carefully and please let me know if I made a mistake.

You should only need to press a maximum of 210 keys before you could gain access. You would need a maximum of 10 key presses to get each next digit, and you also need to press in the code you have so far (if you’re guessing the fourth digit, you have to press the first three and then make a maximum of ten guesses to get the fourth).

I think the math works out to 210 total presses at the worst case scenario. I get 210 from 10+20+30+40+50+60, which I think is correct. Now, the way the current system works, you would have no idea if you’ve made a mistake until the very end of punching in the six digits, which means you have to try every single combination. From good old fashioned high school combinatorics (and a quick refresher course from Wikipedia), we know that

Using n=10 and r=6, we get 151,200. I’ll take this number a bit further: That’s 720 times larger that the old number of 210. If we assume that a person can punch in four keys per second (I’d say that’s pretty fast), have a perfect memory, and never pause, then…

a) It would have taken them 210/4=52.5 seconds under the old system. Less than one minute to break into a lab.
b) It now takes 151,200/4=37,800 seconds, or 630 minutes, or 10.5 hours.

Of course, I assume that there is only one valid key per door, which there might not be. (I seriously hope the math above is correct.)

So there you have it! I cannot imagine any circumstance where a company thought this was a good idea. It’s like having a car that tells you how you’re doing when you’re trying to break into it.

It does make me wonder though. Did someone discover the problem and report it? Was there a break in? Did Concordia complain to the lock company? Who is the lock company?

I’m sure I could continue, but this post is probably long enough as it is.

I hope I’ve inspired some of you to check out your own university’s door locks. Are they the same as I describe? Do tell!

Music: Red Hot Chili Peppers
IBC: 66,602-72,910 (about a 100ish change)

Prepare yourselves for a tech-heavy post. Hey, at least I wrote something.

My job here in Animal Sciences at McGill is to write a Java program that a bunch of people will hopefully be using by the end of the summer. Essentially, I’m writing a new version of an old benchmarking program that they want to ditch. It was too slow and insecure. And buggy. Very buggy.

The old program was written in Visual Basic 6 over the last few years. The code base gives the impression that the program was designed while simultaneously being coded: it ended up with thousands of lines of code in each file. It’s unmaintainable by pretty much anyone except the student who wrote it a few years back (some code is commented nicely, but some of it…well, isn’t). Anyway, what I’m getting at is that the old program works alright but is excessively sloppy. One of the worst aspects is the language handling. Since it is to be used by both French and English speakers, the application needs to be able to switch languages on the fly (not that hard of a thing to do, providing you know both the languages). This was not done properly in the old program: when you change languages, only half (ish) of the program actually gets changed.

I’ve never written a program that needed to support more than one language, but it’s definitely something I’ve thought about. In my recent research, I’ve found that the solution I had in my head was close enough to reality (text or resource files containing the strings in different languages, stored separate from the program and accessed at runtime).

So remember, internationalization and localization prevents misinterpretation! (I’d love to hear crowds of people chanting this in a protest somewhere.)

The programmer who wrote the old VB program, while probably a pretty decent coder, definitely fell into many of the traps described near the end of this posting. I really hope that in two years I don’t end up reading someone’s blog describing how painful my code is to read.

Iraq Body Count range: 66,500-72,800. (up 300ish from last post)

Music: Neil Young