確率的並行ファジング
本稿は、自作OS AdC 2019の12/21兼IQ1 AdC 12/24の記事です（ポストが遅れてしまい申し訳ございません）。
並行プログラムの実装で問題になる並行バグを対象とする自動検知の手法として、並行ファジングと呼ばれる手法があります[1,2,3,4,5]。本稿では、そのうちのPCT（Probabilistic Concurrency Testing）と呼ばれる、確率保証付きで並行バグを検知するファジング[2]を紹介します。
並行バグ
並行バグ（concurrency bug）とは、 並行プログラムにおいて特定のスレッドスケジュールでのみ発現するバグです。典型的な並行バグとして図1の3種類の並行バグがあります（論文[2]のFigure 1を引用）。図1(a)は順序違反（order violation）と呼ばれる並行バグで、Thread 1が変数tを初期化する前にThread 2がtの値を読むというスレッドスケジュールで発現します。図1(b)は原子性違反（atomicity violation）と呼ばれる並行バグで、Thread 2がif文の条件判定でxの値がnullでないと判定した直後にThread 1がxにnullを代入し、その後Thread 2がx->print()を実行するというスケジュールで発現します。図1(c)はデッドロック（deadlock）と呼ばれる並行バグで、Thread 1がThread 2より先にロックaを獲得し、かつ、Thread 2がThread 1より先にロックbを獲得するというスケジュールで発現します。
並行バグは一般に再現性が低く、発見と修正が困難な厄介なバグとして知られています。並行バグを含む並行プログラムに対し同じ入力を与えて複数回実行した場合、スレッドスケジュールは一般に実行のたびに変化します。その結果、プログラムのテスト時に観測される多くのスケジュールで並行バグが発現せず、ディプロイ後に稀に生じる特定のスケジュールでのみ並行バグが発現する、ということが起きます。
現実の多くの並行プログラムに対し、上記の3種を含む様々な並行バグが報告されており、ソフトウェアのテストとデバッグの研究分野では並行バグの調査と分類が行われています[0]。
並行ファジング
並行ファジング（concurrency fuzzing）は、並行バグの検知を目的とするスレッドスケジューリングです。通常のスレッドスケジューリングの目的が何らかの指標での並行処理の効率化であるのに対し、並行ファジングのスケジューリングは効率ではなく並行処理のバグの検出を目的とします。言い換えると、並行ファジングは並行バグを発現させるスレッドスケジュールを意図的に合成する手法です。並行ファジングの前提として、検査対象の並行プログラムの実行に必要な入力は予め用意されているものとします。
例えば、図1の各種の並行バグを考えます。これらの並行バグを検知するために、並行ファジングは数多のスレッドスケジュールの中から、図中の黒矢印の順序でThread 1とThread 2の各式/文を実行するスケジュールを見つけ出そうとします。通常のスレッドスケジューリングでは図中の矢印の順序が稀にしか実行されない場合に対して、並行ファジングは意図的にこれらのスレッド実行順序を引き起こそうとします。
並行ファジングにも様々な方式があります。以下に代表的な方式を挙げます。
1．ヒューリスティクスに基づくスケジューリング
この方式はまず、対象プログラムの実行時監視（動的解析）によって、（正常な）実行トレースから並行バグに関係しそうな挙動を捉えます。例えば、複数スレッドによる共有変数アクセスやロック獲得は並行バグの要因となり得る挙動です。次に、捉えた疑わしき挙動に焦点を当て、独自のスケジューラによって、並行バグが発現するよう各スレッドの共有変数アクセス順序やロック獲得順序を意図的に調整します。その結果、意図した通りにスレッドスケジュールを合成・実行できた場合、それを並行バグとして報告します。
2．システマティックなスケジューリング
この方式は、可能な限り多くの異なるスレッドスケジュールを限られた予算内で、あるいは、特定の上限（例えばスレッド切り替えの回数）に達するまで、網羅的に列挙して実行しようとする方式です。実際に網羅実行されたスケジュール中に各種の並行バグの条件を満たすものがあれば、それらを並行バグとして報告します。
3．ランダムなスケジューリング
この方式は、OSやランタイムによる各スレッドの実行スケジューリングに対し、ランダムに遅延を加えたり、スレッド切り替えやスレッド優先度変更をランダムに引き起こすことで、通常のスレッドスケジュールとは異なるランダム性の増したスケジュールを合成します。それによって、膨大なスケジュール空間に潜む並行バグをランダムにあぶり出します。
確率的並行ファジング
前述のランダムスケジューリングに属する手法として、確率保証付きで並行バグを検知するファジング手法があります[2]。この手法はPCT（Probabilistic Concurrency Testing）と呼ばれるもので、スレッド数がnで全スレッドの総実行命令数がkである並行プログラムに対し、1回の実行につき深さdの並行バグを少なくとも1/(nk^(d-1))の確率で検知します。ここで、並行バグの深さdとは、あるスレッドの実行命令aの後に別のスレッドの実行命令bが実行されるというスレッド間の命令実行順序に関する制約a→bの個数を意味します。例えば、図1(a)の順序違反の深さは1、図1(b)の原子性違反の深さは2、図1(c)のデッドロックの深さは2です。図中で各黒矢印はスレッド間の命令実行順序の制約に対応し、各並行バグの深さdは黒矢印の本数に対応します。
1．PCTアルゴリズムの概要
深さdの並行バグdを検知するために、PCTはまず、検査対象である並行プログラムのn個のスレッドの各々に対し、優先度d, d+1, ..., d+n-1から値を1つ選んで割り当てます（値の大きい優先度を持つスレッドの実行が優先）。次に、PCTはn個のスレッドによる長さkの実行命令列上にd-1箇所の優先度変更点を設置します。これらの優先度変更点には低い優先度を割り当てます。具体的には、i番目の優先度変更点に優先度d-iを割り当てます。このように各スレッドと各優先度変更点に対応する命令のそれぞれに優先度を設定した上で、PCTは優先度の高いスレッドから順に実行して行きます。実行中に特定のスレッドがi番目の優先度変更点を通過した際に、PCTはそのスレッドの優先度をd-iに下げます。ここで、PCTは優先度の高いスレッドを、ロック獲得待ちになるなどしてブロック状態に入るまで実行し続けます。その間、優先度の低いスレッドは実行されません。
2．PCTアルゴリズムの直観
図1の各種並行バグに対し、PCTが有効に機能する例を図2に示します（論文[2]のFigure 6を引用）。 図2では、Thread 1とThread 2に対してPCTが最初に割り当てる優先度を白丸の数値で表現しています。例えば、図2(b)では、PCTはThread 1に優先度2を、Thread 2に優先度3を割り当てています。また、図中の黒丸の位置および数値は、PCTが検査対象の並行プログラムの命令列上に設置した優先度変更点の位置および優先度を表現しています。例えば、図2(b)では、PCTはif文の条件判定式に対応する最後の命令に優先度変更点を設置し、変更点を通過したスレッドに割り当てる優先度を1に設定しています。このように各スレッドと各優先度変更点の優先度を設定したうえで、PCTは優先度の高いスレッドから順に実行を進めます。例えば、図2(b)では、PCTは初めに優先度3のThread 2から実行を開始し、if文の条件判定式に対応する最後の命令まで実行したところ（優先度変更点）でThread 2の優先度を1に下げます。この時点でThread 1の優先度2がThread 2の優先度1より高くなるため、PCTは次にThread 1の実行を開始します（x = nullが実行される）。最後に、Thread 1の実行が終了またはブロックした後でPCTはThread 2の実行を再開します（x->print()が実行されSegmentation Faultが起きる）。このようにして、PCTは図2(b)の原子性違反を検知します。図2(a)の順序違反の検知と図2(c)のデッドロックの検知も同様に機能します。
PCTが各実行につき1/(nk^(d-1))の確率で並行バグを検知できる理由を図2(b)の原子性違反（d=2）の検知の例に基づき説明します。まず、PCTがこの原子性違反を検知するには、d-1個（=1個）の優先度変更点をif文の条件判定式の最終命令上に設置する必要がありますが、命令列の長さがkであるため、この設置の確率は1/kです。更に、初期状態としてPCTはThread 2に対しThread 1よりも高い優先度を割り当てる必要がありますが、これはThread 1にn個のスレッドの中で最も低い優先度を割り当てることで実現でき、その確率は1/nです。結果として、PCTがこの原子性違反を検知できる確率は1/nkです。上記の議論における確率は、最悪のケースでの下限の確率を想定しています。しかし、現実には優先度変更点の設置個所は1命令に限定されず、ある範囲内の命令であれば良いケースもあります。例えば、図2(c)のデッドロックを検知するには、PCTはThread 1のlock(a)とlock(b)の間にあるいずれかの命令に優先度変更点を設置すれば十分です。このような理由から、現実にはPCTは対象の並行プログラムの各実行につき1/(nk^(d-1))より良い確率で並行バグの検知が可能であることが実験的に示されています[2]。PCTによる並行バグの検知確率保証に関する証明および現実の並行プログラムを対象とする並行バグ検知実験の詳細については論文[2]を参照してください。
並行ファジングの最近の研究動向
本稿で紹介した並行ファジングはPCTですが、この手法は2010年に発表されたもので、その後も並行ファジングの研究は進んでいます。例えば、2012年に発表されたヒューリスティクスベースの並行ファジング手法であるMaple[3]はPCTよりも並行バグの検知性能が高いという実験結果が得られています。また、PCTのアイデアを分散システムのバグ検知に拡張したPCTCP[4]という手法も2018年に発表されています。更に、2019年には洗練されたヒューリスティクスと遅延挿入等により並行バグをより効率的に発見するTSVD[5]と呼ばれる手法も提案されています。PCTCPとTSVDはそれぞれOOPSLAとSOSPというプログラミング言語とシステムソフトウェアの著名会議のBest Paperにも選出されており当該分野での注目を集めています。
参考文献
[0] Learning from Mistakes — A Comprehensive Study on Real World Concurrency Bug Characteristics [ASPLOS'08]
[1] Finding and Reproducing Heisenbugs in Concurrent Programs [OSDI'08]
[2] A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs [ASPLOS'10]
[3] Maple: A Coverage-Driven Testing Tool for Multithreaded Programs [OOPSLA'12]
[4] Randomized Testing of Distributed Systems with Probabilistic Guarantees [OOPSLA'18]
[5] Efficient Scalable Thread-Safety-Violation Detection [SOSP'19]
