Premium
A hybrid approach to testing for nonfunctional faults in embedded systems using genetic algorithms
Author(s) -
Yu Tingting,
Srisaan Witawas,
Cohen Myra B.,
Rothermel Gregg
Publication year - 2018
Publication title -
software testing, verification and reliability
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.216
H-Index - 49
eISSN - 1099-1689
pISSN - 0960-0833
DOI - 10.1002/stvr.1686
Subject(s) - interrupt , computer science , interrupt handler , stack (abstract data type) , distributed computing , resource (disambiguation) , call stack , static analysis , embedded system , operating system , real time computing , programming language , computer network , microcontroller
Summary Embedded systems are challenging to program correctly, because they use an interrupt‐driven programming paradigm and run in resource‐constrained environments. This leads to various classes of nonfunctional faults that can be detected only by customized verification techniques. These nonfunctional faults are specifically related to usage of resources such as time and memory. For example, the presence of interrupts can induce delays in interrupt servicing and in system execution time. Such delays can occur when multiple interrupt service routines and interrupts of different priorities compete for resources on a given CPU. As another example, stack overflows are caused when the combination of active methods and interrupt invocations on the stack grows too large, and these can lead to data loss and other significant device failures. To detect these types of nonfunctional faults, developers need to estimate worst‐case resource usage. Most existing approaches for calculating such estimates are based on static analysis; however, these have a tendency to overapproximate the resources needed. Dynamic techniques such as random testing, in contrast, often underapproximate resource usage. In this article, we present SimEspresso , a framework that uses a combination of static analysis and a test case generation algorithm to estimate worst‐case resource usage. There are three different worst‐case resource usage scenarios that we consider: (1) worst‐case execution times, (2) worst‐case interrupt latencies, and (3) worst‐case stack usage. SimEspresso first uses static analysis to identify program paths and interrupt interleavings that potentially lead to worst‐case scenarios. It then uses a genetic algorithm to generate test cases that guide program execution down these paths, using these particular interrupt interleavings. We performed an empirical study to evaluate the effectiveness of SimEspresso ; our results show that SimEspresso is more effective than static analysis approaches and improves significantly over the state of the art dynamic technique, random test case generation. We also find that when we use only the genetic algorithm, omitting the static analysis, SimEspresso performs almost as effectively, but takes significantly longer to complete its task.