静的解析による並行性エラーの検出

数十年にわたる微細化技術の進歩により、単一プロセッサーの性能は飛躍的に向上してきました。しかしその時代は終わりを迎えつつあり、今後の性能向上はコア数の増加によってもたらされると考えられています。これにより並行プログラミングの重要性が高まっていますが、データ競合やデッドロックなど、従来とは異なる種類の欠陥が潜んでおり、非常に難解です。特にマルチプロセッサー環境では、単一プロセッサーでは表面化しなかったバグが顕在化することがあります。

本コラムでは、並行性の落とし穴と、静的解析ツールCodeSonar による検出方法を紹介します。

1. はじめに

数十年にわたる微細化技術の進歩により、単一プロセッサーの性能は飛躍的に向上してきました。しかし、その時代もいよいよ終わりを迎えつつあるようです。業界は、今後の単一チップにおける性能向上が、コア数の増加によってもたらされると考え、大きな賭けに出ています。ただし、これはソフトウェアが並列プロセッサーを有効活用できるようにプログラムされて初めて成立するもので、残念ながら並行プログラミングは非常に難しいのです。

シングルスレッドのプログラミングに長けた専門家でさえ、並行プログラムにはまったく異なる種類の欠陥（データ競合、デッドロック、スターベーションなど）が潜んでいることを十分に理解していないことがあります。こうした落とし穴を避けるには、並行性についての深い理解と論理的な思考が求められます。しかしこれは人間にとって容易なことではなく、並行性を扱うことを前提として設計されていない主流のプログラミング言語では、その難しさがさらに増します。その結果、並行性エラーは、非常に経験豊富なプログラマーでさえもつまずくことがよくあります。例えば、iOS 4.0〜4.1に存在していたある競合状態（現在は修正済み）では、条件がそろえば、物理的にアクセス可能なiPhone 3G以降の端末のパスコードロックを回避できてしまうという問題がありました。

並行プログラムとそれに伴う問題は、マルチプロセッサーマシンが登場するよりもずっと前から存在していました。しかし、並行性の欠陥は、マルチプロセッサー（マルチコアを含む）コンピューター上で現れやすくなっています。単一プロセッサーシステムでは、スレッドは比較的長い時間連続して実行されることが多く、実際には同時に実行されることはありません。そのため、発生しうる動作のパターンは大きく制限されます。この結果として、単一プロセッサー上では問題なく動作していた並行プログラムが、マルチプロセッサー上で実行されると潜在していた欠陥が表面化するといったことがよくあります。

このコラムでは、よくある並行性の落とし穴について解説するとともに、静的解析ツールCodeSonarによる静的解析を用いて、プログラムを実行することなくそれらの欠陥を検出する方法を紹介します。CodeSonarには、並行プログラムで発生しうる問題を検出する高度なチェック機能が多数搭載されています。例えば、異なるスレッド間の相互作用を可視化できるユーザーインターフェースと組み合わせた革新的なデータ競合解析が含まれています。また、標準搭載されているチェッカー以外にも、拡張APIが提供されており、ユーザーが独自のバグ検出ルールを追加することも可能です。

警告クラス名の記載について：
・CodeSonarの警告クラス名は斜体で表記されます：（例）Null Pointer Dereference
・デフォルトで無効になっている警告クラス名にはアスタリスクが付けられます：（例）Recursive Macro*

2. スレッド間の複雑な相互作用

複数の処理が同時に実行され得る状況では、基本的にあらゆることが複雑になります。その中でも特に重大な問題のひとつが、複数のスレッドにおける命令の実行順序が交錯（インターリーブ）することがあるという点です。スレッド間で命令がどのように交錯するかのパターンは膨大にあり、命令数が増えるにつれてその数は指数関数的に増大します。この現象は、「組み合わせ爆発（combinatorial explosion）」として知られています。例えば、スレッドAがM個、スレッドBがN個の命令を実行する場合、それらの命令の交錯可能な順序は非常に多く存在します。たとえごく短いスレッドであっても、可能な実行順序の数は増加します（図1参照）。それぞれ12個の命令を持つ2つのスレッドの場合には、可能なインターリーブの数は200万を超えます。

図1. 2つのスレッドがそれぞれ2つずつの命令を持つ場合、可能なインターリーブの数は6通りある。それぞれが命令を3つもつ場合、その数は20に増える。

