Team for Research in
Ubiquitous Secure Technology

Citation
Domagoj Babic, Daniel Reynaud, Dawn Song. "Malware Analysis with Tree Automata Inference". Proceedings of the 23rd international conference on Computer aided verification, ACM, 2011.

Abstract
The underground malware-based economy is flourishing and it is evident that the classical ad-hoc signature detection methods are becoming insufficient. Malware authors seem to share some source code and malware samples often feature similar behaviors, but such commonalities are difficult to detect with signature-based methods because of an increasing use of numerous freelyavailable randomized obfuscation tools. To address this problem, the security community is actively researching behavioral detection methods that commonly attempt to understand and differentiate how malware behaves, as opposed to just detecting syntactic patterns. We continue that line of research in this paper and explore how formal methods and tools of the verification trade could be used for malware detection and analysis. We propose a new approach to learning and generalizing from observed malware behaviors based on tree automata inference. In particular, we develop an algorithm for inferring k-testable tree automata from system call dataflow dependency graphs and discuss the use of inferred automata in malware recognition and classification.

Electronic downloads

• 2011%20cav11malware.pdf · application/pdf · 331 kbytes

• HTML

  Domagoj Babic, Daniel Reynaud, Dawn Song. <a
  href="http://www.truststc.org/pubs/856.html"
  >Malware Analysis with Tree Automata Inference</a>,
  Proceedings of the 23rd international conference on Computer
  aided verification, ACM, 2011.

• Plain text

  Domagoj Babic, Daniel Reynaud, Dawn Song. "Malware
  Analysis with Tree Automata Inference". Proceedings of
  the 23rd international conference on Computer aided
  verification, ACM, 2011.

• BibTeX

  @inproceedings{BabicReynaudSong11_MalwareAnalysisWithTreeAutomataInference,
      author = {Domagoj Babic and Daniel Reynaud and Dawn Song},
      title = {Malware Analysis with Tree Automata Inference},
      booktitle = {Proceedings of the 23rd international conference
                on Computer aided verification},
      organization = {ACM},
      year = {2011},
      abstract = {The underground malware-based economy is
                flourishing and it is evident that the classical
                ad-hoc signature detection methods are becoming
                insufficient. Malware authors seem to share some
                source code and malware samples often feature
                similar behaviors, but such commonalities are
                difficult to detect with signature-based methods
                because of an increasing use of numerous
                freelyavailable randomized obfuscation tools. To
                address this problem, the security community is
                actively researching behavioral detection methods
                that commonly attempt to understand and
                differentiate how malware behaves, as opposed to
                just detecting syntactic patterns. We continue
                that line of research in this paper and explore
                how formal methods and tools of the verification
                trade could be used for malware detection and
                analysis. We propose a new approach to learning
                and generalizing from observed malware behaviors
                based on tree automata inference. In particular,
                we develop an algorithm for inferring k-testable
                tree automata from system call dataflow dependency
                graphs and discuss the use of inferred automata in
                malware recognition and classification.},
      URL = {http://www.truststc.org/pubs/856.html}
  }
  

Posted by Mary Stewart on 4 Apr 2012.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.