Evaluating machine-independent metrics for state-space exploration
type: CreativeWork
description: 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 fut…
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 fut…
author: Kirn, Mathew
language: en
keywords: State Space, Exploration, Concurrency, Metrics
date published: 2012-02-06T20:17:38Z
date modified: 2026-07-22T22:25:29Z
provider: University of Illinois - Urbana-Champaign
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: University of Illinois at Urbana-Champaign

PropertyValue
property ID: Handle
value: http://hdl.handle.net/2142/29796