检索结果-内蒙古大学图书馆

SRD: Static data race detection for concurrent programs

International Journal of Performability Engineering 2018年第11期14卷 2683-2691页

作者： Zhang, Yang Liang, Yanan Zhang, Dongwen School of Information Science and Technology Hebei University of Science and Technology Shijiazhuang050000 China

Data race probably occurs when many threads concurrently access the same memory location and at least one is a write thread. Data race detection suffers from false negatives and false positives. How to detect data race and avoid false negatives and false positives has become a hot topic. This paper proposes a static data race detection methodology to eliminate false negatives and false positives. We use Soot to conduct intra-thread and inter-thread analysis. Our data race detection focuses on variable access events that are collected from call graphs. Several program analysis technologies, such as alias variable analysis, alias lock analysis, happens-before analysis, constraint graph, and slicing analysis, are used to improve the coverage and precision of the detection results. In the experimentation, several benchmarks, such as raytracer, sor, and mergesort, have been selected to evaluate our methodology. Experimental results show that SRD can not only eliminate fake races but also identify potential races. Furthermore, SRD can detect more positive races than the existing tool RVPredict. © 2018 Totem Publisher, Inc. All rights reserved.

关键词： Alias analysis concurrent program Data race Happens-before Intra/inter-thread analysis

来源：评论

学校读者我要写书评

暂无评论

CONTEXT-AWARE DEBUGGING FOR concurrent programS

CONTEXT-AWARE DEBUGGING FOR CONCURRENT PROGRAMS

引用

作者： Justin Chu University of Kentucky

学位级别：硕士

Concurrency faults are difficult to reproduce and localize because they usually occur under specific inputs and thread interleavings. Most existing fault localization techniques focus on sequential programs, but fail to identify faulty memory access patterns across threads, which are usually the root causes of concurrency faults. Moreover, existing techniques for sequential programs cannot be adapted to identify faulty paths in concurrent programs. While concurrency fault localization techniques have been proposed to analyze passing and failing executions and identify faulty ac- cess patterns, they primarily focus on using statistical analysis. We present a novel approach to fault localization using feature selection techniques from machine learn- ing. Our insight is that the concurrency access patterns obtained from a large volume of coverage data generally constitute high dimensional data sets, yet existing statis- tical analysis techniques for fault localization are usually applied to low dimensional data sets. Each additional failing or passing run can provide more diverse informa- tion, which can help localize faulty concurrency access patterns in code. The patterns with maximum feature diversity information can point to the most suspicious pattern. We then apply data mining technique and identify the interleaving patterns that are occurred most frequently and provide the possible faulty paths. We also evaluate the effectiveness of fault localization using test suites generated from different test adequacy criteria. We have evaluated Cadeco on 10 real-world multi-threaded Java applications. Results indicate that Cadeco outperforms state-of-the-art approaches for localizing concurrency faults.

关键词： concurrent program Fault Localization Debugging Machine Learning Data Mining Empirical Study

来源：评论

学校读者我要写书评

暂无评论

DDS: Deadlock Detector and Solver 29

DDS: Deadlock Detector and Solver

引用

29th IEEE International Symposium on Software Reliability Engineering (ISSRE)

作者： Aldakheel, Eman Buy, Ugo Kaur, Simran Univ Illinois Dept Comp Sci Chicago IL 60607 USA Princess Nourah bint Abdulrahman Univ Dept Comp Sci Riyadh Saudi Arabia

ISBN: (纸本)9781538694435

Deadlock is among the most complex problems that affect the reliability of concurrent programs such as real-time operating systems. Deadlocks occur when multiple processes or threads are mutually blocked while holding a resource required by another process or thread. Current deadlock detection methods are typically based on timeout mechanisms. Recovery from deadlocks frequently involves the rollback of computations, resulting in significant delays. Here we discuss Deadlock Detector and Solver (DDS), which can rapidly detect and resolve circular deadlocks in Java programs. The DDS uses a supervisory controller, which monitors program execution and automatically detects the deadlocks resulting from the hold-and-wait cycles in Java locks. When a deadlock is detected, the DDS uses a preemptive strategy to break it. We use static analysis to assist DDS when selecting the Java thread to be preempted. Our empirical results show that the DDS can monitor program execution and resolve deadlocks without significant runtime overhead.

关键词： deadlocks concurrent program supervisory control deadlock detection multithreaded programs

来源：评论

学校读者我要写书评

暂无评论

Synthesis of large dynamic concurrent programs from dynamic specifications

引用

FORMAL METHODS IN SYSTEM DESIGN 2016年第1-2期48卷 94-147页

作者： Attie, Paul C. Amer Univ Beirut Dept Comp Sci POB 11-0236 Beirut 11072020 Lebanon

