\section{Modeling in Software Engineering}
\label{modelingInSE}
%Our thesis is that software engineers use models, that are problems with manual model-based
%methods, and that we can augment manual methods with treatment learning.
%
%It is simple to demonstrate the first part of our thesis.
%%Software engineering is modeling.  \cite{schmidt06}  
%Software engineers build
%models at every phase of the life cycle.
%Some models are paper-based and some models are executable but all these artifacts
%are 
% \emph{models}; 
%i.e. as 
%Mellow says
%\cite{mellor03}:
% ``elements
%describing something (for example, a
%system, bank, phone, or train) built for some
%purpose that is amenable to a particular form
%of analysis, such as
%\begin{itemize}
%\item Communication of ideas between people
%and machines
%\item Completeness checking
%\item  Race condition analysis
%\item   Test case generation
%\item Viability in terms of indicators such as
%cost and estimation
%\item Standards
%\item Transformation into an implementation"
%\end{itemize}
%
%In a more general sense, modeling has been used for centuries.  Schichl finds that the etymology of the term modeling is from the Latin word modellus. \cite{Schichl04} He goes on to day that modeling "describes a typical human way of coping with reality.  
%
  
Model-driven software engineering is no longer a future goal, but is becoming an industry expectation.   

This expectation permeates the software life cycle.  (This expectation
for the efficacy of models at this time is due to the confluence
of two evolutionary developments as pointed out by Selic \cite{selic03}:
maturity of automation techniques and industry standards like UML
\cite{booch99, uml04}.)  


\begin{figure*}[htb]
\includegraphics[width=7in]{figures/ddp-complexity.png}
\caption{Requirements, Risks, Mitigations, and Linkages Among These}
\label{DDPfigure} \end{figure*}


 In a similar vein, Balasubramanian, et al, have developed a variant of model-driven engineering that they call \emph{Model-Integrated Computing} based on a domain-specific modeling language that ``simplifies and automates many activities associated with developing and deploying component-based systems."  \cite{bala06}  (Specifically, they have developed a tool suite for development of distributed embedded automotive systems.)  
 
 The importance of models and the model-driven approach is not limited to software design (e.g., the design of software architecture as in the OMG Model-Driven Architecture \cite{omg03, frankel03} ) where modeling  languages like UML have strength.  One can find models used in the requirements phase (see the DDP method and tool \cite{feather03} which are a risk-based approach and visual tool to support requirements engineering), refactoring of designs using patterns \cite{france03}, software integration \cite{denno03}, model-based security \cite{jurjens06}, and performance assessment \cite{bals04}.
 
 Other researchers have recognized the need for support environments to help explore the increasingly complex models that engineers are developing.  Gray, at al, \cite{gray06} have developed the Constraint-Specification Aspect Weaver (C-Saw) that uses aspect-oriented approaches \cite{filman04} to help engineers in the process of model transformation.  Cai and Sullivan \cite{cai05} describe a formal method and tool called \emph{Simon} that ``supports interactive construction of formal models, derives and displays design structure matrices ... and supports simple design impact analysis."  \emph{Alloy} \cite{jackson02} is a ``lightweight" formal language for modeling of structural properties of software.
 
%\subsection{Model Complexity}
%There is a tension in model construction between keeping the model simple (so that is can more easily be analyzed and manipulated) and making the model accurate.  Accuracy generally implies complexity.  As Hailpern, et al, point out, raising the level of abstraction is the primary goal of modeling.  However, ``. there is always a trade-off between simplification by raising the level of abstraction and oversimplification, where there are insufficient details for any useful purpose" \cite{hailpern06}
%
%In either case, that is, whether the model being constructed is simple or complex, the process of model building is an intellectually difficult one.  Creating a useful simple model often requires deep intuition into a system that is the result of much contemplation. 
%
%The introduction of computer-based tools for model construction, manipulation, and analysis has permitted more complex models to be created.  To illustrate the level of complexity in current SE models, consider an example from the DDP tool. \cite{feather03}  This is tool that is used in the requirements phase or the early phases of design to capture requirements, risks in attaining those requirements, and mitigations that can lower risks to achieve the requirements.  This is tool and method that are currently in use at NASA's Jet Propulsion Laboratory.   See Figure~\ref{DDPfigure} that visually shows the linkages among requirements (at the top), associated risk (in the center) and mitigation (at the bottom).  Managers can choose among the possible mitigations to reduce risks which will help achieve various requirements.  The complexity here in the model and in the manager's task is apparent.
%

