2 年 2019 月 XNUMX 日の Cloudflare 障害の詳細

ほぼ9年前、Cloudflareは小さな会社で、私はそこで働いていたわけではなく、単なる顧客でした。 Cloudflare を立ち上げてから XNUMX か月後、私のウェブサイトに次の通知が届きました。 jgc.orgDNSが機能していないようです。 Cloudflare が変更を加えた プロトコルバッファ、DNSが壊れていました。

私はすぐに Matthew Prince に「私の DNS はどこですか?」というタイトルで手紙を書きました。彼は技術的な詳細が満載の長い返信を返してきました。ここで通信全体を読んでください）、私はこう答えました。

出典: ジョン・グラハム＝カミング
日時：7年2010月9日14時XNUMX分
件名: Re: DNS はどこですか?
宛先: マシュー・プリンス

素晴らしいレポート、ありがとう。問題があれば必ず電話します。すべての技術情報を収集したら、これについて投稿する価値があると考えられます。オープンで正直なストーリーを楽しんでいただけると思います。特に、ローンチ以来トラフィックがどのように増加したかを示すためにグラフを添付する場合はそうです。

私のサイトでは適切な監視が行われており、障害が発生するたびに SMS を受け取ります。監視の結果、障害は 13:03:07 から 14:04:12 までに発生したことがわかります。テストは XNUMX 分ごとに実行されます。

きっと分かりますよ。ヨーロッパに自分の人間は必要ないと思いますか? 🙂

そして彼は答えた：

出典: マシュー・プリンス
日時：7年2010月9日57時XNUMX分
件名: Re: DNS はどこですか?
宛先: ジョン・グラハム・カミング

ありがとう。書いてくださった皆様にお返事をさせていただきました。私は今オフィスに向かっています。ブログに何か書くか、掲示板に公式の投稿を固定する予定です。私も完全に同意します、正直さがすべてです。

現在、Cloudflare は非常に大きな会社であり、私はそこで働いていますが、今では私たちの間違い、その結果、そして私たちの行動について率直に書かなければなりません。

2月XNUMX日の出来事

2 月 XNUMX 日、WAF のマネージド ルールに新しいルールを展開しました。 CPUリソースが不足していました 世界中のCloudflareネットワーク上のHTTP/HTTPSトラフィックを処理するすべてのプロセッサコア上で。新しい脆弱性や脅威に対応して、WAF の管理ルールを継続的に改善しています。たとえば、5 月に私たちは急ぎました。 ルールを追加SharePoint の重大な脆弱性から保護します。当社の WAF の重要な点は、ルールを迅速かつグローバルに展開できることです。

残念ながら、先週木曜日の更新には、バックトラッキングで HTTP/HTTPS CPU リソースを多量に浪費する正規表現が含まれていました。その結果、コアのプロキシ、CDN、WAF 機能が影響を受けました。グラフは、HTTP/HTTPS トラフィックを処理するためのプロセッサ リソースがネットワーク内のサーバーでほぼ 100% に達していることを示しています。

インシデント中のある時点での CPU 使用率

その結果、当社のクライアント（および当社のクライアントのクライアント）は、Cloudflareドメインで502エラーページを表示することになりました。 502 エラーは、空きコアはまだあるものの、HTTP/HTTPS トラフィックを処理するプロセスと通信できなかった Cloudflare フロントエンド Web サーバーによって生成されました。

この件でお客様にどれほどのご迷惑をおかけしたかは承知しております。私たちはとても恥ずかしいです。そして、この失敗により、インシデントに効果的に対処することができなくなりました。

あなたがこれらの顧客の一人だったら、おそらく怖がり、怒り、動揺しているでしょう。さらに、私たちは 世界的な混乱。 CPU 消費量が高くなるのは、正規表現の表現が不適切な 1 つの WAF ルールが原因で、過剰なバックトラッキングが発生しました。罪悪感のある表現は次のとおりです。 (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))

これはそれ自体興味深いものですが (これについては後ほど詳しく説明します)、Cloudflare サービスが 27 分間ダウンしたのは正規表現が間違っていたためだけではありません。障害に至った一連の出来事を説明するのに時間がかかり、対応が遅れました。この投稿の最後では、正規表現でのバックトラッキングについて説明し、その操作方法について説明します。

どうした

順番に始めましょう。ここでの時間はすべて UTC です。

