ソフトウェア・シンポジウム 2015 in 和歌山

安全系組込ソフトウェア開発におけるユニットテストの効率化〜Concolic Testing の活用事例〜
岸本 渉
株式会社デンソー
wataru kishimoto@denso.co.jp

要旨

化を進める必要があるが，従来の自動化のように人手で出来ることをスクリプトや記述言語で開発，蓄積して実機能安全など，安全系のソフトウェアに対する詳細な行を自動化する方式ではやはり限界がある．

テスト要件は MC/DC カバレッジなど具体的な要求としソフトウェア工学では，近年，モデル検査の技術を拡て浸透し始めている．人手に頼ったテストでは抜け漏れ張し，ソースコードを探索する技術が急激に発達してい等の問題と，コスト増の問題が生じ対応できないため自る [2]．静的解析では，有力なプロプライエタリ系のツー動化が進んでいる．しかし，現有のツールでは C0，C1，ルが出現し，この分野では人手による方式を完全に駆逐

MC/DC カバレッジ 100 ％を達成することが出来ず，そしつつある．しかし，仕様ベースのテストについては，の部分を人手で対処するため大きな損失が生じている．

様々な研究が行われているが，有力な自動化ツールは存

本稿では，ソフトウェア工学における最新の研究成果在しない．

が反映しているオープン系のツール Concolic Testing を

現状では，我々が求める自動化を達成できる統合ツール活用してこの問題を解決したので報告する．オープン系は存在しないが，部分的には利用できる技術が出現し，そのツールは導入時に，技術的なスキルが求められるが，れらの技術は現在も発達中である．具体的には，Symbolic

様々な工夫を行うことが出来るので，柔軟に対応し，導Execution や Concolic testing など，ソースコードの高度な解析を行う技術を指す [3, 4, 5]．この分野では，NASA入時の問題を解決したので報告する．の JPF/SPF や LLVM/KLEE や CIL/CREST などオープン系のツールが先行しており，これらを超えるプロプ

1. はじめにライエタリ系のツールは出現していない [6, 7, 8]．
本論文では，高度な解析技術を実際のユニットテスト

我々は，センサで車両の状態を検知し，その結果を用に活用する試みについて報告する．この種の技術は，最いて安全系装置を制御する組込ソフトウェアの開発を担

先端のオープン系技術を使いこなす高度なエンジニアを当している．このシステムは，車種やグレードにおける育成しないと利用することが困難である．将来に向けてオプション搭載ではなく標準搭載が進み，他サプライヤ新たなソフトウェア生産技術を構築する試みとして評価との価格競争が激化している．高い品質と自動車機能安を兼ねて行った．

全規格 ISO26262 に準拠するなど安全性を担保しつつ，本論文の構成と主な内容は以下の通りである．2 章で一層のコスト削減が求められている．さらに，車両の安は，現行のユニットテスト方式における課題を明確にし，全系機能が多様化し，従来以上に開発短納期化の要求が強くなり，コスト削減以上に開発サイクルの短期化が求

3 章では，その対策と導入するツールについて説明する．
4 章では，我々のソースコードに対してツールは有効にめられている [1]．

機能するのかを確認した．その方法は，あるプロジェク

このような状況に対応するには，従来のテスト方式をトのソースコードのなかからサンプリングしたものを評基に要員の増強や方式改善では限界がある．当然，自動価用に書きなおしたコードを使って行った．その結果，

57

SEA

ソフトウェア・シンポジウム 2015 in 和歌山

ツールを使うための工夫を行えば十分使えることが判った．5 章では，実際にプロジェクトにおけるユニット群に対し，現行のツールでは MC/DC カバレッジ 100%が未達であるユニットに適用し，達成できることを確認できた．6 章では，この結果からテスト方式を変更することについて検討した．

2. 現行ユニットテスト方式の分析
安全系組込ソフトウェアは，自動車機能安全規格

ISO26262 に準拠することが求められている．そのため，我々の職場では，ユニットテストにおいて，実装マイコンコードを評価対象としてマイコンシミュレータでユニットテスト実行を行う仕組みを持つツールと，そのツールを効率よく用いるための内製ツールを採用している（図1）．このユニットテストツールはソース解析を行い C0，C1，MC/DC カバレッジを 100%達成するテストケースを生成する機能も持っている．

図 1. 現行ユニットテスト方式

これらのツールを用いて大部分の作業を自動化しているが，実際のところ C0，C1，MC/DC カバレッジが100%未満のテストケースが生成される場合がある．安全系のテスト対象ユニット，すなわち ASIL A 以上が割り当てられたユニットでは，人手により C0，C1，MC/DC