\section{A Saturation Effect or Order out of Chaos} \label{saturation}
A recurring theme from multiple sources is that, despite the complexity of many models (SE and others), there is often a surprising amount of "order" or "stability" that emerges.  In \cite{lewin92} Lewin attributes the following phrase to the Nobel-prize winning Physicist Murray Gell-Man: ``Surface complexity arising from deep simplicity."   Now, Gell-Man was referring to physical systems, not to computer models.  However, we assert that this insight is often appropriate in the domain of SE models.

In categorizing complexity of systems that we model, at one end are linear systems that are easy to understand and hence have simple models.  At the other end of the complexity scale are systems with completely random behavior that no model can adequately capture and from which reasonable conclusions are very difficult to derive.  Between these are systems that display nonlinear, dynamical behavior.  \cite{lewin92}  Nature is replete with such systems  (e.g., weather prediction, animal population dynamics, turbulence in fluid flow, etc. ). These are completely orderly and deterministic, and in principle completely predictable. ``It is just that in practice it is impossible to predict in detail what is going to happen more quickly than events unfold in real time." \cite{gribbin04} These are systems right at the edge of disequilibrium; nevertheless, patterns appear in their behavior.  The behavior of such systems tends to states of minimum energy or maximum entropy that called \emph{attractors}.  The reader is probably aware of the Lorenz attractor or butterfly attractor that Lorenz discovered in studying the sensitivity of weather to its initial conditions.  (A picture of this consists of two connected "pools" that look like the wings of a butterfly.) This is one of a category of attractors called \emph{strange attractors} whose trajectories through phase space ``correspond to an infinitely long line wrapped in a complex way, without ever crossing itself, around a finite surface."  \cite{gribbin04} Such systems are said to be chaotic.  Chaos ``is based on two simple ideas -- the sensitivity of a system to its starting conditions and feedback." \cite{gribbin04}

Thus, there are many naturally arising situations in which a complex system has an underlying law that is quite simple.  Consider the power law that explains the relationship between the magnitude and quantity of earthquakes: for every 100 earthquakes at magnitude 4, there are about 10 at magnitude 5.  \cite{gribbin04} (Remember that the Richter scale for earthquake magnitude is a logarithmic one. )  There is a similar power law that relates the size of cities in the world to the number of each size of city (when cities are organized into bins of similar size.) \cite{gribbin04} These are just two of a multitude of systems that display this pattern.

The point of this detour into chaos is to illustrate the ubiquity of our hypothesis that often complex models display some inner structure.   

Here are some other examples from the field of software.  In a study of an early machine learning program for the game of checkers,  A. L. Samuel \cite{samuel59} modeled strategies for determination of 32 term scoring polynomial where each parameters qualified various aspects of the board configurations.  For example \emph{king center control} means that a king occupies one of the center positions.  The program learns weights for these parameter coefficients.  After 42 games, the program had learned that 12 parameters were important, although only 5 of these were of any real significance.

We have previously discussed the complexity in the DDP model that relates requirements to risks, and risks to mitigations.  To mine this complex data (as visually displayed in Figure~\ref{DDPfigure}), Kiper and Feather \cite{kiper04} have used simulated annealing (a search-based approach to SE -- see section \ref{subsection-Search-basedSE}) to find a set of near-optimal solutions that meet a cost bound.  In exploring, this region of near-optimality, these researchers used cluster analysis to find those sets of mitigations that agree to within 95\%.  In the case study that they present in \cite{kiper04}, there are 58 possible mitigations from which engineering managers must choose.  Thus, there are $2^{58} =  \sim10^{17}$ possible choices.  The simulated annealing search for near optimal solutions sets found about 3,400 solutions that were within 95\% of the best value of the objective function and satisfied the cost constraint of \$1,000,000.   This set of over 3000 sets of mitigations represents a model that is still too complex from humans to easily comprehend.  To this set, these researchers applied a cluster analysis algorithm that looked for clusters of mitigation sets which were almost identical in that they shared 85\% of the mitigation choices.  Figure \ref{clusters} visual displays a group of such clusters of mitigations. Each row represents one mitigation; each column displays a cluster where the darkness of the shading gives a measure of the number of times that mitigation appears in this cluster.  Again, the point here is that, in complex data, it is common to find structure.  


