Detail View

오픈 소스 소프트웨어의 증가와 더불어 코드 클론 (소프트웨어 내에서, 혹은 소프트웨어 간에 복제된 코드 조각) 역시 증가하고 있다. 코드 클론은 소프트웨어 개발 과정을 촉진한다는 장점이 있으나, 취약점이나 버그를 확산시킨다는 점에서 소프트웨어 보안에 악영향을 끼치기도 한다. 취약한 코드 클론은 오픈소스 생태계가 확대될수록 더 증가하며 많은 소프 트웨어 시스템을 오염시키고 있다. 지난 몇십 년간 코드 클론 탐지를 목표로 하는 연구가 수행되었으나, 대부분의 시도는 폭발적으로 증가하는 오픈 소스 코드 베이스의 사이즈를 감당하지 못하고 있다. 이러한 확장성의 결여는 소프트웨어 개발자가 코드 클론 및 코드 클론으로 인한 취약점을 쉽고 효율적으로 관리하지 못하는 주된 이유가 된다. 게다가, 기존의 코드 클론 탐지 기술 대부분은 일반적인 코드 클론 탐지에 초점이 맞추어져 있으므 로 “취약한” 코드 클론을 탐지하는 용도로 사용하기에 적합하지 않다.
본 논문에서는 확장성과 정확성을 겸비한 취약 코드 클론 탐지 기술인 VUDDY를 제안한다. VUDDY는 거대한 소프트웨어 시스템으로부터 취약 코드 클론을 신속하고 정확하게 탐지한다. 탐지 단위로서 함수를 채택하고, 자료 구조에 길이 분류를 적용함으로써 함수 시그니쳐 비교의 횟수가 최소화되어 확장성이 극대화되어 10억 라인의 코드를 전처리하는 데에 오직 14시간 17분밖에 소요되지 않으며, 실제 탐지에는 1초 내외가 소요된다. 또한, 취약점을 보존하는 추상화 기술을 개발 및 도입하여 코드 클론에 어느 정도의 수정이 가해지더라도 탐지가 가능하다. 이를 통해 VUDDY의 탐지 범위는 알려진 취약점뿐 아니라 알려진 취약점의 변형된 형태로까지 늘어나게 된다. 본문에서는 VUDDY의 원리를 설명하고 효율성을 평가하며, 실제 소프트웨어로부터 VUDDY가 찾아낸 취약 코드 클론 (e.g., Apache HTTP server daemon, 안드로이드 스마트폰 취약점 등)을 분석하고 기술한다.

With the growth of open source software (OSS), code clones - code fragments that are copied and pasted within or between software systems - are proliferating. Although code cloning may expedite the process of software development, it often critically affects the security of software because vulnerabilities and bugs can easily be propagated through code clones. These vulnerable code clones are increasing in conjunction with the growth of OSS, potentially contaminating many systems. Although researchers have attempted to detect code clones for decades, most of these attempts fail to scale to the size of the ever-growing OSS code base. The lack of scalability prevents software developers from readily managing code clones and associated vulnerabilities. Moreover, most existing clone detection techniques focus overly on merely detecting clones and this impairs their ability to accurately find “vulnerable” clones.
In this thesis, we propose VUDDY, an approach for the scalable detection of vulnerable code clones, which is capable of detecting security vulnerabilities in large software programs efficiently and accurately. Its extreme scalability is achieved by leveraging function-level granularity and a length-filtering technique that reduces the number of signature comparisons. This efficient design enables VUDDY to preprocess a billion lines of code in 14 hour and 17 minutes, after which it requires a few seconds to identify code clones. In addition, we designed a vulnerability-preserving abstraction technique that renders VUDDY resilient to common modifications in cloned code, while preserving the vulnerable conditions even after the abstraction is applied. This extends the scope of VUDDY to identifying variants of known vulnerabilities, with high accuracy. An implementation of VUDDY has been serviced online for free at IoTcube, an automated vulnerability detection platform. In this study, we describe its principles, evaluate its efficacy, and analyze the vulnerabilities VUDDY detected in various real-world software systems, such as Apache HTTPD server and an Android smartphone.

국문 요약 i
Abstract ii
Contents iv
List of Tables vii
List of Figures viii
List of Equations x
1. Introduction 1
1.1. Motivation 1
1.2. Approach 3
1.3. Contributions	4
1.4. Thesis Outline	4
2. Taxonomy and Related Work	6
2.1. Taxonomy 6
2.2. Related Work	7
2.2.1. Token-level granularity 7
2.2.2. Line-level granularity 8
2.2.3. Function-level granularity	8
2.2.4. File-level granularity 9
2.2.5. Hybrid granularity 10
3. Problem and Goal Statement 11
3.1. Problem Formulation 11
3.1.1. Clone detector 11
3.1.2. Abstract clone detector 11
3.2. Goals 12
4. The Proposed Method: VUDDY	13
4.1. Preprocessing	13
4.2. Clone Detection 18
5. Vulnerability Detection 20
5.1. Establishing a Vulnerability Database 20
5.2. Vulnerable Code Clone Detection 23
6. Implementation 25
6.1. Generating a Robust Parser 25
6.2. Selection of Hash Function 25
6.3. Dictionary Implementation 26
7. Theoretical Evaluation 27
7.1. Empirical Setup and Dataset	27
7.2. Scalability Evaluation 28
7.3. Accuracy Evaluation 30
7.3.1. Comparison with SourcererCC, DECKARD, and CCFinderX 30
7.3.2. Comparison with ReDeBug	33
7.3.3. Exact-matching vs abstract matching	37
8. Empirical Evaluation: Case Study 38
8.1. Kernel Clone Cases	38
8.2. Library Clone Cases	41
8.2.1. Database engines	42
8.2.2. Web servers and browsers	44
8.2.3. Others	47
8.3. Intra-project Code Clone Cases	48
8.4. Lessons Learned 49
9. Application: IoTcube	50
10. Discussion	56
10.1. The Use of Function-level Granularity	56
10.1.1. Time complexity	56
10.1.2. Memory use 58
10.1.3. Accuracy 59
10.2. Room for Speedup 60
10.3. Detecting Semantic Clones	60
10.4. Collecting Vulnerable Functions	61
10.5. Language Support 61
11. Conclusion 62
Reference 63