时间戳

首页 > 解决方案 > 200kB文件搜索8！Python 或 IDA 中的（40320 个排列）

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

问题描述

我正在拆卸 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"

但也没有命中...

任何想法我做错了什么？

标签： pythonidahexdump

解决方案

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

由于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。后者当然行不通，因为hexstrfinalhas type str， not bytes。如果您要将其转换为bytes使用简单的hexstrfinal.encode('ascii')，您会得到b'\\x...'，这根本不是您想要的。正确的方法是

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

希望您能明白为什么将字符串转换 3 次以获得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 个半字节数组。这两个案例都是独立报告的。

推荐阅读