對正規表示式進行模糊測試

拜讀了 Cloudflare 服務中斷報告，腦海浮現了對正規表示式去進行模糊測試的想法。針對此題目，我於 2019 年 Europe PerlCon 研討會上給了場五分鐘的閃電講：Fuzzing regexp (WIP)。

模糊測試的過程，大致上設想如下：

1. 對所指定的測試目標 r （正規表示式​）生成一測試用函式 f(x)。此函式的參數 x 為一個字串，回傳值為一個正整數，表示處理參數之字串所需要的步數。
2. 隨機產生許多長度為 1...n 的字串 x
3. 取所有 ( length(x), f(x) ​) ，以線性回歸判斷兩者關係是否為線性

雖然已經初步以 Regexp::Debugger 完成 refuzz​，但尚有兩點問題待解：

1. 隨機生成的字串 x 有很高的機率是不會與 r 匹配成功的，如果只生成那種很快就會匹配失敗的字串，f(x) 就會一直很小​。必須仔細依 r 的內容來撰寫字串產生器才能進行較有效率的測試。
2. Regexp::Debugger 所實做的是沒有經過任何最佳化過的 DFA​ 引擎，雖然有代表性，但可能與實際上各市面上常見的引擎有點出入

總之是個可以來慢慢研究的主題，日後若有更新再來追加補充。