10( ) CPLV11-90.hwp

Size: px

Start display at page:

Download "10( ) CPLV11-90.hwp"

서일 석
5 years ago
Views:

1 Concolic Testing 도구 KLEE 의다양한탐색방법비교 321 Concolic Testing 도구 KLEE 의다양한탐색방법비교 (Comparison of Search Strategies of KLEE Concolic Testing Tool) 김영주 김문주 (YoungJoo Kim) (Moonzoo Kim) 김윤호 정의준 (Yunho Kim) (Uijune Jung) 요약테스트케이스자동생성기법인 Concolic (concrete+ symbolic) 테스팅기법을사용하는테스팅도구인 KLEE 의심볼릭 state 를스케줄링하는탐색방법 (search strategy) 들의분기커버리지성능을비교분석했다. 또한분기커버리지를보다빠르게높일수있는 breadth first search (BFS) 를새롭게구현해기존방법들과비교했다. 본실험에서는 GNU Coreutils 버전 8.9 를대상으로, 주어진시간에각탐색방법들이달성하는분기커버리지 (branch coverage) 를비교하고결과를분석했다. 키워드 : Concolic 테스팅, 동적심볼릭수행, KLEE, 탐색방법, Breadth First Search Abstract Concolic (Concrete+symbolic) testing is an automated test case generation technique that works on target source code. This paper analyzes the branch coverage 본연구는교육과학기술부 / 한국연구재단우수연구센터육성사업의지원으로수행되었음 ( 과제번호 ) 이논문은제38회추계학술발표회에서 Concolic 테스팅기법을구현한 KLEE 테스팅도구의사례연구 의제목으로발표된논문을확장한것임 학생회원 : 한국과학기술원전산학과 jerry88@cs.kaist.ac.kr (Corresponding author 임 ) 종신회원 : 한국과학기술원전산학과교수 moonzoo@cs.kaist.ac.kr 비회원 : 한국과학기술원전산학과 kimyunho@kaist.ac.kr uijune.jeong@gmail.com 논문접수 : 2011년 12월 29일심사완료 : 2012년 2월 6일 CopyrightC2012 한국정보과학회ː개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지 : 컴퓨팅의실제및레터제18권제4호 (2012.4) performances of the search strategies of a Concolic testing tool KLEE. In addition, we implemented the breadth first search (BFS) strategy to get higher branch coverage in KLEE. To compare the effectiveness of the search strategies, we applied KLEE to GNU Coreutils version 8.9 and compared the branch coverage of these search strategies and analyze their results. Key words :Concolic Testing, Dynamic Symbolic Execution, KLEE, Search Strategy, Breadth First Search 1. 서론 동적심볼릭기법으로도알려진 Concolic 테스팅기법은동적테스팅과심볼릭수행을함께적용시킨기법이다 [1]. Concolic 테스팅기법은모든수행경로를커버하는테스트케이스를생성하는것을목표로하지만, 주어진시간안에높은분기커버리지를달성하는테스트케이스생성이중요하고, 이를위해심볼릭 state를스케줄링하는다양한탐색방법이제시됐다. 본논문에서는 Concolic 테스팅도구인 KLEE에서제공하는여러탐색방법들을비교하고, 또한새로운탐색방법으로 breadth first search(bfs) 방법을 KLEE 에새롭게구현했다. 기존탐색방법과 BFS 방법과의효과및효율성차이의비교, 분석을위해 GNU Coreutils 을대상으로각탐색방법별로대상프로그램들을테스트해분기커버리지결과를비교분석했다. 2. 관련연구 Concolic 테스팅기법은실제수행 (concrete execution) 으로부터심볼릭경로수식 (symbolic path formula) 추출방법에따라두가지로나뉜다. 첫째, 대상프로그램을정적으로 instrument하는테스팅도구다. 이카테고리의테스팅도구는 probe를삽입해실제수행으로부터심볼릭경로수식을추출한다. CREST[2], CUTE[3], DART[4] 등이이카테고리에해당한다. 둘째, 심볼릭경로수식을추출하기위해수정된가상머신을활용하는방법이다. KLEE[5] 는 LLVM[6] 바이너리를대상으로구현됐고, PEX[7] 는 Microsoft.Net 바이너리로컴파일되는 C# 프로그램을대상으로한다. Concolic 테스팅기법은다양한소프트웨어에적용되고있다. [8] 에서는플래시메모리플랫폼소프트웨어의멀티섹터읽기연산수행함수에 concolic 테스팅기법을적용해테스팅성능측정및장단점을분석했다. 또한 [9] 에서는오픈소스라이브러리 libexif에 concolic 테스팅툴인 CREST와 KLEE를적용해 concolic 테스팅기법의효과를분석하고, 두툴의장단점을분석해비교했다.

