
%
%  $Description: Author guidelines and sample document in LaTeX 2.09$ 
%
%  $Author: ienne $
%  $Date: 1995/09/15 15:20:59 $
%  $Revision: 1.4 $
%

\documentclass[times, 10pt,twocolumn]{article} 
\usepackage{latex8}
\usepackage{alltt,cite,bar,graphicx, times,url, xspace}
\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{smallnums}{
   \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{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\tion}[1]{\S\ref{sec:#1}}

%\documentstyle[times,art10,twocolumn,latex8]{article}

%------------------------------------------------------------------------- 
% take the % away on next line to produce the final camera-ready version 

%------------------------------------------------------------------------- 
\begin{document}

\title{
Notes
\thanks{The research described in this paper
was carried out at the NASA-Ames Research Center and
West Virginia University under
contracts with NASA.
Reference herein to any specific commercial product, process, or service
by trademark, manufacturer, or otherwise, does not constitute or imply
its endorsement by the United States Government.
}
}

\author{
Yue Jiang
\and
Bojan Cukic
\and
Tim Menzies\\
Lane CS \& EE\\
West Virginia University\\
\small{\url{tim@menzies.us}}
}

\maketitle
\Section{About the Features}
\subsection{Related Work}
Many researchers use static features from software artifacts to guide software quality
predictions  (see
\cite{halstead77,mccabe76,nikora03,chapman02,me04g,polyspace,nagappan05,hall00,nikora03,conf/icse/NagappanB05a,khoshgoftaar01,conf/ictai/TangK04,journals/ese/KhoshgoftaarS03,me03a,me02e,me03k,me03q,porter90,tiang95,khoshgoftaar99,srinivasan95}).
V\&V textbooks(\cite{rakitin01}) advise using
them to decide modules are worthy
of manual inspections.  For several  years, the first author worked
on-site at the NASA software Independent Verification and Validation
facility and he knows of several large government software contractors
that won't review software modules {\em unless} tools like McCabe
predict that they are fault prone.  

The use of such measures is controversial.
Fenton offers an example where {\em the
same} functionality is achieved using {\em different} programming
language constructs resulting in {\em different} static measurements
for that module~\cite{fenton97}.  Fenton uses this example to argue
the uselessness of static code attributes. 
Fenton~\&~Pfleeger
note that the main McCabe's attribute (cyclomatic complexity, or
$v(g)$) is highly correlated with lines of code~\cite{fenton97}. Also,
Shepperd~\&~Ince remarks that ``for a large class of software
it(cyclomatic complexity) is no more than a proxy for, and in many
cases out performed by, lines of code''~\cite{shepperd94}.

In summary,
Shepperd~\&~Ince and Fenton~\&~Pfleeger
are arguing against the use of {\em single} features to predict for
defects. Further, they reject other commonly used indicators since they are
all highly correlated and, so they argue, just as uninformative.

When single features fail, {\em combinations} can succeed. This paper argues
that {\em combinations} of static features extracted from requirements  and code
can be exceptionally good predictors for defects. 

In previous work~\cite{me07c}, we have
compared defect prediction using single code features versus more complex
schemes that accepted evidence from  multiple features. 
$\Delta$ is the median {\em difference} in probability of detection
when the {\em same}
data was passed to 
{\em different} learners (so $\Delta$ has the range $-100\% \le \Delta \le 100\%$).  
\bi
\item Rules based on single features performed worse than those based on feature combinations
($\Delta= - 16.7$\%);
\item Bayesian methods that combined evidence from  multiple features performed much better
($\Delta = +52.4$\%).
\ei
$\Delta$ is a relative measure of performance,
Measured in absolute terms, these Bayesian combinations achieved mean probabilities of detection
and false alarm of $\{pd,pf\}= \{71,25\}$ (over eight data sets in a 10-way cross-validation experiment).
It is insightful to compare these results to industrial averages:
\bi
\item
A panel at {\em IEEE Metrics
2002}~\cite{shu02} concluded that manual software  reviews can find ${\approx}60\%$ 
of defects\footnote{That panel supported neither Fagan
claim~\cite{fagan86} that inspections can find 95\% of defects before
testing or Shull's claim that specialized directed inspection methods
can catch 35\% more defects that other
methods~\cite{shull00a}.}  
\item
Raffo reports that
industrial review methods have \mbox{$pd=TR(35, 50,
65)\%$}\footnote{ $TR(a,b,c)$ is a triangular distribution with
min/mode/max of $a,b,c$.}
 for full Fagan inspections~\cite{fagan76} to
\mbox{$pd=TR(13, 21, 30)\%$} for less-structured inspections.
\ei
Note that:
\bi
\item  Contrary to the pessimism of
Shepperd~\&~Ince and Fenton~\&~Pfleeger, static measures are both 
useful for predicting defects and do better than certain standard industrial practices.
\item
There is still considerable room for improvement such as lower $pf$s and higher $pd$s. 
\ei
One way to improve the $<pd,pf>$ results is to define better combination methods for partial
indicators from the available features.
{\em Sampling} methods
explore different combinations of different types of static features. For example, code measures could
be combined with measures taken from early life cycle requirements documents.

An alternative to {\em sampling} methods are {\em algorithmic} methods
such as the Bayesian approach described above
or
{\em ensemble}  learners that auto-generate a set of experts which
``vote'' on
new problems.  Ensembles can beat Bayesian methods for the same reason that 
Bayesian methods beats rules learned from single features.
\bi
\item
Single features are not strong indicators for defects;
\item
Combination methods do better since they combine partial indicators from multiple features;
\item
Ensembles do the same but auto-generate more combinations of partial indicators;
\ei

A popular ensemble method is the
the AdaBoost
algorithm~\cite{FreSch97} that builds an ensemble of detectors 1,2,3,...
where detector $i$ is built from problems that were misclassified
by detectors $1,2,..,i-1$.  Increasing the size
of the ensemble decreases error~\cite{FreSch97}. 
Prior experiments on boosting for defect detection
have not demonstrate significant
improvement over simpler methods~\cite{khos02z,ma07}.

Another ensemble method is random forests (XXX reference).
Random forests are decision tree learners that
build $N$ trees using randomly selected subsets of the attributes. New examples are assigned a classification
if $M of N$ of the trees ``vote'' for that classification. 
Prior experiments have shown that random forests can beat boosting and Bayesian methods for defect
detection~\cite{ma07}.


In this report we combine {\em algorithmic} methods with {\em sampling} methods for defect detection
and show that the combination can defeat either method used separately.

blah blah blab

\Section{Static Features}
\subsection{Code Features}

\begin{figure}[!t] \begin{center} {\footnotesize
\begin{tabular}{l@{~}|l@{~}|l@{~}|c@{~}p{3.9cm}|}\cline{2-5}
%\begin{tabular}{|l|l|lcl|}\hline
%\multicolumn{3}{|c}{grouping}&\multicolumn{2}{|c|}{measure}\\\hline
		&\multicolumn{2}{l}{m = Mccabe }       &$v(g)$
		&cyclomatic\_complexity  \\
	&        \multicolumn{2}{l}{~}                                 &
	$iv(G)$&design\_complexity\\ &         \multicolumn{2}{l}{~}
	& $ev(G)$&essential\_complexity\\\cline{2-5} &locs&{loc}
	&   &loc\_total (one line = one count\\\cline{3-5} &
	&loc(other)                      &   &loc\_blank           \\
	&       &                                &
	&loc\_code\_and\_comment\\ &       &
	&   &loc\_comments         \\ &        &
	&   &loc\_executable\\ &       &                                &
	&number\_of\_lines (opening to closing brackets)\\\cline{2-5}
	&{Halstead} & h& $N_1$ &num\_operators\\ &       &
	&$N_2$ &num\_operands \\ &       &
	&$\mu_1$ &num\_unique\_operators\\ &       &
	&$\mu_2$ &num\_unique\_operands\\\cline{3-5} &       &  {
	H}&$N$  &length: $N= N_1 + N_2$\\ &       &
	& $V$  &volume: $V=N * log_{2}\mu$\\ &       &
	& $L$  &level: $L=V^*/V$ where\newline
	$V^*=(2+\mu{_2}^{*})log_{2}(2+\mu{_2}^{*})$\\ &       &
	& $D$  &difficulty: $D=1/L$\\ &       &
	&$I$   &content: $I=\hat{L}*V$ where\newline
	$\hat{L}=\frac{2}{\mu_{1}} * \frac{\mu_{2}}{N_{2}}$ \\ &
	&                                 & $E$  &effort: $E=V/\hat{L}$\\
	&       &                                 & $B$  &error\_est\\
	&       &                                 & $T$  &prog\_time:
	$T=E/18$ seconds\\\cline{2-5} &       \multicolumn{2}{l}{misc
	= Miscellaneous}                                  &&branch\_count\\
	&       \multicolumn{2}{l}{~}
	&&call\_pairs\\ &       \multicolumn{2}{l}{~}
	&&condition\_count\\ &       \multicolumn{2}{l}{~}
	&&decision\_count\\ &       \multicolumn{2}{l}{~}
	&&decision\_density\\ &       \multicolumn{2}{l}{~}
	&&design\_density\\ &       \multicolumn{2}{l}{~}
	&&edge\_count\\ &       \multicolumn{2}{l}{~}
	&&global\_data\_complexity\\ &       \multicolumn{2}{l}{~}
	&&global\_data\_density\\ &       \multicolumn{2}{l}{~}
	&&maintenance\_severity\\ &       \multicolumn{2}{l}{~}
	&&modified\_condition\_count\\ &       \multicolumn{2}{l}{~}
	&&multiple\_condition\_count\\ &       \multicolumn{2}{l}{~}
	&&node\_count\\ &       \multicolumn{2}{l}{~}
	&&normalized\_cyclomatic\_complexity\\ &
	\multicolumn{2}{l}{~}
	&&parameter\_count\\ &       \multicolumn{2}{l}{~}
	&&pathological\_complexity\\ &       \multicolumn{2}{l}{~}
	&&percent\_comments\\\cline{2-5}
\end{tabular}} \end{center} \caption{Attributes used in this study.
}\label{fig:attr} \end{figure} % XXX need introduction words saying

The Halstead attributes were derived by Maurice Halstead in 1977. He
argued that modules
that are hard to read are more likely to be fault
prone~\cite{halstead77}. Halstead estimates reading complexity by
counting the number of operators and operands in a module: see the
$h$ attributes of \fig{attr}.  These three raw $h$  Halstead
attributes were 
then used to compute the $H$: the eight derived Halstead attributes
using the equations shown in
\fig{attr}.  In between the raw and derived Halstead attributes are
certain intermediaries (which do not appear in the MDP data sets);
 \bi
\item
$\mu= \mu_1 + \mu_2$;
\item
minimum operator count: $\mu_1^*=2$;
\item
$\mu_2^*$  is the minimum operand count and equals the number of module parameters.
\ei

%XXXX conclusion. Halstead and McCabe very odd 1970s. sureyin the 21st cenyru we can do better

An alternative to the Halstead attributes are the complexity attributes proposed by Thomas McCabe in 1976.
Unlike Halstead,
McCabe
 argued that the complexity of
pathways {\em between} module symbols are more insightful than just a count of the symbols~\cite{mccabe76}. 
The first three lines of \fig{attr}
shows McCabe three
main attributes for this pathway complexity. These are defined as follows.
A
module is said to have a {\em flow graph}; i.e. a directed graph where each node corresponds to a
program statement, and each arc indicates the flow of control from
one statement to another.
The {\em cyclomatic complexity} of a module is   $v(G) = e - n +
2$ where $G$ is a program's flow graph, $e$ is the number of arcs in
the flow graph, and $n$ is the number of nodes in the
flow graph~\cite{fenton96}.
The {\em essential complexity}, ($ev(G)$) or a module is  the extent to which a
flow graph can be ``reduced'' by decomposing all the subflowgraphs
of $G$ that are {\em D-structured primes}
(also sometimes referred to as ``proper one-entry
one-exit subflowgraphs''~\cite{fenton96}). $ev(G) = v(G) - m$ where $m$ is the number of subflowgraphs of
$G$ that are D-structured primes~\cite{fenton96}.
Finally, the
{\em design complexity}   ($iv(G)$) of a module is the cyclomatic complexity of a
module's reduced flow graph.


At the end of \fig{attr} are a set of {\em misc} attributes that are less well-defined than lines of code attributes
or the Halstead and McCabe attributes. 
The meaning of these attributes is 
   poorly documented in the MDP database. Indeed,
   they seem to be values generated from some unknown tool set that
   was available at the time of uploading the data into the MDP.
Since there are difficulties in reproducing these attributes at other sites, an argument could be made
for trying different {\em sampling} combinations of (e.g.) no {\em misc} attributes, just misc,
just Halstead+misc, etc.

\subsection{Static Requirements Features}

The ARM ({\em automated analysis of requirements}) tool~\cite{wilson97} was an experiment in lightweight parsing of requirements
documents. Rather that tackle the complexities of full-blown natural language, the ARM research explored
what could be easily automatically identified.

The ARM work resulted in an automatic parser and some threshold guidelines for when to be concerned about a document\footnote{\url{http://satc.gsfc.nasa.gov/tools/arm/ }}.
Since our learners can automatically generate such thresholds, we ignored the ARM thresholds and just used the results
of that parser.

The ARM parser reports information at the level of either
individual specifications {\em or} the whole document.
Specification statements have the following features:
\bi
\item
{\em Imperatives} (something that must be provided) contain the phrases
``shall'',
``must'' or ``must not'',
``is required to'',
``are applicable'',
``responsible for'',
``will'', or
``should''.
\item
{\em Continuances} (connections between statements)
contain the phrases
``as follows'', ``following'', ``listed'', ``in particular'', or``support''.
\item
{\em Directives} (to supporting illustrations)
contain the phrases
``figure'', ``table'', ``for example'', ``note''.
\item
{\em Options} (giving  the developer latitude in satisfying the specification statement)
contain the phrases
``can'', ``may'', ``optionally''.
\item
{\em Weak Phrases} (causing uncertainty, leave room for multiple interpretations)
contain the phrases
``adequate'',  ``as a minimum'', ``as appropriate'', ``be able to'',
 ``be capable'', ``but not limited to'', ``capability of'', ``capability to'', `` effective'', ``if practical'', ``normal'',
`` provide for'',  ``timely'', and ``tbd''.
\ei
Other features relate to the entire document:
\bi
\item
{\em Size} reports
total number of  lines of text, imperatives, subjects of specification statements.
\item
{\em
Text Structure}  reports the number of statement identifiers found at each hierarchical level of the requirements document. 
The detailed NASA documents can go down to nine levels
and
high level requirements documents rarely have more than four.
\item
{\em 
Specification Depth Specification:}
 the number of imperatives found at each of the document's levels of text structure. 
These numbers also include the count of lower level list items that are introduced at a higher level by an imperative and followed by a continuance.
\item
Four {\em 
readability Statistics Readability Statistics} indicating  how easily an adult can read and understand the requirements document:
\be
\item
The {\em Flesch Reading Ease} index:  based on the average number of syllables per word and the average number of words per sentence
. Scores range from 0 to 100 with standard writing averaging 60 - 70. In theory,
the higher the score, the greater the number of people who can readily understand the document. 
\item
The {\em Flesch-Kincaid Grade Level} index:  also based on the average number of syllables per word and the average number of words per sentence. The score in this case indicates a grade-school level. A score of 8.0 for example, means that an eighth grader would understand the document. Standard writing averages seventh to eighth grade. 
\item
The {\em Coleman-Liau Grade Level} index: uses word length in characters and sentence length in words to determine grade level. 
\item
The {\em Bormuth Grade Level} index: also  word length in characters and sentence length in words to determine a grade level.
\ee
\ei

\bibliographystyle{latex8}
\bibliography{refs}

\end{document}

