Dynamic data flow analysis for Java programs

A large portion of high-level computer programs consists of data declaration. Thus, an increased focus on testing the data flow aspects of programs should be considered. In this paper, we consider testing the data flow in Java programs dynamically. Data flow analysis has been applied for testing procedural and some object-oriented programs. We have extended the dynamic data flow analysis technique to test Java programs and show how it can be applied to detect data flow anomalies.     

并发Java程序同步操作的有效删除

同步操作是并发Java程序非常大的一部分开销.在现有程序分析方法的基础上,提出了一种精确而有效的冗余同步操作的静态删除方法.该方法分为基本处理和线程间时序分析两个阶段,充分考虑了控制流结构和线程交互时序对同步删除的影响.构造了一个Java编译器JTool,并在其上实现了同步删除算法.对于确定的单线程程序,同步删除率达到100%;对于多线程程序,同步删除率高于现有的分析工具.     

Anomaly Detection in Concurrent Software by Static Data Flow Analysis

Algorithms are presented for detecting errors and anomalies in programs which use synchronization constructs to implement concurrency. The algorithms employ data flow analysis techniques. First used in compiler object code optimization, the techniques have more recently been used in the detection of variable usage errors in dngle process programs. By adapting these existing algorithms, the sane classes of variable usage errors can be detected in concurrent process programs. Important classes of errors unique to concurrent process programs are also described, and algorithms for their detection are presented.     

一个用于Java程序可达性测试的改进方案

Java程序的并发性使它比串行程序更难测试,而可达性测试是一种有效的并发程序测试方法。首先比较了现有的Java程序可达性测试技术,进而提出了一种融合的改进方案以提高同步序列集的生成效率。然后指出新方案已覆盖了用伯恩斯坦条件裁减同步序列集的功能。最后详述如何通过扫描源程序来自动获取同步事件的时序约束关系,进而减少不可行的同步序列,并介绍了相应的实现算法和数据结构。     

Java中的并发机制的研究与实现

开发并发程序并非是一件容易的事情。随着程序设计的日益庞大和复杂,怎样开发出高性能的并发程序变得越来越重要。在分析了Java的并发机制和同步机制的基础上,给出了一些在开发Java并发程序中防止死锁的策略和方法,这些方法为并发程序的设计带来了方便。     

Analysis and testing of programs with exception handling constructs

Analysis techniques, such as control flow, data flow, and control dependence, are used for a variety of software engineering tasks, including structural and regression testing, dynamic execution profiling, static and dynamic slicing, and program understanding. To be applicable to programs in languages such as Java and C++, these analysis techniques must account for the effects of exception occurrences and exception handling constructs; failure to do so can cause the analysis techniques to compute incorrect results and, thus, limit the usefulness of the applications that use them. This paper discusses the effects of exception handling constructs on several analysis techniques. The paper presents techniques to construct representations for programs with explicit exception occurrences-exceptions that are raised explicitly through throw statements-and exception handling constructs. The paper presents algorithms that use these representations to perform the desired analyses. The paper also discusses several software engineering applications that use these analyses. Finally, the paper describes empirical results pertaining to the occurrence of exception handling constructs in Java programs and their effect on some analysis tasks     

一种并发程序可测试性分析框架

软件可测试性是对测试软件难易程度的预测，在测试、度量等许多领域中得到了广泛应用．由于并发程序执行的不确定性，其可测试性分析尚有很多难点有待解决．该文提出了一种并发程序可测试性分析框架．在充分分析程序内部数据流、控制流以及并发和同步对数据流和控制流影响的基础上，从单个并发单元、并发因素、共享变量因素及通信关系4个方面对并发程序的可测试性进行了分析，为综合度量并发程序的可测试性提供了依据．     

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.     

Using atomic await commands to develop concurrent programs in Java

