200kB文件要搜索8个！ Python 或 IDA 中的（40320 个排列）
200kB file to search for 8! (40320 permutations) in Python or IDA
我正在 IDA 中反汇编固件（Siemens 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"
但也没有命中...
知道我做错了什么吗？
不清楚您要搜索的内容但是...
(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
>>>
当我想到二进制文件时，我真的认为整数而不是字符。
您的代码中存在一些误解，并且效率低下。先从误区说起吧
由于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 的类型是 str，而不是 bytes。如果您要使用简单的 hexstrfinal.encode('ascii') 将其转换为 bytes，您将得到 b'\x...'，这根本不是您想要的。正确的方法是
s.find(hexstrfinal.encode('ascii').decode('unicode-escape').encode('latin1'))
希望您能明白为什么将字符串转换三次以获得所需的 bytes 是不必要的低效率。每当您开始使用字符串作为操纵数字的拐杖时，都是评估您的方法的好时机。我们将开始讨论您的代码中的低效率问题。
您目前正在尝试遍历 0-7 的所有可能排列，而不是寻找实际存在的排列。鉴于该文件只有 200KB 大小，期望所有甚至大多数排列出现在其中是不合理的。此外，您正在为每个可能的排列搜索整个文件。对于文件大小 N 和 K 排列，您的代码 运行s 在 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 检查在一个字节（4 个元素）上对齐的 8 个半字节数组，或偏移半个字节（5 个元素）的 8 个半字节数组。两个案例都是独立报告的。
我正在 IDA 中反汇编固件（Siemens 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"
但也没有命中...
知道我做错了什么吗？
不清楚您要搜索的内容但是...
(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
>>>
当我想到二进制文件时，我真的认为整数而不是字符。
您的代码中存在一些误解，并且效率低下。先从误区说起吧
由于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 的类型是 str，而不是 bytes。如果您要使用简单的 hexstrfinal.encode('ascii') 将其转换为 bytes，您将得到 b'\x...'，这根本不是您想要的。正确的方法是
s.find(hexstrfinal.encode('ascii').decode('unicode-escape').encode('latin1'))
希望您能明白为什么将字符串转换三次以获得所需的 bytes 是不必要的低效率。每当您开始使用字符串作为操纵数字的拐杖时，都是评估您的方法的好时机。我们将开始讨论您的代码中的低效率问题。
您目前正在尝试遍历 0-7 的所有可能排列，而不是寻找实际存在的排列。鉴于该文件只有 200KB 大小，期望所有甚至大多数排列出现在其中是不合理的。此外，您正在为每个可能的排列搜索整个文件。对于文件大小 N 和 K 排列，您的代码 运行s 在 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 检查在一个字节（4 个元素）上对齐的 8 个半字节数组，或偏移半个字节（5 个元素）的 8 个半字节数组。两个案例都是独立报告的。