Autonomous systems often address complex planning problems, which require both prospective action planning and retrospective data evaluation. Timed games could aid since they automatically synthesize strategies that, provably correct, solve those planning problems; yet, they assume a static model of the environment, which is not realistic for autonomous systems. However, many autonomous systems are control applications, which employ sensors that capture system behavior at run time and can thus compensate for incomplete knowledge at modeling time. In this paper, we propose an online strategy synthesis , which, based on offline strategy synthesis on the one hand and on sensor information about the current state of the physical world on the other hand, derives formal safety guarantees while reacting and adapting to environment changes. We formalize the needle-steering problem from medical robotics, i.e., the problem of navigating a (flexible and beveled) needle through partially unknown tissue towards a target without damaging its surroundings, by interpreting it as a timed game. Further, we introduce a new representation of its environment through different region types that determine the acceptance of action plans and trigger local correcting actions. We present an algorithm for online strategy synthesis and, for the given region representation, formally prove that it returns safe online controllers. The algorithm is implemented on top of Uppaal Stratego. For two medical applications of needle steering, peridural anesthesia and predefined needle trajectory , we demonstrate the necessity of online adjustments in a series of simulations with various degrees of initial knowledge about the environment, and show that the overhead of online synthesis remains practical.

Abstract Verifying safety requirements by model checking becomes increasingly important for safety-critical applications. For the validity of such proof in practice, the model needs to capture the actual behavior of the real system, which could be tested by containment checks of real observation traces. Basic equivalence checks, however, are not applicable if the system is only partially or imprecisely observable, if the model abstracts from explicit states with symbolic semantics, or if the checks are not expressible in the logics supported by a model checker. In this article, we solve the problem of observation containment checking in timed automata via reachability checking on tester systems. We introduce the logic SRL (sequence reachability logic) to express observations as sequences of delayed reachability properties. Through SBLL (introduced by Aceto et al.) as intermediate logic, we synthesize a set of matcher model templates for partial and imprecise observations and further extend these templates for the case of limited state accessibility in a model. For the obtained matching traces, we define the back-transformation into the original model domain and formally prove the correctness of the transformation. We implemented the observation matching approach, and apply it to a set of 7 demo and 3 case study models with different levels of observability. The results show that all positive and negative observations are correctly classified, and that the most advanced matcher model instance still offers average run times between 0.1 and 1 s in all but 3 scenarios.

Abstract When the simulation of a system, or the verification of its model, needs to be resumed in an online context, we face the problem that a particular starting state needs to be reached or constructed, from which the process is then continued. For timed automata, especially the construction of a desired clock state, represented as a difference bound matrix (DBM), can be problematic, as only a limited set of DBM operations is available, which often does not include the ability to set DBM entries individually to the desired value. In online applications, we furthermore face strict timing requirements imposed on the generation process. In this paper, we present an approach to construct a target clock state in a model via sequences of DBM operations (as supported by the model checkerUppaal), for which we can guarantee bounded lengths, solving the present problem of ever-growing sequences over time. The approach forges new intermediate states and transitions based on an overapproximation of the target state, followed by a constraining phase, until the target state is reached. We prove that the construction sequence lengths are independent of the original trace lengths and are determined by the number of system clocks only, allowing for state construction in bounded time. Furthermore, we implement the (re-)construction routines and an extendedUppaalmodel simulator which provides the original operation sequences. Applying the approach to a test model suite as well as randomly generated DBM operation sequences, we empirically validate the theoretical result and the implementation.

Previous online reachability algorithms for hybrid automata reduced conservatism in verified Simplex controller architectures, but were restricted to the imprecise real-time paradigm, i.e., their precision increases over time. Yet, many safety-critical cyber-physical systems are hard real-time systems, requiring an upper bound on the worst-case execution time (WCET) of each task to be known. We show that the iteration bound of the reachability loop can be parameterized by a single factor which determines the precision. Consequently, an algorithm could select a fixed precision depending on the time left until its deadline. In this paper we present such a WCET-aware reachability algorithm, based on an existing algorithm for imprecise real-time. Its smallest WCET bound on an Infineon XMC4500 microprocessor is 32.861 milliseconds.

