第VI部:オートマトン、トライ、意味解析ファイアウォール¶
1マイクロ秒未満の分類を支えるアルゴリズムを調べます。タグ付きのAho-Corasickオートマトン、IPv4/IPv6の基数トライ、意味解析WAFのバイトクラスによるトークナイザー、WEIGHによるスコア付けを持つ宣言的ポリシーエンジンです。
一回の走査による複数パターンの照合¶
密なDFAとしてのAho-Corasick¶
Sibunaには二つのリテラルパターンの集合があります。約40個のボットのシグネチャと、約100個の攻撃のシグネチャです。一つのフィールドを\(N\)個のパターンと一つずつ照合すると\(O(NM)\)です。AhoとCorasick(1975)のオートマトンは、失敗リンク付きのトライを構築した後、フィールドを一度だけ\(O(M)\)で走査します。Sibunaは構築時に失敗リンクを遷移表に組み込むので、走査は入力1バイトあたり表の読み込み一回で、パターン集合に関する分岐はありません。オートマトンはsibuna-patternsクレートにあります。
/// `state`(行のオフセット)から`byte`で一歩進む。
fn step(&self, state: usize, byte: u8) -> usize {
self.table[state + usize::from(self.classes[usize::from(byte)])] as usize
}
pub fn find_first(&self, haystack: &[u8]) -> Option<Match> {
let mut state = 0;
for (index, &byte) in haystack.iter().enumerate() {
state = self.step(state, byte);
if state >= self.first_match {
let id = self.first_output_in(self.match_state(state), self.all_tags)?;
return Some(self.report(id, index + 1));
}
}
None
}
状態は一つの平坦な表の中の行オフセットとして保存するので、1ステップは加算一回と読み込み一回です。状態には、すべての一致状態が他のすべての状態の後に来るように番号を付けます。そのため一致の検出はfirst_matchとの比較一回で済み、内側のループで二つ目の表を読み込む必要はありません。
オートマトンの状態数の予算は実行時のオプションです。ポリシーエンジンは、根一つとすべてのシグネチャの長さの合計を上限として確保します。これはトライの状態数の安全な上限です。これにより、かつての大きすぎる固定サイズの表を避けつつ、すべてのバイトクラスについて密な遷移を保てます。各パターンは小さなカテゴリータグ(0から63なので、タグの集合は64ビットの語一つ)を持ちます。大文字小文字の同一視には、オートマトンとともに構築する256項目のバイトクラス表を使います。ある文字の大文字と小文字は同じクラスを共有し、どのパターンにも現れないバイトは一つのクラスを共有します。そのため表の1行の幅は256ではなく、パターン中の異なるバイトの数に1を足した値です。エンジンの正確なサイズと、逐次的な部分文字列探索との比較は第VIII部に記録しています。後者は同じパターンと、いずれかに一致すればよいという意味論を使います。
正規表現、SIMDエンジン、そして選択¶
シグネチャの段階には、三つの系統を比較検討しました。
- バックトラックする正規表現(バックトラック型ルールセットの方式)は、リクエストごとに数百のパターンを実行し、一致ごとにメモリを確保します。最も遅く、最も誤検知を起こしやすい選択肢です。
- SIMDリテラルエンジン(Hyperscan、Vectorscan)は、シャッフルに基づくニブルマスク(「Teddy」アルゴリズム)で16から32バイトのブロックを事前に絞り込み、候補をオートマトンで検証します。長い入力と大きなリテラル集合で真価を発揮します。代償は、数メガバイトのC++依存、コンパイル時のパターンデータベース、WebAssemblyターゲットがないこと、そして100バイト程度の入力では利点がないことです。フィールド全体の走査は、キャッシュミス一回より短い時間で終わります。
- 密なAho-Corasickと小さな構造トークナイザーの組み合わせはlibinjectionの系譜で、固定した表で正確に線形時間で動作し、バイナリの外に何も必要としません。
Sibunaのフィールドは短いので、メモリと速度の両面で三つ目の系統が勝ります。第VIII部では、8 KiBのボディーで1バイトあたり約1.56 nsを記録しています(意味解析の走査は12,784.3 nsで、benchmarks/results/primitives-latest.mdの8kb_body_semantic_scanです)。SIMDによる事前絞り込みが元を取るのはこのワークロードだけで、SID 0006はこれを未解決の項目として残しています。
IPv4とIPv6の基数トライ¶
128ビットのキーに対する一つの二分トライが両方のアドレス族に使われます。IPv6の接頭辞はそのまま挿入し、IPv4の接頭辞は::ffff:0:0/96に対応付けるので、/24は深さ120の経路になります。ノードはu32で添字付けた一つの平坦なVecに置き、添字0は根と「子なし」の両方を表します。そのため検索は高々128回の依存した読み込みで、ポインターをたどることはありません。このトライはsibuna-cidrクレートのPrefixTrieです。
IPv4の検索のたびに対応付けた接頭辞の96段をたどると、IPv4アドレスの最初のビットに達するまでに96回の依存した読み込みがかかります。そこでトライは初期化時に深さ96のノードを記録し、IPv4の検索をそこから始めます。
let (mut node, mut depth, mut best) = if is_ipv4_mapped(key) {
let start = self.ipv4_root;
let value = self.nodes[start as usize].value.as_ref();
(start, IPV4_DEPTH, value.or(self.nodes[0].value.as_ref()))
} else {
(0, 0, self.nodes[0].value.as_ref())
};
IPv4アドレスの分類には32.0 ns、IPv6アドレスには79.3 nsかかります(benchmarks/results/primitives-latest.mdのipv4_cidr_classificationとipv6_cidr_classification)。エンジンはトライを二回参照します。終端のallow/denyの判定はルール表の前に行うので、クラスター全体の禁止はどのルールにも優先します。challengeの判定はルール表の後に行います。
意味解析ファイアウォール¶
誤検知の教訓¶
WAFの最初の版は、平坦な部分文字列のリストをすべてのヘッダーと照合していました。リストには/*が含まれており、どのブラウザーもAccept: text/html,...,*/*;q=0.8を送ります。本物のブラウザーはすべてSQLインジェクションに分類され、403を受け取りました。この教訓が設計を形作りました。検出器が反応してよいのは構造に対してだけです。テストスイートは現在、select、--、アポストロフィーを含むコメント本文も含めた完全なChromeのリクエストをエンジンに通し、問題なしと判定されることを確認しています。
一回の走査でのバイトクラス¶
検査する各フィールドを一度走査し、どのバイトクラスが現れるかを集めます。引用符、=、<、シェルの区切り文字、%、NUL、正規化のきっかけ、連続した空白です。各検出器は再走査せずにこのクラスを参照し、正規化した二回目の走査は、きっかけが見つかったときだけ行います。走査は1バイトあたり256項目の表の参照一回で、sibuna-policyのWAFモジュールにあります。四つのアキュムレーターでORの連鎖を短く保ち、二つのバイトの組(/*と、隣り合う二つの空白)は、単独のバイトがまだ正規化を要求していないときだけ探します。
pub(crate) fn scan(text: &[u8]) -> Classes {
let (chunks, remainder) = text.as_chunks::<8>();
// 四つのアキュムレーターでORの連鎖を短く保ち、ロードを連続して発行できるようにする。
let mut lanes = [0u16; 4];
for chunk in chunks {
lanes[0] |= TABLE[usize::from(chunk[0])] | TABLE[usize::from(chunk[4])];
lanes[1] |= TABLE[usize::from(chunk[1])] | TABLE[usize::from(chunk[5])];
lanes[2] |= TABLE[usize::from(chunk[2])] | TABLE[usize::from(chunk[6])];
lanes[3] |= TABLE[usize::from(chunk[3])] | TABLE[usize::from(chunk[7])];
}
let mut bits = lanes[0] | lanes[1] | lanes[2] | lanes[3];
for &byte in remainder {
bits |= TABLE[usize::from(byte)];
}
// バイトの組が意味を持つのは、単独のバイトがまだ正規化を要求していない間だけ。
if bits & CANONICAL == 0
&& ((bits & SPACE != 0 && has_pair(text, b' ', b' '))
|| (bits & (SLASH | STAR) == SLASH | STAR && has_pair(text, b'/', b'*')))
{
bits |= CANONICAL;
}
Classes { bits }
}
検出器¶
- シグネチャ。すべてのカテゴリーの強いシグネチャは、一つのタグ付きオートマトンにあります。ヒットは、
waf:sqli、waf:xss、waf:path-traversal、waf:rceという名前の終端のdenyです。 - SQLインジェクション。一回の走査で語を読むスキャナーが、英数字の各語(最大7バイト)をキーワード表で引き、
or/andではliteral = literalという恒真式を確認します。id=1 or 1=1は終端です。それ以外の場合は引用符のバイトが必須で、証拠のスコアは次のうち4以上でなければなりません。引用符(1)、最大二つのキーワード(2)、コメント記号(1)、=(1)です。admin'--はそれだけで終端です。"it's a group order from the shop"のスコアは3で、通過します。 - クロスサイトスクリプティング。
<が必須です。スクリプトを載せられるタグが、属性の位置にあるon<event>=属性と同時に現れたときに反応します。onboarding=1は数えません。 - コマンドインジェクション。区切り文字が必須です。
;、|、&&、$(、バッククォート、改行の後に既知のコマンド名が続くときに反応します。status ok; done | nextは通過します。 - パストラバーサル。シグネチャ(
../、..%2f、/etc/passwd、id_rsaなど)に加えて、NULと%00。
文法上正当に引用符やアスタリスクを含む構造的なヘッダー(Accept*、Content-Type、Sec-*、If-*など)は飛ばします。パス、クエリ、User-Agent、その他のヘッダー、ボディーの先頭8 KBを検査します。パーセントエスケープ、プラス記号、コメントの開始記号、まとめられる空白を含むフィールドは、8 KBのスタック上のバッファーに正規化してもう一度検査します。そのため1%27/**/UnIoN/**/SeLeCtや%252e%252e/は、元のシグネチャに帰着します。
コスト¶
検査のコストは、リクエストの数だけでなく、エンジンに渡されるフィールドとバイトによって決まります。ベンチマークの章では、Gate、Shield、8 KBのボディーの場合を別々に報告します。8 KBという上限は検査の制限であり、アップロードの残りが安全だという主張ではありません。forward-authを使うイングレスは、関係するリクエストの情報を渡さなければなりません。渡されなかったバイトを、このプロセスは検査できません。
宣言的ポリシーエンジン¶
ルールは任意の条件(パスのパターン、User-Agentのパターン、最大四つのヘッダー、最大八つのIPv4/IPv6 CIDRブロック、一つのJA4フィンガープリントまたは接頭辞)の論理積で、動作ALLOW、DENY、CHALLENGE、WEIGHのいずれか、任意のルールごとの難易度(作業ビット)とアルゴリズム、符号付きのweightを持ちます。評価の順序は次のとおりです。
- 意味解析WAF(Shieldのみ):違反は終端の
denyです。 - レピュテーショントライ:
denyまたはallowの接頭辞は終端です。 - ルールを順に:最初の終端の一致で返ります。
WEIGHの一致は累積します。 - スコア:合計が負なら
allow。合計が\(\geq 40\)ならdeny。合計が\(\geq 10\)ならchallengeで、しきい値を5点超えるごとに作業ビットを一つ加え、最大で六つまで加えます。 - バイパス対象の静的パス、次にトライの
challengeの判定、次にボットのオートマトン。 - 既定の動作。ポリシーファイルで別に指定しない限り
challengeです。
組み込みのルールは、/.well-known/*、/favicon.ico、/robots.txt、/__sibuna/*を許可し、CF-WorkerのクライアントとAmazonbotを拒否し、Mozillaを含むすべてのUser-Agentにチャレンジします。ブラウザーの文字列は自由に偽造できるので、それだけで許可すればゲートは飾りになってしまいます。
{
"default_action": "CHALLENGE",
"waf": true,
"thresholds": { "challenge_at": 10, "deny_at": 40, "bits_step": 5 },
"ip_rules": { "10.0.0.0/8": "ALLOW", "2001:db8::/32": "DENY" },
"rules": [
{ "name": "internal-api", "path": "/api/*", "headers": { "X-Api-Key": ".*" },
"action": "ALLOW" },
{ "name": "checkout", "path": "/checkout/*", "action": "CHALLENGE",
"challenge": { "difficulty": 20, "algorithm": "posw" } },
{ "name": "headless", "user_agent": "Headless", "action": "WEIGH", "weight": 30 },
{ "name": "no-language", "headers": { "Accept-Language": "" },
"action": "WEIGH", "weight": -5 }
]
}
実行トレースの例:有効なセッションを持つエンコードされた攻撃¶
有効なセッションを持つクライアントからのGET /search?q=%2527%2520OR%25201%253D1を考えます。まずHTTPパーサーが、バイトをコピーせずにパスとクエリを分けます。ローカルの制限が実行され、次にShieldがリクエストを検査します。パーセント記号があるので、このフィールドは正規化の対象になります。一回のデコードで%27%20OR%201%3D1が現れ、二回目で' OR 1=1が現れます。
トークナイザーは引用符、キーワードOR、等しいリテラルのオペランドを見つけます。拒否はポリシーの終端の結果です。有効なセッションがあっても許可には変わりません。セッションの確認が解決するのはチャレンジの判断だけです。ストレージのフックは上限のあるインシデントレコードをコピーし、SQLは後で実行されます。オリジンへの接続がアイドルの間、応答の経路がエンジンのスナップショットを保持し続ける必要はありません。