Selectively Sensitive Static Analysis by Impact Pre-analysis and Machine Learning

학위논문 (박사)-- 서울대학교 대학원 공과대학 전기·컴퓨터공학부, 2017. 8. 이광근.이 학위 논문에서는 정적 분석 성능을 결정짓는 세 가지 축인 안전성 (soundness), 정확도 (precision), 확장성 (scalability) 을 최대한 달성할 수 있는 방법을 제시한다. 정적 분석에는 여러가지 정확도 상승 기법들이 있지만, 무턱대고 적용할 시에는 분 석이 심각하게 느려지거나 실제 실행 의미를 지나치게 많이 놓치는 문제가 있다. 이 논문의 핵심은, 이렇게 정확하지만 비용이 큰 분석 기법이 꼭 필요한 곳만을 선별해 내는 기술이다. 먼저, 정확도 상승 기법이 꼭 필요한 부분을 예측하는 또 다른 정적 분석인 예비 분석을 제시한다. 본 분석은 이 예비 분석의 결과를 바탕으로 정확도 상 승 기법을 선별적으로 적용함으로서 효율적으로 분석을 할 수 있다. 또한, 기계학습 을 이용하여 과거 분석 결과를 학습함으로써 더욱 효율적으로 선별할수 있는 기법을 제시한다. 학습에 쓰이는 데이터는 앞서 제시한 예비 분석과 본 분석을 여러 학습 프 로그램에 미리 적용한 결과로부터 자동으로 얻어 낸다. 여기서 제시한 방법들은 실제 C 소스 코드 분석기에 적용하여 그 효과를 실험적으로 입증했다.1. Introduction 1 1.1 Goal 1 1.2 Solution 2 1.3 Outline 4 2. Preliminaries 5 2.1 Program 5 2.2 Collecting Semantics 6 2.3 Abstract Semantics 6 3 Selectively X-sensitive Analysis by Impact Pre-Analysis 9 3.1 Introduction 9 3.2 Informal Description 11 3.3 ProgramRepresentation 17 3.4 Selective Context-Sensitive Analysis with Context-Sensitivity Parameter K 18 3.5 Impact Pre-Analysis for Finding K 22 3.5.1 Designing an Impact Pre-Analysis 22 3.5.2 Use of the Pre-Analysis Results 28 3.6 Application to Selective Relational Analysis 35 3.7 Experiments 40 3.8 Summary 42 4 Selectively X-sensitive analysis by learning data generated by impact pre-analysis 47 4.1 Introduction 47 4.2 Informal Explanation 50 4.2.1 Octagon Analysis with Variable Clustering 50 4.2.2 Automatic Learning of a Variable-Clustering Strategy 52 4.3 Octagon Analysis with Variable Clustering 56 4.3.1 Programs 56 4.3.2 Octagon Analysis 56 4.3.3 Variable Clustering and Partial Octagon Analysis 58 4.4 Learning a Strategy for Clustering Variables 59 4.4.1 Automatic Generation of Labeled Data 60 4.4.2 Features and Classier 63 4.4.3 Strategy for Clustering Variables 64 4.5 Experiments 66 4.5.1 Effectiveness 67 4.5.2 Generalization 68 4.5.3 Feature Design 69 4.5.4 Choice of an Off-the-shelf Classification Algorithm 70 4.6 Summary 70 5 Selectively Unsound Analysis by Machine Learning 75 5.1 Introduction 75 5.2 Overview 78 5.2.1 Uniformly Unsound Analysis 78 5.2.2 Uniformly Sound Analysis 79 5.2.3 Selectively Unsound Analysis 80 5.2.4 Our Learning Approach 80 5.3 Our Technique 81 5.3.1 Parameterized Static Analysis 82 5.3.2 Learning a Classifier 83 5.4 Instance Analyses 87 5.4.1 A Generic, Selectively Unsound Static Analysis 87 5.4.2 Instantiation 1: Interval Analysis 91 5.4.3 Instantiation 2: TaintAnalysis 91 5.5 Experiments 92 5.5.1 Setting 92 5.5.2 Effectiveness of Our Approach 93 5.5.3 Efficacy of OC-SVM 96 5.5.4 Feature Design 97 5.5.5 Time Cost 98 5.5.6 Discussion 98 5.6 Summary 100 6 Related Work 106 6.1 Parametric Static Analysis 106 6.2 Goal-directed Static Analysis 107 6.3 Data-driven Static Analysis 108 6.4 Context-sensitivity and Relational Analysis 108 6.5 Unsoundness in Static Analysis 110 7 Conclusion 112Docto