@inproceedings {173, title = {Non-intrusive Program Tracing and Debugging of Deployed Embedded Systems Through Side-channel Analysis}, booktitle = {Proc. of the 14th ACM SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems (LCTES)}, year = {2013}, note = {

(best paper award)

}, pages = {77-88}, publisher = {ACM}, organization = {ACM}, address = {Washington, USA}, abstract = {

One of the hardest aspects of embedded software development is that of debugging, especially when faulty behavior is observed at the production or deployment stage. Non-intrusive observation of the system\&$\#$39;s behavior is often insufficient to infer the cause of the problem and identify and fix the bug. In this work, we present a novel approach for non-intrusive program tracing aimed at assisting developers in the task of debugging embedded systems at deployment or production stage, where standard debugging tools are usually no longer available. The technique is rooted in cryptography, in particular the area of side-channel attacks. Our proposed technique expands the scope of these cryptographic techniques so that we recover the sequence of operations from power consumption observations (power traces). To this end, we use digital signal processing techniques (in particular, spectral analysis) combined with pattern recognition techniques to determine blocks of source code being executed given the observed power trace. One of the important highlights of our contribution is the fact that the system works on a standard PC, capturing the power traces through the recording input of the sound card. Experimental results are presented and confirm that the approach is viable.

}, keywords = {debugging, embedded systems, side-channel analysis, simple power analysis, tracing}, isbn = {978-1-4503-2085-6}, doi = {10.1145/2465554.2465570}, url = {http://doi.acm.org/10.1145/2465554.2465570}, author = {Moreno, Carlos and Fischmeister, Sebastian and Hasan, M. Anwar} } @article {69, title = {Tracing and Recording Interrupts in Embedded Software}, journal = {Journal of Systems Architecture}, volume = {58}, year = {2012}, month = {Oct}, pages = {372-385}, abstract = {

During the system development, developers often must correct wrong behavior in the software\–-an activity colloquially called program debugging. Debugging is a complex activity, especially in real-time embedded systems because such systems interact with the physical world and make heavy use of interrupts for timing and driving I/O devices. Debugging interrupts is difficult, because they cause non-linear control flow in programs which is hard to reproduce in software. Record/replay mechanisms have proven their use to debugging embedded systems, because they provide means to recreate control flows offline where they can be debugged. In this work, we present the data tracing part of the record/replay mechanism that is specifically targeted to record interrupt behavior. To tune our tracing mechanism, we use the observed principle of return address clustering and a formal model for quantitative reasoning about the tracing mechanism. The presented heuristic and mechanisms show surprisingly good results\–-with higher fingerprint widths an 800 percent speedup on the selector function and a 300 percent reduction on duplicates for non-optimal selector functions\–-considering the leanness of the approach. Using an equal portion for the fingerprint and for the return address lead to the best results in our experiments.

}, keywords = {debugging, embedded systems, record and replay, tracing}, issn = {1383-7621}, doi = {10.1016/j.sysarc.2012.06.003}, url = {http://www.sciencedirect.com/science/article/pii/S1383762112000574}, author = {Giovani Gracioli and Sebastian Fischmeister} } @inproceedings {64, title = {Lowering Overhead in Sampling-based Execution Monitoring and Tracing}, booktitle = {Proc. of the ACM SIGPLAN/SIGBED Conference on Languages, Compilers, Tools and Theory for Embedded Systems (LCTES)}, year = {2011}, pages = {101-110}, address = {Chicago, USA}, abstract = {

Debugging is an important phase in the embedded software development cycle because of its high proportion in the overall cost in the product development. Debugging is difficult for real-time applications as such programs are time-sensitive and must meet deadlines in often a resource constrained environment. A common approach for real-time systems is to monitor the execution instead of stepping through the program, because stepping will usually violate all deadline constraints. We consider a sampling-based approach for monitoring, because of its predictable overhead for the system compared to traditional monitoring. However, the sampling-based approach can easily have high overhead depending on the length of branches and the granularity of the monitoring effort. To reduce this overhead, we instrument the program with markers that will permit us to sample less frequently and thus reduce the overhead. This leads to the interesting problems of (a) where to place the markers in the code and (b) how to manipulate the markers. While related work investigates the first part, in this work, we investigate the second component of the problem. We investigate different instrumentation schemes and propose two new schemes based on bitvectors that significantly reduce the overhead for sampling-based execution monitoring.

}, keywords = {debugging, embedded, monitoring, sampling, tracing}, isbn = {978-1-4503-0555-6}, doi = {10.1145/1967677.1967692}, url = {http://dl.acm.org/citation.cfm?id=1967692}, author = {Johnson Thomas and Fischmeister, Sebastian and Deepak Kumar} } @inproceedings {67, title = {Optimal Instrumentation of Data-flow in Concurrent Data Structures}, booktitle = {Proc. of the 15th International Conference On Principles Of Distributed Systems (OPODIS)}, year = {2011}, month = {December}, pages = {497-512}, address = {Toulouse, France}, abstract = {

In this paper, we propose an automated technique for optimal instrumentation of multi-threaded programs for debugging and testing of concurrent data structures. We define a notion of observability that enables debuggers to trace back and locate errors through data-flow instrumentation. Observability in a concurrent program enables a debugger to extract the value of a set of desired variables through instrumenting another (possibly smaller) set of variables. We formulate an optimization problem that aims at minimizing the size of the latter set. In order to cope with the exponential complexity of the problem, we present a SAT-based solution. Our approach is fully implemented and experimental results on popular concurrent data structures (e.g., linked lists and red-black trees) show significant performance improvement in optimally-instrumented programs using our method as compared to ad-hoc over-instrumented programs.

}, keywords = {debugging, Instrumentation}, doi = {10.1007/978-3-642-25873-2_34}, url = {http://www.springerlink.com/content/dh336633w17613jp/}, author = {Samaneh Navabpour and Borzoo Bonakdarpour and Fischmeister, Sebastian} } @inproceedings {57, title = {Sampling-based Program Execution Monitoring}, booktitle = {Proc. of the ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES)}, year = {2010}, month = {April}, pages = {133-142}, address = {Stockholm, Sweden}, abstract = {

For its high overall cost during product development, program debugging is an important aspect of system development. Debugging is a hard and complex activity, especially in time-sensitive systems which have limited resources and demanding timing constraints. System tracing is a frequently used technique for debugging embedded systems. A specific use of system tracing is to monitor and debug control-flow problems in programs. However, it is difficult to implement because of the potentially high overhead it might introduce to the system and the changes which can occur to the system behaviour due to tracing. To solve the above problems, in this work, we present a sampling-based approach to execution monitoring which specifically helps developers debug time-sensitive systems such as real-time applications. We build the system model and propose three theorems to determine the sampling period in different scenarios. We also design seven heuristics and an instrumentation framework to extend the sampling period which can reduce the monitoring overhead and achieve an optimal tradeoff between accuracy and overhead introduced by instrumentation. Using this monitoring framework, we can use the information extracted through sampling to reconstruct the system state and execution paths to locate the deviation.

}, keywords = {debugging, embedded, monitoring, sampling, tracing}, isbn = {978-1-60558-953-4}, doi = {10.1145/1755888.1755908}, url = {http://dl.acm.org/citation.cfm?id=1755908}, author = {Fischmeister, Sebastian and Ba, Yanmeng} } @article {60, title = {Time-Aware Instrumentation of Embedded Software}, journal = {IEEE Transactions on Industrial Informatics}, volume = {6}, year = {2010}, month = {August}, pages = {652{\textendash}663}, abstract = {

Software instrumentation is a key technique in many stages of the development process. It is particularly important for debugging embedded systems. Instrumented programs produce data traces which enable the developer to locate the origins of misbehaviours in the system under test. However, producing data traces incurs runtime overhead in the form of additional computation resources for capturing and copying the data. The instrumentation may therefore interfere with the system\’s timing and perturb its behavior. In this work, we propose an instrumentation technique for applications with temporal constraints, specifically targetting background/foreground or cyclic executive systems. Our framework permits reasoning about space and time and enables the composition of software instrumentations. In particular, we propose a definition for trace reliability, which enables us to instrument real-time applications which aggressively push their time budgets. Using the framework, we present a method with low perturbation by optimizing the number of insertion points and trace buffer size with respect to code size and time budgets. Finally, we apply the theory to two concrete case studies: we instrument the OpenEC firmware for the keyboard controller of the One Laptop Per Child project, as well as an implementation of a flash filesystem.

}, keywords = {debugging, Instrumentation, real-time, tracing}, issn = {1551-3203}, doi = {10.1109/TII.2010.2068304}, url = {http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5559440}, author = {Fischmeister, Sebastian and Lam, Patrick} } @inproceedings {49, title = {On Time-Aware Instrumentation of Programs}, booktitle = {Proc. of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)}, year = {2009}, month = {April}, pages = {305{\textendash}314}, address = {San Francisco, USA}, abstract = {

Software instrumentation is a key technique in many stages of the development process. It is of particular importance for debugging embedded systems. Instrumented programs produce data traces which enable the developer to locate the origins of misbehaviours in the system under test. However, producing data traces incurs runtime overhead in the form of additional computation resources for capturing and copying the data. The instrumentation may therefore interfere with the system\&$\#$39;s timing and perturb its behavior. In the worst case, this perturbation leads to new system behaviours that prevent the developer from locating the original misbehaviours. In this work, we propose an instrumentation technique for applications with temporal constraints, specifically targetting background/foreground systems. Our framework permits reasoning about space and time for software instrumentations. In particular, we propose a definition for trace reliability, which enables us to instrument real-time applications which aggressively push their time budgets. Using the framework, we present a method with low perturbation by optimizing the number of insertion points and trace buffer size for code size and time budgets. Finally, we apply the theory to a concrete case study and instrument the OpenEC firmware for the keyboard controller of the One Laptop Per Child project. This publication has been superseeded by an article in the IEEE Transactions on Industrial Informatics to be published soon.

}, keywords = {debugging, real-time, tracing}, isbn = {9780769536361}, doi = {10.1109/RTAS.2009.26}, url = {http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=04840591}, author = {Fischmeister, Sebastian and Lam, Patrick} } @inproceedings {54, title = {Tracing Interrupts in Embedded Software}, booktitle = {Proc. of the ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES)}, year = {2009}, note = {

(best in research forum award)

}, month = {June}, pages = {137{\textendash}146}, address = {Dublin, Ireland}, abstract = {

During the system development, developers often must correct wrong behavior in the software\–-an activity colloquially called program debugging. Debugging is a complex activity, especially in real-time embedded systems because such systems interact with the physical world and make heavy use of interrupts for timing and driving I/O devices. Debugging interrupts is difficult, because they cause non-linear control flow in programs which is hard to reproduce in software. Record/replay mechanisms have proven their use to debugging embedded systems, because they provide means to recreate control flows offline where they can be debugged. In this work, we present the data tracing part of the record/replay mechanism that is specifically targeted to record interrupt behavior. To tune our tracing mechanism, we use the observed principle of return address clustering and a formal model for quantitative reasoning about the tracing mechanism. The presented heuristic and mechanisms show surprisingly good results\–-up to an 800 percent speedup on the selector function and a 300 percent reduction on duplicates for non-optimal selector functions\–-considering the leanness of the approach.

}, keywords = {debugging, real-time, tracing}, isbn = {978-1-60558-356-3}, doi = {10.1145/1542452.1542471}, url = {http://dl.acm.org/citation.cfm?doid=1542452.1542471}, author = {Giovani Gracioli and Fischmeister, Sebastian} }