\section{SEESAW}

Since 2007, researchers at WVU have applied AI algorithms over parametric models of software development (based on COCOMO)~\cite{me07f} to implement quality optimizers. This is a a challenging task since they must execute over partial descriptions of projects and, in the case of parametric models, over models with uncertain internal parameters (like the ranges shown in \fig{coc1}).

In order to address this challenge, one needs to understand the nature of those models. In parametric modeling, the predictions of a model about a software engineering project are altered by project variables $P$ and {\em tunable} attribute coefficients $T$:
\begin{equation}\label{eq:pred}
prediction = model(P, T)
\end{equation}
In the simplified COCOMO model of \eq{simp}, the tuning options $T$ are the range of $(a,b)$ and the project 
options  $P$ are the range of $pmat$ (process maturity) and $acap$ (analyst capability). 
\begin{equation}\label{eq:simp}
effort = a \cdot LOC^{b +  pmat}\cdot acap  
\end{equation}
Based on the definitions of the COCOMO model, the ranges of the project attributes are: 
\begin{equation}
P=1 \le (pmat,acap) \le 5
\end{equation}
 Further, the cone of uncertainty associated with a particular project $p$ can identify the subset of the project options $p\subseteq P$ relevant to a particular  project. For example, a project manager may be unsure of the exact skill level of team members. However, if they were to assert ``my analysts are better than most'', then $p$ would include $\{acap=4,acap=5\}$.

SEESAW seeks a treatment $r_x \subseteq p$ that maximizes the $value$ of a  model's predictions where
{\em value} is a domain-specific function that scores model outputs according to user goals:
\begin{equation} \label{eq:argmin}
\arg\max_x\left( \overbrace{r_x \subseteq p}^{AI\;search}, 
\underbrace{t \subseteq T, value(model(r_x,t))}_{Monte\;Carlo} \right)
\end{equation}
The intuition of \eq{argmin} was that, when faced with tuning variance like that seen in \fig{coc1}, one should search for conclusions that are stable across the space of possible tunings. SEESAW assumed that the dominant influences on the $prediction$ are the project options $p$ (and not the tuning options $T$).
Under this assumption, the predictions can be controlled by:
\bi
\item
Constraining $p$ (using some AI tool)
\item
Leaving $T$ unconstrained (and sampling $t\in T$ using Monte Carlo methods)
\ei 
The parametric models used by SEESAW's models come from COCOMO. Shown in ~\fig{cocattrs}, these attributes
have a range taken from
\{very low, low, nominal, high, very high, extremely high\} or
\[\{vl=1, l=2, n=3, h=4, vh=5, xh=6\}\]

In COCOMO-II model~\cite{boehm00b}, Boehm divided the attributes into two sets: the {\em effort multipliers} and the {\em scale factors}. The effort multipliers affect effort/cost in a linear manner. Their off-nominal ranges \{vl=1, l=2, h=4, vh=5, xh=6\} change the prediction by some ratio. The nominal range \{n=3\}, however, corresponds to an effort multiplier of 1, causing no change to the prediction.
Hence, these  ranges  can be modeled as straight lines $y=mx+b$ passing through the point $(x,y)$=$(3,1)$. Such a line has a y-intercept of $b=1 - 3m$. Substituting this value of $b$ into $y=mx+b$ yields:
\begin{equation}\label{eq:lineem}\small
\begin{array}{l}
\forall x \in \{1..6\}\; EM_i=m_\alpha(x-3) + 1
\end{array}
\end{equation}
where  $m_\alpha$ is the effect of $\alpha$ on effort/cost.

One can also derive a general equation for the scale factors that influence cost/effort in an exponential manner. These features do not ``hinge'' around (3,1) but take the following form:
\begin{equation}\label{eq:linesf}\small
 \forall x \in \{1..6\}\; SF_i=m_\beta(x - 6) 
\end{equation}
where  $m_\beta$ is the effect of factor $i$ on effort/cost.

Along with COCOMO-II, Boehm also defined the COQUALMO defect predictor. COQUALMO contains equations of the same syntactic form as \eq{lineem}  and \eq{linesf}, but with different coefficients. Using experience from 161 projects~\cite{boehm00b}, one can find the maximum and minimum values ever assigned to $m$ for COQUALMO and COCOMO. Hence, to explore tuning variance (the $t\in T$ term in \eq{argmin}), all we need to do is select $m$ values at random from the min/max $m$ values ever seen.

