\section{DDP Model}

The defect detection and prevention (DDP) approach was first invented
in 1998 by Steven Cornford, at the Jet Propulsion
Laboratory~\cite{corn98}. It is a risk-based requirements model that
assists in early life-cycle decision making to help developers select
assurance activities in a cost-effective maner. That is, maximizing
requirements attainment while minimizing mitigation costs.


\begin{figure}[!b]
~\hrule~\\

DDP assertions are either:

\bi
\item \textit{Requirements} (free text) describing the objectives
and constraints of the mission and its development process; 
\item \textit{Weights} (numbers) associated with 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. The key ones are \textit{impacts},
each one of which is a quantitative estimate of the proportion of a requirement that would be lost should a risk occur, and
\textit{effects}, each one of which is a quantitative estimate of the proportion by which a risk would be reduced were a
mitigation to be employed (the ontology is also able to capture the phenomenon of a mitigation making some risks \textit{worse}).
\item \textit{Part-of relations}
structure the collections of requirements, risks and mitigations; 
\ei

~\hrule~
\caption{DDP's ontology}
\label{ddpont}
\end{figure}


The process by which DDP is employed is as follows:

\bi
\item 6 to 20 experts are gathered 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. 
\item The DDP tool supports a graphical interface for the rapid entry of the
assertions. Such rapid entry is essential, lest using the tool slows
up the debate. 
\item Assertions from the experts are expressed in
using an ultra-lightweight decision ontology (e.g. see Figure~\ref{ddpont}).
The ontology \textit{must} be ultra-lightweight since: 
\bi
\item Only brief assertions can be collected in short knowledge acquisition
sessions. 
\item If the assertions get more elaborate, then experts
may be unable to understand technical arguments from outside their
own field of expertise. 
\ei
\ei


The result of these sessions is a network of influences connecting
project requirements to risks to possible mitigations.

The ontology of Figure~\ref{ddpont} may appear too weak for useful
reasoning. However, in repeated sessions with DDP, it has been seen
that the ontology is rich enough to structure and guide debates
between NASA experts.  For example, DDP has been applied to over a
dozen applications to study advanced technologies such as
\bi
\item a computer memory device; 
\item gyroscope design; 
\item software code generation; 
\item a low temperature experiments apparatus; 
\item an imaging device;
\item circuit board like fabrication; 
\item micro electro-mechanical devices; 
\item a sun sensor; 
\item a motor controller;
\item photonics; and 
\item interferometry. 
\ei
In those studies, DDP sessions have led to cost savings exceeding \$1
million in at least two instances, and lesser amounts (exceeding
\$100,000) in some others. The DDP sessions have also generated
numerous design improvements such as savings of power or mass, and
shifting of risks from uncertain architectural ones to better
understood (and hence more predictable and manageable) design
ones. Further, at these meetings, some non-obvious significant risks
have been identified and mitigated. Lastly, DDP can be used to
document the information and decision making of these studies. Hence,
DDP, although not mandated, remains in use at JPL:

\bi
\item not only for its original purpose (group decision support);
\item but also as a design rationale tool to document decisions. 
\ei

Note that DDP is not just a software design tool. At JPL, software and
hardware are designed together. DDP is best viewed as a {\em software
  systems engineering} tool where the interactions between hardware
and software can be quickly explored.


\subsection{DDP Model Format}

In the implementation of DDP models, values for risks, requirements,
and mitigations are assigned to reflect importance, likelihood, and
cost respectively.  Each requirement is assigned a numeric
\textit{Weight} ranging from 0 to a MAXWEIGHT, usually 100. This
number denotes the priority of the requirement in terms of how
important it is to attain it compared to other requirements. In terms
of risks, each one of them is assigned a likelihood indicating the
probability of its occurrance in case no mitigation is exercised. This
a-priori likelihood or \textit{rAPL} is measured as a floating-point
number ranging from 0 to 1 . Lastly, each mitigation is assigned a
\textit{Cost} which is usually the financial cost it would take to
take the steps necessary to prevent a risk (or risks) from
happening. Mitigations are also assigned a boolean, \textit{Selected},
that is set to \textit{true} it will be performed, \textit{false}
otherwise.

In additon to these factors, DDP models also consider the
relationships among them. For instance, risks and requirements are
related in that if the former occurs, the attainment of the latter is
negatively impacted. Given that our goal is to maximize requirement,
this impact is measured as the loss of attainment imposed by the risk
should it occur in floating-point values ranging from 0 to 1
(inclusive). An \textit{Impact(risk,requirement)} value of 0.5 means
that should the risk happen, the requirements attainment is reduced by
one half. A second relationship is established between risks and
mitigatins. The \textit{effect} of a mitigation indicates how much it
reduces each risk, and it is also measured in decimal values ranging
from 0 to 1 inclusive. An \textit{Effect(mitigation,risk)} value of
0.5 means that the given mitigation reduces the risk by one half.


Given these factors and the relationships among them we can then
search for the best way to control them to achieve the maximum
requirements attainment at the lowest mitigation costs. Keep in mind
that maximizing attainment requires minimizing risks by implementing
costly mitigations. At the same time, minimizing costs prevents
projects from implementing mitigations to reduce risks.

\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}
\label{fig:ddpExample}
\end{figure}


One of the measures that we have taken to improve the runtimes of
previous experiments is to use a method called {\em knowledge
compilation}.  Knowledge compilation is a technique where certain
information is compiled into a target language.  Previous work with
knowledge compilation has focused on compilation languages utilizing
CNF equations, state machines, or BDD~\cite{darwiche02,biere99:bmc}.
None of these made sense for our experiments, we instead compiled the
DDP models into a structure used by the C programming language.

These compiled models are used to rapidly answer a large number of
queries while the main program is running
~\cite{selman96knowledge,darwiche02}.  This pushes a large percentage
of the computational overhead into the compilation phase. This cost is
amortized over time as we increase the number of on-line queries.
Some of the algorithms that we use make thousands of calls to these
DDP models; therefore, the runtime increase from knowledge compilation
is significant.

This knowledge compilation process stores a flattened form of the DDP
requirements tree. In standard DDP:
\bi
\item 
Requirements form a tree;
\item
The relative influence of each leaf requirement is computed via
a depth-first search from the root down to the leaves.  
\item
This computation is repeated each time the relative influence of a 
requirement is required.
\ei
In our compiled form, the computation is performed once 
and added as a constant to each reference of the requirement.

For example, here is a trivial DDP model where  {\tt mitigation1}
costs \$10,000 to apply and each requirement is of equal value (100): 
\[\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.\] (The other numbers show the impact of mitigations on risks,
and risks on requirements).

The knowledge compiler converts this trivial DDP model into {\tt setupModel} and {\tt model} functions 
similar to those in \fig{ddpExample}.
The {\tt setupModel} function is called 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 grows more complex, so do these equations. For example,
our biggest model, which contains 99 mitigations, generates 1427 lines of code.

Knowledge compilation is useful for more than just runtime optimization, it has actually made some of this research possible in the first place.
This method allows JPL to retain their proprietary information. 
In turn, this has given researchers outside of JPL access to their models.
For our experiments, JPL ran the knowledge compiler and passed West Virginia University models like those shown in \fig{ddpExample}. These models have been anonymized to remove proprietary information while still maintaining their computational nature.
JPL could assure its clients that any project secrets would be safe while allowing outside researchers to perform valuable experiments.

