Data race detection using sequential program analysis

Details Data race detection using sequential program analysis Data race detection using sequential program analysis

2008-01-01

2008-01-01

Zhen, Wei (Department: 2191)

Data processing: software development, installation, and managem

Software program development tool

Testing or debugging

Reexamination Certificate

active

07316005

ABSTRACT:
A concurrent program is analyzed for the presence of data races by the creation of a sequential program from the concurrent program. The sequential program contains assertions which can be verified by a sequential program analysis tool, and which, when violated, indicate the presence of a data race. The sequential program emulates multiple executions of the concurrent program by nondeterministically scheduling asynchronous threads of the concurrent program on a single runtime stack and nondeterministically removing the currently-executing thread from the stack before instructions of the program. Checking functions are used to provide assertions for data races, along with a global access variable, which indicates if a variable being analyzed for data races is currently being accessed by any threads.

REFERENCES:
patent: 6289360 (2001-09-01), Kolodner et al.
patent: 6343371 (2002-01-01), Flanagan et al.
patent: 6393440 (2002-05-01), Salant et al.
patent: 6405326 (2002-06-01), Azagury et al.
patent: 6671707 (2003-12-01), Hudson et al.
patent: 6779135 (2004-08-01), Ur et al.
patent: 6817009 (2004-11-01), Flanagan et al.
patent: 6826752 (2004-11-01), Thornley et al.
patent: 7028119 (2006-04-01), Hue
patent: 2002/0120428 (2002-08-01), Christiaens
patent: 2003/0131283 (2003-07-01), Ur et al.
patent: 2004/0123185 (2004-06-01), Pierce et al.
patent: 2005/0283781 (2005-12-01), Karp et al.
Vhsnftsdrkhst Noyspsyi, et al., “Ownership Types for Safe Programming: Preventing Data Races and Deadlocks” Nov. 2002, ACM Press, vol. 37 Issue 11, pp. 211-230.
Stefan Savage, et al., “Eraser: A Dynamic Data Race Detector for Multithreaded Programs”, Nov. 1997, ACM Press vol. 15, Issue 4, pp. 391-411.
Eli Pozniansky, et al., “Efficient On-the-Fly Data Race Detection in Multithreaded C++ Programs”, Jun. 2003, ACM Press, vol. 38, Issue 10, pp. 179-190.
Ball et al., “The SLAM project: debugging system software via static analysis.”Proceedings of the 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages(POPL '02), ACM Press, 2002, 3 pages.
Bouajjani et al., “A generic approach to the static analysis of concurrent programs with procedures.”Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages(POPL '03), ACM Press, 2003, 12 pages.
Bush et al., “A static analyzer for finding dynamic programming errors.” Software-Practice and Experience, 30(7):775-802, Jun. 2000.
Corbett et al., “Bandera: extracting finite-state models from Java source code.”International Conference on Software Engineering, 2000, pp. 439-448.
Das et al., “ESP: Path-sensitive program verification in polynomial time.”Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation(PLDI'02), ACM Press, 2002, 12 pages.
Das, “Unification-based pointer analysis with directional assignments.”Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation(PLDI'00), ACM Press, 2000, pp. 35-46.
Engler et al., “Checking system rules using system-specific, programmer-written compiler extensions.”Proceedings of the 4th Symposium on Operating Systems Design and Implementation(OSDI'00), Usenix Association, 2000, 16 pages.
Flanagan et al., “Thread-modular model checking.”Proceedings of the SPIN Workshop on Software Verification, 2003, 15 pages.
Havelund et al., Model checking Java programs using Java PathFinder.Software Tools for Technology Transfer(STTT), 2(4):72-84, 2000.
Henzinger et al., “Thread-modular abstraction refinement.”CAV 2003: Computer Aided Verification, 2003, 13 pages.
Henzinger et al., “Lazy abstraction.”Proceedings of the 29thACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages(POPL '02), ACM Press, 2002, 13 pages.
Holzmann, “The Model Checker SPIN.”IEEE Transactions on Software Engineering, 23(5):279-295, May 1997.
Reps et al., “Precise interprocedural dataflow analysis via graph reachability.”Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ACM, 1995, pp. 49-61.
Robby et al., “Bogor: an extensible and highly-modular software model checking framework.”FSE 2003: Foundations of Software Engineering, 2003, 10 pages.
Sharir et al., “Two approaches to interprocedural data flow analysis.”Program Flow Analysis: Theory and Applications, Prentice-Hall, 1981, pp. 189-233.

Affiliated with

Also associated with

Rating

Data race detection using sequential program analysis does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data race detection using sequential program analysis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data race detection using sequential program analysis will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2764056