Virus Detection is Undecidable

https://enterprise.comodo.com/whitepaper/Impossibility_of_Virus_Detection_WP.pdf

-이와 유사한 Halting 문제 이해를 통해 제목의 명제가 undecidable한 이유를 이해해 보자. 

 

어떤 문제들은 컴퓨터로 해결이 불가능 한데 이것을 Undecidable 하다고 명명한다. Undecidable한 문제중 유명한 것은 Halting 이슈다.

이해한대로 적자면 contradictHalt 를 !Halt 로 받아들임

- if halt(!halt()):

   loop

  else:

   stop(멈춰) 

인데 두가지 가정을 해보자. (일단 halt()라는 함수는 프로그램이 멈추면 T 계속되면 F 인데 본래 Halt(P)지만 이 경우에는 P대신 자기자신을 넣었음 Halt(Halt())

1. halt 가 멈췄다. -> halt()함수에 의해 T 
   • !T= F  다. 아무튼 halt  내부에서 함수는 끝났기 때문에 true 로 감 -> loop -> halt 가 멈췄다고 가정했는데 계속되어야됨 -> 모순
2. Halt가 계속된다. -> halt()함수에 의해 F
   • !F = T 다. 아직도 halt 내부에서 함수가 끝나지 않았기 때문에 F로 감 -> stop -> halt가 계속된다고 가정했는데 멈춰야 됨 -> 모순

 

Halting문제를 통해 Virus Detection 같은 문제도 같은 결론을 낼 수가 있다.

 

• Reduction Proof 란? 
  • A를 구현하기 위해 B를 사용할 수 있지만 A가 이미 존재 하지 않는 다는 것을 알기 때문에 B또한 존재 할 수 없다는 걸 보여주는 것.
  • ex. halting 문제는 undecidable하기 때문에 HALT라는 (해결)프로그램이 존재 하지 않는 다는 것. 
  • 이러한 Reduction Proof 에서 바이러스 여부를 탐지할 수 있는 Detectvirus 가 있는 경우, 감염 중지 코드를 실행하기 되기 때문에 모순이 발생한다. 
    • 다시 전개를 해보자 어떤 프로그램 P에 바이러스가 있는지 없는지를 보자!

def Q():

  if not isVirus(Q):

     infect()

  else:

    continue

1. isVirus(Q)가 True다. Q를 봤는데 바이러스가 있었다! T 
   • !T=F다 continue 다 바이러스에 감염되었다고 하는데 계속 하면 안되잖슴(이렇게 이해한 게 맞나)
2. isVirus(Q)가 False다 Q를 봤는데 바이러스가 없었다! F
   • !F=T다 그런데 만약! 이 조건으로 바이러스가 활성화(infect)된다면? 그럼 바이러스를 발견하지 못했는데 바이러스가 활동하는 셈이 된다. -> isVirus 라는 프로그램을 만들지 못한다는 게 이런 의미 

= Virus Detection is Undecidable 에 대해서 알아보았다. 위 IF문은 컴퓨터가 no isVirus(Q)를 통해 바이러스를 감지한다는 로직을 제공하는 것이 아니고, 저런 '경우'라면 '완전하지 않다는 반례'를 제공함으로써 모순이 발생하는 것을 보였고 이를 통해 Undecidable 하다는 것을 증명했다.