Elamur Research⌕
☰
home / papers / 2016 / Synthesizing Program Input Grammars

Synthesizing Program Input Grammars

Paper · 2016 · Osbert Bastani, Rahul Sharma, Alex Aiken et al.

Summary

The paper addresses the problem of automatically inferring a grammar of a program's valid inputs. Official format specifications are often incomplete or not written in machine-readable form. The authors work in a blackbox setting: the program's source code is unavailable, and there are only a few examples of valid inputs (seed inputs). The program can be run on an arbitrary string to see whether it accepts it (membership oracle). The algorithm starts with a language containing only the example and gradually extends it. First, it adds repetitions and alternations, as in regular expressions. Then it adds recursive rules for nested structures such as matching parentheses, and also generalizes constants. Each extension is checked by generated queries to the program, so overly general candidates are rejected. The implementation is called GLADE. It is noticeably more accurate and faster than the classical L-Star and RPNI. The synthesized grammars drive a grammar-based fuzzer, which increases code coverage with valid inputs. The work is important for testing, reverse engineering of formats, and input whitelisting.

Key points

  • The GLADE tool (Grammar Learning for AutomateD Execution) is open source: github.com/obastani/glade. The authors are from Stanford and Microsoft Research India.
  • Grammar quality is evaluated through precision and recall. For this, strings are sampled from probabilistic versions of the target and synthesized grammars.
  • L-Star and RPNI failed to learn even a simple XML-like language. They either overgeneralize (to Σ*) or undergeneralize, and with few examples they are also slow.
  • When fuzzing with valid inputs only, GLADE covers up to 6× more new lines of code than a naive fuzzer and afl-fuzz.
  • The authors consider this the first practical blackbox approach for complex recursive formats: XML, regular expression syntax, and programming languages.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Stanford UniversityStanford · United States567 works · 335,189 citations🏢Microsoft ResearchBengaluru · India19 works · 4,213 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksComputational Theory and Mathematics · 496 worksSoftware · 150 works

Cite

Cite as Osbert Bastani, Rahul Sharma, Alex Aiken and Percy Liang. 2016. Synthesizing Program Input Grammars. arXiv:1608.01723.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1608.01723 · arXiv 1608.01723

@misc{bastani2016synthesizing,
  title = {{Synthesizing Program Input Grammars}},
  author = {Osbert Bastani, Rahul Sharma, Alex Aiken and Percy Liang},
  year = {2016},
  doi = {10.48550/arxiv.1608.01723},
  eprint = {1608.01723},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1608.01723}
}

References