\begin{figure}[htb]
\begin{center}
\includegraphics[width=3in]{figures/clusters.pdf}
\caption{Visualizations of Clusters \cite{kiper04}}
\label{clusters}
\end{center}
\end{figure}



\subsection{Related Work: Saturation Elsewhere}
There is a particular type of structure that we have observed in many SE models -- that we have labeled a \emph{saturation effect}.  This name derives from the idea that "random search quickly yields all that can be found, even after a much longer search."  \cite{menzies02}  That is, the search space has been explored to a sufficient extent in that longer searches will produce little or no more information.  (We do not assert that all SE models have this property, but that, when a model does exhibit saturation, we can avoid the problem of incompleteness of a random search.)  In this subsection, will illustrate this effect in a number of areas of software engineering.  

In one study of testing of formal models \cite{menzies02}, repeated experiments have demonstrated the plateau that is typical of a saturation effect.  See figure \ref{formalTesting}.  In this experiment, finite state machines were translated into a particular variant of AND-OR graphs. Figure \ref{formalTesting} shows results from a random search for errors of a very large model.  (There are 250 finite state machines in this model, each with an average of 6 states.  This gives a total of 1,455 local states which is equivalent to a composite finite state machine of $2.65 x 10^{178}$ states.)  It is clear that the marginal gain after a search of the first few million nodes is negligible.  

In some prior work, Menzies, et al, have surveyed empirical reports in the field of testing where this saturation effect has been observed, i.e., where computer programs were observed to have zones that were easily reachable in testing, and others that were not reachable at all.  Here is a survey of some of such reports.  

\begin{itemize}
\item In \cite{bieman92}, Bieman and Schultz report that 10 or fewer paths through programs explored 83\% of the du-pathways.  (A du-path is a set of statements in a computer program from a definition to a use of a variable.  This is one common form of structural coverage testing.) 

\item In another study, Harrold and colleagues \cite{harrold98} studied over 4000 Fortran routines and 3147 C functions to look at their control graphs.  Potentially, the size of a control graph may grow as the square of the number of statements (in the case where every statement was linked to every other statement.)  This research found that, in these case studies, the size of the control graph is a linear function of the number of statements.  

\item In \cite{colomb99}, Colomb reports about the use of a medical expert system.  Colomb expected that, for a system with V variables and S state, this system should have $S^V$ states.  In this case, $S^V \approx 10^{14}$  However, after operation for one year, he found that only 4000 states had been exercise.  

\item In another examination of an expert system, this one in the telecommunications domain, Avritzer,  Ros, and Weyuker found that a sample of 6\% of all inputs to this expert system covered 99\% of all inputs seen in about one year of operation, and a sample of just over 12\% covered 99.9\%.

\item In a study of the testing of two extensively used systems, the Unix report-generation language AWK and the text formatting language TEX.  In both cases, despite elaborate testing, various measures of coverage showed that large portions of these programs were not covered.  For example, in \emph{block coverage}, TEX testing had achieved 85\% coverage, and AWK had achieved only 70\%.  Since these programs are viewed as quite reliable, this is evidence that most paths get exercised early in testing with little further improvement with further testing.

\item Another form of testing that has interested software engineers is mutation testing.  This method of testing is useful for getting an estimate of what percentage of errors have been discovered by testing.  Such tester have often reported that a small sample of mutations are as useful as a much larger number of mutations.  See \cite{acree80, budd80, michael97, wong95}

\item A similar effect has been noted in the certification of expert systems.  \cite{menzies01} In this work, Menzies and Singh present evidence from nine empirical studies that the number of tests to certify an expert system is often quite low, in the range of 4 to 200 tests.  See \cite{betta95, bobrow86, buchanan84, caraca00, davies94, harmon86, menzies97, ramsey89, yu79}.  Thus, the number of tests need to discover the errors in an expert system is often quite low. 

\end{itemize}


\begin{figure}[htb]
\begin{center}
\includegraphics[width=3in]{figures/saturationMenzies02.pdf}
\caption{Random search of a very large model \cite{menzies02}}
\label{formalTesting}
\end{center}
\end{figure}