2 322 정보과학회논문지 : 컴퓨팅의실제및레터제 18 권제 4 호 (2012.4) 3. KLEE 테스팅도구 KLEE는 LLVM bitcode로컴파일된프로그램을인터프리트해 concolic 테스팅기법을수행하는도구다 [5]. KLEE는오픈소스로제공되며다양한탐색방법을포함한다는장점이있다. KLEE는심볼릭프로세스의운영체제와인터프리터역할을동시에수행한다. 심볼릭프로세스는실제 concolic 테스팅실행경로를따라가며분기조건 (branch condition) 을저장하는 concolic 테스팅을위한프로세스로, state라표현한다. 각 state는프로세스와동일하게스택, 힙, 프로그램카운터등의정보를갖고있고, 자신이수행한경로조건정보를축적해나중에경로종료시테스트케이스도출에쓴다. 3.1 KLEE 기본구조 KLEE는현재수행하는 state가분기지점에도달하면그분기의조건이 true로갈수있는지, false로갈수있는지의여부를판단하기위해 STP solver[10] 에게현재까지의심볼릭경로수식에현재분기조건을더해서쿼리로보낸다. true와 false 모두가능한경우 state를 fork하여자식 state를생성해그 state가 false 인경로조건을수행하도록 false 경로조건을추가하고, 자기자신은 true인경로조건을추가한다. 그리고현재모든실행가능한 state들중하나를택하고, 그 state의프로그램카운터가가리키는 instruction 수행을계속해모든가능한 state를다분석할때까지또는주어진시간제한까지수행한다 [5]. 예를들어그림 1 예제코드로부터 KLEE는각노드가분기지점이고, 총노드 7개인심볼릭수행경로트리를생성한다 ( 그림 2참조 ). 3-4번째줄은 i와 j변수를심볼릭변수로선언하고, 심볼릭변수가포함된분기조건그림 1 여러개의분기문을갖는예제코드그림 2 그림 1에서생성한심볼릭수행경로트리 ( 알파벳은각노드를수행한 state) 문만고려해심볼릭수행경로트리를생성한다. 제일처음 main에해당되는 a 1 state 생성후, i 값이아직정해지지않았으므로 5번째줄에서 i==0을만족하지않는, 즉 i!=0 조건의 b 1 state를생성하고, 자기자신은 i==0조건을저장한다. 이 true쪽경로조건이추가된 a 1 state를 a 2 state 라한다. 그후, a 2 와 b 1 state 중어떤 state를먼저선택해수행할지는탐색방법이결정한다 (3.2절참조 ). b 1 state가먼저수행한다가정할때, 10 번째줄의분기문을실행하고마찬가지방법으로 j!=1 조건의 c state를생성한다. 이때 b 1 state는 j==1 조건을저장하고이를 b 2 state라한다. 이렇게해서 b 2 와 c state는심볼릭수행을마치게된다. 이때, b 2 와 c state는자신들이축적한경로조건들을 solver에게보내각경로의테스트케이스를도출하며종료한다. 그다음에실행가능한 state는 a 2 state 뿐이므로, a 2 state 에서 d state를생성해분기조건을추가해 a 3 state로업데이트하고모든 state가종료하면서, 더이상수행가능한 state가없으므로 KLEE는종료하게된다. 3.2 State 스케줄링 ( 또는 state 탐색방법 ) KLEE는각 instruction 마다수행가능한 state들중하나를택해수행토록하는 state 스케줄링방법을사용한다. KLEE는총 6개의 non-uniform random search (NURS) 방법을제공하며 [5] 상응하는조건을만족하는 state를확률적으로우선선택한다. depth: 총수행한분기개수가적은 state. icnt: 총수행한 instruction이적은 state. cpicnt: 수행중인함수를수행한지얼마안된 state. 즉, 현재함수를수행한 instruction이적은 state. query-cost: STP solver가분기조건을푸는데걸린시간이적은 state. 즉, state가분기지점을수행할때마다그분기조건을 STP solver가푸는데걸린시간을축적해기록한값이작은 state. md2u: 아직커버되지않았지만곧커버할코드와거리가작아서새로운코드를곧커버할것같은 state. covnew: 새코드를커버한지얼마안된 state. 즉, 커버되지않았던코드를커버한가장최근시점부터지금까지수행한 instruction이적은 state. 그리고 round robin 방식으로일정시간, 혹은일정 instruction 개수수행후다음수행 state를선택하는배칭 (batching) 기법을위스케줄링기법과함께쓸수있다. 3.3 Breadth First Search (BFS) 방법본연구에서는 KLEE에서제공하는기존탐색방법외에새롭게 BFS 방법을구현했다. BFS 방법은루트노드에서시작해모든이웃한노드들을수행하며진행한다. 이방법은규모가큰대상프로그램의경우동시에너무많은 state 생성으로인한메모리부족문제가

