컴퓨터 소프트웨어계에는 이미 작성되어 있는 프로그램을 실제로 돌려 보지 않고(샌드박스 가상 머신 안에서..) 형태만 들여다보고는 버퍼 오버런이나 메모리 누출 같은 잠재적 위험성 및 논리 결함을 어느 정도 찾아 주는 '정적 분석'이라는 기술이 존재한다. 그 프로그램이 기계어 바이너리 형태이건, 고급 언어 소스 코드이건 형태는 무엇이건 상관없다.
그런데 정적 분석 툴은 그 누가 만든 것이라도 원천적으로 이론적으로 근본적으로 100% 정확하게 작동하지는 못한다.
이에 대해서 "아니 소스 코드가 무슨 자유 의지를 지닌 생명체도 아닌데 그 뻔한 로직을 분석해서 결과를 사전 예측하는 게 그렇게 어려운가? 단순히 소모하는 메모리와 계산량만 많아서 어려운 거라면 컴퓨터의 성능빨로 극복 가능하지 않은가? AI 기술을 접목하면 되지 않는가?" 처럼 생각하기 쉽다.
하지만 그렇지 않다. 그 말은 저런 차원이 아니다.
그런 함수는 단순히 현실적으로 구현하기가 어려운 정도가 아니라 논리 차원에서 모순에 빠지며 존재 불가능하기 때문이다. "모든 창을 막는 방패와 모든 방패를 뚫는 창 세트"와 동급으로 존재 불가능하다~! 창이나 방패의 제조 기술과는 무관하게 말이다.
가장~~ 원초적인 정적 분석 프로그램을 생각해 보기로 한다.
분석할 대상인 프로그램 코드, 그리고 그 프로그램에다가 넘겨줄 입력 데이터.
이 둘을 인자로 받아서 이 프로그램의 시시콜콜한 무슨 메모리 문제 따위를 진단하는 게 아니라..
이 프로그램이 무한 루프에 빠지지 않고 실행이 종료되기는 할지를 정확하게 판단해 주는 bool DoesThisProgramReturn(func, argument) 라는 가상의 함수 프로그램을 생각해 보자.
argument는 현실의 프로그램으로 치자면 명령 인자뿐만 아니라 프로그램이 파일이나 네트워크 형태로 읽어들이는 방대한 입력 데이터까지 모두 포함하는 개념이다. "일괄 처리 형태가 아니라 입출력이 실시간으로 들어오는 프로그램은요?" 이건 이 시점에서 그리 중요한 문제가 아니니 논외로 한다.
func는 뭐.. C/C++로 치면 기계어 코드를 가리키는 함수 포인터 정도로 생각하면 이해하기 편하겠다.
당연한 말이지만 저 함수 자체는 절대로 무한 루프에 빠지지 않고 언제나 유한 시간 안에 답이 나오는 게 보장된다. 무한 루프에 빠지는 프로그램을 의뢰했더라도 말이다. 그러므로 DoesThisProgramReturn(DoesThisProgramReturn, xxx)는 xxx로 무엇을 넘겨주건 그 정의상 리턴값이 언제나 true가 된다.
그럼.. 저 가상의 함수는 어떤 식으로 동작할지를 생각해 보자.
func가 가리키는 코드를 읽으면서 while(true); 같은 패턴을 발견한다거나,
더 구체적으로는 예전에 한번 거쳤던 state와 동일한 state로 이미 지났던 지점을 또 지나는 게 감지되면.. 이 프로그램은 실행이 끝나지 않는다는 결론을 내릴 수 있을 것이다.
이거 만델브로트(망델브로) 집합을 그릴 때 주어진 복소수의 발산 여부를 판별하는 것과 비슷하게 느껴진다.
배배 꼬인 복잡한 프로그램에서는 좀 어렵겠지만 그래도 도저히 불가능한 문제는 아니어 보이는데..??
하지만 튜링 기계는 우리가 흔히 생각하는 것보다 자유도가 더 높은 계산 모델이다.
메모리에 저장된 주소값에 해당하는 다른 메모리의 값을 마음대로 읽고 쓸 수 있을 뿐만 아니라(= 포인터) 거기 저장된 데이터를 코드로 간주해서 실행할 수도 있다(= 함수 포인터).
재귀 호출도 되고.. 또 앞서 살펴보았듯이 DoesThisProgramReturn 자신조차도 튜링 기계에서 실행되는 함수이기 때문에 DoesThisProgramReturn의 인자로 전달할 수 있다. 그리고 분석 대상인 타 함수가 얘를 또 호출할 수도 있다.
이런 상황까지 다 허용 가능해야 한다면 DoesThisProgramReturn의 존재 가능성은 굉장히 난감해진다.
아래와 같이.. DoesThisProgramReturn가 true라고 판정한(= 실행이 끝난다) func에 대해서는 "반대로" 자신이 무한 루프로 가 버리고, 실행이 끝나지 않는 함수에 대해서는 실행을 끝내는 HangIfReturns이라는 함수를 정의해 보자.
bool HangIfReturns(func) {
if (DoesThisProgramReturn(func, func)) while(true);
return true;
}
그러니 HangIfReturns(DoesThisProgramReturn)을 하면.. 얘는 무한 루프에 빠지게 된다.
DoesThisProgramReturn은 자기 자신에 대해서는 앞서 정의한 바와 같이 언제나 true를 되돌리고(= 늘 깔끔하게 실행 종료) if문을 만족하기 때문이다. 여기까지는 쉽다.
하지만 반대로 HangIfReturns가 DoesThisProgramReturn의 인자로 들어가면 어떤 일이 벌어질까? DoesThisProgramReturn(HangIfReturns, HangIfReturns)는 리턴값이 무엇이 되는 게 이치에 맞을까? 이제 좀 머리가 복잡해질 것이다.
DoesThisProgramReturn(HangIfReturns, HangIfReturns)가 true라면.. HangIfReturns 안의 if문은 true가 되므로 HangIfReturns은 무한 루프에 빠진다. 그러면 저 함수의 리턴값은 원래 false가 되어야 하게 된다.
반대로 저 리턴값이 false라면.. 역시 이제 HangIfReturns는 실행이 깔끔하게 종료되므로 저 함수의 리턴값을 정면으로 부정하는 결과가 나온다.
요컨대 HangIfReturns가 무한 루프에 빠지는지의 여부는 DoesThisProgramReturn의 리턴값에 따라 달라지는데, 이 과정에서 서로 물고 무는 구조적인 모순이 발생하는 셈이다.
이 모순은 DoesThisProgramReturn라는 함수가 존재한다는 가정으로부터 비롯되었다. 그러니 튜링 기계 하에서 다른 코드의 실행 종료 여부를 완벽하게 판단하는 코드를 똑같은 튜링 기계 기반으로 구현하는 것은 불가능하다는 것이 입증된다.
이 논리는 "정지 문제"(halting problem)이라고 불리며, 컴퓨터라는 기계의 계산 가능 범위를 고민하게 하는 매우 탁월한 통찰이다. 이걸 처음으로 생각해서 논문으로 발표한 사람이 바로 그 이름도 유명한 앨런 튜링이다.
과학 철학에서 "반증 가능한가", 천문학에서 "관측 가능한가"처럼.. 전산학에서는 "계산 가능한가, 튜링 기계를 돌려서 답을 구할 수 있는 문제인가"가 중요한 고민거리가 된다. 계산 자체가 이론적으로 가능해야 그 다음 관심사는 "실용적으로 유의미한 시간 만에 빨리 해결할 수 있는가?", 더 구체적으로는 "입력 크기 N에 관한 다항식 급의 시간 안에 해결 가능한가 (팩토리얼이나 지수 함수 급이 아니라)"라는 시간 복잡도가 될 것이다.
TSP(순회하는 세일즈맨) 문제 같은 NP-완전 문제는 이론적으로 알려진 시간 복잡도가 너무 높기 때문에 실생활에서는 적당히 성능이 좋은 다항 시간 근사 알고리즘이 쓰인다.
그래도 정지 문제는 3-SAT 문제라든가 NP-완전처럼 시간 복잡도를 따지는 증명보다는 덜 난해하고 직관적인 설명도 가능하기 때문에 수식 없이 블로그에다 증명 방식을 소개도 할 수 있다. 현실에서는 논리적으로 100% 완벽하고 헛점이 없고 100% 정확하게 동작하지는 못하지만 그래도 현실적으로 충분히 정확하고 속도도 적절한 각종 소스 코드 정적 분석 기능이 개발되어 쓰이고 있다.
Posted by 사무엘
