{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/29796"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/29796","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Evaluating machine-independent metrics for state-space exploration","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Kirn, Mathew"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Marinov, Darko"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012-02-06T20:17:38Z","date_published":"2012-02-06T20:17:38Z","updated_at":"2026-07-22T22:25:29Z","subjects":["State Space","Exploration","Concurrency","Metrics"],"languages":["en"],"rights":["Copyright 2011 Mathew Alan Kirn"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/29796","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Marinov, Darko"]},{"key":"dc:creator","label":"Author","values":["Kirn, Mathew"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2012-02-06T20:17:38Z","2011-12"]},{"key":"dc:type","label":"Dc Type","values":["Dissertation / Thesis","text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["State Space","Exploration","Concurrency","Metrics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2011 Mathew Alan Kirn"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/29796"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-12-06T14:34:45Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Kirn_Mathew.pdf: 435852 bytes, checksum: b058821c6353ea32e20e09ab1a70be29 (MD5)","Made available in DSpace on 2012-02-06T20:17:38Z (GMT). No. of bitstreams: 2 Kirn_Mathew.pdf: 435852 bytes, checksum: b058821c6353ea32e20e09ab1a70be29 (MD5) license.txt: 4058 bytes, checksum: 457990458222b6e4d97e2ba1d20ae8f0 (MD5)"]},{"key":"dc:title","label":"Title","values":["Evaluating machine-independent metrics for state-space exploration"]}]}],"canonical_facts":{"dc:contributor":["Marinov, Darko"],"dc:creator":["Kirn, Mathew"],"dc:date":["2012-02-06T20:17:38Z","2011-12"],"dc: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 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.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-12-06T14:34:45Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Kirn_Mathew.pdf: 435852 bytes, checksum: b058821c6353ea32e20e09ab1a70be29 (MD5)","Made available in DSpace on 2012-02-06T20:17:38Z (GMT). No. of bitstreams: 2 Kirn_Mathew.pdf: 435852 bytes, checksum: b058821c6353ea32e20e09ab1a70be29 (MD5) license.txt: 4058 bytes, checksum: 457990458222b6e4d97e2ba1d20ae8f0 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/29796"],"dc:language":["en"],"dc:rights":["Copyright 2011 Mathew Alan Kirn"],"dc:subject":["State Space","Exploration","Concurrency","Metrics"],"dc:title":["Evaluating machine-independent metrics for state-space exploration"],"dc:type":["Dissertation / Thesis","text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:29Z"}