Runtime Verification

Futures are a program abstraction that express a simple form of fork-join parallelism. The expression

future (e)

declares that

e

can be evaluated concurrently with the

future

’s continuation.

Safe

-futures provide additional deterministic guarantees, ensuring that all data dependencies found in the original (non-future annotated) version are respected. In this paper, we present a dynamic analysis for enforcing determinism of safe-futures in an ML-like language with dynamic thread creation and first-class references. Our analysis tracks the interaction between futures (and their continuations) with other explicitly defined threads of control, and enforces an

isolation

property that prevents the effects of a continuation from being witnessed by its future, indirectly through their interactions with other threads. Our analysis is defined via a lightweight capability-based dependence tracking mechanism that serves as a compact representation of an effect history. Implementation results support our premise that futures and threads can extract additional parallelism compared to traditional approaches for safe-futures.

Deadlock immunity is a property by which programs, once afflicted by a deadlock, develop resistance against future occurrences of that deadlock. Our deadlock immunity system, called Dimmunix, provides transparent immunization against deadlocks involving mutex locks.

In this paper, we focus on efficiently protecting systems against deadlocks regardless of the rate of synchronization operations performed. We describe five optimizations that reduce the runtime overhead imposed by Dimmunix on the host system: (1) offline deadlock detection and signature extraction, which avoids runtime tracking of lock-to-thread allocations; (2) selective program instrumentation, whereby only vulnerable synchronization statements are monitored; (3) inline matching of deadlock signatures, which avoids expensive call stack retrieval; (4) false positive reduction, which avoids unnecessary thread serialization; and (5) safe early resumption of threads, allowing suspended threads to resume their execution more quickly than in the original Dimmunix. Our optimizations enable Dimmunix to achieve a reduction of 2.8x-5.2x in the runtime overhead it introduces for real-world systems like Eclipse, Vuze, and MySQL JDBC.

It is difficult to write parallel programs that are correct. This is because of the potential for

data races

, when parallel tasks access shared data in complex and unexpected ways. A classic approach to addressing this problem is dynamic race detection, which has the benefits of working transparently to the programmer and not raising any false alarms. Unfortunately, dynamic race detection is very slow in practice; further, it can only detect low-level races, not high-level races which are also known as

atomicity violations

. In this paper, we present a new approach to dynamic detection of data races and atomicity violations based on the concept of

permission regions

, which are regions of code that have permission to read or write certain variables. Dynamic checks are used to ensure that no conflicting permission regions execute in parallel, thereby allowing the granularity of checks to be adjusted according to the size of permission regions. We demonstrate that permission regions can be used to achieve significantly better performance than past work on dynamic race detection, to the point where they could be used to enable always on race detection for both low- and high-level races in production code.

Data races are among the most difficult to detect and costly bugs. Race detection has been studied widely, but none of the existing tools satisfies the requirements of high speed, detailed reports and wide availability at the same time. We describe our attempt to create a tool that works fast, has detailed and understandable reports and is available on a variety of platforms. The race detector is based on our previous work, ThreadSanitizer [1], and the instrumentation is done using the LLVM compiler. We show that applying compiler instrumentation and sampling reduces the slowdown to less than 1.5x, fast enough to use instrumented programs interactively.

Protecting running programs from exploits has been the focus of many host-based intrusion detection systems. To this end various formal methods have been developed that either require manual construction of attack signatures or modelling of normal program behavior to detect exploits. In terms of the ability to discover new attacks before the infection spreads, the former approach has been found to be lacking in flexibility. Consequently, in this paper, we present an anomaly monitoring system, NORT, that verifies on-the-fly whether running programs comply to their expected normal behavior. The

model of normal behavior

is based on a rich set of discriminators such as minimal infrequent and maximal frequent iterative patterns of system calls, and relative entropy between distributions of system calls. Experiments run on malware samples have shown that our approach is able to effectively detect a broad range of attacks with very low overheads.

Linear Temporal Logic (LTL) on finite traces has proven to be a good basis for the analysis and enactment of flexible constraint-based business processes. The

Declare

language and system benefit from this basis. Moreover, LTL-based languages like Declare can also be used for runtime verification. As there are often many interacting constraints, it is important to keep track of