午後 13 時 42 分に、ファイアウォール チームのエンジニアが検出ルールに小さな変更を加えました。 XSS 自動プロセスを使用します。これにより、変更要求チケットが作成されました。このようなチケットは Jira を通じて管理します (下のスクリーンショット)。

3 分後、PagerDuty の最初のページが表示され、WAF の問題が報告されました。これは、通常の動作を監視するために、Cloudflare の外部で WAF (数百個あります) の機能をテストする総合テストでした。このすぐ後には、他の Cloudflare エンドツーエンドサービステストの失敗、世界的なトラフィックの問題、広範囲にわたる 502 エラー、および世界中の都市にあるポイント オブ プレゼンス (PoP) からの不足を示す大量のレポートに関するアラートのページが続きました。 CPU リソースの。

これらのアラートをいくつか受信し、会議から飛び出し、テーブルに向かう途中で、ソリューション開発部門の責任者が、トラフィックの 80% が失われたと言いました。私は SRE エンジニアの元に駆けつけました。彼らはすでに問題に取り組んでいたのです。最初、私たちはそれが何らかの未知の攻撃であると考えました。

CloudflareのSREエンジニアは世界中に散らばっており、0時間体制で状況を監視しています。通常、これらのアラートは範囲が限定された特定のローカルな問題を通知し、内部ダッシュボードで追跡され、XNUMX 日に複数回解決されます。しかし、これらのページと通知は非常に深刻な事態を示していたため、SRE エンジニアは直ちに重大度レベル PXNUMX を宣言し、経営陣とシステム エンジニアに連絡しました。

そのとき、ロンドンのエンジニアたちはメインホールで講義を聞いていました。講義は中断され、全員が大きな会議室に集まり、さらに専門家が呼ばれた。これは、SRE が自分たちで対処できる典型的な問題ではありませんでした。適切な専門家を関与させることが急務でした。

14:00 に、問題は WAF にあり、攻撃はなかったと判断しました。パフォーマンス チームが CPU データを抽出したところ、WAF が原因であることが明らかになりました。別の従業員は strace を使用してこの理論を確認しました。他の誰かが、WAF に問題があることをログで確認しました。午後14時02分、世界中でXNUMXつのコンポーネントをシャットダウンするCloudflareに組み込まれたメカニズムであるグローバルキルを使用することが提案されたとき、チーム全体が私のところにやって来ました。

WAF のグローバル キルをどのように行ったかは別の話です。それはそれほど単純ではありません。当社は自社製品を使用しており、当社のサービス以来 アクセス が機能せず、内部コントロール パネルを認証してログインできませんでした (すべてが修正された後、内部コントロール パネルが目的で使用されていない場合に資格情報を無効にするセキュリティ機能が原因で、一部のチーム メンバーがアクセスできなくなったことがわかりました)長い間）。

そして、Jira やビルド システムなどの内部サービスにアクセスできませんでした。回避策のメカニズムが必要でしたが、それはあまり使用されませんでした (これも解決する必要があります)。最終的に、14 人のエンジニアが 07 時 14 分に WAF を無効にすることに成功し、09 時 XNUMX 分にはトラフィックと CPU レベルがどこでも正常に戻りました。 Cloudflareの残りの保護メカニズムは通常どおり機能しました。

次に、WAF の復元に着手します。状況が異常だったため、1 つの都市で別のトラフィックを使用してネガティブ テスト (変更が本当に問題なのか自問する) とポジティブ テスト (ロールバックが機能することを確認する) を実行し、そこから有料顧客を転送しました。

14時52分、原因が分かったと確信して修正し、WAFを再度オンにしました。

Cloudflareの仕組み

Cloudflareには、WAFのルール管理を専門とするエンジニアのチームがいます。検出率を向上させ、誤検知を減らし、新たな脅威が出現したときに迅速に対応するよう努めています。過去 60 日間で、WAF の管理ルールに対して 476 件の変更リクエストが処理されました (平均 3 時間に XNUMX 件)。

この特定の変更は、実際のクライアント トラフィックがルールを通過するものの、何もブロックされないシミュレーション モードで展開する必要がありました。このモードを使用して、ルールの有効性をテストし、偽陽性率と偽陰性率を測定します。ただし、シミュレーション モードであっても、ルールは実際に実行する必要があり、この場合、ルールにはプロセッサ リソースを過剰に消費する正規表現が含まれていました。

