Anderson algorithm

개요

앤덜슨 알고리즘은 프로그램 분석에서 기본이 되는 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가 가르키는 모든

• 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의 최대 계산 복잡도를 가진다.

같이 보기

1. Steensgaard's algorithm
2. Field sensitive algorithm
3. Context sensitive algorithm