スト対象ユニットを安全系かどうかに関わらず全ユニッカバレッジを 100%達成するテストケースを追加する作

なり，生産性と品質の両方を向上できる．

トに拡大することができる．それによって，統合テストにおけるユニットテストレベルの詳細なテストが不要と業が発生する．これは，単にカバレッジが悪い所を見れ

3.2. ツールの選択ば追加できる容易な作業ではなく，カバレッジが達成できていない箇所に至る制御経路を解析する必要がある．

ユニットテストのテスト設計に新しいテストツール

そのため，安全系のユニットテストは，多くの工数を必の適用を検討することとした．ユニットテストの自動化要とし，生産性を低下させ，納期を圧迫している．

については様々なアプローチが研究されているが，本稿では，現場にて実用化するため，容易に試用でき，事前

3. 対策と CREST の導入評価できることが求められることから，研修用に提供されている環境 (RAM は 2GB，CPU は Xeon E5520

3.1. 対策の考え方

2.26GHz，OS は CentOS) で CREST を用いることとした．CREST とはオープンソースとして公開されている
C 言語向け concolic testing ツールである [9]．

前章で分析した通り，現在使用しているユニットテストツールだけでは十分なテストケースの生成ができない．
安全系以外のユニットで C0，C1，MC/DC カバレッジ

3.3. CREST 概要

が 100%未満のユニットに対しては，実機を用いた統合テストにおいてユニットテストレベルの詳細なテストをCREST は Concrete Execution と Symbolic Execution を組み合わせた Concolic Testing を行うツールである．ここでは，まず Symbolic Exectution と Concolic

大きな工数をかけて行っており，システムテストを含めたテスト工程全体の効率化の妨げとなっている．
したがって，十分なテストケースが自動で生成できるTesting について説明する．

ようになれば，MC/DC カバレッジ 100%のユニットテ

58SEAソフトウェア・シンポジウム 2015 in 和歌山(1)Symbolic Execution:

Execution は変数を抽象解釈 (abstract interpreta-0tion) と呼ばれる方法で取扱い，各条件分岐の組合せを制約式として得る．得られた制約式を制約ソルバー (constraint solver) を用いて解く．

400

変数に代入された値を使って実行するが，Symbolic

200

Frequency

600

Symbolic Execution は，プログラムの制御フローを解析する手段である．通常のプログラム実行は，01020304050

CCN(2)Concolic Testing:

図 2. プロジェクト A で作成したソースコードのConcolic Testing は固定の具体的な値を使ったテス
トと Symbolic Execution を連携させて実行することにより，プログラムが持つすべての可達経路を網循環複雑度の分布羅するテストデータを生成することを目標としてい1 unsigned char ccn2( unsigned char a ){2unsigned char result ;3if ((a & 0x01U) == 0x01U){
4result = 1U;5}else{6result = 0;
7}
8return ( result );9 }る．経路探索は，Symbolic Execution により分岐点における分岐条件を求め，実行されなかった経路を選択するための入力値を制約ソルバーで求め，その具体的な入力値でプログラムを実行する，という流れである．

Symbolic Execution との違いは，すべてを疑似実行するのではなく，実コードでの実行とハイブリッドで行う点にある．この特徴を生かし，テスト対象の範囲を広図 3. CCN=2 のサンプル関数

く取り扱うことができるし，ランダム探索におけるスピードも改善されている．制約ソルバーでは解析的に解ると大部分が 10 以下であることがわかった（図 2）．よっけない場合，乱数を用いたヒューリスティックな解を求て，サンプル関数として CCN が 2(小)，4(中)，8(大) のめるが，そのランダム探索におけるスピードも改善され3 ユニットを抽出して試用することとした．
まず，CCN=2 のサンプル関数 (図 3) に CREST を試用した．探索オプションとして DFS(Depth-First Search)ている．

4. CREST の網羅性確認

では，カバレッジ 100%のテストケースが生成されなかったが，その他の探索方法ではカバレッジ 100%のテスト現行ユニットテスト方式の欠点を補うため CREST をケースが生成された．DFS オプションの場合，例題のよ導入するにあたり，我々のソースコードにおいて CRESTうなビット演算に対して，CREST が使っている制約ソにより全可達経路のテストケースを生成できるかを確ルバー（yices）が対応していないことが原因である．韓認する必要がある．そこで，いくつか関数を抽出し，国の SAMSUNG 社が携帯電話の OS に対して行った論CREST で確認を行った．確認を行う上で，問題点を評価するため，選んだ関数の持つロジックを抽象化したサ文では，ビット演算のための機能追加を行ったことが書かれている [10]．ここでは，追加機能を用いず，DFS 以ンプル関数を作成して試用した．その理由は，色々なバ外の探索オプションとして CFG(Control-Flow DirectedSearch) を用いて解を求めた．

