高精度的大規模程序數據競爭檢測方法

隨著技術的不斷發展,軟件系統的非確定性（uncertainty）不斷增強,數據競爭是并發系統這一類典型的非確定性軟件系統中常見的缺陷.盡管數據競爭靜態檢測近年來取得了巨大進展,但其面臨的重要問題仍然存在.先前的靜態技術要么以分析精度為代價達到高擴展性,要么由于高精度分析而導致可擴展性問題.提出一種解決上述矛盾的分段分析方法——GUARD.它首先基于程序值流進行輕量級上下文敏感的數據訪問分析,以識別出候選的數據競爭子路徑而非完整的程序路徑.接下來,進行可能并行執行（may-happen-in-parallel,即MHP）分析來確定程序中的兩個數據訪問操作是否可能會同時執行.MHP分析基于線程流圖（TFG）將線程信息進行編碼以便于高效地查詢各個子路徑之間的并發關系.最后,對于每條存在MHP數據訪問的子路徑,進行重量級路徑敏感分析以確定數據競爭路徑的可行性.針對12個開源項目的實驗評估顯示,GUARD能夠在1 870s內完成對130萬行代碼的工業規模項目的檢測,且平均誤報率為16.0%.此外,GUARD的分析速度更快,比現有的前沿技術平均快了6.08倍,并且顯著降低了誤報率.除此之外,GUARD在其中還發現了12個數據競爭漏洞.將它們全部報告給了開發者,其中8個已得到了確認. With the development of techniques, the uncertainty in software systems is continuously increasing. Data race is a typical bug in current programs, which is a classic type of uncertainty programs. Despite significant progress in recent years, the important problem of practical static race detection remains open. Previous static techniques either suffer from a high false positive rate due to the compromise of precision, or scalability issues caused by a highly precise analysis. This paper presents GUARD, a staged approach to resolve this paradox. First, it performs a lightweight context-sensitive data access analysis, based on the value flow of a program, to identify the candidate data race subpaths instead of the whole program paths. Second, may-happen-in-parallel (MHP) analysis is employedto identify whether two data accesses in a program may execute concurrently. This stage is scalable, due to the design of the thread flow graph (TFG), which encodes thread information to query MHP relationship of the subpaths. Finally, for each subpath whose two data accesses are MHP, the heavyweight path-sensitive analysis is appliedto verify the feasibility of the data races. The evaluation demonstrates that GUARD can finish checking industrial-sized projects, up to 1.3MLoC, in 1 870s with an average false positive rate of 16.0%. Moreover, GUARD is faster than the state-of-the-art techniques with the average speedup 6.08X and significantly fewer false positives. Besides, GUARD has found 12 new race bugs in real-world programs. All of them are reportedtothe developers and 8 of them have been confirmed. © Copyright 2021, Institute of Software, the Chinese Academy of Sciences. All rights reserved.