競合状態

競合状態は、システムや処理過程の問題であり、処理過程の出力結果がイベントなどの順序やタイミングと予期しない依存関係にある場合をいう。本来の意味は、2つの電気信号が競合していずれかが出力に影響を与える状態である。

競合状態は設計の不十分な電子工学システム、特に論理回路で発生するが、コンピュータソフトウェアでもよく発生する。

この問題の最も厄介なところは、タイミングによっては正常に動作してしまう場合もある、ということである。結果として、判明しにくい不具合を引き起こす。

1. 電子工学
-------

競合状態の典型例は論理回路システムで入力が変化するときに発生するものである。ある出力が入力の状態に依存する場合、それは定常状態の信号に関して定義されるだけかもしれない。入力の状態が変化するとき、電子システムの物理特性によって出力が変化するまである程度の遅延が生じる。その間、出力は定義された状態以外の不安定な状態となる可能性がある。このような一時的な障害を許すシステムもあるが、例えばその出力信号が他のメモリなどを含むシステムのクロックとして使用される場合、システムは設計されたものとは異なった振る舞いをするかもしれない。

例えば、2入力ANDゲートで論理信号 X とその否定 NOT X を入力にしている場合を考えてみる。理論上、その出力はONになることはない。しかし、信号 X がそのまま入力される側と NOT ゲートを通して入力される側で遅延時間に差があった場合、短い時間ではあるが、一時的にANDゲートの出力がONになることがある。

適切な設計技法により設計者は競合状態を認識して事前にそれを排除することができる。他にも準安定状態  が発生することもある。

2. 情報処理
-------

情報処理における競合状態は「イベントタイミングへの予期せぬ依存が引き起こす異常な振る舞い」である。特に複数のプロセスやスレッドが通信しながら動作する場合に発生するが、単一スレッドで動作している場合であっても、シグナルによる割り込みが原因で発生することもある。

以下は「read-modify-write」で発生する競合状態の例である。

2つのスレッド T1 と T2 がそれぞれグローバルな整数を 1 ずつインクリメントしていくとする。理想的には以下のような順序で処理したい。

整数 i = 0;
T1 が i の値を読み、レジスタに格納する : 0
T1 が i の値をインクリメントする :  + 1 = 1
T2 が i の値を読み、レジスタに格納する : 1
T2 が i の値をインクリメントする :  + 1 = 2この例では、i の最終的な値として 2 を期待している。しかし、二つのスレッドは並行に動作し、ロックや同期などの機構を使用しないため、処理結果は間違ったものとなる可能性がある。以下にそのような場合のシナリオを示す。

整数 i = 0;
T1 が i の値を読み、レジスタに格納する : 0
T2 が i の値を読み、レジスタに格納する : 0
T1 が i の値をインクリメントする :  + 1 = 1
T2 が i の値をインクリメントする :  + 1 = 1i の最終値は期待されている 2 ではなく 1 となる。

以下は「check-then-act」で発生する競合状態の例である。二つのタスクを示す擬似コードである。

global integer A = 0;

// A の値をインクリメントして "RX" を表示する // 端末からの割り込みが発生するたびに起動されるものとする task Received { A = A + 1; print "RX"; }

// A が偶数のときだけそれを表示する // 1秒間隔で起動されるものとする task Timeout { if  { print A; } }

出力結果は以下のようになるだろう: 0 0 0 RX RX 2 RX RX 4 4

ここで、以下のような順序でイベントが発生する場合を考える:

タイムアウトによってタスク Timeout が起動される。
タスク Timeout が A を調べ、偶数だったので、次の "print A" を実行しようとする。
端末から割り込みが発生し、タスク Received に切り換えられる。
タスク Received が最後まで動作し、A をインクリメントして "RX" を表示する。
制御がタスク Timeout に戻される。
そのタスクは A を表示するが、そのときに A の現在値を使用するため、5 が表示されてしまう。ミューテックスは、並行プログラミングにおけるこのような問題に対処するために使われる。

2.1. 競合状態の実例
------------

2.1.1. ファイルシステム
---------------

