データ競合を検出するための 割込み自動生成 井上研究室　M2　東 誠 「大阪大学」の東です． コードクローンのメトリクス「ち」と 開発者の「そーかん」の「ちょーさ」 について発表します． 別刷り 2010/2/15 修士論文発表会

発表概要 目的:割込みを用いたプログラムのテスト支援 手段:割込みを自動的に生成することで，割込みによる欠陥の一種(データ競合)を検出 結果:割込みの生成タイミングを手動で調整することなしに，OSの障害を再現 修士論文発表会 2010/2/15

割込みを用いたプログラム 発生タイミングが判らないイベントを処理するために，割込みを利用するプログラムがある 割込み:プログラムに現在実行中の処理を中断させ，より優先度の高い処理を実行させる要求 プログラムの動作に関係なく，いつでも発生する 例:デバイスドライバ，タイマー処理 main(void) handler(void) 通常処理 もっと割込みの必然性のある例 ポーリングでもできるならやるなよって話になる ～なプログラムがあります ＞先に具体例(「例えば，携帯電話のソフトウェアでは～」「～など，」) 割込みハンドラ 割込み op = 1 op = 0 割込み return return 修士論文発表会 2010/2/15

割込みを用いたプログラムに 存在する欠陥 割込みハンドラと通常処理の間に存在するデータ競合 データ競合を発見し，除去する必要がある 通常処理が利用しているメモリの値が，意図しないタイミングで，割込みハンドラによって変更されてしまうという欠陥 以降，割込みによるデータ競合を単にデータ競合と呼ぶ データ競合による障害の例 放射線医療機器の事故[1] データ競合を発見し，除去する必要がある [1] N. G. Leveson. An investigation of the therac-25 accidents. IEEE Computer, 26:1841, 1993. 修士論文発表会 2010/2/15

interrupt_handler(void) データ競合の例 x が 0 以外なら除算を実行 x が 0 になるのに 除算を実行 変数 x 通常処理 divide(void) 割込みハンドラ 使用 使用 割込み interrupt_handler(void) 使用 yes 割込み x != 0 x = 0 割込み no ret = 100 / x return 割込み return 割込み4つの話をするタイミングが凄く中途半端． これはテストの難しさを伝えたいためにやってるんだが 最初に普通のプログラム 割込みハンドラはボタンの値をバッファに格納し，通常の関数はバッファのデータを送信しています． 抽象ではなく具体？ 条件分岐の後に割込みが発生すると， 割込みも厳密には嘘なんだけどね 機械語というかアセンブラレベル ポイントは？ ・特定のタイミング(でのみ)割込みが発生する時に発生 ・結果的に，データに対する仮定が崩れる 駆け足か？ 本質は「4つあるのに1つだけ＞効率的な検出手法」 対策を全く書いていないのが問題 (uClinuxで「禁止」と言う?) Uclinuxなら送って減らす つまり逆方向なのか しかし直感的に「なんでそうなってるの？」って判りがたい これだけ見てプログラムとして完結してないと もう1つのは，配列 しかし二度だからなー データ競合をテストによって発見したい 修士論文発表会 2010/2/15

テストでデータ競合を発見する 際の問題 割込みを利用しないプログラムのテスト手順 割込みを利用するプログラムのテストの問題 入力を与える 正しい出力を返すことを確認 割込みを利用するプログラムのテストの問題 通常処理だけではなく，割込みハンドラとの組でテストを行わなければならない 通常処理の中で割込みが発生するタイミングが膨大である 障害を起こしそう 系統的に テストで問題 入力から出力 系統的＋起こしそう しかし組考慮 しかも割込み膨大 これらテストは現実的じゃない なので 障害起こしそうな組を系統的にテストしたい 今回はタイミングだけ，理由は(こちらの方が困難なので) 修士論文発表会 2010/2/15

本研究の着目点 データ競合が存在する条件 通常処理で1つの変数を2回使用 2回使用する変数の値が同じことを通常処理が仮定 1回目は読み込みか書き出し 2回目は読み込み 2回使用する変数の値が同じことを通常処理が仮定 1回目と2回目の間で割込みが発生し，割込みハンドラが変数の値を変更 x = 3 x != 0 割込み x が0以外 であること を仮定 割込み no ret = 100 / x x が3 であること を仮定 修士論文発表会 ret = 100 / x return 2010/2/15

本研究の目的と手段 目的:データ競合が存在しうる箇所で割込みを発生させる 手段:メモリを使用する任意の2つの命令間で割込みを生成する メモリを使用する全ての命令を実行した後に生成 修士論文発表会 2010/2/15

提案手法 機械語命令 CPUエミュレータ テスト対象の プログラム 割込み 割込み生成部 命令実行部 割込み 生成指示 実行した 命令 設定ファイル 実行した命令が 読み込みまたは 書き出し であるか判断 割込み自動生成機構 プログラムの実行前に 割込みの種類を ユーザが記述 指定 修士論文発表会 2010/2/15

実験内容 提案手法をCPUエミュレータskyeyeに実装し，データ競合が存在するプログラムに適用 実験の目的 提案手法でデータ競合が実際に発見できることを確認 データ競合の発見に必要な作業を調査 適用対象は実際に使われているOSの過去のバージョン uClinux TinyOS 修士論文発表会 2010/2/15

