MSDN Magazine - June 2008 - (Page 56)

The analysis typically includes some formal inspection to ensure that the intent and assumptions of the programmer prevents incorrect behavior. Prefix and Prefast are two of the most popular static analysis tools for native applications, whereas FxCop is very popular for managed code. There are advantages and disadvantages to static analysis. Among the advantages are the thorough and detailed coverage achieved, the confidence in the product design that such formal analysis helps build, and the precise error reports that make bugs easier to find and fix. However, to deal with concurrency bugs, static analysis requires a great deal of annotation specifying intent. Moreover, these annotations need to be correct themselves. Plus, tools that use static analysis tend to generate a lot of false positives and require a significant effort to minimize the false positives. In dynamic analysis, bugs are detected by looking at the footprints of execution. There are two types of dynamic analysis: online and offline. Tools that use online dynamic analysis analyze a program while it is executing; tools that use offline dynamic analysis record traces and analyze them later to detect bugs. Dynamic analysis is convenient because it requires little-to-no extra work from the developer at the time of programming, yields fewer false positives, and makes it easier to address the more obvious problems. Since bugs are discovered only in the path of execution, the more frequently traversed paths yield the first set of bugs. This makes it cheaper to improve reliability. But there are disadvantages, too. You can detect bugs only in the path of execution, and you need to rely on test cases for a good code coverage. In fact, some tools can only catch a race if a race occurred in that run. Thus, if the tool does not report any bugs, you still can’t be certain there aren’t any. Most dynamic analysis tools rely on some sort of instrumentation that can modify the behavior of runtime, which is another drawback. Due to the complexity, the performance of these tools tends to be very poor. The final method is model checking—the method for verifying the correctness of a finite state concurrent system. It allows for formal deductive reasoning. A model checker tries to simulate race and deadlock conditions. Using model checking, you can formally prove the absence of races and deadlocks. This method provides superior confidence in design and architecture, provides very high coverage, and requires minimal external drivers. Like other testing methods, model checking has some disadvantages. In most cases, it is very difficult to automatically extract the model from code (rare cases exist with limited use). Performing the model extraction manually is also quite tedious. There is also too much to verify due to state space explosion, a condition wherein the potential number of possible states is too huge to analyze. State space explosion can be controlled to some extent by applying reduction techniques which utilize complicated heuristics. Such heuristics can also have downsides, such as failing to detect bugs in long-running applications. 56 msdn magazine Model checking provides superior confidence in design, provides high coverage, and requires minimal external drivers. Finally, model checking requires disciplined design and implementation planning. Model checking may prove that the design is error free, but the implementation may still be incorrect. In practice, model checking is useful only for small, critical sections of a product. Other hybrid techniques include combining dynamic analysis and model checking. An example is CHESS, which you’ll see shortly. There are a number of concurrency testing tools on the market to help you deal with potential deadlocks, livelocks, hangs, and all the other issues you experience when running parallel transactions. Each tool we look at here will help in a particular area. CHeSS Created by Microsoft Research, CHESS is a novel combination of model checking and dynamic analysis (see go.microsoft.com/fwlink/?LinkId=116523). It detects concurrency errors by systematically exploring thread schedules and interleaving. It is capable of finding race conditions, deadlocks, hangs, livelocks, and data corruption issues. To help with debugging, it also provides a fully repeatable execution. Like most model checking, the systematic exploration provides thorough coverage. As a dynamic analysis tool, CHESS runs a regular unit test repeatedly on a specialized scheduler. On every repetition, it chooses a different scheduling order. As a model checker, it controls the specialized scheduler that is capable of creating specific thread interleavings. To control the state space explosion, CHESS applies partial-order reduction and a novel iteration context bounding. In iteration context bounding, instead of limiting the state space explosion by depth, CHESS limits number of thread switches in a given execution. The thread itself can run any number of steps between thread switches, leaving the execution depth unbounded (a big win over traditional model checking). This is based on the empirical evidence that a small number of systematic thread switches is sufficient to expose most concurrency bugs. CHESS can detect deadlocks and races (using the Goldilocks lockset algorithm explained at go.microsoft.com/fwlink/?LinkId=116877) but relies on programmer assertions for other state verification. It also expects all programs to terminate and that there is a fairness guarantee (forward progress) for all threads. Thus, if the program enters a state of continuous loop, it reports a livelock. From the testing view point, you would begin by running CHESS with an iteration context bound of 2. Once there are no more bugs to be found, you would increase the bound to 3 and so on. Empirically, most of the bugs should be detected with a bound of 2 and 3. Hence, this can be a very efficient way to weed out bugs sooner. For instrumentation, CHESS detours Win32® API synchronization calls to control and intentionally introduces non-determinism. Additionally, it requires developer code to include a lot of asserts to ensure consistency of states (something good code should do anyway). However, like most dynamic analysis tools, it requires a good test suite for broad coverage. CHESS is a boon for all those Concurrency Concurrency Testing Tools http://go.microsoft.com/fwlink/?LinkId=116523 http://go.microsoft.com/fwlink/?LinkId=116877

Table of Contents Feed for the Digital Edition of MSDN Magazine - June 2008

MSDN Magazine - June 2008 Contents Toolbox CLR Inside Out Cutting Edge Patterns In Practice SAAS Concurrency Robotics Form Filler GUI Library Service Station Foundations Windows With C++ Concurrent Affairs Going Places { End Bracket }

MSDN Magazine - June 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.