ファイルシステムにおけるファイルロックは一般的解決法を提供する。もっと面倒だが根本的な解決策としては、あるファイルについてひとつのプロセスが排他的なアクセス権を持ち、他のプロセスがそのファイルにアクセスしたいときはプロセス間通信でそのプロセスに依頼するという方式が考えられる。

2.1.2. ネットワーク
-------------

ネットワークでは、IRCのような分散チャットネットワークがあり、ユーザーは新たなチャンネルを開始させるとそのオペレータ特権を得る。異なるサーバを使用中の2人のユーザーが同じ名前のチャンネルを同時に作成しようとする場合、それぞれのサーバは対応するユーザーそれぞれにオペレータ特権を与えてしまう。これは別のサーバからの信号が届く前に特権を与えてしまうことから発生した。なお、現在では多くのIRCサーバの実装でこの問題が解決されている。

この場合の競合状態では、リソース共有のコンセプトでネットワークの状態を隠して、各サーバが自由に状態を変更した後でネットワーク上のサーバにその変化を通知している。しかし、ネットワークによる遅延があるためにこのような競合状態が発生するのである。この競合状態を解決するには、何らかの中心となるシステムを用意してチャンネルの生成と特権の付与を集中管理する必要がある。ユーザーがそのような解決策を受け入れられない場合、競合状態を検出して後からそれを訂正するなどの処理が必要となる。

2.1.3. 人命に関わるシステム
-----------------

競合状態が致命的な問題を引き起こした事例として、放射線療法機器セラック25の事故がある。この装置の制御をつかさどるリアルタイムOSには、競合状態によって引き起こされるバグが存在していたが、この判明しにくいバグが原因で、操作コマンドを素早く打ち込んだ場合、セラック25ではX線用の金属製ターゲットをきちんと配置しないまま高エネルギーの放射線を照射する設定が可能になっていた。そもそもこの装置は、従来機に搭載されていた電気機械式の安全保護装置を取り除いてソフトウェア制御に置き換えてしまっていた。結果として顕在化したソフトウェアのバグが牙をむき出し、6件の重大な被ばく事故を引き起こし、5人の患者が死亡することになった。

他の例として、オハイオ州の FirstEnergy 社の電力管理システムの事故がある。このシステムは警報装置に競合状態を発生する問題があった。3本のたるんだ送電線が同時に外されたとき、競合状態が発生して監視要員に警報が届かなかった。このソフトウェア上の問題によって2003年北アメリカ大停電が発生した。

2.2. コンピュータセキュリティ
-----------------

述語のチェックと使用にかかわる競合状態というものがある。チェック時点と使用時点で状態を変更できるなら、競合状態が発生する。このような競合状態を発生させるバグがコンピュータセキュリティに関わるコードに存在すると、セキュリティホールになる可能性がある。例えば、ファイルのアクセス権をチェックした後で実際のファイルオープンをする場合、チェックとオープンの間にファイルをすりかえると通常アクセスできないファイルにアクセスできる。

2.3. 非同期有限状態機械
--------------

常に1ビットだけ入力が変化すると仮定している非同期有限状態機械は、同時に複数の入力ビットが変化すると障害が発生する。これに対する解決策としては、マシンを設計する際に各状態が検知する入力ビットの変化を1ビットに限定することである。

2.3.1. 種別
---------

静的競合状態 : ある信号とその否定信号が入力として与えられるときに発生する可能性がある。動的競合状態 : 一回の遷移が期待されているときに多重遷移が発生する。これはゲート間の相互作用で発生する。2段階より多いゲートを使わないことで防ぐことができる。基本競合状態 : 全体のフィードバック伝播時間より短い間隔で2回入力が変化すると発生する。入力信号に何らかの遅延要素を取り入れることで解決する場合がある。

3. 脚注
-----

4. 関連項目
-------

同期 
並行性制御
排他制御
特異なバグ

5. 外部リンク
--------

IPA セキュア・プログラミング講座
[1] C/C++言語編
[2] セキュアJavaプログラミング
[3] セキュアUnix/Linuxプログラミング

6. 参考文献
-------

bmurphy1976, et al.. . [4] Stack Overflow
David A. Wheeler. . [5]. Secure Programming HOWTO, 7:11.
Article "[6]" by David A. Wheeler