Deriving input syntactic structure from execution

ABSTRACT

Program input syntactic structure is essential for a wide range of applications such as test case generation, software debugging and network security. However, such important information is often not available (e.g., most malware programs make use of secret protocols to communicate) or not directly usable by machines (e.g., many programs specify their inputs in plain text or other random formats). Furthermore, many programs claim they accept inputs with a published format, but their implementations actually support a subset or a variant. Based on the observations that input structure is manifested by the way input symbols are used during execution and most programs take input with top-down or bottom-up grammars, we devise two dynamic analyses, one for each grammar category. Our evaluation on a set of real-world programs shows that our technique is able to precisely reverse engineer input syntactic structure from execution.

REFERENCES

• 1: Libyahoo2: A c library for yahoo! messenger. http://libyahoo2.sourceforge.net/.
• 2: The Protocol Informatics Project. http://www.baselineresearch.net/PI/.
• 3: The SNORT network intrusion detection system. http://www.snort.org.
• 4: Wireshark: The World's Most Popular Network Protocol Analyzer. http://www.wireshark.org/.
• 5: Grammar of HTML Document. http://www.unix.org.ua/orelly/web/html/appa_02.html.
• 6: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 7: Philip Bille, A survey on tree edit distance and related problems, Theoretical Computer Science, v.337 n.1-3, p.217-239, 9 June 2005 [doi>10.1016/j.tcs.2004.12.030]
• 8: David Coppit , Jiexin Lian, yagg: an easy-to-use generator for structured test inputs, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA [doi>10.1145/1101908.1101969]
• 9: 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
• 10: 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]
• 11: 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]
• 12: Patrice Godefroid , Adam Kiezun , Michael Y. Levin, Grammar-based whitebox fuzzing, Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, June 07-13, 2008, Tucson, AZ, USA
• 13: K. Hanford. Automatic Generation of Test Cases. In IBM Systems Journal, 9(4), 1970.
• 14: Z. Lin, X. Jiang, D. Xu and X. Zhang. Automatic Protocol Format Reverse Engineering through Context-Aware Monitored Execution. In Proceedings of the 15th Annual Network and Distributed System Security Symposium (NDSS), 2008.
• 15: Z. Lin and X. Zhang. Deriving Input Syntactic Structure from Execution and Its Applications. Purdue Technical Report CSD TR #08-006, 2008.
• 16: 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]
• 17: Rupak Majumdar , Ru-Gang Xu, Directed test generation using symbolic grammars, Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, November 05-09, 2007, Atlanta, Georgia, USA [doi>10.1145/1321631.1321653]
• 18: Wes Masri , Andy Podgurski , David Leon, Detecting and Debugging Insecure Information Flows, Proceedings of the 15th International Symposium on Software Reliability Engineering, p.198-209, November 02-05, 2004 [doi>10.1109/ISSRE.2004.17]
• 19: Peter M. Maurer, Generating Test Data with Enhanced Context-Free Grammars, IEEE Software, v.7 n.4, p.50-55, July 1990 [doi>10.1109/52.56422]
• 20: Ghassan Misherghi , Zhendong Su, HDD: hierarchical delta debugging, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134307]
• 21: V. Nagarajan, R. Gupta, X. Zhang, M. Madou, B. De Sutter, and K. De Bosschere. Matching control flow of program versions. In Proceedings of the 2007 International Conference on Software Maintenance (ICSM), Paris, 2007.
• 22: Nicholas Nethercote , Julian Seward, Valgrind: a framework for heavyweight dynamic binary instrumentation, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 23: R. Parekh and V. Honavar. Grammar Inference, Automata Induction, and Language Acquisition. 2000.
• 24: P. Purdom. A sentence generator for testing parsers. In BIT Numerical Mathematics, 12(3), 1972.
• 25: L. V. Put, D. Chanet, B. De Bus, B. De Sutter, and K. D. Bosschere. Diablo: a reliable, retargetable and extensible link-time rewriting framework. In Proceedings of IEEE International Symposium On Signal Processing And Information Technology, 2005.
• 26: Emin Gün Sirer , Brian N. Bershad, Using production grammars in software testing, Proceedings of the 2nd conference on Domain-specific languages, p.1-13, October 03-06, 1999, Austin, Texas, United States
• 27: 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
• 28: XiaoFeng Wang , Zhuowei Li , Jun Xu , Michael K. Reiter , Chongkyung Kil , Jong Youl Choi, Packet vaccine: black-box exploit detection and signature generation, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180412]
• 29: G. Wondracek, P. M. Comparetti, C. Kruegel, and E. Kirda. Automatic Network Protocol Analysis. In Proceedings of the 15th Annual Network and Distributed System Security Symposium (NDSS), 2008.
• 30: Weidong Cui , Marcus Peinado , Karl Chen , Helen J. Wang , Luis Irun-Briz, Tupni: automatic reverse engineering of input formats, Proceedings of the 15th ACM conference on Computer and communications security, October 27-31, 2008, Alexandria, Virginia, USA [doi>10.1145/1455770.1455820]
• 31: Bin Xin , Xiangyu Zhang, Efficient online detection of dynamic control dependence, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273489]
• 32: Andreas Zeller , Ralf Hildebrandt, Simplifying and Isolating Failure-Inducing Input, IEEE Transactions on Software Engineering, v.28 n.2, p.183-200, February 2002 [doi>10.1109/32.988498]
• 33: Mingwu Zhang , Xiangyu Zhang , Xiang Zhang , Sunil Prabhakar, Tracing lineage beyond relational operators, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 34: Xiangyu Zhang , Rajiv Gupta, Cost effective dynamic program slicing, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 35: Xiangyu Zhang , Sriraman Tallam , Rajiv Gupta, Dynamic slicing long running programs through execution fast forwarding, Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, November 05-11, 2006, Portland, Oregon, USA [doi>10.1145/1181775.1181786]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Parsing

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Tracing
      D.2.7 Distribution, Maintenance, and Enhancement

General Terms:
Algorithms, Verification

Keywords:
bottom-up grammar, control dependence, input lineage, reverse engineering, syntax tree, top-down grammar