March 29, 2024

Why So Many False Positives on the No-Fly List?

Yesterday I argued that Walter Murphy’s much-discussed encounter with airport security was probably just a false positive in the no-fly list matching algorithm. Today I want to talk about why false positives (ordinary citizens triggering mistaken “matches” with the list) are so common.

First, a preliminary. It’s often argued that the high false positive rate proves the system is poorly run or even useless. This is not necessarily the case. In running a system like this, we necessarily trade off false positives against false negatives. We can lower either kind of error, but doing so will increase the other kind. The optimal policy will balance the harm from false positives against the harm from false negatives, to minimize total harm. If the consequences of a false positive are relatively minor (brief inconvenience for one traveler), but the consequences of a false negative are much worse (non-negligible probability of multiple deaths), then the optimal choice is to accept many false positives in order to drive the false negative rate way down. In other words, a high false positive rate is not by itself a sign of bad policy or bad management. You can argue that the consequences of error are not really so unbalanced, or that the tradeoff is being made poorly, but your argument can’t rely only on the false positive rate.

Having said that, the system’s high false positive rate still needs explaining.

The fundamental reason for the false positives is that the system matches names , and names are a poor vehicle for identifying people, especially in the context of air travel. Names are not as unique as most people think, and names are frequently misspelled, especially in airline records. Because of the misspellings, you’ll have to do approximate matching, which will make the nonuniqueness problem even worse. The result is many false positives.

Why not use more information to reduce false positives? Why not, for example, use the fact that the Walter Murphy who served in the Marine Corps and used to live near Princeton is not a threat?

The reason is that using that information would have unwanted consequences. First, the airlines would have to gather much more private information about passengers, and they would probably have to verify that information by demanding documentary proof of some kind.

Second, checking that private information against the name on the no-fly list would require bringing together the passenger’s private information with the government’s secret information about the person on the no-fly list. Either the airline can tell the government what it knows about the passenger’s private life, or the government can tell the airline what it knows about the person on the no-fly list. Both options are unattractive.

A clumsy compromise – which the government is apparently making – is to provide a way for people who often trigger false positives to supply more private information, and if that information distinguishes the person from the no-fly list entry, to give the person some kind of “I’m not really on the no-fly list” certificate. This imposes a privacy cost, but only on people who often trigger false positives.

Once you’ve decided to have a no-fly list, a significant false positive rate is nearly inevitable. The bigger policy question is whether, given all of its drawbacks, we should have a no-fly list at all.