68 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. A. Albarghouthi, S. Gulwani, and Z. Kincaid. Recursive program synthesis. In Computer Aided Verification, pages 934–950. Springer, 2013. find
  2. S. Anand, E. K. Burke, T. Y. Chen, J. Clark, M. B. Cohen, W. Grieskamp, M. Harman, M. J. Harrold, P. McMinn, et al. An orchestrated survey of methodologies for automated software test case generation. Journal of Systems and Software, 86(8):1978–2001, 2013. find
  3. D. Angluin. Learning regular sets from queries and counterexamples. Information and computation, 75(2):87–106, 1987. find
  4. S. Artzi, A. Kiezun, J. Dolby, F. Tip, D. Dig, A. Paradkar, and M. D. Ernst. Finding bugs in dynamic web applications. In Proceedings of the 2008 international symposium on Software testing and analysis, pages 261–272. ACM, 2008. find
  5. B. Bollig, J.-P. Katoen, C. Kern, M. Leucker, D. Neider, and D. R. Piegdon. libalf: The automata learning framework. In International Conference on Computer Aided Verification, pages 360–364. Springer, 2010. find
  6. M. Botinčan and D. Babić. Sigma*: Symbolic learning of input-output specifications. In Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 443–456, 2013. find
  7. A. S. Boujarwah and K. Saleh. Compiler test case generation methods: a survey and assessment. Information and software technology, 39(9):617–625, 1997. find
  8. J. Caballero, H. Yin, Z. Liang, and D. Song. Polyglot: Automatic extraction of protocol message format using dynamic binary analysis. In Proceedings of the 14th ACM conference on Computer and communications security, pages 317–329. ACM, 2007. find
  9. C. Cadar and K. Sen. Symbolic execution for software testing: three decades later. Communications of the ACM, 56(2):82– 90, 2013. find
  10. C. Cadar, D. Dunbar, D. R. Engler, et al. Klee: Unassisted and automatic generation of high-coverage tests for complex systems programs. In OSDI, volume 8, pages 209–224, 2008. find
  11. C. Cadar, V. Ganesh, P. M. Pawlowski, D. L. Dill, and D. R. Engler. Exe: automatically generating inputs of death. ACM Transactions on Information and System Security (TISSEC), 12(2):10, 2008. find
  12. C. Y. Cho, D. Babic, P. Poosankam, K. Z. Chen, E. X. Wu, and D. Song. Mace: Model-inference-assisted concolic exploration for protocol and vulnerability discovery. In USENIX Security Symposium, pages 139–154, 2011. find
  13. W. Choi, G. Necula, and K. Sen. Guided gui testing of android apps with minimal restart and approximate learning. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages &\#38; Applications, pages 623–640, 2013. find
  14. C. De la Higuera. Grammatical inference: learning automata and grammars. Cambridge University Press, 2010. find
  15. ECMA International. Standard ECMA-262: ECMA 2015 Language Specification. 6 edition, June 2015. find
  16. J. K. Feser, S. Chaudhuri, and I. Dillig. Synthesizing data structure transformations from input-output examples. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 229–239. ACM, 2015. find
  17. J. E. Forrester and B. P. Miller. An empirical study of the robustness of windows nt applications using random testing. In Proceedings of the 4th USENIX Windows System Symposium, pages 59–68. Seattle, 2000. find
  18. V. Ganesh, T. Leek, and M. Rinard. Taint-based directed whitebox fuzzing. In Proceedings of the 31st International Conference on Software Engineering, pages 474–484. IEEE Computer Society, 2009. find
  19. D. Giannakopoulou, Z. Rakamarić, and V. Raman. Symbolic learning of component interfaces. In International Static Analysis Symposium, pages 248–264. Springer, 2012. find
  20. GNU. Gnu bison. bison, 2014. https://www.gnu.org/software/ ↗
  21. GNU Grep. https://www.gnu.org/software/grep/manual, 2016. ↗
  22. P. Godefroid, N. Klarlund, and K. Sen. Dart: Directed automated random testing. In Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 213–223. ACM, 2005. find
  23. P. Godefroid, A. Kiezun, and M. Y. Levin. Grammar-based whitebox fuzzing. In Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 206–215, 2008. find
  24. P. Godefroid, M. Y. Levin, D. A. Molnar, et al. Automated whitebox fuzz testing. In NDSS, volume 8, pages 151–166, 2008. find
  25. E. M. Gold. Language identification in the limit. Information and control, 10(5):447–474, 1967. find
  26. S. Gulwani. Automating string processing in spreadsheets using input-output examples. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 317–330, 2011.
  27. W. R. Harris and S. Gulwani. Spreadsheet table transformations from examples. In Proceedings of the 32Nd ACM SIG-PLAN Conference on Programming Language Design and Implementation, pages 317–328, 2011. find
  28. C. Holler, K. Herzig, and A. Zeller. Fuzzing with code fragments. In Presented as part of the 21st USENIX Security Symposium (USENIX Security 12), pages 445–458, 2012. find
  29. M. Höschele and A. Zeller. Mining input grammars from dynamic taints. In Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering, pages 720–725. ACM, 2016. find
  30. L. Huang, J. Jia, B. Yu, B.-G. Chun, P. Maniatis, and M. Naik. Predicting execution time of computer programs using sparse polynomial regression. In Advances in Neural Information Processing Systems, pages 883–891, 2010. find
  31. H. Ishizaka. Polynomial time learnability of simple deterministic languages. Machine Learning, 5(2):151–164, 1990. find
  32. B. Knobe and K. Knobe. A method for inferring context-free grammars. Information and Control, 31(2):129–146, 1976. find
  33. L. Lee. Learning of context-free languages: A survey of the literature. Techn. Rep. TR-12-96, Harvard University, 1996. find
  34. A. Leung, J. Sarracino, and S. Lerner. Interactive parser synthesis by example. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 565–574. ACM, 2015. find
  35. Z. Lin and X. Zhang. Deriving input syntactic structure from execution. In Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of software engineering, pages 83–93. ACM, 2008. find
  36. Z. Lin, X. Zhang, and D. Xu. Reverse engineering input syntactic structure from program execution and its applications. Software Engineering, IEEE Transactions on, 36(5):688–703, 2010. find
  37. C. Lindig. Random testing of c calling conventions. In Proceedings of the sixth international symposium on Automated analysis-driven debugging, pages 3–12. ACM, 2005. find
  38. R. Majumdar and R.-G. Xu. Directed test generation using symbolic grammars. In Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, pages 134–143. ACM, 2007. find
  39. B. P. Miller, L. Fredriksen, and B. So. An empirical study of the reliability of unix utilities. Communications of the ACM, 33(12):32–44, 1990. find
  40. B. P. Miller, G. Cooksey, and F. Moore. An empirical study of the robustness of macos applications using random testing. In Proceedings of the 1st international workshop on Random testing, pages 46–54. ACM, 2006. find
  41. M. Naik, H. Yang, G. Castelnuovo, and M. Sagiv. Abstractions from tests. pages 373–386, 2012. find
  42. N. Nethercote and J. Seward. Valgrind: A framework for heavyweight dynamic binary instrumentation. In Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 89–100, 2007. find
  43. P. Norvig. http://norvig.com/lispy.html, 2010. ↗
  44. J. Oncina and P. Garcı́a. Identifying regular languages in polynomial time. Advances in Structural and Syntactic Pattern Recognition, 5(99-108):15–20. find
  45. Oracle America, Inc. The Java TM Virtual Machine Specification. 7 edition, July 2011. find
  46. D. Perelman, S. Gulwani, D. Grossman, and P. Provost. Test-driven synthesis. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 408–418, 2014. find
  47. O. Polozov and S. Gulwani. Flashmeta: A framework for inductive program synthesis. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 107–126. ACM, 2015. find
  48. P. Purdom. A sentence generator for testing parsers. BIT Numerical Mathematics, 12(3):366–375, 1972. find
  49. M. Rinard. Acceptability-oriented computing. pages 221– 239, 2003. find
  50. M. C. Rinard. Living in the comfort zone. pages 611–622, 2007. find
  51. R. L. Sauder. A general test data generator for cobol. In Proceedings of the May 1-3, 1962, spring joint computer conference, pages 317–323. ACM, 1962. find
  52. K. Sen, D. Marinov, and G. Agha. CUTE: a concolic unit testing engine for C, volume 30. ACM, 2005. find
  53. R. Singh and S. Gulwani. Synthesizing number transformations from input-output examples. In Computer Aided Verification, pages 634–651. Springer, 2012. find
  54. R. J. Solomonoff. A new method for discovering the grammars of phrase structure languages. In Information Processing. Unesco, Paris, 1960. find
  55. Stack Overflow. http://stackoverflow.com/questions/3809401/what-is-a-good-regular-expression-to-match-a-url, 2010. ↗
  56. A. Stolcke. Bayesian learning of probabilistic language models. PhD thesis. find
  57. A. Stolcke and S. Omohundro. Inducing probabilistic grammars by bayesian model merging. Grammatical inference and applications, pages 106–118, 1994. find
  58. Z. Su and G. Wassermann. The essence of command injection attacks in web applications. In Conference Record of the 33rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 372–382, 2006. find
  59. M. Sutton and A. Greene. The art of file format fuzzing. In Blackhat USA conference, 2005. find
  60. M. Sutton, A. Greene, and P. Amini. Fuzzing: brute force vulnerability discovery. Pearson Education, 2007. find
  61. The Flex Project. Flex: The fast lexical analyzer. http://flex.sourceforge.net, 2008. ↗
  62. A. Vardhan, K. Sen, M. Viswanathan, and G. Agha. Learning to verify safety properties. In International Conference on Formal Engineering Methods, pages 274–289. Springer, 2004. find
  63. J. Viide, A. Helin, M. Laakso, P. Pietikäinen, M. Seppänen, K. Halunen, R. Puuperä, and J. Röning. Experiences with model inference assisted fuzzing. In WOOT, 2008. find
  64. W3C. https://www.w3.org/TR/2008/REC-xml-20081126, 2008. ↗
  65. T. Wang, T. Wei, G. Gu, and W. Zou. Taintscope: A checksum-aware directed fuzzing tool for automatic software vulnerability detection. In Security and privacy (SP), 2010 IEEE symposium on, pages 497–512. IEEE, 2010. find
  66. G. Wondracek, P. M. Comparetti, C. Kruegel, E. Kirda, and S. S. S. Anna. Automatic network protocol analysis. In NDSS, volume 8, pages 1–14, 2008. find
  67. X. Yang, Y. Chen, E. Eide, and J. Regehr. Finding and understanding bugs in c compilers. In Proceedings of the 32Nd ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 283–294, 2011.
  68. M. Zalewski. American fuzzy lop. coredump.cx/afl, 2015. http://lcamtuf. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/bastani-2016-synthesizing-program-input-grammars/