Unsupervised clustering of file dialects according to monotonic decompositions of mixtures
This work addresses the challenge of reducing cognitive load for analysts studying complex file formats, though it appears incremental as it builds on existing concepts of message-based classification.
The paper tackles the problem of unsupervised classification of files into dialects based on message patterns, proposing a greedy algorithm that reduces the number of dialects an analyst must consider compared to distinct message patterns.
This paper proposes an unsupervised classification method that partitions a set of files into non-overlapping dialects based upon their behaviors, determined by messages produced by a collection of programs that consume them. The pattern of messages can be used as the signature of a particular kind of behavior, with the understanding that some messages are likely to co-occur, while others are not. Patterns of messages can be used to classify files into dialects. A dialect is defined by a subset of messages, called the required messages. Once files are conditioned upon dialect and its required messages, the remaining messages are statistically independent. With this definition of dialect in hand, we present a greedy algorithm that deduces candidate dialects from a dataset consisting of a matrix of file-message data, demonstrate its performance on several file formats, and prove conditions under which it is optimal. We show that an analyst needs to consider fewer dialects than distinct message patterns, which reduces their cognitive load when studying a complex format.