포인터 분석

Pointer analysis

컴퓨터 과학에서 포인터 분석 또는 포인트 투 분석(point-to-analysis)은 어떤 포인터 또는 힙 참조가 어떤 변수 또는 저장 위치를 가리킬 수 있는지를 설정하는 정적 코드 분석 기법입니다.이것은 종종 이스케이프 분석과 같은 더 복잡한 분석의 구성요소이다.이와 밀접한 관련이 있는 기술은 형상 분석입니다.

(이것은 이 용어의 가장 일반적인 구어체 사용법입니다.두 번째 용도에는 위와 같이 정의된 포인트 투 분석과 별칭 분석의 총칭이 포인터 분석입니다.포인트 투 에일리어스 분석과 에일리어스 분석은 밀접하게 관련되어 있지만 항상 동등한 문제는 아닙니다.)

예

다음 예제 프로그램의 경우 포인트 투 분석은 포인트 투 세트의p{입니다.x,y}.

인트 x; 인트 y; 인트* p = 알 수 없는() ? &x : &y;

서론

정적 분석의 한 형태로서, 완전 정밀 포인터 분석은 결정할 [1]수 없다는 것을 보여줄 수 있다.대부분의 접근방식은 건전하지만 퍼포먼스와 정밀도가 매우 다양합니다.많은 설계 결정이 분석의 정밀도와 성능 모두에 영향을 미칩니다. 종종 (항상 그렇지는 않지만) 정밀도가 낮으면 더 높은 성능을 얻을 수 있습니다.다음과 같은 선택지가 있습니다.[2][3]

  • 필드 감도(구조 감도라고도 함):분석은 구조 또는 객체의 각 필드를 개별적으로 처리하거나 병합할 수 있습니다.
  • 어레이의 감도:배열에 민감한 포인터 분석은 배열 내의 각 인덱스를 개별적으로 모델링합니다.다른 선택지로는 첫 번째 엔트리만 따로 모델링하고 나머지는 함께 모델링하거나 모든 어레이 엔트리를 병합하는 방법이 있습니다.
  • 컨텍스트 감도: 포인터 분석은 각 프로그램 포인트로 이어지는 제어 흐름의 요약을 사용하여 포인트 투 정보를 검증할 수 있습니다.
  • 흐름 감도:분석을 통해 절차 내 제어 흐름이 포인트 투 팩트에 미치는 영향을 모델링할 수 있습니다.
  • 힙 모델링: 런타임 할당은 다음과 같이 추상화할 수 있습니다.
    • 할당 사이트(할당을 실행하는 명령 또는 명령, 예를 들어 콜)malloc또는 오브젝트 컨스트럭터).
    • 형태 분석을 바탕으로 한 더 복잡한 모델입니다.
    • 할당 유형 또는
    • 1개의 단일 할당(히프 감도라고 불립니다)
  • 히프 클로닝:힙 및 상황 의존 분석은 할당을 수행하는 명령 또는 문장으로 이어지는 제어 흐름의 요약을 통해 각 할당 현장을 추가로 검증할 수 있다.
  • 부분 집합 제약 조건 또는 동일 제약 조건:Point-to-Facts를 전파할 때, 다른 프로그램 문장은 변수의 Point-to-Set에 대해 다른 제약을 유도할 수 있습니다.Steensgaard 알고리즘에 사용된 것과 같은 등식 구속조건은 유니언-파인드 데이터 구조로 추적할 수 있으며, 하위 집합 구속조건 기반 분석(예: Andersen 알고리즘)의 정밀도를 희생시키면서 고성능으로 이어진다.

컨텍스트 비인시티브, 플로우 비인시티브 알고리즘

포인터 분석 알고리즘은 수집된 원시 포인터 사용법(한 포인터를 다른 포인터로 할당하거나 다른 포인터를 포인터로 할당)을 각 포인터가 가리킬 [4]수 있는 유용한 그래프로 변환하기 위해 사용됩니다.

Steensgaard의 알고리즘과 Andersen의 알고리즘은 포인터 분석을 위한 일반적인 컨텍스트 비센서티브, 흐름 비센서티브 알고리즘입니다.컴파일러에서 자주 사용되며 LLVM 코드베이스에 구현되어 있습니다.

흐름 비감응적 접근법

흐름 비감응 포인터 분석에 대한 많은 접근법은 힙 할당이 할당 사이트(즉, 프로그램 위치)[5]에 의해 추상화되는 추상 해석의 형태로 이해될 수 있다.

A diagram showing how pointer analysis abstracts runtime memory
흐름 비감응 포인터 분석에서는 할당 사이트별로 가능한 런타임 할당을 추상화하는 경우가 많습니다.실행 시 이 프로그램은 3개의 개별 힙 할당을 생성합니다.흐름 비감응성 포인터 분석에서는 이러한 포인터는 단일 추상 메모리 위치로 취급되므로 정밀도가 저하됩니다.

데이터로그에는 [6]Java용 Sult 분석 프레임워크의 알고리즘을 포함하여 많은 흐름 비감응 알고리즘이 지정되어 있습니다.

