The following paragraphs list many papers that try to contribute to the P-versus-NP question. Among all these papers, there is only a single paper that has appeared in a peer-reviewed journal, that has thoroughly been verified by the experts in the area, and whose correctness is accepted by the general research community: The paper by Mihalis Yannakakis. (And this paper does not settle the P-versus-NP question, but "just" shows that a certain approach to settling this question will never work out.)

Of course, there's a million-dollar prize for resolving the question -- so expect the flawed proofs to continue.

On the 31st episode of The Silver Bullet Security Podcast, Gary talks with Matt Bishop, professor of Computer Science at UC Davis and author of the book Computer Security: Art and Science as well as many peer-reviewed papers. Gary and Matt discuss Matt’s plan to work security analysis and secure coding into a wider computer science cirriculum, Matt’s early work with Mike Dilger on TOCTOU, whether or not progress is being made in the field of software security, and the role of training in large-scale software security initiatives. Their chat closes with a mention of Matt’s home menagerie (which does not include any one-legged chickens at this time).

• Matt Bishop
• IEEE Security & Privacy Magazine
• Computer Security: Art and Science
• Silver Bullet Security Podcast interview with Dorothy Denning
• Security Controls for Computer Systems: Report of Defense Science Board Task Force on Computer Security (the “Ware Report” referred to in the podcast)
• Secure Computer Systems: Mathematical Foundations - The Bell Lapadula model [PDF]
• Secure Computer System: Unified Exposition and Multics Interpretation [PDF]
• Testing C Programs for Buffer Overflow Vulnerabilities - Eric Haugh, Matt Bishop [PDF]
• TOCTOU
• Checking for Race Conditions in File Accesses by Matt Bishop and Michael Dilger
• “The Song of the One Legged Chicken”

These “take-down” companies are generally specialist offshoots of more general “brand protection” companies, and are hired by banks to handle removal of fake phishing websites.

When we examined our data more carefully we found that we were receiving “feeds” of phishing website URLs from several different sources — and the “take-down” companies that were passing the data to us were not passing the data to each other.

So it often occurs that take-down company A knows about a phishing website targeting a particular bank, but take-down company B is ignorant of its existence. If it is company B that has the contract for removing sites for that bank then, since they don’t know the website exists, they take no action and the site stays up.

Since we were receiving data feeds from both company A and company B, we knew the site existed and we measured its lifetime — which is much extended. In fact, it’s somewhat of a mystery why it is removed at all! Our best guess is that reports made directly to ISPs trigger removal.

The paper contains all the details, and gives all the figures to show that website lifetimes are extended by about 5 days when the take-down company is completely unaware of the site. On other occasions the company learns about the site some time after it is first detected by someone else; and this extends the lifetimes by an average of 2 days.

Since extended lifetimes equate to more unsuspecting visitors handing over their credentials and having their bank accounts cleaned out, these delays can also be expressed in monetary terms. Using the rough and ready model we developed last year, we estimate that an extra $326 million per annum is currently being put at risk by the lack of data sharing. This figure is from our analysis of just two companies’ feeds, and there are several more such companies in this business.

Not surprisingly, our paper suggests that the take-down companies should be sharing their data, so that when they learn about websites attacking banks they don’t have contracts with, they pass the details on to another company who can start to get the site removed.

We analyse the incentives to make this change (and the incentives the companies have not to do so) and contrast the current arrangements with the anti-virus/malware industry — where sample suspect code has been shared since the early 1990s.

In particular, we note that it is the banks who would benefit most from data sharing — and since they are paying the bills, we think that they may well be in a position to force through changes in policy. To best protect the public, we must hope that this happens soon.

Around the same time that Professor Luckham and his team was working on CEP applications in network management and security management, I was leading efforts to build network and security management control centers for the United States Air Force.  In the beginning, dating back to 1994, my Internet-related work was for Air Combat Command (ACC), working out of ACC headquarters at Langley Air Force Base.

In 1997, I lead a technical team that developed countermeasures against an actual distributed Internet-based attack on the Langley AFB SMTP email infrastructure.  This attack was documented in a technical paper, E-Mail Bombs and Countermeasures: Cyber Attacks on Availability and Brand Integrity, IEEE Network Magazine, Vol. 12, No. 2, pp. 10-17, March/April 1998.  In addition, this attackand countermeasures I designed was featured in Popular Science Magazine in an 1998 article, War.Com and other news channels.  I also published a number of related papers on this topic.

Our team used a rule-based approach for countermeasures against massive email bombs attacks on the Langley Air Force Base email infrastructure.   We called this rule-based system, BombShelter. and it was written in PERL.  I developed both the original software architecture and the original working prototype for BombShelter (in two days) and then we turned the software over to our team who used the rule-based approach for daily attack countermeasures.

I watched for days, and then weeks, as my team designed rules, and the attackers wrote new attacks that circumvented the rules.  Some folks in the Pentagon used to say that I “lead the effort to fight the first war in cyberspace”.   It might have have been the first cyberwar, I am not sure, but it was certainly the first publicly documented cyberwar.  There is no doubt about this.

