組込みソフトウェアのテストを目的とした CPUエミュレータ上での異常注入手法 東 誠†　山本 哲男‡　早瀬 康裕† 石尾 隆†　井上 克郎† 「大阪大学」の東です． コードクローンのメトリクス「ち」と 開発者の「そーかん」の「ちょーさ」 について発表します． 別刷り †　大阪大学大学院情報科学研究科 ‡　立命館大学総合理工学院情報理工学部 2009/11/6 SIGSE-166-19

発表内容 背景 提案手法 ケーススタディ 考察 組込みシステムの信頼性 組込みソフトウェアのテストの問題点 本研究の目的 SIGSE-166-19 2009/11/6

組込みシステムの信頼性 組込みシステムは，専用の外部デバイスと組込みソフトウェアから成り立つ 外部デバイス:機器の外部から受け取った入力を変換してソフトウェアに出力する装置 携帯電話の場合，ボタンやタッチパネル，カメラなど 組込みシステムには高い信頼性が求められるものがある ペースメーカーが停止すると人命の危機に陥る 携帯電話内の個人情報が読み取られる SIGSE-166-19 2009/11/6

組込みソフトウェアの故障 信頼性を向上させるには，組込みソフトウェアの故障に対処する必要がある 特定の状況で外部デバイスから特定の入力列を受け取った際に，故障が発生することがある 短期間で通信を繰り返すと，携帯電話端末の動作が不安定になる[1] 携帯電話でメール作成中，「題名」を入力直後に「本文」を入力すると，操作ができなくなる場合がある[2] 以降，組込みソフトウェアの故障を発生させる可能性のある入力を，異常な入力と呼ぶ 着信時に終了キーを連続押下した場合などに， 稀に着信履歴が表示されない，または同じ着信履歴が2回表示される 話のロジックが破綻しつつあるな． 論文:信頼性向上→異常な入力による故障に対処→故障の原因は処理の誤った実装 →処理のテスト必要→テストには～という問題あり 今:信頼性向上→異常な入力に対処→入力への対処方は処理 →処理のテストの必要性→テストに最適な方法 (なるほど，つまり「異常な入力」の定義がおかしいから． それで良かったのかも) とりあえず背景周りは後で置いておいて， 今は先に進みましょう．本来なら手法終わっているはずだし． でも，故障が起こったのは，そもそも処理がいい加減だからであって， [1] FOMA M1000 | お客様サポート | NTTドコモ, http://www.nttdocomo.co.jp/support/trouble/data/smart_phone/m1000/ [2]重要なお知らせ : 「FOMA　D900i」をご愛用のお客様へ | お知らせ | NTTドコモ , http://www.nttdocomo.co.jp/info/notice/page/040817_00.html SIGSE-166-19 2009/11/6

組込みソフトウェアのテストの問題点 異常な入力を用いたテストには手間がかかる テストの度に外部デバイスから受け取る入力値を調整しなければならない ソースコードを書き換えて入力値を自動的に書き換えるには，ビルドし直す必要がある デバッガで入力値を書き換えるには，細かい作業を大量に行う必要がある テストには様々な入力が必要になるため，それらの用意に必要な手間は無視できない ハードウェアで発生しがたい～は SIGSE-166-19 2009/11/6

