Unshuffling fields in data formats
arXiv:1910.09964
Abstract
Data format reverse engineering commonly involves identifying conserved format motifs. However, this process typically requires establishing a common ordering for format elements across instances, particularly for formats using type-(length)-value tuples or "chunk" encoding. It is useful to \emph{unshuffle} chunks with common length statistics as a precursor to identifying conserved internal structures. We formalize the unshuffling problem and subsequently derive probabilistic bounds and outline corresponding algorithms for it. We empirically demonstrate unshuffling and highlight connections with the related class of synchronization problems.
arXiv comment6 pages; 7 figures