Robert Luh, Gregor Schramm, Markus Wagner and Sebastian Schrittwieser, “Sequitur-based inference and analysis framework for malicious system behavior”, 1st International Workshop on FORmal methods for Security Engineering (ForSE)

Targeted attacks on IT systems are a rising threat against the confidentiality of sensitive data and the availability of critical systems. With the emergence of Advanced Persistent Threats (APTs), it has become more important than ever to fully understand the particulars of such attacks. Grammar inference offers a powerful foundation for the automated extraction of behavioral patterns from sequential system traces.
In order to facilitate the interpretation and analysis of APTs, we present a grammar inference system based on Sequitur, a greedy compression algorithm that constructs a context-free grammar (CFG) from string-based input data. Next to recursive rule extraction, we expanded the procedure through automated assessment routines capable of dealing with multiple input sources and types. This enables the identification of relevant patterns in sequential corpora of arbitrary quantity and size. On the formal side, we extended the CFG with attributes that help depict the extracted (malicious) actions in a comprehensive fashion. The tool’s output is automatically mapped to the grammar for further parsing and discovery-focused pattern visualization.