개요
앤덜슨 알고리즘은 프로그램 분석에서 기본이 되는 2가지 알고리즘 중에 하나로, 제일 정확하지만, 제일 오래걸리는 특징을 가진다. Context-insensitive 알고리즘 이며, Flow-insensitive분석 방법이다.
알고리즘
포인터는 다음 4가지의 상태에서 연산된다.
- address of: A = &B or (A = malloc(size), A = new ...)
- copy: A = B
- assign: *A = B
- dereference: A = *B
각각의 상태는 다음과 같은 집합에 의해서 표현될 수 있다. 이때 A, B는 변수 A, B가 가르키는 주소들에 대한 집합이며, [math]l_x[/math]는 X라는 변수의 위치 (즉 포인터)를 나타낸다. * 오퍼레이션은 집합 기호에서는 원래 없는 기호인데, 여기서는 *A가 가르키는 모든 변수들을 말한다. 예를 들어서 A->B->C 라는 관계도에서 *B는 A를 가르킨다.
- address-of: [math]l_b \in A[/math]
- copy: [math]A \supseteq B[/math]
- assign: [math] *A \supseteq B[/math]
- dereference: [math] A \supseteq *B[/math]
결과적으로 다음과 같이 나타난다.
- address of : A = {A, [math]l_b[/math]}
- copy: A = {A, B}
- assign: var1 = {var1, [math]l_b[/math]}, var2 = {var2, [math]l_b[/math]}, .., var_x is #x element of A.
- dereference: A = {A, var1, var2, ...}, var_x is #x element of B
결국, 각 set A, B는 내부적으로 변수 집합을 가지게 되고, 각 변수 집합은 A라는 포인터 변수가 가르키는 오브젝트의 집합이 된다.
복잡도
N개의 변수가 프로그램에 있다고 해보자. 이경우 각 변수 집합은 최대 N개의 다른 변수집합을 가르킬 수 있음으로, 최종 메모리의 사용량은 최대 O([math]n^2[/math])이 된다.
dereference상황에서, 변수 [math]X\in N[/math]는 dereference operation을 위해서 최대 O([math]n^2[/math])의 operation을 각각의 원소에 대해서 수행해야 한다. 따라서 최종적으로는 O([math]n^2[/math])의 계산 복잡도를 가진다.
쉽게 요약하자면, 엔더슨 알고리즘은 각 변수의 대입을 집합을 통해서 추적한다. 모든 변수가 서로 다른 모든 변수를 참고할 가능성이 있는 경우가 최대한의 복잡도의 상황이며, 이경우 각 집합은 N즉 최종적으로 N*N의 크기를 먹는다. 만약 변수 하나를 Dereference하게 된다면, 상태를 업데이트 하기 위해서 N*N개의 변수 집합에 대한 dereference operation이 필요하다. 따라서 최종적으로 N*N*N의 최대 계산 복잡도를 가진다.