リエーションを試すことと，問題点について外部からコメントをもらうとき，製品そのものが持つ情報を隠ぺい

次に，CCN=4 のサンプル関数 (図 4) に CREST を試するためである．

用した．CCN=2 のサンプル関数と同様に DFS 以外のサンプル関数の抽出方法は循環的複雑度（以下，CCN）探索方法でカバレッジが 100%のテストケースが生成さを基に選択することとした．あるプロジェクト A で作成れたが，引数 a が 5 行目で配列 c の領域外アクセスとなしたソースコードの各関数の CCN の分布状況を確認す

59SEAソフトウェア・シンポジウム 2015 in 和歌山

1234567891011121314unsigned char ccn4( unsigned char a,unsigned short b ){static const unsigned short c[2]={ 510U, 514U };unsigned short d;unsigned char result;d = c[a];if ( b == 0U ){result = 2U ;}else if ( (d <= b) && (b <= 1000U) ){result = 1U ;}else{
result = 0U ;}return ( result ) ;}図 4. CCN=4 のサンプル関数
12345678978
9int main( void ){unsigned char a;unsigned short b;while ( 1 ){CREST_unsigned_char( a ) ;if ( a < 2U ){break ;}}CREST_unsigned_short( b );printf( "%d %d\t\t %d\n", a, b, ccn4( a, b ) );}図 5. 入力値を制限する処理を追加したテストドラ

1 void func( void ){2 if ( Dat6 > 0U ){3Dat6--;
4if ( Dat6 == 0U ){5AAA[ Dat5 ]._dat2--;
6if ( AAA[ Dat5 ]._dat2 > 0U ){7
Dat6 = AAA[ Dat5 ]._dat1;
8if ( Dat1 == 0x01 ){9
Dat1 = 0x00;
10}12} else {13Dat5++ ;14if ( Dat5 < 6 ){15
Dat6 = AAA[ Dat5 ]._dat1 ;16
Dat1 = AAA[ Dat5 ]._dat3 ;17} else {18Dat4++ ;19if ( Dat4 < Dat7 ){20} else {21if ( Dat3 == 0x01 ){22Dat4 = 0U ;23} else {24Dat2 = 0x00 ;
25}
26}
27}
28}
29}
30}
31 }

図 6. CCN=8 のサンプル関数の場合は，その必要が無く使い勝手が良い．

イバ

最後に，CCN=8 のサンプル関数 (図 6) に CREST を試用した．CCN の増加だけでなく入力変数が 24 もある関数のため，何の工夫もせずに CREST によりテストる値を生成していた．CREST はあくまでプログラムをケースを生成すると 14 分岐あるうちの 7 分岐まで網羅実行して入力を求めているため，配列の領域外にアクセするテストケースは生成されたが，残り 7 分岐を網羅すスして得られた値により分岐条件が成立すれば，それがるテストケースは約 1 時間探索を繰り返しても生成さテストデータになってしまう．

れなかった．ここで，この CCN=8 のサンプル関数も変この問題を回避するために CREST が生成する a の値

数 Dat5 が配列 AAA のインデックスとなっているためが 2 未満となるように条件文を追加した (図 5 の 4 行目，入力値を制限する処理を追加した．それにより生成され及び，6 行目から 9 行目)．その結果，適切なテストデーたテストケースによるカバレッジは増加したが 100%にタによりカバレッジが 100%となるテストケースが生成は至らなかった．そこで，可達経路を網羅する入力値のされることを確認した．

候補が多いために探索に時間がかかっていると考え，配ここでテストドライバに print 文を使用しているが，列のインデックスとなる変数以外で取り得る値の範囲がCREST 以外の Symbolic Execution ツールでは，テス決まっている変数に対しても入力値を制限する処理を追トドライバで使用する print 文自身も経路探索の対象と加した．その結果，約 1 分の探索時間でカバレッジがなり，ソースコードを与える必要が生じるが，CREST100%となるテストケースが生成された．ここで行った

60

SEAソフトウェア・シンポジウム 2015 in 和歌山

表 1. ユニットテストツールで生成したテストケー

表 2. CREST で生成したテストケース追加後のカスのカバレッジ

バレッジ