上記の変更リクエストからわかるように、展開計画、ロールバック計画、およびこのタイプの展開用の内部標準操作手順 (SOP) へのリンクがあります。ルールを変更するための SOP により、ルールをグローバルに公開できます。実際、Cloudflareでは、物事はまったく異なる方法で行われ、SOPでは、テストおよび内部使用のためにソフトウェアを最初に社内のPoint of Presence（PoP）（従業員が使用する）に出荷し、次に社内の少数のクライアントに出荷することが規定されています。隔離された場所に、次に多数のクライアントに、そして初めて全世界に。

見た目はこんな感じです。 BitBucket 経由で内部的に git を使用します。変更に取り組むエンジニアはコードを送信し、それが TeamCity に組み込まれます。ビルドが合格すると、レビュー担当者が割り当てられます。プル リクエストが承認されると、コードがアセンブルされ、一連のテストが (再度) 実行されます。

ビルドとテストが正常に完了すると、Jira で変更リクエストが作成され、適切なマネージャーまたはリーダーが変更を承認する必要があります。承認後、DOG、PIG、およびいわゆる「PoP 動物園」への展開が行われます。 カナリア （犬、豚、カナリア）。

DOG PoP は、Cloudflare の従業員のみが使用する Cloudflare PoP (他の都市と同様) です。内部使用のための PoP を使用すると、顧客のトラフィックがソリューションに流入し始める前に問題を発見できます。便利なもの。

DOG テストが成功すると、コードは PIG (モルモット) ステージに進みます。これは Cloudflare PoP で、少量の無料の顧客トラフィックが新しいコードを通過します。
すべてが正常であれば、コードは Canary に入力されます。世界のさまざまな地域に 3 つの Canary PoP があります。このコードでは、有料クライアントと無料クライアントのトラフィックが新しいコードを通過し、これがエラーの最後のチェックとなります。

Cloudflareでのソフトウェアリリースプロセス

コードが Canary で問題なければ、リリースします。 DOG、PIG、Canary、全世界のすべての段階を通過するには、コードの変更に応じて数時間または数日かかります。 Cloudflareのネットワークとクライアントは多様であるため、コードをすべてのクライアントにグローバルにリリースする前に、コードを徹底的にテストします。ただし、脅威には迅速に対応する必要があるため、WAF は特にこのプロセスに従いません。

WAFの脅威
過去数年間で、一般的なアプリケーションにおける脅威が大幅に増加しました。これは、ソフトウェア テスト ツールの可用性が向上したためです。たとえば、最近次のように書きました。 毛羽立ち).

出所： https://cvedetails.com/

多くの場合、概念実証が作成され、すぐに Github で公開されるため、アプリケーションを保守しているチームはアプリケーションを迅速にテストし、適切にセキュリティが確保されていることを確認できます。したがって、Cloudflareは、顧客がソフトウェアを修正する機会を得ることができるように、新しい攻撃にできるだけ早く対応する能力を必要としています。

