有限狀態自動機FA 懶人在思考?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/) 推薦閱讀: 相关文章 {{#data}} {{title}} {{/data}}