論文紹介：Efficient scalable thread-safety-violation detection: finding thousands of concurrency bugs during testing

元論文: https://dl.acm.org/doi/10.1145/3341301.3359638

並行システムをテストし、スレッド安全性の違反を効率よく見つけるという論文です。
並行システムの検証・テストというトピック自体はかなり有名で様々な方法がすでに提唱はされています。
しかし、この論文のポイントは実際のMicrosoft製品のビルドシステムの過程にこのテストシステムを実際に組込み、いくつものバグをちゃんと発見した、というところです。

論文概要

このブログではおなじみのシステム系論文のトップカンファレンスSOSPで発表されたものです。
SOSPではこのような検証やバグ発見のようなどうやったら安全なシステムを構築できるかのようなセクションがあり、こういうタイプの論文も一定数あります。
筆頭著者のGuanpu Li氏はシカゴ大学所属で、Microsoft Researchとカルフォルニア大学の方々も著者に含まれています。

この論文では、TSVD（Thread-Safety-Violation Detector）という並行システムのバグ発見システムを提案しています。
並行システムはバグ発見や再現が難しいことが知られていて、並行システムの安全性検証・テストは古くからあるテーマです。
しかし、並行システムは状態数が多い・様々な並行化モデルが存在しているなどの理由から、実製品できちんと用いるというのは難しいというのが多くの既存手法の抱える問題でした。
TSVDのすごいところはMicrosoftの実際の製品のビルドシステムに統合し、ちゃんといくつものバグを発見できたところです。

動機・目的

TSVDはテスト実行の際に適当な遅延を埋め込むことでデータ競合を実際に発生させることで、動的にバグを見つけるというのが大まかな仕組みです。
データ競合を検出すると、その命令までのスタックトレースを出力します。
似たような手法は存在しているのですが、TSVDは現実世界のアプリケーションのビルドに組み込んで使えるように様々な工夫をし、パフォーマンスを高めています。
また、実際に競合を発生させることで検出するので、false-positiveは原則起こらないという特徴もあります。

TSVDでは並行システムのバグの内、Thread-safety violationの発見に特化しています。Thread-safety violationとは、要はデータ競合で、並列にアクセスされることが想定されていないデータ構造に同時にアクセスすることで起きる不整合です。
この論文では複数のスレッドから並行に呼び出すことのできるメソッド以外のメソッド呼び出しを指します。
この論文では例としてKey-ValueストアのためのDictionaryクラスへの追加と読み込みを同時に行うことを上げています。
Dictionaryクラスが２分探索木のようなデータ構造で実装されている場合、読み込みをしている途中で追加処理によって現在探索中のノードの枝が変化するなどされれば、本来見つかるはずのノードに辿り着けない、といったことです。
これはデータ競合の全てのケース、というわけではないですが、このように対象を限定することがハイパフォーマンスの理由のひとつになってます。

データ競合の検出手法として広く知られているもののひとつとしてHappen-Before（HB）分析というものがあります。
これは全ての同期命令を集めて、実際にどの命令が並行に実行される可能性があるかというものを分析するものです。
しかし、forkやjoinが頻繁に行われる場合、状態数が爆発し、また先行研究ではjoinするタイミングに制約があるなど、広く用いるには難しいという問題があります。

アルゴリズム

まず、データ競合の起こりうるメソッド呼び出し（TSVD pointsと呼んでいる）を静的解析で列挙し、これを特殊なcall命令に置き換えます。
この命令はスレッドID、オブジェクトID、メソッドIDをもとに、このメソッド呼び出しにディレイを必要に応じて差し込み、データ競合の検出もおこないます（別スレッドから同一オブジェクトに対して同時にメソッド呼び出しが発生し、かつどちらかが書き込み命令だった場合は競合とみなす）。
単なるメソッド呼び出し自体は相当数あり、そこにランダムに遅延を発生させるだけではデータ競合を発見させるのは難しいです。
そこで、TSVDはデータ競合が発生しそうな箇所を絞り込み、効率よく遅延を差し込むような工夫をしています。

