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

作者:   發佈於:   #perl #regexp #fuzzing

拜讀了 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​ 引擎,雖然有代表性,但可能與實際上各市面上常見的引擎有點出入

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