関数
No.

C0
カバレッジ

C1
カバレッジ

MC/DC
カバレッジ

CCN

関数
No.

C0
カバレッジ

C1
カバレッジ

MC/DC
カバレッジ

1

100.0%

100.0%

2

100.0%

100.0%

100.0%

4

1

100.0%

100.0%

100.0%

4

100.0%

112

100.0%

100.0%

100.0%

113

100.0%

4

100.0%

100.0%

100.0%

123

100.0%

100.0%

100.0%12

100.0%

100.0%

10

4

100.0%

100.0%

100.0%

10

◦CCN

∗

5

75.0%

50.0%

33.0%

4

5

100.0%

100.0%

100.0%

4

6

100.0%

100.0%

100.0%

1

6

100.0%

100.0%

100.0%

1

7

100.0%

100.0%

100.0%

1

7

100.0%

100.0%

100.0%

1

8

100.0%

100.0%

100.0%

28

100.0%

100.0%

100.0%

2

◦

∗

9

45.0%

50.0%

42.0%

8

9

100.0%

100.0%

100.0%

810

100.0%

100.0%

100.0%

12

10

100.0%

100.0%

100.0%

12

11∗

97.0%

80.0%

50.0%

15

11◦

100.0%

100.0%

100.0%

15∗∗1252.0%

42.0%

20.0%

13

12

97.0%

95.0%

90.0%

13

13

100.0%

100.0%

100.0%

113

100.0%

100.0%

100.0%

114

100.0%

100.0%

100.0%

1

14

100.0%

100.0%

100.0%

115

100.0%

100.0%

100.0%

115

100.0%

100.0%

100.0%

1

1 if ( (a == FALSE) && (b == TRUE) ){2 ・・・・・・3 }else if ( (a == FALSE) && (b != TRUE) ){4 ・・・・・・5 }6 else {7 }対策は，形式仕様で用いられている「事前条件」に相当すると考えられる．
以上のことから，CREST を我々のソースコードに適用できる目途付けを行うことができた．次章では，実在するプロジェクト A で作成したソースコードにおいてC0，C1，MC/DC カバレッジ 100%のテストケースが生成できなかった関数に対して，実際に CREST を適用し

図 7. 未達経路 の例

現行ツールの問題を解決できるかを確認する．
ケースが生成された (表 2)．残り 1 つの関数においてカ

5. 現行ユニットへの CREST 適用結果

バレッジが 100%とならなかった理由は 2 つあり，1 つ

ここでは，プロジェクト A で作成した実際のソースは防衛的プログラミングによりメモリ破壊が発生しないコードに対して，CREST が現行ツールより優れている限り通らない経路である．もう 1 つは図 7 のように 1 行か否かを比較評価する．

目の 2 つ目の条件式が成立しない場合は 3 行目の 2 つ目の条件式が必ず成立するため無駄な処理となっていたた

まず，プロジェクト A のライブラリから無作為に Cめであった．

ソースファイルを抽出し，そこに含まれる関数に対して，現行ユニットテストツールによりテストケースを生成さ以上のことから，現行のユニットテストツールで全可せた．その結果を表 1 に示す．対象とするソースファイ達経路のテストケースを生成できなかったユニットに対ルに含まれる 15 関数の内，∗ 印の 4 つの関数においてして，この実験では CCN の大小に関わらず CREST にC0，C1，MC/DC カバレッジ 100%に未達であった．

より全可達経路のテストケースを生成することが確認できた．

それらの関数に対して CREST によりテストケース◦を生成し直した結果，4 つのうち 印の 3 つの関数において C0，C1，MC/DC カバレッジ 100%となるテスト

61

SEA

ソフトウェア・シンポジウム 2015 in 和歌山

図 8. CREST 導入後のユニットテスト方式
図 9. CREST 導入後のデグレードテスト方式

6. CREST によるユニットテスト方式の改善を使いテスト結果を生成し，それをデグレードテストの本章では，2 章で示した現行のユニットテスト方式に期待値とすることで，ほとんど人手を必要としなくなる．

対して，どのように CREST を導入するかを述べる．

但し，4 章で説明したようにただ入力を与えるだけでは可

まず，現状の方式ではユニットテストツールが出力す達経路を通るテストケースを得られない場合があり，入るテストケースに対して，カバレッジ 100%となるテス力値を制限する処理の追加は必要となる．また，CRESTトケースと正解値を設計書を基に追加する．CREST 導の特性やパラメータの理解と，テスト対象ユニットが持入により，設計書を基にテストケースを追加する作業が，つドメイン固有のレジスタ操作などの特殊性を理解するユニットテストツールが生成した関数の入出力情報からスキルも求められる．

