CVE-2018-1040漏洞现形记（3）

5 内核有多大

        分析内核，肯定要看内核的大小。有人说windows操作系统有近3000万行代码。当然，这是包含全部的东东，如内核外部得驱动，测试等程序，真正得内核呢？好像有人说，linux得内核大概有200W行代码。估计这个是靠谱得。以此推算，windows也在200-400W行左右，这个也是靠谱得。更重要得是，一旦真正做好了程序，300W或500W只是数字，都不是问题。

        继续深入。我们按200W估计，平均每个函数300行代码，则总计函数不到1W，乐观估计为1W左右。从指令得角度看，如果每个函数有指令500条，则内核指令500W条。当然，内核二进制函数我们不考虑那种直接跳转得过度函数，其实这种在windows下还是有很多的。

        写到这，想到crystal还可以加个功能：显示程序的函数个数，指令条数，全部找出估计没有问题，应该是比较精确的。

        如此大的代码量，程序如何处理呢？显然要考虑时间复杂度和空间复杂度的问题。

6 时间复杂度和空间复杂度

        记得上次检测HEVD.sys时，系统直接死机了。后来看原因，数据访问量过大且过于频繁，内存占用，后台程序的缓冲过多，所有就。。。后来做了点优化，其实算不上优化，只是设计实现上改了点而已。在软件设计上，我一直认为没有解决不了的问题，因为办法总比困难多。

        二进制指令500W条，若按每条指令6字节计算，则有3000W字节，即30M，看来好像不大。但是，从分析角度看，指令中的变量、操作数，类型、函数、操作、控制流、路径、数据流、符号值等，分析的中间数据扩张至少10-100倍。有编译器宣称代码分析的数据扩展最大是500倍，但无法考证。但可以想象扩张很大。

        我们该如何处理呢？首先是空间复杂度问题。30M的100倍就是3G吧，这还只是代码，中间的数据分析等呢？显然从实现的角度很难，只能从设计角度考虑。方案一：将中间数据保存到磁盘文件，如数据库、XML、记事本文件等。方案二，在设计时根据需要动态临时生成中间数据，不需要时丢弃。显然，方案一、方案二各有优势。方案二对设计要求高，而且有许多东西可能临时不能生成，而且在大型系统中，这一设计会极大提高系统的复杂度，给系统的研发、设计、调试、维护、健壮性等方面带来极大困难。对此我们有惨痛教训。方案一实现简单，但对于海量数据而言，数据的访问量将会大增。毕竟我们面对的时一个大而且超级复杂的操作系统代码。前文所述的HEVD.sys访问死机就是一例，而且这种复杂系统的异常情况很多时候显得没有规律性，分析、调试、查找相当困难。从此，我们的教训是，程序越简单越好，所有的高技术都是个屁。有如机械设备永远比电子设备可靠。

        在说了空间复杂度之后，就要说时间复杂度了。在系统中，路径的遍历，多遍的程序前后信息分析，跨文件，跨函数的分析，都会消耗大量的时间。特别是分析循环、递归、循环递归、结构、函数参数、指针、数组、函数返回值类型等，这些很多要前后多遍次的分析。分析1000行指令或10个函数就可以整7-8个小时。一般我能等20分钟就没有耐心了。记得去年有一次分析路径爆炸，一个近千行的程序，好像是某个版本的input函数，真出现了路径爆炸。我花了一个晚上还没有遍历完。一直怀疑是我的程序有问题。可是抽样验证都没有重复。

        对于时间复杂度的解决方案，其实还是从设计和实现的角度解决。有时可用空间换时间。毕竟内存快些，能缓解一点问题。但这个要结合具体事例和具体应用场景来解决，在此就不多说了。

        不过，老实说crystal解决时间问题并不好。一个内核的中等规模程序，我计划用4个小时来做一次全面的深度分析，这是我能忍受的极限。毕竟二进制分析工具的关键在于能全面分析系统，能发现漏洞，至于时间，1天、1周能全面分析并不重要。与当前人工用1个月、几个月乃至半年去找一个漏洞来说，效率还是有极大提高的。（可能这就是我失去持续优化的动力，直接导致crystal效率不高）

        由于涉密原因，在此没有涉及一些具体的解决方案，大家有问题可以在朗曦科技公众号上与团队交流。但是crystal初期可能面临的技术问题，或者说可能的大坑，我都提及了。有心的人如果做过类似东东，会有心有戚戚焉得感受。

       下一节：我被X86的指令系统淹没了。敬请关注。

（未完，待续）

2019.10.31

朗曦科技  林孟尼

[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法