Safe TinyOS

What is Safe TinyOS?

Safe TinyOS is a modified compilation toolchain, released as part of TinyOS 2.1, that uses the Deputy compiler (now part of the Ivy project) to enforce type and memory safety at run time on motes. Together, type and memory safety give Java-like guarantees to TinyOS programs: pointer and array errors are trapped before they occur.

Untrapped memory errors are particularly harmful in sensor network applications because

• Lacking memory protection hardware and a user/kernel boundary, it is easy to accidentally corrupt OS code; these errors are never trapped as segmentation violations.
• Since memory objects are tightly packed, walking even one element past the end of an array is likely to corrupt RAM that your application relies on.
• Since deployed motes are difficult to debug, and since other failure modes exist (concurrency errors, battery outage, connectivity failure, etc.) it can be very hard to tell when memory corruption is the root cause of a serious deployment problem.

Safe TinyOS is described in detail in a paper from SenSys 2007: Efficient Memory Safety for TinyOS.

Supported Platforms

Safe compilation is supported by default by TinyOS 2.1 for these platforms:

• Mica2
• MicaZ
• TelosB

TODO: Support intelmote2, shimmer, and iris (patches welcome)

TODO: Commit the Utah patch for safe TOSSIM

Building a Safe Application

Getting started is easy. To compile a safe application go to for example $TOSROOT/apps/Blink and run:

  make micaz safe

Since Blink contains no known safety errors, the safe version of Blink should act just like its unsafe counterpart.

As a sanity check, you may want to make sure that the code size of the safe version of Blink is larger than that of the unsafe version:

$ make micaz
mkdir -p build/micaz
    compiling BlinkAppC to a micaz binary
ncc -o build/micaz/main.exe ....
    compiled BlinkAppC to build/micaz/main.exe
            2052 bytes in ROM
              51 bytes in RAM
avr-objcopy --output-target=srec build/micaz/main.exe build/micaz/main.srec
avr-objcopy --output-target=ihex build/micaz/main.exe build/micaz/main.ihex
    writing TOS image

$ make micaz safe
mkdir -p build/micaz
    compiling BlinkAppC to a micaz binary
ncc -o build/micaz/main.exe ...
    compiled BlinkAppC to build/micaz/main.exe
            2562 bytes in ROM
              51 bytes in RAM
avr-objcopy --output-target=srec build/micaz/main.exe build/micaz/main.srec
avr-objcopy --output-target=ihex build/micaz/main.exe build/micaz/main.ihex
    writing TOS image

The ROM overhead is due to bounds-checking code inserted by the Deputy compiler. As illustrated here, Safe TinyOS does not have any RAM overhead.

TODO: Although both the Deputy compiler and gcc attempt to remove unneeded safety checks, there is still room for improvement. We'd like advanced compiler techniques (e.g. calling out to a modern decision procedure) for showing that safety checks definitely do or do not fire.

Interpreting Safety Violations

TinyOS 2.1 comes with an application that is designed to fail; it is here:

$TOSROOT/apps/tutorials/BlinkFail

Looking at BlinkFailC.nc, it is easy to see that the 11th time the Timer1.fired() is signaled, it will access out of bounds storage.

First, run the unsafe version of this application:

make micaz install

In general, it is hard to predict the consequences of a memory safety violation in a TinyOS program. In many cases, the observable symptom is node crash. That is what should happen after running the unsafe BlinkFail for a few seconds.

Next run the safe version:

make micaz safe install

Prior to accessing a[10], the Safe TinyOS failure handler is invoked, resulting in lots of LED activity. The purpose of this activity is to give you a "FLID" (fault location identifier) indicating the source-code location of the faulting access.

A FLID is a sequence of 8 base-4 digits. To read a FLID, wait for the mote's LEDs to "roll," or rapidly blink several times in a 1-2-3 sequence. Next, some number of LEDs will be lit: write down this number. Usually the first digit or two of a FLID will be zero. Following each digit of the FLID, all three LEDs will be very briefly illuminated to serve as a separator. After all 8 digits have been presented, the LEDs will again roll and then the FLID is repeated. Once you have the sequence of 8 digits, it can be decoded as follows:

tos-decode-flid flid-file flid

The flid-file argument specifies a file that helps the script map from the flid to an error message. Building a safe application causes this file to be placed here:

build/[platform]/flids.txt

Running the FLID decoding tool on the BlinkFail error gives:

