% Prediction.tex

\section{Defect Prediction}
\label{DefectPrediction:sec}

In this section, we step back from the specific issue of activity to discuss the more general
field of defect prediction.

%When building a software system, engineers build and combine software ``modules''; i.e.
%a small unit of compilation which might be a function in ``C'' or a class in ``JAVA''.
%Typically, one {\em project} contains hundreds to tens of thousands of {\em modules}.

%We assume that some quality assurance (QA) technique is applied to assess module quality.
%Those techniques include inspections, unit tests, static source code analyzers, etc.
%A record of the results of this QA is a {\em defect log}. {\em Defect predictors} can be learned from these historical 
%logs, if the logs contain tables of data. In those tables, rows describe data from one module.
%Table columns describe static code features such as lines of code measures, the McCabe measures, the Halstead 
%measures and (for OO systems), the number of methods per class, the number of children per class, etc. One
%column is added for ``{\em bugs}''; i.e.  a count of how many defects where found during the inspection process.

A typical, object-oriented, software project can contain hundreds to thousands of classes.
In order to guarantee general and project-related fitness attributes for those classes, it is commonplace to apply
some quality assurance (QA) techniques to assess the classes's inherent quality.
These techniques include inspections, unit tests, static source code analyzers, etc.
A record of the results of this QA is a \emph{defect log}. We can use these logs to learn \emph{defect predictors}
if the information contained in the data provides not only a precise account of the encountered faults (\ie, the 
``bugs"),  but also a thorough description of static code features such as \emph{Lines of Code} (LOC), complexity measures 
(\eg, McCabe's cyclomatic complexity), and suitable object-oriented design 
metrics~\cite{chidamber:94a,Vasa10a,vasa:09a,lumpe:10a}.

%For these data sets, the data mining goal is to learn a predictor for the number of $defective$ modules from past 
%projects that can be applied to future projects. Such defect predictors can be used to focus the QA budgets.
%This is an important task since, during development, developers {\em skew} their limited quality assurance (QA)
%budgets towards artifacts they believe most require extra QA. For example, it is common at NASA to focus QA more 
%on the on-board guidance system than the ground-based database storing scientific data collected from a satellite.

For this, data miners can learn a predictor for the number of \emph{defective} 
classes from past projects so that it can be applied for QA assessment in future projects. Such a predictor allows
focusing the QA budgets. This is an important task as, during development, developers have to \emph{skew} their 
quality assurance activities towards artifacts they believe require most effort due to limited 
project resources. For example, it is a common QA practice at NASA to focus  on on-board 
guidance systems rather than  ground-based databases that  store data collected from the satellite~\cite{me07b}.


%This skewing process can introduce an inappropriate bias to QA. If  the QA activities concentrate on  project
%artifacts, say {\em A,B,C,D}, then that leaves {\em blind spots} in {\em E,F,G,H,I,...}.
%Blind spots can compromise high assurance software. Leveson remarks that in modern complex systems, unsafe
%operations often result from an unstudied interaction between components~\cite{leven95}. For example, Lutz and
%Mikulski~\cite{lutz03} found a blind spot in NASA deep-space missions: most of the mission critical {\em in-flight} 
%anomalies resulted from errors in {\em ground software} that fails to correctly collect in-flight data.

Skewing can introduce an inappropriate QA bias. Consider $n$ project 
classes $C_1, ..., C_n$. If the QA team only verifies $C_1, ..., C_m$ with $1 \le m \le n$, using some ordering and 
inspection threshold of the analyzed classes, then $C_{m+1},...,C_n$ constitute a \emph{blind spot} that can 
compromise the system's required quality attributes. Leveson remarks that, in modern complex systems, unsafe
operations often result from an unstudied interaction between components~\cite{leven95}.
For example, Lutz and Mikulski~\cite{lutz03} found a blind spot in NASA deep-space missions, where
most of the mission critical \emph{in-flight} anomalies resulted from errors in the \emph{ground software} that failed
to correctly collect in-flight data.
To avoid blind spots, one option is to rigorously assess all aspects of all  software modules. But this is impractical.
Exponential costs quickly exhausts finite QA resources. We must, therefore, devise a technique to manage them. 

%%To avoid blind spots, one option is to rigorously assess all aspects of all  software modules. But this is
%%impractical. Software project budgets are finite and QA effectiveness increases with QA effort:
%%\bi
%%\item
%%A {\em linear} increase in the confidence $C$ of finding faults takes {\em exponentially} more effort. 
%%For example, to detect one-in-a-thousand module faults, moving $C$ from 90\% to 94\% to 98\% takes 2301,
%%2812, and 3910 black box tests (respectively)\footnote{A randomly selected input will find a fault with probability $x$.
%%Voas observes~\cite{voas95} that after $N$ random black-box tests, the chance of the inputs not revealing any fault
%%is $(1-x)^N$. Hence, the chance $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$.}.
%%\item
%%The infamous state space explosion problem imposes strict limits on how much a system can be explored
%%via automatic formal methods~\cite{me00q}. Lowry et.al.~\cite{lowrey98} and Menzies and Cukic~\cite{me99q}
%%offer numerous other examples where assessment effectiveness is exponential on effort.
%%\ei
%
%To avoid blind spots, we could rigorously assess all aspects of all components comprising the software system. 
%But this is impractical. Software project budgets are finite and QA effectiveness plateaus eventually with increasing
%QA effort:
%\bi
%\item
%A \emph{linear} increase in the confidence $C$ of finding faults requires \emph{exponentially} more effort. 
%For example, to detect one-in-a-thousand module faults, improving the confidence first from 90\% to 94\% and 
%than to 98\% requires 500 and 1100 additional black-box tests, respectively, while it takes 2301 black-box tests to reach the initial confidence of 90\%.\footnote{A random input finds a fault at probability $p$. 
%Hence, after $N$ random inputs, the chance of missing a fault is
%$(1-p)^N$ and   the probability of seeing the fault is $1-(1-p)^N$. Hence,
% $N(C,p)=\frac{log(1-C)}{log(1-p)}$. For example, $N(0.90,10^{-3})=2301$.}
%\item
%The state space explosion problem imposes strict limits on how much a system can be explored
%via automatic formal methods~\cite{me00q}. Lowry et.al.~\cite{lowrey98} and Menzies and Cukic~\cite{me99q}
%offer numerous other examples where assessment effectiveness is exponential on effort.
%\ei
%
%%Exponential costs quickly exhausts finite QA resources. Hence, blind spots can't be avoided and must be managed. 
%%Standard practice is to apply the best available assessment methods on the sections of the program that the best 
%%available domain knowledge declares is the most critical.  We endorse this approach.  Clearly, critical sections
%%require the best known assessment methods, in hope of minimizing the risk of safety or mission critical failure 
%%occurring post deployment. However, this focus on certain sections can blind us to defects in other areas which,
%%through interactions, may cause similarly critical failures. Therefore, the standard practice should be augmented
%%with a {\em lightweight sampling policy} like defect predictors that (a)~explores the rest of the software and 
%%(b)~raises an alert on parts of the software that appear problematic.  This sampling approach is incomplete by
%%definition. Nevertheless, it is the only option when resource limits block complete assessment.
%
%Exponential costs quickly exhausts finite QA resources. Hence, blind
%spots cannot be avoided and we must devise a technique to manage
%them. 

Static code defect predictors are a \emph{lightweight sampling policy} that guides the exploration of a
system and raises an alert on sections that appear problematic. This approach is 
incomplete by definition. But, it is the only option when resource limits prevent us from performing a complete 
assessment of the code base.

%Compared to certain reports of standard industrial practice, defect predictors are better than humans are identifying 
%which modules will require further QA. Previously we have reported studies where defect predictors had probabilities 
%of detection (recall) and probabilities of false alarm (pf) of (recall,pf)=(71\%,25\%), on average~\cite{me07b}. These 
%values are higher than known results from manual inspection methods. For example, 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's 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}.}. In other work, Raffo found that the defect detection capability of industrial review 
%methods can vary from
%\[
%Recall=TR(35, 50, 65)\%\]
%for full Fagan inspections~\cite{fagan76} to
%\[
%Recall=TR(13, 21, 30)\%\]
%for less-structured inspections~\cite{raffo05} (note: ``$TR(a,b,c)$'' is a triangular distribution with
%min/mode/max of $a,b,c$).

%Standard industrial practice suggests that defect predictors perform better compared to humans when identifying 
%which modules will require further quality assurance. In earlier work we noticed that defect predictors exhibited 
%\emph{probabilities of detection} (recall) and \emph{probabilities of false alarm} (pf)  of (recall,pf)=(71\%,25\%), 
%on average~\cite{me07b}. These values are clearly better than known results from manual inspection methods.
%For example, a panel at \emph{IEEE Metrics 2002}~\cite{shu02} concluded that manual software reviews can 
%at best find approx. 60\% of defects in a software system.\footnote{The panel did not accept (a)~Fagan's 
%claim~\cite{fagan86} that inspections can find 95\% of defects before testing or (b)~Shull's claim~\cite{shull00a}
%that specialized directed inspection methods can catch 35\% more defects that other methods.}
%Similarly, Raffo~\cite{raffo05} determined that the defect detection capability of industrial review methods can vary 
%from
%\[
%Recall=TR(35, 50, 65)\%\]
%for full Fagan inspections~\cite{fagan76} to
%\[
%Recall=TR(13, 21, 30)\%\]
%for less-structured inspections, where ``$TR(a,b,c)$'' denotes a triangular distribution with min, mode, and max.
%
%Defect prediction can also be faster than human-intensive methods. Static code features can be automatically and 
%cheaply extracted from source code, even for very large systems~\cite{nagappan05}. By contrast, other methods 
%such as manual code reviews are labor-intensive.  Depending on the review methods 8 to 20 LOC/minute
%can be inspected and this effort repeats for all members of the review team, which can be as large as four or
%six~\cite{me02f}.

One reason to favor static code measures is that they can be automatically extracted from the code base, with very 
little effort even for very large systems~\cite{nagappan05}.
%
%Also, there are industrial reports where this style of defect prediction was found pragmatically useful by industry:
%\bi
%\item 
%Defect predicting technology has been commercialized in commercial tools like {\em Predictive}~\cite{ism06}.
%One company used these tools to manage  safety critical software for  fighter aircraft (the software controlled a
%lithium ion battery, which can over-charge and possibly explode).  After applying a more expensive tool for structural
%code coverage was applied,  the company ran Predictive on the same code base. Predictive produced consistent 
%results with the more expensive tools while being able to faster process a larger code base than the more
%expensive tool~\cite{ism06}.
%\item
%Defect predictors developed at NASA ~\cite{me07b} have been applied to software development companies in
%another country (in Turkey). When inspection teams focused on the modules that trigger the defect predictors,
%they found up to 70\% of the defects using 40\% of the effort (measured in staff hours)~\cite{tosun09}.
%\item
%A  subsequent study on the Turkish software compared how much code needs to be inspected using random 
%selection vs selection via our defect predictors. Using random testing, 87\% of the files would have to be inspected
%in order to detect 87\% of the defects. However, if the inspection process was restricted to the 25\% of the files that 
%trigger the defect predictors, then 88\% of the defects could be found. That is, the same level of defect detection
%(after inspection) can be achieved using $\frac{87-25}{87}=71\%$ less effort~\cite{tosun10}.
%\ei
The industrial experience is that defect prediction scales well to 
a commercial context.
Defect predicting technology has been commercialized in \emph{Predictive}~\cite{ism06} a scalable product suite
to analyze and predict defects in software projects. One company used it to manage the safety critical software for a 
fighter aircraft (the software controlled a lithium ion battery, which can over-charge and possibly explode).  
After applying a more expensive tool for structural code coverage, the company ran Predictive on the same code 
base. Predictive produced results consistent with the more expensive tool. But, Predictive was able to faster process a larger code base than the more expensive tool~\cite{ism06}.

In addition, defect predictors developed at NASA~\cite{me07b} have also been used in software development companies outside the US (in Turkey). When the inspection teams focused on the modules that trigger the defect predictors,
they found up to 70\% of the defects using just 40\% of their QA effort (measured in staff hours)~\cite{tosun09}.

Finally, a  subsequent study on the Turkish software compared how much code needs to be inspected using random 
selection vs. selection via defect predictors. Using random testing, 87\% of the files would have to be inspected
in order to detect 87\% of the defects. However, if the inspection process was restricted to the 25\% of the files that 
trigger the defect predictors, then 88\% of the defects could be found. That is, the same level of defect detection
(after inspection) can be achieved using $\frac{87-25}{87}=71\%$ less effort~\cite{tosun10}.
