2010/9/8

[Regex] 值得注意的 Regular Expression 樣式的潛在風險

Regex 本身已經十分複雜, 但不知道大家有沒有想過, 它的解析引擎和處理機制又是如何實作的呢? 一般來講, Regular Expression 的解析引擎可以分為三種, 一種叫做 DFA (Deterministic Finite Automation, 決定性有限自動機制), 另一種叫做 NFA (Nondeterministic Finite Automation, 非決定性有限自動機制), 還有一種叫做 POSIX NFA。.Net 採用了傳統的 NFA 引擎, 使得它既能兼顧速度與功能, 但缺點就是由於傳統 NFA 只接受它找到的第一個相符比對,它也可能讓其它比對無法被找到 (POSIX NFA 雖然可以找到, 但速度緩慢)