3 Concolic Testing 도구 KLEE 의다양한탐색방법비교 323 있으나, 크기가작은 Coreutils와같은프로그램은효과적으로분기커버리지를높일수있다. BFS를 depth first search(dfs) 방법 ( 수행경로트리가장깊은부분까지먼저수행하며진행 ) 과비교해설명하기로한다. BFS 방법과 DFS 방법을그림 1에적용했을때수행순서는그림 3과같다. 우선 BFS 방법의수행순서는그림 1의 a 1 state( 그림 3 BFS 트리 1번노드 ) 가먼저선택돼수행되고, a 1 state 수행중 false 경로쪽분기조건을추가한 b 1 state가생성된다. 이때 a 1 state 는 true 쪽분기조건을추가해 a 2 state로업데이트된다. 그후스케줄링을통해 a 2 와 b 1 state 중 b 1 state(2 번노드 ) 를선택해수행한다. b 1 state 수행중 c state 가생성된시점에 b 1 state는 true쪽경로조건을추가해 b 2 state가되고, 스케줄링을통해 a 2, b 2, c state 중 a 2 state(3번노드 ) 를선택해수행한다. a 2 state 수행중 d state가생성된시점에 a 2 state는 true쪽경로조건을추가해 a 3 state가되고, 스케줄링을통해 a 3, b 2, c, d state 중 c state(4번노드 ) 를선택해수행한다. c state가수행을종료하고 a 3, b 2, d state만남은시점에 b 2 state(5번노드 ) 가선택되고, d state(6번노드 ), a 3 state(7번노드 ) 순으로선택돼수행한다. DFS 방법의수행순서는 a 1 state(dfs 트리 1번노드 ) 가먼저선택돼수행되고, a 1 state 수행중 b 1 state 가생성된시점에 a 1 state는 true쪽분기조건을추가해 a 2 state가된다. 그후스케줄링을통해 a 2 와 b 1 state 중 b 1 state(2번노드 ) 를선택해수행한다. b 1 state 수행중 c state가생성된시점에 b 1 state는 true쪽분기조건을추가해 b 2 state가되고, 스케줄링을통해 a 2, b 2, c state 중 c state(3번노드 ) 를선택해수행하고, c state 가수행을마치고종료하면 a 2 와 b 2 state 중 c state의마지막조건에반대되는쪽경로의 state인 b 2 state(4번노드 ) 를선택해수행한다. b 2 state가수행을종료하면 a 2 state밖에남지않아 a 2 state(5번노드 ) 를수행토록한다. a 2 state 수행중 d state가생성된시점에 a 2 state 는분기조건을추가해 a 3 state가되고, 아까와같은방식으로 d state(6번노드 ) 를먼저선택하고, d state 종료후 a 3 state(7번노드 ) 를선택해수행한다. BFS 방법을 KLEE에구현한알고리즘은그림 4와같다. 그림 4 알고리즘에서 StateQueue는 BFS 순서대그림 3 그림 1의소스코드에서 BFS와 DFS적용시수행경로그래프 ( 각노드번호는 state 선택순서 ) 로수행하기위한, state를각요소로하는큐구조체고, 프로그램첫번째 state를 initstate라가정하고시작한다 (1-2번째줄 ). 우선, 첫번째 state인 initstate가 StateQueue 안에들어간다 (3번째줄 ). StateQueue에 state가존재하므로 while 반복문내부로들어간다 (4번째줄 ). 현재 StateQueue에 initstate 밖에없으므로수행할 state인 curstate는 initstate를가리킨다 (5번째줄 ). 그후 Execute 함수에서인자로들어온 curstate 를한 instruction 수행하고, 분기를만나 fork해자식 state를생성한경우에만 childstates 배열에자식 state 부터자기자신순으로저장하고리턴한다 (6번째줄 ). childstates 배열의 state들은반복문을돌며 StateQueue 에삽입된다 (7-9번째줄 ). 그후수행가능한 state가존재하지않을때까지 while 반복문내에서위의수행단계를반복한다. 그림 4 BFS 방법의프로그램수행알고리즘 4. KLEE 적용비교분석 본장에서는 NURS 방법, DFS 방법및새로이구현한 BFS 방법을적용해달성한분기커버리지를측정해분석한다. 대상프로그램은 GNU Coreutils 8.9[11] 이고, 시간제약으로인해총 89개의유틸리티중기존 KLEE논문 [5] 에서실험했던 15개프로그램을선택했다. 선택한프로그램각각의분기개수및코드크기 ( 행수 ) 는표 1과같다. 각프로그램당수행시간은 30분으로 표 1 Coreutils 15개유틸리티의크기 유틸리티 분기수 LOC 유틸리티 분기수 LOC base pinky csplit seq df stat expr sum fmt tee ginstall tsort join unexpand nohup

