はじめに

寒い日が続きますが、みなさんいかがお過ごしでしょうか。本連載は「著名なOSSに過去発見された脆弱性を題材に、その修正方法について解説していく」という趣旨で、前号（2021年2月号）よりスタートしました。そして、連載第1回目にはcURLの脆弱性を取り上げました。連載第2回目となる今回は、Pythonにおいて2020年に修正された脆弱性を紹介します。具体的には、CVE番号で表すと「CVE-2020-8492」にあたる脆弱性の脆弱性箇所と、その修正方法について説明します。

恐らくエンジニアならば、誰もが名前を知っていると言っても過言ではないスクリプト言語Pythonに、いったいどのような脆弱性があったのでしょうか。一緒に見ていきましょう！

今回の脆弱性：CVE-2020-8492

CVE-2020-8492はPythonで発見・修正されたReDoSと呼ばれる、DoS（Denial of Service）の脆弱性の一種にあたります。DoSの脆弱性とは、システムを逼迫《ひっぱく》させて正常な稼働を妨げるなど、サービス運用の妨害を引き起こすことが可能な脆弱性のことを指します。そしてReDoSとは、Regular expression Denial of Serviceの略であり、簡単に言えば正規表現の処理に起因するDoSの脆弱性にあたります。

正規表現をおさらい

正規表現とは、端的に言えば「さまざまな文字列を1つの文字列で表現する表記手法」のことで、一般的には文字列の検索や抽出の際に利用されます。たとえば仕事で、「⁠とある文章の中から電話番号を抽出するプログラム」を書くとします。事前に存在するすべての電話番号を用意し、それが文章中に存在するか否かを総当たりでチェックすることも、もちろん可能ですが、電話番号は何億通りもあるため、処理に時間がかかってしまいます。このような場合、「⁠電話番号」という文字列の特徴を表す図1のような正規表現文字列を用意することで、手軽にチェックを行えます。「⁠これが電話番号を表しているだって？」と思った方もいると思います。前提として、正規表現はさまざまな文字列を表現するための表記手法であるため、記号などで構成された構文が存在します。そして、図1の電話番号を表す正規表現は、表1に記載の構文を用いて表されています。

ちなみに、実は正規表現の構文にはさまざまな種類が存在します。ですが、本記事ではPythonの脆弱性を対象にしているため、Pythonで利用される正規表現の構文を用いて説明を進めていきます。

前置きが長くなりましたが、図1の正規表現について説明します。最初の[0-9]は、0から9の数字のうちの1文字を表しており、その直後に続く{2,3}は、それが2回または3回繰り返して出現する文字列のことを表現しています。

これは、電話番号の先頭番号を表す正規表現にあたり、携帯電話（080や090）や市外局番2桁の固定電話（03）を含めたい意図から、このように表記しています。そしてハイフンがついたあと、[0-9]{4}-[0-9]{4}となっており、これは電話番号の「中4桁-下4桁」を表した正規表現になります。

正規表現を利用した文字列マッチングプログラム

正規表現に対する理解を深めるため、今度は実際のプログラム例（リスト1）を見ていきます。これは、先ほど紹介した図1の正規表現を使い、技術評論社の会社案内文から電話番号のみを抜き出すプログラムになります。簡単にこのPythonプログラムの解説をします。

# -*- coding: utf-8 -*-

# reモジュールのインポート
import re

"""
1.電話番号検索するような正規表現パターンを設定し、
正規表現オブジェクトを生成
"""

# 正規表現オブジェクト名 = re.compile(正規表現パターン文字列)
rx = re.compile("[0-9]{2,3}-[0-9]{4}-[0-9]{4}")

"""
2.検索対象文字列の中から最初に正規表現にマッチする文字列を探し、
マッチオブジェクトを返す。今回は技術評論社の会社案内を検索対象文字列とする
"""

# 今回の検索対象文字列
gihyo = '''
  会社情報
  名称  株式会社技術評論社
  代表取締役    片岡 巖
  本社ビル 所在地       東京都新宿区市谷左内町21-13
  設立  1969年3月
  資本金        3,000万円
  販売促進部電話       03-3513-6150
'''

