SED navigation bar go to SED home page go to SED publications page go to NIST home page SED Home Page SED Contacts SED Projects SED Products and Publications Search SED Pages


contents     previous     next


3.1.3 Statistics of Software Conformance Testing

Charles Hagwood, Raghu Kacker, James Yen
Statistical Engineering Division, CAML

Lynne Rosenthal, Leonard Gallagher, Paul Black
Software Diagnostics and Conformance Testing Division, ITL

Conformance tests are written to determine if the implementation of a software package complies with agreed upon specifications. The goal is to provide some level of assurance that the requirements imposed by a specification are being met by implementations claiming conformance to that specification.

In this project we provide a confidence interval for the reliability of the NIST CGM (Computer Graphics Metafile) Conformance Test. The CGM International Standard ISO/IEC 8632, is a precise specification of a method of storing pictures on a computer system. The ATA (Air Traffic Association-United, Delta, KLM, Northwest,etc), aerospace companies (Boeing, Aerospatiale), and vendors have agreed on a subset, i.e. a common standard for representing graphical illustrations of plane parts, wiring, etc. The ATA uses the CGM to exchange electronic graphics sent by the aircraft, engine, and equipment manufacturers to the airlines. It is critical that the electronic graphics, exchanged in the CGM format, be processed in an identical manner by the airlines, whatever their origin. The NIST CGM conformance test suite determines whether a CGM interpreter product meets all the requirements specificed in the ATA profile of CGM. Testing implementations of the ATA profile is a means of achieving this goal and ensuring CGM software product reliability.

Ideally, one would like the test suite to include all the means of invoking the functional requirements of the specification at least once. In general, this is impossible due to the explosion of all the possible combinations of input values as well as the combination of requirements. Exhaustive testing is impossible. Therefore, it is important to sample the input space in such a way to obtain an accurate as possible estimate of the software's reliability. The method we choose is to partition the test point space into s disjoint homogeneous subspaces, Ei. Homogeneous in the sense that the input values in each subspace test similar aspects of the specification. We assume that test point space is finite, albeit containing a large number of elements, N. Let Ni denote the number of elements in Ei. Then the conformance test suite is made up of random samples of zero/one random variables, $y_{i,j}, j=1,\ldots, n_i$, from each of these subspaces. That is, ni of the Ni tests points from Ei are selected and tested on the implementation of the software resulting in outcomes yi,j. Define the reliability, 1-p, as the probability that the specifications will be performed correctly. The reliability is calculated from the conformance test data.

Let pi denote the probability that the implementation of the software fails to correctly perform at an arbitrary test point from Ei, then the reliability is given by $1-p=1-\sum^s_{i=1}p_i\frac{N_i}{N}$. The ATA/CGM specification requires that no errors occur. Therefore in order for the implementation to conform none of the test results must fail, i.e. yi,j=0. We find a nondegenerate confidence interval for 1-p given these zero data.

The solution derived is based on solving the optimization problem for pi

\begin{displaymath}Maximize~\sum^s_{i=1}p_i\frac{N_i}{N}~~~~Subject~to:~P_{\bf p}[\bar{y}_1=0,\bar{y}_2=0,\ldots,\bar{y}_s=0]\geq \alpha
\end{displaymath}

and letting the confidence interval be (1-p0,1] where $p_0=\sum^s_{i=1}p_i\frac{N_i}{N}$ at the maximum. The solution is

\begin{displaymath}p_0=1-(\alpha)^{(\sum^s_{i=1}n_i)^{-1}}e^{-D({\bf n}\parallel {\bf N})}.
\end{displaymath}

where $D({\bf n}\parallel {\bf N})$ is the divergence between the vectors ${\bf n}=\{n_i/\sum^s_{i=1}n_i, i=1,\ldots,s\}$ and ${\bf N}=\{N_i/N, i=1,\ldots,s\}$. The above formula provides a general confidence interval for any conformance test with fault intolerant specifications.



contents     previous     next

Date created: 7/20/2001
Last updated: 7/20/2001
Please email comments on this WWW page to sedwww@nist.gov.