Use your computer fearlessly.

Mission Services Articles Research

everyone: older news

business: Intractable Cybersecurity, Quantum Communications

Impossible Problems in Computer Security

by Brent Kirkpatrick

(Date Published: .)

Impossible Problems in Computer Security

Hi, I am Brent Kirkpatrick. Today, we are going to discuss impossible or intractable problems in computer security and cybersecurity. Three problems: detecting hacking, doing digital forensics, and detecting vulnerabilities. All three of these problems are impossible. Or in the technical wording undecidable.

What does this mean? So, in lay terms, there is no computer program that can solve these problems. I'll be a little more technical for a moment. These three problems are undecidable as proven by reduction to the halting problem. The halting problem is known to have no solution, no algorithmic solution. Because of the reduction of these three problems, this constitutes proof, mathematical proof, that these three problems are intractable. There is no algorithm, no computer program, that can possibly solve these three problems.

In fact, you'd think that detecting one buffer over-run... So, a buffer over-run is one of the major vulnerabilities of computer software... So, you'd think that detecting one single buffer over-run would be tractable. Surely, just one buffer over-run can be detected with an algorithm. It turns out not to be the case. Not even one buffer over-run can be detected with a computer algorithm.

This is important because DARPA has organized the Cyber Grand Challenge. This Grand Challenge is a contest. I'll read, read a quote from their web site. "the goal is automated defense systems capable of reasoning about flaws in computer programs" They go on to describe this as a break-through. This is over-sold. And, we know that now, because of these mathematical proofs that these three problems, one of which is detecting buffer over-runs, that is the technical wording for the word-choice on their web site: "reasoning about flaws in computer programs." They're referring to the technical problem of detecting buffer over-runs. Because of this mathematical proof, we now know that this problem is intractable, algorithmically intractable.

I would encourage all of my colleagues to work on problems that are tractable.

Trojan Hunter image

Trojan Hunter (TM). Digital forensics for Trojans at an accessible, fixed price. For any operating system.

INC Logo

What Is New? | Contact | Tips

© 2015-2021 Intrepid Net Computing. All rights reserved.