懶人在思考？WAF研究中...

有限狀態自動機(Finate Automaton)是假想機器，用來判斷字元串是否匹配正則表達式。

FA：{Σ,S,T}

  • Σ：字母表{a,b}
  • S：狀態集合{S1,S2,S3,S4}
  • T：轉換表

當FA處於某個狀態時，若讀入一個字母表中的字元，那麼將查找轉換表，轉換到另一個狀態。

  • 圓圈表示：狀態
  • 線和線上字元表示：轉換表

S1是入口，看看自動機能表示哪些字元串？

abbb
abbababab
aaababab
bababab
aaa
bbb

可以看出此自動機和正則表達式[ab]+是等價的！

數學證明任何一個正則表達式都有一個等價的FA！ 任何一個FA也有一個等價的正則表達式！

我們要整一個FA來代替正則表達式：

  • 一來可以構建語義引擎，（開源XSS語義引擎核心技術：FA）
  • 二來可以為機器學習提特徵，（優化掉提特徵需要用到的正則表達式）

flex詞法分析

新建h-d.l文件，用？替換數字，其他原樣輸出，內容如下：

%%
[0-9]+ printf("?");
# return 0;
. ECHO;
%%

int main(int argc, char* argv[]) {
yylex();
return 0;
}

int yywrap() {
return 1;
}

生成C代碼，編譯運行：

root@ubuntu:/home/flex# flex h-d.l
root@ubuntu:/home/flex# ls
h-d.l lex.yy.c
root@ubuntu:/home/flex# gcc lex.yy.c
root@ubuntu:/home/flex# ./a.out
hackbiji2018
hackbiji?
.
.
#
root@ubuntu:/home/flex#

效果：

  • 輸入符合正則表達式[0-9]+ 列印？
  • 輸入符合正則表達式# 退出
  • 輸入符合正則表達式. 直接列印

注意優先順序先後順序，在前的優先順序高，是不是很強大！這一切都歸功於flex將正則表達式轉換成自動機FA ~

參考文獻：自己動手寫編譯器（pandolia.net/tinyc/）

推薦閱讀：

相关文章