Trace Wringing

When working towards application-tuned systems, developers often find themselves caught between the need to share information (so that partners can make intelligent design choices) and the need to hide information (to protect proprietary methods or sensitive data). One place where this problem comes to a head is in the release of program traces, for example a memory address trace. A trace taken from a production server might expose details about who the users are or what they are doing, or it might even expose details of the actual computation itself (e.g. through a side channel). Engineers are often asked to make, by hand, “analogs” of their codes that would be free from such sensitive data or, may even try to describe behaviors at a high level with words. Both of these approaches lead to missed opportunities, confusion, and frustration.

We propose a new problem for study, trace wringing, that seeks to remove as much information from the trace as possible while still maintaining key characteristics of the original. We formalize this problem and show that, for a specific instance around memory traces, as little as a few thousand bits need to be shared. We demonstrate experimentally that the trace-wrung proxies behave similarly in the context of cache simulation but with bounded leakage, and examine the sensitivity of wrung traces to a class of attacks on AES encryption.

Trace Wringing Privacy Model

Forcing a trace through a channel with a capacity of only a few bits bounds the amount of sensitive data shared. While any amount of public information such as prior non-private traces can be used in the creation of the code, the trace to be coded must not be known to the receiver. The objective is to minimize the number of bits shared while maximizing the utility of the proxy trace. We measure the utility in terms of whether or not certain utility tests are passed by the proxy and/or how close to the original tests results they get. We present a signal processing approach to reduce the trace to an n-bit channel.

To maximize privacy one wants to give away as little data as possible about the trace. However, to maximize utility the opposite is true. The question is then how little can one give away from the trace while still being useful?

Answering this question requires an analysis across two metrics: information leaked and utility. Information is surprisingly easy to quantify; it is the number of bits from the secret trace that needs to be transmitted between the full trace (which contains every address) and proxy trace (which is a stand-in for the full trace and is ready for release). Quantifying utility is harder and more use-case specific. For memory address traces, we define a distance function between cache miss-rates of trace vectors as one such function, but in general there are many other metrics one might use.

The video above explains the core concept of trace wringing in two minutes.

Our privacy argument is simple: if we only share n bits about a trace then we cannot leak more than n bits about that trace. While it is not a perfect solution, as some information might be lost, a useful upper-bound on information leakage is obtained.

Signal Processing Approach to Wringing

We project the address trace onto a fixed-size modulo-mapping of the memory spaces to create a heatmap. Interesting and intuitive patterns emerge after looking over this graph. The flat horizontal lines in the graph are patterns of repeating access to a set of addresses. These are high temporal locality behaviors. Sharp diagonal lines, on the other hand, are regions of high spatial locality as addresses are accessed one after the other in succession. If we can concisely capture the character of these behaviors, without transmitting the addresses themselves, we can minimize the amount of information leaked.