Segment protection for embedded systems using run-time checks

ABSTRACT

The lack of virtual memory protection is a serious source of unreliability in many embedded systems. Without the segment-level protection it provides, these systems are subject to memory access violations, stemming from programmer error, whose results can be dangerous and catastrophic in safety-critical systems. The traditional method of testing embedded software before its deployment is an insufficient means of detecting and debugging all software errors, and the reliance on this practice is a severe gamble when the reliable performance of the embedded device is critical. Additionally, the use of safe languages and programming semantic restrictions as prevention mechanisms is often infeasible when considering the adoptability and compatibility of these languages since most embedded applications are written in C and C++.This work improves system reliability by providing a completely automatic software technique for guaranteeing segment protection for embedded systems lacking virtual memory. This is done by inserting optimized run-time checks before memory accesses that detect segmentation violations in cases in which there would otherwise be no error, enabling remedial action before system failure or corruption. This feature is invaluable for safety-critical embedded systems. Other advantages of our method include its low overhead, lack of any programming language or semantic restrictions, and ease of implementation. Our compile-time analysis, known as intended segment analysis, is a uniquely structured analysis that allows for the realization of optimizations used to reduce the number of required run-time checks and foster our technique into a truly viable solution for providing segment protection in embedded systems lacking virtual memory.Our experimental results show that these optimizations are effective at reducing the performance overheads associated with providing software segment protection to low, and in many cases, negligible levels. For the eight evaluated embedded benchmarks, the average increase in run-time is 0.72%, the average increase in energy consumption is 0.44%, and the average increase in code size is 3.60%.

REFERENCES

• 1: L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, University of Copenhagen, May 1994.
• 2: Andrew W. Appel , Maia Ginsburg, Modern Compiler Implementation in C, Press Syndicate of the University of Cambridge, 1998
• 3: Todd M. Austin , Scott E. Breach , Gurindar S. Sohi, Efficient detection of all pointer and array access errors, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.290-301, June 20-24, 1994, Orlando, Florida, United States
• 4: Surupa Biswas , Matthew Simpson , Rajeev Barua, Memory overflow protection for embedded systems using run-time checks, reuse and compression, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023872]
• 5: Chandrasekhar Boyapati , Alexandru Salcianu , William Beebee, Jr. , Martin Rinard, Ownership types for safe region-based memory management in real-time Java, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 6: J. Carbone. Efficient memory protection for embedded systems. RTC Magazine, September 2004. http://www.rtcmagazine.com/home/article.php?id=100120.
• 7: John Cocke, Global common subexpression elimination, Proceedings of a symposium on Compiler optimization, p.20-24, July 27-28, 1970, Urbana-Champaign, Illinois
• 8: CodeSourcery, LLC. GNU ARM Toolchain=. http://www.codesourcery.com/.
• 9: Jeremy Condit , Matthew Harren , Scott McPeak , George C. Necula , Westley Weimer, CCured in the real world, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 10: Manuvir Das, Unification-based pointer analysis with directional assignments, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.35-46, June 18-21, 2000, Vancouver, British Columbia, Canada
• 11: Dinakar Dhurjati , Sumant Kowshik , Vikram Adve , Chris Lattner, Memory safety without garbage collection for embedded applications, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.1, p.73-111, February 2005 [doi>10.1145/1053271.1053275]
• 12: M. Durrant. Running Linux on low cost, low power MMU-less processors, August 2000. http://www.linuxdevices.com/articles/AT6245686197.html.
• 13: F. C. Eigler. Mudflap: Pointer use cheking for C/C++. In Proceedings of the GCC Developers Summit 2003, pages 57--70, 2003.
• 14: Björn Franke , Michael O'boyle, Array recovery and high-level transformations for DSP applications, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.2, p.132-162, May 2003 [doi>10.1145/643470.643472]
• 15: David Gay , Alex Aiken, Memory management with explicit regions, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.313-323, June 17-19, 1998, Montreal, Quebec, Canada
• 16: Dan Grossman , Greg Morrisett , Trevor Jim , Michael Hicks , Yanling Wang , James Cheney, Region-based memory management in cyclone, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 17: M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge, and R. B. Brown. Mibench: A free, commercially representative embedded benchmark suite. In Proceedings of the IEEE Workshop on Workload Characterization, 2001.
• 18: R. Hastings and B. Joyce. Purify: Fast detection of memory leaks and access errors. In Proceedings of the USENIX Technical Conference, pages 205--215, 1992.
• 19: John L. Hennessy , David A. Patterson, Computer Architecture: A Quantitative Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 20: Bruce Jacob , Trevor Mudge, Uniprocessor Virtual Memory without TLBs, IEEE Transactions on Computers, v.50 n.5, p.482-499, May 2001 [doi>10.1109/12.926161 ]
• 21: David Seal, ARM Architecture Reference Manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 22: Sumant Kowshik , Dinakar Dhurjati , Vikram Adve, Ensuring code safety without runtime checks for real-time control systems, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France [doi>10.1145/581630.581678]
• 23: Chris Lattner , Vikram Adve, Automatic pool allocation for disjoint data structures, Proceedings of the 2002 workshop on Memory system performance, p.13-24, June 16-16, 2002, Berlin, Germany
• 24: Chris Lattner , Vikram Adve, LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.75, March 20-24, 2004, Palo Alto, California
• 25: P. R. Panda , F. Catthoor , N. D. Dutt , K. Danckaert , E. Brockmeyer , C. Kulkarni , A. Vandercappelle , P. G. Kjeldsberg, Data and memory optimization techniques for embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.2, p.149-206, April 2001 [doi>10.1145/375977.375978]
• 26: J. Seward and N. Nethercote. Using Valgrind to detect undefined value errors with bit-precision. In Proceedings of the USENIX Technical Conference, pages 17--30, 2005.
• 27: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
• 28: Richard Uhlig , David Nagle , Tim Stanley , Trevor Mudge , Stuart Sechrest , Richard Brown, Design tradeoffs for software-managed TLBs, ACM Transactions on Computer Systems (TOCS), v.12 n.3, p.175-205, Aug. 1994 [doi>10.1145/185514.185515]
• 29: Venture Development Corporation. The Embedded Software Strategic Market Intelligence Program 2002/2003 Volume 2, 2003. http://www.vdc-corp.com/embedded/white/03/03esdtvol2.pdf.
• 30: Venture Development Corporation. The Embedded Software Strategic Market Intelligence Program 2004 Volume 1, 2004. http://www.vdc-corp.com/embedded/white/04/04esdtvol1.pdf.
• 31: Robert Wahbe , Steven Lucco , Thomas E. Anderson , Susan L. Graham, Efficient software-based fault isolation, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.203-216, December 05-08, 1993, Asheville, North Carolina, United States
• 32: Emmett Witchel , Josh Cates , Krste Asanović, Mondrian memory protection, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems
  C.4 PERFORMANCE OF SYSTEMS

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
      D.4.5 Reliability

General Terms:
Languages, Reliability

Keywords:
MMU, MPU, compilers, ewmbedded systems, memory safety, reliability, run-time checks, safe languages, segment protection, segmentation violations, virtual memory