[解決済み] 正規表現に悪意のあるコードを入れる方法はありますか？

質問

公開用Webページに正規表現による検索機能を追加したい。他の HTML をエンコードする以外に、悪意のあるユーザー入力から保護するために何かする必要がありますか？

Google の検索は、悪意のある入力を検出するために正規表現を使用するという逆の問題を解決する人々であふれかえっていますが、私はそれに興味がありません。私のシナリオでは、ユーザー入力 は であり、正規表現です。

を使うことになります。 Regex ライブラリを使用します。

どのように解決するのですか？

サービス拒否の懸念

正規表現で最も一般的な懸念は、指数関数的、あるいは超指数関数的に増加する病的なパターンによるサービス拒否攻撃です! - そのため、解決するのに永遠にかかるように見えます。これらは特定の入力データでのみ表示されるかもしれませんが、一般的にこれが問題にならないようなものを作成することができます。

これらのうちのいくつかはコンパイル時に検出されるため、これらがどれであるかは、使用している正規表現コンパイラがどれほど賢いかによって多少異なります。 再帰を実装している正規表現コンパイラは通常、非累進をチェックするための再帰深度カウンターを内蔵しています。

Russ Cox の 2007 年の素晴らしい論文 正規表現マッチングはシンプルで高速にできる (しかし、Java、Perl、PHP、Python、Ruby、...では遅い）。 で、Henry Spencer のコードから派生したと思われるほとんどの現代の NFA が深刻なパフォーマンスの低下を被るが、Thompson スタイルの NFA にはそのような問題がない方法について述べています。

DFA によって解決できるパターンのみを認める場合、そのようにコンパイルすることができ、より速く、おそらくはるかに速く実行されます。しかし、そのためには 時間 がかかります。Coxの論文では、このアプローチとそれに付随する問題について言及しています。すべては古典的な時間-空間トレードオフに帰結します。

DFAでは、それを構築する（そしてより多くの状態を割り当てる）ことに多くの時間を費やします。一方、NFAでは、同時に複数の状態になることができ、バックトラックが昼食とCPUを食べることができるので、それを実行することにより多くの時間を費やします。

サービス拒否の解決策

おそらく、宇宙の熱的な死との競争の敗者側にあるこれらのパターンに対処する最も合理的な方法は、効果的に実行を許可される時間の最大量を配置するタイマーでそれらをラップすることです。通常、これは、ほとんどの HTTP サーバーが提供するデフォルトのタイムアウトよりもはるかに少ないでしょう。

これらを実装する方法は様々で、単純な alarm(N) を C レベルで実装する方法から、ある種の try {} をブロックし、タイミング制約を組み込んで特別に作成された新しいスレッドを起動させます。

コード コールアウト

コードの吹き出しを認める正規表現言語では、コンパイルする文字列から吹き出しを許可または禁止するメカニズムがあります。 が必要です。 が提供されるべきです。 コードの吹き出しが使用している言語内のコードのみである場合でも、それらを制限する必要があります。外部コードを呼び出すことができる必要はありませんが、呼び出すことができる場合は、より大きな問題が発生することになります。

例えば、Perl では、文字列の補間から作成された正規表現（これらは実行時にコンパイルされるため、そうなります）において、レキシカルスコープされた特別なプラグマでない限り、コードの吹き出しを持つことはできません。 use re "eval"; が現在のスコープで有効でなければなりません。

のようなシステムプログラムを実行するためのコード・コールアウトを忍び込ませることができないようにします。 rm -rf * のようなシステムプログラムを実行するためにコード・コールアウトを忍び込ませることはできません。コードコールアウトはセキュリティに敏感なので、Perl はすべての補間文字列でデフォルトでこれを無効にし、わざわざ再有効化する必要があります。

ユーザー定義可能な♪roperties

もう一つ、Unicodeスタイルのプロパティに関連した、セキュリティに敏感な問題が残っています - 例えば \pM , \p{Pd} , \p{Pattern_Syntax} または \p{Script=Greek} - その かもしれない は、その表記法をサポートするいくつかの正規表現コンパイラに存在します。

問題は、これらのうち、可能なプロパティのセットがユーザーによって拡張可能であることです。つまり、特定の名前空間における名前付き関数への実際のコード コールアウトであるカスタム プロパティを持つことができます。 \p{GoodChars} または \p{Class::Good_Characters} . あなたの言語がこれらをどのように処理するかは、調べる価値があるかもしれません。

サンドボックス

Perl では、サンドボックス化されたコンパートメントを Safe モジュールによるサンドボックス化された区画は、名前空間の可視性を制御することができます。他の言語でも同様のサンドボックス技術が提供されています。そのようなデバイスがある場合、信頼できないコードの限定的な実行のために特別に設計されているため、それらを調べるとよいでしょう。