# 検索結果 = rx.search(検索対象文字列)
mo = rx.search(gihyo)

"""
3.検索結果を表示。マッチ結果は、03-3513-6150となる
"""
print(mo.group())

最初に、正規表現処理を行うための標準ライブラリであるreモジュールをインポートしています。そのあと、reモジュールで定義されているcompileを使い、図1の正規表現を正規表現オブジェクトに変換しています。

最後に、生成した正規表現オブジェクトを使い、そのメソッド呼び出しで文字列マッチングを行います。具体的にはsearchメソッドを用いて引数に受け取った検索対象文字列の中に、電話番号が出現していないかを検索します。今回の検索対象は技術評論社の会社案内文です。

本プログラムを実行した場合、技術評論社の会社案内から、販売促進部の電話番号である「03-3513-6150」が抽出され、プログラム最終行のprint関数経由で表示されます。

以上が、正規表現を用いた文字列マッチングの簡単なプログラムの例でした。

どこに脆弱性箇所があるのか？

では、正規表現についてのおさらいができたところで、今回の脆弱性箇所を見ていきます。今回の脆弱性はPythonのurllib.requestという、指定したURLにアクセスするためのモジュールの中に存在します。Webサイトにアクセスしたとき、ユーザー名とパスワードを求められる「Basic認証」を体験したことがある読者も多いはずです。このクラスは、簡単に言えばそのようなHTTP認証がかかったWebサイト（URL）にアクセスする際に利用されます。

urllib.requestで問題のある正規表現を行っている部分がリスト2、そしてこの正規表現を利用して、実際に文字列のマッチングを行っている部分がリスト3です。この箇所は、AbstractBasicAuthHandlerクラス内のhttp_error_auth_reqedメソッド内に存在します。このメソッドでは、引数（第4引数）で、リスト4（の★部分）のような情報を受け取ります。この部分はHTTP認証の際に「サーバ側で利用可能な認証方法」を、サーバがクライアントに知らせるためのヘッダとなり、通常のサーバの場合「WWW-Authenticate:」から始まります。