実のところ、同期処理やスケジューラーによる実行順制約によってインターリーブのパターン数はある程度制限されますが、それでも現実の並行プログラムでは、合法的な実行順序の数が天文学的な規模になるのです。実際のソフトウェアではこれらの例よりも命令の数ははるかに多く、分岐などの複雑さも伴うため、すべてのインターリーブをテストすることは現実的ではありません。さらに悪いことに、インターリーブの決定はシステムスケジューラーに委ねられており、プログラマーやエンドユーザーがそれを直接制御することはほとんどできません。単にすべての実行順序をテストするのが不可能であるだけでなく、特定のインターリーブを意図的に実行させることも非常に困難です。システムスケジューリングは極めて複雑で、事実上ランダムに近い挙動をします。これは特に、開発者の手の届かない環境で動作する実運用ソフトウェアにおいて顕著です。

その結果として、マルチスレッドプログラムにおける非決定性は、従来のソフトウェアテスト手法を著しく効果の低いものにしてしまいます。標準的な手法を用いて網羅的なテストセットを構築するには、非常に大きなコストと工数を要する場合があるものの、理論上、シングルスレッドで構成されたプログラムにおける不具合は、適切に設計されたテストによって確実に検出することが可能です。しかし、マルチスレッドプログラムの場合、非決定的なインターリーブにより、ひとつのテストケースでも実行のたびに異なる振る舞いを示す可能性があります。このため、特定のバグを再現させること自体が困難あるいは不可能です。

この非決定性は、「実使用実績（Proven In Use）」に基づく信頼性評価の妥当性にも悪影響を及ぼします。シングルスレッドプログラムであれば、長期間の安定動作は、環境が多少変わっても将来にわたり安定動作する可能性を強く示唆します。しかし、マルチスレッドプログラムでは、わずかな実行環境の違いによりこれまで一度も現れなかったインターリーブが発生し、まったく異なる動作を引き起こすことがあります。インターリーブの可能性がほぼ無限にあるため、徹底的なストレステストを行っても、並行性バグを確実に露呈させるとは限りません。

このような難しい問題に対して有効な手段を提供するのが、静的解析ツールCodeSonarです。このツールは、インターリーブを網羅的に列挙しなくても、ソフトウェアの欠陥を発見することができます。高度なシンボリック実行技術を用いて、複数の実行経路やインターリーブを同時に分析し、プログラムを実行することなく並行性のバグを検出します。そのため、マルチスレッドソフトウェアの検証において非常に重要な役割を果たします。

インターリーブの影響は、テストや検証の領域だけにとどまりません。スレッドが相互に影響を及ぼすためです。理想的にはこうした相互作用は意図され、正しく設計されているべきですが、現実には競合状態などの問題が発生します。これはシングルスレッド環境では存在し得ない種類の問題です。

ソフトウェア業界では、これらの問題を回避するために多大な努力が注がれてきました。ロック、セマフォ、メッセージパッシングなどは、その代表的な手法です。

しかし、残念ながらこれらの技術自体が新たな問題を引き起こすことがあります。コードの規模や複雑さが増し、人間が理解しにくくなるだけでなく、誤った使い方をすると、プロセス全体、場合によってはプログラム全体が停止してしまうこともあります。また、必要のない場面で使うと無駄な遅延を招き、逆に必要な箇所で使い忘れると十分な保護が得られません。CodeSonarは、こうした問題の発見と解決に大きく貢献します。

現在でも、多くの開発現場ではシングルスレッド的な発想が支配的です。マルチスレッド対応を行っているプロジェクトでさえ、開発者が並行性についてあまり深く考えていないことがあります。中には、マルチスレッドとそれに伴うリスクを理解している開発者もいますが、セマフォやスレッドセーフなライブラリ、volatileキーワードなどを、あたかも並行性バグを防ぐ万能の手段であるかのように扱うことがあります。システム全体を包括的に把握し、並行性に起因する欠陥を確実に見つけ出すことは、熟練した技術者であっても困難なのが実情です。

多くの開発手法は、暗黙のうちにスレッドを個別に扱っており、複数のスレッドが同時に実行されることによって生じる問題を十分に考慮していないのが実情です。例えばユニットテストでは、複数スレッド間の相互作用によって発生するすべてのバグを検出することはできません。同様に、マルチスレッドプログラムをデバッガー上で実行することも、並行性の問題を診断する手法としては効果的ではありません。これは、デバッガー自体が実行環境に影響を与える上に、一度の実行では一通りのインターリーブしか観察できないためです。このような従来の手法は、「古典的な」ソフトウェア欠陥への対処には引き続き有効ですが、システムのマルチスレッド特性を正しく考慮した手法によって補完される必要があります。