Comments

  1. In addition to false positives, one should also consider the fact that “the list” appears to be incredibly easy to fool (it doesn’t even “know” that “James” and “Jim” are variants of the same name), which makes it not only annoying, but also very ineffective.

    TSA is supposed to roll out their new Secure Flight Program (I think, in early 2009) and, according to them, there will be some improvements. It sounds, however, that in order not to be subjected to additional screening passengers whose names are the same as those on the list will have to provide additional information about them in order to avoid the hassle.

    Some more info can be found here http://www.1stopit.net/cms5/node/2

  2. Very detailed step-by-step explanation here:

    http://www.guardian.co.uk/usa/story/0,,2064157,00.html

  3. Ever consider that getting people used to being searched and needing lots of papers in order whenever they travel, at first without any real adverse consequences beyond nuisance delays, might serve another purpose?

    Besides, the real reason for the gatorade bomb plot and response was as a pretext to force everyone to pay for drinks on the flight or go thirsty. Which reminds me — baggage searches for illicit candy and drinks are coming soon to a theatre near you; remember, you read it here first!

  4. When they started running a vacuum over your hands to search for nitrates it was getting a little silly but kind of plausible. Then, later the story was that they no longer ran the vacuum over your hands because the vacuum itself left a residue on your hands — short fibreglass needles that get into your eyes if you wipe your eyes with your hands. They decided it was better to run the vacuum over your phone and clothes instead on the basis that every terrorist must have a phone and if the fibreglass needles get on your phone and clothes then that is much safer than getting them on your hands.

    But, when people with no airline tickets and no passports were arrested for plotting to mix gatorade, peroxide and an iPod in an attempt to convince the population that liquid explosives were the next big threat to the civilised world and as a consequence no one is allowed to take a drink of water onto a plane… I finally understood what a big, sad joke our system of decision-making has become.

    I guess I blame the lazy people who want a good life without making an effort to study and think and learn. I blame our education system for failing to teach people how to study and think and learn and to some extent I blame myself for being smart enough to see exactly where the problem is but not smart enough to think of a way to fix it.

    Of course, Darwin must offer some degree of favour to stupid people or else every creature on earth would be a genius by now. Studying the “Cultural Revolution” in China provides one possible explanation of the mechanism. A truely intelligent agent knows the right time to pretend to be stupid, but that is an admission of both defeat and selfishness and maybe there’s still a way we can make this work itself out to a better conclusion.

  5. Adam, got to ask, but why do you think that being forced to be searched and interogated whenever you wish to travel is no big deal? I seriously resent that my government and your government both seem to love this security theatre.

    Next time you are running a little late for a flight, and you don’t get stopped, thank your lucky stars that even the TSA accept that Adam Smith was a revolutionary a long time ago, and so everyone called Adam shouldn’t be stopped, and made to miss the plane.

  6. The misspelling/nonuniqueness/easy-changeability problem with names can be addressed. First, the name on the passport can be used, regardless of any other ID. Then changing the name requires obtaining a phony passport, or using other phony ID to get a genuine-but-new one. But it can be taken further. Instead of a name, use a numerical GUID on the passport. Or fingerprints… A GUID can use the same type of check-digit schemes to detect misspellings as used in credit-card numbers, cheque and account numbers, social security numbers, and even zip codes.

    Of course, taking everyone’s fingerprints or issuing GUIDs will really rile up the folks on the left, and get the ACLU in particular up in arms … 🙂

    None of which addresses the more fundamental problems identified with the secret-ban-list approach. Plastering airports with “most wanted” posters makes more sense. You’ll now have millions of eyes all over the airport surveilling it, all of them connected to facial-recognition software far superior to the dodgy computer-implemented recognition code that’s been tried so far. None of those crowds of embarkees will want to get on the same plane as anyone on the most-wanted list, and they’ll all remember 9/11 … that’s lots of motivation to note those faces and keep an eye out, in general but especially at the boarding gate or actually on board before takeoff. Add that most of those people are armed with cell phones, and nobody on the list will be able to go near an airplane without triggering a storm of 911 calls and a quick police response. They might even wind up Maced and undergoing citizen arrest. Of course, the odd one might get a less legitimate dose of vigilante action, but what the hey. The real downside is the nonnegligible chance that every Arab-looking person that vaguely resembles any of the wanted posters will trigger an alert, and no-one else. But that really speaks to a distinct problem that needs its own solution anyway…

  7. From a security standpoint a no fly list is a complete failure. In a free society it’s an abomination.

    1: If somebody is dangerous enough not to be allowed to fly he should he should be charged with the crime or cleared. In most modern societies the state has to go through a court before dealing out punishment to people. I don’t really understand how any American can accept the state creating secret lists of “evil” people and punishing them without any proof…

    2: A no fly list is an expensive an extremely inefficient tool. It assumes that you know the names of your attackers, which you in most cases do not know. Furthermore it assumes that your attackers do not use fake identities, which they tend to do if they want to hurt you. Last, an attacker can easily test if an identity is on the no fly list or not. Just walk to the airport and check in. If you trigger the list you will learn about it. It’s trivial to bypass.

    Can you please stop this security theatre and spend the money where it matters? It’s a typical example of a security measure that hurts the common people and gives the state more power without actually stopping any attacker. It’s almost as bad as random bag searches in the underground…

  8. Why would the Bush administration have this grand conspiracy to make its political opponents endure a 15 minute hassle with people at an airport? Clearly they still get to where they are going, and the potential downside of such a conspiracy being exposed would surely outweigh the upside of creating a minor inconvenience for their political enemies. Frankly, I fail to see the upside of it at all.

    I think that the simplest explanation is the one that Prof. Felten seems to believe: that the no-fly list simply is set up in a fashion that generates lots of false positives, especially so in the case of people with very common names.

    The notion that the some people have speculated that the NSA is monitoring Dr. Murphy’s phone calls so that they can put him on a no-fly list so that he has to endure a momentary annoyance before getting on a plane is frankly bizarre, and not grounded in reality.

  9. I agree with Matt B. The secrecy of the list is the most suspect thing about it. Why do we not have “Most Wanted” posters floating all about detailing who these “Most Dangerous Terrorists” are, their alleged crimes, and their descriptions. The FBI keeps a public most wanted list, why not the Theatrical Security Agency? Further, “Most Wanted” lists have proven to actually work in many cases, check the show America’s Most Wanted. As long as the list is secret, it will be used by some level of government to harass law abiding citizens, it is simply too well established that this is how governments behave to claim it won’t happen in this case.

    Regarding Dr. Murphy’s experience, why was he not stopped during any previous air travel before he gave this particular speech? The coincidence alongside the secrecy casts some suspicion over the “just another false positive” claim. Due to the secrecy neither side can be proven.

  10. Look, if the reason for a no-fly list is that there is a serious danger to allow those people to fly, then that list should be public, as well as the reasons they are on the no-fly list. It should not be secret, and the process should not be secret. We can argue about false positives vs false negatives, and the balance thereof, all we want, but the bigger issue is why is it secret?

  11. I think it is okay to have the system’s algorithm return fairly high false positives. People need to be protected from potential terrorists and a little extra time and checking out makes sense when doing so.

  12. Another Kevin says

    @Brad Templeton – I wasn’t suggesting that we balance the total harm of false positives against the expected harm of false negatives; rather, I was saying that is the most aggressive standard that a nominally free society should tolerate, and that the current security screening system fails even by that standard. Whether we ought to have greater restrictions on government interference than a strict utilitarian balance is a question that I intentionally do not address. It is perhaps unwise to state that the Bill of Rights is a desirable law.

    @Neil Mix – We have quite a good idea of the false negative rate at airport checkpoints. There have been four suicide attacks on commercial aircraft since the dawn of commercial aviation. The true positive rate is the number we don’t have – but I daresay that if there were significant true positives, the government would surely make a spectacle of them. That’s one spectacle that I haven’t seen our government making.

  13. The elephant in the room is that we don’t know the false negative rate nor the true positive rate. I suspect this is what leads many to believe that the false positive rate is proof of mismanagement — there’s no other evidence available with which we can judge the results of the program!

  14. A minor quibble. The suggestion that we balance the total harm of false positives with the expected value harm of false negatives is only true by a utilitarian standard. There are other, non-utilitarian codes of governance which also apply, and which may actually tolerate greater risk of false negatives, at least up to a point. For example, the bill of rights in theory prohibits the government from taking certain steps, no matter what the consequences of increased false negatives, though there will always be suicide-pact arguments.

    In practice though, governments seem to find ways to declare certain rights invalid in their security checkpoints.

  15. The government knows that terrorists are effective not because they kill people (many other things do a far better job), but because they terrorise the population simply by threat (amplified by precedent).

    The government does not actually have to prevent terrorists commiting crimes such as mass murder (one of the things it can’t do if it is to uphold a free society – it can’t prevent anyone committing crimes). What it has to do is to counter the terror.

    No-fly lists, proscribed luggage item, racial profiling, etc. It doesn’t actually matter that in terms of effectiveness these border upon superstitious talismans against evil, the point is that they are effective in countering terror.

    The no-fly list is not directed at terrorists (potential or real), but at law abiding citizens – precisely so that society feels comforted and the terror is assuaged.

    So, no-fly lists work.

    This is precisely the same basis for the ‘Blogger’s code of conduct’. It’s not designed to dissuade sociopaths, but to reassure blogger’s audiences that something is being done (however ineffective) – and consequently to raise those bloggers (who are ‘doing something’) in the esteem of their audiences.

  16. 3. The Soundex algorithm [ http://en.wikipedia.org/wiki/Soundex ] is perhaps the worst possible way to implement these lists. [ http://www.huffingtonpost.com/jim-moore/are-you-on-the-no-fly-lis_b_42443.html ]

  17. Added to the insightful comments above, I’d like to add:

    1. An airplane hijacking in this country can no longer depend on the rest of the passengers remaining submissive (particularly if you have only box-knives). This alone guarantees 9/11 cannot be repeated. Flight 93 proves this. Everything else is theater.

    2. Any system that tries to find someone by name assumes that the target will not simply use another name. Forged documents are getting marginally harder to fake (though the new insecure RFID passports present a new opportunity), but the fact that the no-fly/”watch”-list includes aliases completely acknowledges this point.

  18. It would seem unlikely if we proceed from the initial assumption that the no-fly-list is designed to be a neutral list of “terrorists”. But that’s not the correct initial assumption.

    By definition, anyone the U.S. thinks is a terrorist should not be extra-searched at airport security, they should be arrested and charged with a crime. So we know that the no-fly list is composed, 100%, of people who are not terrorists – no evidence of any criminal activity exists against any of them. And we know that the Bush administration is dedicated to the principle of maximizing executive power and destroying all enemies, foreign and (primarily) domestic.

    You are far too generous. If Senator Edward Kennedy is not the intended target of the name “Edward Kennedy” on the list, exactly which Edward Kennedy is the intended target?

    There is mountains of evidence that the list is a modern-day “enemies list”.

    http://www.sfgate.com/cgi-bin/article.cgi?file=/c/a/2002/09/27/MN181034.DTL

    Any such list, maintained in secret by a political organization, is guaranteed to be composed far more of that political group’s enemies than enemies of the state. Guaranteed. Basic human nature. And this list is maintained in secret, by the political appointees at the top of the FBI and related organizations.

    You’re a smart guy, Ed. And unfortunately, you’re old enough that you grew up in an era where government was trusted to basically do the right thing and basically have everyone’s best interests at heart. That assumption is no longer operative.

  19. Another Kevin says

    I shan’t go into the civil-liberties issues of the No-Fly List; it would appear that I’m all too likely to suffer the same inconveniences as Professor Murphy if I do. Nevertheless, even the most vehement supporter of tight controls on air passengers would have to look at the practicalities of what response is appropriate to a positive, true or false.

    Let me recommend to your readers a book by Richards J. Heuer, Jr., entitled “Psychology of Intelligence Analysis” (Washington, D.C.: Central Intelligence Agency, 1995). It’s available online at https://www.cia.gov/csi/books/19104/ and provides some interesting insights into how our intelligence agencies train their staff. In it, the base-rate fallacy is quite clearly explained – https://www.cia.gov/csi/books/19104/art15.html#ft145.

    If we run the numbers, the priors indicate that four flights out of a history of millions have been used as terror weapons. A dozen or so passengers out of hundreds of millions have boarded planes in order to mount such attacks. On the other hand, I’ve seldom been on a flight in recent years that has not had a passenger either denied boarding or harrassed by security staff based on some indication unknown to either the passenger or his neighbours in the security line. (I myself have been subjected to peremptory orders – perhaps the worst was an order to handle some sort of paperwork after my eyeglasses had already been confiscated because of a false positive on a metal detector; I literally could not see to read whatever it was the guard was demanding me produce, sign, or whatever.)

    So we have, conservatively, one-in-a-thousand positive tests and one-in-ten-million base rate? Let’s make the impossible assumption that the test is perfectly sensitive; we *still* have, once a passenger has been identified, a 99.99% probability that we’ve flagged an innocent? What is the proper response to someone who accuses, “I’m 0.01% sure that this passenger is a terrorist?”

    And the DHS doesn’t even have ignorance as an excuse – Heuer’s book is a compilation of articles that he wrote around 1980 – the 1995 publication date is more accurately a date of declassification.