入力を用いたテストを容易にするツール ソフトウェアに異常な入力を注入する FIG[3]は関数の呼び出しを横取りし，代わりの返り値を返す → 外部デバイスから入力を受け取る関数の呼び出しを横取りすれば，異常な入力の注入が可能 main関数 read関数 外部デバイス main(){ read(); ・ 呼び出す アクセスする read(){ ・ return input; } この図は前におかしいと言われたような？ CPU命令レベルだと、リターンは寧ろ関数側にある。 ソースコードレベルなら、関数呼び出しと返り値格納は一行で書けるか。 レジスタに格納した後、変数に格納する……とは限らない。 いっそポスターみたいにCPUエミュとして描いて、 呼出し命令実装部とレジスタに分けるのもありだけど。 まあ後でいい、まずは大まかな流れを。 FIGの説明が適切でないかも FIGそのものがなっているというより スタブを自動生成するはず 実装でもそうなっていたし，FIGはスタブを用意する装置 (何故？　同じ名前でないとLD_PRLOADが有効に働かないから？ 実装みて確認) 返り値って「返す」？「出力」？ モジュールの出力を変更する どっちが妥当？ ・意味が通じる ・処理のテストとしてらしいもの ・ FIG 代わりの返り値を返す 返り値を返す 入力を渡す [3] P. Broadwell, N. Sastry, and J. Traupman, FiG: A Prototype Tool for Online Verification of Recovery Mechanisms Proc. ACM ICS SHAMAN Workshop, June 2002. SIGSE-166-19 2009/11/6

組込みソフトウェアのテストに FIGを利用する際の問題点 外部デバイスから入力を受け取る際に関数を利用しない組込みソフトウェアがある メモリからの読み込みと同じ方法を利用する 外部デバイス専用のアドレスを指定 組込みソフトウェア 外部デバイス メモリアドレスにアクセスする LDR ADDR ADD MOV ・ FIG 横取りできない 入力を渡す SIGSE-166-19 2009/11/6

本研究の着眼点 組込みシステムには，外部デバイスがメモリアドレスに対応付けられているものがある その組込みソフトウェアが外部デバイスから入力を受け取るには，CPUのロード命令を使用する → ロード命令を横取りすれば，組込みソフトウェアに異常な入力を注入することができる マップとか言って解るか？ 対応付けられている？ SIGSE-166-19 2009/11/6

本研究の目的 目的:外部デバイスから受け取る入力を用いた組込みソフトウェアのテストを容易にする 手段:ロード命令を横取りしてソフトウェアに異常な入力を注入する SIGSE-166-19 2009/11/6

発表内容 背景 提案手法 ケーススタディ 考察 組込みシステムの信頼性 組込みソフトウェアのテストの問題点 本研究の目的 SIGSE-166-19 2009/11/6

提案手法 異常な入力を注入する機構をCPUエミュレータに加え，ロード命令を横取りする 外部デバイスと同時にソフトウェアを開発する際，外部デバイスが未完成の時にもテストをするため CPUに比べ，機構を加えるのが容易 ハードウェアよりもソフトウェアの方が加工が容易 SIGSE-166-19 2009/11/6

異常な入力を注入する手順 ロード命令 CPUエミュレータ 外部デバイス または そのエミュレータ プログラム メモリアドレスにアクセスする LDR ADDR ADD MOV ・ メモリアドレスにアクセスする メモリアドレスにアクセスする アクセスする 異常注入機構 ロード命令のロード元が 外部デバイスか調べる ロード元が外部デバイスなら 受け取った入力値を破棄し， 新しい入力値を設定する 異常な入力を 注入する 入力を渡す 入力を渡す SIGSE-166-19 2009/11/6

注入内容の指定方法 プログラムの実行前に，ユーザは異常注入設定ファイルに指定内容を記述 算出式:新しい入力値を計算するための数式 異常な入力を注入する条件 条件式:利用する算出式を選ぶための数式 異常注入設定ファイル 関数A メモリアドレスa : 0x10000000 条件式A-a-1 : 現在の入力値が 5 算出式A-a-1 : 変数temp 条件式A-a-2 : 変数temp が0以下 算出式A-a-2 : 現在の入力値 + 1 ・ 異常な入力の注入を指定 異常注入機構 指定内容に従って， 異常な入力を注入する SIGSE-166-19 2009/11/6

注入の条件として指定可能な要素 1/2 メモリアドレス 関数名 ロード元が外部デバイスか判断するために必要 この要素は条件に必須で，他の要素はオプション 関数名 指定された関数が実行されている間のみ，異常な入力を注入することが可能 全ての状況で異常な入力を注入すると，ソフトウェアの動作が遅くなるから 異常な入力によって故障が発生するのは，特定の機能を実行している時に限定されるから SIGSE-166-19 2009/11/6

注入の条件として指定可能な要素 2/2 条件式のオペランドに利用可能な値 定数 プログラム中の変数 現在の入力値 プログラムの状況を考慮 特定の入力値を異常な入力値に変更 プログラム 異常注入設定ファイル 状況を考慮 switch(temp){ case 10: ・ case 20: 条件式A-a-1 : 変数temp が 20 算出式A-a-1 : 現在の入力値 + 1 条件式A-a-2 : 現在の入力値が1 算出式A-a-2 : -999 ・ SIGSE-166-19 2009/11/6

算出式のオペランドに利用できる値 定数 プログラム中の変数 現在の入力値 これを用いた演算結果を新しい入力値とすれば，入力値が部分的に変更された状況を模倣できる 例:センサの検出結果がノイズの影響を受けた場合 異常注入設定ファイル 条件式A-a-1 : 現在の入力値が0x00000001 算出式A-a-1 : 入力値の3ビット目を1に ・ SIGSE-166-19 2009/11/6

発表内容 背景 提案手法 ケーススタディ 考察 組込みシステムの信頼性 組込みソフトウェアのテストの問題点 本研究の目的 SIGSE-166-19 2009/11/6

ケーススタディ 提案手法をCPUエミュレータに実装し，ソフトウェアに異常な入力を注入 CPUエミュレータはskyeye C言語で実装されているため，ロード用関数が異常注入用関数を呼び出すように改変した 提案手法を用いれば，組込みソフトウェアのテストが容易に行えるようになることを確認 実行が困難な処理を異常な入力の注入で実行 FIGとは異なる方法で異常な入力を注入できる でもここでFIGを出すのは拙くないか？ 結局，直接課題は解決できていないんだから． ただ，テスト手法で差別化することは… 関数の仕様か，外部デバイスの仕様か． 別に外部デバイスの仕様見ながらFIG使えばいいんじゃね？ SIGSE-166-19 2009/11/6

実験対象 Rockboxというデジタルオーディオプレイヤーのファームウェアに含まれるSERIAL0関数 シリアルポートから受信するデータの転送率を取得し，それに応じた処理を行う → 殆ど取得される機会がない転送率への処理を実行させるのは困難 とりあえずは今ので作れ Rockboxは話に関係ある範囲で (考察でファームウェア色々という話ができれば 組込みソフトウェア) 書くべき情報は SERIAL0関数の動作，呼び出す関数＞どこをどう実験するのか SERIAL0関数の全般的性質＞まずRockboxが何かを説明しないと？ (別にネットワーク通信ならそれでいいような) SERIAL0 SIGSE-166-19 2009/11/6

実験内容 現在の転送率を取得する際に，SERIAL0関数の処理に必要な転送率を注入 1つの処理につき，1組の条件式と算出式を記述 通常の転送率と，殆ど取得される機会がない転送率の両方を注入するように指定 異常注入設定ファイル SERIAL0関数 条件式A-a-1 : 現在の転送率が0x0D 算出式A-a-1 : 0xFE 条件式A-a-1 : 現在の転送率が0x4E 算出式A-a-1 : 0x00 ・ switch(temp){ case 0xFE: ・ default: 通常の 転送率への処理 殆ど取得される 機会がない 転送率への処理 SIGSE-166-19 2009/11/6

実験結果 SERIAL0関数内の全処理が実行できた 提案手法でテストが容易に行えることを確認 計31行の指定内容を記述し， 13の処理を実行 異常注入設定ファイルの内容を変更しつつ，計5回プログラムを起動 提案手法でテストが容易に行えることを確認 異常注入設定ファイルを2行書き換えるだけで，実行する処理を追加または変更できた 取得される頻度に関わらず様々な転送率を注入し，それに応じた処理が実行できた SIGSE-166-19 2009/11/6

発表内容 背景 提案手法 ケーススタディ 考察 組込みシステムの信頼性 組込みソフトウェアのテストの問題点 本研究の目的 SIGSE-166-19 2009/11/6

注入内容を決める指針 異常な入力を注入する目的は組込みソフトウェアの故障を発見するため → 故障が発生する状況を漏れなくテストできるように注入内容を指定すべき できる限り多くの処理を実行するように注入 故障を発生させる可能性の高い入力を注入 SIGSE-166-19 2009/11/6

指定すべき注入内容の特定方法 他のテスト手法で作成した入力値に加減算 プログラム中の条件分岐全てを網羅するように，注入する入力値を指定 ソースコードの静的解析によって自動化可能 過去の故障から，異常な入力の傾向を調査 発生時に実行していた機能 ソフトウェアが入力を受け取った外部デバイス 異常な入力の値 SIGSE-166-19 2009/11/6

故障発見に対する有用性 短期間で通信を繰り返す時に発生する故障[1]は，連続で入力を注入すれば発見可能 割り込みを連続で発生させる機能によって実現 既に実装している 「題名」から「本文」の入力で発生する故障[2]は，特定の順で入力を注入すれば発見可能 注入する値を格納するキューによって実現 まだ実装していない [1] FOMA M1000 | お客様サポート | NTTドコモ, http://www.nttdocomo.co.jp/support/trouble/data/smart_phone/m1000/ [2]重要なお知らせ : 「FOMA　D900i」をご愛用のお客様へ | お知らせ | NTTドコモ , http://www.nttdocomo.co.jp/info/notice/page/040817_00.html SIGSE-166-19 2009/11/6

まとめ テストに手間がかかる組込みソフトウェアを容易にテストする手法を提案 今後の課題 CPUエミュレータのロード命令を横取り → 異常な入力をソフトウェアに注入 今後の課題 提案手法によるソフトウェアの故障の発見 指定すべき注入内容を特定する方法の適用 注入する値を格納するキューの追加 SIGSE-166-19 2009/11/6

3班が行った課題整理と分析の結果ついて 東が発表します． 2009/11/6 SIGSE-166-19

以降，質疑応答用 SIGSE-166-19 2009/11/6

SIGSE-166-19 2009/11/6

割り込み機能の実装 割り込みを行う条件として指定可能な要素 時間の指定単位および測定方法を，より実際の組込みシステムに近づける必要がある ソースコード中の行番号 前に実行した割り込みからの経過時間 時間の指定単位および測定方法を，より実際の組込みシステムに近づける必要がある 実行した命令数で指定および測定 命令毎に実行に必要な時間を定めて測定 外部デバイスから入力を受け取るのに必要なウェイトを考慮 SIGSE-166-19 2009/11/6

FIGの関数呼び出し横取り方法 Linux の環境変数 LD_PRELOAD を利用 FIGが横取りを行う手順 ソフトウェアの実行前にユーザが異常な入力を注入する内容をファイルに記述 ファイルから横取りしたい関数の代わりになる関数を自動的に生成し，LD_PRELOADに指定 注入する値を代わりの関数の返り値に設定 SIGSE-166-19 2009/11/6

提案手法の実装 skyeye に，以下の機能を追加 関数名に対応するメモリアドレスの範囲を取得 ロード命令を横取りして，新しいロード値を設定 求めた範囲をプログラムカウンタの値と比較することにより，指定された関数が実行中か判断できる ロード命令を横取りして，新しいロード値を設定 異常注入設定ファイルの算出式，条件式を構文解析して数式として利用 グローバル変数に対応するメモリアドレスを取得 数式の利用時に，グローバル変数の値を取得できる SIGSE-166-19 2009/11/6

提案手法とFIGの差別化 1/2 Rockboxには外部デバイスから入力を受け取る関数があるため，FIGも利用可能 様々な機種を想定しているため，様々な外部デバイスに対応する必要がある Rockbox以外の組込みソフトウェアでも，FIGが利用できるものは考えられる OSが提供する関数を用いて外部デバイスから入力を受け取っているソフトウェア 比較ではないような．お互いの長所とかいう話でもないし． 寧ろ，FIGにできないことで提案手法にできることは何か？ 故障発見に対する有用性 言いたいことは寧ろ機能がどうとか SIGSE-166-19 2009/11/6

提案手法とFIGの差別化 2/2 しかし，FIGが利用できなくても，提案手法なら注入が可能なソフトウェアは存在する 例:ペースメーカーの組込みソフトウェア 専用の外部デバイスにのみ対応している 機能が限定されているため，OSを利用する可能性が低い SIGSE-166-19 2009/11/6

例外処理の検知機能をテストする必要性 異常な入力が例外処理の検知機能で検知できないことがある 検知機能の条件が適切かをテストする必要がある 検知機能の条件で網羅していない異常な入力が存在する 検知機能の条件が適切かをテストする必要がある 「検知機能の条件」 検知条件で定義されている条件…口頭ではこういうように 原因は示さないと 「ランダムな確率で検知できないんだったら入力が原因じゃない」 「誤りがあっても直せないんならテストする必要はない」 となる 単に記述ミスってだけでいいような 信頼性の話 1枚使う話でもないか？ しかし次が長いし SIGSE-166-19 2009/11/6

例外処理の対処機能をテストする必要性 組込みシステムや外部デバイスの種類によって，適切な例外処理が必要になる 携帯電話のボタンなら，入力がない時と同じ処理 携帯電話のネットワークなら，通信履歴の整合性チェック ペースメーカなら，機能を制限して動作を継続 各入力に対して実行される対処内容が適切かをテストする必要がある 外部デバイスの出力内容に応じて， 適切な例外処理が必要になる／例外処理の内容を変更する必要がある (なんで？　なんのために？) 入力を受け取らない場合の処理に切り替える 実行履歴に記録する ペースメーカな一部の機能を停止して動作を継続 データベースの整合性を確認してから強制終了 SIGSE-166-19 2009/11/6

SIGSE-166-19 2009/11/6