We present two methods for synthesizing large concurrent programs from temporal logic specifications. The first method deals with finite-state concurrent programs that are static, i.e., the set of processes is fixed. It produces an infinite family of static finite-state concurrent programs. The second method deals with dynamic concurrent programs, i.e., new processes can be created and added at run-time. It produces a single dynamic concurrent program. A dynamic concurrent program may be viewed as a limiting case of an infinite family of static programs, and so the second method may be viewed as generalizing the first. Our methods are algorithmically efficient, with complexity polynomial in the number of component processes (of the program) that are "alive" at any time. We do not explicitly construct the automata-theoretic product of all processes that are alive, thereby avoiding state explosion. Instead, for each interacting pair of processes, we construct (from a pair-specification) a pair-structure which embodies the interaction of the two processes. From each pair-structure, we synthesize a pair-programto coordinate the two processes. Our second method allows pair-programs to be added dynamically at run-time. They are then "composed conjunctively" with the currently alive pair-programs to "re-synthesize" the program. We can thus add new behaviors, which result in new properties being satisfied, at run-time. This "incremental composition" step has complexity independent of the total number of processes;it only requires the mechanical analysis of the two processes in the pair-program, and their immediate neighbors, i.e., the other processes which they interact directly with. Thus, any state-explosion incurred is explosion in the product of only two processes. We establish "large model" theorems which show that the synthesized global program inherits correctness properties from the pair-programs.

关键词： concurrent program Dynamic process creation Formal specification Model checking Synthesis Temporal logic

来源：评论

学校读者我要写书评

暂无评论

A Comparative Study on Test Case Generation of concurrent programs

引用

World Journal of Engineering and Technology 2016年第2期4卷 273-280页

作者： Bidush Kumar Sahoo Mitrabinda Ray Department of Computer Science and Engineering I.T.E.R. Siksha “O” Anusandhan University Bhubaneshwar India

This paper deals with a comparative study on testing of concurrent programs based on different techniques. The various challenges in testing concurrent programming are: defining test coverage criteria based on control flow, generating control flow graph of nondeterministic programs, investigating the applicability of sequential testing criteria to parallel program testing etc. For solving these issues, some existing techniques are discussed in this study. Various researchers use an intermediate graph called Event Inter Actions Graph (EIAG) to solve the problem of generating the control flow graph of nondeterministic programs. Some researches propose an intermediate graph called Interaction Sequence Testing Criteria (ISTC) approach based on sequence of interactions to solve the problem of test coverage criteria based on control and data flow. Another method to solve the problem of generating test coverage based on control flow graph of nondeterministic programs is constraint based approach. It needs constrained elements to generate test case which includes structural element and constraint. The selection of good test cases has been addressed by test data generation technique. The technique of concurrent path analysis approach is used to solve the problem of applicability of sequential testing criteria to parallel program testing. It reduces the number of combined concurrent test paths. The sequential test paths are combined to form concurrent test path. The Integration and System Test Automation (ISTA) approach is used to solve the problem of applicability of sequential testing criteria to parallel program testing. It is used for automated test case generation and execution by using high-level Petri net is a finite state test model.

关键词： concurrent program EIAG Dead Statement Control Flow Graph Nondeterministic program

来源：评论

学校读者我要写书评

暂无评论

Scheduling Parallel Soft Real-Time VM in Dynamic Workloads

引用

INTELLIGENT AUTOMATION AND SOFT COMPUTING 2016年第2期22卷 281-287页

作者： Ding, Xiaobo Ma, Zhong Dai, Xinfa Harbin Engn Univ Coll Comp Sci & Technol Harbin 150001 Heilongjiang Peoples R China China Three Gorges Univ Coll Comp & Informat Technol Yichang 443002 Hubei Peoples R China Wuhan Digital Engn Res Inst Res & Dev Dept Wuhan 430074 Hubei Peoples R China

Virtual machine ( VM) is widely used in many fields now. The CPUs of VM, different from those of physical machines, cannot be ensured to be on line at the same time, and the number of VMs will affect the performance of the parallel VM. So concurrent programs working on the VM is not efficient, and the soft real-time concurrent applications would be invalid especially in the worst case. Based on Xen Credit scheduler, this paper analyzes the factors affecting the performance of Parallel Soft Real-Time task VM ( PSRTVM) and raises a Parallel Soft Real-Time Scheduling Algorithm ( PSRTSA), which could ensure the performance of PSRTVM in dynamic workloads. In PSRTSA, the synchronized scheduling is proposed to meet the parallel workloads, and the opportunity of synchronized scheduling is set to meet the delay of the worst case. The percentage pre-allocation of CPU time is used to ensure the resource of PSRTVM in dynamic workloads of system. The evaluation shows the improvement of the PSRTSA compared to the default Credit scheduler and RT-Credit scheduler based on scheduling synchronization.

关键词： concurrent program soft real-time VM synchronism scheduling

来源：评论

学校读者我要写书评

暂无评论

Detecting harmful data races through parallel verification

引用

JOURNAL OF SUPERCOMPUTING 2015年第8期71卷 2922-2943页

作者： Wu, Zhendong Lu, Kai Wang, Xiaoping Zhou, Xu Chen, Chen Natl Univ Def Technol Sci & Technol Parallel & Distributed Proc Lab Changsha Hunan Peoples R China Natl Univ Def Technol Coll Comp Changsha Hunan Peoples R China

