HALTING Problem

 

 

문제

프로그램 M과 입력 X가 있을 때, M에 입력 X를 주고 수행시키면 종료할 것인가?

 

M은 그냥 어떠한 프로그램 

X는 어떠한 문자열 ex) abcabad

M과 X가 모두 문자열이라고 가정함

 

명확한 두 가지 경우가 존재함

1. 멈추는 것을 알 수 있는 경우 * 안 읽고 멈추는 것도 멈추는 것임 

2. 멈추지 않는 것을 알 수 있는 경우 ex) 문자열을 입력받고 또 다음 문자열을 위해 기다리는 행위 등

 

HALTING Problem은 어떤 프로그램이 종료하지 않는지를 돌려보기 전에 알아야한다.

Q. 돌려보기 전에 알아야하는 이유는 뭘까?

A. 돌려봐서 끝난다면 끝나는 것을 알 수 있지만, 안 끝나고 있다면 "언젠가는" 끝난다는 것을 말할 수 있어야함

ex) 10시간을 기다렸기에 끝나지 않을지, 10시간을 기다렸지만 언젠가 끝날지

 

\(M(X)\)

프로그램 M에 입력 X를 주고 실행시킨 상태

 

해당 Notation을 사용하면 아래의 문장들이 성립한다.

• \(M(X)\)는 종료한다, 혹은 종료하지 않는다
• \(M(X)\)의 출력은 Yes이다. 혹은 No이다.
• \(M(X)\)의 출력은 010011010이다. 

* 참 거짓이 있다는 것, 문장이 성립한다는 것

 

The Proof | HALTING Problem을 풀 수 없다

(by Alan Turing)

 

Decide the HALTING Problem (HALTING Problem이 풀린다)

가정 : 프로그램 D가 존재해서, 모든 프로그램 M과 M에 대한 모든 입력 X에 대해서 M(X)를 실행하면 종료할지 영원히 계속 수행될지 판단할 수 있다고 가정하자

• 프로그램 D는 Yes/No만 대답하는 프로그램
• 프로그램 D는 항상 종료함

 프로그램 D는 프로그램 M, 입력 X를 받으며 출력은 종료 여부이다

> \(D(M,X)\)를 실행하면 Yex, No중 하나를 출력함

 

즉, HALTING Problem을 해결하는 프로그램 D가 있다고 가정하자. 위는 그 프로그램 D의 가정이다

프로그램 D가 있다면 아래의 프로그램을 만들 수 있음

 

\(D'\) 

M(X)가 멈추는 경우: \(D'(M,X)\)는 멈추지 않음

M(X)가 멈추지 않는 경우 :  \(D'(M,X)\)는 멈춘다

즉, D(M,X)의 출력이 No면 멈추고, 출력이 Yes면 무한루프 (D가 이미 가능하기 때문에 반대의 경우는 간단하다)

M(X)가 하는 일의 반대를 실행한다. 

\(S\)

M(M)가 멈추는 경우 : \(S(M)\)은 멈추지 않음

M(M)이 멈추지 않는 경우 \(S(M)\)은 멈춘다

즉, \(D'(M,M)\)을 돌리는 경우와 같음 

M은 프로그램 이지만, 문자열일 뿐이므로 D'의 입력으로 줄 수 있고, M의 입력으로도 가능하다

 

\(S(S)\)를 실행시키면

S(S)가 멈추는 경우 S(S)는 멈추지 않고 (F)

S(S)가 멈추지 않는 경우 S(S)는 멈춘다 (F)

모순

∴ HALTING Problem을 풀 수 없다

 

* 어디서 모순이 생긴걸까?

- S(S)가 실행이 된다 - 프로그램이니까 실행할 수 있음

- S를 코딩할 수 있음 - D, D'이 있다면 코딩할 수 있음

- D가 존재한다 

> D가 존재한다는 것 자체가 해당 모순을 이끌어냄

 

 

[ SQL Injection 막기 ]

외부 입력을 받는 변수들이 검사 루틴을 통과하는지 확인 해야함 

모든 경우의 수를 다 확인할 수 없음 (그래도 '는 막도록 하자..)

보통 CTF 문제에 나오는 문자들을 막으면 거의 다 막히는 듯