We propose a method for generating interpretable descriptions of inputs that cause faults in high-dimensional software interfaces. Our method models the set of fault-triggering inputs as a Cartesian product and identifies this set by actively querying the system under test. The active sampling scheme is very efficient in the common case that few fields in the interface are relevant to causing the fault. This scheme also solves the problem of efficiently finding sufficient examples to model rare faults, which is problematic for other learning-based methods. Compared to other techniques, ours requires no parameter turning or post-processing in order to produce useful results. We analyze the method qualitatively, theoretically, and empirically. An experimental evaluation demonstrates superior performance and reliability compared to a basic decision tree approach. We also briefly discuss how the method has assisted in debugging a commercial autonomous ground vehicle system.

Testing Cyber-Physical Systems is becoming increasingly challenging as they incorporate advanced autonomy features. We investigate using an external runtime monitor as a partial test oracle to detect violations of critical system behavioral requirements on an automotive development platform. Despite limited source code access and using only existing network messages, we were able to monitor a hardware-in-the-loop vehicle simulator and analyze prototype vehicle log data to detect violations of high-level critical properties. Interface robustness testing was useful to further exercise the monitors. Beyond demonstrating feasibility, the experience emphasized a number of remaining research challenges, including: approximating system intent based on limited system state observability, how to best balance the simplicity and expressiveness of the specification language used to define monitored properties, how to warm up monitoring of system variable state after mode change discontinuities, and managing the differences between simulation and real vehicles when conducting such tests.

Electronics systems for modern vehicles must be designed to meet stringent requirements on real-time performance, safety, power consumption, and security. Hardware/software codesign techniques allow system designers to create platforms that can both meet those requirements and evolve as components and system requirements evolve. Design methodologies have evolved that allow systems-of-systems to be built from subsystems that are themselves embedded computing systems. Software performance is a key metric in the design of these systems. A number of methods-of-methods for the analysis of worst case execution time have been developed. More recently, we have developed new methods for software performance analysis based on design of experiments. Formal methods can be used to verify system properties. Systems must be architected to maintain their integrity in the face of attacks from the Internet. All of these techniques build upon generic hardware/software codesign techniques but with significant adaptations to the technical and economic context of vehicle design.

Decomposition is used to manage system complexity, but is problematic for emergent properties such as system safety. Previously, we introduced Indirect Control Path Analysis (ICPA) for elaborating system safety goals in composite systems. We now provide mathematical definitions of emergent and composable system behaviors in the context of formal specifications and ICPA, and identify useful special cases in which partial decomposition of emergent safety goals is possible. We apply ICPA to a semi-autonomous automotive system to identify safety goals for key subsystems, and then monitor the system and subsystem goals at run-time in an implementation of the vehicle. Although false negatives at the subsystem level indicate the subgoals do not fully compose the original safety goal, some system-level goal violations are detected by subsystem monitors. In addition, monitoring at both the system and subsystem level has identified certain safety-related errors that may be imperceptible to system testers.

It is becoming increasingly common to connect traditional embedded system networks to the Internet for remote monitoring, high-level control and integration. It is necessary to protect each part of the interconnected system from faults and attacks which propagate from the other side. One architectural approach is to add a gateway to the embedded system to receive Internet traffic and disperse data to the embedded system, but there is no clear recipe for building such gateways. Since Internet routers commonly use queues to manage traffic, we examine the effectiveness of queues for the embedded system gateway domain. We perform a series of experiments to evaluate the effectiveness of the queue mechanism and various queue management techniques. We show that queues can exhibit poor performance in the context of real-time embedded system gateways due to problems with message latency and dropped messages. We then introduce the concept of a filter mechanism and show that a simple filter mechanism can outper-form queue mechanisms when used in the gateway to manage real-time state-oriented data streams.

Security for wired embedded networks is becoming a greater concern as connectivity to the outside world increases. Protocols used in these networks omit support for authenticating messages to prevent masquerade and replay attacks. The unique constraints of embedded control systems make incorporating existing multicast authentication schemes impractical. Our approach provides multicast authentication for time-triggered applications by validating truncated message authentication codes (MACs) across multiple packets. We extend this approach to tolerate occasional invalid MACs, analyze our approach through simulated attacks, and give an upper bound on the probability of successful attack. This approach allows a tradeoff among per-packet authentication cost, application level latency, tolerance to invalid MACs, and probability of induced failure, while satisfying typical embedded system constraints.