Initially, prior work implemented the AI search of  \eq{argmin} using simulated annealing~\cite{me07f,me08c,me09e}.  Subsequent work demonstrated that the recommendations found in this way did better than numerous  standard process improvement methods~\cite{me09a}. Later implementations were based on a state-of-the-art theorem prover~\cite{me09i}. SEESAW searches within the ranges of project attributes to find constraints that most reduce development effort, development time (measured in calendar months), and defects. Figure ~\ref{fig:seesaw} shows SEESAW's pseudo-code. The code is an adaption of Kautz \& Selman's MaxWalkSat local search procedure [13]. The main changes are that each solution is scored via a Monte Carlo procedure (see score in Figure ~\ref{fig:seesaw}) and that SEESAW seeks to minimize that score (since, for our models it is some combination of defects, development effort, and development time in months).

SEESAW first combines the ranges for all project attributes. These constraints range from Low to High values. If a project does not mention a feature, then there are no constraints on that feature, and the combine function (line 4) returns the entire range of that feature. Otherwise, combine returns only the values from Low to High. In the case where a feature is fixed to a single value, then Low = High. Since there is no choice to be made for this feature, SEESAW ignores it. The algorithm explores only those features with a range of Options where Low \textless High (line 5). In each iteration of the algorithm, it is possible that one acceptable value for a feature X will be discovered. If so, the range for X is reduced to that single value, and the feature is not examined again (line 17). SEESAW prunes the final recommendations (line 21). This function pops off the N selections added last that do not significantly change the final score (t-tests, 95\% confidence). This culls any final irrelevancies in the selections. The score function shown at the bottom of ~\fig{seesaw} calls COCOMO/COQUALMO models 100 times, each time selecting random values for each feature Options. The median value of these 100 simulations is the score for the current project settings. As SEESAW executes, the ranges in Options are removed and replaced by single values (lines 16-17), thus constraining the space of possible simulations.

\begin{figure}[!t]
\begin{verbatim}
1 function run (AllRanges, ProjectConstraints) {
2   OutScore = -1
3   P = 0.95
4   Out = combine(AllRanges, ProjectConstraints)
5   Options = all Out features with ranges low < high
6   while Options {
7     X = any member of Options, picked at random
8     {Low, High} = low, high ranges of X
9     LowScore = score(X, Low)
10    HighScore = score(X, High)
11    if LowScore < HighScore
12      then Maybe = Low; MaybeScore = LowScore
13      else Maybe = High; MaybeScore = HighScore
14    fi
15    if MaybeScore < OutScore or P < rand()
16      then delete all ranges of X except Maybe from Out
17      delete X from Options
18      OutScore = MaybeScore
19    fi
20  }
21  return backSelect(Out)
22 }
23 function score(X, Value) {
24   Temp = copy(Out) ;; don't mess up the Out global
25   from Temp, remove all ranges of X except Value
26   run monte carlo on Temp for 100 simulations
27   return median score from monte carlo simulations
28 }
\end{verbatim}
\caption{Pseudocode for SEESAW}
\label{fig:seesaw}
\end{figure}

While a successful prototype, SEESAW has certain drawbacks:
\bi
\item {\em Model dependency:} 
SEESAW requires a model to generate the estimates. Hence,  the conclusions reached were only as good as this model so 
using this tool requires an initial, possibly time-consuming, model validation process.
\item {\em Data Dependency:}
SEESAW can only process project data in a format compatible with the underlying model. In practice, this limits the scope of the tool.
\item {\em Arbitrary Design}: 
SEESAW handles two dozen cases using rules designed using ``engineering judgment''; i.e. they are not based on any theoretical or empirical results in the literature (for example, ``do not increase automatic tools usage without increasing  analyst capability''). The presence of such ad hoc rules makes it harder to verify that the tool is correct.
\item {\em Performance}: SEESAW uses tens of thousands of iterations,  with several effort estimates needed calculated for each iteration. This resulted in a performance disadvantage.  \item {\em Size and Maintainability}: Due to all the above factors, the SEESAW code base has proved difficult to maintain.
\ei
We have found that these factors limit the widespread use of quality optimizers:
\bi
\item 
In the three years since our first paper~\cite{me07f}, we have only coded one software process model (COCOMO), which inherently limits the scope of our investigations.
\item
No other research group has applied these techniques.
\ei
These problems motivated an exploration of alternate approaches to quality optimization.