開発ツールの中には、シングルスレッドを前提とした設計が根本にあるものも多く存在します。例えば、コンパイラの最適化は「現在のスレッドが変数を変更していないなら、値は変化しない」と仮定して動作することがあります。しかし複数スレッドが同時に動作している場合、この仮定は成り立ちません。
CおよびC++言語の仕様には、2011年の各言語標準の改訂まで、マルチスレッドに関する明確な定義が存在しませんでした。このため、これらの標準に対するコンパイラおよびランタイムの対応はいまだに不完全であり、マルチスレッドプログラムはシングルスレッドプログラムに比べて、処理系依存の挙動に大きく左右される状況にあります。Boehm氏［2］はこの点について、『本質的に、あらゆるアプリケーションは、正しく動作するために処理系依存の挙動に頼らざるを得ない』と述べています。したがって、データ競合やデッドロックといった並行性に関する潜在的な欠陥をすべて排除することは、不適切な処理系依存動作を回避する上で非常に有効な手段であると言えます。

これ以降の章では、マルチスレッドプログラムに特有のソフトウェア欠陥の種類と、CodeSonarを用いてこれらの欠陥を検出し、その発生確率を低減する方法を説明します。

3. データ競合

データ競合とは、複数のスレッドが同時に共有データへアクセスし、そのうち少なくとも1つがそのデータの値を変更しているにもかかわらず、それらのアクセス間に明示的な同期処理が行われていない場合に発生します。スレッドのインターリーブによっては、システムが不整合な状態に陥る可能性があります。データ競合は長期間見つからずに潜伏し、ごくまれな条件下で、しかも診断や再現が非常に困難なかたちで現れるため、特に厄介なバグです。

このため、データ競合は本番環境で広くテストされたソフトウェアでも、一般的なバグの原因のひとつとなっています。最悪の場合、データ競合は深刻な被害を引き起こすことがあります。例えば、2003年に北米で発生した大規模停電では、エネルギー管理システムにおけるデータ競合が、オペレーターに誤った情報を伝達したり、情報伝達が遅延したりする原因となり、被害の拡大に拍車をかけました［4］。Kevin Poulsen氏はTracking the blackout bug［3］という記事の中で、『このバグが発現するタイミングの猶予はミリ秒単位であった』と記しています。テスト中にこのようなバグが顕在化する確率は限りなくゼロに近いと言えるでしょう。

図2は、データ競合の典型的な例を示しています。ある製造ラインには、入口と出口にセンサーが設置されており、ライン上に存在する品目の数（カウント）を常に更新しながら保持しています。入口センサーの制御装置は、品目がラインに入るたびにカウントをインクリメント（加算）し、出口センサーの制御装置は、品目がラインを出るたびにカウントをデクリメント（減算）します。もし、1つの品目がラインに入るタイミングで別の品目がラインを出るとすれば、加算と減算が行われ、実質的にはカウントは変化しない（±0）はずです。

図2. データ競合により、製造ライン上の品目カウントが誤った値となる例

しかし、コンピューターにおける加算・減算処理は単一の操作ではなく、メモリーから値を読み取り、それをローカルに変更し、再びメモリーに書き戻すという一連のステップで構成されています。このため、こうした更新処理が適切な同期処理なしにマルチスレッド環境で実行された場合、データ競合が発生する可能性があります。なぜなら、各制御装置が共有データ（カウント値）を同時に読み書きするからです。図2に示されたような不適切なスレッドのインターリーブにより、最終的なカウントが正しいはずの70ではなく、誤って69となるケースが発生します。同様に、別の順序では71になる場合もあります。もちろん正しく70になるインターリーブも存在します。

このようなデータ競合を排除するのが難しいのには、以下に示すようないくつかの理由があります。

3-1. 発生頻度が極めて低いため、問題の存在に気づきにくい

データ競合は発生頻度が非常に低いため、問題が起きていること自体に気づかないことがあります。実際、問題がテスト中に現れるとは限りません。前述の通り、2つのスレッドが実行される際のインターリーブは膨大な数に上り、しかもその選択はユーザーの制御下にありません。すべてのインターリーブをテストで網羅することは現実的ではなく、仮に注目すべきインターリーブが特定できたとしても、テストでその順序通りに実行させる手段は通常ありません。

3-2.データ競合の診断が難しい

まず、現れる症状がわかりにくいことが挙げられます。図2の例のように、ライン上の品目カウントは、通常では正しい値になりますが、たまに多すぎたり少なすぎたりすることがあります。次に、マルチスレッドプログラミングの落とし穴に慣れていない開発者は、コードの異常な動作に頭を悩ませることになり、データ競合の可能性にたどり着くまでに時間がかかることがあります。また、コード単体で見た場合に、一見するとデータ競合による影響が起こり得ないように見えることがあり、結果的にバグ報告が再現できないとして無視されることもあります。このようなケースにおいて、静的解析ツールCodeSonarは非常に有用です。CodeSonarは、共有メモリー領域へのアクセスパターンを解析することで、データ競合を特定します。つまり、症状ではなく原因に着目するのです。データ競合が検出されると、CodeSonarはData Race（データ競合）警告を出力し、評価やデバッグに役立つ情報も併せて提示します。このため、開発者が表面的な症状から原因を手探りで遡る必要がなくなり、デバッグ負荷を大幅に軽減できます。