In a more general experimental study of state space of models, Pel\'{a}nek \cite{pelanek04} concluded that ``State spaces are usually sparse, without hubs, with one large SCC [strongly connected component], with small diameter \footnote{The diameter of a graph (of a state space here) is the number of edges on the largest shortest path between any two vertices} and small SCC quotient \footnote{SCC quotient is a measure of the complexity of a graph. See \cite{pelanek04} }, with many diamond-like structures."  This sparseness of state spaces was observed previously by Holtzmann \cite{holzmann90} (where he estimate the average degree of a vertex in a state space to be 2), and is further validation of our hypothesis about the nature of SE models.  Pel\'{a}nek further states that these ``observed properties of state spaces are not the result of the way state spaces are generated not of the features of specification languages but rather of the way humans design/model systems."  \cite{pelanek04}

In a comparison of a standard depth first search backtracking algorithm with a randomized search theorem prover, Crawford and Baker \cite{crawford94} found that the randomized search was able to reach \emph{more} scheduling solutions in \emph{less} time.  In speculating about the reasons for this, these researchers indicated that their systems had a small number of ``control" variables that determined the value of the much larger number of ``dependent" variables.
 
\section{Model Comprehension} \label{modelComprehension}
Understanding a model and its implications often pushes human intelligence to its limits.  Writing and running a model is only half the battle. After running, comes \emph{comprehension}.  Available evidence is that humans, unaided, are quite poor at understanding even small models. 

These examples motivate a belief that running and watching modes is not enough to understand them. Instead, model comprehension is best conducted by teams of   human and artificial intelligences working together to understand a domain. In our view, humans are best at painting the "whole" story, the big picture, defining the model, specifying the range of permissible values, perhaps along with some biases about which values are most likely or most improbable. Artificial intelligence (AI) techniques and tools are good at filling in the "holes"; i.e., all the details that humans routinely miss.  As evidence of this claim, we ask the reader to consider the following simple mathematical model of exponential population growth.  (In this particular model, the value over which the optimization is computed are judgments from domain experts.  Thus, focusing on just the one optimal value is not appropriate.)  
 
\begin{equation} 
\label{eq1}
dn/dt = rn
\end{equation}

In equation \#\ref{eq1}, \emph{r} is a constant reflecting environmental conditions, \emph{t} is time, and \emph{n} is the
population. Note that this model is not accurate since population growth must taper off as it
approaches \emph{C}, the maximum carrying capacity of the environment.  Consider another version of this model in the following equation:

\begin{equation}
\label{eq2}
dn/dt = rn(1-(n/c))
\end{equation}

Before reading further, we ask the reader to consider whether equation \#\ref{eq2} is an appropriate model of population growth? If the reader cannot find all errors in a one-line model, then we should be suspicious of claims that the truth status of larger models can be accurately determined by people.

Although equation \#\ref{eq2} does model our intuition in some cases, there is one situation in which it is clearly incorrect.   Consider the case of over-population in an hostile environment: $n > C, r < 0$.  Our intuition is that the population will fall.  However, with these assumptions $rn(1-(n/c)) > 0$.  That is, our model concludes that the population will increase.  (This example is taken from \cite{puccia85}.)   Our experience has been
that this error is not apparent to many people. In this case, we have failed to ascertain the
truth status of a one-line mathematical model.

Myers \cite{myers77} reports controlled experiments with a 63 line model.  In this experiment, 59 experienced IT professionals searched for errors in a very simple text formatter that consisted of 63 lines of
PL/1 code. Even with unlimited time and the use of three different methods, 73 of the
experts could only find (on average) 5 of the 15 errors in this 63 line model \cite{myers77}. This
result, despite its age, and the previous thought experiment do not inspire confidence that experts can
accurately assess larger models.

This phenomenon is not limited to software.  Consider the  results of the Feldman and Compton study in which 109 of 343 (32\%) of the known data points from six studied papers could not be explained using a
glucose regulation model developed from international refereed publications. \cite{fecosm89a, fecosm89b, smythe89} A subsequent study corrected some modeling errors of Feldman and Compton to
increase the inexplicable percentage from 32\% to 45\%. A similar study successfully
faulted another smaller published scientific theory \cite{menzies92}.  