CREST 用にテストドライバを作成する作業に置き換わる．この作業は，設計情報を知らなくてもできる作業の7. おわりにため，設計者のスキルがある人以外でも担当することができる．よって，設計情報を知らないとできない作業はれにより，ユニットテストでかかる工数は大幅に削減さC 言語向け Concolic Testing ツールである CREST が我々のソフトウェアに適用可能であることをサンプル関数，及び，実際の製品ソフトウェアを使って確認できた．

れると考えられる．

これにより，ユニットテストにおいて課題の一つであっ正解値を設計書を基に見直す作業だけとなる (図 8)．こまた，自職場ではマイコン変更，及び，コンパイラ変たテストケース作成の効率化に CREST を用いることで更を伴う派生開発も多々あり，その際に，実施するデグ解決の目途がついた．また，ユニットテストにおけるもレードテストには，CREST の適用が更に有効である．

う一つの課題である正解値の作成も派生開発におけるデその方式を図 9 に示す．現状，派生元のプロジェクトでグレードテストでは解決可能であることが確認できた．

はユニットテストで実施可能なテストケースを実機を用

当初，オープン系のツール CREST は，商用ツールといた結合テストに含めて実施していたため，デグレード比べ入門向けの情報やノウハウが少なくとても困惑した．

テストにおいてユニットテストを実施する場合，一から特に，動作環境を構築するのは，CREST を構成していテストケースの作成を余儀無くされる．しかし，CRESTる様々なオープン系ツールの依存関係があり難しい．実を導入すると可達経路を通るテストケースを得られるた際に CREST が動作する環境があれば，その環境下で試め，派生元のマイコン実コードと得られたテストケース

行的に使いながら問題を解決して行くのは，それほど難62

SEAソフトウェア・シンポジウム 2015 in 和歌山

しくなく，短期間で進めることができた．
今後の課題として，デグレードテストは直ぐにでも改善すべき方式であるため，現場の担当者が容易に使えるような環境の整備と保守方式を検討する．また，CREST でテストケースを生成する上で，変数の各ビットが ON/OFFのような意味を持つ入力のテストケース生成は変数のサイズが大きくなるにつれて長くなる生成時間の短縮が課題である．
最後に，この研究は，デンソー技研センターの 2014
年度ソフトウェア工学ハイタレント研修の中で行った．
講師の先生と，研究の機会を与えていただいた職場に感謝する．

参考文献[1] 大須賀竜治，“ISO26262 の日本自動車業界での活動と今後について ( < 連載 > ISO 26262-自動車業界における機能安全に対する取り組み-)，” 品質，vol.43，no.2，pp.212–217，2013．
[2] 梅村晃広，“SAT ソルバ・SMT ソルバの技術と応用，” コンピュータ ソフトウェア，vol.27，no.3，pp.24–35，2010．
[3] K. Sen, D. Marinov, and G. Agha, CUTE: a concolicunit testing engine for C, vol.30, ACM, 2005.
[4] J. Burnim and K. Sen, “Heuristics for scalable dynamic test generation,” Proceedings of the 2008 23rd
IEEE/ACM international conference on automatedsoftware engineeringIEEE Computer Society, pp.443–446 2008.
[5] J. Foster, “Symbolic execution,” http://www.seas.harvard.edu/courses/cs252/2011sp/slides/Lec13SymExec.pdf.
[6] W. Visser, C.S. Psreanu, and R. Pelánek, “Test input
generation for java containers using state matching,”
Proceedings of the 2006 international symposium on
Software testing and analysisACM, pp.37–48 2006.
[7] C. Cadar, D. Dunbar, and D.R. Engler, “Klee: Unassisted and automatic generation of high-coverage tests
for complex systems programs.,” OSDI, vol.8, pp.209–
224, 2008.
[8] J. Burnim and K. Sen, “Heuristics for scalable dynamic test generation,” Proceedings of the 2008 23rd
IEEE/ACM international conference on automatedsoftware engineeringIEEE Computer Society, pp.443–446 2008.
[9] CREST, “Concolic test generation tool for c,”
http://jburnim.github.io/crest/.
[10] Y. Kim, M. Kim, Y.J. Kim, and Y. Jang, “Industrialapplication of concolic testing approach: A case study
on libexif by using crest-bv and klee,” Software Engineering (ICSE), 2012 34th International Conference
onIEEE, pp.1143–1152 2012.

63SEA