The notion that the time we are living in now is “unprecedented” is a common one, but historians and philosophers alike will happily note that things are rarely so different that we can’t learn a lot from the past. Despite IT often being dominated by forward-thinking individuals developing novel and innovative new designs, a lot of the problems and potential solutions for IT security are ones that have stood the test of time. With that in mind, I’m hoping you’ll all indulge with me for a trip back nearly a century to explore an IT problem that remains true to this day.

The Halting Problem

In 1936, Alan Turing, oft considered to be one of the fathers of modern computer science, proved an important concept for modern computer science that is generally referred to as the “Halting Problem.” In effect, this problem explores the idea that there is no algorithmic way to determine if the program will ever complete, as any algorithm to evaluate the completion could be made to contradict itself.

Fast forward to 1987 and Fred Cohen’s “Computer Viruses: Theory and experiments.” Building from Turing’s intractable problem, Cohen effectively demonstrates that it’s impossible to determine whether a piece of a program is malicious or not by inspection alone. This is something familiar for many of the security researchers who have played cat and mouse with vulnerability makers for years, trying to counter virus and malware payloads built to vary just enough to evade detection.

Cohen stipulated some “unanswerable” issues for virus scanning:

  • Detection of a virus by its appearance
  • Detection of a virus by its behavior
  • Detection of an evolution of a known virus
  • Detection of a triggering mechanism by its appearance
  • Detection of a triggering mechanism by its behavior
  • Detection of an evolution (Read more...)