Embedded control networks commonly use checksums to detect data transmission errors. However, design decisions about which checksum to use are difficult because of a lack of information about the relative effectiveness of available options. We study the error detection effectiveness of the following commonly used checksum computations: exclusive or (XOR), two's complement addition, one's complement addition, Fletcher checksum, Adler checksum, and cyclic redundancy codes (CRCs). A study of error detection capabilities for random independent bit errors and burst errors reveals that XOR, two's complement addition, and Adler checksums are suboptimal for typical network use. Instead, one's complement addition should be used for networks willing to sacrifice error detection effectiveness to reduce compute cost, Fletcher checksum for networks looking for a balance of error detection and compute cost, and CRCs for networks willing to pay a higher compute cost for significantly improved error detection.

Presents the introductory welcome message from the conference proceedings.

Correctly specifying requirements for composite systems is essential to system safety, particularly in a distributed development environment. Goal-oriented requirements engineering can be used to formally specify system goals and decompose them into realizable subgoals for system components. However, an additional aim of safety goal elaboration is to meet a goal coverage strategy. In this paper we propose new tactics for elaborating system safety goals across a composite system. First, indirect control path analysis (ICPA) is used to identify safety-related components and their relationships to the parent goals. Then, goal coverage strategies guide goal elaboration along indirect control paths identified by the ICPA. We demonstrate applicability in real safety critical embedded systems with two case studies: a distributed elevator and a semiautonomous automotive system.

Cyclic redundancy codes (CRCs) are widely used in network transmission and data storage applications because they provide better error detection than lighter weight checksum techniques. 24- and 32-bit CRC computations are becoming necessary to provide sufficient error detection capability (Hamming distance) for critical embedded network applications. However, the computational cost of such CRCs can be too high for resource-constrained embedded systems, which are predominantly equipped with 8- bit microcontrollers that have limited computing power and small memory size. We evaluate the options for speeding up CRC computations on 8-bit processors, including comparing variants of table lookup approaches for memory cost and speed. We also evaluate classes of CRC generator polynomials which have the same computational cost as 24- or 16-bit CRCs, but provide 32-bit CRC levels of error detection, and recommend good polynomials within those classes for data word lengths typical of embedded networking applications.

Designing a distributed fault tolerance algorithm requires careful analysis of both fault models and diagnosis strategies. A system will fail if there are too many active faults, especially active Byzantine faults. But, a system will also fail if overly aggressive convictions leave inadequate redundancy. For high reliability, an algorithm's hybrid fault model and diagnosis strategy must be tuned to the types and rates of faults expected in the real world. We examine this balancing problem for two common types of distributed algorithms: clock synchronization and group membership. We show the importance of choosing a hybrid fault model appropriate for the physical faults expected by considering two clock synchronization algorithms. Three group membership service diagnosis strategies are used to demonstrate the benefit of discriminating between permanent and transient faults. In most cases, the probability of failure is dominated by one fault type. By identifying the dominant cause of failure, one can tailor an algorithm appropriately at design time, yielding significant reliability gain.

A cyclic redundancy code (CRC), when used properly, can be an effective and relatively inexpensive method to detect data corruption across communication channels. However, some systems use CRCs in ways that violate common assumptions made in analyzing CRC effectiveness, resulting in an overly optimistic prediction of system dependability. CRCs detect errors with some finite probability, which depends on factors including the strength of the particular code used, the bit-error rate, and the message length being checked. Common assumptions also include a passive network inter-stage, explicit data words, memoryless channels, and random independent symbol errors. In this paper we identify some examples of CRC usage that compromise ultra-dependable system design goals, and recommend alternate ways to improve system dependability via architectural approaches rather than error detection coding approaches.

Embedded systems encompass a wide range of applications, technologies, and disciplines, necessitating a broad approach to education. We describe embedded system coursework during the first 4 years of university education (the U.S. undergraduate level). Embedded application curriculum areas include: small and single-microcontroller applications, control systems, distributed embedded control, system-on-chip, networking, embedded PCs, critical systems, robotics, computer peripherals, wireless data systems, signal processing, and command and control. Additional cross-cutting skills that are important to embedded system designers include: security, dependability, energy-aware computing, software/systems engineering, real-time computing, and human--computer interaction. We describe lessons learned from teaching courses in many of these areas, as well as general skills taught and approaches used, including a heavy emphasis on course projects to teach system skills.

