パターンマイニング技術を 用いたC言語プログラムからの コーディングパターン抽出 ○中村勇太1 崔恩瀞1 吉田則裕2 春名修介1 井上克郎1 1大阪大学 2名古屋大学 1 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University コーディングパターン •複数のモジュールに分散する定型的なコード[1] –例:ファイルのオープン・クローズ,例外処理など : fopen() : fclose() : : fopen() : fclose() : : fopen() : fclose() : •守らなければいけないルールとして利用できる –例:fopen()を呼び出した後は必ずfclose()を呼び出す [1] 石尾ら.”シーケンシャルパターンマイニングを用いた コーディングパターン抽出”,情報処理学会論文誌(2009) Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 2 コーディングパターンの活用法 コーディングパターンに則った記述がされていない バグを含むコードが存在 ○コーディングパターン fopen() ×欠落 : fopen() : fclose() : ×順序の誤り : fclose() : fopen() : 開発者がコーディングパターンに基づいて プログラムを検査し,バグを発見できる 3 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 関連研究 Javaプログラムからのコーディングパターン抽出[1] –プログラムからメソッド呼び出し,制御構造を抽出 –得られる要素列に対してパターンマイニング技術を適用 •順序を考慮したパターンを見つけるシーケンシャルパターン マイニングを適用 [1] 石尾ら.”シーケンシャルパターンマイニングを用いた コーディングパターン抽出”,情報処理学会論文誌(2009) Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 4 シーケンシャルパターンマイニング -概要•データ中に存在する,順序を考慮したパターンを 見つける –例:ユーザのWEBページのアクセス履歴から,よく閲覧 されているページの順番を検出 •入力は系列データベース,最小支持度(出現頻度) •出力は頻出系列パターン 5 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University シーケンシャルパターンマイニング -系列データベースと支持度•系列データベース –複数の入力系列から構成される –各入力系列はIDとアイテム列を持つ •系列パターンPの支持度 –系列パターンPを含む入力系列の数 •例:系列パターン(c,a)は系列ID=1,2に含まれるため支持度は2 系列ID 1 アイテム列 a b c b a 2 3 b c d a b e b b a c d e b Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 入力系列 6 シーケンシャルパターンマイニング -系列データベースと支持度•系列データベース –複数の入力系列から構成される –各入力系列はIDとアイテム列を持つ •系列パターンPの支持度 –系列パターンPを含む入力系列の数 •例:系列パターン(c,a)は系列ID=1,2に含まれるため支持度は2 系列ID 1 アイテム列 a b c b a 2 3 b c d a b e b b a c d e b Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 7 シーケンシャルパターンマイニング -頻出系列パターン•頻出系列パターン –指定した最小支持度を満たす系列パターン •系列長:系列パターンに含まれるアイテムの数 系列ID 1 2 3 アイテム列 a b c b a b c d a b e a b a c d e b 最小支持度2でマイニングを行うと,一例として 系列パターン(b,c,b)(系列長3,支持度3)が出力される 8 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 組込みプログラムの特性 厳しい時間制約 –リアルタイム性 •計算を正確に,時間内に完了することを保証する ジャンプ命令,プリプロセッサ命令の多用 #ifdef 条件式 処理 A 実行時間短縮 : 処理 B Department of Computer Science, Graduate School of Information Science and Technology, Osaka University goto文 実行コードの 切り替えによる 実行時間短縮 実行コード #else : : #endif 9 研究動機 •C言語プログラムからコーディングパターンを抽出 –高信頼性ソフトウェアである組込みプログラムの主な 開発言語 •関連研究では組込みプログラムの特性を 考慮していない 特性を考慮してC言語プログラムから コーディングパターンを抽出する必要がある 10 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 研究概要 •C言語プログラムからのコーディングパターン 抽出手法の提案 –組込みプログラムの特性を考慮 •組込みプログラムへの適用実験及び評価 11 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University コーディングパターン抽出手法の概要 コーディング パターン抽出 要素抽出 プログラム コーディング パターン 要素列 ステップ1 結果の 絞り込み ステップ2 絞り込み後の コーディング パターン ステップ3 12 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University ステップ1:構成要素の抽出 プログラムから各要素を抽出 –マクロ呼び出し,関数呼び出し –制御構造 –goto文,ラベル文,return文 fp = fopen(); CHECK(); if (flag) { fgets(); goto label; } label: fclose(fp); Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 要素抽出 fopen() CHECK() IF fgets() goto label END-IF label: fclose() 13 ステップ1:構成要素の抽出 プログラムから各要素を抽出 –マクロ呼び出しや関数呼び出し –制御構造 –goto文,ラベル文,return文 fp = fopen(); CHECK(); if (flag) { fgets(); goto label; } label: fclose(fp); Department of Computer Science, Graduate School of Information Science and Technology, Osaka University fopen() CHECK() IF 要素抽出 fgets() goto label END-IF label: fclose() 14 ステップ1:構成要素の抽出 プログラムから各要素を抽出 –マクロ呼び出しや関数呼び出し –制御構造 –goto文,ラベル文,return文 fopen() CHECK() fp = fopen(); CHECK(); if (flag) { fgets(); goto label; } label: fclose(fp); Department of Computer Science, Graduate School of Information Science and Technology, Osaka University IF 要素抽出 fgets() goto label END-IF label: fclose() 15 ステップ1:構成要素の抽出 プログラムから各要素を抽出 –マクロ呼び出しや関数呼び出し –制御構造 –goto文,ラベル文,return文 fp = fopen(); CHECK(); if (flag) { fgets(); goto label; } label: fclose(fp); Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 要素抽出 fopen() CHECK() IF fgets() goto label END-IF label: fclose() 16 ステップ2:コーディングパターン抽出(1/3) • シーケンシャルパターンマイニングを利用 –順序を考慮する方がバグ検出において優秀[2] –使用アルゴリズムはSPADE[3] •最小支持度として10を指定 –10個以上の関数に含まれるコーディングパターンを出力 [2] H.Kagdi et al.” Comparing Approaches to Mining Source Code for Call-Usage Patterns”, in Proc.of MSR 2007(2007) [3] Mohammed J. Zaki.” SPADE: An Efficient Algorithm for Mining Frequent Sequences”, Machine Learning(2001) Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 17 ステップ2:コーディングパターン抽出(2/3) 入力となる系列データベースはステップ1の 要素列を基に作成 –系列IDはプログラム中の各関数に割り当て –アイテム列は各関数中の要素列に対応 系列ID アイテム列 1 IF fopen() END-IF fgets() fclose() 2 fopen() goto label fgets() label: fclose() 3 fopen() IF fgets() return END-IF fclose() 4 fopen() fgets() fclose() Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 18 ステップ2:コーディングパターン抽出(3/3) 例:最小支持度2でシーケンシャルパターン マイニング 系列ID アイテム列 1 IF fopen() END-IF fgets() fclose() 2 fopen() goto label fgets() label: fclose() 3 fopen() IF fgets() return END-IF fclose() 4 fopen() fgets() fclose() fopen() fgets() fclose()という系列長が3, 支持度が4のコーディングパターンが抽出される Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 19 ステップ3:結果の絞り込み -コーディングパターンの除外•コーディングパターンとしての正確性 –制御構造及びジャンプ命令の対応関係が取れていない 場合は除外 •関数呼び出しの数 –関数呼び出しの数が2つ未満の場合は除外 fopen() IF fclose() fopen() label: fclose() END-IFが ない goto文が ない IF goto label END-IF label: 関数呼び出しの 数が2つ未満 20 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University ステップ3:結果の絞り込み -マクロの考慮(1/3)ジャンプ命令の対応関係について –マクロ関数がgoto文を含んでいる場合に対応 コーディングパターン fopen() CHECK() fgets() label: fclose() ジャンプ命令の対応関係が 取れていないため除外される 21 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University ステップ3:結果の絞り込み -マクロの考慮(2/3)ジャンプ命令の対応関係について –マクロ関数がgoto文を含んでいる場合に対応 コーディングパターン fopen() CHECK() fgets() label: fclose() マクロ関数の定義 #define CHECK() do { : goto label; : } while (0) 実際は対応関係が取れている Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 22 ステップ3:結果の絞り込み -マクロの考慮(3/3)#ifdef命令への対応 –ラベルが再定義されている場合が存在 マクロ関数の定義 #define CHECK() do { : goto label; : } while (0) : #ifdef 条件式 define label labelA #else define label labelB #endif : 23 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University ステップ3:結果の絞り込み -極大化極大化 –部分パターンの中から系列長が最大のパターンを選択 系列長1のパターン 関数A : fopen() : fgets() : fclose() : 関数C fopen() コーディング パターン抽出 : fopen() … : fgets() : fclose() : 系列長が最大の パターンを選択 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University fgets() 系列長2のパターン fopen() fopen() fgets() fclose() fclose() fgets() fclose() 系列長3のパターン fopen() fgets() fclose() 24 適用実験 -概要•提案手法の有効性を確認するための適用実験 –実際の組込みプログラムに対して提案手法を適用し, 以下の項目を調査 •コーディングパターンの数 •計算速度 •仕様に基づくコーディングパターンの評価 •提案手法の有効性,改善点を考察 25 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 適用対象 2種類の組込みプログラム,計6つ –ATK2[4] •TOPPERSプロジェクトが開発した自動車制御用の リアルタイムオペレーティングシステム(RTOS) •4つのリリース(SC1,SC3,SC1MC,SC3MC) –Release 1.3.0 1.2.1 1.3.1 1.2.1 –Linuxカーネルソース(v4.0-rc1) •drivers/pci:PCI仮想ドライバのためのプログラム •arch/arm :ARMアーキテクチャ固有のカーネルプログラム [4] TOPPERSプロジェクト https://www.toppers.jp/ Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 26 適用対象 -規模各プログラムの規模は以下の通り –.cファイル数,関数の数,プログラムの総行数(LOC) 対象名 .cファイルの数 関数の数 ATK2/SC1 12 81 4,620 ATK2/SC1MC 17 131 7,726 ATK2/SC3 16 134 7,698 ATK2/SC3MC 19 172 10,244 Linux/pci 30 991 24,441 Linux/arm 61 738 18,672 LOC 27 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 抽出されたコーディングパターンの数 抽出数と各絞り込みを適用後のコーディング パターンの数 –開発者が手作業で確認できる数にまで削減 対象名 抽出数 絞り込み後 絞り込み後 絞り込み後 極大化 (関数呼び出し) (制御構造) (ラベル) 後 ATK2/SC1 409K 393K 258K 9.03K 29 ATK2/SC1MC 176M 175M 172M 154K 240 ATK2/SC3 157K 150K 9.79K 3.64K 64 ATK2/SC3MC 343M 342M 341M 274K 511 Linux/pci 493K 991 296 296 197 Linux/arm 3.20K 17 14 14 7 28 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 計算速度 各ステップの所要時間を測定 –要素抽出,パターンマイニング,絞り込みの3ステップ 対象名 ステップ1 ステップ2 ステップ3 合計時間 ATK2/SC1 0.0930秒 3.06秒 2.14秒 5.29秒 ATK2/SC1MC 0.0780秒 81.2秒 1.1秒 82.4秒 ATK2/SC3 ATK2/SC3MC 0.108秒 4時間46分 74.3秒 4時間47分 0.0780秒 11時間1分 148秒 11時間3分 Linux/pci 0.158秒 376秒 2.12秒 378秒 Linux/arm 0.141秒 19.3秒 0.313秒 19.6秒 29 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University コーディングパターンの評価 -概要•ATK2の各プログラムのコーディングパターンに 対して系列長の上位5個,計20個を選択 –4つのリリース×5個 •コーディングパターンがATK2の仕様を反映して いるか確認 30 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University コーディングパターンの評価 -結果結果 –20個中19個が仕様を反映したコーディングパターンで あることを確認 –コーディングパターンを今後の開発で利用していくことが 可能だと判断 •次回以降の開発においてコーディングパターンと比較することで, プログラム中のバグを検出 31 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University ATK2の仕様 ATK2のRTOSが提供する機能(外部仕様書[5]より) –割込み処理 •割込みの禁止,許可操作(組で使用する必要がある) –エラー処理(エラーハンドリング) •OSが提供するシステムサービスはエラーチェックを行う (割込み管理,アラーム制御,カウンタ制御など) •OSが提供するサービス内で発生したエラーの処理(ハンドリング) [5]”ATK2 外部仕様書”, https://www.toppers.jp/docs/tech/ATK2-0010_ATK2_spec_100.pdf Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 32 ATK2のプログラムの一部 -割込みの禁止,許可操作// アラームの状態参照 StatusType GetAlarm(AlarmType AlarmID, TickRefType Tick) { 他からの割込みを : x_nested_lock_os_int(); 禁止する : // カウンタの現在値を取得 curval = get_curval(p_cntcb, CNTID(p_cntcb)); *Tick = diff_tick(p_almcb->cntexpinfo.expiretick, curval, p_cntcb->p_cntinib->maxval2); : x_nested_unlock_os_int(); : } 他からの割込みを 許可する 33 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University ATK2のプログラムの一部 -エラーチェック//アラームの状態参照 StatusType GetAlarm(AlarmType AlarmID, TickRefType Tick) { : LOG_GETALM_ENTER(AlarmID); CHECK_DISABLEDINT(); CHECK_CALLEVEL(CALLEVEL_GETALARM); CHECK_ID(AlarmID < tnum_alarm); CHECK_PARAM_POINTER(Tick); p_almcb = get_almcb(AlarmID); p_cntcb = p_almcb->p_alminib->p_cntcb; x_nested_lock_os_int(); : システムサービス内の エラーチェック関数群 } 34 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University ATK2のプログラムの一部 -エラーハンドリング: d_exit_no_errorhook: x_nested_unlock_os_int(); exit_no_errorhook: エラーが発生した場合は LOG_GETALM_LEAVE(ercd, Tick); return(ercd); エラーハンドリングを行う #ifdef CFG_USE_ERRORHOOK exit_errorhook: x_nested_lock_os_int(); d_exit_errorhook: call_errorhook(ercd, OSServiceId_GetAlarm); goto d_exit_no_errorhook; #endif } Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 35 仕様を表すコーディングパターン エラーチェック 割込み処理 エラー ハンドリング CHECK_DISABLEDINT() CHECK_CALLEVEL() CHECK_ID() x_nested_lock_os_int() d_exit_no_errorhook: x_nested_unlock_os_int() exit_no_errorhook: return exit_errorhook: x_nested_lock_os_int() call_errorhook() goto d_exit_no_errorhook: goto文 プログラム名:ATK2/SC1 支持度:14 系列長:13 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 36 Linuxカーネルソースからの コーディングパターン pci_read_config_word() pci_write_config_word() Linux/pciより,支持度48のコーディングパターン raw_spin_lock_irqsave() raw_spin_lock_irqstore() Linux/armより,支持度25のコーディングパターン 37 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 考察 ジャンプ命令,プリプロセッサ命令の有効性 –ATK2のコーディングパターンは2命令を含んでいる –Linuxカーネルソース(pci,arm)のコーディングパターンは 含んでいない (プログラム中には存在) 実験対象を増やして手法が有効な場合を 明らかにする必要がある 38 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 今後の課題 -計算速度の改善•計算速度の改善 –コーディングパターンが多いプログラムでは計算に 時間が掛かる –パターンマイニングに掛かる時間が最も多い •解決案 –パターンマイニングを並列処理化 39 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 今後の課題 -コーディングパターンのグループ化•コーディングパターンのグループ化 –同じ機能を表す類似コーディングパターンが多い –例:エラーチェック関数の差異 CHECK_DISABLEDINT() CHECK_CALLEVEL() CHECK_ID() x_nested_lock_os_int() : CHECK_DISABLEDINT() CHECK_CALLEVEL() … x_nested_lock_os_int() : 1つのコーディングパターン集合に 40 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University まとめ •C言語プログラムからコーディングパターンを抽出 –組込みプログラムの特性を考慮 •今後の課題 –計算速度の改善 –コーディングパターンのグループ化 –実験対象の拡大 41 Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
© Copyright 2024 ExpyDoc