주어진 프로그램과 k에 대한 최적 터널링 추상화 알고리즘

1. 문제 (Problem)

Context tunneling [Jeon, Jeong, Oh, OOPSLA 2018]은 k-limited context-sensitive points-to analysis에서 중요한 context element만을 선택적으로 유지하여 정밀도와 확장성을 동시에 향상시키는 기법이다. 핵심은 tunneling relation T ⊆ M × M을 적절히 선택하는 것이다.

현재 접근법의 한계

1. Heuristic의 간접성(Indirection): 학습 알고리즘은 주어진 프로그램에 대한 최적 T를 직접 찾는 것이 아니라, atomic feature의 boolean formula를 통해 T를 간접적으로 생성한다. Boolean formula로 표현 가능한 tunneling relation은 전체 공간의 극히 일부이다.
2. 최적성 보장 부재: Non-greedy 알고리즘은 greedy보다 나은 결과를 내지만, global optimum을 보장하지 않는다.
3. Non-monotonicity의 미해결: T ⊆ T'이라 해서 proved(FP(T)) ⊆ proved(FP(T'))가 성립하지 않음. Non-monotonic 공간에서 최적해를 효율적으로 찾는 알고리즘적 문제 자체는 미해결이다.
4. Program-specific vs. general heuristic의 gap: General heuristic이 program-specific optimum에 도달하지 못함을 시사한다.

문제의 형식화

T* = argmaxT |proved(FP(T))| s.t. cost(FP(T)) ≤ cost(FP(∅))

이 문제의 난이도:

• 공간 크기: 2|MP|2. DaCapo 프로그램에서 reachable methods가 수천~수만 개이므로, 공간 크기는 2106 이상
• Non-monotonicity: 표준 기법이 직접 적용 불가
• 평가 비용: 단일 T에 대한 계산이 전체 points-to analysis 실행을 요구

2. 목표 (Goal)

주어진 프로그램 P와 context depth k에 대해, 최적 또는 근-최적(near-optimal)의 tunneling relation T*를 효율적으로 찾는 알고리즘을 개발한다.

• 최적성: 근사 비율(approximation ratio)을 보장
• 효율성: 합리적 시간 내에 해를 찾음
• 비용 제약 준수
• 이론적 분석: NP-hardness 증명 또는 polynomial-time 알고리즘
• 실험적 검증: program-specific optimal과 general heuristic의 gap 정량화