고성능 정적 프로그램 분석 기법 오학주 고려대학교 컴퓨터학과 서론 1 1.1 소프트웨어 오류 문제 소프트웨어가 모든 산업의 기반 기술이 되면서 소프트웨어의 오류로 인해 발생하는 사회경제적 비 용이 천문학적으로 증가하고 있다. 한 예로 미국의 투자금융회사인 KCG(Knight Capital Group)은 2012년 8월 1일 하루동안 2년치의 매출액에 해당하는 4억 달러의 손실을 입었는데, 이는 주식거래 소 프트웨어의 사소한 오작동 때문이었다.1 이뿐 아니라 소프트웨어 오류로 인한 손실은 IT, 전자, 기계, 항공, 국방 등 전 산업분야에 걸쳐 광범위하게 발생하고 있으며, 미국 표준원(National Institute of Standards and Technology)는 소프트웨어 오류로 인해 발생하는 미국내 사회경제적 손실을 연 595 억 달러로 추정한 바 있다.2 1.2 배경기술: 정적 프로그램 분석 정적 프로그램 분석(정적 분석, static program analysis)은 소프트웨어 오류 문제에 대한 유력한 답 으로 여겨지는 기술이다. 정적 분석은 주어진 프로그램이 실행중에 어떤 성질을 가지는지를 미리 엄밀하게 확인하는 기술로써, 프로그램의 모든 실행 경로에 대하여 오류가 없는지를 확인할 수 있다. 특히, 그 확인이 또 다른 소프트웨어(정적 분석기)를 통해서 자동으로, 대상 프로그램을 실행시키지 않고 이루어지므로 비용이 저렴하다. 특히, 정적 분석은 테스팅(program testing)을 보완하는 기술로 주목받고 있다. 테스팅은 소프트 웨어를 직접 실행시켜서 오류가 발생하는지를 확인하는 기술로써 소프트웨어의 오류를 찾는데 현재 가장 일반적으로 사용되는 기술이다. 하지만 테스팅은 주어진 유한한 입력에 대해서만 오류가 있음을 확인할 수 있을 뿐 오류가 없음을 검증하지 못한다. 또한 프로그램을 일일히 실행시켜야 하므로 대형 소프트웨어에 적용하기 어렵다. 1.3 고성능 정적 분석 기법 정적 분석이 실제 소프트웨어 개발 현장에서 일상적으로 사용되려면 해결해야할 문제가 많다. 특히 다음의 세가지 성능을 갖춘 정적 분석 기술이 필요하다. 안전성(Soundness): 정적 분석이 주어진 프로그램의 실제 실행을 모두 포섭하는지를 의미한다. 프로그램은 그 입력에 따라서 무한히 많은 실행을 가질 수 있는데, 정적 분석은 이 모든 가능 성을 포섭해야 하며, 이러한 정적 분석기를 안전(sound)하다고 한다. 정적 분석이 안전해야만 프로그램에 존재하는 모든 오류를 찾거나 특정 오류가 없음을 보장할 수 있다. 정확성(Precision): 낮은 오탐율을 의미한다. 정적 분석은 본질적으로 실제 프로그램 실행이 아닌 실행도 고려하게 된다. 예를들어, 프로그램에 x / y와같은 나누기 연산이 있고 프로그램 실행중에 y가 0을 가지는 경우가 절대 없지만, 정적 분석기는 y가 0을 가질 수 있어서 실행 중에 0으로 나누는 오류가 발생할 수 있다고 보고할 수 있다. 모든 정적 분석기는 근본적으로 정보과학회지 제34권 제3호 1 http://dealbook.nytimes.com/2012/08/02/knight-capital-says-trading-mishap-cost-it-440-million/?_r=0 2 http://www.ashireporter.org/homeinspection/articles/software-errors-cost-u-s-economy-59-5-billion-annually/ 740 1
Figure 1: 현존하는 정적 분석 기술의 한계와 본 연구의 목표. 이러한 허위경보(false alarm)를 가질 수 밖에 없는데, 오탐율(전체 경보중 허위경보의 비율)이 정확도의 척도가 된다. 유용한 정적 분석기는 충분히 낮은 허위경보율을 가져야 한다. 대형 프로그램(Scalability): 대형 소프트웨어를 적은 비용으로 분석할 수 있는 능력이다. 실제 현장의 소프트웨어는 그 크기가 수백만 라인에 달하는 경우도 흔하다. 대형 소프트웨어를 안 전하고 정확하게 분석하려면 보통 큰 분석 비용이 필요하기 마련이다. 하지만 실용적인 정적 분석기는 이러한 대형 소프트웨어를 적절한 비용(시간, 메모리)내에서 분석을 마칠 수 있어야 한다. 정적 분석 분야에서 위의 세가지 성능을 모두 갖춘 정적 분석 기술을 달성하는 것은 그동안 불 가능하다고 알려져 있었지만, 최근들어 조금씩 그 가능성을 보이는 연구성과들이 나오고 있다. 이 글에서는 이들 기술 가운데 두 가지 최신 기법을 설명한다. 먼저 2장에서는 기존 정적 분석 기술의 한계를 설명하고, 3장에서 이를 극복하기 위한 기술들을 소개한다. 2 기존 정적 분석 기술의 한계 그동안 안전하고, 정확하게, 대형 프로그램을 분석할 수 있는 정적 분석 기법은 불가능하다고 여겨져 왔다. 그 결과 현재 정적 분석 도구들은 그림 1(a)-(c)와 같이 제한적인 성능을 가진다. 오류 검출기 들은 안전성을 포기한다(그림 1(a)): 소프트웨어의 오류 검출을 목적으로 하는 정적 분석 도구들은 모두 실제 개발현장의 대형 소프트웨어를 적은 비용으로 분석할 수 있고 낮은 허위 경보율을 가지지만 이는 분석의 안전성을 포기함으로써 가능한 것이다. 따라서 이들 도구는 대상 오류를 모두 찾을 수 없고 일부만 검출할 수 있어서, 근본적으로 소프트웨어 테스팅 기술과 동일한 한계를 가진다. 오류 검증기 들은 대형 프로그램을 포기한다(그림 1(b)): 안전성이 매우 중요한 소프트웨어 (safety critical software)를 분석할 때는 대상으로 하는 모든 오류들을 찾아내는 것이 매우 중 요하다. 이 경우에 사용되는 오류 검증기들은 안전성을 유지한 채 낮은 허위경보율을 가진다. 하지만 이 경우 분석 비용이 매우 커져서 대형 프로그램에는 적용할 수 없다. 2
Figure 2: 스파스 분석 (Sparse Analysis) 아이디어 컴파일러 최적화 에 사용되는 정적 분석기법들은 정확성을 포기한다(그림 1(c)): 컴파일러는 그 특성상 안전성과 대형 프로그램을 포기할 수 없다. 따라서 컴파일러 최적화 단계에 사용되는 정적 분석 기법들(자료 흐름 분석, data-flow analyses)은 주로 프로그램의 간단한 특성을 알아 내는 기술들을 중심으로 발달해 왔고, 프로그램이 복잡해지면 충분히 최적화된 코드를 생성하지 못한다. 3 고성능 정적 분석 기법 이상적인 정적 분석은 그림 1(d)와 같이 안전성, 정확성, 대형 프로그램의 세 가지 성능을 모두 갖춘 것이다. 최근들어 이를 가능하게 하는 기법들이 발표되고 있는데 그 중 두가지 방법을 소개한다. 3.1 스파스 분석: 필요한 순간에, 필요한 부분만 분석하기 첫 번째는 필요한 순간에 필요한 부분만 분석하는 기법이다. 스파스 분석(sparse analysis)라고도 한다. 먼저 기존의 정적 분석이 동작하는 방식을 보자. 그림 2의 왼쪽은 흐름 그래프(control-flow graph) 로 표현한 프로그램을 정적 분석하는 과정을 보여준다. 흐름을 고려하는(flow-sensitive) 분석은 그림 과 같이 각 프로그램 지점마다 프로그램 변수들이 어떠한 값을 가지는지를 나타내는 요약 메모리를 계산하는 것이라 볼 수 있다 (그림에서 각 변수가 가지는 값들은 편의상 생략하였음). 이러한 요약 메모리들은 프로그램의 시작 지점부터 순차적으로 계산되는데, 예를 들어 첫 번째 문장 x=x+1 을 계산하면 입력 메모리의 x값이 x+1로 바뀌는 식이다. 이러한 단계를 거쳐서 마지막 문장까지 모두 요약 메모리를 계산하는 것을 정적 분석 과정으로 생각할 수 있다. 하지만 이 방식은 두가지 측면에서 불필요한 계산을 수반하고 있다. 첫 번째 문장인 x=x+1 을 계산하기 위해서는 x의 값만 필요함에도 불구하고 그 입력 메모리에는 모든 변수의 값이 저장되어 있 다. 그리고 여기서 새로 만들어진 x값은 세 번째 문장에서만 사용됨에도 불구하고 프로그램의 흐름을 따라서 x의 값이 모두 전파된다. 스파스 분석(sparse analysis)은 이러한 두가지 비효율성을 개선한 분석 기법이다. 그림 2의 오 른쪽을 보자. 스파스 분석에서는 먼저 각 프로그램 지점마다 해당 프로그램 지점에서 필요로 하는 변수의 값만을 기억하고 있다. 예를 들어, 첫 번째 문장에서는 x의 값만, 두 번째 문장에서는 y의 값만 3
Figure 3: 스파스 분석의 성능 향상 정도 이 매달려있다. 그리고 생성된 값들은 바로 그 값이 사용되는 지점으로 바로 전달된다. 예를 들어 첫 번째 문장에서 생성된 x의 값은 두 번째 문장을 거치지 않고 바로 세 번째로 전달된다. 이러한 과정을 거쳐서 필요한 부분만, 필요한 순간에 분석하는 기법이 스파스 분석이다. 그림 3는 정적 분석기 스패로우 [2]에 적용했을때 스파스 분석의 성능을 보여준다. 스파스 분석 기법이 적용되기 전에는 최대로 분석할 수 있는 프로그램의 크기가 3만 5000라인 정도인 반면, 스파스 분석을 최대로 적용했을때에는 백만라인 이상의 프로그램을 분석할 수 있을 정도가 되었다. 그리고 스파스 분석을 적용하지 않았을때의 분석속도(lines/sec)는 평균 600배가 증가하였다. 이처럼 스파스 분석은 간단하고 강력한 아이디어이지만 그 이론적 배경은 최근들어 정립되었다. 기존 컴파일러 최적화등의 기법들에서는 이러한 스파스 분석의 초기 아이디어들이 사용되었지만 그 기법들은 모두 초보적이었다. C 프로그램과 같이 포인터가 빈번히 사용되는 경우에는 각 프로그램 지 점마다 어떠한 변수들이 사용되는지 미리 알기가 어렵기 때문이다. 그래서 기존 기법들은 제한적으로 스파스 분석의 아이디어를 사용해왔다. 스파스 분석이 엄밀하게 정의되고, 그 유용성이 일반적으로 보여진 것은 최근의 일이다 [1, 3]. 3.2 선별적 정확도 향상 기법 두 번째로 소개할 기술은 정교한 정적 분석 기술을 선별적으로 적용하는 기법이다. 먼저 정적 분석에서 정확도 의 개념을 이해하기 위해서 아래 그림을 보자. 왼쪽 그림에서 별 영역은 프로그램이 실행중에 가지는 상태들을 의미하고 오른쪽 위의 팔각형은 프로 그램에서 오류가 발생하는 상태를 나타낸다. 프로그램 실행상태와 오류상태가 서로 겹치지 않으므로 실행중에 오류가 발생하지 않는 상황을 의미한다. 정적 분석은 프로그램을 실행시키지 않고 오류가 4
발생하지 않음을 알아내는 것인데, 이를 정확히 알아내는 것은 논리적으로 불가능하다 (이것이 가능 하면 종료문제(halting problem)을 푸는 것이 가능하기 때문). 따라서 정적 분석은 왼쪽 그림과 같이 프로그램 실행을 포함하는 요약 상태 를 계산하는데 왼쪽 그림과 같이 너무 안전하게 요약하면 실제 오류가 아닌데 오류라고 보고하는 허위경보(false alarm)가 발생하게 된다. 주어진 요약 상태로부터 많은 허위경보가 발생한다면 오른쪽 그림과 같이 정교하게 요약함으로써 허위경보를 최대한 줄일 수 있다. 하지만 이러한 경우 대게 정적 분석은 그 비용이 매우 커지게 된다. 즉, 정적 분석에는 본질적으로 비용이 작으면 정확도가 떨어지고, 정확도가 높으면 비용이 증가하는 딜레마가 있다. 선별적 정적 분석의 목표는 이러한 정적 분석의 딜레마를 해결하는 것이다. 핵심 아이디어는 매우 간단하다. 선별적 분석 방식에서는 아래 그림과 같이 오류가 발생할만한 지점의 요약 상태만 정교하게 하고, 나머지 부분에서는 부정확한 분석을 유지함으로써 분석 비용의 증가는 최소화하고, 그로 인한 정확도 증가는 최대화 시키는 것이다. 문제는 정교화할 부분을 어떻게 찾느냐인데, 이를 위해 두가지 방식이 제시되었다. 첫 번째는 사전 분석(pre-analysis)를 이용하여 정확도 향상이 예상되는 부분을 어림잡는 방식이다 [4, 5]. 본 분석을 진행하기에 앞서서 본 분석의 행동을 한단계 더 요약하여 그 행동을 예측하는 방식이다. 다른 방식은 정확도 향상이 예상되는 지점을 주어진 데이터로부터 학습하는 방식이다 [6]. 이 방식에서는 주어진 데이터(코드베이스)로부터 어떠한 부분을 선별하는 것이 가장 효과적인지를 학습하고, 새로운 프로 그램이 주어졌을 때 학습한 전략을 활용하여 정확도를 높일 부분을 선별해낸다. 두 가지 모두 최근에 제안된 기법으로 각각의 장단점을 가지고 있다. 사전분석 방식은 그 예측이 어느정도 올바르다는 이론적 보장이 가능하지만 각 분석 방식마다 사전분석을 전문가가 디자인해야 한다는 부담이 있고, 기계학습을 이용한 방식은 일반적으로 적용가능하지만 기계학습의 특성상 어떠한 보장도 해줄수 없다 는 점이다. 선별적 정적 분석은 현재 초기단계의 연구성과만 달성되었을 뿐이다. 앞으로 더 획기적인 선별방법, 혹은 위의 두 가지 방식의 장점을 결합하는 방법들이 계속 개발될 것으로 기대된다. 4 결론 이 글에서는 대형 프로그램을 안전하고 정확하게 분석할 수 있도록 하는 정적 분석 기법들의 최근 동향을 살펴보았다. 정적 분석은 소프트웨어 오류 검출 및 검증, 소프트웨어 취약점 검출, 프로그램 최적화, 변환, 합성 등 소프트웨어 개발 전반에 영향을 주는 기반 소프트웨어 기술이지만 현존하는 정적 분석 도구들은 모두 본질적인 제한점을 가지고 있다. 최근들어 그 제한점을 극복하려는 연구 가 수행되고 있고 차차 성과가 보이고 있다. 이 글에는 가장 최근에 이루어진 두가지 연구인 스파스 분석과 선별적 정적 분석 기법을 소개하였다. References [1] Hakjoo Oh, Kihong Heo, Wonchan Lee, Woosuk Lee, Daejun Park, Jeehoon Kang, and Kwangkeun Yi. Global sparse analysis framework. ACM Trans. Program. Lang. Syst., 36(3):8:1 8:44, September 2014. [2] Hakjoo Oh, Kihong Heo, Wonchan Lee, Woosuk Lee, and Kwangkeun Yi. Sparrow. http: //ropas.snu.ac.kr/sparrow. [3] Hakjoo Oh, Kihong Heo, Wonchan Lee, Woosuk Lee, and Kwangkeun Yi. Design and implementation of sparse global analyses for c-like languages. In Proceedings of the 33rd ACM 5
SIGPLAN Conference on Programming Language Design and Implementation, PLDI 12, pages 229 238, New York, NY, USA, 2012. ACM. [4] Hakjoo Oh, Wonchan Lee, Kihong Heo, Hongseok Yang, and Kwangkeun Yi. Selective contextsensitivity guided by impact pre-analysis. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 14, pages 475 484, New York, NY, USA, 2014. ACM. [5] Hakjoo Oh, Wonchan Lee, Kihong Heo, Hongseok Yang, and Kwangkeun Yi. Selective x- sensitive analysis guided by impact pre-analysis. ACM Trans. Program. Lang. Syst., 38(2):6:1 6:45, December 2015. [6] Hakjoo Oh, Hongseok Yang, and Kwangkeun Yi. Learning a strategy for adapting a program analysis via bayesian optimisation. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2015, pages 572 588, New York, NY, USA, 2015. ACM. 6