Precise slicing of interprocedural concurrent programs

Program slicing is an effective technique for analyzing concurrent programs. However, when a conventional closure-based slicing algorithmfor sequential programs is applied to a concurrent interprocedural program, the slice is usually imprecise owing to the intransitivity of interference dependence. Interference dependence arises when a statement uses a variable defined in another statement executed concurrently. In this study, we propose a global dependence analysis approach based on a program reachability graph, and construct a novel dependence graph calledmarking-statement dependence graph (MSDG), in which each vertex is a 2-tuple of program state and statement. In contrast to the conventional program dependence graph where the vertex is a statement, the dependence relation in MSDG is transitive. When traversing MSDG, a precise slice will be obtained. To enhance the slicing efficiency without loss of precision, our slicing algorithm adopts a hybrid strategy. The procedures containing interaction statements between threads are inlined and sliced by the slicing algorithm based on program reachability graphs while allowing other procedures to be sliced as sequential programs. We have implemented our algorithm and three other representative slicing algorithms, and conducted an empirical study on concurrent Java programs. The experimental results show that our algorithm computes more precise slices than the other algorithms. Using partial-order reduction techniques, which are effective for reducing the size of a program reachability graph without loss of precision, our algorithm is optimized, thereby improving its performance to some extent.     

Variable strength combinatorial testing of concurrent programs

Reachability testing is an important approach to testing concurrent programs. It generates and exercises synchronization sequences automatically and on-the-fly without saving any test history. Existing reachability testing can be classified into exhaustive and t-way testing. Exhaustive testing is impractical in many cases while t-way testing may decrease the capability of fault detection in some cases. In this paper, we present a variable strength reachability testing strategy, which adopts the dynamic framework of reachability testing and uses a variable strength combinatorial strategy. Different parameter groups are provided with different covering strength. Variable strength testing covers no t-way combinations but the necessary combinations of parameters having mutual interactions in a concurrent program. It is more reasonable than t-way testing because uniform interactions between parameters do not often exist in concurrent systems. We propose a merging algorithmthat implements the variable strength combinatorial testing strategy and conduct our experiment on several concurrent programs. The experimental results indicate that our variable strength reachability testing reaches a good tradeoff between the effectiveness and efficiency. It can keep the same capability of fault detection as exhaustive reachability testing while substantially reducing the number of synchronization sequences and decreasing the execution time in most cases.     

Incremental integration testing of concurrent programs

We present a method for selecting test sequences for concurrent programs from labeled transitions systems (LTS). A common approach to selecting test sequences from a set of LTSs is to derive a global LTS, called the reachability graph, and then force deterministic program executions according to paths selected from the graph. However, using a reachability graph for test path selection introduces a state explosion problem. To overcome this problem, a reduced graph can be generated using incremental reachability analysis, which consists of repeatedly generating a reachability graph for a subset of LTSs, reducing this graph, and using the reduced graph in place of the original LTSs. Unfortunately, existing incremental reachability analysis techniques generate reduced graphs with insufficient information for deterministic testing. We present an incremental approach to testing concurrent programs. Incremental testing consists of incremental reachability analysis for test path selection and deterministic testing for test execution. We define a new type of reachability graph for incremental analysis, called an annotated labeled transition system (ALTS). An ALTS is an LTS annotated with information necessary for deterministic testing. We propose practical coverage criteria for selecting tests paths from an ALTS and present an ALTS reduction algorithm. The results of several case studies are reported     

Composing Synchronization and Real-Time Constraints

There have been a number of publications illustrating the successes of object-oriented techniques in creating highly reusable software systems. Several concurrent languages have been proposed for specifying reusable synchronization specifications. Recently, a number of real-time object-oriented languages have been introduced for building object-oriented programs with real-time behavior. Composing and reusing object-oriented programs with both synchronization and real-time constraints has not been addressed adequately, although most real-time systems are concurrent. This paper analyzes the origins of the problems in composing and reusing synchronization and real-time specifications, first as separate concerns, and later as composed behavior. To overcome the so-called inheritance anomaly problems, this paper proposes modular and composable synchronization and real-time specification extensions to the object-oriented model. The applicability of the proposed mechanisms is illustrated through a number of examples.     

RGITL: A temporal logic framework for compositional reasoning about interleaved programs