Cloudflare の迅速な対応の好例は、5 月に SharePoint の脆弱性保護を導入したことです (ここで読む）。この発表が行われた直後、私たちは、お客様の SharePoint インストールの脆弱性を悪用しようとする膨大な数の試みに気づきました。当社のスタッフは常に新しい脅威を監視し、お客様を保護するためのルールを作成しています。

木曜日に問題を引き起こしたルールは、クロスサイトスクリプティング（XSS）から保護することを想定していた。このような攻撃も近年非常に頻繁になっています。

出所： https://cvedetails.com/

WAF のマネージド ルールを変更する標準手順は、グローバル展開の前に継続的インテグレーション (CI) テストを実施することです。先週の木曜日にこれを実行し、ルールを展開しました。午後 13 時 31 分に、エンジニアが変更を加えて承認されたプル リクエストを送信しました。

13時37分、TeamCityはルールを収集し、テストを実行し、ゴーサインを出しました。 WAF テスト スイートは、WAF のコア機能をテストし、個々の機能に対する多数の単体テストで構成されます。単体テストの後、膨大な数の HTTP リクエストを使用して WAF のルールをテストしました。 HTTP リクエストは、どのリクエストが WAF によってブロックされるべきか (攻撃を阻止するため)、どのリクエストが通過できるかを確認します (すべてをブロックせず、誤検知を避けるため)。しかし、過剰な CPU 使用率についてはテストしませんでした。また、以前の WAF ビルドのログを調べると、ルール テストの実行時間は増加しておらず、十分なリソースがないことを疑うのは困難であることがわかりました。

テストは合格し、TeamCity は午後 13 時 42 分に変更の自動デプロイを開始しました。

クイックシルバー

WAF ルールは脅威の即時修復に重点を置いているため、変更を数秒でグローバルに伝播する Quicksilver の分散キーバリュー ストアを使用して WAF ルールを展開します。当社のすべてのクライアントは、ダッシュボードまたは API 経由で構成を変更するときにこのテクノロジーを使用しており、そのおかげで当社は変更に超高速で対応できます。

クイックシルバーについてはあまり話してきませんでした。以前に使用していた 京都大物 キーと値のペアのグローバルに分散されたストアとして機能しましたが、運用上の問題があったため、私たちは独自のストアを作成し、180 以上の都市で複製しました。現在、Quicksilver を使用して、構成変更をクライアントにプッシュし、WAF ルールを更新し、クライアントによって作成された JavaScript コードを Cloudflare Workers に配布します。

ダッシュボード上のボタンをクリックするか API を呼び出してから、世界中で構成を変更するまでにかかる時間はわずか数秒です。お客様はこのセットアップの速さを気に入りました。そして、Workers は、ほぼ瞬時にグローバルなソフトウェアを導入できるようにします。平均して、Quicksilver は 350 秒あたり約 XNUMX の変更を伝播します。

そしてクイックシルバーは非常に速いです。平均して、世界中のすべてのコンピューターに変更を伝播するために、99 パーセンタイル 2,29 秒を達成しました。通常、スピードは良いことです。結局のところ、機能を有効にしたりキャッシュをクリアしたりすると、それはほぼ瞬時にどこでも行われます。 Cloudflare Workersを介したコードの送信は同じ速度で行われます。 Cloudflareは、顧客に適切なタイミングでの迅速なアップデートを約束します。

しかし今回の場合、スピードが私たちにひどい冗談を言い、ルールは数秒のうちにどこでも変更されました。 WAF コードが Lua を使用していることに気づいたかもしれません。 Cloudflareは本番環境と詳細でLuaを広範囲に使用しています WAFのLua 我々 すでに議論されています。 Lua WAF が使用する PCRE 内部的に照合のためにバックトラッキングを適用します。制御不能になった表現から保護するメカニズムはありません。以下では、これについて詳しく説明し、それに対して私たちが取り組んでいることについて説明します。

ルールがデプロイされる前は、すべてがスムーズに進みました。プル リクエストが作成されて承認され、CI/CD パイプラインがコードを収集してテストし、デプロイとロールバックを管理する SOP に従って変更リクエストが送信され、デプロイが完了しました。

Cloudflare WAF 導入プロセス

何がうまくいかなかった
先ほども述べたように、私たちは毎週数十の新しい WAF ルールを導入しており、そのような導入による悪影響から保護するための多くのシステムを導入しています。そして、何か問題が発生するときは、通常、複数の状況が一度に組み合わさって起こります。理由が 1 つだけ見つかった場合は、もちろん安心できますが、必ずしもそうとは限りません。これらが重なって、HTTP/HTTPS サービスの失敗につながった理由です。

1. エンジニアが、過剰な結果をもたらす可能性のある正規表現を作成しました。 後戻りする.
2. 正規表現による過剰な CPU の浪費を防ぐ機能が、数週間前の WAF のリファクタリングで誤って削除されました。このリファクタリングは、WAF のリソース消費を減らすために必要でした。
3. 正規表現エンジンには複雑さの保証がありませんでした。
4. テスト スイートは過剰な CPU 消費を検出できませんでした。
5. SOP により、複数段階のプロセスを必要とせずに、緊急でないルール変更をグローバルに展開することができます。
6. ロールバック計画では、完全な WAF ビルドを 2 回実行する必要があり、長い時間がかかりました。
7. 世界的な交通問題に関する最初の警報が発せられるのが遅すぎました。
8. ステータスページの更新に時間がかかりました。
9. 不具合によりシステムへのアクセスに問題があり、バイパス手順が十分に確立されていませんでした。
10. SRE エンジニアは、セキュリティ上の理由により資格情報の有効期限が切れたため、一部のシステムにアクセスできなくなりました。
11. 当社の顧客は、Cloudflare リージョンを経由するため、Cloudflare ダッシュボードや API にアクセスできませんでした。

先週の木曜日から変わったこと

まず、WAF のリリースに関するすべての作業を完全に停止し、次のことを行っています。

1. 削除した CPU 過剰使用保護を再導入します。 （準備ができて）
2. WAF の管理ルール内の 3868 個のルールをすべて手動でチェックして、過剰なバックトラッキングのその他の潜在的なケースを見つけて修正します。 (検証完了)
3. テスト セットにはすべてのルールのパフォーマンス プロファイリングが含まれています。 （予定：19月XNUMX日）
4. 正規表現エンジンへの切り替え re2 または さび - どちらも実行時保証を提供します。 （予定：31月XNUMX日）
5. Cloudflareの他のソフトウェアと同様に、ルールを段階的に展開するためにSOPを書き直していますが、同時に、攻撃がすでに始まっている場合に緊急にグローバルに展開する機能も備えています。
6. Cloudflare リージョンから Cloudflare ダッシュボードと API を緊急に削除する機能を開発中です。
7. ページ更新の自動化 クラウドフレアのステータス.

長期的には、私が数年前に作成した Lua WAF から離れていくことになります。 WAF の移動先 新しいファイアウォールシステム。これにより、WAF の速度が向上し、追加の保護レベルが得られます。

まとめ

この障害により、当社およびお客様にはご迷惑をおかけしました。私たちは状況を修正するために迅速に行動し、現在、クラッシュの原因となったプロセスの欠陥に取り組んでいるほか、将来新しいテクノロジーに移行する際に正規表現に関する潜在的な問題を防ぐためにさらに深く調査しています。

この度のサービス停止については非常に当惑しており、お客様にお詫び申し上げます。これらの変更により、このようなことが二度と起こらないようになることを願っています。

応用。正規表現をバックトラッキングする

式の仕組みを理解するには:

(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))

