When I worked at a larger company, as an Apple Event approached work conversation would take second place to speculation about what Apple would announce. Lunch time conversation was consumed with a battle of predictions and the white board in front of my office became the location for people to publicly make their claims. After the event we would gather around the white board and collectively determine who did the best.

I'm sure I'm not unique in this tradition among Apple fans, so in an effort to support this fun, I have created the Prediction Score Card. Download it, print it out and take it to lunch. Amaze friends with your understanding and sophisticated analysis of current reports! Show your strength of judgment in the face of swirling uncertainty!

Have some fun.

P.S. If I have missed a rumor, please let me know and I'll add it, but be quick, Wednesday is not that far away.

In college I was first introduced to this definition for algorithm:

An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time.¹

An algorithm is a defined process for getting something done. Algorithms are all around us. Recipes are common algorithms. Driving directions can be algorithms. Your morning routine might be an algorithm. How we do the things we do can often, but not always, be described as an algorithm.

In the study of algorithms, we often consider the analysis of how a process scales. That is, as inputs to the process grow to incredibly large sizes, we ask and answer the question: "What factors dominate in determining the cost, both in time and resources, of this process?" The answers to this question often take the form of common mathematical growth functions shown in the diagram below:

As you move across the x-axis you can see that each of these functions grows or increases along the y-axis. While they all grow, they do so at different rates. For example, the linear growth rate is greater than the logarithmic growth rate. In fact you can visually compare each of these curves rather easily for these small values of x, but doing this visual comparison for small values isn't where algorithm analysis normally starts. Remember the point of all this is to answer the question, "But how does it scale?" or "For very large inputs (values of x), which function increases the least?" If an algorithm's representative growth function can scale well, there's profit to be made.

For example, below is a basic chart of possibly the worst of all algorithms for sorting a list of items, namely, Bubble sort.² Imagine a machine you pay to sort items using Bubble sort. The amount you'll have to pay depends on the number of items you ask the machine to sort. The x-axis shows the number of items to sort and the y-axis shows what it will cost, in dollars.

As you can see, the cost of this algorithm grows rapidly. With only 35 items to sort, this Bubble sort machine would cost you well over $1,000 to do the work! You might recognize this graph; it is the graph of an n² function. Any algorithm that grows its cost in a way that follows the general form of an n² function we call an n² algorithm.

The "cost" of an algorithm depends on what you count. In the previous example we counted dollars spent on sorting the items. For computer algorithms the costs normally counted are space and time. Time measures how long the algorithm takes to complete as the number of items increases. Space measures how much extra memory or disk space is needed to complete the algorithm. In other fields, an algorithm's "cost" might refer to other things like money, people required or even distance traveled.

There are only a handful of general functions that are used to represent an algorithm's cost. Here they are:

It is important to note with these functions that when the number of items to process is very small, the cost difference is also relatively small. For example, consider the relative cost of processing 5 items using different algorithms, each with a different efficiency type or class. Of course, the dollar costs shown below are fictional, but it should help you compare the different kinds of algorithms. The cost difference between each class of function follows:

This table orders the function types from least expensive to most expensive at large-scale, that is, when the number of items to process is much larger than five. Even so, some of the more costly functions (Exponential for example) are actually cheaper when considered for only 5 items. Normally, algorithm analysis ignores cost at small-scale and looks at what the relative costs are when things get really, really big. Let's look at 1 million items. That's a big number, and for most people, if they sell or work with 1 million things, that qualifies as a large-scale system.

At large-scale, this kind of analysis begins to make sense. With 1 million things to process, you can really see how the order of growth changes dramatically. If you were responsible for a manufacturing plant and had a process whose cost function was an n² function and you were able to change the process to something that cost more along the lines of a "n-log-n" function, well, you'd have a competitive advantage of $999,994,000,000! That is probably enough to get you that next promotion!

Taking the time to look at your processes, or algorithms, and improving them can result in amazing economic benefits when you are working with large-scale systems. Small changes, even seemingly simple modifications in a core or costly work process can add up to huge economic returns.

What we've been discussing has a name and it is called: asymptotic complexity analysis. It's called this because as an algorithm approaches very large inputs, the cost graph "looks like" or "asymptotically approaches" one of the key functions mentioned above. For our purposes, the word complexity simply means cost.

Economics

What does this asymptotic complexity analysis have to do with Economics? Consider this definition for Economics:

Economics: the branch of social science that deals with the production and distribution and consumption of goods and services and their management.⁵

Algorithms can optimize production, distribution and consumption, and these advancements can save time and money and drive economic growth. There are large economic incentives to scale up your business and reap the rewards that come with increased size and algorithms can help you do this. Remember, algorithms define how you do what you do, and at large-scale, they really matter. The following examples should better illustrate the value of algorithms in production, distribution and consumption of goods and services.

Production

For years the US Constitution has protected manufacturing algorithms in the form of process patents. These limited monopolies began with these lines in the Constitution:

"The Congress shall have Power ... To promote the Progress of Science and useful Arts, by securing for limited Times to Authors and Inventors the exclusive Right to their respective Writings and Discoveries;"⁶

The constitutional patent protection has been further clarified as follows:

"Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement therefore, may obtain a patent therefore."⁷

The ability to secure a process patent for exclusive use has obvious economic value. If you are able to discover and patent a new, more effective process for producing a chemical, drug or other material, the process patent offers a legal protection for your algorithmic advantage. It is for this and other reasons that capturing process patents offer a significant financial incentive.

