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

Question

我正在IDA中反汇编固件（西门子C165处理器-https://www.infineon.com/dgdl/Infineon-C165-DS-v02_00-en%5B8%5D.pdf?fileId=db3a304412b407950112b43a49a66fd7）。你知道吗

我有固件，所以我也可以通过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

现在还不清楚你在寻找什么，但是。。。你知道吗

每个(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
????

如果它找不到它就不在那里。你知道吗

---

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

>>> 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
>>>

---

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

Answer 2

您的代码中存在一些误解，而且效率低下。让我们从误解开始。你知道吗

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

在循环中，您只处理字符串：hexstr = '\\x'.join('{:02x}'.format(x) for x in i)接受您的排列并将其格式化为bytes对象的字符串表示形式。希望你能从上一段理解为什么这行不通。你知道吗

s.find(b'hexstrfinal')搜索文本ASCII数组b'hexstrfinal'，而不是名为hexstrfinal的变量。后者当然不起作用，因为hexstrfinal的类型是str，而不是bytes。如果用一个简单的hexstrfinal.encode('ascii')把它转换成bytes，你会得到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}')

如果你想寻找一点点，事情会变得更复杂。我会完全放弃检查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个元素），或偏移半字节的8个半字节的数组（5个元素）。这两个病例都是独立报告的。你知道吗