Data races widely exist in concurrent programs and the harmful races have caused severe failures. To detect the harmful races, previous tools verify all the races, identifying the harmful ones. However, efficiency is affected when there are a large number of races needed to be verified. The multicore technology trend worsens this problem. Unlike previous work, to detect the harmful races, we try to improve the efficiency through parallel verification. We use imprecise race detection to find the races, including benign races and harmful races. The races are divided into many parts, and each part is sent to one machine for verification. On each machine, the races are verified dynamically, identifying the harmful races that would lead to program failures. To our knowledge, this is the first work that parallelizes race verification to improve the efficiency. We have experimented on a number of real-world concurrent programs and all the known harmful races in known benchmarks are detected. Additionally, our tool could scale well as the number of machines increases, and the speedup can also be increased linearly with the number of machines. Comparing with many previous tools, our work imposes lower runtime overhead.

关键词： Harmful data race concurrent program Dynamic verification Race detection

来源：评论

学校读者我要写书评

暂无评论

A formal semantics for debugging synchronous message passing-based concurrent programs

引用

Science China(Information Sciences) 2014年第12期57卷 198-215页

作者： LI He LUO Jie LI Wei State Key Laboratory of Software Development Environment School of Computer Science and EngineeringBeihang University

In this paper,we propose a semantic framework to debug synchronous message passing-based concurrent programs,which are increasingly useful as parallel computing and distributed systems become more and more *** first design a concurrent programming language model to uniformly represent existing concurrent programming *** to sequential programming languages,this model contains communication statements,i.e.,sending and receiving statements,and a concurrent structure to represent communication and *** then propose a debugging process consisting of a tracing and a locating *** tracing procedure re-executes a program with a failed test case and uses specially designed data structures to collect useful execution information for locating *** provide for the tracing procedure a structural operational semantics to represent synchronous communication and *** locating procedure backward locates the ill-designed statement by using information obtained in the tracing procedure,generates a fix equation,and tries to fix the bug by solving the fix *** also propose a structural operational semantics for the locating *** supply two examples to test our proposed operational semantics.

关键词： debugging synchronous message passing concurrent program operational semantics

来源：评论

学校读者我要写书评

暂无评论

Are concurrency coverage metrics effective for testing: a comprehensive empirical investigation

引用

SOFTWARE TESTING VERIFICATION & RELIABILITY 2015年第4期25卷 334-370页

作者： Hong, Shin Staats, Matt Ahn, Jaemin Kim, Moonzoo Rothermel, Gregg Korea Adv Inst Sci & Technol Dept Comp Sci Taejon 305701 South Korea Univ Luxembourg SnT Ctr Luxembourg Luxembourg Agcy Def Dev Taejon 300600 South Korea Univ Nebraska Dept Comp Sci Lincoln NE 68588 USA

Testing multithreaded programs is inherently challenging, as programs can exhibit numerous thread interactions. To help engineers test these programs cost-effectively, researchers have proposed concurrency coverage metrics. These metrics are intended to be used as predictors for testing effectiveness and provide targets for test generation. The effectiveness of these metrics, however, remains largely unexamined. In this work, we explore the impact of concurrency coverage metrics on testing effectiveness and examine the relationship between coverage, fault detection, and test suite size. We study eight existing concurrency coverage metrics and six new metrics formed by combining complementary metrics. Our results indicate that the metrics are moderate to strong predictors of testing effectiveness and effective at providing test generation targets. Nevertheless, metric effectiveness varies across programs, and even combinations of complementary metrics do not consistently provide effective testing. These results highlight the need for additional work on concurrency coverage metrics. Copyright (c) 2014 John Wiley & Sons, Ltd.

关键词： software testing test coverage metric concurrent program

来源：评论

学校读者我要写书评

暂无评论

Region-Based May-Happen-in-Parallel Analysis for C programs 44

Region-Based May-Happen-in-Parallel Analysis for C Programs

引用

44th Annual International Conference on Parallel Processing Workshops (ICPPW)

作者： Di, Peng Sui, Yulei Ye, Ding Xue, Jingling UNSW Australia Sch Comp Sci & Engn Kensington NSW Australia

ISBN: (纸本)9781467375887

The C programming language continues to play an essential role in the development of system software. May-Happen-in-Parallel (MHP) analysis is the basis of many other analyses and optimisations for concurrent programs. Existing MHP analyses that work well for programming languages such as X10 are often not effective for C (with Pthreads). This paper presents a new MHP algorithm for C that operates at the granularity of code regions rather than individual statements in a program. A flow-sensitive Happens-Before (HB) analysis is performed to account for fork-join semantics of Pthreads on an interprocedural thread-sensitive control flow graph representation of a program, enabling the HB relations among its statements to be discovered. All the statements that share the same HB properties are then grouped into one region. As a result, computing the MHP information for all pairs of statements in a program is reduced to one of inferring the HB relations from among its regions. We have implemented our algorithm in LLVM-3.5.0 and evaluated it using 14 programs from the SPLASH2 and PARSEC benchmark suites. Our preliminary results show that our approach is more precise than two existing MHP analyses yet computationally comparable with the fastest MHP analysis.

关键词： MHP May-Happen-in-Parallel concurrent program multi-threading static analysis

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：