Elamur Research⌕
☰
home / papers / 2011 / Finding and Understanding Bugs in C Compilers

Finding and Understanding Bugs in C Compilers

Paper · 2011 · Xuejun Yang, Yang Chen, Eric Eide et al.

Summary

Optimizing C compilers are large, intricate systems, and their errors can silently undermine software built on top of them, including verified kernels and safety-critical embedded code. The authors tackle automatic discovery of such defects. They built Csmith, a generator of random C programs for randomized differential testing. Each generated program is compiled by several compilers or option settings and then executed. The program prints a checksum of its global state, and the checksums are compared. A mismatch reveals a bug, and majority voting points to the faulty compiler. The core technical challenge is producing expressive programs, with pointers, nested structs with bit-fields, arrays and rich control flow, that still have exactly one valid meaning. This means they must contain no undefined behavior and not depend on unspecified behavior. Csmith achieves this through constrained generation rules, static analysis and inserted run-time checks. Over three years, the team reported more than 325 new bugs in GCC, LLVM, commercial tools and CompCert. Every compiler they tested both crashed and miscompiled valid input. The results show that fixed test suites are insufficient for compiler quality assurance.

Key points

  • Csmith is a roughly 40,000-line C++ tool. It evolved from Randprog, a random C generator of about 1,600 lines that the authors had earlier extended to about 7,000 lines to test volatile accesses.
  • Generated programs must avoid all 191 kinds of undefined behavior and the 52 kinds of unspecified behavior listed in the C99 standard. Otherwise, wrong-code bugs could not be detected automatically.
  • The authors reported over 325 previously unknown bugs. Most GCC and LLVM reports were fixed, and 25 GCC bugs received P1, the release-blocking priority.
  • Csmith also found wrong-code bugs in the unproved parts of the formally verified compiler CompCert. This shows that verification does not remove the need for testing.
  • The estimated cost was under $1,000 per bug, counting salaries, hardware and overhead. Csmith is open source at embed.cs.utah.edu/csmith.

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

🎓University of UtahSalt Lake City · United States40 works · 6,803 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksInformation Systems · 1,888 worksSoftware · 150 works

Cite

Cite as Xuejun Yang, Yang Chen, Eric Eide and John Regehr. 2011. Finding and Understanding Bugs in C Compilers. PLDI 2011.

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{yang2011finding,
  title = {{Finding and Understanding Bugs in C Compilers}},
  author = {Xuejun Yang, Yang Chen, Eric Eide and John Regehr},
  booktitle = {PLDI 2011},
  year = {2011},
  doi = {10.1145/1993498.1993532},
  url = {https://doi.org/10.1145/1993498.1993532}
}

References

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

  1. ACE Associated Computer Experts. SuperTest C/C++ compiler test and validation suite. http://www.ace.nl/compiler/supertest. html. ↗
  2. F. Bellard. TCC: Tiny C compiler, ver. 0.9.25, May 2009. http://bellard.org/tcc/. ↗
  3. C. L. Biffle. Undefined behavior in Google NaCl, Jan. 2010. http://code.google.com/p/nativeclient/issues/detail?id=245. ↗
  4. 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
  5. C. J. Burgess and M. Saidi. The automatic generation of test cases for optimizing Fortran compilers. Information and Software Technology, 38(2):111–119, 1996. find
  6. E. Eide and J. Regehr. Volatiles are miscompiled, and what to do about it. In Proc. EMSOFT, pages 255–264, Oct. 2008. find
  7. X. Feng and A. J. Hu. Cutpoints for formal equivalence verification of embedded software. In Proc. EMSOFT, pages 307–316, Sept. 2005. find
  8. P. Godefroid, A. Kieżun, and M. Y. Levin. Grammar-based whitebox fuzzing. In Proc. PLDI, pages 206–215, June 2008. find
  9. R. Hamlet. Random testing. In J. Marciniak, editor, Encyclopedia of Software Engineering. Wiley, second edition, 2001. find
  10. K. V. Hanford. Automatic generation of test cases. IBM Systems Journal, 9(4):242–257, Dec. 1970. find
  11. International Organization for Standardization. ISO/IEC 9899:TC2: Programming Languages—C, May 2005. http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf. ↗
  12. G. Klein et al. seL4: Formal verification of an OS kernel. In Proc. SOSP, pages 207–220, Oct. 2009. find
  13. J. C. Knight and N. G. Leveson. An experimental evaluation of the assumption of independence in multiversion programming. IEEE Trans. Software Eng., 12(1):96–109, Jan. 1986. find
  14. X. Leroy. Formal verification of a realistic compiler. Commun. ACM, 52(7):107–115, July 2009. find
  15. C. Lindig. Random testing of C calling conventions. AADEBUG, pages 3–12, Sept. 2005. In Proc. find
  16. W. M. McKeeman. Differential testing for software. Digital Technical Journal, 10(1):100–107, Dec. 1998. find
  17. B. P. Miller, L. Fredriksen, and B. So. An empirical study of the reliability of UNIX utilities. Commun. ACM, 33(12):32–44, Dec. 1990. find
  18. G. Misherghi and Z. Su. HDD: Hierarchical delta debugging. In Proc. ICSE, pages 142–151, May 2006. find
  19. Perennial, Inc. ACVS ANSI/ISO/FIPS-160 C validation suite, ver. 4.5, Jan. 1998. http://www.peren.com/pages/acvs_set.htm. ↗
  20. Plum Hall, Inc. The Plum Hall validation suite for C. //www.plumhall.com/stec.html. http: find
  21. P. Purdom. A sentence generator for testing parsers. BIT Numerical Mathematics, 12(3):366–375, 1972. find
  22. R. L. Sauder. A general test data generator for COBOL. In AFIPS Joint Computer Conferences, pages 317–323, May 1962. find
  23. F. Sheridan. Practical testing of a C99 compiler using output comparison. Software—Practice and Experience, 37(14):1475–1488, Nov. 2007. find
  24. J. Souyris, V. Wiels, D. Delmas, and H. Delseny. Formal verification of avionics software products. In Proc. FM, pages 532–546, Nov. 2009. find
  25. S. Summit. comp.lang.c frequently asked questions. http://c-faq.com/. ↗
  26. Z. Tatlock and S. Lerner. Bringing extensibility to verified compilers. In Proc. PLDI, pages 111–121, June 2010. find
  27. B. Turner. Random Program Generator, Jan. 2007. http://sites.google.com/site/brturn2/randomcprogramgenerator. ↗
  28. B. White et al. An integrated experimental environment for distributed systems and networks. In Proc. OSDI, pages 255–270, Dec. 2002. find
  29. D. S. Wilkerson. Delta ver. 2006.08.03, Aug. 2006. http://delta.tigris.org/. ↗
  30. M. Wolfe. How compilers and tools differ for embedded systems. In Proc. CASES, Sept. 2005. Keynote address. http://www.pgroup.com/lit/articles/pgi_article_cases.pdf. ↗
  31. A. Zeller and R. Hildebrandt. Simplifying and isolating failure-inducing input. IEEE Trans. Software Eng., 28(2):183–200, Feb. 2002. find
  32. C. Zhao et al. Automated test program generation for an industrial optimizing compiler. In Proc. ICSE Workshop on Automation of Software Test, pages 36–43, May 2009. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/yang-2011-finding-understanding-bugs-c-compilers/