{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/29503"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/29503","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Troubleshooting interactive complexity bugs","abstract":"The term “interactive complexity” was introduced by Charles Perrow in his famous book Normal Accidents: Living with High-Risk Technologies [1]. He used the term to describe the interacting tendency of systems with large number of components. He argued that, in systems with large number of components, multiple failures often interact in some unexpected way, leading to catastrophic failures in systems such as planes or nuclear power plants. He also suggested that with increasing interactive complexity and tight coupling, unexpected interactions of failures are bound to happen. Indeed, with the proliferation of Internet enabled cheap embedded devices with built in sensors and actuators (e.g., smart phones, smart appliances), the physical world is increasingly becoming an integral part of the logical world of computation. As computing systems are becoming much more interactive and responsive to the surrounding physical environments, it is becoming increasingly difficult to test such systems to full extent before deployment in real world. Hence, due to increased interactive complexity and tight coupling between physical and logical world, such systems often fail or preform poorly once deployed in real life. Unintended interactions among various system components, or across computing systems and physical environments are often to blame for the problem. With this growing trend, the bugs that arise due to interaction among different distributed components across multiple nodes are likely to get worse, and are going to affect the reliability of the system significantly. This calls for new tools and techniques to troubleshoot future software systems. In this dissertation, we address this significant challenge of troubleshooting interactive complexity bugs in emerging cyber-physical systems using data mining techniques. More specifically, we applied discriminative sequence mining algorithm to isolate chains of events (not necessarily contiguous) that is causally correlated to failure by analyzing system logs. In the first part of our thesis, using our tool, we successfully identified multiple bugs in various real systems such as multi-channel MAC (medium access control) layer protocol for wireless sensor network [2], kernel level race condition bug in the LiteOS operating system, and corner case design flaw in the directed diffusion protocol [3]. Next, we extended our approach to identify “symbolic” patterns, where absolute values are replaced with abstract symbols whenever appropriate to identify more subtle patterns across multiple system logs. Next, we have examined the applicability of our approach to troubleshoot harmful interactive complexity that may arise due to poor integration of adaptive components in server clusters. More specifically, we extended our approach to identify “cyclic” patterns in data center applications, which potentially highlights self-reinforcing loops. Finally, to complement our work on troubleshooting interactive complexity, we address the challenge of diagnosing occasional “lack of interaction” in deployed system. Such “lack of interaction” is often caused by unresponsive nodes. We develop the tele-diagnostic powertracer, an in-situ troubleshooting tool that uses external power measurements to determine the internal health condition of an unresponsive host and the most likely cause of its failure. Using our tool, we successfully distinguish between several categories of failures that cause unresponsive behavior including energy depletion, antenna damage, radio disconnection, system crashes, and anomalous reboots. To the best of our knowledge, we are the first to present a diagnostic tool that uses power measurements to diagnose sensor system failures remotely.","abstract_html":"The term “interactive complexity” was introduced by Charles Perrow in his famous book Normal Accidents: Living with High-Risk Technologies [1]. He used the term to describe the interacting tendency of systems with large number of components. He argued that, in systems with large number of components, multiple failures often interact in some unexpected way, leading to catastrophic failures in systems such as planes or nuclear power plants. He also suggested that with increasing interactive complexity and tight coupling, unexpected interactions of failures are bound to happen. Indeed, with the proliferation of Internet enabled cheap embedded devices with built in sensors and actuators (e.g., smart phones, smart appliances), the physical world is increasingly becoming an integral part of the logical world of computation. As computing systems are becoming much more interactive and responsive to the surrounding physical environments, it is becoming increasingly difficult to test such systems to full extent before deployment in real world. Hence, due to increased interactive complexity and tight coupling between physical and logical world, such systems often fail or preform poorly once deployed in real life. Unintended interactions among various system components, or across computing systems and physical environments are often to blame for the problem. With this growing trend, the bugs that arise due to interaction among different distributed components across multiple nodes are likely to get worse, and are going to affect the reliability of the system significantly. This calls for new tools and techniques to troubleshoot future software systems. In this dissertation, we address this significant challenge of troubleshooting interactive complexity bugs in emerging cyber-physical systems using data mining techniques. More specifically, we applied discriminative sequence mining algorithm to isolate chains of events (not necessarily contiguous) that is causally correlated to failure by analyzing system logs. In the first part of our thesis, using our tool, we successfully identified multiple bugs in various real systems such as multi-channel MAC (medium access control) layer protocol for wireless sensor network [2], kernel level race condition bug in the LiteOS operating system, and corner case design flaw in the directed diffusion protocol [3]. Next, we extended our approach to identify “symbolic” patterns, where absolute values are replaced with abstract symbols whenever appropriate to identify more subtle patterns across multiple system logs. Next, we have examined the applicability of our approach to troubleshoot harmful interactive complexity that may arise due to poor integration of adaptive components in server clusters. More specifically, we extended our approach to identify “cyclic” patterns in data center applications, which potentially highlights self-reinforcing loops. Finally, to complement our work on troubleshooting interactive complexity, we address the challenge of diagnosing occasional “lack of interaction” in deployed system. Such “lack of interaction” is often caused by unresponsive nodes. We develop the tele-diagnostic powertracer, an in-situ troubleshooting tool that uses external power measurements to determine the internal health condition of an unresponsive host and the most likely cause of its failure. Using our tool, we successfully distinguish between several categories of failures that cause unresponsive behavior including energy depletion, antenna damage, radio disconnection, system crashes, and anomalous reboots. To the best of our knowledge, we are the first to present a diagnostic tool that uses power measurements to diagnose sensor system failures remotely.","abstract_has_math":false,"creators":["Khan, Mohammad M."],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Abdelzaher, Tarek F.","Han, Jiawei","Sha, Lui R.","Liu, Jie"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012-02-01T00:49:40Z","date_published":"2012-02-01T00:49:40Z","updated_at":"2026-07-22T22:25:27Z","subjects":["interactive complexity bugs","discriminative sequence mining","troubleshooting"],"languages":["en"],"rights":["Copyright 2011 Mohammad Maifi Hasan Khan."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/29503","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Abdelzaher, Tarek F.","Han, Jiawei","Sha, Lui R.","Liu, Jie"]},{"key":"dc:creator","label":"Author","values":["Khan, Mohammad M."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2012-02-01T00:49:40Z","2014-02-01T11:00:32Z","2011-12"]},{"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":["interactive complexity bugs","discriminative sequence mining","troubleshooting"]}]},{"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 Mohammad Maifi Hasan Khan."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/29503"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The term “interactive complexity” was introduced by Charles Perrow in his famous book Normal Accidents: Living with High-Risk Technologies [1]. He used the term to describe the interacting tendency of systems with large number of components. He argued that, in systems with large number of components, multiple failures often interact in some unexpected way, leading to catastrophic failures in systems such as planes or nuclear power plants. He also suggested that with increasing interactive complexity and tight coupling, unexpected interactions of failures are bound to happen. Indeed, with the proliferation of Internet enabled cheap embedded devices with built in sensors and actuators (e.g., smart phones, smart appliances), the physical world is increasingly becoming an integral part of the logical world of computation. As computing systems are becoming much more interactive and responsive to the surrounding physical environments, it is becoming increasingly difficult to test such systems to full extent before deployment in real world. Hence, due to increased interactive complexity and tight coupling between physical and logical world, such systems often fail or preform poorly once deployed in real life. Unintended interactions among various system components, or across computing systems and physical environments are often to blame for the problem. With this growing trend, the bugs that arise due to interaction among different distributed components across multiple nodes are likely to get worse, and are going to affect the reliability of the system significantly. This calls for new tools and techniques to troubleshoot future software systems. In this dissertation, we address this significant challenge of troubleshooting interactive complexity bugs in emerging cyber-physical systems using data mining techniques. More specifically, we applied discriminative sequence mining algorithm to isolate chains of events (not necessarily contiguous) that is causally correlated to failure by analyzing system logs. In the first part of our thesis, using our tool, we successfully identified multiple bugs in various real systems such as multi-channel MAC (medium access control) layer protocol for wireless sensor network [2], kernel level race condition bug in the LiteOS operating system, and corner case design flaw in the directed diffusion protocol [3]. Next, we extended our approach to identify “symbolic” patterns, where absolute values are replaced with abstract symbols whenever appropriate to identify more subtle patterns across multiple system logs. Next, we have examined the applicability of our approach to troubleshoot harmful interactive complexity that may arise due to poor integration of adaptive components in server clusters. More specifically, we extended our approach to identify “cyclic” patterns in data center applications, which potentially highlights self-reinforcing loops. Finally, to complement our work on troubleshooting interactive complexity, we address the challenge of diagnosing occasional “lack of interaction” in deployed system. Such “lack of interaction” is often caused by unresponsive nodes. We develop the tele-diagnostic powertracer, an in-situ troubleshooting tool that uses external power measurements to determine the internal health condition of an unresponsive host and the most likely cause of its failure. Using our tool, we successfully distinguish between several categories of failures that cause unresponsive behavior including energy depletion, antenna damage, radio disconnection, system crashes, and anomalous reboots. To the best of our knowledge, we are the first to present a diagnostic tool that uses power measurements to diagnose sensor system failures remotely.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-07-26T17:45:15Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 khan_mohammad.pdf: 1763181 bytes, checksum: 9fcd4bc5820f90549afc67f7efc58638 (MD5) khan_mohammad.pdf: 1763181 bytes, checksum: 9fcd4bc5820f90549afc67f7efc58638 (MD5)","Made available in DSpace on 2012-02-01T00:49:40Z (GMT). No. of bitstreams: 2 khan_mohammad.pdf: 1763181 bytes, checksum: 9fcd4bc5820f90549afc67f7efc58638 (MD5) license.txt: 4062 bytes, checksum: e4762f8e2543cdacde5b5c074020b2b4 (MD5)","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by William Ingram (wingram2@illinois.edu) on 2012-02-01T00:50:44Z Item is restricted until 2014-02-01T00:50:07Z","Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2014-02-01T11:00:32Z Item was in collections: Dissertations and Theses - Computer Science (ID: 587) Graduate Theses and Dissertations at Illinois (ID: 204) No. of bitstreams: 3 khan_mohammad.pdf.txt: 285832 bytes, checksum: 60550d530024dd2048181fa88ab4788e (MD5) khan_mohammad.pdf: 1763181 bytes, checksum: 9fcd4bc5820f90549afc67f7efc58638 (MD5) license.txt: 4062 bytes, checksum: e4762f8e2543cdacde5b5c074020b2b4 (MD5)","Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2014-02-01T11:00:32Z"]},{"key":"dc:title","label":"Title","values":["Troubleshooting interactive complexity bugs"]}]}],"canonical_facts":{"dc:contributor":["Abdelzaher, Tarek F.","Han, Jiawei","Sha, Lui R.","Liu, Jie"],"dc:creator":["Khan, Mohammad M."],"dc:date":["2012-02-01T00:49:40Z","2014-02-01T11:00:32Z","2011-12"],"dc:description":["The term “interactive complexity” was introduced by Charles Perrow in his famous book Normal Accidents: Living with High-Risk Technologies [1]. He used the term to describe the interacting tendency of systems with large number of components. He argued that, in systems with large number of components, multiple failures often interact in some unexpected way, leading to catastrophic failures in systems such as planes or nuclear power plants. He also suggested that with increasing interactive complexity and tight coupling, unexpected interactions of failures are bound to happen. Indeed, with the proliferation of Internet enabled cheap embedded devices with built in sensors and actuators (e.g., smart phones, smart appliances), the physical world is increasingly becoming an integral part of the logical world of computation. As computing systems are becoming much more interactive and responsive to the surrounding physical environments, it is becoming increasingly difficult to test such systems to full extent before deployment in real world. Hence, due to increased interactive complexity and tight coupling between physical and logical world, such systems often fail or preform poorly once deployed in real life. Unintended interactions among various system components, or across computing systems and physical environments are often to blame for the problem. With this growing trend, the bugs that arise due to interaction among different distributed components across multiple nodes are likely to get worse, and are going to affect the reliability of the system significantly. This calls for new tools and techniques to troubleshoot future software systems. In this dissertation, we address this significant challenge of troubleshooting interactive complexity bugs in emerging cyber-physical systems using data mining techniques. More specifically, we applied discriminative sequence mining algorithm to isolate chains of events (not necessarily contiguous) that is causally correlated to failure by analyzing system logs. In the first part of our thesis, using our tool, we successfully identified multiple bugs in various real systems such as multi-channel MAC (medium access control) layer protocol for wireless sensor network [2], kernel level race condition bug in the LiteOS operating system, and corner case design flaw in the directed diffusion protocol [3]. Next, we extended our approach to identify “symbolic” patterns, where absolute values are replaced with abstract symbols whenever appropriate to identify more subtle patterns across multiple system logs. Next, we have examined the applicability of our approach to troubleshoot harmful interactive complexity that may arise due to poor integration of adaptive components in server clusters. More specifically, we extended our approach to identify “cyclic” patterns in data center applications, which potentially highlights self-reinforcing loops. Finally, to complement our work on troubleshooting interactive complexity, we address the challenge of diagnosing occasional “lack of interaction” in deployed system. Such “lack of interaction” is often caused by unresponsive nodes. We develop the tele-diagnostic powertracer, an in-situ troubleshooting tool that uses external power measurements to determine the internal health condition of an unresponsive host and the most likely cause of its failure. Using our tool, we successfully distinguish between several categories of failures that cause unresponsive behavior including energy depletion, antenna damage, radio disconnection, system crashes, and anomalous reboots. To the best of our knowledge, we are the first to present a diagnostic tool that uses power measurements to diagnose sensor system failures remotely.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-07-26T17:45:15Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 khan_mohammad.pdf: 1763181 bytes, checksum: 9fcd4bc5820f90549afc67f7efc58638 (MD5) khan_mohammad.pdf: 1763181 bytes, checksum: 9fcd4bc5820f90549afc67f7efc58638 (MD5)","Made available in DSpace on 2012-02-01T00:49:40Z (GMT). No. of bitstreams: 2 khan_mohammad.pdf: 1763181 bytes, checksum: 9fcd4bc5820f90549afc67f7efc58638 (MD5) license.txt: 4062 bytes, checksum: e4762f8e2543cdacde5b5c074020b2b4 (MD5)","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by William Ingram (wingram2@illinois.edu) on 2012-02-01T00:50:44Z Item is restricted until 2014-02-01T00:50:07Z","Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2014-02-01T11:00:32Z Item was in collections: Dissertations and Theses - Computer Science (ID: 587) Graduate Theses and Dissertations at Illinois (ID: 204) No. of bitstreams: 3 khan_mohammad.pdf.txt: 285832 bytes, checksum: 60550d530024dd2048181fa88ab4788e (MD5) khan_mohammad.pdf: 1763181 bytes, checksum: 9fcd4bc5820f90549afc67f7efc58638 (MD5) license.txt: 4062 bytes, checksum: e4762f8e2543cdacde5b5c074020b2b4 (MD5)","Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2014-02-01T11:00:32Z"],"dc:identifier":["http://hdl.handle.net/2142/29503"],"dc:language":["en"],"dc:rights":["Copyright 2011 Mohammad Maifi Hasan Khan."],"dc:subject":["interactive complexity bugs","discriminative sequence mining","troubleshooting"],"dc:title":["Troubleshooting interactive complexity bugs"],"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:27Z"}