CPU リソースをすべて使い果たした場合は、標準の正規表現エンジンがどのように動作するかについて少し知っておく必要があります。ここで問題となるのはパターンです .*(?:.*=.*). (?: そして対応する ) は非キャプチャ グループです (つまり、括弧内の式は 1 つの式としてグループ化されます)。

過剰な CPU 消費のコンテキストでは、このパターンは次のように説明できます。 .*.*=.*。この形式では、パターンが不必要に複雑に見えます。しかし、より重要なのは、現実の世界では、あるフラグメントとその後に別のフラグメントが続くことをエンジンに要求する式 (WAF ルールの複雑な式など) が致命的なバックトラッキングにつながる可能性があることです。だからこそ。

正規表現では . 1 文字と一致する必要があることを意味します。 .* - 0 個以上の文字を「貪欲に」一致させます。つまり、最大の文字をキャプチャします。 .*.*=.* は、0 個以上の文字と一致し、次に 0 個以上の文字と一致し、リテラル = 文字を検索し、0 個以上の文字と一致することを意味します。

テストラインに行ってみましょう x=x。という表現に相当します .*.*=.*. .*.* 等号が最初のものと一致する前に x (グループのうちの1つ .* 一致 x、2番目のゼロ文字）。 .* after = 最後に一致 x.

この比較には 23 の手順が必要です。最初のグループ .* в .*.*=.* 貪欲に動作し、文字列全体と一致します x=x。エンジンは次のグループに移動します .*。一致する文字がもうないので、2 番目のグループ .* ゼロ文字と一致します (これは許可されます)。その後、エンジンが標識に移動します =。これ以上シンボルはありません (最初のグループ) .* 表現全体を使用した x=x)、比較は行われません。

そして、正規表現エンジンは最初に戻ります。彼は最初のグループに移ります .* そしてそれを比較します с x= （その代わり x=x)、その後 2 番目のグループと対戦します .*。 2番目のグループ .* 2番目と比較されます x, そしてまたしても文字が残りません。そしてエンジンが再びかかると = в .*.*=.*、何も機能しません。そして彼は再び後戻りします。

今回のグループは .* まだ一致します x=、しかし、2番目のグループ .* もういや x、ゼロ文字。エンジンはリテラル文字を見つけようとしています = パターンの中で .*.*=.*、しかし出てきません（結局最初のグループがすでに占領していました） .*）。そして彼は再び後戻りします。

今回は第一グループ .* 最初の x のみを取ります。しかし第二グループは .* 「貪欲に」捕らえます =x。何が起こるかすでに予想しましたか？エンジンはリテラルと一致しようとします =、失敗してまた後戻りします。

