模糊測試正則表達式函式庫

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.