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