未找到readme所说的跳过完整解压的实现

[aviraxp]

现代apk dex都是压缩的，很好奇怎么跳过完整解压，特别是字符串搜索的情形下

[MG1937]

感谢大佬的关注！！跳块解压目前是一个实验性功能，会在blackhat现场演示，我自己测试的时候由于部分情况没有命中字符串所以还得再修修，直接合入项目可能会导致项目可用性出现问题，那就会被喷烂了哈哈😭，所以我在这里描述一下思路以及我自己的测试情况（我说的时候可能不太清楚，就顺着脑子想到哪说到哪了哈哈）：

1. 最早的时候我是这样构想的，我希望能够快速命中class具体位于哪个dex内，把apk内所有dex一个个解压下来去定位还是太慢了，我又想到既然我要去命中class，我本质上（第一步）不就是在dex的string段里面搜“ Lxxx/yyy/zzz;”吗，同时lz77去压缩数据的时候，不是会通过霍夫曼编码一个当前block内特定的sym去代替某段重复数据吗，比如有一段数据03 9e 53 00 2a 9e 53 00，lz77发现很多个9e 53 00可以被压缩，比如就会给霍夫曼树分配一个sym <3, 4>，由于string id list, type id list内的offset，id阿之类的都是规律增长的，就会有非常非常多的sym <3, 4>，但我想要快速定位到string段，这些东西我自然是不需要的对不对（跳块解压），同时又由于lz77的block大概有32kb，基本至少要覆盖掉header和string id list的一部分，那我就先正常解压dex的头部0x70，拿到string ids off，再顺序解压1个byte，就可以拿到第一个string的offset，也就是string段的开头的地址，然后每个deflate block大概32kb左右（我拿某厂apk做过实验，有些block确实会非常小只有几kb），那就大约跳过string offset/32kb个块就可以到string所在段的block了，这个时候我再顺序解压，就能不用deflate string段前面那么一大堆ids off之类的臃肿的数据了。
2. 问题是你就算直接跳到string段所在block了，正常deflate是要依赖前几个block解压出来的数据哇！那你没有之前的数据你不是会解压出没法解析的sym吗？不会滴！记得我说class都是纯字符串吗，之前几个ids段基本全是没法被解析为可见字符的byte，string段内的class字符不可能跳到几个block之外去复制数据的！
3. 其次是跳块也得正常解霍夫曼码阿，你不解码没法知道sym 256具体长啥样阿，这你要咋跳块？？还真是，最开始我搞得方案就非常抽象，我去正常拿到第一个block的开头解霍夫曼树拿到sym256，由于sym256必然在块末尾，那至少这一段block恰好匹配这个sym256的bit流只有一个，并且末尾跟着一个BINAL=0（string段结束后BFINAL也必然是0，所以无所谓），但实际情况是我想简单了，根本没法直接跳到下一个block开头，并且有非常多的误命中导致实际解压速度反而慢了，所以我后来换成去改libdeflate的实现，其中一个原因是因为libdeflate解bit流的时候会根据当前霍夫曼树+固定bit长度暴力建表，然后就能不解霍夫曼码O(1)快速跳到下一个block，跳到string段所在block的速度相当快，测试了一下定位某厂apk的“Lio/reactivex/android/MainThreadDisposable;”字符串，速度快了一半：
   跳块解压：

py test.py douyinneice.apk --workers 8 "Lio/reactivex/android/MainThreadDisposable;"
Hit found in: classes30.dex
Workers used: 8
Total fast_dex time across all threads: 170.220 ms
Total exact-lookup time across all threads: 49.451 ms
Total script execution time: 84.425 ms

目前ASC：

py main.py getclass --thread 8 --debug xxx.apk io/reactivex/android/MainThreadDisposable
[APK] scan setup=5709.50 us entries=58
[APK] [T56b0] 'classes54.dex' inflate=6820.00 us lookup=49.90 us hit=False
[APK] [T4b94] 'classes2.dex' inflate=21667.20 us lookup=66.60 us hit=False
[APK] [T9994] 'classes8.dex' inflate=23051.40 us lookup=94.00 us hit=False
[APK] [T98ec] 'classes12.dex' inflate=25450.80 us lookup=47.60 us hit=False
[APK] [T9bf0] 'classes24.dex' inflate=27875.50 us lookup=55.30 us hit=False
[APK] [T8ed8] 'classes11.dex' inflate=28006.50 us lookup=48.50 us hit=False
[APK] [T56b0] 'classes34.dex' inflate=24752.00 us lookup=67.10 us hit=False
[APK] [T8598] 'classes.dex' inflate=30362.60 us lookup=104.30 us hit=False
[APK] [T4544] 'classes53.dex' inflate=34168.90 us lookup=49.40 us hit=False
[APK] [T4b94] 'classes23.dex' inflate=26837.10 us lookup=60.90 us hit=False
[APK] [T9994] 'classes16.dex' inflate=25813.10 us lookup=38.30 us hit=False
[APK] [T56b0] 'classes18.dex' inflate=26597.60 us lookup=48.30 us hit=False
[APK] [T8598] 'classes46.dex' inflate=25455.60 us lookup=44.00 us hit=False
[APK] [T8ed8] 'classes33.dex' inflate=29345.10 us lookup=36.30 us hit=False
[APK] [T4544] 'classes6.dex' inflate=26217.60 us lookup=28.20 us hit=False
[APK] [T9bf0] 'classes4.dex' inflate=31397.80 us lookup=26.90 us hit=False
[APK] [T98ec] 'classes15.dex' inflate=38820.70 us lookup=49.10 us hit=False
[APK] [T4b94] 'classes20.dex' inflate=29654.50 us lookup=41.90 us hit=False
[APK] [T9994] 'classes50.dex' inflate=31313.40 us lookup=44.60 us hit=False
[APK] [T4544] 'classes48.dex' inflate=24196.00 us lookup=364.80 us hit=False
[APK] [T8598] 'classes7.dex' inflate=28582.00 us lookup=23.80 us hit=False
[APK] [T9bf0] 'classes22.dex' inflate=29188.00 us lookup=57.50 us hit=False
[APK] [T8ed8] 'classes55.dex' inflate=31807.10 us lookup=42.30 us hit=False
[APK] [T98ec] 'classes41.dex' inflate=30099.60 us lookup=39.50 us hit=False
[APK] [T56b0] 'classes21.dex' inflate=42455.70 us lookup=29.30 us hit=False
[APK] [T4b94] 'classes39.dex' inflate=28375.70 us lookup=57.70 us hit=False
[APK] [T9994] 'classes27.dex' inflate=25491.00 us lookup=28.60 us hit=False
[APK] [T8598] 'classes32.dex' inflate=25481.10 us lookup=45.80 us hit=False
[APK] [T4544] 'classes51.dex' inflate=28461.40 us lookup=27.90 us hit=False
[APK] [T9bf0] 'classes42.dex' inflate=27846.90 us lookup=46.90 us hit=False
[APK] [T8ed8] 'classes10.dex' inflate=28303.90 us lookup=28.50 us hit=False
[APK] [T98ec] 'classes25.dex' inflate=29347.00 us lookup=47.60 us hit=False
[APK] [T56b0] 'classes29.dex' inflate=27039.90 us lookup=28.70 us hit=False
[APK] [T4b94] 'classes19.dex' inflate=28401.80 us lookup=39.00 us hit=False
[APK] [T9994] 'classes30.dex' inflate=29564.60 us lookup=61.10 us hit=True
[APK] getclass total=151870.50 us