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.
Copyright 2015-2021 Intrepid Net Computing. All rights reserved.