Dynamic binary instrumentation (DBI) frameworks make it easy to build dynamic binary analysis (DBA) tools such as checkers and profilers. Much of the focus on DBI frameworks has been on performance; little attention has been paid to their capabilities. As a result, we believe the potential of DBI has not been fully exploited.

Several existing dynamic binary analysis tools use shadowmemory-they shadow, in software, every byte of memory used by a program with another value that says something about it. Shadow memory is difficult to implement both efficiently and robustly. Nonetheless, existing shadow memory implementations have not been studied in detail. This is unfortunate, because shadow memory is powerful-for example, some of the existing tools that use it detect critical errors such as bad memory accesses, data races, and uses of uninitialised or untrusted data. In this paper we describe the implementation of shadow memory in Memcheck, a popular memory checker built with Valgrind, a dynamic binary instrumentation framework. This implementation has several novel features that make it efficient: carefully chosen data structures and operations result in a mean slow-down factor of only 22.2 and moderate memory usage. This may sound slow, but we show it is 8.9 times faster and 8.5 times smaller on average than a naive implementation, and shadow memory operations account for only about half of Memcheck's execution time. Equally importantly, unlike some tools, Memcheck's shadow memory implementation is robust: it is used on Linux by thousands of programmers on sizeable programs such as Mozilla and OpenOffice, and is suited to almost any memory configuration. This is the first detailed description of a robust shadow memory implementation, and the first detailed experimental evaluation of any shadow memory implementation. The ideas within are applicable to any shadow memory tool built with any instrumentation framework.

Lossless text compression based on the Burrows-Wheeler transform (BWT) has become popular. Compression-time issues-MTF coding or the avoidance thereof (Wirth 2000), encoding the MTF values, sorting fast (Seward 2000)-have seen considerable investigation. Decompression-time issues remain underinvestigated. For some applications, decompression-time behaviour is a critical issue. For example, boot-time decompression of the Linux kernel requires decompression in limited memory. On-the-fly disk compressors employing the BWT demand fast decompression. This paper presents a number of ways to implement the inverse B-W transform, giving a useful range of speed-memory tradeoffs. We show that, at one extreme, it is possible to invert the BWT, slowly, using just one byte per block-byte. At the other extreme, we argue that the maximum speed of BWT decompression is unavoidably constrained by the rate at which cache misses are serviced.

In recent years lossless text compression based on the Burrows-Wheeler transform (BWT) has grown popular. The expensive activity during compression is sorting of all the rotations of the block of data to compress. Burrows and Wheeler (1994) describe an efficient implementation of rotation sorting but give little analysis of its performance. This paper addresses that need. We present the base algorithm using a more formal framework, describe two important optimisations not present in the original paper, and measure performance of the variants on a set of 14 files. For completeness, a tuned implementation of Sadakane's (1998) sorting algorithm was also tested. Merely measuring running times gives poor insight into the finer aspects of performance on contemporary machine architectures. We report measurements of instruction counts and cache misses for the algorithms giving a clearer picture of which variants perform well, and why.

Financial and insurance contracts do not sound like promising territory for functional programming and formal semantics, but in fact we have discovered that insights from programming languages bear directly on the complex subject of describing and valuing a large class of contracts.We introduce a combinator library that allows us to describe such contracts precisely, and a compositional denotational semantics that says what such contracts are worth. We sketch an implementation of our combinator library in Haskell. Interestingly, lazy evaluation plays a crucial role.

This paper shows how to implement sensible polymorphic strictness analysis using the Frontiers algorithm. A central notion is to only ever analyse each function once, at its simplest polymorphic instance. Subsequent non-base uses of functions are dealt with by generalising their simplest instance analyses. This generalisation is done using an algorithm developed by Baraki, based on embedding-closure pairs. Compared with an alternative approach of expanding the program out into a collection of monomorphic instances, this technique is hundreds of times faster for realistic programs. There are some approximations involved, but these do not seem to have a detrimental effect on the overall result. The overall effect of this technology is to considerably expand the range of programs for which the Frontiers algorithm gives useful results reasonably quickly.