First blog entry: Hello world

This semester my wife gives a lecture in theoretical computer science at the KIT (Karlsruhe Institute of Technology). The current topic is decidability and therefor the students learn about the halting problem. The whole topic is rather dry and good examples for illustration are always welcome.

One example I liked is the question whether a program is a virus or not. As a proof, you could reduce the halting problem to this problem, but it is far better illustrated by giving a self-referencing program (the formal proof then would be based on diagonalization):

Let P be the program that decides whether A is a virus. Then you could define your virus A as:

if P(A) then exit; else infect();

Great, isn’t it? The virus knows the virus-detector P and doesn’t behave as a virus if P can identify it as a virus. If not, it’s evil. q.e.d.

That’s the theory. Let’s have a practical look at it.

First of all, it seems that the virus author is a pretty bad program designer - we usually try to avoid circular dependencies. But, being pragmatic I’m willing to compromise where it is necessary and in this case I must (unless I want to reduce the halting problem).

What seems more awkward to me is that the virus depends on P to being a behavioral analysis. Antivirus programs actually do behavioural analysis to detect viruses. And although I can’t find a link of proof between all the antivirus ads in Google I remember at least one headline where a root kit detected antivirus software and clouded itself against it. But Antivirus programs also do statical analysis. In statical analysis the code isn’t run but only looked at. And any P that does statical analysis would find infect() (hopefully, if the heuristics work) and thus mark the self-clouding virus as virus anyway.

Of course this does not invalidate the proof that I hinted to above. I really like it as example for decidability. It works if you define “virus” as a program with malicious behaviour. It’s sad that in practice we can’t always restrict our environment as we need it - unless we just write a “Hello World”.