개요
Infinite loop은 Intended된 경우와, Unintended된 경우로 나눌 수 있다. Polling과 같은 서비스 루틴을 돌리기 위한 Infinite loop은 정상적인 것 이지만, 프로그래머의 실수로 인해서 야기된 Uninited infinite loop은 시스템을 halting시키기 때문에 취약점으로 악용될 수 있다. ([[Deny of service)
무한 루프의 검출 알고리즘은 프로그램이 무한루프를 가지고 있는지 체크하는 것 이외에도, Data structure에서 순환 루프가 있는지 테스팅하는 것과 같은 상황에서도 이용된다.
의도된 무한 루프 vs 의도되지 않은 무한 루프
Polling, Graphic Library, Multithreading처럼 지속적으로 작업을 계속 해야 하거나, 특정 서비스는 프로그램의 전체 파트에서 반복적으로 처리되는 작업이거나, Threading library를 이용하는 경우에 많은 경우 무한 루프가 프로그래머의 의도에 의하여 사용되고 있다. 예를 들어서 게임의 대부분의 로직은 Looping을 통해서 처리되며, OS의 경우에도, Interrupt방식이 아니라 Polling방식은 Input이 들어 오기전까지는 특정 조건을 만족시키기 전까지 무한루프를 통해서 기다린다.
그러나 의도치 않은 프로그래머의 실수로 인해서 무한루프가 발생할 경우도 있다. 이러한 경우 시스템에 Deny-of-service attack을 일으킬 수 있다. 예를 들어서 OS에서 Atomic context에서 무한루프가 일어나면, Interrupt을 통해서 kill을 할 수도 없기에, OS를 재부팅 하기 전까지는 특정 시스템 파트를 사용할 수 없게 된다.
그렇다면 의도하지 않는 무한루프를 찾아 내거나, 아니면 검출해 내서 사전에 방지할 수 있을까? 이는 Halting problem으로서, 완전한 Detection은 불가능 하다는 것이 증명되었다. 그러나 Halting problem으로 인해서 Pratical한 수준의 무한루프 Detector을 만들지도 못한다는 것은 아니다. Halting problem은 어디까지나 모든 무한루프의 케이스를 막을 수 있는 알고리즘은 없다는 증명이지, while(1) {} 혹은, Limited된 Computer resource하에서의 무한루프는 CPU나 Memory를 소비하긴 하지만, Detection할 수 있다.
무한 루프의 검출
만약 어떤 프로그램의 현재 상태가 과거의 특정 상태와 정확히 같은 상태라면 이 프로그램은 무한루프에 있다고 할 수 있다. 좀더 쉽게 이해하자면, 무한루프 물에서 (하루가 계속 반복되는 경우), 아침에 일어난 나의 상태는 과거의 상태와 정확히 같은 상황이다. 이처럼 프로그램이 과거의 어느 상황 (State)와 완전히 같다는 것을 보이면, 현재 프로그램이 무한루프 상황에 있다는 것을 증명할 수 있다. 물론 이러한 방식을 사용한다고 해서 Halting problem을 증명할 수 있는 것은 아니다. Halting problem을 해결하기 위해선 무한히 큰 Resource가 필요하기 때문이다.
토끼와 거북이 (Floyd's tortoise and hare) 알고리즘
컴퓨터가 2대가 있다고 하자. 토끼 컴퓨터는 정확히 두배의 속도로 거북이 컴퓨터보다 빠르게 프로그램을 실행시킨다. 만약 토끼 컴퓨터의 상태와 (State)와 거북이 컴퓨터의 상태가 정확히 같은 순간이 있다면, 토끼 컴퓨터는 그 순간 부터 거북이 컴퓨터랑 똑같이 실행시키고, 거북이 컴퓨터는 처음부터 시작시킨다. 그러면 거북이 컴퓨터와 토끼 컴퓨터는 정확히 "시작 지점"에서 만난다. 시작 시점에 만난 후 부터, 거북이 컴퓨터는 정지 시키고, 토끼 컴퓨터만 작동시키면, 거북이 컴퓨터의 상태와 토끼 컴퓨터의 상태가 같은 지점의 위치를 구한 "시작 지점"에서 빼면 "사이클의 길이"가 나온다.
직관적으로 이해 한다면, 집에서 출발해서 운동장을 돈다고 해보자. 친구가 나보다 2배 빠르게 움직인다 하더라도, 언젠가 운동장의 어느 구간에서는 나와 친구가 만날 것이다. 따라서 토끼 거북이 방식은 Loop가 있다면 (운동장이 있다면), 토끼와 거북이 컴퓨터가 어느순간 만나는 것을 보장한다. 그렇다면 어떻게 시작 시점 부터 토끼 거북이 컴퓨터가 만난 지점의 걸이가 정확히 시작 시점 부터 루프 시작 시점의 2배가 됨을 보장하는 것일까? 수학적으로 쉽게 유추 할 수 있다. (증명은 생략). 직관적으로 생각 해보자. 운동장이 지구만하다고 생각하자. 친구는 비행기 타고 20KM앞에서 출발하고, 나는 기차타고 정확히 친구보다 반의 속도로 움직인다고 하자. 그러면 내가 지구 반바퀴 돌았을때, 정확히 친구는 원래 위치로 돌아온다. 그렇다면 나와 친구는 위와 같은 상황에서 다시 어디서 만나게 될까? 친구가 두배 빠르니깐, 원래 같이 출발하면, 출발 시점에서 친구는 2바퀴 돌고, 나는 한바퀴 돌때 만났을 것을, 출발 지점에서 -10KM지점에서 같이 만나게 될 것이다. 자 왜 친구가 출발 지점에서 20KM앞에 있을까? 바로 친구가 나보다 출발지점을 더 빠르게 갔기 때문이다. 2배 빠르기 때문에 10KM정도 집에서 출발지점까지 떨어져 있을 것이다. 즉 운동장 부터, 집까지의 거리는 운동장에서 출발 지점까지의 거리와 같다.