200kB的文件要搜索8个！Python 或 IDA 中的（40320 个排列）

Question

我正在拆解固件（西门子 C165 处理器 - https://www.infineon.com/dgdl/Infineon-C165-DS-v02_00-en%5B8%5D.pdf?fileId=db3a304412b407950112b43a49a66fd.7）我有固件，所以我也可以通过 Python 读取它。我需要找到一个被排列的字符串0, 1, 2, 3, 4, 5, 6, 7 (0-7)写了这个简单的程序：from itertools import permutations l = list(permutations(range(0,8))) print(len(l))with open("firm.ori", 'rb') as f:    s = f.read()for i in l:    hexstr = '\\x'.join('{:02x}'.format(x) for x in i)    hexstrfinal = "\\0x" + hexstr    #print hexstrfinal    if(s.find(b'hexstrfinal')>0):        print "found"但是，它没有找到任何东西我以为序列会彼此相邻，但也许不是。只想确保程序正确。实际上，0-7 应该是半字节，所以这是否意味着我需要搜索，例如作为一个组合：0x01, 0x23, 0x45, 0x67 以上是字节。有人可以确认这一点并建议如何搜索吗？更新 1：尝试了第二个变体from itertools import permutations l = list(permutations(range(0,8))) print(len(l))with open("firm.ori", 'rb') as f:  s = f.read()for item in l:  str1 = ''.join(str(e) for e in item)  n = 2  out = [str1[i:i+n] for i in range(0, len(str1), n)]  hexstr = '\\x'.join(e for e in out)  hexstrfinal  = "\\x" + hexstr   #print hexstrfinal  if(s.find(b'hexstrfinal')>0):    print "found"但也没有命中...任何想法我做错了什么？

Answer 1

您的代码中有一些误解，并且效率低下。让我们从误解开始。

由于firm.ori以二进制模式 ( rb)打开，因此结果s = f.read()是一个bytes对象。尽管具有与字符串类似的方法，但这不是字符串！它包含字节，而不是字符。当您显示它时，\x...输出不指示bytes包含 ASCII 反斜杠和 xes的对象。相反，每个\x...都是一个转义序列，用于表示与 ASCII 可打印字符不对应的给定字节的十六进制值。

在您的循环中，您专门处理字符串：hexstr = '\\x'.join('{:02x}'.format(x) for x in i)采用您的排列并将其格式化为看起来像一个bytes对象的字符串表示。希望您从上一段中了解为什么这行不通。

s.find(b'hexstrfinal')搜索文字 ASCII 数组b'hexstrfinal'，而不是名为 的变量hexstrfinal。后者当然不起作用，因为hexstrfinal有 type str，而不是bytes. 如果您要将其转换为bytes使用简单的hexstrfinal.encode('ascii')，则会得到b'\\x...'，这根本不是您想要的。正确的方法是

s.find(hexstrfinal.encode('ascii').decode('unicode-escape').encode('latin1'))

希望您能明白为什么将字符串转换三次以获得所需的效率会不必要地低下bytes。任何时候您开始使用字符串作为操纵数字的拐杖时，都是评估您的方法的好时机。这开始了我们对代码效率低下的讨论。

您目前正在尝试遍历 0-7 的所有可能排列，而不是寻找实际存在的排列。鉴于该文件只有 200KB 大小，期望所有甚至大部分排列都出现在其中是不合理的。此外，您正在为每个可能的排列搜索整个文件。对于文件大小N和K排列，您的代码会O(N * K)及时运行，而可以在一次通过文件或O(N). 使用适当的数据结构，即使是用纯 Python 编写的循环也可能比当前代码的优化版本运行得更快。

策略很简单。遍历s. 如果当前字符和以下七个字符构成有效排列，则开始聚会。否则，继续寻找：

N = 8

allowed = set(range(N))

for index, b in enumerate(s):

    if b in allowed and set(s[index:index + N]) == allowed:

        print(f'Found sequence {s[index:index + N]} at offset {index}')

这里有许多可能的优化，你可以用 numpy 或 scipy 更有效地完成整个事情。

如果您允许在序列中重复，事情也会变得更加复杂。在这种情况下，您必须对序列进行排序：

allowed = sorted(...)

N = len(allowed)

for index, b in enumerate(s):

    if b in allowed and sorted(s[index:index + N]) == allowed:

        print(f'Found sequence {s[index:index + N]} at offset {index}')

如果您要搜索小吃，事情会变得更加复杂。我会完全放弃 check b in allowed，只写一个可以在每半步应用的自定义检查：

N = 8

def build_set(items):

    output = set()

    for b in items:

        output.add(b & 0xF)

        output.add((b >> 4) & 0xF)

    return output

def matches(seq):

    if len(seq) == N // 2:

        return build_set(seq) == allowed

    elif len(seq) == N // 2 + 1:

        check = build_set(seq[1:-1])

        check.add(seq[0] & 0xF)

        check.add((seq[-1] >> 4) & 0xF)

        return check == allowed

    else:

        return False

allowed = set(range())

for index, b in enumerate(s):

    if matches(s[index:index + N // 2]):

        print(f'Found sequence {s[index:index + N // 2]} at offset {index}.0')

     if matches(s[index:index + N // 2 + 1]):

        print(f'Found sequence {s[index:index + N // 2 + 1]]} at offset {index}.5')

在这里，build_set只是将半字节分成一组。matches检查一个字节对齐的 8 个半字节数组（4 个元素），或偏移半字节（5 个元素）的 8 个半字节数组。这两个案例都是独立报告的。

Answer 2

目前尚不清楚您要搜索的内容，但是...

的每个排列(0,1,2,3,4,5,6,7)将是一个与此类似的七项元组

t = (7, 6, 4, 1, 3, 5, 0, 2)

你可以像这样制作两个项目的字符串

>>> a = [''.join(map(str,thing)) for thing in zip(t,t[1:])]

>>> a

['76', '64', '41', '13', '35', '50', '02']

然后制作字符串的整数并将其提供给 bytes

>>> b = bytes(map(int,a))

>>> b

b'L@)\r#2\x02'

然后搜索一下

>>> b in s

????

如果它没有找到它就不存在。

这是一个十个字符的字节对象（类似于您的文件）

>>> b = b'\xcbl\x7f|_k\x00\x9f\xa2\xcc'

它恰好是：

>>> bytes([203, 108, 127, 124, 95, 107, 0, 159, 162, 204])

搜索3 个字符（或 3 个整数）序列

>>> bytes([127,94,107]) in b

False

>>> bytes([127,95,107]) in b

False

>>> bytes([124,95,107]) in b

True

>>>

当我处理二进制文件时，我真的认为整数而不是字符。