Cyclic redundancy codes (CRCs) provide a first line of defense against data corruption in many networks. Unfortunately, many commonly used CRC polynomials provide significantly less error detection capability than they might. An exhaustive exploration reveals that most previously published CRC polynomials are either inferior to alternatives or are only good choices for particular message lengths. Unfortunately these shortcomings and limitations often seem to be overlooked. This paper describes a polynomial selection process for embedded network applications and proposes a set of good general-purpose polynomials. A set of 35 new polynomials in addition to 13 previously published polynomials provides good performance for 3- to 16-bit CRCs for data word lengths up to 2048 bits.

For safety-critical systems, it is essential to quantify the reliability of the assumptions that underlie proven guarantees. We investigate the reliability of the assumptions of the SPIDER group membership service with respect to transient and permanent faults. Modeling 12,600 possible system configurations, the probability that SPIDER's maximum fault assumption does not hold for an hour mission varies from less likely than l0/sup -11/ to more likely than 10/sup -3/. In most cases examined, a transient fault tolerance strategy was superior to the permanent fault tolerance strategy previously in use for the range of transient fault arrival rates expected in aerospace systems. Reliability of the maximum fault assumption (upon which the proofs are based) differs greatly when subjected to asymmetric, symmetric, and benign faults. This case study demonstrates the benefits of quantifying the reliability of assumptions for proven properties.

Some safety-critical distributed embedded systems may need to use centralized components to achieve certain dependability properties. The difficulty in combining centralized and distributed architectures is achieving the potential benefits of centralization without giving up properties that motivated the use of a distributed approach in the first place. This paper examines the impact on fault tolerance of adding selected centralized components to distributed embedded systems, and possible approaches to choosing an appropriate configuration. We consider the proposed use of a star topology with centralized bus guardians in the time-triggered architecture. We model systems with different levels of centralized control in their star couplers, and compare fault tolerance properties in the presence of star-coupler faults. We demonstrate that buffering entire frames in the star coupler could lead to failures in startup and integration. We also show that constraining buffer size imposes restrictions on frame size and clock rates.

We present the concept of alternative functionality for improving dependability in distributed embedded systems. Alternative functionality is a mechanism that complements traditional performability and graceful degradation techniques. Rather than providing reduced performance or functionality when components or subsystems fail, alternative functionality replaces a lost feature with another existing system junction that can substitute for the lost service. This can provide improved system dependability when it is not feasible to allocate dedicated backup systems for fault tolerance. We show how alternative functionality can be applied to enhance system dependability with a case study of an elevator control system. In simulation, an elevator design that implemented alternative functionality in some of its subsystems tolerated many combinations of component failures that caused system failures in the original design.

Evaluation of system-level dependability can benefit from representing and assessing the effects of user workarounds as a response to system component failures. We assemble sequence diagrams that represent UML scenarios into mission graphs that contain all possible paths from a particular mission starting point to a particular mission success goal point. Analysis of these graphs reveals potential dependability bottlenecks and the existence of possible workarounds that can be intentionally added to a design, retrofitted to fit an existing design, or discovered as an emergent property of existing system and user behaviors. Simulations of a moderately complex distributed embedded system demonstrate that this approach has potential benefits for representing and improving system-level dependability by including the ability of users to perform simple workarounds to achieve mission objectives.

Software developers identify two main reasons why software systems are not made robust: performance and practicality. We demonstrate the effectiveness of general techniques to improve robustness that are practical and yield high performance. We present data from treating three systems to improve robustness by a factor of 5 or more, with a measured performance penalty of under 5% in nearly every case, and usually under 2%. We identify a third possible reason why software systems are not made robust: developer awareness. A case study on three professional development groups evaluated their ability to estimate the robustness of their software. Two groups were able to estimate their software's robustness to some extent, while one group had more divergent results. Although we can overcome the technical challenges, it appears that even experienced developers can benefit from tools to locate robustness failures and training in robustness issues.

Standardized 32-bit cyclic redundancy codes provide fewer bits of guaranteed error detection than they could, achieving a Hamming Distance (HD) of only 4 for maximum-length Ethernet messages, whereas HD=6 is possible. Although research has revealed improved codes, exploring the entire design space has previously been computationally intractable, even for special-purpose hardware. Moreover, no CRC polynomial has yet been found that satisfies an emerging need to attain both HD=6 for 12K bit messages and HD=4 for message lengths beyond 64 Kbits. This paper presents results from the first exhaustive search of the 32-bit CRC design space. Results from previous research are validated and extended to include identifying all polynomials achieving a better HD than the IEEE 802.3 CRC-32 polynomial. A new class of polynomials is identified that provides HD=6 up to nearly 16K bit and HD=4 up to 114K bit message lengths, providing the best achievable design point that maximizes error detection for both legacy and new applications, including potentially iSCSI and application-implemented error checks.

