使用空间填充曲线可视化二进制文件(2011)

编辑：自从这篇文章以来，我已经创建了一个用于二进制可视化的交互式工具-请参见binvis.io。

在日常工作中，我经常遇到内容未知的二进制文件。当我面对这样的野兽时，我有一套标准的攻击途径-使用文件来检查它是否是已知的文件类型，使用字符串来查看是否有可读的文本，运行一些内部代码来提取压缩部分，当然，还可以启动十六进制编辑器来直接查看。不过，这份列表中缺少一些东西--我无法快速查看文件的整体结构。使用十六进制编辑器来做这件事并不费力--如果文件的第一部分看起来是随机的(即可能是压缩的或加密的)，谁又能说再低一点的地方就没有一大块非随机信息呢？理想情况下，我们希望通过肉眼进行这种类型的广泛模式查找，因此可视化似乎是合适的。

首先，让我们从选择配色方案开始。我们有256个不同的字节值，但是对于第一遍查看文件，我们可以将其压缩成几个公共类：

这涵盖了最常见的填充字节，很好地突出显示了字符串，并将所有其他内容集中到一个杂项存储桶中。我们下一步需要做的大致轮廓很清楚-我们定期对文件进行采样，将每个采样的字节转换为一种颜色，并将相应的像素写入我们的图像。这给我们带来了一个大问题--排列像素的最佳方式是什么？第一步可能是逐行布置像素，来回蜿蜒以确保每个像素始终与其前一个像素相邻。然而，事实证明，这种之字形模式并不是很令人满意-小比例的要素(即只占几行的要素)往往会丢失。我们需要的是一种布局，它将一维样本序列映射到二维图像上，同时保持一维上相近的元素在二维上尽可能彼此接近。这就是所谓的局部保持性，空间填充曲线就是一族具有这种性质的数学构造。如果你是这个博客的常客，你可能知道我对这些动物有一种近乎不合时宜的喜爱。因此，让我们在混合中添加几条填充空间的曲线，看看它们是如何堆积起来的。Z级曲线在计算机科学中有广泛的实际应用。就保存地方性而言，它并不是最好的，但它很容易计算，而且计算起来也很快。另一方面，Hilbert曲线在局部保持方面(几乎)和它一样好，但是生成起来要复杂得多。下面是我们的三条候选曲线的外观-在每种情况下，遍历都从左上角开始：

下面是它们，可视化使用OSX分发的ksh(Mach-O，双体系结构)二进制文件，并单击以获取更壮观的更大版本的图像：

经典的希尔伯特曲线和Z级曲线实际上是正方形的，所以为了便于理解，我展开了它们，将四条子曲线叠加在一起。在我看来，希尔伯特曲线显然是这里的赢家。地方特色之所以突出，是因为它们很好地聚集在一起。Z顺序曲线显示了一些令人讨厌的伪像，其中连续的数据块有时会在两个或多个视觉块之间拆分。

空间填充曲线可视化的缺点是，我们不能查看图像中的某个特征，然后判断它在文件中的确切位置。我正在考虑(尽管不是很认真地)编写一个带有空间填充曲线导航窗格的交互式二进制文件查看器。这会让用户点击或悬停在结构的补丁上，并看到文件偏移量和相应的十六进制。

通过增加颜色映射的粒度，我们可以在这些图像中获得更多细节。要做到这一点，一种方法是使用我第一次炮制的技巧在比例上可视化希尔伯特曲线。基本思想是使用RGB颜色立方体的3-d希尔伯特曲线遍历来创建调色板。这利用了Hilbert曲线的局部性保持特性，以确保相似元素在可视化中具有相似的颜色。有关更多信息，请参阅原始帖子。

因此，这里是一个二进制文件的希尔伯特曲线映射，使用希尔伯特顺序遍历的RGB立方体作为调色板。同样，点击图片可以看到更好的大尺寸版本：

这显示出明显更细粒度的结构，这对于深入研究二进制文件可能是有好处的。另一方面，颜色不能清晰地映射到不同的字节类，因此图像更难理解。理想的十六进制查看器可以让您在两个调色板之间切换以进行导航。

像往常一样，我将发布生成此帖子中所有图像的代码。二进制可视化是用binvis创建的，这是我的充满空间的曲线项目scurve的一个新功能。曲线图是用可以在同一位置找到的绘图工具绘制的。