PowerPoint プレゼンテーション

記号実行を用いた

テストデータ自動生成の試行評価

株式会社デンソー 電子技術3部

榎本秀美

1

/ 19

目次

1. 背景

2. 単体テストの問題点

3. 対策案の検討

4. 評価内容

5. 評価結果

6. まとめ

［参考］CREST

 主要製品

2

/ 19

3

/ 19

1. 背景

 自動車系組込みソフトウェアの動向

市場の要求

規模の増加・複雑化

2000年

現在

100万行

500万～

1000万行

プログラム行数

（参考）経済産業省HP

環境

電動化、小型化

安全

安全運転支援、自動走行

快適・利便 インフラ連携

＜プログラム規模＞

機能安全準拠と短期開発・コスト削減の両立が必要

＜機能開発＞

機能安全規格の準拠

短期開発・コスト削減



製品の早期市場投入



新興市場での低価格車需要



安全・安心の保障

5～10倍

4

/ 19

1. 背景

 機能安全準拠に向けたソフトウェア開発の取組み

機能安全規格：

・ 機能・部品が故障したとしてもシステムの安全性を確保することを

狙いとして定められた規格

・ ソフトウェア開発においては、安全性確保のための具体的な手法が

定義されている

今回は、単体テストに対する取組み内容を報告する

要件定義

アーキテクチャ設計

部品作成

ユニット設計

要求の検証

結合テスト

単体テスト

欠陥注入

負荷計測

インターフェース試験

MC/DCカバレッジの

実施

トレーサビリティ管理

詳細な設計要件

（安全設計）

設計検証

（制御フロー解析など）

機能安全規格へ対応と効率化を推進している

5

/ 19

2. 単体テストの問題点

MC/DCカバレッジ100%を達成するために、

仕様ベーステストに加えて実装ベーステストを実施している

手作業

実行

コード

シミュレータ

テスト結果

MC/DCカバレッジ

仕様書

ソース

コード

（関数）

MC/DCカバレッジのテストが追加されたことで、

単体テストの工数が更に増加した

テスト

ケース

工数増加

人手による

テストデータの作成

＋

MC/DCカバレッジの

テスト（テスト数が多い）

クロス

コンパイラ

手作業

ソースコードに対する

MC/DCカバレッジ100%達成は不可

仕様ベーステスト

実装ベーステスト

6

/ 19

2. 単体テストの問題点

実装ベーステストは入力が形式言語のためテストデータ自動生成可能

⇒市販ツールの導入を開始している

ツールが生成するテストデータの

MC/DCカバレッジ率を高める必要がある

市販ツールでは、MC/DCカバレッジ未達のケースが発生し、

手作業による追加テストを行うため効率化の妨げとなっている

手作業

実行

コード

シミュレータ

テスト結果

MC/DCカバレッジ

仕様書

ソース

コード

（関数）

テスト

ケース

クロス

コンパイラ

市販ツール

自動生成

手作業

C言語

仕様ベーステスト

実装ベーステスト

追加テスト

カバレッジ未達

の場合

7

/ 19

3. 対策案の検討

 テストデータの生成方式

静的解析

記号実行

説明

・ ソースコードから制御パスを解析

そのパスを通るテストデータを生成

・ ソースコードを疑似的に実行

・ 変数間の関係を制約として記述

制約ソルバで解を得てテストデータ

を生成

メリット



市販ツールを含め多くのツールが

存在



事前準備も含めた機能を持ち、

操作性が洗練されている



動的なメモリを使った制御を

解析可能

デメリット



動的なメモリを使った制御を

解析することが困難



研究段階で、操作性が行き届いた

製品は見当たらない



ツールはオープンソースで、

事前準備に手間がかかる

“静的解析”と“記号実行”の2種類が存在

合理的にテストを行うには、“静的解析”と“記号実行”を組合わせる

記号実行は、MC/DCカバレッジ率を高めることができるが、効率面で課題がある

8

/ 19

3. 対策案の検討

“記号実行” は、市販ツールよりテストデータ生成能力は高いが、

実行するのに多くの手間がかかるため、使用する範囲を限定したい

②記号実行ツールを実行

①市販ツールを実行

記号実行

ツール

市販

ツール

関数

関数

関数

市販ツールで

