
%
%  $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{cite,latex8}
\usepackage{times,url}
\usepackage{graphicx}
\newcommand{\boxplot}[5]{
	\begin{picture}(100,10)
		%\put(0,0){\line(0,1){8}}
		%\put(100,0){\line(0,1){8}}
		\put(#1,4){\line(1,0){#2}}
		\put(#3,4){\circle*{6}}
		\put(#4,4){\line(1,0){#5}}
		\put(50,0){\line(0,1){8}}
	\end{picture}
}
\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}}

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

%------------------------------------------------------------------------- 
% take the % away on next line to produce the final camera-ready version 
\pagestyle{empty}

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

\title{Plateau Effects and Learning Defect Predictors}

\author{Burak Turhan, Ayse Bener\thanks{The research described in this paper was supported by Bo{\u g}azi{\c c}i  University 
research fund under grant number BAP-06HA104 and at West Virginia 
University under grants with NASAs Software Assurance Research Program. 
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.}\\
Dept. of Computer Engineering \\ Bogazici University\\ 
34342 Bebek, Istanbul, Turkey\\ \url{{turhanb , bener}@boun.edu.tr}\\
\and
Tim Menzies\\
Lane Dept. of CS\&EE \\West Virginia University \\ 
Morgantown, WV, USA\\\url{tim@menzies.us}\\}

\maketitle
\thispagestyle{empty}


\input{abstract}
\input{introduction}
\input{related}
%------------------------------------------------------------------------- 
%------------------------------------------------------------------------- 

%------------------------------------------------------------------------- 
\subsection{Regularities in Defect Prediction}

In prior work~\cite{me08d,me08e}, we have used the NASA and SOFTLAB data of \fig{data}
to explore learning defect predcitors using data miners. 
To learn defect predictors we use a Naive Bayes data miner since prior work~\cite{me07b} could not
find a better data miner for learning defect predictors.
In all our experiments, the data was pre-processed as follows:
\bi
\item
The number of features in each data table is not consistent,  we use only the shared attributes in our experiments. 
\item
Previously~\cite{me07b}, 
we have observed that
all the numeric distributions in the \fig{data}
data are exponential in nature. It is therefore useful to apply a  ``log-filter'' that all numerics $N$ with $log(N)$.
This spreads out exponential
curves more evenly across the space from the minimum to maximum values
(to avoid numerical errors with  $ln(0)$,
all numbers under 0.000001 are replaced with  $ln(0.000001)$). 
\ei
\begin{figure}
\scriptsize
\begin{center}
\begin{tabular}{ll|rrr@{.}l}
     &         & (\# modules)         &          &  &\\
source & data &  examples & features  & \multicolumn{2}{c}{\%defective}\\\hline
%pc5  & C++ & 17,186   & 22          & 3&0\\
%mc1  & C++ & 9,466    & 22          & 0&71\\
%pc2  & C++ & 5,589    & 22         & 0&41 \\
%pc3  & C++ & 1,563    & 22          & 10&23\\
%pc4  & C & 1,458    & 22          & 12&2\\
NASA & pc1   & 1,109    & 22          & 6&94\\
NASA & kc1  & 845      & 22          & 15&45\\
NASA & kc2  & 522      & 22          & 20&49\\
NASA & cm1   & 498      & 22          & 9&83\\
NASA & kc3  &  458      & 22          & 9&38\\
NASA & mw1  &  403      & 22          & 7&69\\
NASA & mc2  & 61      & 22          & 32&29\\
SOFTLAB & ar3 & 63 & 29 & 12&70\\
SOFTLAB & ar4 &  107 & 29 & 18&69\\
SOFTLAB & ar5 &  36 & 29 & 22&22\\
OPEN SOURCE. & cav91 &  1169 &   26 & 0&20\\
OPEN SOURCE. & gcc &  116 & 26 & 100&0 \\ \\

\end{tabular}
\end{center}
\caption{Datasets used in this study. The defect rate of gcc is denoted as 100\% since we were able to collect only 116 defective modules. All the NASA and SOFTLAB data sets are available at \protect\url{http://promisedata.org}.}\label{fig:data}
\end{figure} 

Inspired by the recent systematic review of within vs cross company effort estimation studies by Kitchenham et al.~\cite{kitch07}, we have done extensive experiments on Promise data tables to analyze predictor behavior using a) local data(within the same company) b) imported data (cross company). For each NASA and SOFTLAB table of \fig{data}, we built test sets from
10\% of the rows, selected at random.  Then we learned defect
predictors from:
\bi
\item the other 90\% rows of the corresponding table (i.e. local data).
\item 90\% rows of the other tables combined (i.e. imported data).
\ei

We repeated this procedure 100 times, each time randomizing the order of the rows in each table, in order to control  {\em order effects} (where the 
learned theory is unduly affected by the order of the examples). 
We measured the performance of predictor using $pd$, $pf$ and $balance$.
If $\{A,B,C,D\}$ are the
true negatives,
false negatives, 
false positives, and 
true positives
(respectively) found by a defect predictor, then:

{\footnotesize
\begin{eqnarray}
pd=&recall=&D/(B+D)\\
pf=&&C/(A+C)\\\label{eq:bal}
bal=&balance=&1 - \frac{\sqrt{\left(0 - pf\right)^2 + \left(1 - pd\right)^2}}{\sqrt{2}}
\end{eqnarray}
}
All these values range zero to one.
Better and {\em larger} balances fall  {\em closer} to the desired  zone 
of no false alarms ($pf=0$) and 100\% detection ($pd=1$). We then used the Mann-Whitney U test~\cite{mann47} in order to test
for statistical difference.

In a finding consistent with our general thesis (that software artifacts conform to very regular
statistical patterns),
we found that the following result was very stable across the ten NASA and
SOFTLAB data sets:

\bi
\item Imported data dramatically increased the probability of detecting defective modules;
\item But imported data also dramatically increased the false alarm rate. 
\ei
Our suspicion is that the reason for the high false alarm rates was the irrelevancies introduced by imported data.
That is, rather than unquestionally using imported data, it could be advantegeous to only use {\em relevant}
data from external sources. 
In the 
sequel we will use nearest neighbor methods to find these relevant instances\footnote{TURKEY: rhetoical issue- do
you want to stress NN as an nnvoation in this paper? If not, remove it from the abstract.
If so, then pull the NN results from figure 5 and use them later in the paper and change this para.}.
\begin{figure}[!t]
\begin{center}
{\scriptsize
\begin{tabular}{r@{}r|r@{~}r@{~}r@{~}r@{~}r@{~}|l}
\multicolumn{7}{l}{Nasa on local Nasa data.}\\\hline
&treatment & min & Q1 & median & Q3 & max  \\\hline
 pd  & Local&       0&  60&  75&   82& 100& \boxplot{0}{60}{75}{82}{18}\\\hline
 pf  & Local&        0&  24&  29&   35&  73& \boxplot{0}{24}{29}{35}{38}\\
\hline\end{tabular}

~\\~\\

\begin{tabular}{r@{}r|r@{~}r@{~}r@{~}r@{~}r@{~}|l}
\multicolumn{7}{l}{Nasa on imported Nasa data.}\\\hline
&treatment & min & Q1 & median & Q3 & max  \\\hline
 pd & Imp.&       81&  84&  94&  98& 99& \boxplot{81}{3}{94}{98}{1}\\
 pf & Imp.&        26&  60&  68&   90& 94& \boxplot{26}{23}{68}{90}{4}\\ \hline\end{tabular}

~\\~\\

\begin{tabular}{r@{}r|r@{~}r@{~}r@{~}r@{~}r@{~}|l}
\multicolumn{7}{l}{Nasa on nn-imported Nasa data.}\\\hline
&treatment & min & Q1 & median & Q3 & max  \\\hline
 pd & NN Imp.&       50&  59&  68&  73& 79& \boxplot{50}{9}{68}{73}{6}\\
 pf & NN Imp.&        15&  20&  27&   38& 41& \boxplot{15}{5}{27}{38}{3}\\
\hline\end{tabular}

~\\~\\

\begin{tabular}{r@{}r|r@{~}r@{~}r@{~}r@{~}r@{~}|l}
\multicolumn{7}{l}{Softlab on local Softlab data.}\\\hline
&treatment & min & Q1 & median & Q3 & max  \\\hline
 pd & Local&      35&  40&  88&   100& 100& \boxplot{35}{5}{88}{100}{0}\\\hline
 pf & Local&        3&  5&  29&   40&  42& \boxplot{3}{2}{29}{40}{2}\\
\hline\end{tabular}

~\\~\\


\begin{tabular}{r@{}r|r@{~}r@{~}r@{~}r@{~}r@{~}|l}
\multicolumn{7}{l}{Softlab on imported Nasa data.}\\\hline
&treatment & min & Q1 & median & Q3 & max  \\\hline
 pd & Imp.&      88&  88&  95&  100& 100& \boxplot{88}{0}{95}{100}{0}\\
  pf & Imp.&        52&  59&  65&   68& 68& \boxplot{52}{7}{65}{68}{0}\\ \hline\end{tabular}

~\\~\\

\begin{tabular}{r@{}r|r@{~}r@{~}r@{~}r@{~}r@{~}|l}
\multicolumn{7}{l}{Softlab on nn-imported Nasa data.}\\\hline
&treatment & min & Q1 & median & Q3 & max  \\\hline
 pd & NN Imp.&      70&  70&  88&  88& 88& \boxplot{70}{0}{88}{88}{0}\\
  pf & NN Imp.&        24&  28&  32&   38& 44& \boxplot{24}{4}{32}{38}{6}\\

\hline\end{tabular}

}
\end{center}
\caption{Results for NASA and SOFTLAB  tables.
Numeric results on left; quartile charts on right. ``Q1'' and ``Q3'' denote
the 25\% and 75\% percentile points (respectively). 
}\label{fig:promise}
\end{figure}



Those prior results are shown in the {\em quartile charts} of
Figure \ref{fig:promise}. 
Quartile charts are generated from sorted sets of results, divided into four subsets of (approx) same cardinality.
For example these numbers have four quartiles:
\[
{\footnotesize
\{\overbrace{4,7,15}^{q1},20,31,\overbrace{40}^{median},52, 64, \overbrace{70,81,90}^{q4}\}}
\]
These quartiles can be drawn as follows:
the upper and lower quartiles are  marked with black lines;
the
median is marked with a black dot; and
vertical bars  are added to
mark the 50\% percentile value.
For example, the above numbers can be drawn as:
{\small
\[0\%\; \boxplot{4}{11}{40}{70}{20}\; 100\%\]}

\section{How General are our Regularities?}

XXX back to you Turkey

XXX back to you Turkey

Note the external validity of the 
above results: from basa to softwlab and visa versa

Motivated by the above reasoning, we now present another set of experiments, this time using nearest-neighbor sampling rather than random sampling. We will show that nearest neighbor sampling reduces the conjectured irrelevancies in imported data to some extent. The experimental rig is the same as before, however, we do not use the random 90\% of imported data, rather we use the nearest neighbors of local data among the imported data. Our preliminary analysis shows that this latter approach lies somewhere between using local data and imported data, while closer to former than the latter. 



In Figure \ref{fig:promise},  the visual pattern is clear: imported data increase probability of detections along with false alarm rates, and nn-imported data remove the high false alarm rates, again, along with probability of detections. This outcome does not contradict our previous conclusion that imported data should only be used in mission critical projects. While nn-imported data decreases false alarm rates, predictors learned from local data still performs the best. Thus, companies should still rely on using local data for learning predictors. 

These results are more interesting, considering the LHF approach. 
Note that Softlab data were collected from a Turkish white- goods manufacturer. The datasets (\{ar3, ar4, ar5\}), marked
as "Softlab'' in \fig{data},
are the 
controller software for a washing machine, a dishwasher and a
refrigerator. 
Note that this software was developed via methods that are both
culturally and organizationally different to Nasa aerospace software.
The patterns found in American Nasa rocket software
   also exist in software controllers of Turkish domestic appliances. While this is not 
   definitive proof of  our
   claim, we find it a very compelling result suggesting that these
   patterns apply to a very wide range of software
   from around the world.
   
%------------------------------------------------------------------------- 
\Section{Similar Patterns in Open Source }

In the previous section, in all experiments, we analyzed various commercial software projects from USA and Turkey. Since we claim the existence of tight statistical patterns through all kind of software, in this section, we make similar analysis for a new data table, i.e an open source anti-virus project (Clam AV v0.91) denoted as cav91 in Figure \ref{fig:data}.

The same set of experiments are once more applied on cav91 data table and the results are visualized in Figure \ref{fig:os}. We again used Nasa tables as imported data, since they provide a large basis with 5000+ samples. At the first glance, the patterns in Figure \ref{fig:os} seem a bit different than those in Figure \ref{fig:promise}. There are still increases in probability of detection and false alarms rates, though not dramatically. However, this is not a counter example to the LHF approach. We explain this behavior with the following assertions: 

Our experiments:
\bi
\item in commercial software analysis, local data corresponds to projects developed by a relatively small team of people in the same company and with certain business knowledge.
\item in commercial software analysis, imported data corresponds to a variety of projects developed by various people in different companies and spans a larger business knowledge.  
\item in open source software analysis,  local data corresponds to projects developed by a larger team of people at different geographical locations with various backgrounds.
%\item In open source software analysis, imported data corresponds to variety of projects developed by various people in different companies.  
\ei 

We argue that, the above assertions clearly differentiate the meaning of local data for open source projects from commercial projects. The nature of open source development allows the definition of local data to be closer to commercial imported data, since both are developed by people at different sites with different background. That's the reason why adding commercial imported data does not add as much detection capability as it does for commercial local data. Furthermore, the false alarms are not that high since there are less irrelevancies in local open source data than commercial imported data, which is the cause of high false alarms. That's because open source local data consist of a single project and commercial imported data consist of several projects, which introduces irrelevancies.


\begin{figure}[!t]
\begin{center}
{\scriptsize
\begin{tabular}{r@{}r|r@{~}r@{~}r@{~}r@{~}r@{~}|l}
\multicolumn{7}{l}{Open-source on local OS data.}\\\hline
&treatment & min & Q1 & median & Q3 & max  \\\hline
 pd & Local&       0&  67&  67&  100& 100& \boxplot{0}{67}{67}{100}{0}\\
 pf & Local&        17&  25&  28&   30& 39& \boxplot{17}{8}{28}{30}{9}\\
\hline\end{tabular}

~\\~\\
 
\begin{tabular}{r@{}r|r@{~}r@{~}r@{~}r@{~}r@{~}|l}
\multicolumn{7}{l}{Open Source on imported Nasa data.}\\\hline
&treatment & min & Q1 & median & Q3 & max  \\\hline
 pd & Imported&       77&  77&  77&  77& 77& \boxplot{77}{0}{77}{77}{0}\\
 pf &Imported&        36&  38&  38&   39& 40& \boxplot{36}{2}{38}{39}{1}\\ \hline
 \end{tabular}

~\\~\\

\begin{tabular}{r@{}r|r@{~}r@{~}r@{~}r@{~}r@{~}|l}
\multicolumn{7}{l}{Open Source on nn-imported Nasa data.}\\\hline
&treatment & min & Q1 & median & Q3 & max  \\\hline
  pd & NN Imp.&       73&  73&  73&  73& 73& \boxplot{73}{0}{73}{73}{0}\\
 pf &NN Imp.&        27&  28&  28&   29& 30& \boxplot{27}{1}{28}{29}{1}\\

\hline\end{tabular}
}
\end{center}
\caption{Results for Open-source cav91table.
Numeric results on left; quartile charts on right. ``Q1'' and ``Q3'' denote
the 25\% and 75\% percentile points (respectively). }\label{fig:os}
\end{figure}


%------------------------------------------------------------------------- 
\Section{Defect Patterns with Handful Data}

\begin{figure*}[!t]
\begin{center}
\begin{tabular}{ccc}
\includegraphics[angle=90,width=2.1in]{underCM1.pdf}&
\includegraphics[angle=90,width=2.1in]{underKC1.pdf}&
\includegraphics[angle=90,width=2.1in]{underKC2.pdf}\\
\includegraphics[angle=90,width=2.1in]{underKC3.pdf}&
\includegraphics[angle=90,width=2.1in]{underMC2.pdf}&
\includegraphics[angle=90,width=2.1in]{underMW1.pdf}\\
\includegraphics[angle=90,width=2.1in]{underPC1.pdf}&


\end{tabular}
\end{center}
\caption{Micro-sampling results}\label{fig:under}
\end{figure*}



Micro Sampling goes here supported with nasa softlab and opensource

In order to determine the lower-limit on the number of cases that require manual
inspection, we performed
another experiment. Another under-sampling policy was employed, which we call {\em micro-sampling}.
 Given $N$ defective modules
in a data set, \[M \in \{25,50,75,.\} \le N\] 
defective modules were selected
at random. Another $M$ non-defective modules were selected, at random. The combined $2M$ data set was
then passed to a 10*10-way cross validation. 

Formally, under-sampling is a micro-sampling where $M=N$. Micro-sampling explores
training sets of size up to N, standard under-sampling just explores once data set of
size $2N$.

For this study we used Naive Bayes since,
in all the above work, it seems to be doing as well as anything else.
\fig{under} shows the results of an under-sampling study where $M\in\{25,50,75,...\}$
defective modules were selected at random, along with an equal $M$ number of defect-free modules.
Note the same visual pattern as before: increasing data does not necessarily improve $balance$.

Mann-Whitney tests were applied to test this visual pattern. 
Detectors learned from small $M$ instances do as well
as detectors learned from any other number of instances.
\bi
\item
For eight data sets,
\{CM1,KC2, KC3,MC1, MC2, MW1, PC1, PC2\},
micro-sampling at $M=25$ did just as well as anything larger sample size.
\item
For one data sets,
\{PC3\}, best results were seen at $M=75$. However , in many cases $\frac{8}{11}$,
$M=25$ did just as well as anything else.
\item
For three data sets \{PC4,KC1,PC5\} best results were seen at $M=\{200,575,1025\}$, respectively. 
However, for these three data sets, in all by one case
$M=25$ did as well as any larger value.
\ei

In summary, 
the number of cases that  must be reviewed in order to arrive at the performance ceiling of  defect 
predictor is very small:  as low as 50 randomly
selected modules (25 defective
and 25 non-defective).

%------------------------------------------------------------------------- 
\Section{Handful Data in Open Source}
\begin{figure}
\begin{center}
\begin{tabular}{ccc}
\includegraphics[width=3in]{v91self+gcc.pdf}
\end{tabular}
\end{center}
\caption{Predictors for cav91 are learned using available local bugs adding one at a time (upto vertical line). Then we incrementally introduced gcc bugs to learn more predictors.
}\label{fig:v91self+gcc}
\end{figure}


\begin{figure}
\begin{center}
\begin{tabular}{ccc}
\includegraphics[width=3in]{v91gcc.pdf}
\end{tabular}
\end{center}
\caption{We learn predictors using only a random 30\% of cav91 data, including 7 local bug reports on the average (upto vertical line). Then we introduced gcc bugs incrementally to learn more predictors.  
}\label{fig:v91self+gcc}
\end{figure}

%------------------------------------------------------------------------- 
\Section{Conclusion}

Based on this work, we suggest two directions for ASE research:
\bi
\item
One direction should explore software analysis using rigorous formalisms that offer ironclad
gaureentees of the corrections of a code (e.g. interactive theorem proving, model  checking,
or the 
correctness preserving transoftations discussed by Doug Smith\footnote{Keynote address, ASE'07}).
This approach is required
for the analysis of mission-critical
software that must always function correctly. 
\item 
Another direction should explore automatic methods with a stronger focus on maximizing
the effectiveness of the  analysis while minimizing the associated cost.
\ei
There has been some exploration of the second approach using
lightweight formal methods (e.g.~\cite{easter98}) 
or formal methods that emphasis the usability and ease of use of the 
tool (e.g.~\cite{levenson96,heitmeyer96automated}).
However,  our results also show that there exists an under-explored space of extrememly
cost-effective automated analysis methods. While these methods cannot offer 100\% certification gauteenees,
they can useful augment more expensive methods. 

%------------------------------------------------------------------------- 

\bibliographystyle{latex8}
\bibliography{ase,refs}


\end{document}

