전민석

5 minute read

“안된다고 알려진 걸 되게 해보자”

내 박사 과정 동안 떠올렸던 아이디어 중에서 가장 자부심을 느끼는 아이디어는 단연코 컨텍스트 터널링[3]이다. 컨텍스트 터널링 이라는 아이디어 덕분에 박사 과정을 순탄하게 마쳤다고 해도 과언이 아니다. 좋은 아이디어였다는 이야기를 들으면 아직도 가슴이 벅차오르고 뿌듯함을 느낀다. 컨텍스트 터널링 이라는 아이디어를 기반으로 재미있고 학술적으로 멋진 결과들을 만들어왔지만, 처음부터 원대한 목표를 가지고 컨텍스트 터널링 을 만든 것은 아니었다. 처음에 컨텍스트 터널링 은 작고 엉뚱한 호기심에서 발견되었다.


컨텍스트 터널링이란?

컨텍스트 터널링 은 쉽게 말해 정적 분석에서의 스팸 필터링 기술이다. 자신의 받은 메일함에 들어가 보자. 받은 메일함 첫 페이지에는 중요한 최근 메일들이 정렬되어 것이다. 이때 한 통의 새로운 메일이 왔다고 생각해보자. 가장 먼저 아래와 같은 생각을 하게 될 것이다.

이 새로운 이메일은 지워야 하나 말아야 하나?

이메일을 지울 경우 새로운 메일은 더 이상 첫 페이지에서 볼 수 없게 되어 더 이상 최근 중요한 메일이 아니게 된다. 반대로 새로운 이메일을 지우지 않을 경우 첫 페이지 마지막에 있던 메일이 더 이상 첫 페이지에서 볼 수 없게 되어 더 이상 최근 중요한 메일이 아니게 된다.

위 분류 과정은 1초면 끝나지만 중요하다. 위 분류 과정이 없는 메일함을 상상해 보자. 메일을 매번 지우지 않을 경우 메일함은 스팸으로 꽉 차게 될 것이다. 메일함의 첫 페이지로 더 이상 최근 중요한 일을 파악할 수 없게 된다. 공감이 가지 않는다면 일주일만 모든 스팸 필터링 기능을 해제하고 새로운 메일을 지우지도 말아보자. 메일함은 광고와 스팸 메일들로 인해 쓰레기통이 될 것이다. 최근 중요한 업무를 파악할 수 없을뿐더러 메일 검색 기능마저 없다면 아무 일도 처리할 수 없을 것이다.

정적 분석에서 1981년 이후로 40년동안 사용되어온 함수 호출 요약 방식은 스팸 필터링 기술이 없는 (검색기능도 없는) 메일함의 첫페이지라고 할 수 있다. 만들어진 컨텍스트들은 전혀 중요하지 않은 요소로만 구성되어 (e.g., 스팸으로 꽉 찬 받은 메일함의 첫 페이지) 부정확한 분석의 원인이 되고 있다. 40년 묵은 관성에 의해 정적분석 분야에서는 아직도 스팸 필터링 기술이 없는 (검색 기능도 없는) 메일함을 사용하고 있다.

컨텍스트 터널링 은 함수 호출 요약에서 컨텍스트를 생성할 때 중요하지 않은 요소들을 필터링하는 기술이다. 작동 원리는 위에서 설명한 스팸 필터링 과정과 같다. k-컨텍스트 함수 호출 요약(e.g., 메일함에는 k개의 메일까지 있을 수 있음)에서 컨텍스트 터널링 의 동작방식은 아래와 같다.

위 그림이 이해되지 않는다면 Old context는 받은 메일함, New context element는 새로운 메일이라고 생각하면 된다. 컨텍스트 터널링 은 함수가 새로운 함수 호출 요소 c’ 에 의해 호출되었을 때, c’이 중요할 경우 c’을 사용하여 함수호출 컨텍스트를 생성한다 (e.g., 메일함에 새로운 메일이 들어오면서 가장 오래된 메일이 지워짐). c’ 이 중요하지 않을 경우 컨텍스트를 새로 생성하지 않는다 (e.g., 메일함에 변화는 없음). 컨텍스트 터널링 을 사용하는 분석은 분석 과정 동안 중요한 함수 호출 요소들만을 사용해 고품질 컨텍스트를 생성하게 된다. 실험적으로 확인한 컨텍스트 터널링 은 큰 포텐셜을 가진 기술이다. 어떻게 사용하느냐에 따라 듣도 보도 못한 정확도를 얻을 수 있다.


나는 어쩌다 문제를 만나게 되었나

당시는 대학원 2학기였다. 만족스러운 연구 주제를 찾지 못하고 있었으며, 약 한 달간 진행했던 연구에서 실패를 경험한 직후였다. 이에 따라 걱정과 불안이 밤잠을 설치게 만드는 시기였다. 충분한 고민 끝에 초심으로 돌아가기로 결심하고, 이전에 공부했던 정적 분석 교과서[1]를 다시 한번 열어보게 되었다. 단순한 복습을 목적으로 시작했지만, 처음 공부할 때와는 교과서의 내용이 사뭇 다르게 느껴졌다. 처음에는 단지 내용을 이해하는 데 급급해 깊이 있게 고민하지 못했던 것들에 대해 이제는 궁금증이 생겼다.

컨텍스트 터널링 이라는 아이디어는 안 된다고 알려진 걸 되게 해보다 발견하게 되었다. 아래 예제는 정적분석 수업 교과서[1]에서 1-위치 기반 함수 호출 구분 기법(1-callsite sensitivity)의 한계를 설명하기 위해 제시한 예제이다.

