Volatiles are miscompiled, and what to do about it

ABSTRACT

C's volatile qualifier is intended to provide a reliable link between operations at the source-code level and operations at the memory-system level. We tested thirteen production-quality C compilers and, for each, found situations in which the compiler generated incorrect code for accessing volatile variables. This result is disturbing because it implies that embedded software and operating systems---both typically coded in C, both being bases for many mission-critical and safety-critical applications, and both relying on the correct translation of volatiles---may be being miscompiled.

Our contribution is centered on a novel technique for finding volatile bugs and a novel technique for working around them. First, we present access summary testing: an efficient, practical, and automatic way to detect code-generation errors related to the volatile qualifier. We have found a number of compiler bugs by performing access summary testing on randomly generated C programs. Some of these bugs have been confirmed and fixed by compiler developers. Second, we present and evaluate a workaround for the compiler defects we discovered. In 96% of the cases in which one of our randomly generated programs is miscompiled, we can cause the faulty C compiler to produce correctly behaving code by applying a straightforward source-level transformation to the test program.

REFERENCES

• 1: Hans Boehm and Nick Maclaren. Should volatile acquire atomicity and thread visibility semantics? WG21 Paper N2016, ISO, April 2006. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2016.html.
• 2: Digital Equipment Corporation. DDT kits. http://nar-associates.com/site/sdr/projects/ddt/download/kits/, December 1996.
• 3: Free Software Foundation. GCC, the GNU compiler collection. http://gcc.gnu.org/, 2008.
• 4: Freescale Semiconductor, Inc. CodeWarrior Development Studio. http://www.freescale.com/webapp/sps/site/overview.jsp?nodeId=0127262E70, 2008.
• 5: Douglas Gwyn. NEVERMIND! (was: Re: A question on volatile accesses). USENET post to comp.std.c, November 1990. http://groups.google.com/group/comp.std.c/msg/7709e4162620f2cd.
• 6: Intel Corporation. Intel C++ Compiler 10.1, professional and standard editions, for Linux. http://www.intel.com/cd/software/products/asmo-na/eng/compilers/277618.htm, 2008.
• 7: 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.
• 8: International Organization for Standardization. Information technology -- programming languages -- C -- extensions to support embedded processors. ISO/IEC draft Technical Report 18037, ISO, April 2006. http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1169.pdf.
• 9: Philip Levis et al. T2: A second generation OS for embedded sensor networks. Technical Report TKN-05-007, Telecommunication Networks Group, Technische Universitaet Berlin, November 2005.
• 10: Christian Lindig, Random testing of C calling conventions, Proceedings of the sixth international symposium on Automated analysis-driven debugging, p.3-12, September 19-21, 2005, Monterey, California, USA [doi>10.1145/1085130.1085132]
• 11: Christian Lindig. Quest - an extensible test-code generator for C. http://code.google.com/p/quest-tester/, 2007.
• 12: LLVM Team, University of Illinois at Urbana-Champaign. The LLVM compiler infrastructure project. http://llvm.org/, 2008.
• 13: William M. McKeeman. Differential testing for software. Digital Technical Journal, 10(1):100--107, December 1998.
• 14: George C. Necula , Scott McPeak , Shree Prakash Rahul , Westley Weimer, CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs, Proceedings of the 11th International Conference on Compiler Construction, p.213-228, April 08-12, 2002
• 15: 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
• 16: NULLSTONE Corporation. NULLSTONE for C. http://www.nullstone.com/htmls/ns-c.htm, 2007.
• 17: Flash Sheridan, Practical testing of a C99 compiler using output comparison, Software—Practice & Experience, v.37 n.14, p.1475-1488, November 2007 [doi>10.1002/spe.v37:14]
• 18: Steve Summit. comp.lang.c frequently asked questions. http://c-faq.com/.
• 19: Sun Microsystems, Inc. Sun Studio 12 C, C++, and Fortran compilers and tools. http://developers.sun.com/sunstudio/, 2008.
• 20: Ben L. Titzer , Jens Palsberg, Nonintrusive precision instrumentation of microcontroller software, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 21: Bryan Turner. Random C program generator. http://brturn.googlepages.com/randomcprogramgenerator, January 2007.
• 22: Brian White , Jay Lepreau , Leigh Stoller , Robert Ricci , Shashi Guruprasad , Mac Newbold , Mike Hibler , Chad Barb , Abhijeet Joglekar, An integrated experimental environment for distributed systems and networks, 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.1060313]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Languages, Reliability

Keywords:
automated testing, compiler defect, compiler testing, random program generation, random testing, volatile