懒人在思考？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/）

推荐阅读：

相关文章