A hole in NCD

The Short Version

I found a weird edge case that affects certain implementations of an algorithm called Normalized Compression Distance (NCD). It's designed to estimate the degree of similarity between two inputs in domains where many other measures of distance are unsuitable. You might use it when comparing data of unequal lengths, like unstructured text, or genetic sequences, or binary data.

The algorithm was introduced concurrently through a few papers dating back to between 2001 and 2005, depending on if you count preprint servers as publication. "The Similarity Metric" (Li, Chen, Li, Ma, Vitányi) describes its output as a value between zero and one, plus some error rate. "Clustering by Compression" (Cilibrasi, Vitányi) omits the error term, seemingly suggesting it will reliably stay within those bounds.

Subsequent papers which have built on their work have favoured the latter definition and have proposed methods which assume that outputs will be constrained to that range.

I've found pairs of inputs which produce negative distances for implementations based on the the deflate algorithm, violating such assumptions. In many situations this is probably fine, but under certain conditions I can see it being used by malicious actors to crash software that cannot handle values outside the expected range.

Background

I learned about NCD in 2023 thanks to a paper which proposed its use for classification problems (“Low-Resource” Text Classification: A Parameter-Free Classification Method with Compressors). I wrote about their method's general principles and my impression of the paper on one of my other blogs (transitiontech.ca: gzip-knn, 2023-09-03), as well as my experience using the paper's methods for some practical problems (transitiontech.ca: gzip-knn-follow-up, 2024-01-09). In this write-up I'll try to focus on the relevant details, but you might want to read those for extra context.

The general idea is that lossless compression utilities like gzip can be used to estimate how much information is actually expressed by some data. By concatenating two inputs together and comparing their compressed length against that of the separate inputs, it's possible to estimate how much of that information they have in common. It's expected that highly similar inputs to the NCD function will yield a distance close or equal to zero, while dissimilar inputs will be closer to one. In practice the exact values depend on the quirks of the compression function that is used, so NCD with gzip may behave differently than bzip, brotli, or other less common methods.

As noted above, the earlier paper by Li and Vitányi (The Similarity Metric) acknowledged the effect of an error rate (ε) on the function's output, paraphrased as:

0 <= ncd(a, b) <= 1 + ε

They describe a violation of the upper bound:

"The ε in the upper bound is due to imperfections in our compression techniques, but for most standard compression algorithms one is unlikely to see an ε above 0.1 (in our experiments gzip and bzip2 achieved NCD’s above 1, but PPMZ always had NCD at most 1)."

...but I haven't found any mention of possible negative distances in any literature.

A basic implementation

I've implemented NCD in NodeJS (using the built-in zlib module for compression), and in the browser using the promise-based Compression Streams API. The former is somewhat simpler to read but otherwise equivalent, so I'll prefer that form. Likewise, concatenation of strings in JavaScript is accomplished via the + operator, so my example assumes string inputs instead of binary data.

// assume a synchronous compression function ;)
const string_ncd = (a, b) => {
    // length of a, b, and a+b after compression
    const la = compress(a).length;
    const lb = compress(b).length;
    const lab = compress(a + b).length;

    const numerator = lab - Math.min(la, lb);
    const denominator = Math.max(la, lb);
    const distance = numerator / denominator;

    return distance;
};

I've written it to be a little more verbose than usual so that I can refer directly to particular terms.

First, I'm not aware of any compression functions which return a zero-length buffer even when compressing the empty string, but I suppose that such a function would result in a denominator of zero if such an input were compared against itself. If you're aware of any such compression functions then I suppose division-by-zero errors are something to be concerned about, but I think it's fair to consider that as a more theoretical problem.

The issue I encountered relates to the numerator. While it's pretty easy to recognize that it is possible, it is non-trivial to identify the exact circumstances in which it might occur. The lesser length of the two inputs after compression is subtracted from that of their concatenation. Intuitively, you'd probably expect the concatenation to be longer or at least equal, but there are cases where it is not, and these can lead to negative distances.

Gzip implements the deflate algorithm but prepends a 20-byte header to its output, producing a buffer that is larger than most small inputs:

> zlib.gzipSync('pewpew').length
26

Passing "pewpew" for both inputs yields the concatenation "pewpewpewpew", which results in an output that is shorter by one character:

