An Incremental Learner for Language-Based Anomaly Detection in XML

Research output: Chapter in Book/Report/Conference proceedingsConference contributionpeer-review

1 Citation (Scopus)


The Extensible Markup Language (XML) is a complex language, and consequently, XML-based protocols are susceptible to entire classes of implicit and explicit security problems. Message formats in XML-based protocols are usually specified in XML Schema, and as a first-line defense, schema validation should reject malformed input. However, extension points in most protocol specifications break validation. Extension points are wildcards and considered best practice for loose composition, but they also enable an attacker to add unchecked content in a document, e.g., for a signature wrapping attack. This paper introduces datatyped XML visibly pushdown automata (dXVPAs) as language representation for mixed-content XML and presents an incremental learner that infers a dXVPA from example documents. The learner generalizes XML types and datatypes in terms of automaton states and transitions, and an inferred dXVPA converges to a good-enough approximation of the true language. The automaton is free from extension points and capable of stream validation, e.g., as an anomaly detector for XML-based protocols. For dealing with adversarial training data, two scenarios of poisoning are considered: a poisoning attack is either uncovered at a later time or remains hidden. Unlearning can therefore remove an identified poisoning attack from a dXVPA, and sanitization trims low-frequent states and transitions to get rid of hidden attacks. All algorithms have been evaluated in four scenarios, including a web service implemented in Apache Axis2 and Apache Rampart, where attacks have been simulated. In all scenarios, the learned automaton had zero false positives and outperformed traditional schema validation.

Original languageEnglish
Title of host publicationProceedings - 2016 IEEE Symposium on Security and Privacy Workshops, SPW 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages15
ISBN (Electronic)9781509008247
Publication statusPublished - 1 Aug 2016
Event2016 IEEE Symposium on Security and Privacy Workshops, SPW 2016 - San Jose, United States
Duration: 23 May 201625 May 2016

Publication series

NameProceedings - 2016 IEEE Symposium on Security and Privacy Workshops, SPW 2016


Conference2016 IEEE Symposium on Security and Privacy Workshops, SPW 2016
Country/TerritoryUnited States
CitySan Jose


  • anomaly detection
  • experimental evaluation
  • grammatical inference
  • stream validation
  • visibly pushdown automata
  • XML


Dive into the research topics of 'An Incremental Learner for Language-Based Anomaly Detection in XML'. Together they form a unique fingerprint.

Cite this