On software verification for sensor nodes

We consider software written for networked, wireless sensor nodes, and specialize software verification techniques for standard C programs in order to locate programming errors in sensor applications before the software's deployment on motes. Ensuring the reliability of sensor applications is challenging: low-level, interrupt-driven code runs without memory protection in dynamic environments. The difficulties lie with (i) being able to automatically extract standard C models out of the particular flavours of embedded C used in sensor programming solutions, and (ii) decreasing the resulting program's state space to a degree that allows practical verification times.We contribute a platform-dependent, OS-independent software verification tool for OS-wide programs written in MSP430 embedded C with asynchronous hardware interrupts. Our tool automatically translates the program into standard C by modelling the MCU's memory map and direct memory access. To emulate the existence of hardware interrupts, calls to hardware interrupt handlers are added, and their occurrence is minimized with a double strategy: a partial-order reduction technique, and a supplementary reachability check to reduce overapproximation. This decreases the program's state space, while preserving program semantics. Safety specifications are written as C assertions embedded in the code. The resulting sequential program is then passed to CBMC, a bounded software verifier for sequential ANSI C. Besides standard errors (e.g., out-of-bounds arrays, null-pointer dereferences), this tool chain is able to verify application-specific assertions, including low-level assertions upon the state of the registers and peripherals.Verification for wireless sensor network applications is an emerging field of research; thus, as a final note, we survey current research on the topic.     

基于变量访问序模式的中断数据竞争检测方法

在航天嵌入式软件等中断驱动型软件中,中断数据竞争问题十分突出.然而中断在并发语义、同步机制、调度机制等方面与线程（任务）有诸多不同,具有Ad-hoc特征,难以统一刻画,因此主流的数据竞争检测方法并不适用.以航天嵌入式软件数据竞争案例库为基础进行了系统分析,提出刻画有害中断数据竞争的7种缺陷模式.针对其中最常见且最难解决的单变量访问序模式,基于抽象解释提出一种支持过程间分析、中断并发分析的高效检测方法.设计并实现了相应的检测工具SpaceDRC.实验表明,SpaceDRC能够在145毫秒内检测出约21400行程序中的真实数据竞争.SpaceDRC已经在多个航天重点型号中进行了应用,使得中断数据竞争专项分析的效率提高了至少5倍,并且降低了问题遗漏率.     

Modeling Multithreaded Applications Using Petri Nets

Since most modern computing systems contain multiple processing elements, applications are relying on multithreaded programming techniques that allow a program to execute multiple tasks concurrently to take advantage of the processing capabilities. Multithreaded programs are more difficult to design and test because of the nondeterministic execution orders and synchronization among the threads. Different approaches can be used to test Multithreaded Applications. In our approach we use Petri nets to represent the key elements of interactions among threads to identify potential problems such as race conditions, lost signals, and deadlocks. A tool called C2Petri has been developed which converts C-Pthreads programs to the equivalent Petri net model. This tool helps verification of Pthread-based programs. At present the tool has limited capabilities and we hope to expand the capabilities of our tool in the near future.     

Certifying Low-Level Programs with Hardware Interrupts and Preemptive Threads

Hardware interrupts are widely used in the world’s critical software systems to support preemptive threads, device drivers, operating system kernels, and hypervisors. Handling interrupts properly is an essential component of low-level system programming. Unfortunately, interrupts are also extremely hard to reason about: they dramatically alter the program control flow and complicate the invariants in low-level concurrent code (e.g., implementation of synchronization primitives). Existing formal verification techniques—including Hoare logic, typed assembly language, concurrent separation logic, and the assume-guarantee method—have consistently ignored the issues of interrupts; this severely limits the applicability and power of today’s program verification systems. In this paper we present a novel Hoare-logic-like framework for certifying low-level system programs involving both hardware interrupts and preemptive threads. We show that enabling and disabling interrupts can be formalized precisely using simple ownership-transfer semantics, and the same technique also extends to the concurrent setting. By carefully reasoning about the interaction among interrupt handlers, context switching, and synchronization libraries, we are able to—for the first time—successfully certify a preemptive thread implementation and a large number of common synchronization primitives. Our work provides a foundation for reasoning about interrupt-based kernel programs and makes an important advance toward building fully certified operating system kernels and hypervisors.     

Signals,timers, and continuations for multithreaded user‐level protocols