콘텍스트에 민감한 흐름 비감응 알고리즘은 각 절차를 [7]컨텍스트별로 한 번씩 여러 번 분석함으로써 일반적으로 일부 성능을 희생하면서 보다 높은 정밀도를 달성합니다.대부분의 분석에서는 '콘텍스트스트링' 방식을 사용합니다.콘텍스트는 엔트리의 리스트로 구성됩니다(컨텍스트엔트리의 일반적인 선택에는 콜사이트, 할당 사이트 및 [8]유형이 포함됩니다).종료(및 더 일반적으로 확장성)를 보장하기 위해 이러한 분석은 일반적으로 컨텍스트가 고정된 최대 크기를 가지며 필요에 [9]따라 가장 최근에 추가된 요소를 제거하는 k-제한 접근법을 사용한다.문맥 의존형 흐름 비감응형 분석의 3가지 일반적인 변형은 다음과 같습니다.[10]

  • 콜 사이트의 기밀성
  • 오브젝트 감도
  • 유형 감도

콜 사이트의 기밀성

콜 사이트의 감도에서는, 각 변수의 포인트 투 세트(각 변수가 가리킬 수 있는 추상적인 힙 할당의 세트)는, 프로그램의 콜 사이트 리스트로 구성되는 컨텍스트에 의해서 한층 더 수식됩니다.이러한 컨텍스트는 프로그램의 제어 흐름을 추상화합니다.

다음 프로그램은 콜 사이트의 감도가 흐름 비감응적, 상황 비감응적 분석보다 높은 정밀도를 달성하는 방법을 보여줍니다. 

인트 *아이디(인트* x) {   돌아가다 x; } 인트 주된() {   인트 y;   인트 z;   인트 *y2 = 아이디(&y); // 콜 사이트 1   인트 *z2 = 아이디(&z); // 콜 사이트 2   돌아가다 0; }

이 프로그램의 경우 상황 비감시적 분석은 (음향적이지만 부정확하게) 다음과 같은 결론을 내릴 것이다.x할당 보류 중 하나를 가리킬 수 있습니다.y또는 의 그것z,그렇게y2그리고.z2에일리어스를 지정할 수 있으며 둘 다 할당 중 하나를 가리킬 수 있습니다.콜 사이트에 민감한 분석에서는id콜 사이트1과 콜 사이트2의 2회, 및 그 2회, 및 그 요점x콜사이트에 의해 인정되기 때문에 분석에서는 다음과 같이 추정할 수 있습니다.main돌아온다,y2할당 보류만 가리킬 수 있습니다.y그리고.z2할당 보류만 가리킬 수 있습니다.z.

오브젝트 감도

오브젝트 감응 분석에서 각 변수의 포인트 투 세트는 메서드 호출의 리시버 객체의 추상 힙 할당에 의해 인정된다.콜 사이트의 감도와는 달리 오브젝트의 감도는 구문적이지 않거나 로컬적이지 않습니다.컨텍스트 엔트리는 포인트 투 분석 [11]중에 도출됩니다.

유형 감도

유형 감도는 리시버 객체의 할당 사이트가 리시버 [12]객체의 할당 사이트를 포함하는 메서드를 포함하는 클래스/타입으로 대체되는 객체 감도의 변형입니다.그 결과 오브젝트에 민감한 분석에서 사용되는 것보다 컨텍스트 수가 훨씬 적기 때문에 일반적으로 성능이 향상됩니다.

레퍼런스

  1. ^ Reps, Thomas (2000-01-01). "Undecidability of context-sensitive data-dependence analysis". ACM Transactions on Programming Languages and Systems. 22 (1): 162–186. doi:10.1145/345099.345137. ISSN 0164-0925. S2CID 2956433.
  2. ^ Barbara G. Ryder (2003). "Dimensions of Precision in Reference Analysis of Object-Oriented Programming Languages". Compiler Construction, 12th International Conference, CC 2003 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2003 Warsaw, Poland, April 7–11, 2003 Proceedings. pp. 126–137. doi:10.1007/3-540-36579-6_10.
  3. ^ () 오류:
  4. ^ Zyrianov, Vlas; Newman, Christian D.; Guarnera, Drew T.; Collard, Michael L.; Maletic, Jonathan I. (2019). "srcPtr: A Framework for Implementing Static Pointer Analysis Approaches" (PDF). ICPC '19: Proceedings of the 27th IEEE International Conference on Program Comprehension. Montreal, Canada: IEEE.
  5. ^ Smaragdakis, Yannis; Bravenboer, Martin; Lhoták, Ondrej (2011-01-26). "Pick your contexts well: understanding object-sensitivity". Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. POPL '11. Austin, Texas, USA: Association for Computing Machinery: 17–30. doi:10.1145/1926385.1926390. ISBN 978-1-4503-0490-0. S2CID 6451826.
  6. ^ Antoniadis, Tony; Triantafyllou, Konstantinos; Smaragdakis, Yannis (2017-06-18). "Porting doop to Soufflé: a tale of inter-engine portability for Datalog-based analyses". Proceedings of the 6th ACM SIGPLAN International Workshop on State of the Art in Program Analysis. SOAP 2017. Barcelona, Spain: Association for Computing Machinery: 25–30. doi:10.1145/3088515.3088522. ISBN 978-1-4503-5072-3. S2CID 3074689.
  7. ^ (Smaragdakis & Balatsouras, 29) 오류:: Balatsouras
  8. ^ Thiessen, Rei; Lhoták, Ondřej (2017-06-14). "Context transformations for pointer analysis". ACM SIGPLAN Notices. 52 (6): 263–277. doi:10.1145/3140587.3062359. ISSN 0362-1340.
  9. ^ (Li 등, 페이지 1:4) 오류:: (
  10. ^ (Smaragdakis & Balatsouras) 오류:: Balatsouras
  11. ^ (Smaragdakis & Balatsouras, 37) 오류:: Balatsouras
  12. ^ (Smaragdakis & Balatsouras, 39) 오류:: Balatsouras

참고 문헌