The patent protection of algorithms is not new. The first patent for a chemical process was granted in 1793 for a process used to make potash.⁸ Since then many famous chemical processes have been patented.⁹

While there are those who criticize the patent system, even some of the most ardent opponents of the current system have concluded "the patent system still appeared to offer positive innovation incentives for drug and chemical firms."¹⁰

To summarize there are at least three key ways algorithms have a significant impact on economic production:

• Better algorithms can lower production costs
• Better algorithms can allow production to scale
• Better algorithms patented can provide a competitive advantage

As companies deal with market pressures, algorithms-their discovery, improvement and protection-are an important part of doing business.

Distribution

When we think of the distribution of goods, images of trucks, trains, boats and planes crisscrossing the globe often come to mind. Certainly when you attempt to achieve large-scale distribution, the need to move goods across the globe becomes important. This kind of physical distribution is critical to many economic activities.

Overnight delivery services were largely unknown before the birth of FedEx. Yet it was an insight and an algorithm and its application to shipping that led FedEx to become a synonym for next day delivery. In his autobiographical account of starting up FedEx, Fred Smith explains how the algorithm he chose for distribution was central to his initial design for the company:

"My solution was to create a delivery system that operates essentially the way a bank clearinghouse does: Put all points on a network and connect them through a central hub. If you take any individual transaction, that kind of system seems absurd-it means making at least one extra stop. But if you look at the network as a whole, it's an efficient way to create an enormous number of connections. If, for instance, you want to connect 100 markets with one another and if you do it all with direct point-to-point deliveries, it will take 100 times 99-or 9,900-direct deliveries. But if you go through a single clearinghouse system, it will take at most 100 deliveries. So you're looking at a system that is about 100 times as efficient."¹¹

The insight was the growing need to transport goods reliably overnight and the algorithm was this "spoke and hub" delivery system. The algorithm was not new, in fact Delta was already using it when FedEx was in its infancy, but it's application to shipping and next day delivery was new.¹² For FedEx this algorithm served as their initial economic advantage.

Another example of algorithms and distribution improvements comes from UPS and their Right Turn Policy.¹³ UPS has always tried to optimize their delivery routes, but in 2005 UPS began the process of creating a new computerized route optimization system. This new system was in essence an algorithm that allowed for faster delivery of more packages while reducing costs. The new system generates delivery routes that do all they can to avoid left turns and the idling and waiting that accompany them. Ninety percent of the time, if a UPS truck is turning, it's turning right. For a company that delivers 15.8 million packages and documents around the world each day with a fleet of almost 100,000 cars, vans, tractors and motorcycles, this algorithmic improvement adds up.¹⁴

What have been the results of this optimization? In 2007 the algorithm removed 30 million miles off its delivery routes, saved 3 million gallons of gas, and reduce CO2 emissions by 32,000 metric tons, equal to removing 5,300 passenger cars from the road for an entire year.¹⁵

When it comes to distribution systems on a large-scale, the development and choice of algorithms have not only an economic impact, but an environmental one as well.

Consumption

It's hard to imagine now, but it wasn't long ago that searching for and gathering information involved travel, visiting libraries and other institutional records facilities. Google has changed all that, and at the heart of that change was an algorithm, namely PageRank.

It all began at Stanford in 1995. Larry Page and Sergey Brin met while Page was considering attending Stanford for his graduate degree.¹⁶ Part of their research was focused on a "web crawler" that would visit every web page it could find and begin to analyze the page and it's relative importance. The algorithm for determining a page's rank ultimately received the creative name of PageRank. By 1998 PC Magazine reported that Google "has an uncanny knack for returning extremely relevant results."¹⁷

How did this algorithm work?¹⁸ At the most basic level it would create a "citation graph" of the World Wide Web. Pages with more citations or links to it would be given a higher page rank. This idea was not new, but using web links and other web meta data and applying it to cataloging and judging the vast and growing data online was something new indeed.¹⁹

By August 1996, this research project part of the Digital Library Project in the Computer Science Department at Stanford had discovered roughly 75 million pages on the Internet and indexed about 30 million of them in a 28 GB database! It was obvious that the Google algorithm would need to be something that could deal with scale. This algorithm would need to deal with enormous amounts of data while still allowing instantaneous access to a constantly changing data set.²⁰

This one algorithm solved a real problem: finding relevant information when faced with the information overload online. Word spread fast and soon almost everyone was going to Google to search the web. This presented an opportunity to sell contextual and relevant ads along with the search results and the rest is, as they say, history.

In Google's case, the PageRank algorithm is perhaps one of the most useful and lucrative algorithms in recent history, but it has not come without challenges. Google has had to constantly combat those who try to game the system for profit, using the fact that a system based on an algorithm, even a "smart" one, has inherent and repeatable weaknesses.

Googlebombing is when a person or group tricks Google's algorithm to return a certain search result. Since at least 1999 people have attempted to influence the ranking of particular pages in the search results returned by Google. My first experience with googlebombing was when I was informed that the top result for the search "more evil than Satan himself" was a link to Microsoft's web page.²¹ Google resisted manually tweaking these results citing the importance of the "objectivity" of the algorithm.²² In 2007 Google changed the algorithm so that this kind of thing was more difficult,²³ but the economic incentive to be on the first page of Google's search results has continued to motivate determined hackers and business people alike.²⁴ Search Engine Optimization (SEO) is the process of changing your website's data to improve rank and relevance in the Google search results.²⁵ While there are legitimate ways to improve your rank, significant effort has been invested in finding ways to illegitimately place their website on the first page or top spot in the search results.²⁶ Additionally Search Engine Optimization scams are prevalent. It is common for a business to pay a purported SEO company for a better page rank, often with little success.²⁷