\begin{table}
\center
\caption{Experts Comprehension of Others' Models}
\begin{tabular}{|c|c|c|} \hline
Expert Pairs&Understanding&Agreement\\ \hline
Expert \#1 and \#2&62.5& 33.3\\
Expert \#2 and \#1& 61.1& 26.7\\ \hline
Expert \#1 and \#3&31.2& 8.3\\
Expert \#3 and \#1& 42.9& 33.3\\ \hline
Expert \#2 and \#3&44.4& 20.0\\
Expert \#3 and \#2& 71.4& 33.3\\ \hline
\end{tabular}
\label{shawTable1}
\end{table}

In a similar vein, Shaw reports an experiment in which a group of geological experts built models for the
same domain.    Twelve weeks later they reviewed each other's knowledge bases as well as their own
\cite{shaw88}.   These research found that experts disagree significantly with each
other \cite{shaw88}.  (See table \ref{shawTable1}.)  More surprisingly, they found that, after twelve weeks, an expert's understandability of his/her own knowledge base and even his/her agreement with it were considerably less than total. (See table \ref{shawTable2}.) 

\begin{table}
\center
\caption{Experts Comprehension of Their Own Models}
\begin{tabular}{|c|c|c|} \hline
Expert&Understanding&Agreement\\ \hline
Expert \#1&62.5&81.2\\ \hline
Expert \#2&77.8&94.4\\ \hline
Expert \#3&85.7&78.6\\ \hline

\end{tabular}
\label{shawTable2}
\end{table}

Each of these examples helps to confirm our hypothesis that comprehending a model (even an apparently simple one) and its implications can be quite difficult even for domain experts.  AI techniques have proven useful at exploration of such models to provide insights that humans are not able to see.
One rising area of AI applied to software engineering that has proven its effectiveness are those techniques that are described as \emph{search-based software engineering.}  We describe these techniques next.

\section{Search-based Software Engineering} \label{searchBasedSE}
\label{subsection-Search-basedSE}
Thus, models are pervasive in software engineering and are generally quite complex to construct (although there may be embedded structure that we can discover, as described above). This complexity in construction of useful models typically results from deep contemplation about a requirements, design, performance, or some other aspect of a system -- existing or planned.  It is important that this intellectual effort be exploited.  One technique that we have found effective at exploiting SE models falls in the category of search-based software engineering techniques.  (The particular method that we use, minimal contrast set treatment learning, will be described later in a this section.)  However, one of the important points of this article is that SE models should be exploited, iteratively and systematically, and mined by whatever useful technique that software engineers can find useful and effective.

Search-based software engineering consists in using \emph{meta-heuristic} techniques, like genetic algorithms, simulated annealing, treatment learning, etc., to explore a model.  As Clarke, et al, assert: ``...software engineers face problems which consist, not in finding \emph{the} solution, but rather, in engineering an \emph{acceptable} or \emph{near optimal solution} from a large number of alternatives." \cite{clarke03}  

To use a search-based approach, software engineers generally have to reformulate their problem by (1) 
finding a representation of the problem that can be symbolically manipulated, (2) defining a fitness function, and (3) determining an appropriate set of manipulation operators. \cite{harman01}

There is a growing body of research about uses of meta-heuristic search in various fields of software engineering. (See \cite{clarke03}.)   In particular, several researchers have report about the use of search-based techniques in the area of testing. \cite{jones96, jones98, pargas99, tracey98} Others \cite{harman02, lutz01} have used genetic algorithms to examine ways of modularizing software. \cite{clarke03}  Work by Aguilar-Ruiz, et al, \cite{aguilar01} and by Dolado, et al, \cite{dolado00, dolado01} describe search-based approaches to cost estimation.  We have previously mentioned the DDP project that uses simulated engineering in requirements analysis and early phases of design.  \cite{feather03}

We recognize that heuristic search-based approaches may not be
appropriate in all cases.  Sometimes an analytical solution exists.
However, there are several reasons for using search-based methods
alone (when there is no analytical solution) or as a supplement to
analytical techniques.  Haman and Jones \cite{harman01} point out
that search-based techniques may avoid bias in analytical methods,
find gaps that analytical methods leave in search spaces, supplement
suboptimal or partial analytical solutions, and allow for a choice
of fitness function in an iterative fashion.

To quote Clarke, et al, again: ``The strength of meta-heuristic
algorithms is that they seek iteratively an optimal solution within
a landscape that may be extremely complicated and even discontinuous."
\cite{clarke03}