This paper gives a self-contained presentation of the temporal logic Rely-Guarantee Interval Temporal Logic (RGITL). The logic is based on interval temporal logic (ITL) and higher-order logic. It extends ITL with explicit interleaved programs and recursive procedures. Deduction is based on the principles of symbolic execution and induction, known from the verification of sequential programs, which are transferred to a concurrent setting with temporal logic. We include an interleaving operator with compositional semantics. As a consequence, the calculus permits proving decomposition theorems which reduce reasoning about an interleaved program to reasoning about individual threads. A central instance of such theorems are rely-guarantee (RG) rules, which decompose global safety properties. We show how the correctness of such rules can be formally derived in the calculus. Decomposition theorems for other global properties are also derivable, as we show for the important progress property of lock-freedom. RGITL is implemented in the interactive verification environment KIV. It has been used to mechanize various proofs of concurrent algorithms, mainly in the area oflinearizable and lock-free algorithms.     

An application of structural modeling and automated reasoning to real-time systems design

This paper presents an application of structural modeling and automated reasoning as a software development environment for real-time systems. This application satisfies two major requirements for such an environment: (1) to synthesize an absolutely correct program and, (2) to increase software productivity. The real-time systems, which consist of concurrent programs, are described by a Prolog based concurrent object-oriented language, called MENDEL/87. As a typical concurrent program consists of two parts: functional and synchronization parts; the functional part in the reusable component to be registered in a library will be generated by a structural modeling through the use of structuring functions with respect to data flows. The synchronization part will be synthesized from temporal logic specifications by the use of an automated reasoning mechanism. This paper also describes the MENDELS ZONE implemented on a Prolog machine, which is the working base for the presented application method.     

Reachability testing of concurrent programs

One approach to testing concurrent programs, called reachability testing, generates synchronization sequences automatically and on-the-fly, without constructing any static models. In this paper, we present a general execution model for concurrent programs that allows reachability testing to be applied to several commonly used synchronization constructs. We also present a new method for performing reachability testing. This new method guarantees that every partially ordered synchronization sequence will be exercised exactly once without having to save any sequences that have already been exercised. We describe a prototype reachability testing tool called RichTest and report some empirical results, including a comparison between RichTest and a partial order reduction-based tool called VeriSoft. RichTest performed significantly better for the programs in our study.     

Reachability of Patterned Conditional Pushdown Systems

Conditional pushdown systems (CPDSs) extend pushdown systems by associating each transition rule with a regular language over the stack alphabet. The goal is to model program verification problems that need to examine the runtime call stack of programs. Examples include security property checking of programs with stack inspection, compatibility checking of HTML5 parser specifications, etc. Esparza et al. proved that the reachability problem of CPDSs is EXPTIME-complete, which prevents the existence of an algorithm tractable for all instances in general. Driven by the practical applications of CPDSs, we study the reachability of patterned CPDS (pCPDS) that is a practically important subclass of CPDS, in which each transition rule carries a regular expression obeying certain patterns. First, we present new saturation algorithms for solving state and configuration reachability of pCPDSs. The algorithms exhibit the exponential-time complexity in the size of atomic patterns in the worst case. Next, we show that the reachability of pCPDSs carrying simple patterns is solvable in fixed-parameter polynomial time and space. This answers the question on whether there exist tractable reachability analysis algorithms of CPDSs tailored for those practical instances that admit efficient solutions such as stack inspection without exception handling. We have evaluated the proposed approach, and our experiments show that the pattern-driven algorithm steadily scales on pCPDSs with simple patterns.

     

pyOpt: a Python-based object-oriented framework for nonlinear constrained optimization

We present pyOpt, an object-oriented framework for formulating and solving nonlinear constrained optimization problems in an efficient, reusable and portable manner. The framework uses object-oriented concepts, such as class inheritance and operator overloading, to maintain a distinct separation between the problem formulation and the optimization approach used to solve the problem. This creates a common interface in a flexible environment where both practitioners and developers alike can solve their optimization problems or develop and benchmark their own optimization algorithms. The framework is developed in the Python programming language, which allows for easy integration of optimization software programmed in Fortran, C, C+ +, and other languages. A variety of optimization algorithms are integrated in pyOpt and are accessible through the common interface. We solve a number of problems of increasing complexity to demonstrate how a given problem is formulated using this framework, and how the framework can be used to benchmark the various optimization algorithms.     