Much of the software we use for everyday purposes incorporates elements developed and maintained by someone other than the developer. These elements include not only code and databases but also dynamic data feeds from online data sources. Although everyday software is not mission critical, it must be dependable enough for practical use. This is limited by the dependability of the incorporated elements.It is particularly difficult to evaluate the dependability of dynamic data feeds, because they may be changed by their proprietors as they are used. Further, the specifications of these data feeds are often even sketchier than the specifications of software components.We demonstrate a method of inferring invariants about the normal behavior of dynamic data feeds. We use these invariants as proxies for specifications to perform on-going detection of anomalies in the data feed. We show the feasibility of our approach and demonstrate its usefulness for semantic anomaly detection: identifying occasions when a dynamic data feed is delivering unreasonable values, even though its behavior may be superficially acceptable (i.e., it is delivering parsable results in a timely fashion).

Lack of data quantifying the performance cost of implementing good exception handling often causes developers to skimp on exception handling based on its overestimated perceived cost. In an effort to remedy this problem we provide performance data on the cost of building good exception handling into software. We use the Safe Fast IO library as a basis for this study. SFIO improves robustness by a factor of 3 to 10 over STDIO without sacrificing performance. We were able to improve the robustness of the critical SFIO functions by another factor of 5, thus quantifying and reducing robustness failure rates by a factor of up to 70 from standard I/O functions, with an average performance penalty of 1% as measured by the original SFIO benchmark scheme. Future processor architecture improvements will further improve checking speed, essentially eliminating performance as an obstacle to improving software robustness.

Before using CORBA (Common Object Request Broker Architecture) applications in mission-critical scenarios, it is important to understand the robustness of the Object Request Broker (ORB) being used, which forms the platform for CORBA applications. We have extended the Ballista software testing technique to test the exception-handling robustness of C++ ORB client-side application interfaces, and have tested two major versions of three ORB implementations on two operating systems, yielding robustness failure rates ranging from 26% to 42%. To improve ORB robustness, we also propose a probing method to harden object and pseudo-object related data types against exceptional inputs. Using these probes on omniORB 2.8 has proven to be effective in eliminating some cases of robustness failures found during testing. These results suggest that CORBA implementations currently have significant robustness vulnerabilities, but that some important classes of problems can be overcome with better exception-handling approaches.

The design and design automation of embedded systems is rapidly emerging as a research area in its own right. It draws from several traditional areas of study such as system specification, modeling and analysis; computer architecture and micro-architecture; as well as compilers and operating systems. However, the embedded domain adds some interesting twists in terms of tighter problem constraints that demand a fresh look at even these traditional areas. In addition, there are several emerging EDA areas such as design reuse and integration of systems on a chip that are critical to the study of embedded systems. These aspects are not typically covered by computer engineering and EDA curricula. This panel addresses the challenges associated with the educational issues in embedded systems design and design automation. The panelists will examine issues in including embedded systems in university curricula, as well as in setting up research programs that are crucial for the education of graduate students.

Although Microsoft Windows is being deployed in mission-critical applications, little quantitative data has been published about its robustness. We present the results of executing over two million Ballista-generated exception handling tests across 237 functions and system calls involving six Windows variants, as well as similar tests conducted on the Linux operating system. Windows 95, Windows 98 and Windows CE were found to be vulnerable to complete system crashes caused by very simple C programs for several different functions. No system crashes were observed on Windows NT, Windows 2000 or Linux. Linux was significantly more graceful at handling exceptions from system calls in a program-recoverable manner than Windows NT and Windows 2000, but those Windows variants were more robust than Linux (with glibc) at handling C library exceptions. While the choice of operating systems cannot be made solely on the basis of one set of tests, it is hoped that such results will form a starting point for comparing dependability across heterogeneous platforms.

