binpac: a yacc for writing application protocol parsers

ABSTRACT

A key step in the semantic analysis of network traffic is to parse the traffic stream according to the high-level protocols it contains. This process transforms raw bytes into structured, typed, and semantically meaningful data fields that provide a high-level representation of the traffic. However, constructing protocol parsers by hand is a tedious and error-prone affair due to the complexity and sheer number of application protocols.This paper presents binpac, a declarative language and compiler designed to simplify the task of constructing robust and efficient semantic analyzers for complex network protocols. We discuss the design of the binpac language and a range of issues in generating efficient parsers from high-level specifications. We have used binpac to build several protocol parsers for the "Bro" network intrusion detection system, replacing some of its existing analyzers (handcrafted in C++), and supplementing its operation with analyzers for new protocols. We can then use Bro's powerful scripting language to express application-level analysis of network traffic in high-level terms that are both concise and expressive. binpac is now part of the open-source Bro distribution.

REFERENCES

• 1: Mark B. Abbott , Larry L. Peterson, A language-based approach to protocol implementation, IEEE/ACM Transactions on Networking (TON), v.1 n.1, p.4-19, Feb. 1993 [doi>10.1109/90.222903]
• 2: M. Arlitt, B. Krishnamurthy, and J. C. Mogul. Predicting short-transfer latency from TCP arcana: A trace-based validation. In Proceedings of the Internet Measurement Conference (IMC), October 2005.
• 3: Abstract Syntax Notation One (ASN.1). ISOIEC 8824-1:2002.
• 4: Godmar Back, DataScript - A Specification and Scripting Language for Binary Data, Proceedings of the 1st ACM SIGPLAN/SIGSOFT conference on Generative Programming and Component Engineering, p.66-77, October 06-08, 2002
• 5: Edoardo Biagioni , Robert Harper , Peter Lee, A Network Protocol Stack in Standard ML, Higher-Order and Symbolic Computation, v.14 n.4, p.309-356, December 2001 [doi>10.1023/A:1014403914699]
• 6: Thomas P. Blumer , John C. Burruss, Generating a Service Specification of a Connection Management Protocol, Proceedings of the IFIP WG6.1 Second International Workshop on Protocol Specification, Testing and Verification, p.161-170, May 17-20, 1982
• 7: N. Borisov, D. J. Brumley, H. J. Wang, J. Dunagan, P. Joshi, and C. Guo. Generic application-level protocol analyzer and its language. Under submission.
• 8: Common Internet File System. http://www.snia.org/tech_activities/CIFS/CIFS-TR-1p00_FINAL.pdf.
• 9: D. Crocker , P. Overell, Augmented BNF for Syntax Specifications: ABNF, RFC Editor, 1997
• 10: DCE 1.1: Remote procedure call. http://www.opengroup.org/onlinepubs/9629399/toc.htm.
• 11: DSniff. www.monkey.org/dugsong/dsniff.
• 12: The Ethereal Network Analyzer. http://www.ethereal.com/.
• 13: Anja Feldmann , Nils Kammenhuber , Olaf Maennel , Bruce Maggs , Roberto De Prisco , Ravi Sundaram, A methodology for estimating interdomain web traffic demand, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028833]
• 14: R. Fielding , J. Gettys , J. Mogul , H. Frystyk , L. Masinter , P. Leach , T. Berners-Lee, Hypertext Transfer Protocol -- HTTP/1.1, RFC Editor, 1999
• 15: Kathleen Fisher , Robert Gruber, PADS: a domain-specific language for processing ad hoc data, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 16: Kathleen Fisher , Yitzhak Mandelbaum , David Walker, The next 700 data description languages, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.2-15, January 11-13, 2006, Charleston, South Carolina, USA
• 17: M. Handley, C. Kreibich, and V. Paxson. Network Intrusion Detection: Evasion, Traffic Normalization, and End-to-End Protocol Semantics. In Proceedings of USENIX Security Symposium, 2001.
• 18: Gerard J. Holzmann, The Model Checker SPIN, IEEE Transactions on Software Engineering, v.23 n.5, p.279-295, May 1997 [doi>10.1109/32.588521]
• 19: V. Jacobson, C. Leres, and S. McCanne. TCPDUMP. ftp://ftp.ee.lbl.gov/libpcap.tar.Z.
• 20: S. C. Johnson. YACC - Yet Another Compiler-Compiler. Computer Science Technical Report No. 32, Bell Laboratories, Murray Hill, New Jersey, July 1975.
• 21: Jaeyeon Jung , Emil Sit, An empirical study of spam traffic and the use of DNS black lists, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028838]
• 22: Eddie Kohler , M. Frans Kaashoek , David R. Montgomery, A readable TCP in the Prolac protocol language, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.3-13, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 23: C. Kreibich. NetDude (NETwork DUmp data Displayer and Editor). http://netdude.sourceforge.net/.
• 24: C. Kreibich. Design and implementation of netdude, a framework for packet trace manipulation. June 2004.
• 25: A. Kumar, V. Paxson, and N. Weaver. Exploiting Underlying Structure for Detailed Reconstruction of an Internet-scale Event. In Proceedings of the Internet Measurement Conference (IMC), October 2005.
• 26: Peter J. McCann , Satish Chandra, Packet types: abstract specification of network protocol messages, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.321-333, August 28-September 01, 2000, Stockholm, Sweden
• 27: P. V. Mockapetris, Domain names - implementation and specification, RFC Editor, 1987
• 28: NFR Security. http://www.nfr.com.
• 29: Ruoming Pang , Vinod Yegneswaran , Paul Barford , Vern Paxson , Larry Peterson, Characteristics of internet background radiation, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028794]
• 30: T. J. Parr , R. W. Quong, ANTLR: a predicated-LL(k) parser generator, Software—Practice & Experience, v.25 n.7, p.789-810, July 1995 [doi>10.1002/spe.4380250705]
• 31: V. Paxson. BRO: A system for detecting network intruders in real time. In Proceedings of USENIX Security Symposium, San Antonio, TX, January 1998.
• 32: V. Paxson, K. Asanovic, S. Dharmapurikar, J. Lockwood, R. Pang, R. Sommer, and N. Weaver. Rethinking hardware support for network analysis and intrusion prevention. In Proceedings of Workshop on Hot Topics in Security (HotSec), Vancouver, B.C., Canada, July 2006.
• 33: NetWare Core Protocol. http://forge.novell.com/modules/xfmod/project?ncp.
• 34: T. H. Ptacek and T. N. Newsham. Insertion, Evasion, and Denial of Service: Eluding Network Intrusion Detection. Technical report, Secure Networks, Inc., January 1998.
• 35: Martin Roesch, Snort - Lightweight Intrusion Detection for Networks, Proceedings of the 13th USENIX conference on System administration, November 07-12, 1999, Seattle, Washington
• 36: The SNORT network intrusion detection system. http://www.snort.org.
• 37: Stefan Saroiu , Krishna P. Gummadi , Richard J. Dunn , Steven D. Gribble , Henry M. Levy, An analysis of internet content delivery systems, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060319]
• 38: C. Shannon and D. Moore. The Spread of the Witty Worm. http://www.caida.org/analysis/security/witty, 2004.
• 39: R. Srinivasan, RPC: Remote Procedure Call Protocol Specification Version 2, RFC Editor, 1995
• 40: R. Srinivasan, XDR: External Data Representation Standard, RFC Editor, 1995
• 41: Ethereal OSPF Protocol Dissector Buffer Overflow Vulnerability. http://www.idefense.com/intelligence/vulnerabilities/display.php?id=349.
• 42: Snort TCP Stream Reassembly Integer Overflow Exploit. http://www.securiteam.com/exploits/5BP0O209PS.html.
• 43: Symantec Multiple Firewall NBNS Response Processing Stack Overflow. http://www.eeye.com/html/research/advisories/AD20040512A.html.
• 44: tcpdump ISAKMP packet delete payload buffer overflow. http://xforce.iss.net/xforce/xfdb/15680.
• 45: Separation of concerns. http://en.wikipedia.org/wiki/Separation_of_concerns.
• 46: Cynthia Wong , Stan Bielski , Jonathan M. McCune , Chenxi Wang, A study of mass-mailing worms, Proceedings of the 2004 ACM workshop on Rapid malcode, October 29-29, 2004, Washington DC, USA [doi>10.1145/1029618.1029620]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Applications (SMTP, FTP, etc.)

General Terms:
Languages

Keywords:
parser generator, protocol