individual constraints

and

combinations of potentially conflicting constraints

. In this paper, we operationalize the notion of conflicting constraints and demonstrate how innovative automata-based techniques can be applied to monitor running process instances. Conflicting constraints are detected immediately and our toolset (realized using Declare and ProM) provides meaningful diagnostics.

Given a dense-time real-valued signal and a parameterized temporal logic formula with

both

magnitude and timing parameters, we compute the subset of the parameter space that renders the formula satisfied by the trace. We provide two preliminary implementations, one which follows the exact semantics and attempts to compute the validity domain by quantifier elimination in linear arithmetics and one which conducts adaptive search in the parameter space.

Recent research has proposed several analyses to mitigate the fact that finding concurrency bugs in multi-threaded software is notoriously hard. This work proposes a new analysis based on a correctness criterion called “atomic-set serializability”, which incorporates both race conditions and traditional atomicity/serializability. We present a novel analysis based on conflict cycle detection that is guaranteed to find all violations in the intercepted execution trace. A set of heuristics automatically determines all annotations required for atomic-set serializability. We implemented the analysis and evaluated it on a suite consisting of real programs and benchmarks. The evaluation demonstrates the usefulness of our heuristics by finding a number of known (as well as new) violations with competitive overhead and a very low false positive rate.

Coverage metrics play a crucial role in testing. They allow one to estimate how well a program has been tested and/or to control the testing process. Several concurrency-related coverage metrics have been proposed, but most of them do not reflect concurrent behaviour accurately enough. In this paper, we propose several new metrics that are suitable primarily for saturation-based or search-based testing of concurrent software. Their distinguishing feature is that they are derived from various dynamic analyses designed for detecting synchronisation errors in concurrent software. In fact, the way these metrics are obtained is generic, and further metrics can be obtained in a similar way from other analyses. The underlying motivation is that, within such analyses, behavioural aspects crucial for occurrence of various bugs are identified, and hence it makes sense to track how well the occurrence of such phenomena is covered by testing. Next, coverage tasks of the proposed as well as some existing metrics are combined with an abstract identification of the threads participating in generation of the phenomena captured in the concerned tasks. This way, further, more precise metrics are obtained. Finally, an empirical evaluation of the proposed metrics, which confirms that several of them are indeed more suitable for saturation-based and search-based testing than the previously known metrics, is presented.

We introduce the concept of

Runtime Verification with State Estimation

and show how this concept can be applied to estimate the probability that a temporal property is satisfied by a run of a program when monitoring overhead is reduced by sampling. In such situations, there may be

gaps

in the observed program executions, thus making accurate estimation challenging. To deal with the effects of sampling on runtime verification, we view event sequences as observation sequences of a Hidden Markov Model (HMM), use an HMM model of the monitored program to “fill in” sampling-induced gaps in observation sequences, and extend the classic forward algorithm for HMM state estimation (which determines the probability of a state sequence, given an observation sequence) to compute the probability that the property is satisfied by an execution of the program. To validate our approach, we present a case study based on the mission software for a Mars rover. The results of our case study demonstrate high prediction accuracy for the probabilities computed by our algorithm. They also show that our technique is much more accurate than simply evaluating the temporal property on the given observation sequences, ignoring the gaps.

Time-triggered

runtime verification aims at tackling two defects associated with runtime overhead normally incurred in event-triggered approaches:

unboundedness

and

unpredictability

. In the time-triggered approach, a monitor runs in parallel with the program and periodically samples the program state to evaluate a set of properties. In our previous work, we showed that to increase the sampling period of the monitor (and hence decrease involvement of the monitor), one can employ auxiliary memory to build a history of state changes between subsequent samples. We also showed that the problem of optimization of the size of history and sampling period is NP-complete.

In this paper, we propose a set of heuristics that find near-optimal solutions to the problem. Our experiments show that by employing negligible extra memory at run time, we can solve the optimization problem significantly faster, while maintaining a similar level of overhead as the optimal solution. We conclude from our experiments that the NP-completeness of the optimization problem is not an obstacle when applying time-triggered runtime verification in practice.

We present

CoMA

