포인터 분석

3. 알고리즘

포인터 분석 알고리즘은 프로그램 내에서 수집된 포인터 사용 정보(예: 한 포인터 변수에 다른 포인터 변수를 할당하거나, 특정 메모리 주소를 할당하는 등)를 바탕으로, 각 포인터 변수가 가리킬 수 있는 메모리 위치들의 집합을 계산하여 유용한 그래프 형태로 나타내는 데 사용된다.^[4]

대표적인 포인터 분석 알고리즘으로는 스테엔스가르드 알고리즘과 앤더슨 알고리즘이 있다. 이들은 컨텍스트 비의존적(context-insensitive)이고 흐름 비의존적(flow-insensitive)인 분석 방식으로, 컴파일러 최적화나 프로그램 분석 도구에서 널리 사용된다. 예를 들어, [https://github.com/SVF-tools/SVF SVF]나 LLVM과 같은 프레임워크에 구현되어 있다.^[5] 이러한 컨텍스트/흐름 비의존적 분석은 특정 실행 문맥이나 프로그램의 제어 흐름 순서를 엄격하게 구분하지 않고 분석을 수행하는 특징이 있다. 분석의 효율성을 높이기 위해 이진 의사결정 다이어그램(Binary Decision Diagram, BDD)과 같은 자료 구조가 활용되기도 한다.

3. 1. 앤더슨 알고리즘 (Andersen's Algorithm)

하지만 앤더슨 알고리즘과 같은 컨텍스트 비의존적 분석은 id 함수가 호출될 때 &x가 전달되었는지 &y가 전달되었는지 구별하지 않는다. 따라서 함수 내의 포인터 p가 main::x와 main::y 모두를 가리킬 수 있다고 분석하게 된다. 결과적으로, 함수 호출의 반환값을 받는 포인터 u와 v 역시 main::x와 main::y 두 위치 모두를 가리킬 수 있다는, 실제보다 덜 정밀한(보수적인) 분석 결과를 내놓게 된다.

(여기서 X::Y 표기는 함수 X 내부에 선언된 지역 변수 Y를 저장하기 위해 할당된 메모리 위치를 나타낸다.)

앤더슨 알고리즘은 스테엔스가르드 알고리즘에 비해 일반적으로 더 많은 포인터 관계를 고려하여 상대적으로 더 정밀한 분석 결과를 제공하는 경향이 있지만, 그만큼 계산 시간과 메모리 사용량이 더 많은 단점이 있다. 이 알고리즘은 컴파일러 최적화나 프로그램 오류 검출 등 다양한 정적 프로그램 분석 분야에서 중요한 기술로 사용되며, [https://github.com/SVF-tools/SVF SVF]나 LLVM과 같은 실제 컴파일러 및 분석 도구 프레임워크에 구현되어 있다.^[5] 분석의 효율성을 높이기 위해 이진 의사결정 다이어그램(Binary Decision Diagram, BDD)과 같은 자료 구조를 활용하기도 한다.

3. 2. 스틴스가드 알고리즘 (Steensgaard's Algorithm)

3. 3. 이진 의사결정 다이어그램 (Binary Decision Diagram)

4. 문맥 민감도

Context Sensitivity^eng(문맥 민감도)는 포인터 분석 시 함수 호출의 문맥(context) 정보를 고려하여 분석의 정밀도를 높이는 기법이다. 여기서 문맥이란 함수가 호출된 특정 지점(호출 지점, call site)이나 호출 경로, 또는 객체 지향 언어에서의 수신 객체 등 분석의 정밀도에 영향을 미치는 부가 정보를 의미한다.

문맥을 고려하지 않는 분석(문맥 비민감 분석, context-insensitive analysis)은 서로 다른 상황에서의 함수 호출을 구별하지 못하여, 실제 프로그램 실행 결과보다 더 넓은 범위의 가능성을 포괄하는, 즉 덜 정밀한 결과를 내놓는 경향이 있다. 이는 컴파일러 최적화나 버그 탐색과 같은 후속 작업의 효율성을 저해할 수 있다.

문맥 민감 분석은 이러한 한계를 극복하기 위해 다양한 기법을 사용하며, 대표적인 기법들은 다음과 같다.

• 호출 지점 민감도: 함수가 호출된 소스 코드 상의 위치를 구별하여 분석한다.
• 객체 민감도: 메서드 호출 시 수신 객체의 정보를 이용하여 분석한다.
• 타입 민감도: 객체 대신 객체의 타입 정보를 이용하여 분석한다.

4. 1. 호출 지점 민감도 (Call-site Sensitivity)

그러나 Andersen의 알고리즘이나 Steensgaard의 알고리즘과 같이 컨텍스트에 민감하지 않은(context-insensitive) 분석 방식은 id 함수에 대한 두 번의 호출을 구별하지 못한다. 이로 인해 id 함수 내부의 포인터 p가 x의 주소(main::x)와 y의 주소(main::y) 모두를 가리킬 가능성이 있다고 분석하게 된다. 결과적으로, 함수 호출 이후의 포인터 u와 v 역시 main::x와 main::y 둘 다 가리킬 수 있다는, 실제보다 덜 정밀한(imprecise) 결과를 내놓게 된다.

호출 지점 민감도 분석은 이러한 부정확성을 개선한다. 이 분석 방식에서는 각 변수가 가리킬 수 있는 메모리 위치들의 집합(points-to set) 정보를, 해당 함수가 호출된 지점들의 목록으로 구성된 '컨텍스트(context)' 정보와 함께 관리한다. 이 컨텍스트는 프로그램의 제어 흐름을 추상화하여 나타내는 역할을 한다.

아래 코드처럼 각 호출 지점을 명시적으로 구분해 보자.



int *id(int* p) {

return p;

}

void main(void) {

int x;

int y;

int *u = id(&x); // 호출 지점 1 (예: main 함수의 3번째 줄)

int *v = id(&y); // 호출 지점 2 (예: main 함수의 4번째 줄)

}



호출 지점 민감도 분석은 '호출 지점 1'에서 호출된 id 함수와 '호출 지점 2'에서 호출된 id 함수를 서로 다른 컨텍스트에서 분석한다.

• '호출 지점 1'의 컨텍스트(예: [main.3])에서는 p가 x의 주소(main::x)만을 가리킨다고 분석한다.
• '호출 지점 2'의 컨텍스트(예: [main.4])에서는 p가 y의 주소(main::y)만을 가리킨다고 분석한다.

이처럼 호출 지점 민감도 분석은 각 함수 호출의 컨텍스트를 구별함으로써, 흐름 비의존적(flow-insensitive)이거나 컨텍스트 비민감(context-insensitive) 분석 방식에 비해 더 정밀한 포인터 정보를 제공할 수 있다.

4. 2. 객체 민감도 (Object Sensitivity)

(여기서 X::Y는 함수 X의 지역 변수 Y가 저장된 스택 할당 위치를 의미한다. p는 id 함수 내에서 호출에 따라 main::x 또는 main::y를 가리킬 수 있으므로, 가능한 모든 위치를 나타낸다.)

하지만 Andersen의 알고리즘이나 Steensgaard의 알고리즘과 같이 컨텍스트 비민감 분석은 id 함수를 분석할 때 두 호출(id(&x), id(&y))을 구분하지 못한다. 그 결과, id 함수로 전달된 모든 포인터 정보가 합쳐져 다음과 같이 부정확한 결과를 내놓는다.

이처럼 컨텍스트 비민감 분석은 u가 실제로는 main::x만 가리킴에도 불구하고 main::y도 가리킬 수 있다고 잘못 판단하게 된다.

4. 3. 타입 민감도 (Type Sensitivity)

5. 추가 정보

정적 분석의 한 형태로서, 완전히 정확한 포인터 분석은 결정 불가능하다는 것이 증명될 수 있다.^[1] 대부분의 포인터 분석 접근 방식은 안전성(soundness)은 보장하지만, 성능과 정밀도 면에서는 큰 차이를 보인다. 분석의 정밀도와 성능은 여러 설계 결정에 영향을 받으며, 일반적으로 정밀도가 낮을수록 성능이 높아지는 경향이 있다. 이러한 선택에는 다음이 포함된다:^[2][3]

• '''필드 민감도''' (''구조체 민감도''라고도 함): 구조체나 객체의 각 필드를 개별적으로 처리할지, 아니면 하나로 병합할지 결정한다.
• '''배열 민감도''': 배열의 각 인덱스를 개별적으로 모델링할지, 첫 항목만 분리하고 나머지를 병합할지, 또는 모든 항목을 하나로 취급할지 결정한다.
• '''컨텍스트 민감도''' (''다변성''): 프로그램의 특정 지점에 도달하기까지의 제어 흐름 정보를 요약하여 분석에 포함시킬지 여부이다.
• '''흐름 민감도''': 프로시저 내의 제어 흐름이 포인터 정보에 미치는 영향을 모델링할지 여부이다.
• '''힙 모델링''': 런타임 메모리 할당을 추상화하는 방식으로, 할당 위치(malloc 호출 등), 형상 분석 기반 모델, 할당 유형 또는 모든 할당을 하나의 단일 할당으로 취급하는 방식(힙 비민감도) 등이 있다.
• '''힙 클로닝''': 힙 및 컨텍스트 민감 분석에서 각 할당 위치를 해당 할당을 수행하는 명령어나 문으로 이어지는 제어 흐름의 요약 정보로 추가 구체화하는 방식이다.
• '''제약 조건''': 포인터 정보를 표현할 때 사용하는 제약 조건의 종류이다. Steensgaard 알고리즘에 사용된 동등성 제약은 합병-찾기(Union-Find) 자료 구조로 효율적으로 추적할 수 있으며, Andersen 알고리즘과 같은 부분 집합 제약 기반 분석의 정밀도를 희생하는 대신 높은 성능을 얻을 수 있다.

• 호출 사이트 민감도
• 객체 민감도
• 타입 민감도

참조

_[1] 논문 Undecidability of context-sensitive data-dependence analysis 2000-01-01
_[2] 간행물 Dimensions of Precision in Reference Analysis of Object-Oriented Programming Languages
_[3] 문서 Hind
_[4] 간행물 srcPtr: A Framework for Implementing Static Pointer Analysis Approaches https://www.zyrianov[...] IEEE
_[5] 간행물 SVF: interprocedural static value-flow analysis in LLVM https://yuleisui.git[...] ACM
_[6] 서적 Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages Association for Computing Machinery 2011-01-26
_[7] 서적 Proceedings of the 6th ACM SIGPLAN International Workshop on State of the Art in Program Analysis Association for Computing Machinery 2017-06-18
_[8] 문서 Smaragdakis Balatsouras
_[9] 논문 Context transformations for pointer analysis https://doi.org/10.1[...] 2017-06-14
_[10] 문서 Li Tan Møller Smaragdakis
_[11] 문서 Smaragdakis Balatsouras
_[12] 문서 Smaragdakis Balatsouras
_[13] 문서 Smaragdakis Balatsouras