まず、データ競合になりうるメッソド呼び出しが近い時間で行われた箇所を危険と判断します。
つまり、異なるスレッドから同じオブジェクトへのアクセスが一定時間内に行われたかを調べ、その2箇所をdangerous pairとして管理します。

また、これらのdangerous pairは並列に実行されないとデータ競合は起きません。そのため、各TSVD pointsについて、これらの実行履歴を一定数持っておき、それらの中に異なるスレッドからの実行が存在する場合、そのTSVD pointは並列に実行されていると判断します。
dangerous pairの内片方が並行実行されている場合、遅延を差し込むようにします。

dangerous pairのすべてがデータ競合を起こす訳ではないので、これを更に絞り込む必要があります。
まず、Happen-before（HB）関係、つまり片方の命令はもう片方の命令より常に先に実行される関係を推論するといことで絞り込みます。
ある同一オブジェクトの実行履歴に注目し、dangerous pair(loc1, loc2)が以下を満たす場合、HB関係にあるとみなしてリストから除外します。

  1. loc1の直前に遅延が差し込まれた
  2. loc2のスレッド上で過去同一オブジェクトへのメソッド実行を行った箇所loc0が存在する
  3. loc0の終了時間はloc1前に差し込まれた遅延の終了時間より前である
  4. 上記の条件を満たす遅延が一定回数以上存在している

また、各pair毎にprobabilityを設定しておき、遅延を挟むごとにprobabilityを下げる、とすることで、同一箇所に過剰に遅延を設定するということを防ぎます。

これらの遅延挿入アルゴリズムはテストを実行しながら同時に実行できる、というのがポイントのひとつです。
これにより、遅延挿入箇所の決定のための独立したテスト実行は不要なので、テスト時間の短縮になります。
もちろん、複数回テストを実行させ、前回のテスト情報を次回に引き継ぐこともできます。

実装については、.NETアプリケーション（C#やF#のプログラム）に限定されますが、理論的には他のタイプのアプリケーションにも使えるとしています。
また、実装はGithub上で公開されています。

GitHub - microsoft/TSVD: TSVD is a tool for quickly finding thread-safety violations (e.g., data races) in .NET applications.
TSVD is a tool for quickly finding thread-safety violations (e.g., data races) in .NET applications. - GitHub - microsoft/TSVD: TSVD is a to…

評価

1,657のMicrosoftで実際に開発しているアプリケーションのビルドプロセスに組込み、1,134箇所のバグを発見できたとしています。
false-positiveは存在しなく、いくつかのバグは実際のプロダクション環境で問題を引き起こしているものであったとしています。

これらのバグの見つかったアプリケーションの内1000のモジュールとスモールベンチマークを用いて、他の手法とのパフォーマンスの比較も行っています。
実行時のオーバーヘッドは平均で33％ほどで、既存手法と比べてもかなり少なく、発見できたバグの数も上でした。

この手法にはいくつかチューニングすべきパラメータが存在します（dangerous pairを決めるための間隔、HB関係を決定させるための回数など）。
これらについても、各パラメータとそれを増減させた際のバグ検出数とそのオーバーヘッドを調べて分析しています。

まとめ・感想

TSVDというMicrosoftの製品から並行実行時のデータ競合を検出した手法の紹介をしました。

実は以前、並行プログラムのバグを検出するというテーマで研究していた時期があって、それだけに興味深い論文でした。
この手の話はどちらかというと綺麗なモデルを組んで論理的に検証する話が多く、それが故に制約も多く、実世界に持ち出すという話はあまり見ることがありませんでした。
論文全体的にあまり難しい論理の話はないのですが、やはり現実のアプリケーションで少ないコストでバグを見つけられた、というのはインパクトが大きかったのだと思います。
Microsoftは少し前に安全性の観点からRustを推すブログを発表していたりと近年、この手の安全性の分野に力を入れているように見えます。

ところで、今回の対象としているようなバグはRustで書いていれば起きなかったのでしょうかね