Systematic techniques for dealing with concurrency can be very helpful in concurrent programming. In his concurrent programming text, Andrews [2] describes a technique for developing concurrent programs based on first developing solutions using course-grained atomic commands and atomic await primitives (which are usually not available in real programming environments), then systematically transforming the solution to an implementation that uses available synchronization primitives. Transformations are known for semaphores, conditional critical regions, and monitors. In this paper, transformations are given for the synchronization constructs provided by the Java programming language [1]. Familiarity with the basic facilities to support concurrency provided by Java is assumed.     

基于Java多线程的并发机制的研究和实现

针对高可靠性、高质量的Java并行多任务程序设计,分析了Java多线程机制的原理及其实现技术,研究了程序并发过程中的同步机制和交互通信机制,比较了基于操作系统级和基于Java多线程级并发机制的实现结构,总结了并发程序中死锁预防的一些编程规则和策略。所构造的一个具有完全意义上的并发同步的框架实例有一定的实用价值。     

Model-checking multi-threaded distributed Java programs

State-space exploration is a powerful technique for verification of concurrent software systems. Applying it to software systems written in standard programming languages requires powerful abstractions (of data) and reductions (of atomicity), which focus on simplifying the data and control, respectively, by aggregation. We propose a reduction that exploits a common pattern of synchronization, namely, the use of locks to protect shared data structures. This pattern of synchronization is particularly common in concurrent Java programs, because Java provides built-in locks. We describe the design of a new tool for state-less state-space exploration of Java programs that incorporates this reduction. We also describe an implementation of the reduction in Java PathFinder, a more traditional state-space exploration tool for Java programs. Published online: 2 October 2002 RID="*" ID="*"Present address: Computer Science Dept., SUNY at Stony Brook, Stony Brook, NY 11794-4400, USA. The author gratefully acknowledges the support of ONR under Grants N00014-99-1-0358 and N00014-01-1-0109 and the support of NSF under Grant CCR-9876058.     

Distributed reachability testing of concurrent programs

Reachability testing is an approach to verifying concurrent programs. During reachability testing, every partially ordered synchronization sequence of a program with a given input is exercised exactly once. In this paper, we present the design and implementation of a distributed reachability testing algorithm for a cluster of workstations. This algorithm allows different test sequences to be exercised concurrently by different workstations without any synchronization, and without any duplication of sequences among workstations. Dynamic load balancing is performed using a work‐stealing scheme. A novel aspect of this scheme is that work‐stealing requests progress in rounds. This round‐based structure identifies overloaded workstations to target for work stealing. Empirical studies show good speedup for four benchmark Java programs and one Lotos specification. Copyright © 2010 John Wiley & Sons, Ltd.     

Java并发机制研究

针对高质量Java多线程并发程序设计，结合实例分析研究了Java多线程同步机制、通信机制以及并发机制的扩展，给出了防止死锁现象的编程策略，有助于解决实际编程中的并发问题。     

并发Java程序动态分析及重演技术研究

Java语言在并发程序方面的广泛应用对软件测试提出了新的挑战。众所周知,由于并发程序的不确定性,使得并发程序的设计、开发、调试和测试都非常困难。文章介绍了Safepro／Java中的多线程测试技术,通过对Java源程序进行适当的修改并且保持语义不变,跟踪并发Java程序的运行过程,收集有关数据并对数据进行分析,最终控制并发Java程序的重演。     

一种并发程序依赖性分析方法

并发程序的依赖性分析是并发程序分析，理解，调试，测试和维护的重要手段，由于并发程序执行的不确定性，目前，尚有很多难点有待解决，针对Ada任务机制，首先提出了一种简洁，有效的并发程序表示方法－并发程序流图，然后讨论了由任务间同步引起的同步依赖和由访问共享变量引起的任务数据依赖，建立了并发程序依赖图，并在此基础上给出了一种有效的并发程序依赖性分析算法，得到一个比较精确的依赖性，较好地解决了并发程序依赖关系不可传递性问题。     

An extensive empirical study on C++ concurrency constructs

