Computer Security: Uni-Aufgabe

[aXiEd]

Hallo, ich häng hier grad mit einem Freund an ner Aufgabe, die wie folgt aussieht:

The question arises as to whether it is possible to develop a program that can analyze a piece of software to determine if it is a virus. Consider that we have a program D that is supposed to be able to do that. That is, for any program P, if we run D(P), the result returned is TRUE (P is a virus) or FALSE (P is not a virus). Now consider the following program:

  Program CV :=
    {...
    main-program :=
      {if D(CV) then goto next:
                else infect-executable;
      }
    next:
    }

In the preceding program, infect-executable is a module that scans memory for executable programs and replicates itself in thosse programs. Determine if D can correctly decide whether CV is a virus.

Wir glauben dass D() nicht erkennen kann dass CV ein Virus ist, jedoch fehlt uns die richtige Begründung.
Weiß jemand Rat?

 

[rash65]

Also es geht darum, ob D(CV) entschieden werden kann. Die Antwort ist nein, dies lässt sich durch einen Widerspruch beweisen.

a) Wenn D(CV) TRUE zurückgibt, dürfte CV keinen schadhaften Code ausführen und wäre somit kein Virus. -> Widerspruch

b) Wenn D(CV) FALSE zurückgibt, führt CV schadhaften Code aus und ist somit ein Virus. -> Widerspruch

=> D() kann für CV nicht entscheiden, ob es sich um einen Virus handelt.

Wenn euch das Thema weiter interessiert, sollte ihr euch mal bezüglich Turing und dem Halteproblem informieren.

 

[tafkas]

Wenn euch das Thema weiter interessiert, sollte ihr euch mal bezüglich Turing und dem Halteproblem informieren.

Wieso muss ich dabei an die Gödelnummer™ denken?

 

[aXiEd]

Also es geht darum, ob D(CV) entschieden werden kann. Die Antwort ist nein, dies lässt sich durch einen Widerspruch beweisen.

a) Wenn D(CV) TRUE zurückgibt, dürfte CV keinen schadhaften Code ausführen und wäre somit kein Virus. -> Widerspruch

b) Wenn D(CV) FALSE zurückgibt, führt CV schadhaften Code aus und ist somit ein Virus. -> Widerspruch

=> D() kann für CV nicht entscheiden, ob es sich um einen Virus handelt.

Wenn euch das Thema weiter interessiert, sollte ihr euch mal bezüglich Turing und dem Halteproblem informieren.

Vielen Dank für deine Antwort, wir sind am Dienstag Abend später auf genau die selbe Lösung gekommen.