class S {
  Object id(Object a){ return a; }
  Object id2(Object a){ return a; }
}
class C extends S {
  void fun1() { 
    Object a1 = new A1(); 
    Object b1 = id2(a1);
  }
}
class D extends S {
  void fun2() {
    Object a2 = new A2();
    Object b2 = id2(a2);
  }
}

위 예제나 함수 호출 구분 기법을 이해할 필요는 없다. 다만, 위 예제는 위치 기반 함수 호출 구분 기법의 한계를 설명하기 위해 제작된 예제라는 것이다.

“…, we add an extra level of calling, via a method id2, which wraps id— a complication that would cause a loss of precision for a call-sitesensitive analysis.”
-Smaragdakis and Balatsouras [1]

당시 아래와 같은 엉뚱한 고민을 하게 되었다.

1-위치 기반 함수 호출 구분 기법으로 위 예제를 정확하게 분석하려면 어떻게 해야 할까?

지금 돌아와 생각해보면, 꽤 큰 도전이었다. 정적 분석을 10년 연구한 전문가가 분석 기법의 한계를 설명하기 위해 제작한 예제에 대해, 정적 분석을 1년정도 공부한 대학원생이 분석 기법의 한계가 아니라는 것을 보이겠다는 것이기 때문이다. 하지만, 당시 위 질문을 지적 호기심을 자극하는 퀴즈 정도로 여겨, 두려움 없이 도전 했었다. 컨텍스트 터널링 은 위 퀴즈에 대한 나의 해답이다.


나는 어떻게 이 문제를 풀게 되었나

위 퀴즈의 해답을 찾기 위한 목적으로, 이전에 읽었던 정적 분석 논문들을 처음부터 다시 살펴보게 되었다. 이전에는 내용을 파악하고자 논문을 읽었지만 이번에는 위 퀴즈의 해답을 찾기 위해 논문들을 읽었다. 목적 없이 내용 파악을 위한 논문을 읽는 것과 명확한 목적을 가지고 논문을 읽는 것은 다르다. 퀴즈의 해답을 찾기까지는 그리 오래 걸리지 않았다. 한 논문[2]을 읽다가 스치듯 우연히 _컨텍스트 터널링_을 떠올리게 되었다.

해당 논문(“Hybrid context-sensitivity for points-to analysis”)의 주된 내용은 위치 기반 함수 호출 구분 기법(call-site sensitivity)과 값 기반 함수 호출 구분 기법 (object sensitivity)를 조화롭게 사용하여 분석의 정확도를 끌어올렸다는 것이다. 위 퀴즈를 풀기 위하여 나 또한 위치 기반 함수 호출 구분 기법(call-site sensitivity) 과 값 기반 함수 호출 구분 기법(object sensitivity)를 조화롭게 사용해 보고자 하였다. 이해할 필요는 없지만 아래는 논문[2]에서 설명하는 값 기반 함수 호출 구분 기법 (Object Sensitivity)의 구현 중 일부이다.

MergeStatic (invo, ctx) = ctx

또한 아래는 위치 기반 함수 호출 구분 기법(call-site sensitivity)의 구현 중 일부이다.

MergeStatic(invo, ctx) = invo

위 두 구현을 보고 아래와 같은 구현이 스치듯 머릿속을 지나갔다.

MergeStaticSome(invo, ctx) = ctx
MergeStaticOthers(invo, ctx) = invo

위 구현은 위에서 설명한 두 함수 호출 구분 기법을 선택적으로 사용한다는 의미이다. 일부 함수 호출에 대해서는 MergeStaticSome 을 사용하고 나머지 함수 호출에 대해서는 MergeStaticOthers 을 사용하겠다는 것이다. 자세히 이야기 하지는 않겠지만 위 구현은 내가 도전했었던 퀴즈의 정답이었다. 컨텍스트 터널링 [3] 이 탄생하는 순간이었다.


배운 점

우리는 매일 일상에서 좋은 문제 또는 아이디어를 보고 있거나 이미 보았다. 다만 감지하지 못하고 있을 뿐이다. 일상에서 떠오르는 나만의 물음표 에 집중하고 도전해 보자. 좋은 연구는 작고 개인적인 물음표에서 시작한다. 컨텍스트 터널링 은 위와 같이 호기심에서 출발한 개인적이고 가벼운 퀴즈에서 시작 하였지만 이 후 센세이셔널한 임팩트를 가진 연구[4]로 발전하였다.


참조

[1] Yannis Smaragdakis and George Balatsouras (2015), “Pointer Analysis”, Foundations and Trends® in Programming Languages: Vol. 2: No. 1, pp 1-69. http://dx.doi.org/10.1561/2500000014

[2] George Kastrinis and Yannis Smaragdakis. 2013. Hybrid context-sensitivity for points-to analysis. SIGPLAN Not. 48, 6 (June 2013), 423–434. https://doi.org/10.1145/2499370.2462191

[3] Minseok Jeon, Sehun Jeong, and Hakjoo Oh. 2018. Precise and scalable points-to analysis via data-driven context tunneling. Proc. ACM Program. Lang. 2, OOPSLA, Article 140 (November 2018), 29 pages. https://doi.org/10.1145/3276510

[4] Minseok Jeon and Hakjoo Oh. 2022. Return of CFA: call-site sensitivity can be superior to object sensitivity even for object-oriented programs. Proc. ACM Program. Lang. 6, POPL, Article 58 (January 2022), 29 pages. https://doi.org/10.1145/3498720

Hits

You May Also Enjoy