Precise timing and asynchronous I/O are appealing features for many applications. Unix kernels provide such features on a per‐process basis, using signals to communicate asynchronous events to applications. Per‐process signals and timers are grossly inadequate for complex multithreaded applications that require per‐thread signals and timers that operate at finer granularity. To respond to this need, we present a scheme that integrates asynchronous (Unix) signals with user‐level threads, using the ARIADNE system as a platform. This is done with a view towards support for portable, multithreaded, and multiprotocol distributed applications, namely the CLAM (connectionless, lightweight, and multiway) communications library. In the same context, we propose the use of continuations as an efficient mechanism for reducing thread context‐switching and busy‐wait overheads in multithreaded protocols. Our proposal for integrating timers and signal‐handling mechanisms not only solves problems related to race conditions, but also offers an efficient and flexible interface for timing and signalling threads. Copyright © 2006 John Wiley & Sons, Ltd.     

Deadline analysis of interrupt-driven software

Real-time, reactive, and embedded systems are increasingly used throughout society (e.g., flight control, railway signaling, vehicle management, medical devices, and many others). For real-time, interrupt-driven software, timely interrupt handling is part of correctness. It is vital for software verification in such systems to check that all specified deadlines for interrupt handling are met. Such verification is a daunting task because of the large number of different possible interrupt arrival scenarios. For example, for a Z86-based microcontroller, there can be up to six interrupt sources and each interrupt can arrive during any clock cycle. Verification of such systems has traditionally relied upon lengthy and tedious testing; even under the best of circumstances, testing is likely to cover only a fraction of the state space in interrupt-driven systems. This paper presents the Zilog architecture resource bounding infrastructure (ZARBI), a tool for deadline analysis of interrupt-driven Z86-based software. The main idea is to use static analysis to significantly decrease the required testing effort by automatically identifying and isolating the segments of code that need the most testing. Our tool combines multiresolution static analysis and testing oracles in such a way that only the oracles need to be verified by testing. Each oracle specifies the worst-case execution time from one program point to another, which is then used by the static analysis to improve precision. For six commercial microcontroller systems, our experiments show that a moderate number of testing oracles are sufficient to do precise deadline analysis.     

航天嵌入式软件整数溢出的形式化验证方法

整数溢出引起的软件系统安全性问题屡见不鲜,已有的模型检测技术由于存在状态空间爆炸、不能有效支持中断驱动型程序检测等缺点而少有工程应用.结合真实案例,对航天嵌入式软件整数溢出问题的分布和特征进行了系统性的分析.在有界模型检测技术的基础上,结合整数溢出特征,提出了基于整数溢出变量依赖的程序模型约简技术;同时,针对中断驱动型程序,结合中断函数特征抽象,提出了基于干扰变量的中断驱动程序顺序化方法.经过基准测试程序和真实航天嵌入式软件实验,结果表明：该方法在保证整数溢出问题检出率的前提下,不仅能够提高分析效率,还使得已有的模型检测技术能够适用于中断驱动型程序整数溢出检测.     

On Automation in the Verification of Software Barriers: Experience Report

We present an experience report on automating the verification of the software barrier synchronization primitive. The informal specification of the primitive is: when a thread calls the software barrier function, the thread halts until all other threads call their instances of the software barrier function. A successful software barrier call ensures that each thread has finished its portion of work before the threads start exchanging the results of these portions of work. While software barriers are widely used in parallel versions of major numerical algorithms and are indispensable in scientific computing, software barrier algorithms and their implementations scarcely have been verified. We improve the state of the art in proving the correctness of the major software barrier algorithms with off-the-shelf automatic verification systems such as Jahob, VCC, Boogie, Spin and Checkfence. We verify a central barrier, a C implementation of a barrier, a static tree barrier, a combining tree barrier, a dissemination barrier, a tournament barrier, a barrier with its client and a barrier on a weak memory model. In the process, we introduce a novel theorem proving method for proving validity of formulas containing cardinalities of comprehensions and improve the capabilities of one of the verification systems. Based on our experience, we propose new challenges in the verification of software barriers.     

Arachne: a portable threads system supporting migrant threads onheterogeneous network farms