Violations of the privacy of users can happen if data protection is not a fundamental part of the development process of a software system. The principle of Privacy by Design (PbD) therefore stipulates the consideration of privacy as a default feature. We have developed an integrated tool environment called CAPVerDE that provides a formal description language of software architectures and helps a designer by automatically verifying data minimization properties at the architectural level. Our logic includes probabilistic properties that introduce uncer- tainty into the architectures. These properties can be used to model attack scenarios that rely on chance. This paper presents the logic of the description language of CAPVerDE and illustrates the verification process by applying it to a smart energy metering scenario.

A challenge in sound reverse engineering of binary executables is to determine sets of possible targets for dynamic jumps. One technique to address this challenge is abstract interpretation, where singleton values in registers and memory locations are overapproximated to collections of possible values. With contemporary abstract interpretation techniques, convexity is usually enforced on these collections, which causes unacceptable loss of precision. We present a non-convex abstract domain, suitable for the analysis of binary executables. The domain is based on binary decision diagrams (BDD) to allow an efficient representation of non-convex sets of integers. Non-convex sets are necessary to represent the results of jump table lookups and bitwise operations, which are more frequent in executables than in high-level code because of optimizing compilers. Our domain computes abstract bitwise and arithmetic operations precisely and looses precision only for division and multiplication. Because the operations are defined on the structure of the BDDs, they remain efficient even if executed on very large sets. In executables, conditional jumps require solving formulas built with negation and conjunction. We implement a constraint solver using the fast intersection and complementation of BDD-based sets. Our domain is implemented as a plug-in, called BDDStab, and integrated with the binary analysis framework Jakstab. We use Jakstab's k-set and interval domains to discuss the increase in precision for a selection of compiler-generated executables.

This paper presents a big-step operational semantics for distributed lazy evaluation. Our semantics is an extension to the famous heap-based semantics of Launchbury for lazy evaluation. The high level of abstraction in our semantics helps us to easily prove different properties that are of interest to task distribution. Most importantly, we give criteria which establish a notion of bisimilarity between heaps. We also prove the validity of an induction principle that is used for proving observational equivalence between programs written in our system. Additionally, we briefly report the mechanisation of our semantics.

RegVIS is a tool for viewing directed graphs with start and end nodes. It applies a new visualization technique, which uses regular expressions as a meta-representation of all the paths in an input graph, the result is a containment-based and structured visualization of that graph. The tool can be configured to derive these regular expressions from the input graph using either the Brzozowski algebraic method or the transitive closure method. Regvis can be used in combination with the binary code analysis tool IDA (Interactive Disassembler), either integrated or standalone, to view the control flow graph (CFG) of assembler code. The resulting visualization, which restructures the control flow and can thus help reduce program comprehension efforts, is called control flow blocks (CFB). In this paper, we present the workings of regVIS and evaluate the new CFB visualization it produces against the traditional CFG visualization in an explorative user study. The study suggests that the CFB is better for analyzing and navigating along specific execution paths, while the CFG is better for getting an overview of the overall control flow.

During the last decade, static analyzers of source code have improved greatly. Today, precise analyzers that propagate values for the program's variables, for instance with interval arithmetic, are used in the industry. The simultaneous propagation of sets of values, while computationally efficient, is a source of approximations, and ultimately of false positives. When the loss of precision is detrimental to the user's goals, a user needs to provide some kind of manual guidance. Frama-C, a framework for the static analysis of C programs, provides a sound value analyzer. This analyzer can optionally be guided by skillfully placed user annotations. This article describes SPALTER, a Frama-C plug-in that uses a variation of the Skelboe-Moore algorithm from the field of interval arithmetic to guide Frama-C's value analyzer towards a high-level objective set by the user. SPALTER reproduces the results of a case study that used Frama-C's value analysis and required extensive manual guidance. In difference, our approach with SPALTER required no guidance, except preparation of the analyzed program by slicing.

