[NOTE] Matryoshka: Fuzzing Deeply Nested Branches (CCS 19)

之前已经有很多文章通过污点分析等技术观察影响条件判断语句的字节位置,通过变异指定字节来尝试改变判断的结果。但是,当出现深层嵌套的条件判断时,对影响目标条件判断的字节进行变异,可能会导致外层的条件判断结果改变,进而根本无法到达目标条件判断,这是本文试图解决的问题。

对于一个条件判断语句,Matryoshka首先使用常规的求解方式,如果失败了,再依次使用prioritize reachability、prioritize satisfiability、joint optimization 这三种方式。

在上述三种方式执行之前,有以下几个信息需要收集:

  1. 获得prior conditional statements。对于目标条件判断语句,首先要收集其prior conditional statements, 即在目标条件判断之前的,结果的改变能够影响目标条件判断能否到达的条件判断语句。
  2. 获得effective prior conditional statements。假如条件判断语句St受到字节位置1影响,该位置同时也能影响St的一个prior conditional statement Sp,那么Sp就是St的一个effective prior conditional statement。显然,为了求解St,需要着重关注它的effective prior conditional statement,因为其它的prior conditional statements并不会受到St对应字节位置变异的影响,而是类似于Sp这样的条件判断可能会发生判断结果的改变,影响St的可达性。

有了上述的关键信息(原文中描述该收集过程为Determine control and taint flow dependency),首先使用prioritize reachability。这是一种悲观的变异方式,它假设所有对能够同时影响目标条件判断和其effective prior conditional statements的字节的变异都会影响effective prior conditional statements的判断结果,进而影响可达性。因此,它只对能够影响目标条件判断却不能影响effective prior statements的字节位置进行变异。

如果上述过程没有成功解决,则尝试prioritize satisfiability。这时一种乐观的变异方式,它假设所有对影响目标条件判断的字节的变异都不会影响其可达性,因此,通过故意保持所有prioritize conditional statements的判断结果,判断变异是否解决了目标条件判断。如果解决了,再用原始的目标程序运行一遍该输入,检查是否真的没有影响其prioritize conditional statements。如果真的没有印象,成功解决;如果有影响,再回溯并fuzz解决各个prioritize conditional statements。

如果上述过程还没有成功解决,则尝试joint optimization。它要求同时满足由目标条件判断和其prioritize conditional statements导出的方程,并采取了一系列优化措施。

No Comments

Leave a Reply

Your email address will not be published. Required fields are marked *