[regehr@babel BlinkFail]$ tos-decode-flid ./build/micaz/flids.txt 00001020
Deputy error message for flid 0x0048:

BlinkFailC__a <= BlinkFailC__a + BlinkFailC__i++ + 1 (with no overflow): BlinkFailC.nc:70: Assertion failed in CPtrArithAccess:
  BlinkFailC__a + BlinkFailC__i++ + 1 <= BlinkFailC__a + 10 (with no overflow)
[regehr@babel BlinkFail]$ 

This confirms what we can easily see by inspecting BlinkFailC.nc: there is a potential safety error at line 70.

Safety Violations in a Simulator

A simulator offers a pleasant alternative to debugging safety violations on real hardware. To try this out, first download and install the CVS version of Avrora.

Next: build a safe version of BlinkFail, make a copy with the .elf extension, and run it in Avrora:

make micaz safe
cp build/micaz/main.exe main.elf
java avrora.Main -simulation=sensor-network -platform=micaz -monitors=leds,break,sleep,interrupts main.elf

The Avrora output should contain text like this:

   0      54435382  break instruction @ 0x0B9E, r30:r31 = 0x0048
   0      54435382        @ deputy_fail_noreturn_fast
   0      54435382        @ deputy_fail_mayreturn
   0      54435382        @ VirtualizeTimerC$0$fireTimers
   0      54435382        @ AlarmToTimerC$0$fired$runTask