Operating systems form a foundation for robust application software, making it important to understand how effective they are at handling exceptional conditions. The Ballista testing system was used to characterize the handling of exceptional input parameter values for up to 233 POSIX functions and system calls on each of 15 widely used operating system (OS) implementations. This identified ways to crash systems with a single call, ways to cause task hangs within OS code, ways to cause abnormal task termination within OS and library code, failures to implement defined POSIX functionality, and failures to report unsuccessful operations. Overall, only 55 percent to 76 percent of the exceptional tests performed generated error codes, depending on the operating system being tested. Approximately 6 percent to 19 percent of tests failed to generate any indication of error despite exceptional inputs. Approximately 1 percent to 3 percent of tests revealed failures to implement defined POSIX functionality for unusual, but specified, situations. Between 18 percent and 33 percent of exceptional tests caused the abnormal termination of an OS system call or library function, and five systems were completely crashed by individual system calls with exceptional parameter values. The most prevalent sources of these robustness failures were illegal pointer values, numeric overflows, and end-of-file overruns.

Creating robust software requires not only careful specification and implementation, but also quantitative measurement. This paper describes Ballista exception handling testing of the High Level Architecture RunTime Infrastructure (HLA RTI). The RTI is a standard distributed simulation system intended to provide completely robust exception handling, yet implementations have normalized robustness failure rates as high as 10%. Non-robust testing responses include exception handler crashes, segmentation violations, "unknown" exceptions, and task hangs. Other issues include different robustness failure modes across ports to two operating systems, and mandatory client machine rebooting after a particular RTl failure. Testing the RTI led to scalable extensions of the Ballista architecture for handling exception-based error reporting models, testing object-oriented software structures (including call-backs, pass by reference, and constructors), and operating in a state-rich, distributed system environment. These results demonstrate that robustness testing can provide useful feedback to high-quality software development processes, and can be applied to domains well beyond the previous work on testing operating systems.

When creating mission-critical distributed systems using off-the-shelf components, it is important to assess the dependability of not only the hardware, but the software as well. This paper proposes a way to test operating system dependability. The concept of response regions is presented as a way to visualize erroneous system behavior and gain insight into failure mechanisms. A 5-point "CRASH" (catastrophic, restart, abort, silent, hindering) scale is defined for grading the severity of robustness vulnerabilities encountered. Test results from five operating systems are analyzed for robustness vulnerabilities, and exhibit a range of dependability. Robustness benchmarking comparisons of this type may provide important information to both users and designers of off-the-shelf software for dependable systems.

Many embedded systems have substantially different design constraints than desktop computing applications. No single characterization applies to the diverse spectrum of embedded systems. However, some combination of cost pressure, long life-cycle, real-time requirements, reliability requirements, and design culture dysfunction can make it difficult to successfully apply traditional computer design methodologies and tools to embedded applications. Embedded systems in many cases must be optimized for life-cycle and business-driven factors rather than for maximum computing throughput. There is currently little tool support for expanding embedded computer design to the scope of holistic embedded system design. However, knowing the strengths and weaknesses of current approaches can set expectations appropriately, identify risk areas to tool adopters, and suggest ways in which tool builders can meet industrial needs.

The results of cache-simulation experiments with an abstract machine for reducing combinator graphs are presented. The abstract machine, called TIGRE, exhibits reduction rates that, for similar kinds of combinator graphs on similar kinds of hardware, compare favorably with previously reported techniques. Furthermore, TIGRE maps easily and efficiently onto standard computer architectures, particularly those that allow a restricted form of self-modifying code. This provides some indication that the conventional "stored program" organization of computer systems is not necessarily an inappropriate one for functional programming language implementations. This is not to say, however, that present day computer systems are well equipped to reduce combinator graphs. In particular, the behavior of the cache memory has a significant effect on performance. In order to study and quantify this effect, trace-driven cache simulations of a TIGRE graph reducer running on a reduced instruction-set computer are conducted. The results of these simulations are presented with the following hardware-cache parameters varied: cache size, block size, associativity, memory update policy, and write-allocation policy. To begin with, the cache organization of a commercially available system is used and then the performance sensitivity with respect to variations of each parameter are measured. From the results of the simulation study, a conclusion is made that combinator-graph reduction using TIGRE runs most efficiently when using a cache memory with an allocate-on-write-miss strategy, moderately large block size (preferably with subblock placement), and copy-back memory updates.

We present a new abstract machine for graph reduction called TIGRE. Benchmark results show that TIGRE's execution speed compares quite favorably with previous combinator-graph reduction techniques on similar hardware. Furthermore, the mapping of TIGRE onto conventional hardware is simple and efficient. Mainframe implementations of TIGRE provide performance levels exceeding those previously available on custom graph reduction hardware.