Grigore Roşu

An automated and configurable technique for runtime safety analysis of multithreaded programs is presented, which is able to predict safety violations from successful executions. Based on a user provided safety formal specification, the program is automatically instrumented to emit relevant state update events to an observer, which further checks them against the safety specification. The events are stamped with dynamic vector clocks, enabling the observer to infer a causal partial order on the state updates. All event traces that are consistent with this partial order, including the actual execution trace, are analyzed on-line and in parallel, and a warning is issued whenever there is a trace violating the specification. This technique can be therefore seen as a bridge between testing and model checking. To further increase scalability, a window in the state space can be specified, allowing the observer to infer the most probable runs. If the size of the window is 1 then only the received execution trace is analyzed, like in testing; if the size of the window is then all the execution traces are analyzed, such as in model checking.

This paper presents an automatic code instrumentation technique, based onmultithreaded vector clocks, for extracting the causal partial order on relevant state update events from a running multithreaded program. This technique is used in a formal testing environment, not only to detect, but especially topredict safety errorsin multithreaded programs. The prediction process consists of rigorously analyzing other potential executions that are consistent with the causal partial order: some of these can be erroneous despite the fact that the particular observed execution was successful. The technique has been implemented as part of a Java program analysis tool. Copyright © 2006 John Wiley & Sons, Ltd.

Operation BAGRATION took place during what the Soviet analysts consider the third period of the war: that of the Soviet strategic offensives which marked the ascendancy of the Soviet armed forces over the German Wehrmacht. During this period, the armed forces of the Soviet Union held the strategic initiative and used it to defeat the Wehrmacht, gain control of Eastern Europe, and invade Germany proper, meeting Allied forces on the Elbe River on 25 April 1945. The period is regarded as beginning January 1944 and ending with the V-E Day, 7 May 1945.