基于上下文定界的Fork/Join并行性的并发程序可达性分析

随着多核技术日益发展,并发程序通过引入Fork/Join并行性,将任务分解为更细粒度的子任务并行执行,从而充分利用多核处理器提供的计算性能。并发执行线程之间的交错可能产生隐匿的程序设计错误,因此有必要对此类并发程序的正确性进行分析。上下文定界分析方法是一种检测并发程序中隐匿错误的高效方法,计算线程有限次上下文切换内的可达状态,确定错误状态是否可达。针对Fork/Join并行性的并发程序的可达性分析思想如下:首先,动态并发程序被建模为可模拟线程Fork/Join操作的动态并发下推系统P;然后从P中提取模拟其k-定界执行的并发下推系统Pk。现有的上下文定界可达算法可解决提取后的并发下推系统的k-定界可达性问题。     

A combinatorial testing strategy for concurrent programs

One approach to testing concurrent programs is called reachability testing, which derives test sequences automatically and on‐the‐fly, without constructing a static model. Existing reachability testing algorithms are exhaustive in that they are intended to exercise all possible synchronization sequences of a concurrent program with a given input. In this paper, we present a new testing strategy, called t‐way reachability testing, that adopts the dynamic framework of reachability testing but selectively exercises a subset of synchronization sequences. The selection of the synchronization sequences is based on a combinatorial testing strategy called t‐way testing. We present an algorithm that implements t‐way reachability testing, and report the results of several case studies that were conducted to evaluate its effectiveness. The results indicate that t‐way reachability testing can substantially reduce the number of synchronization sequences exercised during reachability testing while still effectively detecting faults. Copyright © 2007 John Wiley & Sons, Ltd.     

面向方面程序的调用图生成算法

调用图(call graph)分析是进行程序分析、程序理解、软件测试和软件维护的重要基础.目前已提出的调用图生成算法多数是针对面向对象编程;而面向方面编程作为面向对象编程的扩展,还没有比较良好的调用图生成算法.为此,分析了既有的面向对象程序调用图生成算法,讨论了面向方面程序语言(AspectJ为例)的特殊语言元素及其对生成的调用图的影响,从而构筑了面向方面程序调用图的生成算法.     

基于基本并行进程的异步通信程序的验证方法

异步通讯程序是进程间通过异步消息通讯实现非阻塞并发的程序. 当前异步通讯程序的程序验证问题通常将其归约至向量加法系统及其扩展模型,因而复杂度很高,并缺乏高效工具. 基本并行进程作为向量加法系统的一个子类,其可达性的验证问题为NP完备.首先,本文改进了Osualdo等提出的为异步通讯程序建模的Actor通讯系统, 将其归约至基本并行进程. 然后,实现了基本并行进程的模型检测工具RABLE,实验结果表明,验证方法在异步通讯程序的一系列程序验证问题上具有比已有工具更高效的结果.     

Zero—a blend of static typing and dynamic metaprogramming

Zero is an experimental statically typed, fully object-oriented reflective programming language. Reflective features cover introspection as well as structural and behavioural reflection. The reflective facilities include safe method and class replacements and detailed modification of methods. These enable Zero programs to quickly accommodate to run-time requirements. Behavioural reflection is realised using handlers (hooks), which may be attached to all language constructs based on closures. Zero provides an efficient static typing system with run-time extensions. Methods are first class values and are represented as objects when such representation is required. By using such representation, Zero provides elegant use of statically typed higher-order methods.     

Structuring parallel algorithms in an MIMD,shared memory environment

This paper discusses the class of algorithms having global parallelism, i.e. those in which parallelism is introduced at the top of the program structure hierarchy. Such algorithms have performance advantages in a shared-memory. MIMD computational model. A programming environment consisting of FORTRAN, enhanced by some pre-processed macros, has been built to aid in writing programs for such algorithms for the Denelcor HEP multiprocessor. Applications of from tens to hundreds of FORTRAN statements have been written and tested in this environment. A few parallelism constructs suffice to yield understandable programs with a high degree of parallelism. The automatic generation of programs with global parallelism seems to be a promising possibility.     

