The need for understanding and validating unexpected behaviors in software.
Computational models are being used more and more to predict potential outcomes of systems involving human lives and costly
resources. Generally when software is used to predict outcomes uncertainty exists about conditions affecting the system
being modeled, and about the model itself. As a result, developers often experience unexpected program behaviors and must
then explore whether the behaviors reflect an implementation error or an unexpected behavior of the system. My work
addresses the development of a methodology to support the explanation for behaviors that are unexpected at the time they are
first observed. The explanation enables users to determine if the behavior valid or invalid.
Episims
Recently, the inability of researchers to explain the results of a developing computational model, Episims, has led to
public policy debate. Episims models the nationwide spread of the smallpox virus under various vaccination strategies [Euba
2004]. The results of Episims show that in the event of a smallpox outbreak the number of infections and death under a
targeted vaccination is similar to the number of infections and death under a mass vaccination. Previous established
estimates of a nationwide spread of the smallpox virus had shown that a mass vaccination drastically reduced the number of
infections and death compared to a targeted vaccination. The difference between these predictions has led to policy debate
over "whether or not it's necessary to synthesize enough smallpox vaccine for the entire country" [Cha 2005]. The Institute
of Medicine of the National Academies has published a collection of critical opinions of the predictions from Episims. The
chief complaint is that the model developers cannot provide a clear explanation for the difference between their predictions
under these vaccination strategies and previously established estimates [Baci 2005]. Methodology to facilitate the
understanding and validation of Episims' behavior would resolve this debate.
My Thesis Statement
Semi-automated search, uncertainty representation, program slicing, and causal inference procedures can be employed to
provide users with more precise and richer analysis of unexpected program behavior than current tools, and this analysis
will improve user understanding and the subsequent determination of validity of unexpected program behavior.
Hypothesis Testing Through Semi-automated Search
I will develop a hypothesis testing capability using semi-automatic search to enable users to test hypotheses about
unexpected program behavior under conditions they do not know how to create directly. Semi-automated search is a
program adaptation process that combines the use of optimization and manual modification. Program adaptation is the
process of expressing new program requirements and modifying an existing program to meet the new requirements. In this context,
optimization refers to automatic function minimization, not to performance-improving code transformation. The term
conditions of interest means when an identified quantifiable condition of the program is maximized, minimized, or
targeted to a specified requirement.
Precise and Rich Program Analysis
Program slicing has been developed to facilitate the understanding of cause and effect within program behavior. Program
slicing is a decomposition technique that extracts program statements relevant to a particular computation within the
program [Weis 1984]. Researchers in the medical, social science and economics communities have also faced the problem of
identifying the causal structure of behaviors from deterministic and stochastic systems. One solution used by researchers in
these fields is causal inference procedures. Causal inference procedures are a solution to the task of finding a
satisfactory explanation to a given set of observations [Pear 2000], [Spirtes 2001]. Despite the common goal of determining
the causal structure of a system these analyses have inherent differences. Due to the different nature of these types of
analysis they can be combined in a complementary fashion to provide a causal analysis that is richer than either of these
analysis techniques alone. Richer means the analysis will include all the analysis provided by causal inference
procedures
and program slicing, as well as new analysis that can only be revealed by combining these two analyses.
Uncertainty in program input information (aleatory uncertainty) and uncertainty in program design information (epistemic
uncertainty) result in stochastic and often unexpected program behaviors. Currently, there is no program analysis tool that
is able to provide precise analysis of stochastic program behaviors. As a result stochastic program behaviors are difficult
to understand and validate. Precision is measured by the number of program slices for a fixed input uncovered by the
analysis divided by the number of possible program slices for a fixed input [Van 2006].
I will create a program analysis tool for programming languages with uncertainty representation that is more precise than
any existing tool. Uncertainty representation is the first class representation in software of aleatory and epistemic
uncertainty, reflected through continuous and discrete random variables [Spie 2007], [Park 2005], [Park 2006]. The
uncertain
type is the data type used for the first class representation of continuous and discrete random variables in programming
languages with uncertainty representation. The tool will combine analysis performed by existing program slicing tools with
analysis enabled by the first class representation of the uncertain type.
My Programs of interest
My goal is to develop a methodology to understand and validate program behavior. Programs which use stochastics or
emphasize insight over precision are my programs of interest and are the programs most likely to benefit from my research.
The Episims simulation is one example of a program which emphasizes insight over precision. The goal of Episims is not to
predict the exact number of infections and deaths for a national release of smallpox but to determine the effectiveness of
the different vaccination strategies. Most simulations are in my domain of programs of interest due to their emphasis on
gathering insight. As a result simulations will be used extensively to evaluate my methodology. However, my methodology will
address the understanding and validation of behaviors for programs that use stochastics or emphasize insight over
precision.