We present the design and implementation of Arachne, a threads system that can be interfaced with a communications library for multithreaded distributed computations. In particular, Arachne supports thread migration between heterogeneous platforms, dynamic stack size management, and recursive thread functions. Arachne is efficient, flexible, and portable-it is based entirely on C and C++. To facilitate heterogeneous thread operations, we have added three keywords to the C++ language. The Arachne preprocessor takes as input code written in that language and outputs C++ code suitable for compilation with a conventional C++ compiler. The Arachne runtime system manages all threads during program execution. We present some performance measurements on the costs of basic thread operations and thread migration in Arachne and compare these to costs in other threads systems     

Generation, Optimization, and Evaluation of Multithreaded Code

The recent advent of multithreaded architectures holds many promises: the exploitation of intrathread locality and the latency tolerance of multithreaded synchronization can result in a more efficient processor utilization and higher scalability. The challenge for a code generation scheme is to make effective use of the underlying hardware by generating large threads with a large degree of internal locality without limiting the program level parallelism or increasing latency. Top-down code generation, where threads are created directly from the compiler's intermediate form, is effective at creating a relatively large thread. However, having only a limited view of the code at any one time limits the quality of threads generated. These top-down generated threads can therefore be optimized by global, bottom-up optimization techniques. In this paper, we introduce the Pebbles multithreaded model of computation and analyze a code generation scheme whereby top-down code generation is combined with bottom-up optimizations. We evaluate the effectiveness of this scheme in terms of overall performance and specific thread characteristics such as size, length, instruction level parallelism, number of inputs, and synchronization costs.     

基于AOP技术的通用线程监控平台的研究与实现

在传统的OOP编程中,由于需求空间是N维而实现空间是一维的,导致了软件开发中横切关注点的代码纠缠问题,严重影响了软件的质量.作为OOP的补充,AOP很好地解决了横切关注点带来的问题,提供了核心关注点和横切关注点互相分离的解决方案.本文从具体工程中开发线程监控这一需求所暴露的问题出发,提出了为什么需要AOP编程;然后着重讨论如何通过AOP技术解决这一问题,提出并实现了基于AOP技术的通用线程监控平台.该平台可以在不手工改变系统源代码的情况下通过工具植入系统内部,实现对运行线程信息的监视、对指定线程运行速度的变换和对整个系统运行行为的控制.     

Atomizer: A dynamic atomicity checker for multithreaded programs

Ensuring the correctness of multithreaded programs is difficult, due to the potential for unexpected interactions between concurrent threads. Much previous work has focused on detecting race conditions, but the absence of race conditions does not by itself prevent undesired interactions between threads.A more fundamental noninterference property is atomicity. A method is atomic if its execution is not affected by and does not interfere with concurrently-executing threads. Atomic methods can be understood according to their sequential semantics, which significantly simplifies both formal and informal correctness arguments.This paper presents a dynamic analysis for detecting atomicity violations. This analysis combines ideas from both Lipton’s theory of reduction and earlier dynamic race detectors. Experience with a prototype checker for multithreaded Java code demonstrates that this approach is effective for detecting errors due to unintended interactions between threads. In particular, our atomicity checker detects errors that would be missed by standard race detectors. Our experimental results also indicate that the majority of methods in our benchmarks are atomic, indicating that atomicity is a standard methodology in multithreaded programming.     

Interface-Based Specification and Verification of Concurrency Controllers

We present a modular approach to specification and verification of concurrency controllers by decoupling their behavior and interface specifications. The behavior specification of a concurrency controller defines how its shared variables change their values whereas the interface specification defines the order in which a client thread should call its methods. We show that the concurrency controllers can be designed modularly by composing their interfaces. We separate the verification of the concurrency controllers from the verification of the threads that use them. For the verification of the concurrency controllers we use infinite state verification techniques which enable us to verify controllers with parameterized constants and arbitrary number of user threads. We automatically generate Java monitors from the concurrency controller specifications which preserve the verified properties. For the thread verification we use finite state program verification tools which enable us to verify Java threads without any restrictions. We show that the user threads can be verified using stubs generated from the concurrency controller interfaces which improves the efficiency of the thread verification significantly.     

多线程应用程序调试技术

对多线程应用程序进行调试是一项具有挑战性的任务。多线程应用程序采用的互斥、同步技术使得调试时查看程序运行状态变得困难,线程的时序和多个线程间的交叉执行增加了程序调试的复杂性。采用适用于调试多线程应用程序的通用技术,并结合Visual Studio调试器提供的工具可以有效调试多线程应用程序。     

