解説: 飛行機事故とソフトウェアDOE

先日の投稿「解説: 飛行機事故とセンサー・フィードバックの分布」の続きです。事故の調査が進み、センサーの異常だけではなく、ソフトウェア不具合の可能性も分かってきたので、続きを書いてみようと思いました。

一般的に(今回の事故やボーイングの開発部隊とは関係なく)、ハードウェアとソフトウェアから成る複雑なシステムでは、ハードウェアの異常に起因したり、システムの特殊な使い方に起因したりするような、外部要因の組み合わせによるソフトウェアの不具合は良くあることです。

しかしソフトウェア開発のおいては、ソフトウェア内部のデバッグだけでも大変な作業なので、さらに考えられ得るすべての外部要因を組み合せてテストすることは至難の業です。また通常は考えられないような外部要因が発生することも実際にはあるので、ハードウェアとソフトウェアから成る複雑なシステムを完全にテストで検証することは不可能でしょう。

テストがソフトウェア不具合を検出できる確率

ではボーイング737 Max8の場合、センサー・フィードバックが異常を示した時にソフトウェアが正しく動くかどうかを、テストで検証していなかったのでしょうか。

もちろんボーイングはテストをしていたと思いますし、特に安全基準が厳しい飛行機ならば尚更のこと、国際的に定められた認証を得るためにもテストは行っていたはずです。

ではなぜこのような事故が起きたのかと言うと、恐らく他の様々な条件が複雑に組み合わさり、たまたまある外部要因の組み合せがソフトウェアの動作不良に結びついたのではないでしょうか。事実、事故の調査報告も、センサー・フィードバックの故障、ソフトウェアの制御、それに反応するパイロットの操縦/操作の関連に言及しています。

そこで思い出したのが、NIST(National Institute of Standards and Technology)Rich Kuhn氏の調査レポートです。

Kuhn氏によれば、医療装置やブラウザー、サーバー、NASAのデータベース、ネットワーク・セキュリティー・システムなどのソフトウェアを調査した結果、

  • 1つのパラメータ設定を変えて行ったテストがソフトウェア不具合を検出することができる確率は、18%から65%
  • 2つのパラメータ設定の組み合せを変えて行ったテストがソフトウェア不具合を検出することができる確率は、65%から97%
  • 3つのパラメータ設定の組み合せを変えて行ったテストがソフトウェア不具合を検出することができる確率は、89%からほぼ100%
  • 4つのパラメータ設定の組み合せを変えて行ったテストがソフトウェア不具合をパラメータ検出することができる確率は、96%からほぼ100%
  • 5つのパラメータ設定の組み合せを変えて行ったテストがソフトウェア不具合を検出することができる確率は同じく、96%からほぼ100%
  • 6つのパラメータ設定の組み合せを変えて行ったテストがソフトウェア不具合を検出することができる確率は、ほぼ100%

ということが分かったそうです。

パラメータの組合せ数とソフトウェア異教の検出

このグラフを見て僕は、「累積分布関数(CDF: Cumulative Distribution Function)に似ているな」と思いました。正規規分布の場合、累積確率は1シグマで68.27%、2シグマで95.45%、3シグマで99.73%の確率になるからです。

また、この「シグマ値と組み合わせるソフトウェアのパラメータ数の関連性」を使えば、テストで検証できるソフトウェアの信頼性を計算することができるのではないかと思いました。つまり先の投稿から引用すれば、ボーイング737の飛行信頼性であるシグマレベル5.15を維持するためには、ソフトウェアは6つのパラメータのすべての組み合せをテストする必要があるということです。

正規分布の確率分布図

組み合せテスト(Combinatorial Testing)

興味深いことに、Kuhn氏も同様に、テストでソフトウェアの不具合を100%検出したいのであれば、6つ以上のパラメータのすべての組み合せをテストする必要があると言っています。

一方(一般的に)、ソフトウェア・エンジニアが行っているテストのやり方は、一つずつパラメータの設定を変えながらテストを繰り返す方法です。例えば6つのパラメータ(または6つの機能)があり、それぞれのパラメータ(機能)が3値(-1/0/1)を取るとき、一般的なソフトウェア開発では、それぞれのパラメータ(機能)で3通りのテストしか行いません。つまり18通り(6機能 x 3値)のテストに合格すればテスト完了です。

このようなテストのやり方だと、多くても65%程度の不具合しか検出できません。

もしこの6つのパラメータの組み合せをすべてテストするとなると、その組み合せの数は729通り(3の6乗)になります。すべての組み合せをテストすることは、時間的にもコスト的にもはかなり難しいものがあります。しかし、ほぼ100%、テストで不具合を検出することができるでしょう。

そこで組み合せ数を減らすために、Kuhn氏はペア・アルゴリズムとカバーリング・アレイ・アルゴリズムを用いて、組み合せテスト用のツールを開発しました(ACTS: Automated Combinatorial Testing for Software)。そのツールはNISTサイトから無償で提供されています。

t-way組み合わせテスト

ACTSによるテストケースの削減例

以前、僕は入力パラメータが13もあるソフトウェア機能を開発しました。その時8つのパラメータの組み合せを確認する必要がありました。8つのパラメータのうち、5つのパラメータは2値を、2つのパラメータは4値を、一つのパラメータは3値を取りました。そのためすべてのパラメータの組み合せは1536 (2^5 x 4^2 x 3)通りとなりました。

1536通りのすべてのテストケースを実施することは時間的にもコスト的にも不可能だったので、ACTSを使ってテストケースの削減を行いました。ACTSにパラメータの条件を入れてテストケースを生成したところ、テストケースの数を118にまで減らすことができました。

テストの信頼性を確保しながらテストケースの数を減らすACTSのアルゴリズムの詳細については、ぜひNISTのサイトをご参照ください。

ソフトウェアDOE

さて、この組み合せテスト(Combinatorial Testing)は、ソフトウェアのDOE(Design of Experiments)と言われています。なぜならハードウェアのDOEと同様、入力パラメータの値とその組み合せを計画的に変えながら、出力パラメータの値を記録し、未知のシステムを理解しようとするからです。

しかし、ハードウェアDOEとソフトウェアDOEにはいくつかの違いがあります。

ハードウェアDOEの場合は、ハードウェア・システムをブラックボックスとして扱い、入力パラメータ値の組み合わせと記録した出力パラメータ値から数値モデルを組み立てることを目的としています。つまり数値モデルを使って、ブラックボックスのハードウェア・システムを理解することを目的としています。

一方ソフトウェアDOEの場合は、ソフトウェアの作ったのは自分たちなのでソフトウェアの中身は分かっていますし、ソフトウェア自体がモデルなので、ソフトウェア・システムの数値モデルを作る必要はありません。しかし、どんな入力パラメータ値やどんな入力パラメータ値の組み合わせが不具合を起こすのかが分かりません(グレーボックス)。

そこで不具合を起こす入力パラメータ値の組み合わせを知るために、DOEを使います。 ACTSは、入力パラメータ値の組み合わせを計画的に作ることができるので、ソフトウェアDOEに最適のツールと言えそうです。

ボーイングはソフトウェアDOEを使って組み合わせテストを行ったのでしょうか。僕はきっと組み合せテストをやったと思います。しかし、きっと想定外の外部要因があったのかもしれません。あくまでも想像の域を出ませんが。