Skip to main content
Department of Information Technology

SAAPP: Approach

The key feature of our approach is to use an instruction-level simulator, which gives a number of interesting advantages:

  • The system does not need to be modelled in a formal language. Therefore the inherent abstraction problem related to formal methods are avoided.
  • The system being examined is exactly the real software system. There is no inherent abstraction, and thus the exact interactions between the software system, the operating system and the hardware are analysed.
  • As long as it can be executed on a processor supported by the simulator, the software to be examined can be written in any programming language. It need not even be available in source code.
  • Software execution can be deterministically replayed and non-intrusively monitored by the simulator. Thus probe effects [GAI86], common when using traditional binary rewriting techniques, are avoided.
  • The scheduling of parallel threads and processes can be fully controlled, allowing interleaving variants to be generated.

Previously, dynamic data race detection has mainly relied on binary rewriting (instrumentation) [CMN91,SBN+97,HAR00,ROB00], leading to probe effects [GAI86]. By using an instruction-level simulator, we hope to eliminate the restrictions of earlier approaches. Our aim is to work on existing software systems of realistic size.

Virtutech Simics

In our work we will investigate the possibilities and specific advantages of using the Virtutech Simics [MDG+98,MCE+02] system level instruction set simulator as a base for analysing the execution of parallel shared memory programs at runtime, in a predictable and reproducible way, in order to find race conditions and other dependencies between processes, and analyse properties of the system as a whole.

Virtutech Simics runs single- or multiprocessor configurations of Sun SPARC, Intel x86 and Itanium, AMD x86-64, PowerPC, ARM, MIPS, and HP Alpha processors running commercial operating systems, e.g. Solaris and Windows NT. Snapshots of running systems can be created and restarted, and details of processor scheduling, memory accesses etc can be retrieved. Several simulators can be connected via a virtual local area network, thus simulating distributed systems and network traffic. The simulation is deterministic and can be controlled to obtain different order of memory accesses and interrupts which interact between processors.

During simulation, points of communication in a program can be extracted. These points can serve as the base for further analysis and formal model generation or be used to change the latency of specific instructions and thus the interleaving of communicating memory references. Doing this iteratively is a method for automatically testing different schedulings of the program execution. Compared to other dynamic methods, using the simulator to monitor the execution instead of binary rewriting, no probe effects or "Heisenbugs" can emerge.

To support detecting communication patterns in a multi-threaded program, it is central that the simulator has the ability to (1) detect memory accessed by more than one thread and (2) how shared memory is accessed (load or store). If the threads are running on the same processor, detecting communication will be a somewhat harder problem since the current version of the simulator has no knowledge about threads . There is also a need for mapping the memory addresses to back to the source code, if source code is available. However, the analysis should be independent of the source code.

Virtutech Simics is an advanced instruction set simulator. By utilizing the unique features of the simulator, more details of the actual execution are available for program analysis compared to earlier dynamic methods. At any time, the simulated execution can non-intrusively be stopped and the complete state including the operating system can be examined. By dynamically examining the operating system, we can differentiate between processes and threads as they are created or terminated, or directly monitor different scheduling queues. Furthermore, if we wish to extend our analysis beyond data race detection, other communication primitives such as sockets or signals can be used in the analysis. Already built in to the simulator is the basic support to point back from the executable binary to the source code. This feature will be very useful to guide a future data race detection user interface and may require further development of the simulator. The simulator can slow down or stop the simulation without affecting the simulated execution time. We pay for all advantages by one main disadvantage; the simulator causes an almost uniform slowdown of approximately 100 times. Besides the slowdown, memory and disk usage can must be kept at a reasonable level.

Updated  2003-04-08 09:53:24 by Björn Victor.