A Grammatical Inference Approach to Language-Based Anomaly Detection in XML
This work addresses the issue of XML-based attacks for security applications, but it is incremental as it builds on existing language-theoretic methods for anomaly detection.
The paper tackles the problem of false positives in XML-based anomaly detection by proposing a grammatical inference approach that learns a visibly pushdown automaton from example XML documents to detect anomalous syntax, without requiring schemas or tree representations.
False-positives are a problem in anomaly-based intrusion detection systems. To counter this issue, we discuss anomaly detection for the eXtensible Markup Language (XML) in a language-theoretic view. We argue that many XML-based attacks target the syntactic level, i.e. the tree structure or element content, and syntax validation of XML documents reduces the attack surface. XML offers so-called schemas for validation, but in real world, schemas are often unavailable, ignored or too general. In this work-in-progress paper we describe a grammatical inference approach to learn an automaton from example XML documents for detecting documents with anomalous syntax. We discuss properties and expressiveness of XML to understand limits of learnability. Our contributions are an XML Schema compatible lexical datatype system to abstract content in XML and an algorithm to learn visibly pushdown automata (VPA) directly from a set of examples. The proposed algorithm does not require the tree representation of XML, so it can process large documents or streams. The resulting deterministic VPA then allows stream validation of documents to recognize deviations in the underlying tree structure or datatypes.