最初のグループ .* まだ最初のものと一致します x。 2番 .* だけかかります =。もちろん、エンジンは文字通り一致することはできません =、2番目のグループがすでにこれを行っているため、 .*。そしてまた後戻り。そして、3 文字の文字列を照合しようとしています。

その結果、最初のグループは、 .* 最初のもののみに一致します x二番目 .* - 文字がゼロの場合、エンジンは最終的にリテラルと一致します = 式で с = 列をなして。次は最後のグループです .* 前回のものと比較されます x.

のみの23ステップ x=x。 Perl の使用に関する短いビデオを見る 正規表現::デバッガ, これは、ステップとバックトラッキングがどのように発生するかを示しています。

これはすでに大変な作業ですが、代わりにどうでしょうか x=x 私たちは持っています x=xx?それは33ステップです。で、もし x=xxx? 45. この関係は直線的ではありません。グラフは以下との比較を示しています。 x=x до x=xxxxxxxxxxxxxxxxxxxx （20 x 後の =）。後の x が 20 ある場合 =、エンジンは 555 ステップでマッチングを完了します。 (また、負けてしまった場合は、 x= 文字列は単純に 20 で構成されます x、エンジンは一致しないことを理解するまでに 4067 ステップかかります)。

このビデオでは、比較のためにすべてのバックトラッキングを示しています x=xxxxxxxxxxxxxxxxxxxx:

問題は、文字列サイズが増加するにつれて、マッチング時間が超直線的に増加することです。ただし、正規表現を少し変更すると、状況がさらに悪化する可能性があります。持っていたとしましょう .*.*=.*; (つまり、パターンの最後に文字通りのセミコロンがありました)。たとえば、次のような式に一致させるには、 foo=bar;.

そして、ここで後戻りすると本当に悲惨なことになります。比較用 x=x 90 ステップではなく 23 ステップかかります。そしてその数は急速に増加しています。比べる x= そして、20 x, 5353歩必要です。これがチャートです。軸の値を見てください Y 前のグラフと比較してください。

興味があれば、5353 件の失敗したマッチング ステップをすべて確認してください。 x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;

貪欲なマッチングではなく遅延マッチングを使用することにより、バックトラッキングの程度を制御できます。元の表現を次のように変更すると、 .*?.*?=.*?、比較のために x=x 11 ステップ (23 ステップではありません) が必要です。はどうかと言うと x=xxxxxxxxxxxxxxxxxxxx。すべての理由は ? 後の .* 次に進む前に、最小限の文字数と一致するようにエンジンに指示します。

しかし、遅延マッピングはバックトラッキングの問題を完全に解決するわけではありません。悲惨な例に置き換えると .*.*=.*; на .*?.*?=.*?;の場合、実行時間は変わりません。 x=x それでも 555 ステップ必要です。 x= そして、20 x - 5353

(より具体性を高めるためにパターンを完全に書き直す以外に) できる唯一のことは、バックトラッキング メカニズムを備えた正規表現エンジンを放棄することです。これが今後数週間にわたって行われる予定です。

この問題の解決策は、ケント・トンプソンが記事を書いた 1968 年以来知られていました。 プログラミング手法: 正規表現検索アルゴリズム (「プログラミング方法: 正規表現検索アルゴリズム」)。この記事では、正規表現を非決定的有限状態マシンに変換し、非決定的有限状態マシンの状態変化後に、実行時間が一致した文字列に線形に依存するアルゴリズムを使用できるメカニズムについて説明します。

プログラミング方法
正規表現検索アルゴリズム
ケン・トンプソン
Bell Telephone Laboratories, Inc.、ニュージャージー州マレーヒル

テキスト内の特定の文字列を検索するメソッドについて説明し、コンパイラ形式でのこのメソッドの実装について説明します。コンパイラーは正規表現をソース・コードとして受け取り、IBM 7094 プログラムをオブジェクト・コードとして生成します。オブジェクト プログラムは、検索テキストの形式で入力を受け取り、テキスト文字列が指定された正規表現と一致するたびにシグナルを発行します。この記事では、例、問題、解決策を示します。

アルゴリズム
以前の検索アルゴリズムでは、部分的に成功した検索で結果が得られなかった場合、バックトラッキングが発生していました。

