Abstract:

There are many problems such as repetitive message interaction, blind input and so on in the current protocol fuzzing techniques. This paper presents a fuzzing method based on protocol state migration traversal. The method transforms protocol state migration traversal into a Chinese postman problem, and obtains the shortest path traversing all protocol state transitions. The method then tests each state transition according to the shortest path. In the process of fuzzing, message input is dynamically adjusted through analyzing the response message of protocol entity so as to avoid invalid interaction. In addition, the UIO sequence is used to determine whether the protocol entity state is abnormally migrated or not in order to detect the protocol logic vulnerability in time. Experimental results show that the fuzzing optimization method can significantly improve the fuzzing efficiency and the vulnerability mining ability.

Key words: fuzzing, protocol state machine, protocol state migration, Chinese postman problem, UIO sequence

摘要：

针对现有的协议模糊测试技术存在报文重复交互、输入盲目等问题，提出一种基于协议状态迁移遍历的模糊测试优化方法。该方法将协议状态迁移遍历问题转化为中国邮路问题，求解遍历所有协议状态迁移的最短路径，并依据该最短路径对各个状态迁移进行测试。在测试过程中，通过分析协议实体在执行测试用例后的响应报文，动态调整后续的报文输入，进而避免无效交互。同时利用UIO序列判断协议实体状态是否发生异常迁移，及时检测协议逻辑漏洞。实验结果表明，该模糊测试优化方法可以显著提高测试效率与漏洞挖掘能力。

关键词: 模糊测试, 协议状态机, 协议状态迁移, 中国邮路问题, UIO序列