Clearly, Google's success shows that creation of a new algorithm for doing something that scales can be a critical part to business. Still, that was not enough. Google has had to continually adapt the algorithm to changes in the market. Perhaps this simply underscores the fact that the people who can invent, maintain and improve these algorithms are even more economically valuable than the algorithms themselves.

The Dark Side of Algorithms

"Not everything that can be counted counts, and not everything that counts can be counted." - Albert Einstein²⁸

One of the great things about an algorithm is the fact that it is an "unambiguous sequence of instructions." This unambiguous nature allows for repeatability and scalability, but this very strength is also a weakness. Process patents, desirable as they are, often specify in clear terms what it means to follow the process and what it means to do something different and thereby avoid infringing on the patent. Since patents are public, you are in a sense giving the competition the map to the minefield! The other and perhaps larger weakness with algorithms is that there are qualities like style, judgment, understanding and creativity that simply resist being defined algorithmically.

Clearly employing repeatable and scalable processes to produce, distribute and consume goods and services is a boon economically, but there is a dark side to this specification and reduction of all things into a "sequence of unambiguous instructions for solving a problem."

Food

Consider your personal experience with food. Have you noticed a difference between homemade meals and those produced at a fast food establishment? If you have, you probably haven't noticed that the fast food was better. McDonalds famously applied for a patent with a 55-page description of a "Method and Apparatus for Making a Sandwich" underscoring their algorithmic focus to food production.²⁹ While much of what has made McDonalds successful has been their focus on algorithmic repeatability, this has allowed for worldwide growth in scale, not deep improvements in culinary quality.

The quality of food isn't just in how it tastes, but also in how it helps us to stay healthy. Large-scale and efficient food production has been helpful in meeting the world's hunger needs, but along with the scale have come other problems. High output factory processes have created new risks for large-scale food-borne illnesses³⁰ and high yield crops can generate food of decreasing nutritional value.³¹

The Unquantifiable

"The only problem with Microsoft is they just have no taste, they have absolutely no taste, and what that means is - I don't mean that in a small way I mean that in a big way. In the sense that they, they don't think of original ideas and they don't bring much culture into their product" - Steve Jobs, 1996³²

How does one define in systematic and unambiguous terms what is original, beautiful, stylish, elegant or even culturally valuable? Some things simply resist precise definition. Additionally, there is an economic reality that often good enough is sufficient, especially on a large-scale. One can be remarkably successful without these ambiguous and intangible qualities like beauty and elegance. Certainly Jobs' assertion that Microsoft lacks taste hasn't kept the company from being phenomenally successful. Indeed taking the extra time and money to push your work to the level of art can easily be considered wasted effort from an algorithmic efficiency point of view.

On the other hand consider Steve Jobs assessment of their "system" for developing innovative products:

The system is that there is no system. That doesn't mean we don't have process. Apple is a very disciplined company, and we have great processes. But that's not what it's about. Process makes you more efficient.

But innovation comes from people meeting up in the hallways or calling each other at 10:30 at night with a new idea, or because they realized something that shoots holes in how we've been thinking about a problem. It's ad hoc meetings of six people called by someone who thinks he has figured out the coolest new thing ever and who wants to know what other people think of his idea.³³

For a company so often praised for style, beauty, innovation and elegance it's somewhat surprising that Apple doesn't have a system in place to ensure continued success along these lines. The reason for this omission is that creativity, art, style and beauty remain far outside the algorithm's grasp.

Banking

Perhaps nothing is more central to our economic system than banking. As banking operations have become more sophisticated and computer automated, the use of algorithms to make important decisions has increased.³⁴

In the past, getting a loan meant a personal visit to a loan officer of a bank and an interview. Following the interview and documented analysis of income, the loan officer would discuss the loan with a loan approval committee and make the case for issuing the loan.³⁵

Now, algorithms and risk probability models often replace this human factor. Is this better? The answer is complicated, but the underwriting of subprime loans for individuals and institutions that were unable to service the loan may not have occurred except for the powerful force of statistical algorithms and investment models suggesting it was a prudent course.³⁶ These "bad loans" contributed to the housing bubble and the current US economic climate.³⁷ We are now in the meltdown of the US residential real estate market and the beginnings of a commercial real estate depression.³⁸ Perhaps there is room for more human judgment in banking loan decisions. This brings to mind what Warren E. Buffett said about the complex securities engineered by Wall Street mathematicians: "Beware of geeks bearing formulas."³⁹

Problems of Scale

One reason to focus energy on algorithms comes from the problems associated with scale. When you grow the raw size of an organization or the customers you serve, algorithms can help you deal with that growth in a uniform way. On the other hand, this very growth can make it hard to focus. The reason that focus is often lost at scale is that a small percentage of a big number is still a big number! Even small problems are big problems when magnified by the sheer size of things. Focused efforts become more defuse, as almost any effort pales in comparison to the magnitude of the overall size of things. In this case, one's focus on size, algorithms and their efficiency are of utmost importance, but this comes at the cost of a host of smaller advancements which can be the seeds of real innovation.⁴⁰