ContextNowadays concurrent programming is in large demand. The inherent support for concurrency is therefore increasingly important in programming languages. As for C++, an abundance of standard concurrency constructs have been supported since C++11. However, to date there is little work investigating how these constructs are actually used in developing real software.ObjectiveIn this paper, we perform an extensive empirical study to investigate the actual adoption of C++ concurrency constructs in open-source applications, with the goal to provide useful information for language designers and practitioners to improve the design and use of concurrency constructs.MethodWe first conduct a survey to understand the developers’ perception of concurrency constructs. Then, we analyze 492 open-source concurrent applications, comprising 131 million lines of C++ code, to collect the data of the practical adoption of concurrency constructs. Finally, we perform statistical analysis on the collected data and get the quantitative analysis results.ResultsUsing the experimental data, we uncover many interesting findings with respect to the usage of concurrency constructs, the management of synchronization, the relationship between standard concurrency constructs and third-party concurrency constructs, and the difference of applications in using concurrency constructs. For example, we find that: (1) thread-based constructs are significantly more often used to write concurrent programs than atomics-based constructs and task-based constructs; (2) lock-based constructs are significantly more often used to manage synchronization than lock-free constructs and blocking constructs; (3) developers in most projects do not move from third-party concurrency constructs to standard concurrency constructs; and (4) small-size applications introduce concurrency constructs more intensively and more quickly than medium-size applications and large-size applications.ConclusionsThis is the first extensive empirical study on C++ concurrency constructs. The results of this paper should be helpful for designing, teaching, and using C++ concurrency constructs.     

Data mining for defects in multicore applications: an entropy‐based call‐graph technique

Multicore computers are ubiquitous. Expert developers as well as developers with little experience in parallelism are now asked to create multithreaded software to exploit parallelism in mainstream shared‐memory hardware. However, finding and fixing parallel programming errors is a complex and arduous task. Programmers thus rely on tools such as race detectors that typically focus on reporting errors due to incorrect usage of synchronization constructs or due to missing synchronization. This arsenal of debugging techniques, however, is incomplete. This article presents a new perspective and addresses a largely unexplored direction of defect localization where a wrong usage of nonparallel programming constructs might cause wrong parallel application behavior. In particular, we make a contribution by showing how to use data‐mining techniques to locate defects in multithreaded shared‐memory programs. Our technique analyzes execution anomalies in a condensed representation of the dynamic call graphs of a multithreaded object‐oriented application and identifies methods that contain a defect. Compared with race detectors that concentrate on finding incorrect synchronization, our method is able to reveal a wider range of defects that affect the control flow of a parallel program. Results from controlled experiments show that our data‐mining approach finds not only race conditions in different types of multicore applications but also other errors that cause incorrect parallel program behavior. Data‐mining techniques offer a fruitful new ground for parallel program debugging, and we also discuss long‐term directions for this interesting field. Copyright © 2012 John Wiley & Sons, Ltd.     

基于全同步对覆盖的线程调度序列生成方法

针对多线程并发程序生成覆盖同步语句的线程调度序列(TSS)效率低问题,提出了一种基于全同步对覆盖(APSC)准则的TSS生成(TGBA)方法。首先,对并发程序中的同步语句,定义了同步对及APSC;然后,给出了一个同步对-线程关联图(SPTG)构建方法;在此基础上,生成满足APSC的TSS;最后,使用JPF检测工具,对4个Java类库并发程序进行了TSS生成实验,并与常用的默认线程调度(DS)、抢占式线程调度(PS)和交叉线程调度(CS)序列生成方法在生成效率方面进行了对比分析。实验结果表明,与DS、CS方法相比,TGBA方法生成的TSS能够覆盖全部同步对;当满足APSC时,与PS方法相比,TGBA方法测试生成所需要的状态数、迁移数至少减少了19889和44352,并且生成效率平均提升了1.95倍,因此TGBA方法能够降低状态空间的规模开销,提高TSS的生成效率。