カバレッジ未達の対象を

実行する

関数

MC/DC100%未満

MC/DC100%

MC/DC100%

関数

関数

＜対策案＞

テスト対象

市販ツールのMC/DCカバレッジ未達部分を

記号実行で、カバレッジ100%にできるか確認する

記号実行の対象を

絞り込む

記号実行ツールの作業量を減らす

市販ツールで出来ない関数を解決する

関数

関数

関数

（静的解析）

9

/ 19

4. 評価内容

 評価事項

 対象関数

製品で用いるソフトウェア

(*)

から、循環複雑度（CCN）の平均を中心に、

40個をランダムに選定

(*) 特徴： グローバル変数の参照が多い / 判断文のネストや構成する条件が多い

②記号実行ツール実行

①市販ツール実行

評価事項

記号実行の対象関数を

絞込みできているか

市販ツールのカバレッジ未達

関数を解決できているか

確認項目



カバレッジ未達関数の数



未達パスの条件



カバレッジ結果



カバレッジ未達の原因

関数

関数

MC/DC

カバレッジ未達

市販

ツール

記号実行

ツール

関数

MC/DC

カバレッジ達成

関数

カバレッジ達成

10

/ 19

4. 評価内容

 評価ツール

市販ツールは現在使用しているツールとし、

記号実行ツールはC言語に対応したツールを選定



市販ツール①

静的解析に基づくツール

組込み系テストベッドと親和性が高い



市販ツール②

静的解析にモンテカルロ法による機能を加えたツール

モデルベース開発と親和性が高い



記号実行ツール

Concolic tesiting方式の「CREST」

Concolic testing ： 記号実行の一種で、解析速度が改善された方式

CREST： C言語向けのオープンツール

一般的なCのライブラリが使用可能

11

/ 19

［参考］CREST

 CRESTの仕組み

CRESTは、“中間コードへの変換”と“テストデータの生成”の

2つの機能で構成されている

CREST

中間

コード

_{（Concolic testing）}

記号実行

ソースコード

（対象関数）

テスト

データ

中間言語

コンパイラ

テストドライバ

テストデータを

生成する変数

変数名

変数名

テストデータの生成

（run_crest）

中間コードへ変換

（crestc）

解析・実行できる形式に変換

パスを解析し、テストデータを生成

12

/ 19

4. 評価内容

 評価環境

MC/DCカバレッジを比較評価するため、シミュレータを統一

実行

コード

シミュレータ

クロス

コンパイラ

テスト結果

MC/DCカバレッジ

ソース

コード

記号実行ツール

（CREST）

テスト

データ

市販ツール①

市販ツール②

実行環境：

Windows OS上にVagrantを用いて

構築したLINUX（ubuntu）環境

Vagrant：

開発環境の構築と共有を容易とするツール

Vagrant

仮想化ソフトウェア

（VirtualBox）

仮想マシン

（LINUX）

記号実行ツール

（CREST）

コマンドを実行

仮想マシン内の

_{環境を設定}

仮想マシンを

作成、設定

（参考）Vagrant： https://www.vagrantup.com/

実行環境：

Windows OS

テスト

データ

テスト

データ

13

/ 19

5. 評価結果

 市販ツールの実行結果

市販ツール①

市販ツール②

カバレッジ達成（100%）

9

29

カバレッジ未達（100%未満）

31

11

市販ツール②でカバレッジ未達の関数に対して

記号実行ツールを実行する



関数内で算出される変数を含む条件文

・・・

市販ツール②はモンテカルロ法により、テストデータを生成できるケースあり



変数同士を比較する条件文（市販ツール①のみ）



条件が多い判断文（市販ツール②のみ）

・・・静的解析の原理上可能だが、ツールの仕様制限によりテストデータを生成できない



市販ツール①より、市販ツール②の方が記号実行の対象関数を絞り込める

＜MC/DCカバレッジ達成/未達関数の数＞ 対象関数：40個

＜未達パスの条件＞

14

/ 19

5. 評価結果

 記号実行ツールの実行結果

記号実行ツール

カバレッジ達成（100%）

7

カバレッジ未達（100%未満）

4

記号実行を用いて、MC/DCカバレッジ100%の

テストデータを生成できることを確認した

：

10