Sometimes limiting growth can help generate profit as you focus on quality or target your product effectively. Apple has done this recently with the iPhone. While many have suggested that Apple should focus on capturing market share, Apple has been focusing on profit-share. According to a recent report, Apple made $1.6 billion in operating profit off of the iPhone in Q3 2009. In the same quarter Nokia, made $1.1 billion, but consider this: Apple owns 2.5% of the cell phone market while Nokia controls about 35% of the market! Apple's focus is on a smaller sector of the market, but a sector where they can be focused and extremely profitable.⁴¹

Apple doesn't always play only for profit share. Certainly the iTunes Music Store is a market share leader, but there is something to be learned from growth through focus rather than scale. Apple's own iPhone App Store provides another example of large-scale and the challenges of "quality vs. quantity" that often come with it.⁴²

Algorithms and Their Limitations

Thinking deeply about the core algorithms in your work can be very productive and help you gain a competitive advantage. Algorithmic complexity analysis can help you find areas where you can improve your economic returns significantly. Many great companies have at their core a collection of algorithms that form the engine of their success.

Algorithmic study makes the most economic sense on a large-scale but don't get caught up in the desire to scale. Sometimes the focus that is provided at small scale can allow you to produce things that would simply be impossible to produce in a large-scale environment. Asymptotic complexity is not everything! You can know how to do something extremely well and not be able to explain it or reproduce it at scale, yet it can still be very valuable. There are many important things that can't be succinctly described in an algorithm and this very fact may be your competitive advantage.

References

¹ Levitin, Anany V. Introduction to the Design and Analysis of Algorithms. 2nd ed. Addison Wesley, 2006. Print. ↩

² For an introduction to Bubble sort see: Bubble sort. Wikipedia: The Free Encyclopedia. Web. ↩

³ This number is very large. I used the command line tool bc, an arbitrary precision calculator, to calculate it and the result was a number 301,030 digits long! It would take 110 pages just to print this number. ↩

⁴ This number is very, very large. It's so large, in fact, I'm not sure how to calculate it. ↩

⁵ Definition of "economics." WordNet. Princeton. Web. ↩

⁶ "Transcript of the Constitution of the United States - Official." Web. 5 Dec 2009. (see Article 1, section 8, clause 8) ↩

⁷ "35 U.S.C. 101 Inventions patentable. - Patent Laws." Web. 5 Dec 2009. ↩

⁸ "BENEFICIATION OF POTASH - Google Patent Search." Web. 5 Dec 2009. ↩

⁹ Bessen, James, and Michael J. Meurer. Patent Failure: How Judges, Bureaucrats, and Lawyers Put Innovators at Risk. illustrated edition. Princeton University Press, 2008. Print. ↩

¹⁰ Ibid. ↩

¹¹ Smith, Fred. "How I Delivered the Goods." Web. 5 Dec 2009. ↩

¹² "Online Extra: Fred Smith on the Birth of FedEx." Web. 5 Dec 2009. ↩

¹³ "Right Turn at the Right Time - UPS Pressroom." Web. 5 Dec 2009. ↩

¹⁴ "UPS Fact Sheet - UPS Pressroom." Web. 5 Dec 2009. ↩

¹⁵ Right Turn at the Right Time ↩

¹⁶ "Corporate Information - Google Milestones." Web. 5 Dec 2009. ↩

¹⁷ "PC Magazine: Top 100 Web Sites (Google!)." Web. 5 Dec 2009. ↩

¹⁸ For a deeper explanation of the algorithm see the patent: "Method for node ranking in a linked database - Google Patent Search." Web. 5 Dec 2009. ↩

¹⁹ "Working Paper SIDL-WP-1997-0072." Web. 5 Dec 2009. ↩

²⁰ "Stanford BackRub Web Project." Web. 5 Dec 2009. ↩

²¹ Sullivan, Danny "Google Bombs Aren't So Scary - Search Engine Watch (SEW)." Web. 5 Dec 2009. ↩

²² "Official Google Blog: Googlebombing 'failure'." Web. 5 Dec 2009. ↩

²³ Co-written with Ryan Moulton and Kendra Carattini. "Official Google Webmaster Central Blog: A quick word about Googlebombs." 25 Jan 2007. Web. 5 Dec 2009. ↩

²⁴ "The Times (UK) Spamming Social Media Sites - Waxy.org." Web. 5 Dec 2009. ↩

²⁵ "Official Google Webmaster Central Blog: Google's SEO Starter Guide." Web. 5 Dec 2009. ↩

²⁶ "Derek Powazek - Spammers, Evildoers, and Opportunists." Web. 5 Dec 2009. ↩

²⁷ "Search Engine Optimization (SEO) - Webmasters/Site owners Help." Web. 5 Dec 2009. ↩

²⁸ Albert Einstein, a US (German-born) physicist (1879-1955). This quote is attributed to him because of sign that he had hanging in his office at Princeton. ↩

²⁹ "(WO/2006/068863) METHOD AND APPARATUS FOR MAKING A SANDWICH." Web. 5 Dec 2009. ↩

³⁰ Roberts, Paul. The End of Food. Reprint. Mariner Books, 2009. Print. ↩

³¹ Pawlick, Thomas F. The End of Food: How the Food Industry is Destroying Our Food Supply--And What We Can Do About It. 1st ed. Barricade Books, 2006. Print. ↩

