On the Performance Evaluation of Protocol State Machine Reverse Engineering Methods

Abstract

Having access to the specifications of network protocols is essential for several reasons in IT security. When the specifications are not known, one may turn to protocol reverse engineering methods to reconstruct these, typically by analysing recorded network traffic or inspecting an executable that implements the protocol. First, the format and structure of the messages need to be recovered, then the state machine of the protocol itself. Over the years, several solutions have been proposed for both tasks. As a consequence, picking the right solution for a given scenario is often a complex problem that involves evaluating and comparing various solutions. In this paper, we review the current means of evaluating the performance of protocol state machine reverse engineering methods. To help alleviate the shortcomings of the current methodology, we propose two new metrics of performance to be measured: correctness and completeness of output for partial runs (when runtime is bounded). These, combined with previously used metrics should make it easier to pick the most ideal choice for a given use case. We also propose the examination of cases where the algorithms have to work with incomplete or inaccurate syntactical information. We showcase how these new metrics and related information may be useful for the evaluation and comparison of various algorithms by applying these new methods to evaluate the performance of a recent protocol state machine reverse engineering method.

Keywords