Evaluating machine-independent metrics for state-space exploration

Kirn, Mathew

Permalink

https://hdl.handle.net/2142/29796 Copy

Description

Title

Evaluating machine-independent metrics for state-space exploration

Author(s)

Kirn, Mathew

Issue Date

2012-02-06T20:17:38Z

Director of Research (if dissertation) or Advisor (if thesis)

Marinov, Darko

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• State Space
• Exploration
• Concurrency
• Metrics

Abstract

Many recent advancements in testing concurrent programs have surfaced as novel optimization and heuristic techniques in tools that explore the state spaces of tests for such programs. To empirically evaluate these techniques, researchers apply them on subject programs, capture a set of metrics, and compare these metrics to provide some measure of the techniques’ effectiveness. From a user’s perspective, the metric that best measures effectiveness is the amount of real time to find a bug (if one exists), but using real time for comparison can produce misleading results because it is necessarily dependent on the configuration of the machine used (i.e., hardware, OS, etc.). The metrics used in evaluations in the literature often vary widely and are either machine-independent (e.g., number of states, transitions, paths) or machine-dependent (e.g., real time, memory), and are captured using a variety of machine configurations ranging from a single machine to a cluster of machines. Depending upon the machine configuration(s) and metric(s) selected for a particular evaluation, the results may suggest different conclusions, and the experiments may be difficult to repeat. As a result, it can be difficult to perform meaningful comparisons for state-space exploration tools and the techniques they employ. This thesis provides a study of the usefulness of different metrics and machine configurations for two different state-space exploration frameworks for Java, JPF (stateful) and ReEx (stateless), by revisiting and extending a previous study (Parallel Randomized State-Space Search) and evaluating the correlation of several machine-independent metrics with real time. We have conducted a set of experiments across both previously used and new subject programs in order to evaluate the degree to which several machine-independent metrics correlate with real time both on a single machine and on a high-performance cluster of machines. We provide new evidence for selecting metrics in future evaluations of state-space exploration techniques by showing that several machine-independent metrics for state-space exploration are a good substitute for real time, and that reporting real time results even from clusters of machines can provide useful information.

Graduation Semester

2011-12

Permalink

http://hdl.handle.net/2142/29796

Copyright and License Information

Copyright 2011 Mathew Alan Kirn

Owning Collections