TY - GEN
T1 - Checking race freedom via linear programming
AU - Terauchi, Tachio
PY - 2008
Y1 - 2008
N2 - We present a new static analysis for race freedom and race detection. The analysis checks race freedom by reducing the problem to (rational) linear programming. Unlike conventional static analyses for race freedom or race detection, our analysis avoids explicit computation of locksets and lock linearity/must-aliasness. Our analysis can handle a variety of synchronization idioms that more conventional approaches often have difficulties with, such as thread joining, semaphores, and signals. We achieve efficiency by utilizing modern linear programming solvers that can quickly solve large linear programming instances. This paper reports on the formal properties of the analysis and the experience with applying an implementation to real world C programs. copyright
AB - We present a new static analysis for race freedom and race detection. The analysis checks race freedom by reducing the problem to (rational) linear programming. Unlike conventional static analyses for race freedom or race detection, our analysis avoids explicit computation of locksets and lock linearity/must-aliasness. Our analysis can handle a variety of synchronization idioms that more conventional approaches often have difficulties with, such as thread joining, semaphores, and signals. We achieve efficiency by utilizing modern linear programming solvers that can quickly solve large linear programming instances. This paper reports on the formal properties of the analysis and the experience with applying an implementation to real world C programs. copyright
KW - Fractional capabilities
KW - Linear programming
UR - http://www.scopus.com/inward/record.url?scp=57349154306&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=57349154306&partnerID=8YFLogxK
U2 - 10.1145/1375581.1375583
DO - 10.1145/1375581.1375583
M3 - Conference contribution
AN - SCOPUS:57349154306
SN - 9781595938602
T3 - Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)
SP - 1
EP - 10
BT - PLDI'08
T2 - 2008 ACM SIGPLAN Conference on Programming Language Design and Implementation 2008, PLDI'08
Y2 - 7 June 2007 through 13 June 2007
ER -