MySQLの正規表現検索とReDoS対策

MySQLに格納されているデータから正規表現のパターンに一致するものを取得するという機能を実装するため、MySQLの正規表現検索について色々調べたことをまとめました。

この記事では主に2つのことを書いています。

• MySQLで正規表現検索する方法
• ReDoS対策

MySQLで正規表現検索する方法

MySQLには正規表現検索するための機能が備わっています。

例えば、下記のSQLではtitleに'はじめて'または'入門'が含まれているデータを取得できます。

SELECT title FROM books WHERE title REGEXP '(はじめての|入門)';

ReDoS対策

ReDoSとは正規表現の脆弱性を利用した攻撃のことです。
QiitaでReDoSについて書かれている記事を見つけたので詳細は下記をご覧ください。

MySQLのREGEXPにもReDoSの脆弱性があるので対策が必要です。

よくあるデータベース関連の脆弱性は事前に入力値をチェックしてSQL発行前にブロックしたり、危険な文字をサニタイズするなどて危険を取り除いたり、クエリー発行前に対策することができますが、ReDoSの場合は入力値は正規表現としては正しいため、事前に取り除くことが困難です。

そこでMySQLではReDoSなクエリーが実行された場合でも負荷がかからないようにする2つの仕組みが実装されています。

regexp_time_limit

REGEXPなどを使った正規表現の照会時間の上限を設定します。
デフォルトでは32msとなっているので、少しでも検証に時間がかかるとすぐにタイムアウトします。
もし照会に時間がかかる正規表現も許可したい場合はここの値をある程度上げる必要があります。

下記にタイムアウトになる例を載せます。

mysql> select title from books;
+------------------------------------------+
| title                                    |
+------------------------------------------+
| AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAC |
+------------------------------------------+
1 row in set (0.01 sec)

mysql> select title from books where title REGEXP '(A+)+B';
ERROR 3699 (HY000): Timeout exceeded in regular expression match.

regexp_stack_limit

REGEXPなどを使った正規表現の照会に使用可能な最大メモリーを設定します。
デフォルトでは8,000,000 Byte ≒ 7.6MBとなっています。

こちらもエラーになる例を載せます。
デフォルト値のままだとregexp_time_limitに先に引っかかってしまうのでデフォルトを小さくして実行しました。

mysql> SET GLOBAL regexp_stack_limit = 32;
mysql> select title from books where title REGEXP '(A+)+B';
ERROR 3698 (HY000): Overflow in the regular expression backtrack stack.

上記2つの仕組みについては下記ドキュメントの「正規表現のリソース制御」に記載されています。

また、各設定値のデフォルト値などはこちらに記載されています。

正規表現がReDoSになるかどうかを判定する方法

前述しましたが、ReDoSの場合は入力値は正規表現としては正しいため、事前に判断することが困難です。
では、どう判定するか？ですが、MySQLの場合はタイムアウトなどReDoS対策がされているので、遠慮せずにクエリーを実行してみてタイムアウトするかどうかで判定すれば良いと思っています。

クエリーを実行してみて、regexp_stack_limitやregexp_time_limitのエラーが発生したらReDoSになる正規表現と判断できます。

この方法で検証する場合、1つ注意点があります。
ReDoSはデータと正規表現の組み合わせで発生するということです。
例えば、regexp_time_limitのエラーが発生する例として紹介したクエリーでも下記のようにデータによってはタイムアウトしません。

mysql> select title from books;
+-------+
| title |
+-------+
| AB    |
+-------+
1 row in set (0.02 sec)

mysql> select title from books where title REGEXP '(A+)+B';
+-------+
| title |
+-------+
| AB    |
+-------+
1 row in set (0.01 sec)

そのため、事前にクエリーを実行してReDoSではないと判定した正規表現でも、のちに追加されたデータによってはReDoSになり得るので注意が必要です。