請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/76652完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 蕭旭君 | |
| dc.contributor.author | Ting-Wei Chen | en |
| dc.contributor.author | 陳庭緯 | zh_TW |
| dc.date.accessioned | 2021-07-10T21:34:31Z | - |
| dc.date.available | 2021-07-10T21:34:31Z | - |
| dc.date.copyright | 2016-11-02 | |
| dc.date.issued | 2016 | |
| dc.date.submitted | 2016-08-21 | |
| dc.identifier.citation | [1] American Fuzzy Lop (AFL). http://lcamtuf.coredump.cx/afl/.
[2] ECMAScript 2016 Language Specification. http://www.ecma-international.org/ecma-262/7.0/. [3] GNU Emacs - An extensible, customizable, free/libre text editor - and more. https://www.gnu.org/software/emacs/. [4] Google’s libfuzzer-bot. https://github.com/google/libfuzzer-bot/. [5] Oniguruma, a regular expressions library. https://github.com/kkos/oniguruma. [6] pcrefuzz - Fuzzer for PCREs. https://code.google.com/archive/p/pcrefuzz/. [7] RE2 is a fast, safe, thread-friendly alternative to backtracking regular expression engines. https://github.com/google/re2. [8] regex in Rust. https://github.com/rust-lang-nursery/regex. [9] RegExLib - the Internet’s first Regular Expression Library. http://www.regexlib.com/. [10] Regular Expression Matching Can Be Simple And Fast. https://swtch.com/~rsc/regexp/regexp1.html. [11] SDL Regex Fuzzer. https://www.microsoft.com/en-us/download/ details.aspx?id=20095. [12] Snort - Network Intrusion Detection & Prevention System. https://www.snort.org/. [13] Stack Overflow. http://stackoverflow.com/. [14] The Fuzzing Project. https://fuzzing-project.org/. [15] The Open Group Base Specifications Issue 7, Chapter 9 - Regular Expressions. http://pubs.opengroup.org/onlinepubs/9699919799/ basedefs/V1_chap09.html. [16] TIOBE programming community index. http://www.tiobe.com/tiobe_index. [17] V. Alfred. Algorithms for finding patterns in strings. Algorithms and Complexity, 1:255, 2014. [18] D. Blazakis. Interpreter exploitation: Pointer inference and JIT spraying. BlackHat DC, 2010. [19] S. K. Cha, M. Woo, and D. Brumley. Program-adaptive mutational fuzzing. In 2015 IEEE Symposium on Security and Privacy, pages 725–741. IEEE, 2015. [20] P. Clifford and R. Clifford. Simple deterministic wildcard matching. Information Processing Letters, 101(2):53–54, 2007. [21] S. Crosby. Denial of service through regular expressions. Usenix Security work in progress report, 2003. [22] J. Kirrage, A. Rathnayake, and H. Thielecke. Static analysis for regular expression denial-of-service attacks. In International Conference on Network and System Security, pages 135–148. Springer, 2013. [23] A. Rathnayake and H. Thielecke. Static analysis for regular expression exponential runtime via substructural logics. arXiv preprint arXiv:1405.7058, 2014. [24] A. Rebert, S. K. Cha, T. Avgerinos, J. Foote, D. Warren, G. Grieco, and D. Brumley. Optimizing seed selection for fuzzing. In 23rd USENIX Security Symposium (USENIX Security 14), pages 861–875, 2014. [25] K. Serebryany, D. Bruening, A. Potapenko, and D. Vyukov. AddressSanitizer: a fast address sanity checker. In Presented as part of the 2012 USENIX Annual Technical Conference (USENIX ATC 12), pages 309–318, 2012. [26] R. C. SomeshJha. Backtracking algorithmic complexity attacks against a nids. 2006. [27] E. Stepanov and K. Serebryany. MemorySanitizer: fast detector of uninitialized memory use in C++. In Proceedings of the 13th Annual IEEE/ACM International Symposium on Code Generation and Optimization, pages 46–55. IEEE Computer Society, 2015. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/76652 | - |
| dc.description.abstract | 正則表達式最初是在形式化語言理論中被用來描述正則語言。因為它簡潔精確的字串表達能力，人們不斷的為其擴展功能。如今，正則表達式已經是處理字串最強而有力的工具。但這些華麗功能也使得近代的正則表達式函式庫的實作異常複雜，且缺乏系統性的測試方法。本論文提出並實作了一個基於模糊測試的正則表達式測試框架。此測試框架可以系統性地測試多個正則表達式函式庫，並且包含了當前世上最大的正則表達式測試集。在測試各個函式庫的的過程中，我們發現了數個嚴重的安全問題，以及數十個程式臭蟲。 | zh_TW |
| dc.description.abstract | Regular expression was used to describe the regular languages in formal language theory. Due to its expressive power and compactness, it was extended with many new features, becoming the most important and extremely powerful tool for text manipulation nowadays. We are using regular expressions everyday everywhere. But modern regular expressions with fancy features introduced extremely high complexity of implementations, and we lack a way to systematically test them. This paper presents a fuzzing based framework to systematically examine multiple regular expression implementations. This framework contains the world's largest corpus of regular expression. Several critical security issues and dozens of bugs on many popular implementations were found by our framework. | en |
| dc.description.provenance | Made available in DSpace on 2021-07-10T21:34:31Z (GMT). No. of bitstreams: 1 ntu-105-R03922009-1.pdf: 842554 bytes, checksum: 0d6da42e1adfd7b3a63a756f2bcf651e (MD5) Previous issue date: 2016 | en |
| dc.description.tableofcontents | 口試委員會審定書 ii
誌謝 iii Acknowledgements v 摘要 vii Abstract ix 1 Introduction 1 2 Background 3 2.1 Common Security Issues Related to RE 3 2.1.1 Code Execution by Design 3 2.1.2 ReDoS 4 2.1.3 Inconsistent Behavior 4 2.1.4 Just Bugs 4 2.2 Guided Fuzzing 5 3 Proposed System 7 3.1 Corpus Preparation 7 3.2 Collaborative Fuzzing 8 3.3 Differential Testing 9 3.4 Progressive Integration 10 4 Result 11 4.1 Target Libraries 11 4.2 Bugs Found by FREE 12 4.2.1 Tasting Some DoS Bugs 12 4.2.2 Tasting Some Inconsistent Behavior 12 4.2.3 Tasting Some Critical Bugs 13 4.2.4 Tasting Some Bug on Shallowly Integrated Libraries 13 4.3 The Importance of Seeds 14 4.4 Library Fingerprinting 15 5 Mitigation 17 6 Related Work 19 7 Conclusion 21 Bibliography 23 | |
| dc.language.iso | en | |
| dc.subject | 資訊安全 | zh_TW |
| dc.subject | 正則表達式 | zh_TW |
| dc.subject | 模糊測試 | zh_TW |
| dc.subject | Regular Expression | en |
| dc.subject | Fuzzing | en |
| dc.subject | Security | en |
| dc.title | 模糊測試正則表達式函式庫 | zh_TW |
| dc.title | Fuzzing Regular Expression Implementations for Fun and Profit | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 104-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 鄭欣明,黃俊穎,黃世昆 | |
| dc.subject.keyword | 資訊安全,正則表達式,模糊測試, | zh_TW |
| dc.subject.keyword | Security,Regular Expression,Fuzzing, | en |
| dc.relation.page | 25 | |
| dc.identifier.doi | 10.6342/NTU201603457 | |
| dc.rights.note | 未授權 | |
| dc.date.accepted | 2016-08-22 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-105-R03922009-1.pdf 未授權公開取用 | 822.81 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。