python - 如何在十六进制转储上查找重复出现的模式？

Question

我需要从十六进制转储输出中找到重复出现的模式。我的输出文件中的每一行都类似于:

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

其中 00 是十六进制的字节。

这些模式的长度不固定，但它们总是排成一行。

我有一个关于如何做到这一点的想法，但我想知道您认为最有效的方法是什么，比如是否存在某种我不知道的已知算法。

我也想用 Python 编写这个代码。

非常感谢任何建议:)

谢谢

编辑:我需要在磁盘转储中找到分区引导扇区。问题是该文件系统不常见，因此我需要扫描十六进制转储以查找经常使用的模式，以限制研究领域。

例如，我正在寻找字节模式，例如:

00 56 f0 43 d0 

Answer 1

您是否知道要搜索的子字符串，或者是否需要首先发现一组查询子字符串，这一点并不明显。我认为可以通过查找频繁出现的 n 元语法来实现这一发现。一旦您有了一组查询子字符串，您就可以继续了解它们所在的位置以及它们之间的距离(例如，如果某个子字符串每 1024 字节出现一次，则可能是一个 block 大小)。

第 1 步:读取 hexdump 文件并将其转换回单个字符串。我会将详细信息留给您。

第 2 步:对于每个有趣的 n 值(例如 3、4、5(如您的示例)、6 等)，请使用此函数:

from collections import Counter # needs 2.7
from operator import itemgetter
def get_ngrams(strg, n, top=10, min_count=2):
    counter = Counter()
    for i in xrange(len(strg) - n + 1):
        gram = strg[i:i+n]
        counter[gram] += 1
    sort_these = [(gram, count) for gram, count in counter.iteritems() if count >= min_count]
    best = sorted(sort_these, key=itemgetter(1), reverse=True)[:top]
    return best

这将为您提供最频繁出现的子字符串。

第 3 步:这些字符串出现的位置:

def multifind(strg, gram):
    positions = []
    end = len(strg)
    pos = 0
    while pos < end:
        pos = strg.find(gram, pos)
        if pos == -1:
            break
        positions.append(pos)
        pos += 1
    return positions

第 4 步:这些事件的间隔有多远:

deltas = [b - a for a, b in zip(positions, positions[1:])]