CodeSonarには、ファイルシステムにおけるレースコンディション（File System Race Condition）の検出機能も備わっています。これは、従来のデータ競合とは異なる形式の脆弱性であり、あるプログラムが、特定のファイルをチェックする関数を呼び出した後、同じファイルを使用する別の関数を呼び出すというパターンで発生します。ソースコード上は、チェック時と使用時で同じファイルであることが前提とされていますが、実際にはその間に他のプロセスがそのファイルを変更してしまう可能性があります。例えば、攻撃者によって、元のファイルが機密情報を含む別のファイルのリンクに置き換えられるといったケースです。

3-3.データ競合の排除により新たな問題を招く可能性がある

データ競合は、通常は、ロックやその他の同期手法を用いて共有リソースを保護することで回避されます。しかし、これらの手法はパフォーマンスのボトルネックを生じさせ、プログラムがマルチコアの性能を最大限に活用することを妨げる可能性があります。そのため、プログラマーはそれらを使用する際に注意を払わなければなりません。最悪の場合、こうした同期手法はデッドロックやスターベーションといった、別の種類の問題を引き起こす可能性があります。

4.デッドロック

デッドロックとは、複数のスレッドが互いに必要なロックを保持したまま、相手のロックを待ち続けることで進行不能になる状態です。図3は、2つの共有変数を保護するために2つのロックを使用した場合、どのようにデッドロックが発生するかを示しています。この例では、複数の製造ラインが存在し、製造中の品目の総数（count）と、品質検査に不合格となった不良品の数（bad_items）をそれぞれ記録する2つの変数を共有しています。あるスレッドがcountに対するロックを取得し、別のスレッドがbad_itemsに対するロックを取得すると、両スレッドとも次に必要とするもう一方のロックを取得できなくなります。その結果、両スレッドとも操作を完了できず、ロックを解放するポイントに到達することもできません。このようにして、どちらの更新処理も完了せず、両スレッドが完全に停止した状態に陥ります。

図3. 2つのスレッド間のデッドロック：どちらのスレッドも進行できない状態

CodeSonarは、異なるスレッドが同じロックを異なる順序で取得する可能性がある場合に、「Conflicting Lock Order（ロック順序の競合）」警告を出すことでデッドロックのリスクを持つソフトウェアを特定するのに役立ちます。図3の例はまさにこの特性を持っています。このような競合がすべて排除されれば、システムがデッドロック状態に陥ることはありません。

さらに積極的な検出として、「Nested Locks（ネストされたロック）」チェックがあります。これは、1つのスレッドが2つ以上のロックを取得しようとした際に警告を発するものです。各スレッドが常に1つのロックしか保持しないようにすれば、理論上デッドロックは発生しません。しかし、すべてのロックのネストを完全に排除することは、多くの実際のプロジェクトにとって現実的ではありません。そのため、ユーザーの中にはこのチェックを無効にして、「ロック順序の競合」の検出のみを有効にする選択をするケースもあります。

なお、これらいずれかの制約によってデッドロックを回避することは可能ですが、それでもなお、次章で示すプロセススターベーションが発生する可能性は残ります。

5.プロセススターベーション

スレッドが、他のスレッドが保持しているロックの解放を非常に長い時間にわたって待ち続ける状態になることを、スターベーションと呼びます。この問題が発生する典型的なケースは、ロックを保持しているスレッドが、大容量のディスク読み込みやネットワーク経由のデータ到着といった外部イベントを待っている場合です。

例えば、前述の製造ラインの自動化システムにおいて、すべての入出庫記録を監査し、現在のカウントが「累積入庫数 − 累積出庫数」と一致しているかを検証する定期監査スレッドが存在するとします。この監査スレッドは、countやすべてのセンサーに対してロックを取得する必要があります。そのため、監査が完了するまで他のすべての更新処理が待機状態になります。監査の処理時間が長いと、更新処理は著しく遅延します。さらに悪いことに、監査が完了する前に次回の監査スレッドがすべてのロックを再取得して処理を開始してしまう可能性もあります。最悪のケースでは、いくつか、あるいはすべての更新処理が永続的に実行されなくなる恐れもあります。