Without getting into all the historical footnotes and significance of this cyberwar that was fought with experts and rule-based systems, I would like to jump to an important conclusion.

Rule-based systems are useful, but have limited functionality and scaleability in most complex event processing applications.

Rule-based systems are human resource intensive because rule-based systems cannot learn and adapt on their own, humans learn and then write new rules.  This is how rule-based systems work.

This is the motivation behind why I spend a lot of time to search for new, more efficient and adaptive methods as alternatives to rule-based systems.   After extensive research, I published a series of papers on the future of intrusion detection in the Internet.  Intrusion Detection Systems & Multisensor Data Fusion - Creating Cyberspace Situational Awareness [1], helped lead an evolution in Internet security, particularly in the area of network-based intrusion detection systems (IDS).

In my published research work, motivated by limitations with rule-based approaches, I used the same mature functional model that is used to process missile attacks, control global air traffic, and other complex event processing applications in physical space; but I applied these concepts to cyberspace.

Around the same time, Professor Luckham and others were working on similar problems, all related to real-time detection and response to threats in cyberspace.  They were also funded by the US government.

Sidebar: Stream processing of transaction- based systems (databases), another area of interest, was focused on a totally different problem, which was the low latency processing of straight-thru processing in databased-oriented systems.   These stream processing systems were, and remain however,  rule-based systems.  The problems we were trying to solve in cyberspace, however, cannot be efficiently and pragmatically solved by rule-based systems alone.  Only relatively simple scenarios can be efficiently detected by rule-based stream processing systems.

The vast majority of complex event processing classes of problems require rules plus advanced algorithms that can learn and adapt in real-time.    I know this, not from reading papers or taking university classes on rule-bases systems, but from working on some very challenging operational problems in real-time.    This is why I remain interested in complex event processing and why I continue to elaborate on why rule-based systems have limitations.

This year, we are particularly looking for submissions from topics other than anonymous communications, so if work from your field may be applied, or is otherwise related, to the topic of privacy, I’d encourage you to consider PETS as a potential venue.

The submission deadline for the main session is 2 March 2009. As with last year, we will also have a “HotPETS” event, for new and exciting work in the field which is still in a formative state. Submissions for HotPETS should be received by 8 May 2009.

Further information can be found in the call for papers.

In a tale rich with incongruities, the Communist-run government of West Bengal State invited the Tata Group, a symbol of Indian capitalism, to set up its plant in an area called Singur. It acquired 1,000 acres from farmers on the company’s behalf.
As the project advanced, some farmers who had sold their land demanded it back. The main state-level opposition party, the Trinamool Congress, led protests demanding that the land be returned. Most people sympathetic to Tata accused the opposition of inducing the farmers to protest, while Tata’s critics said the farmers had legitimate grievances.

The issue simmered for months. But in recent days, protesters began surrounding the plant, blocking roads and preventing Tata workers from reaching the plant. “The existing environment of obstruction, intimidation and confrontation has begun to impact the ability of the company to convince several of its experienced managers to relocate and work in the plant,” Tata said in a statement on Tuesday.

The halt to the plant has caused many Indian business people to warn of a chilling effect on investment in the country. It is also unclear how Tata will be able to keep the Nano’s cost so low, since part of the affordable price reflects the company’s savings on the land in Singur.

There is a fundamental asymmetry between state and markets. It is easier to create markets than it is to create state capacity or to prevent its deterioration. Creating markets is a lot about letting go, establishing a reasonable policy framework, and allowing the natural hustling instinct to take over. In other words, hustling is the natural state. Building state capacity, on the other hand, is quite different. It involves overcoming collective action problems, mediating conflict, creating accountability mechanisms where outputs are multiple and fuzzy and links between inputs and outputs murky, and contending with the deep imprints of history. In Weber’s memorable words, building public institutions is like the “slow boring of hard boards”.

In that light, China’s task of improving its private sector seems easier to accomplish than India’s task of arresting institutional decline. So, while China and India can probably both count on more years of high growth, the odds still favour China pulling off that feat than India. That, and not just the meagre medal tally, should be what India mulls over after the Beijing Olympics.

It's easier to liberalise a functional state than it is to functionalise a dysfunctional one, of any ideological stripe.

I observed that provided one considered “real” aardvarks and zebras — addresses that received good email amongst the spam — then aardvarks got 35% spam and zebras a mere 20%.

This has been widely picked up, first in the Guardian, and later in many other papers as well (even in Danish). However, many of these articles have got hold of the wrong end of the stick. So besides mentioning A and Z, it looks as if I should have published this figure from the paper as well…

… the point being that the effect I am describing has little to do with Z being at the end of the alphabet, and A at the front, but seems to be connected to the relative rarity of zebras.

As you can see from the figure, marmosets and pelicans get around 42% spam (M and P being popular letters for people’s names) and quaggas 21% (there are very few Quentins, just as there are very few Zacks).

There are some outliers in the figure: for example “3″ relates to spammers failing to parse HTML properly and ending up with “3c” (a < character) at the start of names. However, it isn’t immediately apparent why “unicorns” get quite so much spam, it may just be a quirk of the way that I have assessed “realness”. Doubtless some future research will be able to explain this more fully.