Understanding and testing intermittence bugs in transiently-powered computers

Using the energy harvested from the environment for powering small-scale devices reduces maintenance cost, and enables applications and services considered to be impractical due to battery limitations. Devices powered only with such energy source compute intermittently, as energy is available. Their execution is characterized by intervals of active computation, interleaved by periods in which the device is powered off and recharges its energy buffer. Despite different techniques enable forward progress of programs, an intermittent execution inevitably causes the re-execution of some portion of code. Such re-executions may cause unwanted behaviors, such as the computation of incorrect results or unexpected environment interactions. The current literature recognizes such unwanted behaviors as generic intermittence bugs, and does not provide an in-depth analysis of them. Moreover, no available technique enables testing the effects of all the possible combinations of intermittent executions in practical time. This operation has a complexity which grows exponentially with respect to all the possible interruption points, and can result in years of processing time for analyzing even a simple program. In this thesis we provide an exhaustive analysis of intermittence bugs, including an analysis of their causes, guidelines on how to avoid such unwanted behaviors, and a set of techniques that enable their analysis in practical time. We also analyze the possibility of exploiting intermittence bugs for making programs aware of intermittence, and we provide both a technique and a set of guidelines that permit testing the correctness of this new kind of input. Our contribution includes ScEpTIC, an offline tool that implements all the testing techniques that we provide in this thesis. ScEpTIC helps the programmer analyze and test the effects of intermittent executions in practical time. Not only it provides a speedup of six orders of magnitude with respect to brute-force approaches, but it also returns a more complete result that correctly identifies the exact position of intermittence bugs.

Alimentare i dispositivi di dimensioni ridotte usando solo l'energia fornita dall'ambiente riduce i costi di manutenzione e permette la creazione di applicazioni e servizi considerati poco pratici a causa delle limitazioni delle batterie. I dispositivi alimentati con tale sorgente di energia computano solo quando l'energia è disponibile, e sono caratterizzati da un'esecuzione intermittente, che separa intervalli di computazione attiva ad intervalli in cui il dispositivo è spento. Nonostante differenti tecniche permottono di riprendere l'esecuzione da dove è stata interrotta, la ri-esecuzione di alcuni porzioni di codice è inevitabile. Queste ri-esecuzioni possono causare comportamenti inaspettati, come ad esempio il calcolo di risultati non corretti o interazioni non previste con l'ambiente circostante. La letteratura riconosce questi comportamenti inaspettati come dei generici bug da intermittenza, e non fornisce una loro analisi approfondita. Inoltre, nessuna tecnica al momento disponibile permette di analizzare in tempo ragionevole gli effetti di tutte le possibili combinazioni di esecuzioni intermittenti. Questa operazione ha una complessità che cresce esponenzialmente rispetto a tutti i possibili punti in cui la mancanza di energia può causare uno spegnimento del dispositivo, e si potrebbe impiegare anni di computazione per analizzare anche solo dei piccoli programmi. In questa tesi forniamo un'analisi esaustiva dei bug da intermittenza, che include l'analisi delle loro cause, linee guida per evitare tali bug, ed un insieme di tecniche che permottono la loro analisi in tempi pratici. Analizziamo inoltre l'utilizzo di alcuni bug da intermittenza per rendere il programma consapevole dell'intermittenza stessa, e forniamo sia delle tecniche che permottono di verificare la correttezza di questo nuovo tipo di input, che delle line guida per il suo utilizzo. Il nostro contributo comprende anche ScEpTIC, un tool di nostra creazione che implementa le tecniche di analisi fornite in questa tesi. ScEpTIC aiuta il programmatore ad analizzare e verificare gli effetti che tutte le possibili esecuzioni intermittenti hanno sul programma. Nei nostri test di laboratorio, ScEpTIC ha dimostrato una performance di sei ordini di grandezza superiore rispetto a comuni tecniche di brute-force per analizzare tutti i possibili punti di interruzione, e produce un risultato più completo ed accurato rispetto a tali tecniche.