The callstack leading up to the safety violation is shown. The value loaded into the register pair r30:r31 (the AVR's Z register) is the FLID.

TODO: We'd like an Avrora monitor that goes ahead and automatically decodes the FLID.

TODO: We'd like analogous instructions for mspsim.

Understanding Safe Code

Safe code contains annotations that express invariants in such a way that the Deputy compiler can perform appropriate static and dynamic checking. Most annotations appear in function prototypes and on global variables, but sometimes annotations are needed inside functions.

Annotations that you will find in TinyOS code are:

ONE 

A pointer that always refers to a single object, similar to a C++ reference.

ONE_NOK 

Same as ONE but may be NULL.

COUNT(n) 

A pointer that always refers to a block of at least n objects.

COUNT_NOK(n) 

Same as COUNT but may be NULL.

BND(n,m) 

A pointer p such that n≤p<m, and that is aligned with respect to n and m.

BND_NOK(n,m) 

Same as BND but may be NULL.

TCAST(type,expr) 

A trusted cast, which tells Deputy to just trust the programmer. This is needed to perform casts that are inherently unsafe (e.g., casting an array of bytes into a message_t) or to perform casts that are safe but beyond the reach of Deputy's type system (e.g. some kinds of getHeader() and getFooter() calls).

TRUSTEDBLOCK 

Code that is completely trusted (i.e., ignored by Deputy). This is used in very few places, and should be avoided when possible.

The quick reference and user manual for Deputy are the best starting points for learning to use its type system, but note that the Safe TinyOS annotations are slightly different from the original Deputy ones.

Understanding Annotations in tos/interfaces/*.nc

The TinyOS Core Working Group decided that it was important to avoid hurting the readability of the primary TinyOS interfaces by cluttering them up with safety annotations. Therefore, the Safe TinyOS annotations in the interfaces use a different syntax than the one generally used for code in modules. To see how this works, consider this example from $TOSDIR/interfaces/Packet.nc:

/**
  * Return a pointer to a protocol's payload region in a packet.
  * If the caller intends to write to the payload region then
  * the <tt>len</tt> parameter must reflect the maximum required
  * length. If the caller (only) wants to read from the payload
  * region, then <tt>len</tt> may be set to the value of
  * payloadLength(). If the payload region is smaller than 
  * <tt>len</tt> this command returns NULL. The offset where
  * the payload region starts within a packet is fixed, i.e. for
  * a given <tt>msg</tt> this command will always return the same
  * pointer or NULL.
  *
  * @param 'message_t* ONE msg'   the packet 
  * @param len   the length of payload required
  * @return 'void* COUNT_NOK(len)'     a pointer to the packet's data payload for this layer
  *              or NULL if <tt>len</tt> is too big
  */
 command void* getPayload(message_t* msg, uint8_t len);

Instead of inlining the Safe TinyOS annotations into the getPayload() prototype, the annotations are placed in the nesdoc comment. The syntax above is equivalent to

command void* COUNT_NOK(len) getPayload(message_t* ONE msg, uint8_t len);

It would be prudent to avoid mixing the two kinds of annotation syntax within a single function.

The current convention (which is not automatically enforced) is to use the nesdoc annotation syntax in tos/interfaces and the inline syntax elsewhere.

Writing Safe Code

Writing safe code is generally very easy: in the common case annotations are only needed on pointers that reference multiple objects. The best way to get started is to compile regular nesC or C code in safe mode, see what warnings/errors are emitted by the Deputy compiler, and then start annotating the code until it compiles cleanly. In a small minority of cases, it is necessary to do some refactoring.

The non-null versions of the annotations should be used whenever possible, for two reasons. First, the are good documentation. Second, they generally result in more efficient code since dereferences of these pointers need not be preceded by a NULL check.

The quick reference and user manual for Deputy are the best starting points for learning to use its type system, but note that the Safe TinyOS annotations are slightly different from the original Deputy ones.

Mixing Safe and Unsafe Code

By default, a TinyOS module is compiled as unsafe code. In other words, it is trusted code and Deputy will not insert any checks into it. The TinyOS Core Working Group decided on unsafe as the default compilation mode in order to make it easier to transition applications to Safe TinyOS. This default can be overridden using the nesC compiler command line option -fnesc-default-safe.

A module with the @safe() attribute is compiled in safe mode: Deputy checks are inserted. For example in tos/system/SimpleArbiterP.nc starts with:

generic module SimpleArbiterP() @safe() {

A module with the @unsafe() attribute is explicitly exempt from Deputy's checking.

In general, the following conventions should be respected:

• Use @safe() for any module that has been "Deputized," meaning that it contains sufficient annotations to compile and execute properly in safe mode
• Use @unsafe() for any module that fundamentally cannot be compiled in safe mode (at the time this is written, no such modules exist)
• Leave out annotations for modules that have not yet been Deputized

An application that contains no unsafe modules is globally safe: any safety error that can be caught by Deputy, will be caught. The easiest way to check if an application that you are using or writing is globally safe is to inspect its app.c for DEPUTY_TRUSTEDBLOCK annotations, which are inserted by the nesC compiler to tell Deputy to avoid compiling functions from unsafe modules as safe code. For example:

[regehr@babel Blink]$ cd $TOSROOT/apps/Blink
[regehr@babel Blink]$ make micaz safe
mkdir -p build/micaz
    compiling BlinkAppC to a micaz binary
ncc -o build/micaz/main.exe -DSAFE_TINYOS ...
    compiled BlinkAppC to build/micaz/main.exe
            2562 bytes in ROM
              51 bytes in RAM
avr-objcopy --output-target=srec build/micaz/main.exe build/micaz/main.srec
avr-objcopy --output-target=ihex build/micaz/main.exe build/micaz/main.ihex
    writing TOS image
[regehr@babel Blink]$ grep -c DEPUTY_TRUSTEDBLOCK build/micaz/app.c 
14

This shows that the app.c for Blink on MicaZ contains 14 DEPUTY_TRUSTEDBLOCK annotations. However, a detailed inspection shows that almost all of this trusted code is in the failure handlers themselves. It makes no sense to compile these as safe code.

TODO: We'd like a nesC compiler option that prints a list of unsafe modules.

Customizing the Failure Handler

The default safety violation handler is very simple and can be found in $TOSDIR/lib/safe/SafeFailureHandlerP.nc. This code could be changed to notify a base station that a safety violation occurred, log a FLID to flash, reboot the mote, or whatever you like. Ideally, failure handling code should be atomic, should be independent of the state of the hardware at the time a violation happens, and should not call into any safe code. Thus, it is highly unlikely that you could successfully send a packet reporting a fault that occurred in the TinyOS network stack without having written a small, customized network driver whose specific purpose is to report safety errors in the main TinyOS network stack.

To Do

We have not yet, but plan to:

• Integrate Safe TinyOS with a stack depth analysis tool to avoid unsafety through stack overflow
• Solve the problem of unsafe accesses to pointers to dead stack frames -- these are not covered by Deputy
• Eliminate as much trusted code (TCAST and TRUSTEDBLOCK) as possible
• Use compiler techniques to reduce the code bloat from safety

Let us know if you'd like to help!

Feedback

Please send problem reports and other feedback to tinyos-help or tinyos-devel, as appropriate.