> zlib.gzipSync('pewpewpewpew').length
25

...under which conditions the NCD can be simplified to:

> (25 - 26) / 26;
-0.038461538461538464

...the negative value we were looking for.

The deflate algorithm prepends a shorter header, but otherwise behaves the same.

> zlib.deflateSync('pewpew').length
14
> zlib.deflateSync('pewpewpewpew').length
13
> (13 - 14) / 14
-0.07142857142857142

That shorter header magnifies the effect, but otherwies makes little difference.

I don't know enough about Brotli compression to rule out such cases, but at least it does not occur under these exact inputs:

> zlib.brotliCompressSync('pewpew').length
10
> zlib.brotliCompressSync('pewpewpewpew').length
13

Where might this matter?

NCD itself has a wide range of applications, being a very flexible distance metric for any pair of inputs which can be compressed. Depending on the language and environment in which you are using it you might expect different errors, from catastrophic type errors that crash the program to subtler errors where the negative output propagates through other calculations.

Most of my experience is with NCD as a distance metric for the K-Nearest-Neighbours (KNN) algorithm. My basic implementations of this simply sorted distances between an input and a set of labeled examples in ascending order, taking only the first K elements. Negative distances in this context are unlikely to be disastrous, but they could be meaningful, taking precedence over distances of zero.

Some implementations of KNN use the resulting distances to weight the importance of particular neighbours' labels. This is actually how I came to notice the effect, because I was building a toy recommender system which scaled the font-size of links to those neighbours (1 - distance). Simply put, the results just looked wrong, otherwise I would not have looked into exactly how they were derived.

Distances to a fixed set of labeled examples might also be used to construct a feature-vector. If the usage of that vector assumes its components to be between zero and one, then there are all sorts of ways in which strange outcomes might occur. Again, this could range from outright crash bugs to subtly-incorrect results propagating throughout much larger calculations.

Possible Solutions

As noted above, NCD is a family of functions, which can be notated as NCDGzip(a,b) or NCDBrotli(a,b). Because compression algorithms are so varied it probably makes sense to consider mitigations against these edge cases as an implementation detail.

The most obvious options are to simply constrain the output to between zero and one (inclusive), either by wrapping the entire expression in min/max calls, like so:

const safeNCD = (a, b) => {
    return Math.min(Math.max(ncd(a, b), 0), 1);
};

...or by handling the specific cases where the compressed length of the concatenated value is less than that of the of more compressable input, like so:

const numerator = lab - Math.min(la, lb, lab);

Perhaps this is best decided by the person using the metric. NCD's simplicity makes it such that it can be easily adapted to suit different needs. I do think, however, that implementers should be warned of NCD's capacity to produce values outside the expected range. It may only be under extreme circumstances, but a small ε can still become relevant.

Naming the fix

I don't know if these modifications are significant enough to warrant a different name for the algorithm. It is, however, a little unfortunate that Normalized Compression Distance isn't actually guaranteed to fall in a normal range.

For the extremely rare cases where you might need to distinguish between the original formulation and one which mitigates anomalous output, I've thought to call it revised or constrained NCD. That can probably wait until an objectively superior method is decided.

Future work and conclusion

I only noticed this issue less than a week ago, so I'm still thinking about possible implications for different use-cases. Likewise, I have not yet formed any opinions on the best way to approach a definitive solution, if one exists.

A friend of mine is an AI researcher who specializes in robust defenses in adversarial contexts. We've discussed applications of NCD at length, and I shared my observations as soon as I was able to confirm that they weren't due to an implementation error. We quickly discovered many more input pairs with similar features that produce comparable behaviour.

He is already digging further into the exact mechanisms in gzip/deflate that cause this surprising result, and we've discussed the possibility of an exhaustive categorization of the pairwise inputs which would trigger it. That should provide further insight into the most extreme cases where this might occur, and confirm or disprove our suspicions that it relates to small, highly similar inputs.

In any case, I don't think this is a very significant problem. It was just very surprising to consider that I might have been the first to notice an anomalous counter-example beyond the expected bounds of a function that's been in use for more than twenty years.

I welcome questions or comments, especially if they pertain to any existing literature on the topic. I can be reached via the contact form linked in the footer below.