\documentclass{llncs} \usepackage{rotating,wrapfig,cite,url,times,graphicx} \newcommand{\aive}{{\"aive}} \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}} \begin{document} \title{ Finding Robust Solutions in Requirements Models } \author{ Gregory Gay\inst{1} \and Tim Menzies\inst{1} \and Omid Jalali\inst{1} \and Gregory Mundy\inst{2} \and \\ Beau Gilkerson \inst{1} \and Martin Feather\inst{3} \and James Kiper\inst{4} \authorrunning{Gay et al.} \institute{West Virginia University, Morgantown, WV, USA\\ \and Alderson-Broaddus College, Philippi, WV\\ \and Jet Propulsion Laboratory, California Institute of Technology, Pasadena, CA, USA\\ \and Dept. of Computer Science and Systems Analysis, Miami University, Oxford, OH, USA\vspace{0.1cm} {\footnotesize \email{greg@greggay.com, tim@menzies.us, jalali.omid@gmail.com, beau.gilkerson@gmail.com, mundyge@ab.edu, martin.s.feather@jpl.nasa.gov, kiperjd@muohio.edu }} }} \maketitle \vspace{-0.8cm} \begin{abstract} Solutions to non-linear requirements engineering problems may be ``brittle''; i.e. small changes may dramatically alter solution effectiveness. Hence, it is not enough to just generate solutions to requirements problems- we must also assess solution robustness. The KEYS2 algorithm can generate {\em decision ordering diagrams}. Once generated, these diagrams can assess solution robustness in linear time. In experiments with real-world requirements engineering models, we show that KEYS2 can generate decision ordering diagrams in $O(N^2)$. When assessed in terms of terms of (a)~reducing inference times, (b)~increasing solution quality, and (c)~decreasing the variance of the generated solution, KEYS2 out-performs other search algorithms (simulated annealing, ASTAR, MaxWalkSat). \end{abstract} \pagestyle{plain} \section{Introduction} Consider a ``requirements model'' where stakeholders write: \bi \item Their various goals; \item Their different methods to reach those goals; \item Their view of the possible risks that compromise those goals; \item What mitigations they believe might reduce those risks. \ei A ``solution'' to such models is a {\em least} cost set of mitigations that reduce the {\em most} risks, thereby enabling the {\em most} requirements. In theory, software can find the solution that best exploits and most satisfies the various goals of our different stakeholders. Such tools might find good solutions that were missed by stakeholders. Finding solutions to these requirements models is a non-linear optimization problem ({\em minimize} the sum of the mitigation costs while {\em maximizing} the number of achieved requirements). There are many heuristic methods that can generate solutions to non-linear problems (see {\em Related Work}, below). However, such heuristic methods can be {\em brittle}; i.e. small changes may dramatically alter the effectiveness of the solution. Therefore, it important to understand the {\em neighborhood around the solution}. A naive approach to understanding the neighborhood might be to run a system $N$ times then report: \bi \item the solutions appearing in more than (say) $\frac{N}{2}$ cases; \item results with a $\pm95\%$ confidence interval. \ei Note that both these approaches requires multiple runs of an analysis method. Multiple runs are undesirable since, in our experience~\cite{feather08}, stakeholders often ask questions across a range of ``scenarios''; i.e. hard-wired constraints that cannot be changed in that scenario. For example, three scenarios might be ``what can be achieved assuming a maximum budget of one, two, or five million dollars?''. Scenario analysis can be time consuming. Reflecting over (say) $d=10$ possible decisions a statistically significant number of times (e.g. $N=20$) requires up to $20*2^{10}>20,000$ repeats of the analysis. Therefore, this paper proposes a rapid method for exploring decision neighborhoods. {\em Decision ordering diagrams} are a visual representation of the effects of changing a solution. We show below that: \bi \item Using these diagrams, the region around a solution can be explored in linear time. \item A greedy Bayesian-based method called KEYS2 can generate the decision ordering diagrams in $O(N^2)$ time. \item KEYS2 yields solutions of higher quality that several other methods (simulated annealing, MaxWalkSat, ASTAR). \item Also, the variance of the solutions found by KEYS2 is less (and hence, better) than those found by the other methods. \ei This paper is structured as follows: \bi \item After some background notes on the solution robustness, we describe the {\em DDP} requirements engineering tool used at NASA's Jet Propulsion Laboratory (the case studies for this paper come from real-world early lifecycle DDP models); \item DDP inputs and outputs are then reviewed; \item Next, decision ordering diagrams are introduced; \item We then define and compare five different algorithms for generating solutions from DDP models: KEYS, KEYS2, Simulated Annealing, MaxWalkSat, ASTAR. Experimental results will show that KEYS2 out-performs the other methods (measured in terms of quickly generating high quality solutions that allow us to reflect over solution robustness). \item Finally, we offer some notes on related work and conclusions. \ei This paper extends a prior publication~\cite{jalali08} in several ways: \bi \item That paper did not address concerns of solution robustness. \item That paper did not explore a range of alternate algorithms. \item This paper introduces KEYS2, which is an improved version of KEYS,. \item This paper offers extensive notes on related work. \ei \section{Background} According to Harman~\cite{harman07}, understanding the neighborhood of solutions is an open and pressing issue in search-based software engineering (SBSE). He argues that many software engineering problems are over-constrained and no precise solution over all variables is achievable; therefore partial solutions based on heuristic search methods are preferred. {\em Solution robustness} is a major problem for such partial heuristic searches. The results of such partial heuristic search may be ``brittle''; i.e. small changes to the search results may dramatically alter the effectiveness of the solution~\cite{harman01}. When offering partial solutions, it is very important to also offer insight into the space of options around the proposed solution. Such neighborhood information is very useful for managers with only partial control over their projects since it can give them confidence that even if only some of their recommendations are effected, then at least the range of outcomes is well understood. Harman~\cite{harman07} comments that understanding the neighborhood of our solutions is an open and pressing issue in search-based software engineering (SBSE): \begin{quote} ``In some software engineering applications, solution robustness may be as important as solution functionality. For example, it may be better to locate an area of the search space that is rich in fit solutions, rather than identifying an even better solution that is surrounded by a set of far less fit solutions.'' \end{quote} \begin{quote} ``Hitherto, research on SBSE has tended to focus on the production of the fittest possible results. However, many application areas require solutions in a search space that may be subject to change. This makes robustness a natural second order property to which the research community could and should turn its attention~\cite{harman07}.'' \end{quote} This paper reports a set of experiments on AI search for robust solutions. Our experiments address two important concerns. Firstly, {\em is demonstrating solution robustness a time consuming task}? Secondly, is it necessary, as Harman suggests that {\em solution quality must be traded off against solution robustness}? That is, in our search for the conclusions that were stable within their local neighborhood, would we have to reject better solutions because they are less stable across their local neighborhood? At least for the NASA models described in the next section, both these concerns are unfounded. KEYS2 terminates in hundreths of a second (where as our prior implementations took minutes to terminate~\cite{fea02a}). Also, the solutions found by KEYS2 where not only of highest quality, they were also exhibited the lowest variance. Further, KEYS2 generates the decision ordering diagrams that can assess solution robustness in linear time. \section{Requirements Modeling Using ``DDP''} This section introduces the DDP requirements modeling tool~\cite{corn01,feather08}. used to interactively document the ``Team-X'' early lifecycle meetings at NASA's Jet Propulsion Laboratory (JPL). These meetings are the source of the real-world requirements models used in this paper. At ``Team X'' meetings, a large and diverse group of up to 30 experts from various fields (propulsion, engineering, communication, navigation, science, etc) meet for very short periods of time (hours to days) to produce a ``mission concept'' document. This document may commit the project to, say, solar power rather nuclear power or a particular style of guidance software. All of the subsequent work is based on the initial decisions documented in the mission concept. \begin{figure}[!t] {\footnotesize \begin{tabular}{p{\linewidth}}\hline \be \item Requirement goals: \bi \item Spacecraft ground-based testing \& flight problem monitoring \item Spacecraft experiments with on-board Intelligent Systems Health Management (ISHM) \ei \item Risks: \bi \item Obstacles to spacecraft ground-based testing \& flight problem monitoring \bi \item Customer has no, or insufficient, money available for our use \item Difficulty of building the models / design tools \ei \item ISHM Experiment is a failure (without necessarily causing flight failure) \item Usability, User/Recipient-system interfaces undefined \item V\&V (certification path) untried and scope unknown \item Obstacles to Spacecraft experiments with on-board ISHM \bi \item Bug tracking / fixes / configuration management issues, Managing revisions and upgrades (multi-center tech. development issue) \item Concern about our technology interfering with in-flight mission \ei \ei \item Mitigations: \bi \item Mission-specific actions \bi \item Spacecraft ground-based testing \& flight problem monitoring \item Become a team member on the operations team \item Use Bugzilla and CVS \ei \item Spacecraft experiments with on-board ISHM \bi \item Become a team member on the operations team \item Utilize xyz's experience and guidance with certification of his technology \ei \ei \ee\\\hline \end{tabular}} \caption{Sample DDP requirements, risks, mitigations.}\label{fig:ddpegeg} \end{figure} DDP allows for the representation of the goals, risks, and risk-removing mitigations that belong to a specific project. During a Team X meeting, users of DDP explore combinations of mitigations that cost the least and support the most number of requirements. DDP propagate influences over matrices. For example, here is a trivial DDP model where {\tt mitigation1} costs \$10,000 to apply and each requirement is of equal value (100). Note that the mitigation can remove 90\% of the risk. Also, unless mitigated, the risk will disable 10\% to 99\% of requirements one and two (respectively): \begin{equation}\label{eq:mod1} \overbrace{mitigation1}^{\$10,000} \underbrace{\rightarrow}_{0.9} risk1 \rightarrow \left< \begin{array}{c} \overbrace{\rightarrow}^{0.1} (requirement1=100) \\ \underbrace{\rightarrow}_{0.99} (requirement2=100) \end{array} \right.\end{equation} The other numbers show the impact of mitigations on risks, and the impact of risks on requirements. The core of DDP is two matrices: one for {\em mitigations*risks} and another for {\em risks*requirements}. DDP is used as follows. A dozen experts, or more, gather together for short, intensive knowledge acquisition sessions (typically, 3 to 4 half-day sessions). These sessions \textit{must} be short since it is hard to gather together these experts for more than a very short period of time. The DDP tool supports a graphical interface for the rapid entry of the assertions. Such rapid entry is essential, time is crucial and no tool should slow the debate. Therefore, DDP uses a lightweight representations for its model. Such representations are essential for early lifecycle decision making since only high-level assertions can be collected in short knowledge acquisition sessions (if the assertions get more elaborate, then experts may be unable to understand technical arguments from outside their own field of expertise). Therefore, DDP uses the following lightweight ontology: \bi \item \textit{Requirements} (free text) describing the objectives and constraints of the mission and its development process; \item \textit{Weights} (numbers) of each requirements, reflecting their relative importance; \item \textit{Risks} (free text) are events that damage requirements; \item \textit{Mitigations}: (free text) are actions that reduce risks; \item \textit{Costs}: (numbers) effort associated with mitigations, and repair costs for correcting Risks detected by Mitigations; \item \textit{Mappings}: directed edges between requirements, mitigations, and risks that capture quantitative relationships among them. \item \textit{Part-of relations} structure the collections of requirements, risks and mitigations; \ei Note that DDP models are the same as the ``requirements models'' we defined in the introduction. For examples of risks, requirements, and mitigations, see \fig{ddpegeg}. For an example of the network of connections between risks and requirements and mitigations, see \fig{DDPexample}. \begin{figure} \begin{center} \includegraphics[angle=90, height=6in,width=5in]{fig2new.png} \end{center} \caption{An example of a model formed by the DDP tool. Red lines connect risks (middle) to requirements (left). Green lines connect mitigations (right) to the risks.} \label{fig:DDPexample} \end{figure} Sometimes, we are asked if the analysis of DDP requirements models is a real problem. The usual question is something like: ``With these ultra-lightweight languages, aren't all open issues just obvious?''. Such a question is usually informed by the small model fragments that appear in the ultra-lightweight modeling literature. Those sample model fragments are typically selected according to their ability to fit on a page or to succinctly illustrate some point of the authors. Real world ultra-lightweight models can be much more complex, paradoxically perhaps due to their simplicity: if a model is easy to write then it is easy to write a lot of it. \fig{DDPexample}, for example, was generated in under a week by four people discussing one project. It is complex and densely-connected (a close inspection of the left and right hand sides of \fig{DDPexample} reveals the requirements and fault trees that inter-connect concepts in this model) and it is, by no means, the biggest or most complex DDP model that has ever been built. We base our experimentation around DDP for three reasons. Firstly, one potential drawback with ultra-lightweight models is that they are excessively lightweight and contain no useful information. DDP's models are demonstrably useful (that is, we are optimizing a real-world problem of some value). Clear project improvements have been seen from DDP sessions at JPL. Cost savings in at least two sessions have exceeded \$1 million, while savings of over \$100,000 have resulted in others~\cite{feather08}. Cost savings are not the only benefits of these DDP sessions. Numerous design improvements such as savings of power or mass have come out of DDP sessions. Likewise, a shifting of risks has been seen from uncertain architectural ones to more predictable and manageable ones. At some of these meetings, non-obvious significant risks have been identified and subsequently mitigated. Our second reason to use DDP is that we can access numerous real-world requirements models written in this format, both now and in the future. The DDP tool can be used to document not just final decisions but also to review the rationale that led to those decisions. Hence, DDP remains in use at JPL: not only for its original purpose (group decision support), but also as a design rationale tool to document decisions. Recent DDP sessions included: \bi \item An identification of the challenges of intelligent systems health management (ISHM) technology maturation (to determine the most cost-effective approach to achieving maturation)~\cite{feather08b}; \item A study on the selection and planning of deployment of prototype software~\cite{feather08c}. \ei Our third, and most important reason to use DDP in our research is that the tool is representative of other requirements modeling tools in widespread use. At its core, DDP is a set of influences expressed in a hierarchy, augmented with the occasional equation. Edges in the hierarchy have weights that strengthen or weaken influences that flow along those edges. At this level of abstraction, DDP is just another form of QOC~\cite{shum94} or a quantitative variant of Mylopoulos' s qualitative soft goal graphs~\cite{mylo99}. \section{Model Inputs and Outputs} \begin{figure} ~\hrule~ {\scriptsize \begin{verbatim} #include "model.h" #define M_COUNT 2 #define O_COUNT 3 #define R_COUNT 2 struct ddpStruct { float oWeight[O_COUNT+1]; float oAttainment[O_COUNT+1]; float oAtRiskProp[O_COUNT+1]; float rAPL[R_COUNT+1]; float rLikelihood[R_COUNT+1]; float mCost[M_COUNT+1]; float roImpact[R_COUNT+1][O_COUNT+1]; float mrEffect[M_COUNT+1][R_COUNT+1]; }; ddpStruct *ddpData; void setupModel(void) { ddpData = (ddpStruct *) malloc(sizeof(ddpStruct)); ddpData->mCost[1]=11; ddpData->mCost[2]=22; ddpData->rAPL[1]=1; ddpData->rAPL[2]=1; ddpData->oWeight[1]=1; ddpData->oWeight[2]=2; ddpData->oWeight[3]=3; ddpData->roImpact[1][1] = 0.1; ddpData->roImpact[1][2] = 0.3; ddpData->roImpact[2][1] = 0.2; ddpData->mrEffect[1][1] = 0.9; ddpData->mrEffect[1][2] = 0.3; ddpData->mrEffect[2][1] = 0.4; } void model(float *cost, float *att, float m[]) { float costTotal, attTotal; ddpData->rLikelihood[1] = ddpData->rAPL[1] * (1 - m[1] * ddpData->mrEffect[1][1]) * (1 - m[2] * ddpData->mrEffect[2][1]); ddpData->rLikelihood[2] = ddpData->rAPL[2] * (1 - m[1] * ddpData->mrEffect[1][2]); ddpData->oAtRiskProp[1] = (ddpData->rLikelihood[1] * ddpData->roImpact[1][1]) + (ddpData->rLikelihood[2] * ddpData->roImpact[2][1]); ddpData->oAtRiskProp[2] = (ddpData->rLikelihood[1] * ddpData->roImpact[1][2]); ddpData->oAtRiskProp[3] = 0; ddpData->oAttainment[1] = ddpData->oWeight[1] * (1 - minValue(1, ddpData->oAtRiskProp[1])); ddpData->oAttainment[2] = ddpData->oWeight[2] * (1 - minValue(1, ddpData->oAtRiskProp[2])); ddpData->oAttainment[3] = ddpData->oWeight[3] * (1 - minValue(1, ddpData->oAtRiskProp[3])); attTotal = ddpData->oAttainment[1] + ddpData->oAttainment[2] + ddpData->oAttainment[3]; costTotal = m[1] * ddpData->mCost[1] + m[2] * ddpData->mCost[2]; *cost = costTotal; *att = attTotal; } \end{verbatim}} ~\hrule~ \caption{A trivial DDP model after knowledge compilation} \label{fig:ddpExample} \end{figure} Before describing experimental comparisons of different methods for generating decision ordering diagrams, we will first offer more details on the DDP models. \subsection{Pre-Processing} To enable fast runtimes, a simple compiler exports the DDP models into a form accessible by our algorithms. This compiler stores a flattened form of the DDP requirements tree. In our compiled form, all computations are performed once and added as a constant to each reference of the requirement. For example, the compiler converts the trivial model of \eq{mod1} into {\tt setupModel} and {\tt model} functions similar to those in \fig{ddpExample}. The {\tt setupModel} function is called only once and sets several constant values. The {\tt model} function is called whenever new cost and attainment values are needed. The topology of the mitigation network is represented as terms in equations within these functions. As our models grow more complex, so do these equations. For example, our biggest model, which contains 99 mitigations, generates 1427 lines of code. \fig{ddpModels} compares the largest model to four other real-world DDP models. \begin{figure}[!t] \small \begin{center} \begin{tabular}{|c|r|r|r|c|c|} \hline Model&LOC&Objectives&Risks&Mitigations\\ \hline model1.c& 55 &3 &2 &2 \\ \hline model2.c& 272 &1 &30 &31 \\ \hline model3.c& 72 &3 &2 &3 \\ \hline model4.c& 1241 &50 &31 &58 \\ \hline model5.c&1427 &32 &70 &99 \\ \hline \end{tabular} \end{center} \caption{Details of Five DDP Models. } \label{fig:ddpModels} \end{figure} Currently it takes about two seconds to compile a model with 50 requirements, 31 risks, and 58 mitigations. This compilation only has to happen once, after which we will run our $2^{|d|}$ what-if scenarios. While this is not a significant bottleneck, the current compiler (written in unoptimized Visual Basic code) can certainly be sped up. Experts usually change a small portion of the model then run $2^{|d|}$ what-if scenarios to understand the impact of that change. Therefore, an incremental compiler (that only updates changed portions) would run much faster than a full compilation of the entire DDP model. \subsection{Objective Function}\label{sec:of} When the {\tt model} function is called, a pairing of the total cost of the selected mitigations and the number of reachable requirements (attainment) is returned. All of our algorithms then use that information to obtain a ``score'' for the current set of mitigations. The two numbers are normalized to a single score that represents the distance to a {\em sweet spot} of maximum requirement attainment and minimum cost: \begin{equation}\label{eq:score} score = \sqrt{\overline{cost}^2 + (\overline{attainment}-1)^2} \end{equation} Here, $\overline{x}$ is a normalized value $0 \le \frac{x - min(x)}{max(x) - min(x)} \le 1$. Hence, our scores ranges $0 \le score \le 1$ and {\em higher} scores are {\em better}. \subsection{Decision Ordering Diagrams}\label{sec:dod} The objective function described above summarizes {\em one} call to a DDP model. This section describes {\em decision ordering diagrams}, which are a tool for summarizing the results of thousands of calls to DDP models. Consider some recommendation for changes to a project that requires decisions $d$ of size $|d|$. In the general case, $d$ is a subset of the space of all solutions $D$ ($d \subseteq D$). When checking for solution robustness, or reflecting over modifications to $d$, a stakeholder may need to consider up to $d'\subseteq N^{|d|}$ possibilities (and $N=2$ for binary decisions of the form ``should I or should I not do this''). This can be a slow process, especially if evaluating each decision requires invoking a complex and slow simulator. Decision ordering diagrams are a linear time method for studying the robustness and neighborhood of a set of decisions. The diagrams assume that some method could offer a {\em linear ordering} of the decisions $x \in d$ ranked from {\em most-important} to {\em least-important}. They also assume that some method offers information on the effects of applying the top-ranked $1\le x \le |d|$ decisions (e.g. the median and variance seen in the model's objective function after applying solution \mbox{$\{d_1 .. d_x\}$}). For example, the {\em decision ordering diagram} of \fig{actiono} shows such a linear ordering (this figure presents $benefit$ and $cost$ results). In that figure: \bi \item The x-axis denotes the number of decisions made. \item The y-axis shows performance statistics of an objective function seen after imposing the conjunction of decisions $1 \le i \le x$. \ei For performance, we run some objective function and report the median (50th percentile) and {\em spread} (the range given by the 75th percentile - the 50th percentile). We use median and spread to avoid any parametric assumptions. \begin{figure}[!t] \begin{center} \includegraphics[width=3in]{dod.png} \end{center} \caption{A Decision Ordering Diagram. The median and spread plots show 50\%-the percentile and the (75-50)\%-th percentile range (respectively) values generated from some objective function.}\label{fig:actiono} \end{figure} These diagrams can comment on the robustness and neighborhood of solution $\{d_1.. d_x\}$ as follows: \bi \item By considering the variance of the performance statistics after applying $\{d_1 .. d_x\}$. \item By comparing the results of using the first $x$ decisions to that of using the first $x-1$ or $x+1$ actions. \ei The neighborhood of a solution that uses decisions $\{d_1..d_x\}$ are solutions that use the decisions $\{d_1..d_{x\pm j}\}$. Since $j$ is bounded $0 \le |d|-1$, this means that {\em reflecting over solution neighborhoods takes time linear on the number of decisions $d$}. Decision ordering diagrams are a natural representation for ``trade studies,'' the activity of a multidisciplinary team to identify the most balanced technical solution among a set of proposed viable solutions~\cite{faa06}. For example, minimum costs and maximum benefits are achieved at point $x_2$ of \fig{actiono}. However, after applying only half the decisions (see $x_1$) most of the benefits could be achieved, albeit at a somewhat higher cost. Decision ordering diagrams are {\em useful} under at least three conditions: \bi \item The scores output by the objective functions are {\em well-behaved}; i.e. move smoothly to a plateau. \item The decisions {\em tame} the variance; i.e. the spread falls to value much lower than then median (otherwise, it is hard to show that decisions have any effect on the system performance). \item The are generated in a {\em timely} manner. Fast runtimes are required in order to keep up with fast moving discussion. \ei According to these definitions, \fig{actiono} is a {\em useful} decision ordering diagram if it can be generated in a {\em timely} manner. It is an open issue if real worlds requirements models generate useful decision ordering diagrams. The following experiments test if, in practice, decision ordering diagrams generated from real world requirements models are {\em timely} to generate while being {\em well-behaved} and {\em tame}. \section{Searching for Solutions} Our experiments compare the results of numerous algorithms. We selected these comparison algorithms with much care. Numerous researchers have stressed the difficulties associated with comparing radically different algorithms. For example, Uribe and Stickel~\cite{uribe94} tried to make some general statement about the value of Davis-Putnam proof (DP) procedures or binary-decision diagrams (BDD) for constraint satisfaction problems. In the end, they doubted that it was fair to compare algorithms that perform constraint satisfaction and no search (like BDDs) and methods that perform search and no constraint satisfaction (like DP). For this reason, model checking researchers like Holzmann (pers. communication) eschew comparisons of tools like SPIN~\cite{holzmann97}, which are search-based, with tools like NuSMV~\cite{nusmv}, which are BDD-based. Hence we take care to only select algorithms which are similar to KEYS. In terms of the Gu et al. survey~\cite{gu97}, our selected algorithms (simulated annealing, ASTAR and MaxWalkSat) share four properties with KEYS and KEYS2. They are each discrete, sequential, {\em unconstrained} algorithms (constrained algorithms work towards a pre-determined number of possible solutions while unconstrained methods are allowed to adjust to the goal space). For full details on simulated annealing, ASTAR, and MaxFunWalk, see below. We observe that these algorithms share the property that at each step of their processing, they comment on all model inputs. KEYS2, on the other hand, explores the consequences of setting only a subset of the possible inputs. \subsection{SA: Simulated Annealing} Simulated Annealing is a classic stochastic search algorithm. It was first described in 1953~\cite{metropolis53} and refined in 1983 ~\cite{kirkpatrick83}. The algorithm's namesake, annealing, is a technique from metallurgy, where a material is heated, then cooled. The heat causes the atoms in the material to wander randomly through different energy states and the cooling process increases the chances of finding a state with a lower energy than the starting position. \begin{figure} ~\hrule~ {\scriptsize \begin{verbatim} 1. Procedure SA 2. MITIGATIONS:= set of mitigations 3. SCORE:= score of MITIGATIONS 4. while TIME < MAX_TIME && SCORE < MIN_SCORE //minScore is a constant score (threshold) 5. find a NEIGHBOR close to MITIGATIONS 6. NEIGHBOR_SCORE:= score of NEIGHBOR 7. if NEIGHBOR_SCORE > SCORE 8. MITIGATIONS:= NEIGHBOR 9. SCORE:= NEIGHBOR_SCORE 10. else if prob(SCORE, NEIGHBOR_SCORE, TIME, temp(TIME, MAX_TIME)) > RANDOM) 11. MITIGATIONS:= NEIGHBOR 12. SCORE:= NEIGHBOR_SCORE 13. TIME++ 14. end while 15. return MITIGATIONS \end{verbatim} } ~\hrule~ \caption{Pseudocode for SA} \label{fig:simplesa} \end{figure} For each round, SA ``picks'' a neighboring set of mitigations. To calculate this neighbor, a function traverses the mitigation settings of the current state and randomly flips those mitigations (at a 5\% chance). If the neighbor has a better score, SA will move to it and set it as the current state. If it isn't better, the algorithm will decide whether to move to it based on the mathematical function: \begin{equation}\label{eq:ps1}\small prob(w,x,y,temp(y,z)) = e^{((w-x) * \frac{y}{temp(y,z)})} \end{equation} \begin{equation}\label{eq:ps}\small temp(y,z) = \frac{(z-y)}{z} \end{equation} If the value of the {\tt prob} function is greater than a randomly generated number, SA will move to that state anyways. This randomness is the very cornerstone of the Simulated Annealing algorithm. Initially, the ``atoms'' (current solutions) will take large random jumps, sometimes to even sub-optimal new solutions. These random jumps allow simulated annealing to sample a large part of the search space, while avoiding being trapped in local minima. Eventually, the ``atoms'' will cool and stabilize and the search will converge to a simple hill climber. As shown in line 4 of \fig{simplesa}, the algorithm will continue to operate until the number of tries is exhausted or a score meets the threshold requirement. \subsection{MaxFunWalk} The design of simulated annealing dates back to the 1950s. In order to benchmark our own search engine (KEYS2) against a more state-of-the-art algorithm, we implemented the variant of MaxWalkSat described below. WalkSat is a local search method designed to address the problem of boolean satisfiability~\cite{kautz96}. MaxWalkSat is a variant of that algorithm that applies weights to each clause in a conjunctive normal form equation~\cite{selman96}. While WalkSat tries to satisfy the entire set of clauses, MaxWalkSat tries to maximize the sum of the weights of the satisfied clauses. In one respect, both algorithms can be viewed as a variant of simulated annealing. Whereas simulated annealing always selects the next solution randomly, the WalkSat algorithms will {\em sometimes} perform random selection while, other times, conduct a local search to find the next best setting to one variable. \begin{figure} ~\hrule~ {\scriptsize \begin{verbatim} 1. Procedure MaxFunWalk 2. for TRIES:=1 to MAX-TRIES 3. SELECTION:=A randomly generate assignment of mitigations 4. for CHANGED:=1 to MAX-CHANGES 5. if SCORE satisfies THRESHOLD return 6. CHOSEN:= a random selection of mitigations from SELECTION 7. with probability P 8. flip a random setting in CHOSEN 9. with probability (P-1) 10. flip a setting in CHOSEN that maximizes SCORE 11. end for 12. end for 13. return BESTSCORE \end{verbatim} } ~\hrule~ \caption{Pseudocode for MaxFunWalk} \label{fig:MWF} \end{figure} MaxFunWalk is a generalization of MaxWalkSat: \bi \item MaxWalkSat is defined over CNF formulae. The success of a collection of variable settings is determined by how many clauses are ``satisfiable'' (defined using standard boolean truth tables). \item MaxWalkFun, on the other hand, assumes that there exist an arbitrary function that can assess a collection of variable settings. Here, we use the DDP model as a assessment function. \ei Note that $MaxWalkFun=MaxWalkSat$ if the assessment is conducted via a logical truth table. The MaxFunWalk procedure is shown in \fig{MWF}. When run, the user supplies an ideal cost and attainment. This setting is normalized, scored, and set as a goal threshold. If the current setting of mitigations satisfies that threshold, the algorithm terminates. MaxFunWalk begins by randomly setting every mitigation. From there, it will attempt to make a {\em single} change until the threshold is met or the allowed number of changes runs out (100 by default). A random subset of mitigations is chosen and a random number P between 0 and 1 is generated. The value of P will decide the form that the change takes: \bi \item P$\le\alpha$: A stochastic decision is made. A setting is changed completely at random within the set CHOSEN. \item P$>\alpha$: Local search is utilized. Each mitigation in CHOSEN is tested until one is found that improves the current score. \ei The best setting of $\alpha$ is domain-specific. For this study, we used $\alpha=0.3$. If the threshold is not met by the time that the allowed number of changes is exhausted, the set of mitigations is completely reset and the algorithm starts over. This measure allows the algorithm to avoid becoming trapped in local maxima. For the DDP models, we found that the number of retries has little effect on solution quality. If the threshold is never met, MaxFunWalk will reset and continue to make changes until the maximum number of allowed resets is exhausted. At that point, it will return the best settings found. As an additional measure to improve the results found by MaxFunWalk, a heuristic was implemented to limit the number of mitigations that could be set at one time. If too many are set, the algorithm will turn off a few in an effort to bring the cost factor down while minimizing the effect on the attainment. \subsection{A* (ASTAR)} A* is a best-first path finding algorithm that uses distance from origin ($G$) and estimated cost to goal ($H$) to find the best path~\cite{hart68}. The algorithm is widely used~\cite{pearl84,norvig03,stout97,hui04}. A* is a natural choice for DDP optimization since the objective function described above is actually a Euclidean distance measure to the desired goal of maximum attainment and minimum costs. Hence, for the second potion of the ASTAR heuristic, we can make direct use of \eq{score}. The ASTAR algorithm keeps a {\em closed} list in order to prevent backtracking. We begin by adding the starting state to the closed list. In each ``round,'' a list of neighbors is populated from the series of possible states reached by making a change to a single mitigation. If that neighbor is not on the closed list, two calculations are made: \bi \item G = Distance from the start to the current state plus the additional distance between the current state and that neighbor. \item H = Distance from that neighbor to the goal (an ideal spot, usually 0 cost and a high attainment). For DDP models, we use \eq{score} to compute H. \ei The {\em best} neighbor is the one with the lowest F=G+H. The algorithm ``travels'' to that neighbor and adds it to the closed list. Part of the optimality of the A* algorithm is that the distance to the goal is underestimated. Thus, the final goal is never actually reached by ASTAR. Our implementation terminates once it stops finding better solutions for a total of ten rounds. This number was chosen to give ample time for ASTAR to become ``unstuck'' if it hits a corner early on. \begin{figure} ~\hrule~ {\scriptsize \begin{verbatim} 1. Procedure ASTAR 2. CURRENT_POSITION:= Starting assignment of mitigations 3. CLOSED[0]:= Add starting position to closed list 4. 5. while END:= false 6. NEIGHBOR_LIST:=list of neighbors 7. for each NEIGHBOR in NEIGHBOR_LIST 8. if NEIGHBOR is not in CLOSED 9. G:=distance from start 10. H:=distance to goal 11. F:=G+H 12. if F 1,000,000$ possible consistent states. %However, in the context of %$input_i\vdash~goal$, %those 1,000,000 states clumps to just the following two states: %$\{input_1,f,g,h,i,j,goal\}$ or %$\{input_2,k,\neg g,l,m,\neg j,goal\}$. % As documented in our {\em Related Work} section, this notion of $keys$ has been discovered and rediscovered many times by many researchers. Historically, finding the keys has seen to be a very hard task. For example, finding the keys is analogous to finding the {\em minimal environments} of DeKleer' ATMS algorithm~\cite{deKleer86}. Formally, this {\em logical abduction}, which is an NP-hard task~\cite{by91}. Our method for finding the keys uses a Bayesian sampling method. If a model contains keys then, by definition, those variables must appear in all solutions to that model. If model outputs are scored by some oracle, then the key variables are those with ranges that occur with very different frequencies in high/low scored model outputs. Therefore, we need not search for the keys- rather, we just need to keep frequency counts on how often ranges appear in $best$ or $rest$ outputs. KEYS contains an implementation of this Bayesian sampling method. It has two main components - a greedy search and the BORE ranking heuristic. The greedy search explores a space of $M$ mitigations over the course of $M$ ``eras.'' Initially, the entire set of mitigations is set randomly. During each era, one more mitigation is set to $M_i=X_j$, $X_j \in \{true,false\}$. In the original version of KEYS~\cite{promise08}, the greedy search fixes one variable per era. A newer variant, KEYS2, fixes an increasing number of variables as the search progresses (see below for details). In KEYS (and KEYS2), each era $e$ generates a set $$ as follows: \be \item[1:] $MaxTries$ times repeat: \bi \item $Selected[1{\ldots}(e-1)]$ are settings from previous eras. \item $Guessed$ are randomly selected values for unfixed mitigations. \item $Input = selected \cup guessed$. \item Call {\tt model} to compute $score=ddp(input)$; \ei \item[2:] The $MaxTries$ $score$s are divided into $\beta$\% ``best'' and remainder become ``rest''. \item[3:] The $input$ mitigation values are then scored using BORE (described below). \item[4:] The top ranked mitigations (the default is one, but the user may fix multiple mitigations at once) are fixed and stored in $selected[e]$.\ee \begin{figure} ~\hrule~ {\scriptsize \begin{verbatim} 1. Procedure KEYS 2. while FIXED_MITIGATIONS != TOTAL_MITIGATIONS 3. for I:=1 to 100 4. SELECTED[1...(I-1)] = best decisions up to this step 5. GUESSED = random settings to the remaining mitigations 6. INPUT = SELECTED + GUESSED 7. SCORES= SCORE(INPUT) 8. end for 9. for J:=1 to NUM_MITIGATIONS_TO_SET 10. TOP_MITIGATION = BORE(SCORES) 11. SELECTED[FIXED_MITIGATIONS++] = TOP_MITIGATION 12. end for 13. end while 14. return SELECTED \end{verbatim} } ~\hrule~ \caption{Pseudocode for KEYS} \label{fig:KEYS} \end{figure} The search moves to era $e+1$ and repeats steps 1,2,3,4. This process stops when every mitigation has a setting. The exact settings for $MaxTries$ and $\beta$ must be set via engineering judgment. After some experimentation, we used $MaxTries=100$ and $\beta=10$. For full details, see \fig{KEYS}. KEYS ranks mitigations using a support-based Bayesian ranking measure called BORE. BORE ~\cite{clark05} (short for ``best or rest'') divides numeric scores seen over $K$ runs and stores the top 10\% in $best$ and the remaining 90\% scores in the set $rest$ (the $best$ set is computed by studying the delta of each score to the best score seen in any era). It then computes the probability that a value is found in $best$ using Bayes theorem. The theorem uses evidence $E$ and a prior probability $P(H)$ for hypothesis $H\in\{best, rest\}$, to calculate a posteriori probability $P(H|E)=P(E|H) P(H)\; /\; P(E)$. When applying the theorem, {\em likelihoods} are computed from observed frequencies. These likelihoods (called "like" below) are then normalized to create probabilities. This normalization cancels out $P(E)$ in Bayes theorem. For example, after $K=10,000$ runs are divided into 1,000 {\em best} solutions and 9,000 {\em rest}, the value \mbox{$mitigation31=false$} might appear 10 times in the $best$ solutions, but only 5 times in the $rest$. Hence:\newline \begin{minipage}{1.0\linewidth} {\scriptsize \begin{eqnarray}\nonumber E&=& (mitigation31=false)\\\nonumber P(best)&=&1000/10000 = 0.1\\\nonumber P(rest)&=&9000/10000 = 0.9\\\nonumber freq(E|best)&=&10/1000 = 0.01\\\nonumber freq(E|rest)&=&5/9000 = 0.00056\\\nonumber like(best|E)&=&freq(E|best) \cdot P(best)=0.001\\\nonumber like(rest|E)&=&freq(E|rest) \cdot P(rest)= 0.000504\\\label{eq:ten} P(best|E)&=& \frac{like(best|E)}{like(best|E) + like(rest|E)}=0.66 \end{eqnarray}} \end{minipage}\newline Previously~\cite{clark05}, we have found that Bayes theorem is a poor ranking heuristic since it is easily distracted by low frequency evidence. For example, note how the probability of $E$ belonging to the best class is moderately high even though its support is very low; i.e. $P(best|E)=0.66$ but $freq(E|best) = 0.01$. To avoid the problem of unreliable low frequency evidence, we augment \eq{ten} with a support term. Support should $increase$ as the frequency of a value $increases$, i.e. $like(best|E)$ is a valid support measure. Hence, step 3 of our greedy search ranks values via \begin{equation}\label{eq:ps3}\small P(best|E) * support(best|E) = \frac{like(best|E)^2}{like(best|E) + like(rest|E)} \end{equation} For each era, KEYS samples the DDP models and fixes the top $N=1$ settings. KEYS2 assigns progressively larger values. In era 1, KEYS2 behaves exactly the same as KEYS while in (say) era 3, KEYS2 will fix the top 3 ranked ranges. Since it sets more variables at each era, KEYS2 terminates earlier than KEYS. Note that decision ordering diagrams could be directly generated during execution, just by collection statistics from the {\tt SCORES} array used in line 7 of \fig{KEYS}. \section{Results} Each of the above algorithms was tested on the five models of \fig{ddpModels}. Note that: \bi \item Models one and three are trivially small. They were used them to debug our code, but not in the core experiments. We report our results using models two, four and five since they are large enough to stress test real-time optimization. \item Model 4 was discussed in~\cite{me03n} in detail. The largest, model 5 was optimized previously in ~\cite{fea02a}. At that time (2002), it took 300 seconds to generate solutions using our old, very slow, rule learning method. \ei We also studied how well KEYS and KEYS2 scale to larger models. Further, we instrumented KEYS and KEYS2 to generate decision ordering diagrams. The results from all of these experiments are shown below. \subsection{Attainment and Costs} We ran all of our algorithms 1000 times on each model. This number was chosen because it yielded enough data points to give a clear picture of the span of results. At the same time, it is a low enough number that we can generate a set of results in a fairly short time span. \begin{figure}[!b]\centering \begin{center}\scriptsize \begin{tabular}{c@{}c@{}c@{~}c} &Model 2&Model 4 &Model 5 \\ & (31 mitigations)& (58 mitigations)&(99 mitigations)\\ \hline \begin{sideways}~~~~~~~~SA\end{sideways}& \includegraphics[width=4.25cm]{WithLabel/2/SA.pdf} & \includegraphics[width=4cm]{WithLabel/4/SA.pdf} & \includegraphics[width=4cm]{WithLabel/5/SA.pdf} \\\hline \begin{sideways}~~MaxFunWalk\end{sideways}& \includegraphics[width=4.25cm]{WithLabel/2/MaxFunWalk.pdf} & \includegraphics[width=4cm]{WithLabel/4/MaxFunWalk.pdf} & \includegraphics[width=4cm]{WithLabel/5/MaxFunWalk.pdf} \\ \hline \begin{sideways}~~~~~~ASTAR\end{sideways}& \includegraphics[width=4.25cm]{WithLabel/2/AStar.pdf} & \includegraphics[width=4cm]{WithLabel/4/AStar.pdf} & \includegraphics[width=4cm]{WithLabel/5/AStar.pdf} \\ \hline \begin{sideways}~~~~~~~~KEYS\end{sideways} & \includegraphics[width=4.25cm]{WithLabel/2/KEYS.pdf} & \includegraphics[width=4cm]{WithLabel/4/KEYS.pdf} & \includegraphics[width=4cm]{WithLabel/5/KEYS.pdf} \\ \hline \begin{sideways}~~~~~~~KEYS2\end{sideways}& \includegraphics[width=4.25cm]{WithLabel/2/KEYS-L.pdf} & \includegraphics[width=4cm]{WithLabel/4/KEYS-L.pdf} & \includegraphics[width=4cm]{WithLabel/5/KEYS-L.pdf} \\ \end{tabular} \caption{1000 results of running five algorithms on three models (15,000 runs in all). The y-axis shows cost and the x-axis shows attainment. The size of each model is measured in number of mitigations. Note that better solutions fall towards the bottom right of each plot; i.e. lower costs and higher attainment. Also better solutions exhibit less variance, i.e. are clumped tighter together. \label{fig:finalModelResults} } \end{center} \end{figure} The results are pictured in ~\fig{finalModelResults}. Attainment is along the x-axis and cost (in thousands) is along the y-axis. Note that better solutions fall towards the bottom right of each plot; i.e. lower costs and higher attainment. Also, better solutions exhibit less variance; that is, the results are clumped closely together. These graphs give a clear picture of the results obtained by our various algorithms. Two methods are clearly inferior: \bi \item Simulated annealing exhibits the worst variance, lowest attainments, and highest costs. \item MaxFunWalk is better than SA (less variance, lower costs, higher attainment) but its variance is still far too high to use in any critical situation. \ei As to the others: \bi \item On larger models such as model4 and model5, KEYS and KEYS2 exhibit lower variance, lower costs, and higher attainments than ASTAR. \item On smaller models such as model2, ASTAR usually produces higher attainments and lower variance than the KEYS algorithms (this advantage disappears on the larger models). However, observe the results near the $(0,0)$ point of model2's ASTAR results: sometimes ASTAR's heuristic search failed completely for that model \ei \begin{figure}[!t] {\scriptsize \begin{center} \begin{tabular}{c|c|c|c} &Model 2~(31 mitigations)~& Model 4~(58 mitigations)~&Model 5~(99 mitigations)~\\ \hline SA& 0.577 &1.258 &0.854 \\ \hline MaxFunWalk& 0.122 &0.429 &0.398 \\ \hline ASTAR& 0.003 &0.017 &0.048 \\ \hline KEYS & 0.011 &0.053 &0.115 \\ \hline KEYS2 &0.006 &0.018 &0.038 \\ \end{tabular} \end{center} }\caption{ Runtimes in seconds, averaged over 100 runs, measured using the ``real time'' value from the Unix {\tt times} command. The size of each model is measured in number of mitigations (and for more details on model size, see \fig{ddpModels}). } \label{fig:runtimes} \end{figure} \subsection{Runtime Analysis}\label{sec:runtimea} Measured in terms of attainment and cost, there is little difference between KEYS and KEYS2. However, as shown by \fig{runtimes}, KEYS2 runs twice to three times as fast as its predecessor. Interestingly, \fig{runtimes} ranks two of the algorithms in a similar order to \fig{finalModelResults}: \bi \item Simulated annealing is clearly the slowest; \item MaxFunWalk is somewhat better but not as fast as the other algorithms. \ei As to ASTAR versus KEYS or KEYS2: \bi \item ASTAR is faster than KEYS; \item and KEYS2 runs in time comparable to ASTAR. \ei Measured purely in terms of runtimes, there is little to recommend KEYS2 over ASTAR. However, ASTAR's heuristic guesses were sometimes observed to be sub-optimal (recall the above discussion on the $(0,0)$ results in model2's ASTAR results). Such sub-optimality was never observed for KEYS2. \subsection{Scale-Up Studies}\label{sec:scaleup} \fig{scaleupruntimes} and \fig{scaleupmodelcalls} shows the effect of changing the size of the model on the number of times that the model is asked to generate a score for both KEYS and KEYS2. To generate these graph, an {\em instance generator} was created that: \bi \item Examined the real-world DDP models of \fig{ddpModels}; \item Extracted statistics related to the different types of nodes (mitigations or risks or requirements) and the number of edges between different types of nodes; \item Used those statistics to build random models that were 1,2,4 and 8 times larger than the original models. \ei \begin{figure}[!t] \begin{minipage}{.6\linewidth} {\scriptsize \begin{tabular}{c|c|r|r|r|r|} \multicolumn{3}{c}{~}& \multicolumn{2}{|c|}{Runtime (secs)}&$\frac{\mbox{KEYS}}{\mbox{KEYS2}}$\\\cline{4-5} model & expansion & model size & KEYS & KEYS2 & \\\hline 2&1&62&0.01&0.01&1.07\\ 2&2&124&0.03&0.02&1.23\\ 4&1&139&0.04&0.02&2.29\\ 5&1&201&0.13&0.04&3.18\\ 2&4&248&0.10&0.05&2.09\\ 4&2&278&0.17&0.05&3.48\\ 5&2&402&0.50&0.12&4.26\\ 2&8&496&0.44&0.14&3.21\\ 4&4&556&0.73&0.16&4.66\\ 5&4&804&1.98&0.38&5.21\\ 4&8&1112&2.97&0.52&5.71\\ 5&8&1608&8.06&1.35&5.96 \end{tabular}} \end{minipage}\begin{minipage}{.4\linewidth} \includegraphics[width=1.75in]{scaleupruntimes.pdf} \end{minipage} \caption{Runtimes KEYS vs KEYS2 (medians over 1000 repeats) as models increase in size. The ``model'' number in column one corresponds to \fig{ddpModels}. The ``expansion factor'' of column two shows how much the instance generator expanded the model. The ``model sizes'' of column three are the sum of mitigations, requirements, and risks seen in the expanded model. }\label{fig:scaleupruntimes} \end{figure} \begin{figure}[!t] \begin{minipage}{.6\linewidth} {\scriptsize \begin{tabular}{c|c|r|r|r|r|} \multicolumn{3}{c}{~}& \multicolumn{2}{|c|}{Calls to {\tt model}}&$\frac{\mbox{KEYS}}{\mbox{KEYS2}}$\\\cline{4-5} model & expansion & model size & KEYS & KEYS2 & \\\hline 2&1&62&3100&800&3.9\\ 2&2&124&6200&1100&5.6\\ 4&1&139&5800&1100&5.3\\ 5&1&201&9900&1400&7.1\\ 2&4&248&12400&1600&7.8\\ 4&2&278&11600&1500&7.7\\ 5&2&402&19800&2000&9.9\\ 2&8&496&24800&2200&11.3\\ 4&4&556&23200&2200&10.5\\ 5&4&804&39600&2800&14.1\\ 4&8&1112&46400&3000&15.5\\ 5&8&1608&79200&4000&19.8 \end{tabular} } \end{minipage}\begin{minipage}{.4\linewidth} \includegraphics[width=1.75in]{scaleupcalls.pdf} \end{minipage} \caption{Number of model calls made by KEYS vs KEYS2 (medians over 1000 results) as models increase in size. This figure uses the same column structure as \fig{scaleupruntimes}. }\label{fig:scaleupmodelcalls} \end{figure} \begin{figure}[!t] {\footnotesize \begin{center} \begin{tabular}{r|r|r|r|r|} \multicolumn{1}{c}{~} &\multicolumn{2}{c}{KEYS} &\multicolumn{2}{c}{KEYS2}\\\cline{2-5} &runtimes &model calls &runtimes &model calls\\\hline exponential &0.82 &0.83 & 0.88& 0.93\\\hline polynomial (of degree 2)&0.99& 0.99 & 0.99& 0.98\\ \end{tabular} \end{center} } \caption{Coefficients of determination $R^2$ of KEYS/KEYS2 performance figures, fitted to two different functions: exponential or polynomial of degree two. Higher values indicate a better curve fit. In all cases, the best fit is not exponential. }\label{fig:fits} \end{figure} \fig{fits} shows the results of curve fitting to the plots of \fig{scaleupruntimes} and \fig{scaleupmodelcalls}. The KEYS and KEYS2 performance curves fit a low-order polynomial (of degree two) with very high coefficients of determination ($R^2\ge 0.98$). \fig{fits} suggests that we could scale {\em either} KEYS or KEYS2 to larger models. However we still recommend KEYS2. The column marked $\frac{KEYS}{KEYS2}$ in \fig{scaleupmodelcalls} shows the ratio of the number of calls made by KEYS vs KEYS2. As models get larger, the number of calls to the model are an order of magnitude greater in KEYS than in KEYS2. If applied to models with slower runtimes than DDP, then this order of magnitude is highly undesirable. \subsection{Decision Ordering Algorithms} \begin{figure} \begin{center} \noindent \includegraphics[width=5in]{model2.pdf} \noindent {\bf \fig{in5}a:} Internal Decisions on Model 2. \noindent ~\\ \noindent \includegraphics[width=5in]{model4.pdf} \noindent {\bf \fig{in5}b:} Internal Decisions on Model 4. \noindent ~\\ \noindent \includegraphics[width=5in]{model5.pdf} {\bf \fig{in5}c:} Internal Decisions on Model 5. \end{center} \caption{Median and spread of partial solutions learned by KEYS and KEYS2. X-axis shows the number of decisions made. ``Median'' shows the 50-th percentile of the measured value seen in 100 runs at each era. ``Spread'' shows the difference between the 75th and 50th percentile. } \label{fig:in5} \end{figure} The decision ordering diagrams of \fig{in5} show the effects of the decisions made by KEYS and KEYS2. For both algorithms, at $x=0$, all of the mitigations in the model are set at random. During each subsequent era, more mitigations are fixed (KEYS sets one at a time, KEYS2 an incrementally increasing number). The lines in each of these plots show the median and spread seen in the 100 calls to the {\tt model} function during each round. Note that the these diagrams are {\em tame} and {\em well-behaved}: \bi \item {\em Tame:} The "spread" values quickly shrink to a small fraction of the median. \item {\em Well-behaved:} The median values move smoothly to a plateau of best performance (high attainment, low costs). \ei On termination (at maximum value of $x$), KEYS and KEYS2 arrive at nearly identical median results (caveat: for model2, KEYS2 attains slightly more requirements at a slightly higher cost than KEYS). The spread plots for both algorithms are almost indistinguishable (exception: in model2, the KEYS2 spread is less than KEYS). That is, KEYS2 achieves the same results as KEYS, but (as shown in \fig{runtimes} and \fig{scaleupruntimes}) it does so in less time. A core assumption of this work is the ``keys'' concept; i.e. a small number of variables set the remaining model variables. \fig{in5} offers significant support for this assumption: observe how most of the improvement in costs and attainments were achieved after KEYS and KEYS2 made only a handful of decisions (often ten or fewer). On another matter, it is insightful to reflect on the effectiveness of different algorithms for generating decision ordering diagrams. KEYS2 is the most direct and fastest method. As mentioned above, all of the required information can be collected during one execution. On the other hand, simulated annealing, ASTAR, and MaxWalkSat would require a post-processor to generate the diagrams: \bi \item Given $D$ possible decisions, At each era, KEYS and KEYS2 collects statistics on partial solutions where $1,2,3,..|d|$ variables are fixed (where $d$ is the set of decisions) while the remaining $D-d$ decisions are made at random. \item ASTAR, Simulated Annealing, and MaxFunWalk work with full solutions since at each step they offer settings to all $d_i\in D$ variables. In the current form, they cannot comment on partial solutions. Modified forms of these algorithms could add in extra instrumentation and extra post-processing to comment on partial solutions using methods like feature subset selection~\cite{hall03} or a sensitivity analysis~\cite{saltelli00}. \ei \section{Related Work} \subsection{Early vs Later Life-cycle Requirements Engineering}\label{sec:emod} The case studies presented in this paper come from the NASA Jet Propulsion Lab's Team X meetings. Team X conducts early life-cycle requirement discussions. Once a system is running, released, and being maintained or extended, another problem is {\em release planning}; i.e. what features to add to the next $N$ releases. To solve this problem, an inference engine must reason about how functionality extensions to current software can best satisfy outstanding stakeholder requirements. The challenge of release planning is that the benefits of added functionality must be weighed against the cost of implementing those extensions. Several approaches have been applied to this problem including: \bi \item The OPTIMIZE tool of Ngo-The and Ruhe~\cite{ruhe09}, which combines linear programming with genetic programming to optimize release plans for software projects \item The weighted Pareto optimal genetic algorithm approach of Zhang et al.~\cite{zhang07} \ei (See also the earlier comparison of exact vs greedy algorithms by Bagnall et al.~\cite{bagnall01}). Without further experimentation, we cannot assert that KEYS2 will work as well on later life-cycle models (such as those used in release planning) as it did above (on the earlier life-cycle Team X models). However, at this time, we can see no reason why KEYS2 would not work as a non-linear optimizer of these later life-cycle models. This could be a productive area for future work. \subsection{Other Optimizers}\label{sec:oo} As documented by the search-based SE literature~\cite{clarke03,harman01,harman04,rela04} and Gu et al~\cite{gu97}, there are many possible optimization methods. For example: \bi \item Gradient descent methods assume that an objective function $F(X)$ is differentiable at any single point $N$. A Taylor-series approximation of $F(X)$ can be shown to decrease fastest if the negative gradient ($-\Delta F(N)$) is followed from point $N$. \item Sequential methods run on one CPU while parallel methods spread the work over a distributed CPU farm. \item Discrete methods assume model variables have a finite range (that may be quite small) while continuous methods assume numeric values with a very large (possibly infinite) range. \item The search-based SE literature prefers meta-heuristic methods like simulated annealing, genetic algorithms and tabu search. \item Some methods map discrete values true/false into a continuous range 1/0 and then use integer programming methods like CPLEX~\cite{mittle07} to achieve results. \item Other methods find overlaps in goal expressions and generate a binary decision diagram (BDD) where parent nodes store the overlap of children nodes. \ei This list is hardly exhaustive: Gu et al. list hundreds of other methods and no single paper can experiment with them all. All the algorithms studied here are discrete and sequential. We are currently exploring parallel versions of our optimizers but, so far, the communication overhead outweighs the benefits of parallelism. As to the general class of gradient descent methods, we do not use them since they assume the objective function being optimizing is essentially continuous. Any model with an ``if'' statement in it is not continuous since, at the ``if'' point, the program's behavior may become discontinuous. The requirements models studied here are discontinuous about every subset of every possible mitigation. As to the more specific class of integer programming methods, we do not explore them here for two reasons. Coarfa et al.~\cite{coarfa00} found that integer programming-based approaches ran an order of magnitude slower than discrete methods like the MaxWalkSat and KEYS2 algorithms that we use. Similar results have been reported by Gu et.al where discrete methods ran one hundred times faster than integer programming~\cite{gu97}. Harman offers another reason to avoid integer programming methods. In his search-based SE manifest, Harman~\cite{harman01} argues that many SE problems are over-constrained and so there may exist no precise solution that covers all constraints. A complete solution over all variables is hence impossible and partial solution based on heuristic search methods are preferred. Such methods may not be complete; however, as Clarke et al remark, ``...software engineers face problems which consist, not in finding {\em the} solution, but rather, in engineering an {\em acceptable} or {\em near-optimal solution} from a large number of alternatives.'' ~\cite{clarke03} \subsection{Models of Requirements Engineering} DDP is a ultra-lightweight modeling tool. The value of ultra-lightweight ontologies in early life cycle modeling is widely recognized. For example Mylopoulos' {\em soft-goal} graphs~\cite{mylo92,mylo99} represent knowledge about non-functional requirements. Primitives in soft goal modeling include statements of partial influence such as {\em helps} and {\em hurts}. Another commonly used framework in the design rationale community is a ``questions-options-criteria'' (QOC) graph~\cite{shum94}. In QOC graphs: \bi \item {\em Questions} suggest {\em options}. Deciding on one option can raise other questions; \item Options shown in a box denote {\em selected options}; \item Options are assessed by {\em criteria}; \item Criteria are gradual knowledge; i.e. they {\em tend/reject to support} options. \ei QOCs can succinctly summarize lengthy debates; e.g. the 480 sentences uttered in a debate on interface options can be displayed in a QOC graph on a single page~\cite{maclean96}. Saaty's Analytic Hierarchy Process (AHP)~\cite{saaty80} is a variant of QOC. While DDP shares many of the design aspects of softgoals \& QOC \& AHP, it differs in its representations and inference method. As explained above around \eq{mod1}, where as AHP and QOC and softgoals propagate influences over hierarchies, DDP propagate influences over matrices. \subsection{Formal Models of Requirements Engineering}\label{sec:ffm} Zave \& Jackson~\cite{zave97} define requirements engineering as finding the specification $S$ for the domain assumptions $K$ that satisfies the given requirements $R$; i.e. \begin{equation}\label{eq:zj} \mbox{find $S$ such that~} S \vdash R \end{equation} Jureta, Mylopoulous \& Faulkner~\cite{jureta08} (hereafter JMF) take issue with \eq{zj}, saying that it implicitly assume that $K,S,R$ are precise and complete enough for the satisfaction relation to hold. More specifically, JMF complain that \eq{zj} does not permit partial fulfillment of (some) non-functional requirements. Also, the Zave\&Jackson definition does not allow any preference ordering of $specification_1$ over $specification_2$. JMF offer a replacement ontology where classical inference is replaced with operators that supports the generation and ranking of subsets of domain assumptions that lead to maximal (w.r.t. size) subsets of the possible goals, and softgoal quality criteria\footnote{According to JMF: ``a salient characteristic of softgoals is that they cannot be satisfied to the ideal extent, not only because of subjectivity, but also because the ideal level of satisfaction is beyond the resources available to (and including) the system. It is therefore said that a softgoal is not satisfied, but satisficed.''}. DDP reinterprets ``$\vdash$'' in \eq{zj} as an inference across numeric quantities, rather than the inference over discrete logical variables suggested by Zave\&Jackson. Hence, it can achieve the same goals as JMF (ranking of partial solutions with weighted goals) without requiring the JMF ontology. \subsection{Requirements Analysis Tools} There exist many powerful requirements analysis tools including continuous simulation (also called system dynamics)~\cite{hamid91,sterman00}, state-based simulation (including petri net and data flow approaches) ~\cite{akhavi93,harel90,martin00}, hybrid-simulation (combining discrete event simulation and systems dynamics)~\cite{martin01,donzelli01,setamanit07}, logic-based and qualitative-based methods~\cite[chapter 20]{bratko01}~\cite{iwasaki89}, and rule-based simulations~\cite{mi90}. One can find these models being used in the requirements phase (i.e. the DDP tool described below), design refactoring using patterns ~\cite{france03}, software integration~\cite{denno03}, model-based security~\cite{jurjens06}, and performance assessment~\cite{bals04}. Many researchers have proposed support environments to help explore the increasingly complex models that engineers are developing. Gray et al ~\cite{gray06} have developed the Constraint-Specification Aspect Weaver (C-Saw), which 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 {\em Simon} that ``supports interactive construction of formal models, derives and displays design structure matrices... and supports simple design impact analysis.'' Other tools of note are lightweight formal methods such as ALLOY ~\cite{jackson02} and SCR~\cite{heitmeyer02} as well as UML tools that allow for the execution of life cycle specifications (e.g. CADENA~\cite{child06}). Many of the above tools were built to maximize the expressive power of the representation language or the constraint language used to express invariants. What distinguishes our work is that we are {\em willing to trade off representational or constraint expressiveness for faster runtimes}. There exists a class of ultra-lightweight model languages which, as we show above, can be processed very quickly. Any of the tools listed in the last paragraph are also candidate solutions to the problem explored in this paper, if it can be shown that their processing can generate tame and well-behaved decision ordering diagrams in a timely manner. \subsection{Other Work on ``Keys''}\label{sec:keys} Elsewhere ~\cite{me03l}, we have documented dozens of papers that have reported the keys effect (that a small number of variables set the rest) under different names including {\em narrows, master-variables, back doors,} and {\em feature subset selection}: \bi \item Amarel ~\cite{Amarel86} observed that search problems contain narrow sets of variables or collars that must be used in any solution. In such a search space, what matters is not so much how you get to these collars, but what decision you make when you get there. Amarel defined macros encoding paths between {\em narrows}, effectively permitting a search engine to jump between them. \item In a similar theoretical analysis, Menzies \& Singh~\cite{me03l} computed the odds of a system selecting solutions to goals using complex, or simpler, sets of preconditions. In their simulations, they found that a system will naturally select for tiny sets of preconditions (a.k.a. the keys) at a very high probability. \item Numerous researchers have examined {\em feature subset selection}; i.e. what happens when a data miner deliberately ignores some of the variables in the training data. For example, Kohavi and John~\cite{kohavi97} showed in numerous datasets that as few as 20\% of the variables are $key$ - the remaining 80\% of variables can be ignored without degrading a learner's classification accuracy. \item Williams et.al.~\cite{williams03} discuss how to use keys (which they call ``back doors'') to optimize search. Constraining these back doors also constrains the rest of the program. So, to quickly search a program, they suggest imposing some set values on the key variables. They showed that setting the keys can reduce the solution time of certain hard problems from exponential to polytime, provided that the keys can be cheaply located, an issue on which Williams et.al. are curiously silent. \item Crawford and Baker ~\cite{crawford94} compared the performance of a complete TABLEAU prover to a very simple randomized search engine called ISAMP. Both algorithms assign a value to one variable, then infer some consequence of that assignment with forward checking. If contradictions are detected, TABLEAU backtracks while ISAMP simply starts over and re-assigns other variables randomly. Incredibly, ISAMP took {\em less} time than TABLEAU to find {\em more} solutions using just a small number of tries. Crawford and Baker hypothesized that a small set of {\em master variables} set the rest and that solutions are not uniformly distributed throughout the search space. TABLEAU's depth-first search sometimes drove the algorithm into regions containing no solutions. On the other hand, ISAMP's randomized sampling effectively searches in a smaller space. \ei In summary, the core assumption of our algorithms are supported in many domains. \section{Conclusion} Requirements tools such as the DDP tool (used at NASA for early lifecycle discussions), contain a shared group memory that stores all of the requirements, risks, and mitigations of each member of the group. Software tools can explore this shared memory to find consequences and interactions that may have been overlooked. Studying that group memory is a non-linear optimization task: possible benefits must be traded off against the increased cost of applying various mitigations. Harman~\cite{harman01} cautions that solutions to non-linear problems may be ``brittle'' - small changes to the search results may dramatically alter the effectiveness of the solution. Hence, when reporting an analysis of this shared group memory, it is vitally important to comment on the robustness of the solution. Decision ordering diagrams are a solution robustness assessment method. The diagrams rank all of the possible decisions from most-to-least influential. Each point $x$ on the diagrams shows the effects on imposing the conjunction of decisions $1 \le j \le x$. These diagrams can comment on the robustness and neighborhood of solution $\{d_1.. d_x\}$ using two operators: \be \item By considering the variance of the performance statistics after applying $\{d_1 .. d_x\}$. \item By comparing the results of using the first $x$ decisions to that of using the first $x-1$ or $x+1$ actions. \ee Since the diagrams are sorted, this analysis of robustness and neighborhood takes, at most, time linear of the number of decisions. That is, theoretically, it takes linear time to {\em use} a decision ordering diagram (see \tion{dod}). Empirically, it take low-order polynomial time to {\em generate} a decision ordering diagram using KEYS2. This algorithm makes the ``key'' assumption (that a small group of variables set everything else) and uses Bayesian ranking mechanism to quickly find those keys. As discussed above in the {\em Related Work} section, this assumption holds over a wide range of models used in a wide range of domains. This ``keys'' assumption can be remarkably effective: our empirical results show that KEY2 can generate decision ordering diagrams faster than the other algorithms studied here. Better yet, curve fits to our empirical results show that KEYS runs in low-order polynomial time (of degree two) and so should scale to very large models. Prior to this work, our two pre-experimental concerns were that: \bi \item We would need to trade solution robustness against solution quality. More robust solutions may not have the highest quality. \item Demonstrating solution robustness requires multiple calls to an analysis procedure. \ei At least for the models studied here, neither concern was realized. KEYS2 generated the highest quality solutions (lowest cost, highest attainments) and did so more quickly than the other methods. In \tion{dod} it was argued that decision ordering diagrams are useful when they are {\em timely} to generate while being {\em well-behaved} and {\em tame}. KEYS2's results are the most {\em timely} (fastest to generate) of all of the methods studied here. As to the other criteria, \fig{in5} shows that KEYS2's decision ordering diagrams: \bi \item Move smoothly to a plateau with only a small amount of ``jitter''; \item Have very low spreads, compared to the median results. \ei That is, at least for the models explored here, KEYS2 generated decision ordering diagrams they are both {\em well-behaved} and {\em tame}. In summary, we recommend KEYS2 for generating decision ordering diagrams since, apart from the (slightly slower) KEYS algorithm, we are unaware of other search-based software engineering methods that enable such a rapid reflection of solution robustness. \section{Acknowledgments} This research was conducted at West Virginia University, the Jet Propulsion Laboratory under a contract with the National Aeronautics and Space administration, Alderson-Broaddus College, and Miami University. Reference herein to any specific commercial product, process, or service by trade name, trademark, manufacturer, or otherwise, does not constitute or imply its endorsement by the United States Government \bibliographystyle{abbrv} \bibliography{refs,refsgreg} \appendix \section*{Obtaining our System} We have placed on-line all the materials required for other researchers to conduct further investigation into this problem. All the code, Makefiles, scripts, and so on used in this paper are available at \url{http://unbox.org/wisp/tags/ddpExperiment/install}. For security reasons, all the available JPL requirements models have been ``sanitized''; i.e. all words replaced with anonymous variables. \clearpage \appendix \sffamily \section*{Replies to reviewers} Thank you for your careful reviews on the first draft of this paper. On experimentation, we found that the premises of draft \#1 was wrong. It turns out that KEYS2 scales very well to larger models ($O(N^2)$). Hence, the basis of the paper change from issues of runtime to other advantages of our method. The issue of {\em exploring solution robustness} was not adequately discussed in draft \#1. Here, we focus draft \#2 on that issue. Nearly every page of this paper has been extensively rewritten and the whole paper has been shortened. \subsection*{Comments from Reviewer 1} {\em I felt that the preparatory sections built up lots of background, but the meat in the results section was skimmed over by comparison.} \begin{quote} This draft has been extensively rewritten so that we get to the ``meat'' as soon as possible. New results have been added regarding how well these methods scale to larger models (see \tion{scaleup}). In all, the conclusions of this paper are now based on three real-world requirements models from NASA and a dozen artificially generated models. As to excessive amount of background material, much has been pruned from this draft but much more could also be deleted. For example: \bi \item Sections 5.1, 5.2, 5.3 describe algorithms that have been extensively documented elsewhere in the literature. Hence, if you agree, we could cut those sections back to one paragraph each. \item In the {\em Related Work} section, we could delete sections 7.3, 74, 7.5. \ei \end{quote} {\em Fig 10 is too small to read properly.} \begin{quote} That figure has been made larger. \end{quote} {\em I missed a clear and unequivocal explanation of what the fitness function and representation were for the Simulated Annealing} \begin{quote} That has now been placed in its own section, especially marked ``objective function'' (see \tion{of}). \end{quote} {\em The work is written in a compelling and direct style (which occasionally is too direct and a little grating).... .... I liked the novel style opening "The room is crowded and everyone is talking at once.". However this may put off some readers. At present the paper is nice as a compelling read, but starting off like this really could distract the more traditional SE reader who have views about how scientific work should be presented... The colorful writing style comes up again on p17; Uribe and Stickel "struggled valiantly". I don't think that this style is suitable for an academic journal. Maybe I am old fashioned. I think it should be toned down and the style more dispassionate. Did they really struggle "valiantly" anyway? It may well put readers off and that would be a pity. } \begin{quote} That language has been removed, both in the introduction and around the discussion of Uribe and Stickel. \end{quote} {\em The authors make available their code which is helpful. It is not clear whether real world requirements data form JPL is also included in the on line provision. I would like some clarification on this issue in the revised version. Such provision would be a great help to follow on research, though I realize that for reasons of commercial confidentiality this may not be possible.} \begin{quote} Appendix A now details how to obtain this material. For security reasons, all the available JPL requirements models have been ``sanitized''; i.e. all words replaced with anonymous variables. \end{quote} {\em The authors statement:- " This is an exciting result since it means that current results from simulated annealing(e.g.[5,8,10,62,73]) could be greatly improved, just by switching to an alternate search engine. " really needs to be re-written. } \begin{quote} This new draft does not include those over-inflated claims about the merits of KEYS/KEYS2 vs simulated annealing. \end{quote} {\em Other work on SBSE for requirements that is clearly missing and needs to be included is: \bi \item The paper by Gunther Ruhe at FSE 08 \item The Zhang et al (GECCO 2007) and \item the work by Bagnall (I\&ST 2001). \ei} \begin{quote} We cannot find the Ruhe paper at the FSE'08 web site\footnote{\url{https://cgi4.cc.gatech.edu/phps/conferences/fse16/program.php}} or on his home pages (perhaps it was a last minute replacement for a keynote?). However, his 2009 TSE paper is clearly relevant so we used that instead. A curious omission in that paper is the runtimes of the GAs used in that paper. While this does not invalidate that paper, it does mean that we cannot make an extensive comment on that work to this paper. In any case, thanks to this review, we added a reference to his work in our section "Other Optimizers" section (see \tion{oo}). As to the other work on release planning, we added in notes on Ruhe, Zhang, and Bagnall's work in Related Work (see \tion{emod}). \end{quote} {\em Some of the citations are messed up too. For example citation [5] "S M B and S. Mancoridis". S M B is Brian Mitchell I believe. Clearly some more scholarly care is required here, both to chaise up relevant work and to ensure that the citations are present correctly. } \begin{quote} Thanks for catching that- the culprit was two commas together in a .bib file. That has been fixed and the other references checked. Oh- and that particular paper did not not make it into this draft. \end{quote} {\em Does Fig 4 add sufficient value to justify a whole page?} \begin{quote} (FYI: that figure has now moved to page 6). That is, of course, for you to decide. However, we often get questions along the lines of ``aren't these models so simple you can just {\em see} the problems/solutions?''. This figure shows just how complex these models can get. We can remove that figure if you feel that we have made enough of a case in the text that the JPL are hard enough to be interesting. \end{quote} {\em In related work, some recent work by Finkelstein on multi objective requirements models for fairness is missing (this was published in RE 08)} \begin{quote} In RE08, we found: \bi \item Revisiting the Core Ontology and Problem in Requirements Engineering Jureta, I.J.; Mylopoulos, J.; Faulkner, S.; International Requirements Engineering, 2008. RE '08. 16th IEEE \ei Comments on this have been added to the "Related Work" section, see \tion{ffm}. \end{quote} \subsection*{Comments from Reviewer 2} {\em The novelty of the work remains unclear. The paper presents little other (of real substance) than a small performance measurement experiment, results of which are interpreted as supporting the appropriateness of the algorithm for use in automated requirements engineering. } \begin{quote} Certainly, the previous draft was poorly written and obscured the novelty of the paper. This draft has been significantly reorganized and the relevant material moved to the front (and supporting material moved to a related work section at the back of the article). Consequently the novel features of this paper are not obscured: \bi \item A completely naive search through the space of options is exponential on the number of options. We can reduce that search to linear time using {\em decision ordering diagrams}, described in \tion{dod}. \item Better yet, we can generate those diagrams in low-order polynomial time using a Bayesian sampling method called KEYS2. \ei \end{quote} {\em The title and abstract and indeed the overall narrative of this paper are misleading. This is a paper on a small-scale runtime performance study *masquerading* as a paper on requirements analysis.} \begin{quote} We thank this reviewer for this comment- it inspired us to conduct the scale up study of \tion{scaleup}. We agree that the previous draft lacked insufficient analysis to merit journal publication. To address this concern, we have changed the title of the paper; changed the focus of the paper; and clarified and extended our analysis. We would also comment that this {\em is} a real requirements analysis paper. In fact, this new draft's empirical authority is {\em greater than} the standard requirements engineering paper. Here, we explore three real world requirements models (from NASA) as well as a dozen artificially generated models. By contrast, a standard paper in this field uses a single small (possibly ``toy'') case study. \end{quote} {\em The writing in this paper is somewhere between terrible and just plain poor: at the level of sentences, paragraphs, and overall narrative structure..... Opening scenario isn't credible. A decision as substantial as a redesign of the file system would not be made without documenting it in a way that would make everyone with an interest in that aspect of the aware of the decision....} \begin{quote} This reviewer is quite correct in complaining about the quality of the previous draft. This draft has been extensively reorganized. The bogus opening scenario has been deleted. The core of the paper has been made clearer. The paper has been extensively proof read prior to resubmission to ASE. \end{quote} {\em Critical but unexplained and unsupported assumption: Our proposed solution to real-time requirements optimization assumes that the behavior of a large system is determined by a very small number of key variables.} \begin{quote} This assumption has much supporting evidence from other domains (see \tion{keys}). Also, our empirical evidence supports it (see the comment at bottom of p20). \end{quote} \subsection*{Comments from Reviewer 3} {\em The whole discussion of the "real time requirements optimization" problem, while a nice idea and interesting, falls flat by being bogus.} \begin{quote} We agree. When we experimented with this scale up runtime costs using our models (and not using some bogus equation), we found the scale up factors to be far {\em less} than anything suggested by our formulae. So this draft has dropped that whole discussion. Instead, we focus on an issue that was poorly discussed in the previous draft: fast methods for assessing solution robustness. \end{quote} {\em First paragraph of Sec 7: Why? why is it "unfair" to compare BDD-based against search-based? Aren't they solving the same problem? } \begin{quote} Algorithm comparison is far more complicated than it first appears. We have much experience at empirical software engineering conferences where authors of method1 have cried "foul!" when authors have compared model1 against model2 using a particular problem that, by definition, is not suitable for method1. The classic example is NuSMV vs SPIN: the BDDs of NuSMV make it a natural choice for models with extensive symmetry and repeated structures. Given that you know that, should you compare NuSMV and SPIN using such models? Or are they the {\em last} thing you should use for a comparison? We have no good answer. Nor do other researchers: \bi \item Holzmann does not compare SPIN against NuSMV. \item Uribe and Stickel take great care when selecting comparative cases- and when the algorithms are too distant, they don't even do that. \ei \end{quote} {\em Sec 7.2: what is the variable "C"?} \begin{quote} (FYI: in the new draft, this section is appendix B.2.) "C" is "CHOSEN" (fixed in this draft) \end{quote} {\em I'm not sure it is valid to make claims about KEYS2 performance versus MaxWalkSAT when you are actually comparing to MaxFunWalk. You have to do a better job showing how they are related. (E.g. at what level are they the same algorithm?) } \begin{quote} Thanks for this comment- it has allowed us to clarify a confusing part of our text. MaxWalkSat is defined over CNF formulae. MaxWalkFun assumes that some function can assess a collection of variable settings. MaxWalkFun becomes MaxWalkSat when that assessment function is a logical truth table. Here, we use our DDP models as the assessment function (these notes have been added to the bottom of page 12). \end{quote} {\em Last para of Sec 9. "...some requirements models". This comes out of the blue. For which reqts models does KEYS approach fail?} \begin{quote} This section has been removed. As to the ultimate limits of KEYS2, we don't know yet. However, given the simplicity of the algorithm's implementation and its fast runtimes, we offer the following advise: try it and see. FYI, we are using it {\em all} our current projects. We have found it is a good stochastic rule generator for standard UCI data and that it out-performs standard non-linear optimizers for optimizing complex FORTRAN simulators of NASA flight systems. We are also successfully applying it to effort estimation and defect prediction. All those papers are Masters projects, currently in progress (i.e. no tech reports, or publications, yet). But in summary, KEYS2 is remarkably general and remarkably useful. \end{quote} \end{document}