rx = re.compile('(?:.*,)*[ \t]*([^ \t]+)[ \t]+'
                realm=(["\']?)([^"\']*)\\2', re.I)

mo = AbstractBasicAuthHandler.rx.search(authreq)

HTTP/1.1 401 Authorization Required
Date: Wed, 11 May 2005 07:50:26 GMT
Server: Apache/1.3.33 (Unix)
WWW-Authenticate: Basic realm="SECRET AREA" ←★
Connection: close
Transfer-Encoding: chunked
Content-Type: text/html; charset=iso-8859-1

http_error_auth_reqedメソッドでは、この「WWW-Authenticate:」以降の部分の情報を、リスト2の正規表現を用いて、マッチング（パース）しているのです。これがリスト3の部分の具体的な挙動になります。

ここまで聞く限りでは、一見問題のないプログラムのように見えます。ですが、今回の脆弱性の報告者によると、http_error_auth_reqedに対して、リスト5のような引数を渡すプログラムを書いて実行したとき、ReDoSの脆弱性が発現するそうです。

from urllib.request import AbstractBasicAuthHandler

auth_handler = AbstractBasicAuthHandler()

auth_handler.http_error_auth_reqed(
    'www-authenticate',
    'unused',
    'unused',
    {
        'www-authenticate': 'Basic ' + ',' * 64 +
' ' + 'foo' + ' ' + 'realm'
    }
)

実際に、脆弱なバージョンのPythonでこのプログラムを実行すると、なんと1時間経ってもプログラムが終了しません。Python自身が、いわゆるサービス停止状態（DoS）状態に陥ってしまいました。

脆弱性の報告者いわく、簡単に言えば、大量のカンマが含まれる文字列を第4引数（のwww-authenticate以降）に渡したとき、このような事象が発生するそうです。

大量のカンマの部分とはリスト5の','*64のことを指し、ここで64個のカンマからなる文字列を生成しています。

そこで実際に、カンマの数を変えて実行してみた結果が表2になります。ここでは、各実行時間はtimeコマンドで取得しています。表を見ると、カンマ数が10個の場合0.08秒で実行が終わっていますが、カンマの数が30になると、実行を終えるのになんと43分もかかっています。そのため、カンマが64個の場合では、1時間経ってもプログラムが終了しないのもうなずけます。

では、なぜこのようなことが起きてしまうのでしょうか。具体的な脆弱性の解説に移る前に、まずはReDoSのしくみについて説明します。

ReDoSのしくみ

ReDosの脆弱性を理解するためには、そもそも正規表現によるマッチングを行う処理系である、正規表現エンジンのしくみについて知る必要があります。

正規表現エンジンの概要

正規表現エンジンとは、簡単に言えば「ユーザーから受け取った文字列（入力文字列）が、正規表現で表される文字列と合致するか否か」を判定するプログラムです。そしてこのプログラムのキモとなる「正規表現文字列の解釈」と「入力文字列が合致するか否かを判定する部分」は、「⁠有限オートマトン」を利用して実現しています。

具体的には、正規表現の文字列を有限オートマトンに変換後、入力文字列を有限オートマトンの入力として与え、文字列中に正規表現にマッチする部分があるか否かを、有限オートマトンの状態を遷移させることで判定します。

以上の説明だけで「なるほど、わかったぞ！」となる人はごく少数かと思います。そこで、そもそも有限オートマトンとは何かを、噛み砕いて説明します。

有限オートマトン

有限オートマトンとは簡単に言えば、与えられた一連の入力列に対して、その入力に応じて内部の状態を遷移させ、入力終了時の状態に応じて、YesかNoか（受理か拒否か）を出力（判定）する、数学的なモデルのことを指します。この際、内部で定義されている状態数が、その名前のとおり有限個に限られるのが、このオートマトンの特徴の1つです。これだけではイメージが湧きづらいので、具体例を挙げます。

たとえば、2進数の数字の中に、0が偶数個あるかどうかを調べたいとき、有限オートマトンが利用できます。実際に、0が偶数個あるか否かを判定する有限オートマトンを状態遷移図で表したのが、図2です。

簡単に状態遷移図の読み方を説明します。各丸が各状態を表しており、そして丸の中の「q0（偶数⁠）⁠」や「q1（奇数⁠）⁠」が、どの種類の状態にあたるのかを表しています。また、太い矢印が指している丸が、開始時点の状態にあたり、二重丸が「受理」を示す状態にあたります。今回の場合、受理状態は0が偶数個ある状態のことを指します。次に、各丸から伸びる細い矢印の上に書かれている数字が各入力を表し、矢印の指す方向が、その入力に対応する遷移先の状態となります。今回の場合、入力は0か1かになります。

たとえば入力が「1010」の場合、どのような遷移になるか見ていきます。左から右に文字を読み取っていくため、最初の入力文字は1です。この場合、q0からq0に遷移する形となります。その次の入力は0ですので、今度はq0からq1に遷移します。そして次は1ですので、q1からq1に遷移します。最後の入力は0ですので、今度はq1からq0に遷移します。もう与えるべき入力は存在しないので、これが最終的な状態になります。前述したように、二重丸で表されたq0が、今回の受理状態（偶数）になるので、「⁠1010の中には0が偶数個存在する」という判定になります。

まとめると、次のような遷移になります。

以上、有限オートマトンの簡単な説明でした。

正規表現と非決定性有限オートマトン

有限オートマトンにもさまざまな種類があります。前述のような「1つの入力に対して遷移先が1つしかない」有限オートマトンは、「⁠決定性有限オートマトン（DFA⁠）⁠」という種類に分類されます。反対に、「⁠1つの入力に対して遷移先候補が複数存在する」有限オートマトンもあります。このような有限オートマトンのことを「非決定性有限オートマトン（NFA⁠）⁠」と呼びます。

プログラミング言語における正規表現エンジンが、どのような有限オートマトンで表現されるかは実装に左右されます。Pythonでは後者の非決定性有限オートマトンが利用されています。実際に、正規表現を非決定性有限オートマトンの状態遷移図で表した例を見ていきます。

たとえば、ここにa*|abという正規表現があるとします。これは「aが0個以上、またはab」という意味を表しており、これを非決定性有限オートマトンで表現したのが図3になります[1]。

簡単に、この状態遷移図の読み方を説明します。

基本的な表記は図2に対する説明と変わりません。大きな違いとしては、遷移を示す矢印の上に「ε（ギリシャ語でイプシロン⁠）⁠」があることです。これは、入力文字を消費しない「ε遷移」と呼ばれます。

ε遷移は、言い換えれば「空入力による遷移」となります。これだけではイメージが湧きづらいので、具体的な遷移例を紹介します。

たとえば入力文字が空文字であった場合でも、正規表現「aが0個以上」の条件には合致することはわかりますよね。その際の、図3上の遷移は次のようになります。

では次に、入力文字がaaaであった場合についてです。これももちろん「aが0個以上」の条件に合致することはわかりますよね。その際の、最終的な遷移は次のようになります。

しかしここで、「⁠aaaとabの区別はどうやってつけたのか？」という疑問が湧いてくる方もいらっしゃると思います。最初のaだけでは、「⁠abか否かをチェックするルート（0→5…⁠）⁠」か「1つ以上のaが存在し、かつそれ以外の文字がないかをチェックするルート（0→1→2…⁠）⁠」⁠、どちらのルートが正解の遷移先がわからないですよね。このような場合は「遷移先候補が複数存在する状態」と言えます。

バックトラッキングとReDoS

前述のような遷移先が複数存在する場合、非決定性有限オートマトンでは、実は遷移先候補をひとつひとつたどって受理か否かをチェックする「バックトラッキング」と呼ばれる処理を行っています。そして、このバックトラッキングの動作こそが、ReDoSの脆弱性につながる正規表現が悪用されたときに、サービス停止を引き起こしている部分なのです。

例に挙げたようなaaaの場合、遷移先となるルートの候補は2つしか存在しません。しかし、正規表現とそれに対応する入力によっては、遷移先候補が数万個となる場合もあります。そしてこのような場合、遷移先候補をひとつひとつたどって受理か否かをチェックするのには、膨大なリソースがかかってしまいます。この事象のことを、Catastrophic backtracking（壊滅的なバックトラッキング）と呼び、プログラムのサービス停止状態（DoS）を引き起こします。これがReDoSの脆弱性の原理です。

ReDoSの脆弱性は、一見そんなに大した脆弱性には見えないかもしれませんが、それは大間違いです。たとえば2019年には、ReDoSの脆弱性が原因で、Cloudflare社が提供するCDNサービスが約30分ダウンし、その間世界中のWebサイト閲覧に影響が出ました。原因としては、Webアプリケーションファイアウォールに記載されていた、正規表現で定義されていた検知ルールにReDoSの脆弱性があり、それが突かれたことにより世界規模の障害につながってしまったとのことです。

実際の脆弱性箇所について

脆弱性の概要が理解できたところで、実際の脆弱性箇所の解説に移ります。リスト2のソースコードに記載された正規表現部分の内、ユーザーからの入力によっては、壊滅的なバックトラッキングが発生してしまう問題の箇所は(?:.*,)*です。この正規表現の意味を図4を用いながら説明します。最初に補足ですが、(?:)は表1に記載されているとおり、グループ化のみ行うための表現になりますが、正規表現上の動作は()と変わりません。そこで説明簡易化のため、図では?:を省略します。

図4のとおり、この正規表現では最初に(.*,)で、任意の1文字が0回以上に加えてカンマが、グループ化されています。そして、グループ化された正規表現の外にはさらに*があり、「⁠(.*,)の文字列グループを0回以上繰り返す」を意味しています。たとえば、「⁠aaa,bbc,ccc,」などがこの正規表現に一致します。また.*に入る部分はどのような文字でもかまわないので、実は「,,,」でも一致します。

ぱっと見、この正規表現に何か問題があるようには見えません。ですが、この正規表現に対して、リスト5のような、大量のカンマが含まれる文字列を渡した場合、壊滅的なバックトラッキングが発生してしまいます。これは、状態遷移図化された正規表現（図5）を見ると、わかりやすいかと思います。

簡単に要約すると、文字列「,,」が来た際に1→2（.⁠）⁠→3→4（,⁠）⁠→5→1と1→4（,⁠）⁠→5→1→4（,⁠）⁠→5→1と2つ異なるパスがあることが原因です。つまり、カンマの数が増えるごとに、ルート候補が生まれることになります。

このような場合、計算量としてはO(2ⁿ)になります。表2の実行時間でもそれは見て取れます。カンマの数をnと表した場合、2の30乗は、2の25乗の32倍にあたり、処理にかかっている時間は、カンマ30個の場合、カンマ25個の場合に比べ、ほぼ32倍（1m22s→43m55s）になっていることがわかります。

脆弱性の修正方法

では、この脆弱性が実際にどのように修正されたかを見ていきます。この脆弱性に対する修正は、2020年4月に行われました[2]。さまざまな修正が行われているのですが、脆弱性修正の肝となる、正規表現部分を取り上げて解説します（リスト7⁠）⁠。

-    rx = re.compile('(?:.*,)*[ \t]*([^ \t]+)[ \t]+'          ←削除
-                    'realm=(["\']?)([^"\']*)\\2', re.I)      ←削除
+    rx = re.compile('(?:^|,)'   # start of the string or ',' ←追加
+                    '[ \t]*'    # optional whitespaces       ←追加
+                    '([^ \t]+)' # scheme like "Basic"        ←追加
+                    '[ \t]+'    # mandatory whitespaces      ←追加
+                    # realm=xxx                              ←追加
+                    # realm='xxx'                            ←追加
+                    # realm="xxx"                            ←追加
+                    'realm=(["\']?)([^"\']*)\\2',            ←追加
+                    re.I)                                    ←追加

大幅な修正がなされているように見えますが、ほとんどはコメントの追加や、文字列の分割などの表記的な変更にあたります。実際の修正箇所としては、前節において「脆弱な箇所である」と指摘した(?:.*,)*の部分だけです。具体的には、修正前は(?:.*,)*であった箇所が、修正後は(?:^|,)になっています。

修正後の正規表現の意味（意図）は、本筋とは関係ないので説明を省きますが、正規表現がシンプル化されています。言い換えれば、図5にあったような入れ子状態のループをなくしたのです。つまり、破壊的なバックトラッキングが発生しないように修正されている、とも言えます。

最後に、本脆弱性はPythonの次のバージョンに存在します。該当するバージョンを利用している方は、最新版のPythonにアップデートすることをお勧めします。

• Python 2.7～2.7.17
• Python 3.5～3.5.9
• Python 3.6～3.6.10
• Python 3.7～3.7.6
• Python 3.8～3.8.1

ReDoSの脆弱性を作り込まないために

今回のような脆弱性を作り込まないために「自分でReDoSの原理を理解し、脆弱性を作り込まないよう気をつける」というのがもちろん望ましいのですが、実際の開発現場では、さまざまな制約（時間や知識）があるのも承知です。そこで、手軽にできるReDoS対策例を紹介します。

まず、自身が書いた正規表現にReDoSの脆弱性があるか否かを簡易的にチェックするツールとしてsafe-regexがあります。また、ReDoSにつながるようなバックトラッキングをそもそも行わない正規表現ライブラリとして、Googleが開発したRE2があります。

また、プログラミング言語によっては標準で、正規表現を用いた文字列マッチングに対し、タイムアウト機能を提供しているものもあります。

RE2を利用できない場合、そういった機能を利用するもの良いでしょう。

さらに勉強したい人向け

さらに勉強したい方に向け、関連する書籍などを紹介します。まず、有限オートマトンの理論的な部分について勉強したい方には『はじめて学ぶオートマトンと言語理論』[3]がお勧めです。とくに第4章では、本記事で説明したような、正規表現を有限オートマトンに変換する方法について書かれており、筆者も参考にさせていただきました。次に、ReDoSのさらなる詳しい説明や事例について知りたい場合は、OWASP[4]が公式Webサイトで掲載している「Regular expression Denialof Service - ReDoS」というページをまずは読んでみると良いでしょう。

それではみなさん、また次回お会いしましょう！