(Conformance Monitoring by Abstract State Machines), a specification-based approach and its supporting tool for runtime monitoring of Java software. Based on the information obtained from code execution and model simulation, the conformance of the concrete implementation is checked with respect to its formal specification given in terms of Abstract State Machines. At runtime, undesirable behaviors of the implementation, as well as incorrect specifications of the system behavior are recognized.

The technique we propose makes use of Java annotations, which link the concrete implementation to its formal model, without enriching the code with behavioral information contained only in the abstract specification. The approach fosters the separation between implementation and specification, and allows the reuse of specifications for other purposes (formal verification, simulation, model-based testing, etc.).

This paper presents a non-intrusive framework for runtime verification of executable microcontroller code. A dedicated hardware unit is attached to a microcontroller, which executes the program under scrutiny, to track atomic propositions stated as assertions over program variables. The truth verdicts over the assertions are the inputs to a custom-designed

μ

CPU unit that evaluates past-time LTL specifications in parallel to program execution. To achieve this, the instruction set of the

μ

CPU is tailored to determining satisfaction of specifications.

We present and analyze monitoring algorithms for a safety fragment of metric temporal logics, which differ in their underlying time model. The time models considered have either dense or discrete time domains and are point-based or interval-based. Our analysis reveals differences and similarities between the time models for monitoring and highlights key concepts underlying our and prior monitoring algorithms.

Correct functioning of cyber-physical systems is of critical importance. This is more so in the case of safety critical systems such as in medical, automotive and many other applications. Since verification of correctness, in general, is infeasible and testing is not exhaustive, it is of critical importance to monitor such system during their operation and detect erroneous behaviors to be acted on. A distinguishing property of cyber-physical systems is that they are described by a mixture of integer-valued and real-valued variables. As a result, approaches that assume countable number of states are not applicable for runtime monitoring of such systems. This paper proposes a formalism, called Extended Hidden Markov systems, for specifying behavior of systems with such hybrid state. Using measure theory, it exactly characterizes when such systems are monitorable with respect to a given property. It also presents monitoring algorithms and experimental results showing their effectiveness.

In this paper, we investigate formalisms for specifying periodic signals using time and frequency domain specifications along with algorithms for the signal recognition and generation problems for such specifications. The time domain specifications are in the form of hybrid automata whose continuous state variables generate the desired signals. The frequency domain specifications take the form of an “envelope” that constrains the possible power spectra of the periodic signals with a given frequency cutoff. The combination of time and frequency domain specifications yields mixed-domain specifications that constrain a signal to belong to the intersection of the both specifications.

We show that the signal recognition problem for periodic signals specified by hybrid automata is NP-complete, while the corresponding problem for frequency domain specifications can be approximated to any desired degree by linear programs, which can be solved in polynomial time. The signal generation problem for time and frequency domain specifications can be encoded into linear arithmetic constraints that can be solved using existing SMT solvers. We present some preliminary results based on an implementation that uses the SMT solver Z3 to tackle the signal generation problems.

Runtime verification (RV) is a natural fit for ultra-critical systems, where correctness is imperative. In ultra-critical systems, even if the software is fault-free, because of the inherent unreliability of commodity hardware and the adversity of operational environments, processing units (and their hosted software) are replicated, and fault-tolerant algorithms are used to compare the outputs. We investigate both software monitoring in distributed fault-tolerant systems, as well as implementing fault-tolerance mechanisms using RV techniques. We describe the Copilot language and compiler, specifically designed for generating monitors for distributed, hard real-time systems, and we describe a case study in a Byzantine fault-tolerant airspeed sensor system.

For service-based systems which are composed of multiple independent stakeholders, correctness cannot be ascertained statically. Continuous monitoring is required to assure that runtime behavior of the systems complies with specified properties. However, most existing work considers only the temporal constraints of messages exchanged between services, ignoring the actual data contents inside the messages. As a result, it is difficult to validate some dynamic properties such as how message data of interest is processed between different participants. To address this issue, this paper proposes an efficient, online monitoring approach to dynamically analyze data-centric properties in service-based systems. By introducing

Par

-BCL - a Parametric Behavior Constraint Language for Web services - various data-centric properties can be specified and monitored. To keep runtime overhead low, we statically analyze the monitored properties to generate parameter state machine, and combine two different indexing mechanisms to optimize the monitoring. The experiments show that the proposed approach is efficient.

