• Login
    View Item 
    •   MINDS@UW Home
    • MINDS@UW Madison
    • College of Letters and Science, University of Wisconsin–Madison
    • Department of Computer Sciences, UW-Madison
    • CS Technical Reports
    • View Item
    •   MINDS@UW Home
    • MINDS@UW Madison
    • College of Letters and Science, University of Wisconsin–Madison
    • Department of Computer Sciences, UW-Madison
    • CS Technical Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Supporting Proofs for Control-Flow Recovery from Partial Failure Reports

    Thumbnail
    File(s)
    main report (217.3Kb)
    Date
    2017-04-28
    Author
    Ohmann, Peter
    Brooks, Alexander
    D'Antoni, Loris
    Liblit, Ben
    Metadata
    Show full item record
    Abstract
    Debugging post-deployment failures is difficult, in part because failure reports from these applications usually provide only partial information about what occurred during the failing execution. We introduce approaches that answer control-flow queries about a failing program's execution based on failure constraints given as formal languages. A key component of our approach is the introduction of a new class of subregular languages, the unreliable trace languages (UTL), which allow us to answer many common queries in polynomial time. This report supplements the description of these new approaches with formal proofs. Specifically: we prove completeness for our context-insensitive query problem, tightly bind polynomial-time decidability of query recovery to the UTL class, and prove partial correctness for our approach to answering user queries with UTL constraints.
    Subject
    regular languages
    formal languages
    failure reporting
    automata theory
    debugging
    deployed software
    Permanent Link
    http://digital.library.wisc.edu/1793/76432
    Citation
    TR1845
    Part of
    • CS Technical Reports

    Contact Us | Send Feedback
     

     

    Browse

    All of MINDS@UWCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    Contact Us | Send Feedback