スターベーション検出における静的解析の有効性：静的解析は、ロックを保持した状態で呼び出されるすべての関数を解析することによって、スターベーションの原因を特定するのに役立ちます。

CodeSonarでは、このようなパターンを対象としたカスタムチェックをユーザー自身で追加することができます。
例えば、f()という関数がブロッキング処理を行ったり、長時間実行されることが知られていたりする場合、ロックを保持しているスレッドがf()を呼び出した際に警告を出すようなカスタムチェックを追加することが可能です。

6.同期手法の正しい使用

同期処理を正しく行うコードを書くことは難しく、コーディング規約によって、使用可能な同期手法やその条件に制限が設けられていることがよくあります。例えば、JPL（ジェット推進研究所）のC言語コーディング標準［1］では、タスク同期の目的でタスクディレイ関数（タスク遅延関数）を使用することが禁止されています。CodeSonarには、このJPLコーディング標準に対応したチェック群が含まれています。その中には「タスクディレイ関数チェック」があり、該当目的で使用されている関数に対して警告を出します。また、設定パラメーターを使って、用途に応じて既知のタスクディレイ関数のリストを拡張することも可能です。より一般的には、ユーザーはBADFUNC_*ファミリーの設定パラメーターを利用して、使用を禁止すべき同期関数を明示的に指定し、それが使われた際に警告を出すように設定することができます。（BADFUNC_*パラメーターは、特にサードパーティ製コードにおいて、スレッドセーフでない可能性のある関数を検出するのにも有効です。例えばCodeSonarに組み込まれているttyname*関数の使用チェックも、この目的に基づいたものです。）

さらに、CodeSonarは、リスクのある同期関数の使用パターンを検出するのにも適しています。以下は、その代表的な検出項目です：

• Unknown Lock（不明なロック）：ロックまたはアンロック操作が、識別できないロック対象に対して行われている。
• Missing Lock / Missing Unlock / Lock–Unlock Mismatch（ロック／アンロックの欠如・不整合）：ある関数内で実行されているunlock（またはlock）操作に対応するlock（またはunlock）操作が、同じ関数内に存在しない状態を指す。これは必ずしも、対応する操作が実行されていないことを意味するわけではないが、lockとunlockの操作を同一関数内にまとめて記述することで、コードの可読性が向上し、保守性の高い実装が可能。
• Double Lock / Double Unlock（二重ロック／二重アンロック）：同一リソースに対して複数回のロック／アンロック操作が行われており、リソースやロック機構に悪影響を及ぼす可能性がある。特定の実装で問題が発生しなかったとしても、想定外の実行パスが存在する可能性を示唆する重要な兆候。
• 絶対に成功しないtry-lock：冗長で、場合によっては誤解を招く可能性があるtry-lock構文。

CodeSonar Extension API を利用することで、ユーザーはリスクのある使用パターンに対して独自のチェックを追加することができます。
これらのチェックは、自社のコーディング規約や特定のプロジェクトで採用されている同期手法に基づいて設計することが可能です。

7.結論

マルチスレッドプログラミングは、従来の開発におけるバグとはまったく異なる新たな種類の不具合の可能性を開発者にもたらします。同時に、スレッドのインターリーブ（実行順序）の非決定性とその膨大な組み合わせ数により、マルチスレッドシステムにおけるバグをテストや従来の手法だけで見つけ出すことは非常に困難になります。

CodeSonarが提供する静的解析は、これら両方の課題に対処する上で開発チームを強力に支援します。CodeSonarは、実行ベースの手法が抱える制約やシングルスレッド前提の単純化された見方にとらわれることなく、並行処理に関連するさまざまな問題の検出とレポート機能を提供します。

CodeSonarの詳細および無料トライアルについては、ユビキタスAI（CodeSecure社正規代理店）までお問い合わせください。

参考文献

1. JPL Institutional Coding Standard for the C Programming Language, 2009, Jet Propulsion Labora- tory, California Institute of Technology JPL DOCID D-60411.
2. Boehm, H.-J., Threads Cannot be Implemented as a Library. In ACM SIGPLAN Conference on Pro- gramming Language Design and Implementation (PLDI). 2005. Chicago, IL: ACM. pp. 261-268.
3. Kevin Poulsen, Tracking the blackout bug. in SecurityFocus. April 7, 2004.
4. U.S.-Canada Power System Outage Task Force, Final Report on the August 14, 2003 Blackout in the United States and Canada: Causes and Recommendations. 2004.

より詳しく技術や関連製品について知りたい方へ

本コラムに関係する技術や関連する製品について知りたい方は、お気軽にご相談ください。

お問い合わせはこちらから