\documentclass[twocolumn,global]{svjour}
\usepackage{wrapfig,graphicx,cite,url,../../tex/fancyheadings}
%\usepackage[para,symbol*]{footmisc}
%\setfnsymbol{lamport}
\usepackage{amssymb,times}

\newcommand{\epsorpdf}{pdf}





\footrulewidth 0.0pt\headrulewidth 0.1pt
\lhead{}\rhead{}\chead{}\rfoot{}\lfoot{}\cfoot{}
\lhead{{\scriptsize 
HICSS-38\\
January 3-6, 2005\\
Hilton Waikoloa Village\\
Big Island, Hawaii\\ Home
page:
\protect\url{http://www.hicss.hawaii.edu/}\\
Download this paper at
\url{http://menzies.us/pdf/05whatisivv.pdf}.\\
WP ref: wp/05/hicss/hicss.tex\\
\date{\today}.}}
\rhead{\includegraphics[width=3cm]{HICSS38.jpg}}



%\newcommand{\epsorpdf}{eps}

\newenvironment{smallitem}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{itemize}
   \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{itemize}}

\newenvironment{smallenum}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{enumerate}
  \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{enumerate}}


 \newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
 \newcommand{\bi}{\begin{smallitem}}
\newcommand{\ei}{\end{smallitem}}
 \newcommand{\be}{\begin{smallenum}}