T/F

：

if ( ( data1 != 1 )

11

|| ( ( data1 == 1 )

12

&& ( data2 < data3 ) ) {

[MC/DC t/f ] ( data1 != 1 )

[MC/DC t/ ] ( data1 == 1 )

[MC/DC t/f ] ( data2 < data3 )

13

処理;

14

}

：

：

シミュレータ解析画面

_{到達不可のパス}

true

false

true

true

false

false

data1 != 1

data1 == 1

data2 < data3

可読性向上のための冗長なロジックが原因

⇒カバレッジ対象外

実行

MC/DCがOK

MC/DCがNG

＜MC/DCカバレッジ達成/未達関数の数＞ 対象関数：11個

＜カバレッジ未達の原因＞

15

/ 19

［参考］MC/DCカバレッジ結果

関数

MC/DCカバレッジ［%］

No

CCN

市販ツール① 市販ツール② 記号実行ツール

1

3

100

100

-

2

4

0

83

100

3

5

100

100

-

4

5

0

100

-

5

6

60

100

-

6

6

100

100

-

7

6

100

100

-

8

6

100

100

-

9

6

90

100

-

10

7

25

100

-

11

7

100

100

-

12

7

66

100

-

13

7

66

100

-

14

7

100

100

-

15

8

71

100

-

16

8

57

100

17

8

100

86

100

18

9

81

81

※ 93

19

9

0

100

-

20

9

0

62

※ 87

関数

MC/DCカバレッジ［%］

No

CCN

市販ツール① 市販ツール② 記号実行ツール

21

10

66

100

-

22

10

33

100

-

23

10

0

100

-

24

10

44

100

-

25

11

100

100

-

26

11

0

100

-

27

11

80

100

-

28

12

9

100

-

29

13

16

100

-

30

14

53

100

-

31

14

53

96

100

32

14

7

100

-

33

15

22

96

100

34

17

10

58

100

35

17

78

93

※ 93

36

19

27

100

-

37

20

50

94

100

38

20

42

75

※ 91

39

48

4

23

100

40

50

30

100

-

：カバレッジ未達 ※冗長なロジックが原因



ソフトウェアの大部分を占めるCCNが小さい関数は市販ツールでもカバレッジを達成



CCNが大きい関数でも記号実行ツールはカバレッジを達成

市販ツールと記号実行ツールの組合せで、 合理的にテストを実施できる

16

/ 19

6. まとめ

記号実行ツールを用いたテストデータの自動生成

取組み

生成するテストデータのカバレッジ率を高めるために、

MC/DCカバレッジ100%のテストデータ自動生成により、

単体テスト（実装ベーステスト）を効率化する



記号実行ツールを用いることで、可達パスに対する

MC/DCカバレッジ100%のテストデータを生成する

目途付けができた



市販ツールとの併用で、運用方法として有効であることを確認した

実務適用に向けた追加評価と運用方法の検討

今後の課題



記号実行ツールへの置換えを視野に入れた追加評価



開発現場で容易に使える方法の検討と環境整備



ツールの保守方法の検討

目的

17

/ 19

［参考］CREST

 テストドライバ（基本構成）

#include <crest.h> /* CRESTのヘッダをインクルード */

#include <stdio.h>

#include <stdlib.h>

unsigned char In1;

unsigned char In2;

unsigned char Out1;

int main( void ) {

/* テストデータを生成する変数の指定 */

CREST_unsigned_char( In1 );

CREST_unsigned_char( In2 );

/* テスト対象の関数（解析対象のソースコード） */

printf( “%d %d ¥t¥t”, In1, In2 );

TestFunc(); /* テスト対象の関数 */

printf( “%d ¥n”, Out1 );

return EXIT_SUCCESS;

}

/* テスト対象の関数 */

void TestFunc( void ) {

：

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

＜出力結果イメージ（テストデータ）＞

0 145 0

1 0 1

126 255 1

255 152 0

：

1

2

3

4

：

In1

In2

Out1



ヘッダファイルのインクルード



テストデータを生成する変数

の指定

（符号付/なし char, short, long）



テスト対象の関数のコール

（解析対象のソースコード）



テストデータの出力（printf）

期待値（出力変数）

テストデータ（入力変数）

18

/ 19

［参考］CREST

 テストドライバの工夫

：

int main( void ) {

/* テストデータを生成する変数の指定 */

CREST_unsigned_char( In1 ); /* 0 or 1 */

CREST_unsigned_char( In2 );

/* テスト対象の関数（解析対象のソースコード） */

if ( In1 <= 1 ) {

printf( “%d %d ¥t¥t”, In1, In2 );

TestFunc(); /* テスト対象の関数 */

printf( “%d ¥n”, Out1 );

}

return EXIT_SUCCESS;

}

/* テスト対象の関数 */

void TestFunc( void ) {

：

}

：

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27



事前条件を追加

CRESTは型の範囲でテストデータを

生成する

仕様上取り得る値でテストデータを

生成させる仕組みを追加

0 145 0

1 0 1

0 255 1

0 152 0

：

1

2

3

4

：

＜出力結果イメージ（テストデータ）＞

In1

In2

Out1

期待値（出力変数）

テストデータ（入力変数）

19

/ 19

［参考］CREST

 テストデータ生成時の解析方法の選択

CRESTには、幾つかの解析方法が準備されており、

ソフトウェアに合わせて選ぶことができる



-dfs (Bounded Depth First Search) ：主にソルバの性能を高める



-random (Random Search) ：原始的なヒューリスティック など

（例）「-dfs」ではビット演算を解析できず、MC/DCカバレッジ未達となるが、

他の解析方法を用いればカバレッジを達成できる

data1 = (unsigned char)( ( data2 & 0x0000FF00 ) >> 8 );

if ( data1 == 0xE0 ) { 処理; }

1

2

テストドライバや解析方法など、

20

/ 19

参考文献・謝辞



Concolic testing



K. Sen, D. Marinov, and G. Agha, “CUTE: A Concolic Unit Testing Engine for C”, ACM, vol.30, 2005



CREST



CREST, Concolic test generation tool for C,

http://jburnim.github.io/crest/

https://groups.google.com/forum/#!forum/crest-users

(FAQ)



J. Burnim and K. Sen, “Heuristics for Scalable Dynamic Test Generation”,

Automated Software Engineering, 2008. ASE 2008. 23rd IEEEIACM International Conference on



Moonzoo Kim, “CREST Tutorial”,

http://swtv.kaist.ac.kr/courses/cs453-fall13/lec12-crest_tutorial.pdf



事例研究



高松宏樹, 佐藤晴彦, 小山聡, 栗原正仁,

“動的記号実行によるメソッドの複雑度を考慮したテストケース自動生成”,

情報処理学会研究報告, ソフトウェア工学研究会報告, 2014(27)



植月 啓次, “ソフトウェアの実装情報に基づく決定表を活用した論理検証手法”,

ソフトウェアシンポジウム2013, 12, 2013



岸本 渉, “安全系組込ソフトウェア開発におけるユニットテストの効率化”, ソフトウェアシンポジウム2015, C-14-2, 2015



松尾谷 徹, 増田 聡, 湯本 剛, 植月 啓次, 津田 和彦,

“Concolic Testing を活用した実装ベースの回帰テスト 人手によるテストケース設計の全廃”,

ソフトウェアシンポジウム2015, C-14-2, 2015

謝辞：

本取組において、社内の研修などを通じ、ご指導・ご協力いただいた方々に感謝いたします

22

/ 19

［参考］記号実行

入力変数をx, y, zの時、それぞれに与えられる値をX, Y, Z（記号）とする。

制約式は以下となり、X, Y, Z に具体的な値を与えてテストデータを生成する。

① ( X = 0 ) ∧ ( Y > 1 ) ∧ ( Z = 1 )

② ( X = 0 ) ∧ ( Y > 1 ) ∧ ( Z != 1 )

③ ( X = 0 ) ∧ ( Y <= 1 )

④ ( X != 0 )

int TestFunc( int x, int y, int z ) {

int ans;

if (

x

== 0 ) {

ans = 1;

if (

y

> 1 &&

z

== 1 ) {

ans = 2;

}

}

else {

ans = 0;

}

return ans;

}

1

2

3

4

5

6

7

8

9

10

11

12

13

false

x

== 0

y

> 1

z

== 1

true

false

false

true

true

①

②

③

④