World Library  
Flag as Inappropriate
Email this Article


Article Id: WHEBN0000660243
Reproduction Date:

Title: Lurch  
Author: World Heritage Encyclopedia
Language: English
Subject: Debuggers, Formal verification, Software testing/Software testing topics
Publisher: World Heritage Encyclopedia


LURCH is a tool for software design debugging that uses a nondeterministic algorithm to quickly explore the reachable states of a software model. By performing a partial and random search, LURCH looks for faults in the model and reports the pathways leading to the faults.


  • Explanation 1
    • Conventional algorithms 1.1
    • Nondeterministic analysis methods 1.2
  • Decisions on using LURCH 2
  • See also 3
  • References 4


Conventional algorithms

Conventional algorithms for exploring a system's state space are deterministic, in that they have specific decision paths for mapping inputs to outputs. Nondeterministic algorithms, on the other hand, do not have such specific paths, allowing for the same inputs to result in different outputs. Deterministic analysis is often considered safer than nondeterministic methods since it explores all possible system states in an exhaustive and thorough way. Nondeterministic analysis, however, may only explore a subset of the entire state space, and thereby miss some of the possible faults.

Nondeterministic analysis methods

Much evidence supports the notion of clumping (computer science), where the effective state space of a program is small compared to all reachable states. A tool such as LURCH is especially useful in such situations. However, depending on the problem, if clumping does not occur, the nondeterministic approach may not be very effective. Yet in such situations, LURCH can at least report whether performing a nondeterministic search will be safe or not.

Decisions on using LURCH

Menzies et al. in [1] argue that LURCH is no less safe than conventional deterministic algorithms for software model analysis; that LURCH is simple, competent, fast, scalable, and a stable nondeterministic analysis method:

  1. LURCH is simple: The following is pseudocode for LURCH, which is considerably easier to implement compared to more complex standard model checkers.
function step(Q, state)
    while Q is not empty
        // choose a transition at random
        tr := random_pop(Q)
        // modify state vector accordingly
        execute_outputs(tr, state)
        // disqualify transitions ruled out by choice
        for tr' in same machine as tr
           delete(Q, tr')
function check(state)
    // cycle_check requires hash table
function lurch(max_paths, max_depth)
   repeat max_paths times
       // set all machines to initial state
       for m in machines
           state[m] := 0
       // generate a global state path
       repeat max_depth times
           for tr in transitions
               // see if transition is blocked
               if check_inputs(tr)
                   // if not, put it in the queue
                   push(Q, tr)
               // get next global state
               step(Q, state)
               // see if next state represents a fault

See also


  • Menzies, Owen, Heimdahl, Gao, Cukic, Nondeterminism: Unsafe?
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.