\newcommand{\ee}{\end{smallenum}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\tion}[1]{\S\ref{sec:#1}}

%\topmargin -3cm

\begin{document}
\title{
IV\&V is not V\&V so how does that change things?
\thanks{
This research was conducted at
Portland State University and the NASA Software IV\&V Facility, Fairmont, West Virginia,
under various
NASA contracts including the  NASA Office of Safety and Mission
Assurance under the Software Assurance Research Program led by the
NASA IV\&V Facility. 
Reference herein to
any specific commercial product, process, or service by trade name,
trademark, manufacturer, or otherwise, does not constitute or imply
its endorsement by the United States Government.}}
\author{Tim Menzies$^\ddag$, Robert (Mike) Chapman$^\star$}
\institute{$^\ddag$ Computer Science, Portland State 
University, USA
\url{tim@barmag.net} URL: \url{http://barmag.net}\\
$^\star$ Galaxy Global Corporation
\url{Robert.M.Chapman@ivv.nasa.gov}
}



\maketitle \thispagestyle{fancy}
\pagestyle{plain}

\begin{abstract}
IV\&V is {\em not} V\&V. IV\&V activities are opportunistic
stochastic samples of project artifacts, some of which may be
incomplete and imprecisely described.  The mathematics of systems
shows that such sampling can be surprisingly effective.
The best tools for IV\&V understands how to perform
cost-effective  sampling,
and can alert us when that sampling process is incomplete
and needs to be repeated.
\end{abstract}
\tableofcontents
\section{Introduction}

In V\&V, developers assess their own code.  In IV\&V, the developer's
code is assessed by someone else.  

We need to better understand what is unique
about IV\&V. As more and more software development
goes off-shore, IV\&V will be become more frequent as 
(e.g.) American-based companies strive to oversee software developed
at other site.

NASA in particular needs to understand IV\&V better.  A large network
of contractors build NASA systems yet if any of those systems fail,
the general public blames ``NASA'' and not ``contractor XYZ''.  Such
failures severely damage the prestige of the agency and its ability to
collect funding for future endeavors.  Hence, it is vital the agency
as a whole institutes a sampling method for all those contractor
systems.  This sampling method can only be heuristic since a complete
sampling policy would be prohibitively expensive.  For software, the
current sampling policy is managed by the Fairmont software IV\&V
team.

Despite this growing dependency on IV\&V, we don't see in the
literature a recognition of the essential differences between V\&V and
IV\&V. For example, while the formal methods community
improve their ability to automatically find how systems
can violate global temporal constraints, we  would
classify those techniques as {\em V\&V} not {\em IV\&V}
since they require detailed knowledge of the system.
As we shall see, my characterization of IV\&V is software
assessment {\em despite} a poverty of data about this system.


Much of work is empirical and empirical research needs data. The data used
for the case study at the end of this paper is all public domain
and is freely available at 
the NASA Metrics
Data Program web site (see \fig{mdp}).

\begin{figure}[!b]
\begin{center}
\includegraphics[width=2.5in]{mdp.png}
\end{center}
\caption{The MDP data 
repository.\protect\url{http://mdp.ivv.nasa.gov}.}\label{fig:mdp}
\end{figure}

The rest of this paper is structured as follows.
After some notes on the {\em data drought}, we propose
a novel model of IV\&V. This is followed by some notes
on the mathematics of probing a system and some empirical
and theoretical results suggesting that the internals
of a program may be surprisingly simple. That maths,
and those results, has inspired a suite of new IV\&V tools.
V\&V 
teams need {\em in-depth} tools that seek (say) six sigma certification
of a system. Our new IV\&V tools are different. They are not in-depth
tools; rather, they are {\em in-breadth} tools that try to survey a
wide-sample of behaviors in a system in a cost-effect manner.  

\section{The Data Drought}

We base this paper on 
our  time at NASA's
IV\&V group.
Since last century, we have worked
  or with NASA's IV\&V team 
in Fairmont West Virginia.
In that role, we watched numerous attempts
to build rigorous work-breakdown structures (WBSs)
of IV\&V. We came to believe that traditional
{\em prescriptive} 
structures (e.g. IEEE8012) were inappropriate
to {\em describe} IV\&V. 
For one thing,
we could not
even assess the value of those WBS, for
 reasons
that are insightful to the process of IV\&V.
IEEE8012 lists dozens of activities and we
could only ever find data on a few of them.

This {\em data drought} was a persistent problem.
V\&V teams interact with local developers while they are
actively working on some sub-system. IV\&V teams,
on the other hand, interact with remote developers
who may have moved on to other tasks. Hence, by definition,
V\&V can access more information more quickly that an
IV\&V team. An accurate model of IV\&V must therefore
work despite not having full access to all details of a project.

\section{A Model of IV\&V}

Since we couldn't use some IEEE8012-variant to 
describe IV\&V, we turned to a  more opportunistic model.
My preferred model is a
{\em stochastic} and 
{\em opportunistic} manner.
In this model, an {\em
IV\&V agent}
gets sent some {\em randomly selected project artifacts}.
The agent
is required to perform some 
{\em value-added analysis} on the artifact.



Our IV\&V agent faces three challenges. Firstly, the skills
and experience of an IV\&V agent may vary wildly.
For example,  
rarely does a IV\&V agent
have detailed and
 expert knowledge about the domain
of the system.

Secondly, IV\&V is usual a resource-bound activity
(e.g. 5\% if the total system cost).
Hence, our IV\&V must works under strict budgetary constraints.

Thirdly, the artifacts are documented
to a varying standard and so, in the usual case, they are
{\em not} unambiguous;
{\em not} complete;
{\em not} consistent;
and, {\em not}  up-to-date with latest changes to a project.
Our agent therefore has to work in an opportunistic manner:
\bi \item Applies whatever tools\footnote{Here
``tool'' means either some automatic process or
some manual technique such as manual inspection.} they have
experience; \ldots
\item \ldots to whatever artifacts they have from
the projects; \ldots
\item \ldots to
generates a list of {\em
anomalies} that
requires further exploration.  
\ei
The nature of those
anomalies and feedback from the project determines
what happens next. For example, the project could offer
new information that demonstrates that the anomalies are
not an important issue. Alternatively, the project may
reject the anomalies as unimportant in which case the IV\&V agent
has to apply other methods to confirm or deny that the
anomalies indicate that some rework is required.

Hence IV\&V  can't be prescribed
in some one-size-fits-all process document (e.g. some
IEEE8012-variant).  
IV\&V should never be routine. 
Our IV\&V agents should never congratulate themselves
for completing a checklist.
Rather, IV\&V should be
all about the surprise,
the exceptional, and the hunt
for real errors within the space of detected anomalies.


Can we trust such a surprise-driven 
opportunistic and stochastic
process to assure that the system
is being developed properly, and that the right system is being
developed or acquired? 
The answer is ``No''
and anyone who says otherwise
does not understand the mathematics of probing a system.

\section{Mathematics of Probing}


Consider a system containing $V$ variables with
$S$ assignments  may require one test for each combination of
assignments; i.e. $\#tests\;=\;N=\;S^V$.
For example, consider  one sample of fielded expert systems 
in which  knowledge bases were found to
contain between 55 and 510 
``literals''~\cite{preece92}. Literals offer two
assignments for each proposition: true or false; i.e. $S=2$ and
$V$ is half the number of literals. Assuming:
\bi
\item
It takes one
minute to consider each test result (which is a gross
underestimate), and
\item
The effective working year is 225
six hour days,
\ei
then a test of those sampled systems would take
between 29 years and $10^{70}$ years (a time longer than the age
of this universe).

For another example consider how a {\em linear} increase in the
confidence $C$ that we have found all defects can take {\em
exponentially} more effort.  For one-in-a-thousand detects, moving $C$
from 90\% to 98\% takes 2301 to 3910 black box probes (respectively)\footnote{To see that, recall that a randomly selected input to a program will
find a fault with probability $x$.  After $N$ random black-box tests,
the chances of the inputs not revealing any fault is $(1-x)^N$. Hence,
the chances $C$ of seeing the fault is $1-(1-x)^N$ which can be
rearranged to $N(C,x)=\frac{log(1 - C)}{log(1-x)}$. For example,
$N(0.90,10^{-3})=2301$ \cite{voas95}.}.
That is, increasing $C$ by just
under 10\% requires nearly double the tests.


\section{So, is IV\&V  Possible?}

Given such a large space of possibilities, how can we assure that any
system behaves as expected over the space of its possible states?  The
answer is that most systems contain far fewer than $S^{X+Y}$ reachable
states.  

A lower bound on the number of internal states of a system is
the number of states of the input variables. This lower bound may be
very small indeed.  For example, Avritzer et.al. \cite{avri96} studied
the 857 different inputs seen in 355 days operation of an expert
system.  Massive overlap existed between these input sets. On average,
the overlap between two randomly selected inputs was 52.9\%. Further,
a simple algorithm found that 26 carefully selected inputs covered
99\% of the other inputs while 53 carefully selected inputs covered
99.9\% of the other inputs.


More generally, studies on the {\em operational profile} of a
program's input parameters suggest that the input space of a program
may be be particularly complex or large.  \fig{pasquini1} shows a
study where the original operational profile $OPe$ was compared to
three profiles containing an increasing number of errors. The mutants
were called (in order of increasing errors) $OP1,OP2,OP3$. The
inaccuracies in the operational profiles were very apparent after a
small number of tests. However, above 100 tests randomly selected from
each profile, the errors of the different profiles converged.


\begin{figure}
\begin{center}
\includegraphics[width=2in]{pasquini.jpg}
\end{center}
\caption{Reliability-growth models an
operational profile errors. Hand-translated
from~\protect\cite{pasquini96}.}\label{fig:pasquini1}
\end{figure}
Druzdel offers a simple model that explains
why there are so few internal reachable states~\cite{druzdel94}.
If software has $n$ variables, each with its own
assignment probability distribution of $p_i$, then the probability
that a system will fall into a particular state is
$p=p_1p_2p_3...p_n=\prod^n_{i=1} p_i$.
By taking logs of both sides, this equation becomes
\[
\mbox{ln}~p = \mbox{ln}\prod^n_{i=1}p_i=\sum^n_{i=1}\mbox{ln}~p_i
\]
The asymptotic behavior of such a sum of random variables
is addressed by the central limit theorem.
In the case
where we know very little about software, $p_i$ is uniform and many
states are possible. However, the {\em more} we know about a system
the
more varied are individual distributions.
Given
enough variance
in the individual priors and conditional probabilities or
$p_i$, then the expected case is that frequency with which
we reach states will exhibit a
log-normal distribution; i.e. a small fraction of states can be
expected to cover a large portion of the total probability space; and
the remaining states have practically negligible probability.  

\begin{figure}
\begin{center}
\includegraphics[width=1.8in]{stats.pdf}\\
\includegraphics[width=1.8in]{dp.pdf}\\
\includegraphics[width=1.8in]{le.pdf}
\end{center}
\caption{Log-normal state counts.}\label{fig:stats}
\end{figure}
Druzdel found a log-normal distribution in the
frequency of reached states within one system he instrumented: see
{\em Druzdel model} of \fig{stats}. 
One state was seen 54\% of the time;
ten more states were seen 23\% of time; the 48 most frequent
states were seen 91\% of the time; the remaining 525,263 states
occurred with frequencies ranging over 20 orders of magnitude.

Similar analytical results have
been developed independently by D'ambriso~\cite{dambrosio93} and
ourselves~\cite{me99q,me00b} (our method resulted in the same
log-normal distribution but did so via a far more complicated
analysis).  
The Druzdel and D'ambriso results  prompted us
to instrument certain formal
models that we are studying.  As seen in
\fig{stats}, a log-normal distribution of the reached states was seen
in the {\em dining philosophers} and {\em leader election} models.
The two most reached
states were seen 
in 31\% and 29\% of the time;
the ten most reached states were seen 78\% of
the time.
One state was seen 62\% of the time;
the top 50 states appeared 72\% of the time.

\section{IV\&V Tools}
 
The above line of reasoning has motivated the
development of a new suite of IV\&V tools:
LURCH, TAR3 and ONION.
These are IV\&V tools; i.e.
they search for the features that the V\&V team
might of missed. Since they must work in data-starved domains, we
assess these tools on traditional means {\em as well as} how 
well they perform on minimal data. For example, LURCH
is a rapid Monte Carlo method for formal models
where some of the details of the models are 
unknown~\cite{owen03a}. 
LURCH treats such models as a random
distribution of the space
of many models. This space
is rapidly sampled and consistent subsets
of each one is generated. 

One advantage of LURCH's search is that its search
is stochastic. Hence, LURCH can ignore any incorrect preconceptions of system behavior from
the development team, we often used a stochastic search.  
Further, given the
state space clustering results shown above, such a stochastic search
can be remarkably effective at exploring the reachable parts of a
system.
In an observation
consistent with 
Druzdel's results, LURCH can often find as many violations
to system temporal properties than more complete searches,
and do so in a fraction of the memory~\cite{owen03c}.


LURCH generates a lot of Monte Carlo data and TAR3 summarizes that
data using {\em treatment learning}.  TAR3 is a minimal contrast set
learner that returns the difference between Monte Carlo
outputs with different scores~\cite{me03c}. 
Often,
TAR3 often finds {\em minimal contrast sets}
i.e.  a small number of outputs are adequate 
for separating preferred and undesirable outcomes. 
TAR3 extends the Druzdel results
as follows. Druzdel argued that, in the expected case, 
there are a surprisingly small number of reachable states.
The presence of minimal contrast sets that selects for different 
states suggests that there may be a small number of control
variables that select for different states.

ONION has not been reported previously
and is being tested for software defect detection.

\begin{figure}[!t]
\begin{center}
{\scriptsize \begin{tabular}{p{1cm}|p{1.7cm}|p{1.9cm}|p{1.9cm}|}
\multicolumn{2}{c}{}&\multicolumn{2}{c }{module found in defect
tracking log?}\\\cline{3-4} \multicolumn{2}{c|}{}&no&yes\\\cline{2-4}
 ~\newline
 signal&no;\newline i.e. $v(g) < 10$&A = 395\newline$LOC_A = 6816$
 &B = 67\newline$LOC_B = 3182$\\\cline{2-4}
detected?&yes\newline i.e. $v(g) \ge 10$&C = 19\newline$LOC_C =
1816$&D = 39\newline$LOC_D = 7443$\\\cline{2-4}
\end{tabular}
\begin{eqnarray}\nonumber
Acc=&accuracy=&83\%\\\nonumber PF=&Prob.falseAlarm=&5\%\\\nonumber
PD=&Prop.detected=&37\%\\\nonumber
 E=&effort=&48\%
 \end{eqnarray}}
\end{center}\caption{{\small A
ROC sheet assessing the detector $v(g) \ge 10$. Each cell \{A,B,C,D\}
shows the number of modules, and the lines of code associated with
those modules, that fall into each cell of this ROC
sheet.}}\label{fig:roc2}
\end{figure}

\subsection{About ONION}

Standard practice is to apply the best available assessment methods on
the sections of the program that the best available domain knowledge
declares is most critical.  We endorse this approach.  Clearly, the
most critical sections require the best known assessment
methods. However, this focus on certain sections can blind us to
defects in other areas.  
If  most of the assessment effort
explores project artifacts {\em A,B,C,D}, then that leaves
a {\em blind spot} in {\em E,F,G,H,I,...}. 
Therefore, standard practice should be
augmented with a {\em lightweight sampling policy} to explore the rest
of the system.

One common lightweight sample policy is to use defect detectors
learned from static code measures. Data miners input logs of such
measures, plus the logs of known past defects for those
modules, to generate predictors for future defects.
Such detectors
can be assessed
via their {\em accuracy}; i.e.
the number of true negatives and true positives seen
over all events. In terms of the cells $\left<A,B,C,D\right>$ shown 
in \fig{roc2}, accuracy is $Acc=\frac{A+D}{A+B+C+D}$.

Apart from accuracy, several other measures are of interest.
The {\em
probability of detection}, or ``$PD$'', is the ratio of detected
signals, true positives, to all signals; i.e.
$PD=\frac{D}{B+D}$
($PD$ is also called the $recall$
of a detector). Also, the {\em
probability of a false alarm}, or ``$PF$'', is the ratio of
detections when no signal was present to all non-signals: i.e.
$PF=\frac{C}{A+C}$.

Another statistic of interest is the $effort$ associated with a
detector. 
If the detector is triggered, then some further 
assessment procedure must be called.
For the particular static code defect detectors discussed in this paper,
we will assume that this effort is proportional to the lines of
code in the modules.
Under that
assumption, the $effort$ for a detector is what percentage of the
lines of code in a system are selected by a detector; i.e.
$effort=E=\frac{LOC_C+LOC_D}{ LOC_A+LOC_B+ LOC_C+LOC_D}$.

For years, with DiStefano and Chapman and 
Orrego~\cite{me03a,me03k,me03a,me04g}, 
we have strived to
generate detectors have high $PD$s, low $PF$s, and low $effort$. This
ideal state rarely happens.  The only way to make no mistakes (and
achieve a $PF$ of zero) is to do nothing which in turn, means that
nothing will be detected (i.e.  $PD$=0).  Also, the only way to catch
more detects is to make more mistakes (i.e. increasing PD means
increasing PF).  Further, $PD$ and $effort$ are linked: the more
modules that trigger the detector, the higher the $PD$. However,
effort also gets increases.

Standard data miners, built to optimize accuracy, generally generate
detectors with $effort$ higher than $PD$.  Recent results with a novel
rule-covering algorithm called ONION have been more promising. These
results are preliminary but encouraging. ONION divides all numeric
attributes into, say, ten bands. The band with the highest ratio of
$\frac{pd}{effort}$ is then printed to the screen.
All the modules with that band are then removed from the defect
log and the algorithm repeats on the remaining data.  

\begin{figure}
{\scriptsize 
\begin{center}
\begin{tabular}{c|l}
band $B_N$ & range\\\hline
 $B_1$& $0.54 \le I  < 1.73$\\
 $B_2$& $1.00 \le T  < 5.89$\\
 $B_3$& $7.67 \le locCodeAndComment  < 19.19$\\
 $B_4$& $locCodeAndComment \ge  19.19$\\
 $B_5$& $5.15 \le branchCount  < 8.90$\\
 $B_6$& $1.95 \le B  < 4.10$\\
 $B_7$& $569.98 \le  N 5 < 1259.92$\\
 $B_8$& $lOComment \ge 56.38$\\
 $B_9$& $3.07 \le locCodeAndComment  < 7.67$
\end{tabular}
\end{center}}
\caption{Extracted bands}\label{fig:bands}
\end{figure}

The results are the two reports in \fig{bands}
and \fig{nbands}. \fig{bands} shows the order
of the nine bands $B_1 \ldots B_9$
found by ONION in
a particular NASA defect log ($I,T,B,N,etc$) are 
Halstead measures). \fig{nbands}
shows a set of ``what-if''  queries
where a composite
defect detector was built from a disjunction of the first
$N=1,2,\ldots,9$ bands.

\begin{figure}
{\scriptsize 
\begin{center}
\begin{tabular}{c|cccc|c}\hline              
``OR'' the first $N$ bands &   pf&     acc&pd&  effort&  $\frac{pd}{effort}$\\\hline
9  &    18&   80&      55&   33&  1.65\\
  8&   15&   83&     49&   27&  1.80\\
  7&   15&   83&      48&   26&  1.85\\
  6&   14&   83&      44&   22&  2.02\\
  5&   13&   83&      40&   18&  2.29\\
  4&    6&   89&      30&   12&  2.40\\
  3&6&   89&     25&7&  3.45
\end{tabular}
\end{center}}
\caption{Effects of ``OR''-ing together the first $N$ bands}\label{fig:nbands}
\end{figure}

From \fig{nbands}, an IV\&V agent could select a defect
detector that matches the available effort and meets
the desired $effort$ and $pf$. Note that a disjunction of the 
first three bands (shown on the last line of \fig{nbands})
has a $PD$ over three times higher than $effort$. To the best of our
knowledge, no other defect detection method has generated
detectors with $pd \gg effort$.




{\footnotesize
\bibliographystyle{abbrv}
\bibliography{../../refs}}
\end{document}


\end{document}




As the sole entity with the responsibility for IV\&V of all NASA
mission software, the IV\&V Facility is in a unique position to
create and maintain a master repository of software metrics. Under
this charter, the IV\&V Facility reviews requirements, code, and test
results from NASA's most critical projects; hence, many of the
required metrics are collected as a matter of course.  No other
organization has insight into such a broad range of NASA projects.
This affords the IV\&V Facility an unequalled opportunity to research
not only the early life cycle indicators of software quality, but
other topics as well.  Many large corporations have similar software
metrics repositories; however, it is not always in their best
interest to release data or results to the public.  In the case of
the IV\&V Facility, the objective is to improve NASA's mission
software regardless of the source. Once NASA projects agree to
distribution, then sanitized data\footnote{Sanitized data has
project-specific identifiers removed.} would be made available to
NASA, industry, and academia to support software development and
research by other organizations. This is consistent with the IV\&V
Facilities research vision of ``See more, learn more, tell more."



 