Abstract Earlier studies have introduced a list of high-level evaluation criteria to assess how well a language supports generic programming. Languages that meet all criteria include Haskell because of its type classes and C++ with the concept feature. We refine these criteria into a taxonomy that captures commonalities and differences between type classes in Haskell and concepts in C++ and discuss which differences are incidental and which ones are due to other language features. The taxonomy allows for an improved understanding of language support for generic programming, and the comparison is useful for the ongoing discussions among language designers and users of both languages.

Software systems are becoming increasingly vulnerable to a new class of soft errors, originating from voltage spikes produced by cosmic radiation. The standard technique for assessing the source-level impact of these soft errors, fault injection - essentially a black-box testing technique - provides limited high-level information. Since soft errors can occur anywhere, even control-structured white-box techniques offer little insight. We propose a type-based approach, founded on data-flow structure, to classify the usage pattern of registers and memory cells. To capture all soft errors, the type system is defined at the assembly level, close to the hardware, and allows inferring types in the untyped assembly representation. In a case study, we apply our type inference scheme to a prototype brake-by-wire controller, developed by Volvo Technology, and identify a high correlation between types and fault-injection results. The case study confirms that the inferred types are good predictors for soft-error impact.

Since the standard template library (STL), generic libraries in C++ rely on concepts to precisely specify the requirements of generic algorithms (function templates) on their parameters (template arguments). Modifying the definition of a concept even slightly, can have a potentially large impact on the (interfaces of the) entire library. In particular the non-local effects of a change, however, make its impact difficult to determine by hand. In this paper we propose a conceptual change impact analysis (CCIA), which determines the impact of changes of the conceptual specification of a generic library. The analysis is organized in a pipe-and-filter manner, where the first stage finds any kind of impact, the second stage various specific kinds of impact. Both stages describe reachability algorithms, which operate on a conceptual dependence graph. In a case study, we apply CCIA to a new proposal for STL iterator concepts, which is under review by the C++ standardization committee. The analysis shows a number of unexpected incompatibilities and, for certain STL algorithms, a loss of genericity

Abstract Traditional static checking centers around finding bugs in programs by isolating cases where the language has been used incorrectly. These language‐based checkers do not understand the semantics of software libraries, and therefore cannot be used to detect errors in the use of libraries. In this paper, we introduce STLlint, a program analysis we have implemented for the C++ Standard Template Library and similar, generic software libraries, and we present the general approach that underlies STLlint. We show that static checking of library semantics differs greatly from checking of language semantics, requiring new representations of program behavior and new algorithms. Major challenges include checking the use of generic algorithms, loop analysis for interfaces, and organizing behavioral specifications for extensibility. Copyright © 2005 John Wiley & Sons, Ltd.

Abstract Class templates represent a difficulty for C++ garbage collectors since relevant information is available only very late, at instantiation time. Current collectors therefore either fail to work with class templates or have to run in a non‐optimized mode. This paper introduces the template garbage collector (TGC), the first mostly‐copying collector that can handle class templates. It discusses the design decisions that are suggested by the specifics of generic template programming and presents performance results and memory measurements of tests with MTL and GTL, two generic C++ libraries based on the Standard Template Library. The tests show that TGC substantially improves the run times of programs with many small objects with short lifetimes or large objects with long lifetimes. The memory usage at the same time is reasonable. Since TGC modifies the mostly‐copying technique, the heap sizes are in many cases considerably smaller than they are for traditional mostly‐copying collectors. The tests also show that TGC is competitive with the Boehm–Demers–Weiser collector, the most widely used collector for C++. Copyright © 2001 John Wiley & Sons, Ltd.

This paper demonstrates a unified and garbage-collector independent way to describe the information required for precise collection. Thereby it is possible to construct, a library that can be used with various garbage collectors, without modifying the code of the library or the collector itself. The library design presented applies the adaptor idiom of generic programming which guarantees no overhead incurred if the library is used with manual allocators or with garbage collectors that do not require programmer cooperation. As an illustration of our approach we provide sample adaptors for Bartlett's and CMM primary collectors. We also show that the Standard Template Library (STL) can be easily modified to become garbage-collector aware.