Monday, July 05, 2010

What algorithms should new CS students learn first?

Back in my college days, I tutored a lot. I actually paid my way through college by teaching computer programming to many students. At last count, I think I have taught C, C++, and Java to almost 150 students in total. And along the way, I taught them the basic algorithms they could test out.

Which brings on the question: what algorithms should newbies learn first?

From my experience, I think first-timers ought to start learning simple things (such as finding the maximum of three numbers), then progress towards slightly complex versions of these problems (such as finding the maximum of n numbers). Then they should focus on things such as finding the GCD using Euclid's method; Binary search, etc. Sorting can come next, and I started teaching my students Bubble sort (yes, I know, it's the worst performance algorithm, but easy for people to grasp, compared with Quicksort!!).

Once the students master searching, sorting, max-mins etc., I then taught them recursion. It was quite fun to teach them recursion using the analogy of a staircase ... you go down the stairs, doing something in each step as you go down and then return (or doing something in each step on your way up).

Bernhard Koutschan recently posted a list of the most important algorithms. (thanks to Daniel Lemire for pointing it out). Among my favorites for first-timers, only 2 made that list (Euclid's GCD, binary search). The rest of the algorithms in that list are a bit complex for the newbie CS students to grasp in their first semester ... at least that's what I felt during my tutoring days.

Lemire has also posted a shorter list of the 5 most important algorithms, along with a poll, in his blog. It will be interesting to see what shortlist people come up with.

Monday, March 23, 2009

Matthew Caesar's talk on Trustworthy Internet Infrastructure







Among these, Matt talked about Bug tolerant networks.

Building bug tolerant networks with bug tolerant routers



Challenges of router bugs



Solving the bug problem














Finally, Matt presented the research questions.
  • how to do voting?
  • nature o routing bugs?
  • how to achieve diversity?

They also looked into different voting strategies:






And then he ran out of time.



Sunday, March 08, 2009

On Secure Provenance and the logic behind the threat model

In our USENIX FAST 2009 paper (the "Picasso" paper), we discussed a scheme for providing integrity and confidentiality assurances to provenance of files. While this is a good first step towards securing provenance, I think there are many more issues we need to resolve.

These days, I see many security related papers advocating this or that scheme to secure objects. However, I really don't buy anything that claims to solve problems by having access control or policies. Here is why: access control works fine if the system is centralized, or the sysadmin of the system is incorruptible. However, when you have a distributed system with no control over other principals/their systems, OR when even sysadmins may become an attacker, there is no guarantee that access control constraints will be honored.

So, in the "REAL World", we can't claim to have a system that will prevent attacks from happening. With enough money, even trusted hardware devices can be breached (my co-advisor Radu Sion likes to stress on this point ... nothing is invincible). So, what can we do? We can't prevent someone from lying about themselves, or from deleting / changing things in their possession. What we CAN do is to prevent people from lying about others (i.e. "honest" others). This is exactly what guarantee we provide in our Secure Provenance work ... we prevent people from undetectably "invent" history involving other honest people.

To give a real life analogy, suppose a forger has painted a fake Picasso painting. The forger benefits here by taking his fake Picasso, and then inventing a fake history / provenance record involving his painting. He must have some honest buyers / art galleries listed in the provenance, otherwise, if the provenance only lists his cronies, it won't be believed.

The forger will NEVER do the opposite thing, i.e. take a real Picasso, and then remove its provenance and claim it to be painted by him. :)

The analogy applies to many scenarios involving data. I won't claim that it applies to all cases ... there are scenarios where the adversary might want to claim something as his own. An example would be the case of copyright disputes ... imagine two scientists bickering over who discovered something. But in most cases, the forger's goal with data is just like real life objects ... the forger wants to pass off something as what it's not ... so he needs a fake history, and that fake history must involve "honest" principals.

There are tons of issues to solve in order to have secure provenance ... but I'll write more about them later.

BTW, the painting shown above is a "real" Picasso, it is the painting titled "Dora Maar au Chat" (Dora Maar with cat). It is one of the most expensive paintings in the world; it was auctioned off in 2004 for $95 million!! Now, that has got to be the costliest painting of a cat!!

Thursday, March 05, 2009

Ouri Wolfson's talk on using IT for Intelligent Transportation

This afternoon, I listened to Prof. Ouri Wolfson of UIC talk at the DAIS seminar about using IT in managing transportation in an intelligent manner. The talk title was Information Technology and Intelligent Transportation - A Marriage Made in Heaven.

Prof. Wolfson presented some futuristic ideas ... if vehicles could talk to each other, if things such as vehicle speed, road congestion, brake malfunction etc. could be exchanged between adjacent vehicles, and then propagated to a larger area, what things can we do? Wolfson argued that we could do a LOT. For example, if a road is congested, and our car learned that, we can take an alternate route. If suddenly a vehicle in front of a my car lost control, my car could take proactive steps to avoid an accident.

There are of course sensors showing traffic congestion, but those are usually deployed at main highways. Wolfson's vision is to create a vehicular p2p system that will work for arterial roads as well. There are of course many issues such as how cars exchange and propagate the info.

Prof. Wolfson showed a small box-device that can collect vehicle movement/location info, and then transmit that to other such devices. The vision is to have these devices deployed on a large number of cars, and then beam the aggregated system state to all of these devices. The device can then show a map, and provide situational awareness to the entire set of vehicles.

The work is part of the IGERT initiative, for intelligent transportation.

My take: As a security researcher, the first thing that comes into my mind is how we would handle security issues. Thinking like an attacker, I see a lot of ways to subvert the system. For example, how do we know that the boxes are not lying and feeding fake data? If I want other vehicles to erroneously believe a side road is congestion free, move over there, and hence clear the road ahead of me, shouldn't I (or a lot of people) be tempted to do that?

Besides lying for personal benefits, there may be more sinister reasons to cheat/subvert the system. Attackers can also cause congestion, and jam critical highways. Attackers can also feed fake "accident" information to cause nearby vehicles take emergency evasive action, which itself can cause more problems.

When we take information from a mass of potentially untrusted sources, we have to be careful from the outset. Unless we can ensure the provenance of information, and also verify trustworthiness of things we get fed from others, it is better not to look at the info.

People don't even have to be malicious ... a vehicular sensor unit can malfunction ... how do we ensure it won't cause a ripple effect and mess up the entire system?

I won't even touch on the "Privacy" issues i.e. Big brother like monitoring of cars ... though this is a big concern as well.

Of course, the networking and data propagation issues are quite interesting by their own right, and that's where Ouri Wolfson focused on the talk. Quite interesting.