The robustness of software systems is adversely affected by programming errors and security exploits that corrupt heap data structures. In this paper, we present the design and implementation of TxMon, a system to detect such data structure corruptions. TxMon leverages the concurrency control machinery implemented by hardware transactional memory (HTM) systems to additionally enforce programmer-specified consistency properties on data structures at runtime. We implemented a prototype version of TxMon using an HTM system (LogTMSE) and studied the feasibility of applying TxMon to enforce data structure consistency properties on several benchmarks. Our experiments show that TxMon is effective at monitoring data structure properties, imposing tolerable runtime performance overheads.

Monitoring complex applications to detect violations from specified properties is a promising field that has seen the development of many novel techniques and tools in the last decade. In spite of this effort, limiting, understanding, and predicting the cost of monitoring has been a challenge. Existing techniques primarily target the overhead caused by the large number of monitor instances to be maintained and the large number of events generated by the program that are related to the property. However, other factors, in particular, the algorithm used to process the sequence of events can significantly influence runtime overhead. In this work, we describe three basic algorithmic approaches to finite state monitoring and distill some of their relative strengths by conducting preliminary studies. The results of the studies reveal non-trivial differences in runtime overhead when using different monitoring algorithms that can inform future work.

Symbolic execution with interpolation is emerging as an alternative to

cegar

for software verification. The performance of both methods relies critically on interpolation in order to obtain the most general abstraction of the current symbolic or abstract state which can be shown to remain error-free.

cegar

naturally handles unbounded loops because it is based on abstract interpretation. In contrast, symbolic execution requires a special extension for such loops.

In this paper, we present such an extension. Its main characteristic is that it performs

eager subsumption

, that is, it always attempts to perform abstraction in order to avoid exploring redundant symbolic states. It balances this primary desire for more abstraction with the secondary desire to maintain the

strongest loop invariant

, for earlier detection of infeasible paths, which entails less abstraction. Occasionally certain abstractions are not permitted because of the reachability of error states; this is the underlying mechanism which then causes

selective unrolling

, that is, the unrolling of a loop along relevant paths only.

Dynamic analysis is the analysis of the properties of a running program. In order to perform dynamic analysis, information about the running program is often collected through execution traces. Exploring and analyzing these traces can be an issue due to their size and that knowledge of a human expert is often needed to derive the required conclusions. In this paper we provide a framework in which the semantics of execution traces, as well as that of dynamic analyses, are formally represented through ontologies. In this framework the exploration and analysis of the traces is enabled through semantic queries, and enhanced further through automated reasoning on the ontologies. We will also provide ontologies to represent traces and some basic dynamic analysis techniques, along with semantic queries that enable these techniques. Finally we will illustrate our approach through an example.

We present a new multi-valued monitoring approach for linear-time temporal logic that classifies trace prefixes not only according to the existence of correct and erroneous continuations, but also according to the strategic power of the system and its environment to avoid or enforce a violation of the specification. We classify the monitoring status into four levels: (1) the worst case is a

violation

, where no continuation satisfies the specification any more; (2)

unrealizable

means that the environment can force the system to violate the specification; (3)

realizable

means that the system can enforce that the specification is satisfied; (4) the best case,

fulfilled

, indicates that all possible continuations satisfy the specification. Because our approach recognizes situations where the system cannot avoid a violation even though there may still be continuations in which the specification is satisfied, our approach detects errors earlier, and it detects errors that are missed by less detailed classifications. We give an asymptotically optimal construction of multi-valued monitoring automata based on parity games.

We present an on-line algorithm for the runtime checking of temporal properties, expressed as past-time Linear Temporal Logic (LTL) over the traces of observations recorded by a “black box”-like device. The recorder captures the observed values but not the precise time of their occurrences, and precise truth evaluation of a temporal logic formula cannot always be obtained. In order to handle this uncertainty, the checking algorithm is based on a three-valued semantics for past-time LTL defined in this paper. In addition to the algorithm, the paper presents results of an evaluation that aimed to study the effects of the recording uncertainty on different kinds of temporal logic properties.