Using Meta-level Compilation to Check FLASH Protocol Code

Andy Chou, Benjamin Chelf, Dawson Engler et al. · 2000

Building systems such a s O S k ernels and embedded software is di cult.An important source of this di culty i s the numerous rules they must obey: interrupts cannot be disabled for \too long," global variables must be protected by l o c ks, user pointers passed to OS code must bechecked for safety before use, etc.A single violation can crash the system, yet typically these invariants are unchecked, existing only on paper or in the implementor's mind.This paper is a case study in how system implementors can use a new programming methodology, metalevel compilation (MC), to easily check s u c h i n variants.It focuses on using MC to check for errors in the code used to manage cache coherence on the FLASH shared memory multiprocessor.The only real practical method known for verifying such code is testing and simulation.We s h o w that simple, system-speci c checkers can dramatically improve this situation by statically pinpointing errors in the program source.These checkers can be written by implementors themselves and, by exploiting the system-speci c information this allows, can detect errors unreachable with other methods.The checkers in this paper found 34 bugs in FLASH code despite the care used in building it and the years of testing it has undergone.Many of these errors fall in the worst category of systems bugs: those that show up sporadically only after days of continuous use.The case study is interesting because it shows that the MC approach n d s serious errors in well-tested, non-toy systems code.Further, the code to nd such bugs is usually 10-100 lines long, written in a few hours, and exactly locates errors that, if discovered during testing, would require several days of investigation by an experienced implementor.The paper present s 8 c heckers we wrote, their applic a t i o n t o v e di erent protocol implementations, and a discussion of the errors that we found.

Cited by 1 works. doi:10.21236/ada419588

Authors

References