Ada-I:支持保护对象继承的Ada95扩充语言

面向对象并发程序设计语言能够帮助程序员利用面向对象技术编写并发程序,从而获得面向对象技术给软件开发带来的种种好处.然而,由于继承异常现象的存在,影响了并发程序设计语言引入继承特性.Ada95语言是支持并发程序设计的面向对象语言之一,但并不支持保护对象的继承.Ada-I语言在Ada95语言的基础上进行扩充,从而支持保护对象的继承,并且避免了继承异常现象的出现.     

On using priced timed automata to achieve optimal scheduling

In this paper, we describe an approach for solving the general class of energy-optimal task graph scheduling problems using priced timed automata. We provide an efficient zone-based algorithm for minimum-cost reachability. Furthermore, we show how the simple structure of the linear programs encountered during symbolic minimum-cost reachability analysis of priced timed automata can be exploited in order to substantially improve the performance of the current algorithm. The idea is rooted in duality of linear programs and we show that each encountered linear program can be reduced to the dual problem of an instance of the min-cost flow problem. Experimental results using Uppaal show a 70–80 percent performance gain. We provide priced timed automata models for the scheduling problems and provide experimental results illustrating the potential competitiveness of our approach compared to existing approaches such as mixed integer linear programming.This research was conducted in part at Aalborg University, where the author was supported by a CISS Faculty Fellowship.

---

     

simpA: An agent-oriented approach for programming concurrent applications on top of Java

More and more aspects of concurrency and concurrent programming are becoming part of mainstream programming and software engineering, due to several factors such as the widespread availability of multi-core/parallel architectures and Internet-based systems. This leads to the extension of mainstream object-oriented programming languages and platforms-Java is a main example-with libraries providing fine-grained mechanisms and idioms to support concurrent programming, in particular for building efficient programs. Besides this fine-grained support, a main research goal in this context is to devise higher-level, coarse-grained abstractions that would help building concurrent programs, as pure object-oriented abstractions help building large component-based programs. To this end, in this paper we present simpA, a Java-based framework that provides programmers with agent-oriented abstractions on top of the basic OO layer, as a means to organize and structure concurrent applications. We first describe the application programming interface (API) and annotation framework provided to Java programmers for building simpA applications, and then we discuss the main features of the approach from a software engineering point of view, by showing some programming examples. Finally, we define an operational semantics formalizing the main aspects of this programming model.     

Formal derivation of rule-based programs

It is shown that a combination of specification and program refinement may be applied to deriving efficient concurrent rule-based programs. Specification refinement is used to generate an initial rule-based program that is refined into a program which is highly concurrent and efficient. This program derivation strategy is divided into two major tasks. The first task relies on specification refinement. Techniques similar to those employed in the derivation of UNITY programs are used to produce a correct rule-based program having a static knowledge base. The second task involves program refinement and is specific to the development of concurrent rule-based programs. It relies heavily on the availability of a computational model, such as Swarm, that has the ability to dynamically restructure the knowledge base. The ways in which a Swarm program can be translated to OPS5 specifically, given some restrictions, while maintaining the correctness criteria are discussed     

Reducing concurrent analysis under a context bound to sequential analysis

This paper addresses the analysis of concurrent programs with shared memory. Such an analysis is undecidable in the presence of multiple procedures. One approach used in recent work obtains decidability by providing only a partial guarantee of correctness: the approach bounds the number of context switches allowed in the concurrent program, and aims to prove safety, or find bugs, under the given bound. In this paper, we show how to obtain simple and efficient algorithms for the analysis of concurrent programs with a context bound. We give a general reduction from a concurrent program P, and a given context bound K, to a sequential program P _s ^K such that the analysis of P _s ^K can be used to prove properties about P. The reduction introduces symbolic constants and assume statements in P _s ^K . Thus, any sequential analysis that can deal with these two additions can be extended to handle concurrent programs as well, under a context bound. We give instances of the reduction for common program models used in model checking, such as Boolean programs, pushdown systems (PDSs), and symbolic PDSs. Supported by NSF under grants CCF-0540955, CCF-0524051, and CCF-0810053, and by IARPA under AFRL contract FA8750-06-C-0249. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of either NSF or IARPA. Supported by a Microsoft Research Fellowship.