基于最佳路径搜索的二进制协议格式关键词边界确定方法

针对二进制协议报文格式逆向分析中字段切分问题,提出以格式关键词为逆向分析目标,通过改进的n-gram算法和最佳路径搜索算法实现对二进制协议格式关键词的最优定界。首先,将位置因素引入n-gram算法,提出基于迭代n-gram-position的格式关键词边界提取算法,有效解决了n-gram算法中n值不易确定和固定偏移位置格式关键词的边界提取问题;然后,定义了频繁项边界命中率和左右分支信息熵为基础的分支度量,以关键词和非关键词的n-gram-position取值变化率存在差异为基础构造约束条件,提出基于最佳路径搜索的格式关键词边界选择算法,实现了对格式关键词的联合最优定界。在AIS1、AIS18、ICMP00、ICMP03和NetB ios五种不同类型协议报文数据集上的测试结果表明,所提算法能够准确确定不同协议格式关键词的边界,F值均在83%以上。与VDV和AutoReEngine经典算法相比,所提算法的F值平均提升约8个百分点。