³² Sen, Paul. Triumph of the Nerds. Ambrose Video, 2002. Print. Transcript. ↩

³³ "The Seed of Apple's Innovation." Web. 12 Oct 2004. ↩

³⁴ Kim, Jane J. "New FICO Credit Score Debuts." wsj.com 29 Jan 2009. Wall Street Journal. Web. 5 Dec 2009. ↩

³⁵ Clark, Kim B. Speech given at a City Club luncheon December 18, 2008 ↩

³⁶ Coy, Peter. "Why Subprime Lenders Are In Trouble." BusinessWeek: TopNews 2 Mar 2007. BusinessWeek. Web. 5 Dec 2009. ↩

³⁷ "Declaration of the Summit on Financial Markets and the World Economy." Web. 5 Dec 2009. ↩

³⁸ Foust, Mara Der Hovanesian, Dean. "Why This Real Estate Bust Is Different." BusinessWeek: Online Magazine 5 Nov 2009. BusinessWeek. Web. 5 Dec 2009. ↩

³⁹ Lohr, Steve. "Like J.P. Morgan, Warren E. Buffett Braves a Crisis." The New York Times 6 Oct 2008. NYTimes.com. Web. 5 Dec 2009. ↩

⁴⁰ Weiss, David. "Impatience and Design by Counter Example" 6 Nov 2006. Web. 5 Dec 2009. ↩

⁴¹ "While Rivals Jockey For Market Share, Apple Bathes In Profits." Web. 5 Dec 2009. ↩

⁴² Gruber, John. "Daring Fireball: Pound the Quality." Web. 5 Dec 2009. ↩

The other day I noticed one of my friends login to his laptop. I do this all the time, so that he logged in wasn't unusual, but how he did it, that caught my attention. He slid his finger on a small sensing area and after some delay he was logged in! No username and no password! This piqued my curiosity, put me on a research track. Here is what I discovered.

What are Biometrics?

When you login to your computer, security experts would say you authenticate. That is, you prove to the computer that you are indeed who you say you are. There are three ways you can normally prove who you are [2]:

1. What you know
2. What you have
3. Who you are

When you login with a password, you are using the first form, what you know. If the password is kept secret and sufficiently hard to guess, when you enter your password the computer assumes it must really be you, because no one else would know the secret password. By this logic you are authenticated. There are other ways you can prove that you are who you say you are. When you purchase something with your credit card, or unlock your car door, you are normally authenticating with something you have. When someone checks your passport picture against what you look like, this is using two forms of proof: What you are, your face and what you have, namely the passport.

So what are Biometrics? From the word you might be able to deduce some of the meaning. The "bio" part means of or pertaining to biology. The "metrics" part relates to measurement. Put together biometrics it is the measurement of biological data. For authentication purposes a biometric is a physical characteristic that can be measured and then used to identify a specific individual.

When you use a "what you are" proof, it helps that you choose an attribute that is unique. If I used my height to prove that I am who I say I am, most of you would laugh. Why? Because there are lots of other people 6 feet 4 inches tall. For a strong identification, uniqueness matters.

How do fingerprint biometrics work?

Each fingerprint contains ridges in the skin which are detectable. These ridges make patterns which you can see with the naked eye. The ridge patterns can make loops, arches or whorls. In each fingerprint there are areas where one ridge changes, these points of change are called minutia. When a ridge ends, splits into two ridge, joins another ridge or creates a island; all of these features in a fingerprint are minutia. [10]

A fingerprint scanner detects the larger ridge patterns and records the following information about the minutia:

1. Orientation - the direction the minutia is facing
2. Spacial Frequency - how far apart specific features are located
3. Curvature - the rate of orientation change
4. Position - the (x, y) location relative to some fixed point

All of these can yield up to ideally 60 or 70 minutia for a single fingerprint. [10]

When a person first configures a scanner to use their fingerprint, this is called enrollment. This is a key time where strict process must be followed so as to avoid someone enrolling another's fingerprints as his or her own. In this process several fingerprints are recorded by the system and then an averaged template of the fingerprint is stored in the system. [10]

After enrollment, when a new fingerprint is supplied to the system, a statistical match is sought. If no match is discovered, the person is denied access. If a match is found, the person is granted access. Since biometric measurement can change slightly with each scan, determining a match is a probabilistic process. There is always a possibility that a valid fingerprint is rejected or an invalid fingerprint is determined to be good. [10]

What are the advantages and disadvantages?

To compare the relative merits of fingerprint as a biometric, we can considering the following properties of a good biometric [11, 6, 3]:

1. Universality - each person has the characteristic
2. Uniqueness - the characteristic is unique per person
3. Permanence - characteristic remains the same over time
4. Collectability - how easy is it to measure the characteristic
5. Performance - accuracy, speed, and resource requirements
6. Acceptability - culturally accepted by the population
7. Circumvention - robust against fraudulent attacks

Universality

Fingerprints are largely universal. About 2% of the population can not use fingerprints due to skin damage or genetic factors.

Uniqueness

An important aspect of any biometric is that the characteristic be unique among all participants. Empirical evidence of fingerprints gathered since at least 1892, have found no two pairs of fingerprints that are identical, even between twins. [10] While this is reassuring, more recent research [13] indicates that the minutiae-based uniqueness as measured by fingerprint scanners may not be sufficient to determine individuality in every case.

Permanence

Fingerprints can be damaged and change due to manual labor or injuries.

Collectability