Modular Checkpointing for Atomicity

Transient faults that arise in large-scale software systems can often be repaired by re-executing the code in which they occur. Ascribing a meaningful semantics for safe re-execution in multi-threaded code is not obvious, however. For a thread to correctly re-execute a region of code, it must ensure that all other threads which have witnessed its unwanted effects within that region are also reverted to a meaningful earlier state. If not done properly, data inconsistencies and other undesirable behavior may result. However, automatically determining what constitutes a consistent global checkpoint is not straightforward since thread interactions are a dynamic property of the program.In this paper, we present a safe and efficient checkpointing mechanism for Concurrent ML (CML) that can be used to recover from transient faults. We introduce a new linguistic abstraction called stabilizers that permits the specification of per-thread monitors and the restoration of globally consistent checkpoints. Global states are computed through lightweight monitoring of communication events among threads (e.g. message-passing operations or updates to shared variables). Our checkpointing abstraction provides atomicity and isolation guarantees during state restoration ensuring restored global states are safe.Our experimental results on several realistic, multithreaded, server-style CML applications, including a web server and a windowing toolkit, show that the overheads to use stabilizers are small, and lead us to conclude that they are a viable mechanism for defining safe checkpoints in concurrent functional programs. Our experiments conclude with a case study illustrating how to build open nested transactions from our checkpointing mechanism.     

基于长并行距离优先的确定性多线程调度

随着多核技术的不断发展,多线程技术更加广泛地应用于计算机软件中.但由于执行的不确定性,多线程程序的排错和调试存在着很大的困难.确定性多线程系统可以使多线程程序以确定的方式执行,即多次执行同一个多线程程序的顺序和结果是相同的,这可以大大简化多线程程序的排错和调试.但是,确定性多线程系统会导致多线程程序性能的下降.本文提出一种基于长并行距离优先的确定性多线程调度算法,优先执行并行距离长的线程,减少线程总体等待时间,从而提高多线程程序的效率.实验结果表明,本文方法可以使多线程程序的性能提升10%,并且具有很好的可扩展性.     

Automatically Partitioning Threads for Multithreaded Architectures

There is an enormous amount of parallelism exposed to fine-grain multithreaded architectures to cover latencies. It is a demanding task for a multithreading programmer to manage such a degree of parallelism by hand. To use multithreaded architectures efficiently it is essential to have compiler support for automatically partitioning programs into threads. This paper solves a fundamental problem in compiling for multithreaded architectures, automatically partitioning a program into threads. The focus of such partitioning is to overlap the remote communication latency and minimize the total execution time. We first formulate the partitioning problem based on a multithreaded execution cost model. Then, we prove such a formulation is NP-hard. Therefore, we propose two heuristic thread-partitioning methods to solve this problem in practice. The advanced partitioning algorithm is a novel extension of list scheduling, and it takes advantage of the cost model to generate near-optimum partitioning results. The remote-path-based partitioning algorithm is a simplified version of the advanced one but it is easy for compiler implementation. The two partitioning algorithms were implemented respectively in a thread partitioning testbed and a research EARTH-C compiler. The experimental results show that both partitioning algorithms are effective to generate efficient threaded code, and code generated by the compiler is comparable to hand-written code.     

Contextual debugging and analysis of multithreaded applications

Multithreaded programs are especially difficult to test and debug. The aim of the paper is to present a new concept of multithreaded program analysis and debugging based on contextual visualisation of the program components that influence thread execution. For this purpose, a dedicated software package called MTV (multithreading viewer) has been designed and implemented. It performs above the run-time library level, and hence only a programmer's view of multiple threads of control execution may be analyzed. The paper presents tested program code instrumentation, communication and synchronization between the instrumented program and MTV. Next, a general concept of contextual visualisation of multithreaded programs has been elaborated. A scheme of the MTV cooperation with the monitored program is discussed. The user interface has been described. A representation of the multithreaded program state has been shown, and the capability of MTV for certain classes of error recognition has been specified and illustrated by a few examples. These examples have been not intended to be exhaustive, but they rather indicate the opportunities to exploit MTV for analysis of complex applications. Short evaluation of the proposed contextual visualisation techniques with application to multithreaded program analysis concludes the paper. © 1997 by John Wiley & Sons, Ltd.