{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/49713"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/49713","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Algorithmic techniques for predictive testing of concurrent programs and distributed systems","abstract":"The rise of multicore hardware platforms has lead to a new era of computing. In order to take full advantage of the power of multicore processors, developers need to write concurrent code. Unfortunately, as a result of the non-determinism introduced by thread scheduling, multi-threaded programs can show different behaviors even for a single input. Errors in concurrent programs often occur under subtle interleaving patterns that the programmer had not foreseen. There are too many interleavings to explore, even on a fixed test input for a concurrent program, making concurrency testing a hard problem. Current testing technologies such as stress testing (running the program under test repeatedly with randomized sleep statements and by varying parameters on different platforms) have proved largely inadequate in exposing such subtle interleavings. Among the various techniques to test concurrent programs, the prediction-based technique is one of most valuable technology. Starting from one arbitrary concurrent execution of the program under testing, alternate interleavings that are likely to contain bugs are predicted. In our research, we explore prediction algorithms based on a combination of static analysis and logical constraint solving to efficiently and effectively test concurrent programs. The strength of our research lies in the fact that the techniques we propose are general enough to predict, with a high degree of accuracy of feasibility, various kinds of concurrent errors. We provide evidence that such an approach is promising in testing concurrent programs. In fact, we have implemented our techniques in a framework, Penelope. We evaluate it over benchmark programs and find scores of null-pointer dereferences, data-races, atomicity violations and deadlocks by using only a single test run as the prediction seed for each benchmark. We also take into account the challenge of bringing our experience in predictive testing of concurrent programs to the distributed systems environment. We use supervised machine learning to model the system behaviors in response to perturbations, based on recorded observations in a pseudo distributed (small-scale) setting. From the learned model, we predict the next system state given current states and applied perturbations. In a perturbation-based testing framework, accurate prediction helps to shorten the waiting time between the consecutive perturbations. Moreover, from the learned model, we reconstruct a possible sequence of perturbation from a given sequence of observed system states for diagnosis. We demonstrate the usefulness of our approach in a case study of a distributed system based on ZooKeeper and SolrCloud.","abstract_html":"The rise of multicore hardware platforms has lead to a new era of computing. In order to take full advantage of the power of multicore processors, developers need to write concurrent code. Unfortunately, as a result of the non-determinism introduced by thread scheduling, multi-threaded programs can show different behaviors even for a single input. Errors in concurrent programs often occur under subtle interleaving patterns that the programmer had not foreseen. There are too many interleavings to explore, even on a fixed test input for a concurrent program, making concurrency testing a hard problem. Current testing technologies such as stress testing (running the program under test repeatedly with randomized sleep statements and by varying parameters on different platforms) have proved largely inadequate in exposing such subtle interleavings. Among the various techniques to test concurrent programs, the prediction-based technique is one of most valuable technology. Starting from one arbitrary concurrent execution of the program under testing, alternate interleavings that are likely to contain bugs are predicted. In our research, we explore prediction algorithms based on a combination of static analysis and logical constraint solving to efficiently and effectively test concurrent programs. The strength of our research lies in the fact that the techniques we propose are general enough to predict, with a high degree of accuracy of feasibility, various kinds of concurrent errors. We provide evidence that such an approach is promising in testing concurrent programs. In fact, we have implemented our techniques in a framework, Penelope. We evaluate it over benchmark programs and find scores of null-pointer dereferences, data-races, atomicity violations and deadlocks by using only a single test run as the prediction seed for each benchmark. We also take into account the challenge of bringing our experience in predictive testing of concurrent programs to the distributed systems environment. We use supervised machine learning to model the system behaviors in response to perturbations, based on recorded observations in a pseudo distributed (small-scale) setting. From the learned model, we predict the next system state given current states and applied perturbations. In a perturbation-based testing framework, accurate prediction helps to shorten the waiting time between the consecutive perturbations. Moreover, from the learned model, we reconstruct a possible sequence of perturbation from a given sequence of observed system states for diagnosis. We demonstrate the usefulness of our approach in a case study of a distributed system based on ZooKeeper and SolrCloud.","abstract_has_math":false,"creators":["Sorrentino, Francesco"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Parthasarathy, Madhusudan","Marinov, Darko","Roşu, Grigore","Qadeer, Shaz"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-05-30T17:06:04Z","date_published":"2014-05-30T17:06:04Z","updated_at":"2026-07-22T22:25:40Z","subjects":["Testing","Concurrency","Cloud","Diagnosis","Bugs","Data-Race","Deadlock","Null-Pointer","Atomicity"],"languages":["en"],"rights":["Copyright 2014 Francesco Sorrentino"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/49713","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Parthasarathy, Madhusudan","Marinov, Darko","Roşu, Grigore","Qadeer, Shaz"]},{"key":"dc:creator","label":"Author","values":["Sorrentino, Francesco"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-05-30T17:06:04Z","2016-09-22T20:59:12Z","2014-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"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":["Testing","Concurrency","Cloud","Diagnosis","Bugs","Data-Race","Deadlock","Null-Pointer","Atomicity"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2014 Francesco Sorrentino"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/49713"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The rise of multicore hardware platforms has lead to a new era of computing. In order to take full advantage of the power of multicore processors, developers need to write concurrent code. Unfortunately, as a result of the non-determinism introduced by thread scheduling, multi-threaded programs can show different behaviors even for a single input. Errors in concurrent programs often occur under subtle interleaving patterns that the programmer had not foreseen. There are too many interleavings to explore, even on a fixed test input for a concurrent program, making concurrency testing a hard problem. Current testing technologies such as stress testing (running the program under test repeatedly with randomized sleep statements and by varying parameters on different platforms) have proved largely inadequate in exposing such subtle interleavings. Among the various techniques to test concurrent programs, the prediction-based technique is one of most valuable technology. Starting from one arbitrary concurrent execution of the program under testing, alternate interleavings that are likely to contain bugs are predicted. In our research, we explore prediction algorithms based on a combination of static analysis and logical constraint solving to efficiently and effectively test concurrent programs. The strength of our research lies in the fact that the techniques we propose are general enough to predict, with a high degree of accuracy of feasibility, various kinds of concurrent errors. We provide evidence that such an approach is promising in testing concurrent programs. In fact, we have implemented our techniques in a framework, Penelope. We evaluate it over benchmark programs and find scores of null-pointer dereferences, data-races, atomicity violations and deadlocks by using only a single test run as the prediction seed for each benchmark. We also take into account the challenge of bringing our experience in predictive testing of concurrent programs to the distributed systems environment. We use supervised machine learning to model the system behaviors in response to perturbations, based on recorded observations in a pseudo distributed (small-scale) setting. From the learned model, we predict the next system state given current states and applied perturbations. In a perturbation-based testing framework, accurate prediction helps to shorten the waiting time between the consecutive perturbations. Moreover, from the learned model, we reconstruct a possible sequence of perturbation from a given sequence of observed system states for diagnosis. We demonstrate the usefulness of our approach in a case study of a distributed system based on ZooKeeper and SolrCloud.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2014-04-25T13:33:30Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Sorrentino_Francesco.pdf: 4116711 bytes, checksum: e2abefccbd9b13b261557d91a7145ee7 (MD5)","Made available in DSpace on 2014-05-30T17:06:04Z (GMT). No. of bitstreams: 2 Francesco_Sorrentino.pdf: 4116399 bytes, checksum: a07575b60585ecbcb5acee9eed0206ff (MD5) license.txt: 4070 bytes, checksum: 9b3bb6a226d2b64324b758fadf52563e (MD5)","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Seth Robbins (robbins.sd@gmail.com) on 2014-05-30T17:09:48Z Item is restricted until 2016-05-30T17:09:03Z","Restriction data tranferred 2014-07-01T11:39:01-05:00 Original Data Group with Access UIUC Users [automated] Release Date: 2016-05-30 12:09:03 UTC Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 49764 on 2016-09-22T20:59:12Z."]},{"key":"dc:title","label":"Title","values":["Algorithmic techniques for predictive testing of concurrent programs and distributed systems"]}]}],"canonical_facts":{"dc:contributor":["Parthasarathy, Madhusudan","Marinov, Darko","Roşu, Grigore","Qadeer, Shaz"],"dc:creator":["Sorrentino, Francesco"],"dc:date":["2014-05-30T17:06:04Z","2016-09-22T20:59:12Z","2014-05"],"dc:description":["The rise of multicore hardware platforms has lead to a new era of computing. In order to take full advantage of the power of multicore processors, developers need to write concurrent code. Unfortunately, as a result of the non-determinism introduced by thread scheduling, multi-threaded programs can show different behaviors even for a single input. Errors in concurrent programs often occur under subtle interleaving patterns that the programmer had not foreseen. There are too many interleavings to explore, even on a fixed test input for a concurrent program, making concurrency testing a hard problem. Current testing technologies such as stress testing (running the program under test repeatedly with randomized sleep statements and by varying parameters on different platforms) have proved largely inadequate in exposing such subtle interleavings. Among the various techniques to test concurrent programs, the prediction-based technique is one of most valuable technology. Starting from one arbitrary concurrent execution of the program under testing, alternate interleavings that are likely to contain bugs are predicted. In our research, we explore prediction algorithms based on a combination of static analysis and logical constraint solving to efficiently and effectively test concurrent programs. The strength of our research lies in the fact that the techniques we propose are general enough to predict, with a high degree of accuracy of feasibility, various kinds of concurrent errors. We provide evidence that such an approach is promising in testing concurrent programs. In fact, we have implemented our techniques in a framework, Penelope. We evaluate it over benchmark programs and find scores of null-pointer dereferences, data-races, atomicity violations and deadlocks by using only a single test run as the prediction seed for each benchmark. We also take into account the challenge of bringing our experience in predictive testing of concurrent programs to the distributed systems environment. We use supervised machine learning to model the system behaviors in response to perturbations, based on recorded observations in a pseudo distributed (small-scale) setting. From the learned model, we predict the next system state given current states and applied perturbations. In a perturbation-based testing framework, accurate prediction helps to shorten the waiting time between the consecutive perturbations. Moreover, from the learned model, we reconstruct a possible sequence of perturbation from a given sequence of observed system states for diagnosis. We demonstrate the usefulness of our approach in a case study of a distributed system based on ZooKeeper and SolrCloud.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2014-04-25T13:33:30Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Sorrentino_Francesco.pdf: 4116711 bytes, checksum: e2abefccbd9b13b261557d91a7145ee7 (MD5)","Made available in DSpace on 2014-05-30T17:06:04Z (GMT). No. of bitstreams: 2 Francesco_Sorrentino.pdf: 4116399 bytes, checksum: a07575b60585ecbcb5acee9eed0206ff (MD5) license.txt: 4070 bytes, checksum: 9b3bb6a226d2b64324b758fadf52563e (MD5)","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Seth Robbins (robbins.sd@gmail.com) on 2014-05-30T17:09:48Z Item is restricted until 2016-05-30T17:09:03Z","Restriction data tranferred 2014-07-01T11:39:01-05:00 Original Data Group with Access UIUC Users [automated] Release Date: 2016-05-30 12:09:03 UTC Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 49764 on 2016-09-22T20:59:12Z."],"dc:identifier":["http://hdl.handle.net/2142/49713"],"dc:language":["en"],"dc:rights":["Copyright 2014 Francesco Sorrentino"],"dc:subject":["Testing","Concurrency","Cloud","Diagnosis","Bugs","Data-Race","Deadlock","Null-Pointer","Atomicity"],"dc:title":["Algorithmic techniques for predictive testing of concurrent programs and distributed systems"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:40Z"}