コンパイル モードでは、アルゴリズムはシンボルを処理しません。コンパイルされたコードに命令を渡します。実行は非常に高速です。現在のリストの先頭にデータを渡した後、正規表現内のすべての連続文字が自動的に検索されます。
コンパイルおよび検索アルゴリズムは、タイムシェアリング テキスト エディターにコンテキスト検索として組み込まれています。もちろん、このような検索手順を適用するのはこれだけではありません。たとえば、このアルゴリズムの変形は、アセンブラのテーブル内のシンボル検索として使用されます。
読者は正規表現と IBM 7094 コンピュータ プログラミング言語に精通していることを前提としています。

コンパイラ
コンパイラは、並列実行される 2 つのステージで構成されます。最初の段階は構文フィルタリングで、構文的に正しい正規表現のみを通過させます。このステップでは、正規表現と一致させるために「・」演算子も挿入します。 XNUMX 番目のステップでは、正規表現が後置形式に変換されます。第 XNUMX 段階では、オブジェクト コードが作成されます。最初の XNUMX つの段階は明らかなので、ここでは詳しく説明しません。

Thompson の記事は非決定性有限状態マシンについては触れていませんが、線形時間アルゴリズムを詳しく説明しており、IBM 60 用のアセンブリ言語コードを生成する ALGOL-7094 プログラムを紹介しています。実装は難しいですが、アイデアは非常にシンプルです。

現在の検索パス。これは、1 つの入力と 2 つの出力を持つ ⊕ アイコンで表されます。
図 1 は、正規表現の例を変換するときの XNUMX 番目のコンパイル手順の機能を示しています。この例の最初の XNUMX 文字は a、b、c で​​、それぞれスタック エントリ S[i] と NNODE フィールドを作成します。

既存のコードに NNODE を適用して、結果の正規表現を 5 つのスタック エントリに生成します (図 XNUMX を参照)

正規表現は次のようになります .*.*=.*トンプソンの記事の写真のように想像してみてください。

図では、 0 0 から始まる 3 つの状態と、状態 1、2、および 3 から始まる XNUMX つのサイクルがあります。これらの XNUMX つのサイクルは XNUMX つに対応します。 .* 正規表現で。ドットのある 3 つの楕円が XNUMX つのシンボルに対応します。記号付きの楕円形 = リテラル文字と一致します =。状態 4 が最終です。これに到達すると、正規表現が一致します。

このような状態図を正規表現のマッチングにどのように使用できるかを確認するには .*.*=.*、文字列のマッチングを見ていきます。 x=x。図に示すように、プログラムは状態 0 から開始します。 1.

このアルゴリズムが機能するには、ステート マシンが同時に複数の状態にある必要があります。非決定性の有限マシンは、可能なすべての遷移を同時に実行します。

入力データを読み取る前に、図に示すように、両方の最初の状態 (1 と 2) になります。 2.

図では、 2 は、最初のものを見たときに何が起こるかを示しています。 x в x=x. x 状態 1 から状態 1 に戻って、一番上の点にマッピングできます。または x 状態 2 から状態 2 に戻り、以下の点にマッピングできます。

最初に一致した後 x в x=x まだ状態 1 と 2 にいます。リテラル文字が必要なので、状態 3 または 4 に到達することはできません。 =.

次に、アルゴリズムは次のことを考慮します。 = в x=x。その前の x と同様に、状態 1 から状態 1 へ、または状態 2 から状態 2 への上位 XNUMX つのループのいずれかと照合できますが、アルゴリズムはリテラルと照合できます。 = そして状態 2 から状態 3 に移行します (すぐに状態 4)。これを図に示します。 3.

その後、アルゴリズムは最後のアルゴリズムに進みます。 x в x=x。状態 1 と 2 からは、状態 1 と 2 に戻る同じ遷移が可能です。 状態 3 から x 右側の点に一致し、状態 3 に戻ることができます。

この段階では各キャラクターが x=x 検討し、状態 4 に到達したので、正規表現はその文字列と一致します。各文字は XNUMX 回処理されるため、このアルゴリズムは入力文字列の長さに対して線形です。そして後戻りはありません。

明らかに、状態 4 に到達した後 (アルゴリズムが一致したとき)、 x=) 正規表現全体が一致し、アルゴリズムはそれをまったく考慮せずに終了する可能性があります。 x.

このアルゴリズムは、入力文字列のサイズに線形に依存します。

出所： habr.com