A key aspect of any biometric is the reliability of the measure coupled to the convenience of making the measurement. [10] Fingerprints are easy to collect and the systems today very inexpensive, around $20 per scanner if purchased in bulk.

Performance

Fingerprint recognition systems for large-scale deployments require a large amount of computational resources. For smaller populations the computational resources are smaller making this trade off allows for the current use in personal computers. Still compared with face recognition, for example, fingerprint scanners are more accurate, faster and require less computation and storage. Face recognition may seem very intuitive for humans, but the current mature computer systems are still far away from reliable face recognition in practice. [9]

Acceptability

Fingerprints are perhaps the most accepted biometric short of facial recognition. Still, the acceptance of biometric authentication technology depends on context, perceived benefit for the user and perceived privacy risks. [1]

Circumvention

Fingerprints are not impervious to attack, but using multiple finger scans can make the system harder to attack. ( see Myth Busters http://www.youtube.com/watch?v=MAfAVGES-Yc ) One method for improving the accuracy of biometric authentication systems is to enforce "two-factor authentication", that is one must authenticate by some biometric form as well as use a password or posses a token. [10] This additional factor can significantly harden the system.

Problematic Properties

Among the currently available biometrics, fingerprints have a large collection of positive characteristics. Some of the advantages of a biometric are that you don't have to remember passwords, don't have to worry about forgetting a password or smart card and it cannot be easily changed. [4] Because of these advantages systems have been developed for so called "One Touch Logon" [12] but in these systems one still makes significant trade offs between a password-based system and a fingerprint biometric based system. There are large trade offs between security and privacy [11] when using fingerprint biometrics.

Fingerprints have other problematic properties. They can be changed or damaged and some simply don't have fingerprints. Often because of these limitations fingerprint authentication systems have an alternate password based "back door" which can become the weakest link in the authentication system.

I think the biggest problem is that fingerprints are not very private, we leave fingerprints everywhere! Storing large amounts of fingerprint data in a safe way becomes a real challenge. If that data were exposed, criminals might devise a way to create fingerprints from the template data that fool fingerprint scanners. Biometrics in general are or can be unique identifiers, but they are not secrets. [7] Once a fingerprint is stolen, it's stolen for life! You can never get back to a secure situation! With a password or token system you can re-issue the token and invalidate the old token, or change the password. Not so with fingerprints! They are useful, but they are not keys. Keys need to be secret, random and easily updatable. Fingerprints are none of these things.

If fingerprint were to become the common authentication across different applications used for everything from logging onto your PC to accessing your bank account to opening your garage door, then value of stealing this information goes up significantly. At least with passwords you can spread the risk across different passwords for different services creating multiple barriers that must be overcome for full disclosure. With our fingerprints we have only ten of them.

References

[1] Heckle, R. R., Patrick, A. S., and Ozok, A. 2007. Perception and acceptance of fingerprint biometric technology. In Proceedings of the 3rd Symposium on Usable Privacy and Security (Pittsburgh, Pennsylvania, July 18 - 20, 2007). SOUPS '07, vol. 229. ACM, New York, NY, 153-154. DOI=http://doi.acm.org/10.1145/1280680.1280704 

[2] Guinier, D. 1990. Identification by biometrics. SIGSAC Rev. 8, 2 (May. 1990), 1-11. DOI=http://doi.acm.org/10.1145/101126.101127 

[3] Jain, A. K. and Ross, A. 2004. Multibiometric systems. Commun. ACM 47, 1 (Jan. 2004), 34-40. DOI=http://doi.acm.org/10.1145/962081.962102 

[4] Boatwright, M. and Luo, X. 2007. What do we know about biometrics authentication?. In Proceedings of the 4th Annual Conference on information Security Curriculum Development (Kennesaw, Georgia, September 28 - 28, 2007). InfoSecCD '07. ACM, New York, NY, 1-5. DOI=http://doi.acm.org/10.1145/1409908.1409942 

[5] Markowitz, J. A. 2000. Voice biometrics. Commun. ACM 43, 9 (Sep. 2000), 66-73. DOI=http://doi.acm.org/10.1145/348941.348995 

[6] Jain, A., Hong, L., and Pankanti, S. 2000. Biometric identification. Commun. ACM 43, 2 (Feb. 2000), 90-98. DOI=http://doi.acm.org/10.1145/328236.328110 

[7] Schneier, B. 1999. Inside risks: the uses and abuses of biometrics. Commun. ACM 42, 8 (Aug. 1999), 136. DOI=http://doi.acm.org/10.1145/310930.310988 

[8] Bergadano, F., Gunetti, D., and Picardi, C. 2002. User authentication through keystroke dynamics. ACM Trans. Inf. Syst. Secur. 5, 4 (Nov. 2002), 367-397. DOI=http://doi.acm.org/10.1145/581271.581272

[9] Zhao, W., Chellappa, R., Phillips, P. J., and Rosenfeld, A. 2003. Face recognition: A literature survey. ACM Comput. Surv. 35, 4 (Dec. 2003), 399-458. DOI=http://doi.acm.org/10.1145/954339.954342 

[10] Alfred C. Weaver, "Biometric Authentication," Computer, vol. 39, no. 2, pp. 96-97, Feb. 2006, doi:10.1109/MC.2006.47 http://doi.ieeecomputersociety.org/10.1109/MC.2006.47 

[11] Salil Prabhakar, Sharath Pankanti, Anil K. Jain, "Biometric Recognition: Security and Privacy Concerns," IEEE Security and Privacy, vol. 1, no. 2, pp. 33-42, Mar. 2003, doi:10.1109/MSECP.2003.1193209 http://doi.ieeecomputersociety.org/10.1109/MSECP.2003.1193209 

[12] Beomsoo Park, Sungjin Hong, Jaewook Oh, Heejo Lee, Yoojae Won, "One Touch Logon: Replacing Multiple Passwords with Single Fingerprint Recognition," cit,pp.163, Sixth IEEE International Conference on Computer and Information Technology (CIT'06), 2006 http://doi.ieeecomputersociety.org/10.1109/CIT.2006.128 

[13] Pankanti Sharath, Prabhakar Salil, Jain Anil K., "On the Individuality of Fingerprints (2002)," IEEE Transactions on Pattern Analysis and Machine Intelligence, http://biometrics.cse.msu.edu/cvpr2001_indiv.ps

Since the beginning of the Internet people have shared URLs with each other. Often the vehicle for sharing URLs was an email or a personal web page with favorite links. Today there are bookmarking websites where users share URLs, comment on them and rate them. [1] As the popularity of Twitter increases, more and more people are using Twitter to share URLs with each other. [2] The 140 character limit on communication with Twitter combined with the reality that many URLs are easily longer than 140 characters has given rise to more and more URL shortening services. While these services do a simple mapping, exchanging one short URL for a longer one, there are risks involved with trusting a third party to redirect you to a web page.

The basic idea for a URL shortening service is to exchange one URL that is short to another that is long. Typically the long URL is the desired destination. A person might send the short URL to a friend. When the short URL is clicked, the website looks up the longer URL and redirects the user to the longer URL. For example, suppose I just got an Amazon Kindle 2 and I wanted to share with my friends more information about it. Amazon typically has very long URLs. The URL for the Amazon Kindle 2 is as follows:

http://www.amazon.com/Kindle-Amazons-Wireless-Reading-Generation/dp/B00154JDAI/ref=amb_link_83624371_1?pf_rd_m=ATVPDKIKX0DER&pf_rd_s=center-1&pf_rd_r=0YPC2AH8155PQV3FWRPN&pf_rd_t=101&pf_rd_p=469942651&pf_rd_i=507846

That's 215 characters! I'll use this URL as the original URL with the following services to give you an ideas how they work:

bit.ly - http://bit.ly/

http://bit.ly/Z6eYE  19 characters

budURL - http://budurl.com/

http://budurl.com/bsfs  22 characters

eweri - http://eweri.com/

http://eweri.com/8rC  20 characters

hex.io - http://hex.io/

http://hex.io/ajz  17 characters

idek.net - http://idek.net/

http://idek.net/3kH  19 characters

is.gd - http://is.gd/

http://is.gd/lg7L  17 characters

lin.cr - http://lin.cr/

http://lin.cr/fvc  17 characters

POPrl - http://poprl.com/

http://poprl.com/Lm3  20 characters

snipurl - http://snipurl.com/

http://snipurl.com/cucc2  24 characters

tinyurl - http://tinyurl.com/

http://tinyurl.com/bngrky  25 characters

twurl - http://tweetburner.com/

http://twurl.nl/no316s  22 characters

urlBorg - http://urlborg.com/a/

http://ub0.cc/60/3G  19 characters

zi.ma - http://zi.ma/

http://zi.ma/65226b  19 characters

As you can see the original URL was 215 characters long, while the longest of the shortened URLs was only 25 characters long. I could post this shortened URL on Twitter and still have an expansive 115 characters left to comment on this URL. Perfect.

There are over 90 URL shortening services available online. A more complete list of URL shortening services is located at http://mashable.com/2008/01/08/url-shortening-services/.

Trusted or Untrusted

The most obvious risk associated with URL shortening is that it's difficult to know where the URL will take you, until you click it. The true destination of the URL is opaque. Often when I receive a dubious link via email, I hover my mouse over the URL, or view the HTML source to discover the real URL destination address and evaluate if I trust it enough to click. With a shortened URL, it's hard to know where it will take me, until I click it. Email Phishing scams are using URL shortening service for this very reason. [7]

Another problem with URL shortening is how it interacts with filters. A spam filter could use the URL in the past as one more hint that the email could be nefarious, but with a URL shortening service as the broker of URLs, the filter can't make any judgment about the URL. Many URL shortening services take spam complaints and will disable URLs if they are discovered to point to spam websites. [3] Some also proactively search their URLs for blacklisted websites and remove or disable these shortened URLs. [4]

Not just spam filters can be bypassed. Both Firefox and Google Chrome web browsers use Google Safe Browsing [5] a feature with warns users of malware or phishing sites. In the past using a shortened URL, instead of getting a warning message, users are sent directly to the dangerous web page. [6]

Less serious, but still problematic is using URL shortening services to hide the motive for an online review or recommendation. A seemingly objective review is tainted when readers discover that the author gets a monetary kick back for sending people to the reviewed product's site. Since shortened URLs hide the real URL they can be used to hide affiliate URLs and surreptitiously link to online stores. Most affiliate URLs are easy to spot, but when wrapped in a shortened URL, detection is more difficult. [8]

Another more remote, but still plausible problem with URL shortening is that should a URL shortening service become compromised, hacking one site would allow for redirecting popular shortened URLs to phishing or malware sites.

Getting More Transparent

Many URL shortening services have added some level of "see before you click" functionality. For example, any tinyurl can be prepended with the text "preview" in the URL and it will not redirect, but show the destination URL for inspection at tinyurl.com. Take the tinyurl above

http://tinyurl.com/bngrky

and modify it as follows:

http://preview.tinyurl.com/bngrky

While this adds characters to the URL, it allows the user to evaluate the URL before redirecting to the site. BudURL has an even more compact preview function. Just adding a '?' to the end of the URL will turn it into a preview URL.

http://budurl.com/bsfs  will auto redirect to the original URL

http://budurl.com/bsfs?  will preview the link first

Some of the services provide a little popup window that displays a picture of the webpage when you hover over the URL link.

Conclusion

A hacker or spammer is empowered by using a "benign" URL shortening service that everyone uses and everyone trusts. Once the click is made, a homographic attack may follow and will make it very difficult for a normal user to detect that they are being redirected to a phishing site. The real danger is that people have become habituated to trusting unknown links from their friends. This is dangerous because if their friend's account is compromised, it might not be their friend sending a link and the shortened URL will be clicked without concern.

An example of this propensity to click occurred 12 Feb 2009. One of my friends tweeted, "Don't Click: (link)". I was curious, but I didn't click the link. Next another posted the same thing, than another! It seemed fishy to me, and I later found out that the link presented a web page with another button that said, "Don't Click!" Naturally curious people, and trusting in their friend's recommendation, clicked the button and all of the sudden they noticed that they had in fact tweeted the same link though they never consented to doing so! It was the first socially engineered twitter virus. [9] While this virus was started as a joke, it spread extremely fast. [10] Luckily this social virus was harmless, but it reinforces how effective a socially engineered virus can be.

There are always trade off decisions to be made. In this case, the trade off is between the convenience of a short URL and the need for disclosure of a URL's destination.

References

[1] Tony Hammond, Timo Hannay, Ben Lund and Joanna Scott. - Social Bookmarking Tools (I): A General Review In: D-Lib Magazine 11, Nr. 4, 2005 http://www.dlib.org/dlib/april05/hammond/04hammond.html

[2] State of the Twittersphere - Q4 2008 Report - http://blog.hubspot.com/blog/tabid/6307/bid/4439/State-of-the-Twittersphere-Q4-2008-Report.aspx

[3] is.gd - Technical Information - http://is.gd/tech.php

[4] SURBL http://www.surbl.org/

[5] Google Safe Browsing for Firefox BETA http://www.google.com/tools/firefox/safebrowsing/  

[6] Finjan's Malicious Code Research Center, Evasive URL techniques, 25 Jan 2009. http://www.finjan.com/MCRCblog.aspx?EntryId=2153

[7] McGrath, D. Kevin, Gupta, Minaxi. Behind Phishing: An Examination of Phisher Modi Operandi. https://www.usenix.org/events/leet08/tech/full_papers/mcgrath/mcgrath_html/mcgrath_gupta.html

[8] Parker, Ryan J. Shortening (Affiliate) Links For Prettier Linking. 20 Feb 2007. http://www.ryanjparker.net/shortening-affiliate-links-for-prettier-linking/

[9] Korben. Petit cours de Twitt Jacking :-). 30 Jan 2009. http://www.korben.info/petit-cours-de-twitt-jacking.html

[10] Johnson, Clay. What is this Don't Click business? 12 Feb 2009. http://sunlightlabs.com/blog/2009/02/12/what-dont-click-business/

The Bridge Builder
by Will Allen Dromgoole

An old man, going a lone highway,
Came, at the evening, cold and gray,
To a chasm, vast, and deep, and wide,
Through which was flowing a sullen tide.

The old man crossed in the twilight dim;
The sullen stream had no fear for him;
But he turned, when safe on the other side,
And built a bridge to span the tide.

"Old man," said a fellow pilgrim, near,
"You are wasting strength with building here;
Your journey will end with the ending day;
You never again will pass this way;
You've crossed the chasm, deep and wide-
Why build you this bridge at the evening tide?"

The builder lifted his old gray head:
"Good friend, in the path I have come," he said,
"There followeth after me today,
A youth, whose feet must pass this way.

This chasm, that has been naught to me,
To that fair-haired youth may a pitfall be.
He, too, must cross in the twilight dim;
Good friend, I am building this bridge for him."

"Performance is the perceived measure of how fast or efficient your software is and it is critical to the success of all software. If your software seems slow, users may be less inclined to buy it. Even software that uses the most optimal algorithms may seem slow if it spends more time processing data than responding to the user. ... Remember that the perception of performance is informed by two things: The speed with which an application processes data and performs operations and the speed with which the application responds to the user." [1]

Instantaneous (0.1 to 0.2 seconds)
Immediate (0.5 to 1.0 seconds)
Continuous (2 to 5 seconds)
Captive (7 to 10 seconds)

If you address another human being, you expect some communicative response within x seconds-perhaps two to four seconds. ... In conversation of any kind between humans, silences of more than four seconds become embarrassing because they imply a breaking of the thread of communication. [2]

I'll say it again about the iPhone, business models need to be designed as much as the product for the market they are intended to operate in, taking the nuances of culture, socioeconomic development as well as the customer's mindset into account. That is, as Neelakantan puts it so pithily in his most recent comment, "know your customer" and that's something we know that Apple hasn't quite managed to do yet. After all, their design success is primarily through designing for themselves.