4 324 정보과학회논문지 : 컴퓨팅의실제및레터제 18 권제 4 호 (2012.4) 그림 5 각대상프로그램에서의 6 가지 NURS 방법과 BFS 방법, DFS 방법별분기커버리지 제한했고, 각프로그램당 6가지 NURS 방법, DFS, BFS를적용해 concolic 테스팅을수행했다. 실험은 64 bit Fedora Linux 9, intel Core 2 Duo 3 GHz, 16GB 메모리를사용했다. 또한, KLEE 리비전 , LLVM 2.7[12], gcc 4.3.0, 그리고커버리지측정은 gcov 을사용했다. 4.1 수행옵션모든대상프로그램은입력값으로표준입력또는파일이들어가므로이를심볼릭으로처리해주는 KLEE의심볼릭 POSIX 라이브러리를사용하도록옵션을설정했고, 주요 C라이브러리를심볼릭하게지원하는 uclibc 라이브러리를포함했다. 또한모든실험은 state 스케줄링비용을줄이기위해 10000개 instruction마다스케줄링이생기도록배칭기법을적용했다. 4.2 가설설정실험에대한가설은다음과같다. 가설 ) 각탐색방법을 15개대상프로그램에적용해각탐색방법별평균분기커버리지를구했을때, 최대커버리지를가지는방법과최소커버리지를가지는방법의커버리지차가 10% 보다크다. 이때일반적으로커버리지차가적어도 10% 이상돼야커버리지차이가실제적의미를가진다고받아들여지므로그기준을 10% 로뒀다. 가설검정을위해각탐색방법별모든대상프로그램의평균분기커버리지 (%) 를측정했다. 평균분기커버리지측정은아래식과같은산술평균방식으로구했다. 여기서 Util total 은총유틸리티개수고, Cov(i) 는 i 번째유틸리티의분기커버리지 (%) 다. 평균최대커버리지를갖는탐색방법과최소커버리지를갖는방법의커버리지차가 10% 보다크면위가설을채택하고, 10% 이하면위가설을기각한다. 4.3 수행결과 6 가지특성의 NURS 방법과 DFS방법, BFS 방법을적용한결과는그림 5와같다. df의경우모든탐색방법의커버리지차가약 10% 이내로비슷한반면, base64, nohup, sum, tee는특정탐색방법이그외탐색방법 의평균보다약 20% 이상의차로높은분기커버리지를달성했다. 대체로 BFS가다른방법들보다높은커버리지를보이는경향을보인다. 그림 6의그래프에서보듯이평균분기커버리지를도출한결과 DFS 방법이약 57% 로가장낮았고, BFS 방법이약 70% 로가장높았다. 6 가지 NURS 방법들은 60-65% 였다. 평균최대커버리지를가지는방법과최소커버리지를가지는방법의커버리지차는약 13% 로, 위가설의기준인 10% 보다크므로, 가설을채택한다. 이는이전논문인 [13] 과다른결과로, Coreutils의유틸리티들이갖고있는특성을가진도메인에대해평균적으로봤을때우리가구현한 BFS 방법이 KLEE에서제공하는기존탐색방법과비교해보다효과적이며, 탐색방법의선택이중요하다는것을알수있다. 4.4 결과분석앞의실험결과분석을위해최고의성능을보인 BFS 방법과최저의성능을보인 DFS 방법을비교했다. NURS 방법은랜덤특성을가져 BFS와비교가힘들어직접비교는하지않았지만, NURS방법은 BFS와 DFS의중간특성및성능을보여 BFS와 DFS의비교분석결과의간접적용이가능하리라생각한다. csplit, ginstall, join, stat, unexpand의경우 BFS 방법이 DFS 방법보다약 30-50% 높은분기커버리지를보였다. tsort는예외적으로 BFS가 DFS보다약 40% 낮은분기커버리지를보였다. 각유틸리티소스코드분석결과, 두경우대상소스코드의구조특성이다름을파악했다. BFS 방법이효과적인 5개유틸리티는공통적으로그림 7 unexpand의 CFG 예 (a) 와같이수행트리윗부분에서커맨드라인에서받는다양한옵션처리에대한 switch문이존재하는, 다중분기정도가높은 CFG 구조였다. BFS에서는그림 6 각탐색방법별평균분기커버리지

