Tupni: automatic reverse engineering of input formats

ABSTRACT

Recent work has established the importance of automatic reverse engineering of protocol or file format specifications. However, the formats reverse engineered by previous tools have missed important information that is critical for security applications. In this paper, we present Tupni, a tool that can reverse engineer an input format with a rich set of information, including record sequences, record types, and input constraints. Tupni can generalize the format specification over multiple inputs. We have implemented a prototype of Tupni and evaluated it on ten different formats: five file formats (WMF, BMP, JPG, PNG and TIF) and five network protocols (DNS, RPC, TFTP, HTTP and FTP). Tupni identified all record sequences in the test inputs. We also show that, by aggregating over multiple WMF files, Tupni can derive a more complete format specification for WMF. Furthermore, we demonstrate the utility of Tupni by using the rich information it provides for zero-day vulnerability signature generation, which was not possible with previous reverse engineering tools.

REFERENCES

• 1: International Telecommunication Union Recommendation T.81: JPEG Specification. http://www.w3.org/Graphics/JPEG/itu-t81.pdf.
• 2: TIFF Revision 6.0. http://partners.adobe.com/public/developer/en/tiff/TIFF6.pdf.
• 3: Alfred V. Aho , Monica S. Lam , Ravi Sethi , Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools (2nd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2006
• 4: Sanjay Bhansali , Wen-Ke Chen , Stuart de Jong , Andrew Edwards , Ron Murray , Milenko Drinić , Darek Mihočka , Joe Chau, Framework for instruction-level tracing and analysis of program executions, Proceedings of the 2nd international conference on Virtual execution environments, June 14-16, 2006, Ottawa, Ontario, Canada [doi>10.1145/1134760.1220164]
• 5: N. Borisov, D. J. Brumley, H. J. Wang, J. Dunagan, P. Joshi, and C. Guo. A Generic Application-Level Protocol Analyzer and its Language. In Proceedings of the 14th Annual Network & Distributed System Security Symposium (NDSS), March 2007.
• 6: Juan Caballero , Heng Yin , Zhenkai Liang , Dawn Song, Polyglot: automatic extraction of protocol message format using dynamic binary analysis, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315286]
• 7: Magnús M. Halldórsson , Barun Chandra, Greedy local improvement and weighted set packing approximation, Journal of Algorithms, v.39 n.2, p.223-240, May 2001 [doi>10.1006/jagm.2000.1155]
• 8: Mihai Christodorescu , Nicholas Kidd , Wen-Han Goh, String analysis for x86 binaries, Proceedings of the 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, September 05-06, 2005, Lisbon, Portugal
• 9: Manuel Costa , Miguel Castro , Lidong Zhou , Lintao Zhang , Marcus Peinado, Bouncer: securing software by blocking bad input, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 10: Manuel Costa , Jon Crowcroft , Miguel Castro , Antony Rowstron , Lidong Zhou , Lintao Zhang , Paul Barham, Vigilante: end-to-end containment of internet worms, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 11: Jedidiah R. Crandall , Frederic T. Chong, Minos: Control Data Attack Prevention Orthogonal to Memory Model, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.221-232, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.26]
• 12: Weidong Cui , Jayanthkumar Kannan , Helen J. Wang, Discoverer: automatic protocol reverse engineering from network traces, Proceedings of 16th USENIX Security Symposium on USENIX Security Symposium, p.1-14, August 06-10, 2007, Boston, MA
• 13: W. Cui, V. Paxson, N. C. Weaver, and R. H. Katz. Protocol-Independent Adatpive Replay of Application Dialog. In Proceedings of the 13th Symposium on Network and Distributed System Security (NDSS 2006), February 2006.
• 14: Weidong Cui , Marcus Peinado , Helen J. Wang , Michael E. Locasto, ShieldGen: Automatic Data Patch Generation for Unknown Vulnerabilities with Informed Probing, Proceedings of the 2007 IEEE Symposium on Security and Privacy, p.252-266, May 20-23, 2007 [doi>10.1109/SP.2007.34]
• 15: M. D. Ernst, J. H. Perkins, P. J. Guo, S. McCamant, C. Pacheco, M. S. Tschantz, and C. Xiao. The Daikon System for Dynamic Detection of Likely Invariants. 2007.
• 16: R. Fielding , J. Gettys , J. Mogul , H. Frystyk , L. Masinter , P. Leach , T. Berners-Lee, Hypertext Transfer Protocol -- HTTP/1.1, RFC Editor, 1999
• 17: Kathleen Fisher , David Walker , Kenny Q. Zhu , Peter White, From dirt to shovels: fully automatic tool generation from ad hoc data, Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 07-12, 2008, San Francisco, California, USA
• 18: Gaim Instant Messaging Client. http://gaim.sourceforge.net.
• 19: P. Godefroid, M. Levin, and D. Molnar. Automated Whitebox Fuzz Testing. In Proceedings of the 15th Annual Network and Distributed System Security Symposium (NDSS), February 2008.
• 20: T. O. Group. Dce 1.1: Remote procedure call. http://www.opengroup.org/onlinepubs/9629399/toc.htm.
• 21: Elad Hazan , Shmuel Safra , Oded Schwartz, On the complexity of approximating k-set packing, Computational Complexity, v.15 n.1, p.20-39, May 2006 [doi>10.1007/s00037-006-0205-6]
• 22: Jayanthkumar Kannan , Jaeyeon Jung , Vern Paxson , Can Emre Koksal, Semi-automated discovery of application session structure, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177096]
• 23: C. Leita, M. Dacier, and F. Massicotte. Automatic Handling of Protocol Dependencies and Reaction to 0-Day Attacks with ScriptGen based Honeypots. In Proceedings of the 9th International Symposium on Recent Advances in Intrusion Detection, Hamburg, Germany, September 2006.
• 24: Corrado Leita , Ken Mermoud , Marc Dacier, ScriptGen: an automated script generation tool for honeyd, Proceedings of the 21st Annual Computer Security Applications Conference, p.203-214, December 05-09, 2005 [doi>10.1109/CSAC.2005.49]
• 25: Junghee Lim , Thomas Reps , Ben Liblit, Extracting Output Formats from Executables, Proceedings of the 13th Working Conference on Reverse Engineering, p.167-178, October 23-27, 2006 [doi>10.1109/WCRE.2006.29]
• 26: Z. Lin, X. Jiang, D. Xu, and X. Zhang. Automatic Protocol Format Reverse Engineering through Context-Aware Monitored Execution. In Proceedings of NDSS'2008, 2008.
• 27: Zhiqiang Lin , Xiangyu Zhang, Deriving input syntactic structure from execution, Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of software engineering, November 09-14, 2008, Atlanta, Georgia [doi>10.1145/1453101.1453114]
• 28: P. V. Mockapetris, Domain names - implementation and specification, RFC Editor, 1987
• 29: James Newsome , David Brumley , Jason Franklin , Dawn Song, Replayer: automatic protocol replay by binary analysis, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180444]
• 30: J. Newsome, D. Brumley, and D. Song. Vulnerability-specific execution filtering for exploit prevention on commodity software. In Proceeding of the Network and Distributed System Security Symposium (NDSS), 2006.
• 31: J. Newsome and D. Song. Dynamic Taint Analysis for Automatic Detection, Analysis, and Signature Generation of Exploits on Commodity Software. In Proceedings of the 12th Symposium on Network and Distributed System Security (NDSS), February 2005.
• 32: Ruoming Pang , Vern Paxson , Robin Sommer , Larry Peterson, binpac: a yacc for writing application protocol parsers, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177119]
• 33: Vern Paxson, Bro: a system for detecting network intruders in real-time, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.23-24, p.2435-2463, Dec. 1999 [doi>10.1016/S1389-1286(99)00112-7]
• 34: J. Postel , J. K. Reynolds, File Transfer Protocol, RFC Editor, 1985
• 35: The Protocol Informatics Project. http://www.baselineresearch.net/PI/.
• 36: How Samba Was Written. http://samba.org/ftp/tridge/misc/french_cafe.txt.
• 37: K. Sollins, The TFTP Protocol (Revision 2), RFC Editor, 1992
• 38: G. Edward Suh , Jae W. Lee , David Zhang , Srinivas Devadas, Secure program execution via dynamic information flow tracking, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 39: Tom Swan, Inside Windows File Formats, Sams, Indianapolis, IN, 1993
• 40: T. Boutell, PNG (Portable Network Graphics) Specification Version 1.0, RFC Editor, 1997
• 41: Helen J. Wang , Chuanxiong Guo , Daniel R. Simon , Alf Zugenmaier, Shield: vulnerability-driven network filters for preventing known vulnerability exploits, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 42: G. Wondracek, C. Kruegel, E. Kirda, and P. Milani. Automatic Network Protocol Analysis. In Proceedings of the 15th Annual Network and Distributed System Security Symposium (NDSS), February 2008.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

General Terms:
Security

Keywords:
binary analysis, protocol reverse engineering