uClinux のデータ競合 デバイスドライバでキューのデータ送信時に，範囲外を参照 キューのデータ数を確認後，データを送信 → 確認後に割込みが発生すると，割込みハンドラが送信 通常処理 割込みハンドラ ・ ・ キューのデータ数が1 if (xmit_cnt <= 0 || ……) return; ・ xmit_cnt--; if (xmit_cnt <= 0 || ……) return; ・ xmit_cnt--; 割込み キューの範囲外を参照 キューのデータ数が0 修士論文発表会 2010/2/15

データ競合の発見に必要な作業 テスト対象の通常処理を呼び出す 通常処理を呼び出す前に，キューにデータを5個格納しておく データ数の確認前に割込みが計4回発生 通常処理 ・ Static void rs_flush_chars(struct tty_struct *tty){ struct m68k_serial *info = ……; m68328_uart *uart = ……; ・ if (xmit_cnt <= 0 || ……) return; 割込み 割込み 割込み 割込み 修士論文発表会 2010/2/15

提案手法によるテスト手順 データ競合が存在しうる組を特定 テストする通常処理への様々な入力を用意 提案手法により，割込みを自動的に生成 メモリの値を書き換える割込みハンドラを特定 そのメモリの値を2回使用する通常処理を特定 テストする通常処理への様々な入力を用意 例:使用しているメモリの値が配列の添字なら，値を使用するタイミングで上限や下限に設定 提案手法により，割込みを自動的に生成 適切な値 えーと，何かが ここもきっちり説明しろって言われたら，先に余計な割込みが発生するし， 再帰的な呼び出しへの対策も必要だから， そこへの突っ込みは必要なんだろうな 修士論文発表会 2010/2/15

まとめと今後の課題 データ競合を検出するため，メモリを使用する全ての命令の直後で割込み自動生成 今後の課題 割込みの生成タイミングを手動で調整することなしに，データ競合による障害が再現できた 今後の課題 データ競合が存在しうる箇所の自動特定 データ競合の発見に必要な変数の値の自動特定 データ競合の発見に不必要な割込み生成の除去 修士論文発表会 2010/2/15

2010/2/15 修士論文発表会 「大阪大学」の東です． コードクローンのメトリクス「ち」と 開発者の「そーかん」の「ちょーさ」 について発表します． 別刷り 2010/2/15 修士論文発表会

割込み生成時の無限ループ防止 同じ箇所で何度も割込みが発生し、 無限ループに陥る 現在の プログラム カウンタの値 保存された 割込み生成機構 メモリの利用 現在のプログラムカウンタが 割込み発生直前の値と 同じか判定する 割込み発生 直前の プログラム カウンタ の値 プログラム LDR ADDR ADD MOV ・ Interrupt handler: RET 比較結果 プログラムカウンタが 割込み発生直前のと 同じであれば， 割込みを発生させない 現在の プログラムカウンタ の値 割込み 同じ箇所で何度も割込みが発生し、 無限ループに陥る 割込みハンドラ 修士論文発表会 2010/2/15

割込みハンドラ(ADC.dataReady関数) TinyOSのデータ競合 配列にデータ格納時に，添字が上限を越える 配列の添字を加算後，上限を越えたら初期化 → 加算直後に割込みが発生すると，初期化されていない添字を用いて配列を利用 データ競合の発見に必要な作業 通常処理としてADC.dataReady関数を呼び出す 配列の添字を上限に設定 ここもきっちり説明しろって言われたら，先に余計な割込みが発生するし， 再帰的な呼び出しへの対策も必要だから， そこへの突っ込みは必要なんだろうな 割込みハンドラ(ADC.dataReady関数) pack->data[packetReadingNumber++] = data; ・ . if (packetReadingNumber == BUFFER_SIZE) { packetReadingNumber = 0; 割込み 修士論文発表会 2010/2/15

読み込み命令の読み込み元が指定された箇所か調べる メモリの値をすり替える手順 読み込み命令 CPUエミュレータ メモリ プログラム LDR ADDR ADD MOV ・ メモリアドレスにアクセスする メモリアドレスにアクセスする アクセスする 値すり替え機構 読み込み命令の読み込み元が指定された箇所か調べる 読み込み元が指定箇所なら 受け取った値を破棄し， 新しい値を設定する 新しい値を 注入する 値を渡す 値を渡す 修士論文発表会 2010/2/15

提案手法で検出できない例 1: unsigned int len = 0; 2: void str_cpy(char *buf, char *str); 3: { 4: len = strlen(str); 5: if((0 < len) && (len <= strlen(str))) 6: memcpy(buf,str,len+1); 7: } 8: 9: void interrupt_handler(void){ 10: len++; 11: } 特定の変数に対する処理がデータ競合を起こす可能性に着目した時， そのデータ競合を起こす割込みが発生するタイミングは大幅に絞ることができる． それなら，各割込み発生可能箇所についてOn/OFFを設定し， (割込み発生可能箇所をn個とするなら，2^n通りの組み合わせで割込み発生を試す) 修士論文発表会 2010/2/15

修士論文発表会 2010/2/15