5 Concolic Testing 도구 KLEE 의다양한탐색방법비교 결론및향후연구 (a) KLEE의여러탐색방법과새로이구현한 BFS 방법을 Coreutils의 15개유틸리티를적용해분기커버리지의성능차이를비교했다. 어떤탐색방법이든지약 57-70% 의높은분기커버리지를도출했으므로 concolic 테스팅이효과적이라는것을알수있다. 또한 Coreutils 유틸리티에대해 BFS 방법이 KLEE의기존탐색방법들보다분기커버리지측면에서우수했다. 앞으로보다큰규모대상프로그램으로 Concolic 테스팅의실제적효과에대해좀더분석하고연구할것이다. 참고문헌 (b) 그림 7 unexpand의 control flow graph (CFG) 예 (a), tsort의 search_item 함수의 CFG 일부분 (b) 모든가능한분기를커버하면서내려가므로, 그림 7(a) 의 BFS 상자와같이한번반복문수행에 switch 문의모든 case를커버했다. 반면, DFS는한분기끝까지커버하며반복문을수행하므로그림 7(b) 의 DFS 상자와같이반복문을돌며같은분기만계속수행해, 분기커버리지를높이지못하고결국 switch 문의한가지 case만커버했다. 따라서 unexpand 유틸리티에서 BFS 가 DFS 보다분기커버리지가약 40% 높았다. 반면, tsort유틸리티는커맨드라인에서받는옵션이없어다중분기가없었고, CFG가좁고깊은구조였다. BFS는 tsort 시작부분에서불리는 search _item함수 ( 그림 7(b)) 에서이미첫반복문수행시커버한분기들임에도계속반복문을돌며 true와 false 경로모두를커버하며많은 state를생성하느라 30분을다소요해, 제한시간내에 tsort 메인알고리즘의깊은부분에접근하지못했다. 반면, DFS는 search_item 함수의한쪽분기로만계속수행해반복문내로진입하지않고바로빠져나와, tsort 메인알고리즘의깊은부분까지접근해보다많은분기를커버했다. 이처럼대상프로그램의코드구조특성에따라효과적인탐색방법이존재할수있다. 그런면에서 Coreutils의대부분유틸리티가갖고있는, 커맨드라인옵션처리특성구조가 BFS 이용시커버리지측면에서유리하도록만든다고할수있다. [1] C. Pasareanu and W. Visser, "A survey of new trends in symbolic execution for software testing and analysis," in ICSE, [2] J. Burnim and K. Sen, "Heuristics for scalable dynamic test generation," in Technical Report UCB/ EECS , [3] K. Sen, D. Marinov, G. Agha, "CUTE: A concolic unit testing engine for C," in ESEC/FSE, [4] P. Godefroid, N. Klarlund, K. Sen, "DART: Directed automated random testing," in PLDI, [5] C. Cadar, D. Dunbar, and D. Engler, "KLEE: Unassisted and automatic generation of highcoverage tests for complex systems programs," in USENIX Symposium on OSDI, [6] C. Lattner and V. Adve, "LLVM: A compilation framework for lifelong program analysis & transformation," in CGO, [7] N. Tillmann and W. Schulte, "Parameterized unit tests," in ESEC/FSE, [8] M. Kim, Y. Kim and Y. Choi, "Concolic Testing of the Multi-sector Read Operation for Flash Storage Platform Software," in FACJ, Vol.24, No.2, [9] Y. Kim, M. Kim, Y. Kim, and Y. Jang, "Industrial Application of Concolic Testing Approach: A Case Study on libexif by Using CREST and KLEE," in ICSE SEIP track, Jun.2-9th [10] STP solver, [11] Coreutils 8.9, [12] LLVM 2.7, [13] Y. Kim, Y. Kim and M. Kim, "Case Study on Testing with KLEE Concolic Testing Tool," in KCC, 2011.

Chap 6: Graphs

Chap 6: Graphs 그래프표현법 인접행렬 (Adjacency Matrix) 인접리스트 (Adjacency List) 인접다중리스트 (Adjacency Multilist) 6 장. 그래프 (Page ) 인접행렬 (Adjacency Matrix) n 개의 vertex 를갖는그래프 G 의인접행렬의구성 A[n][n] (u, v) E(G) 이면, A[u][v] = Otherwise, A[u][v]