{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T11:08:00Z","timestamp":1776942480839,"version":"3.51.4"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA1","license":[{"start":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T00:00:00Z","timestamp":1714348800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,4,29]]},"abstract":"<jats:p>Testing for data races in the Linux OS kernel is challenging because there is an exponentially large space of system calls and thread interleavings that can potentially lead to concurrent executions with races. In this work, we introduce a new approach for modeling execution trace feasibility and apply it to Linux OS Kernel race prediction. To address the fundamental scalability challenge posed by the exponentially large domain of possible execution traces, we decompose the task of predicting trace feasibility into independent prediction subtasks encoded as learning Boolean indicator functions for specific memory accesses, and apply a sparse fourier learning approach to learning each feasibility subtask.<\/jats:p>\n          <jats:p>Boolean functions that are sparse in their fourier domain can be efficiently learned by estimating the coefficients of their fourier expansion. Since the feasibility of each memory access depends on only a few other relevant memory accesses or system calls (e.g., relevant inter-thread communications), we observe that trace feasibility functions often have this sparsity property and can be learned efficiently. We use learned trace feasibility functions in conjunction with conservative alias analysis to implement a kernel race-testing system, HBFourier, that uses sparse fourier learning to efficiently model feasibility when making predictions. We evaluate our approach on a recent Linux development kernel and show it finds 44 more races with 15.7% more accurate race predictions than the next best performing system in our evaluation, in addition to identifying 5 new race bugs confirmed by kernel developers.<\/jats:p>","DOI":"10.1145\/3649840","type":"journal-article","created":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T17:53:50Z","timestamp":1714413230000},"page":"810-832","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Accurate Data Race Prediction in the Linux Kernel through Sparse Fourier Learning"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-9464-587X","authenticated-orcid":false,"given":"Gabriel","family":"Ryan","sequence":"first","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-8102-3792","authenticated-orcid":false,"given":"Burcu","family":"Cetin","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-9651-2894","authenticated-orcid":false,"given":"Yongwhan","family":"Lim","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3518-4877","authenticated-orcid":false,"given":"Suman","family":"Jana","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,4,29]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2015. Kernel panic due to race condition. https:\/\/access.redhat.com\/solutions\/1593553"},{"key":"e_1_2_1_2_1","unstructured":"2016. Dirty COW (CVE-2016-5195). https:\/\/dirtycow.ninja\/"},{"key":"e_1_2_1_3_1","unstructured":"2022. Huawei Kernel Module Race Condition (CVE-2022-31758). https:\/\/nvd.nist.gov\/vuln\/detail\/CVE-2022-31758"},{"key":"e_1_2_1_4_1","unstructured":"2022. An Introduction to Lockless Algorithms. https:\/\/lwn.net\/Articles\/844224\/"},{"key":"e_1_2_1_5_1","unstructured":"2022. Kernel race exploit for Denial-of-Service (CVE-2022-1652). https:\/\/www.cvedetails.com\/cve\/CVE-2022-1652\/"},{"key":"e_1_2_1_6_1","unstructured":"2022. Kernel race exploit leading to information leak memory corruption (CVE-2022-3028). https:\/\/nvd.nist.gov\/vuln\/detail\/CVE-2022-3028"},{"key":"e_1_2_1_7_1","unstructured":"2022. Syzkaller. https:\/\/github.com\/google\/syzkaller"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","unstructured":"2023. HBFourier Replication Artifact. https:\/\/doi.org\/10.6084\/m9.figshare.25365340.v1 10.6084\/m9.figshare.25365340.v1","DOI":"10.6084\/m9.figshare.25365340.v1"},{"key":"e_1_2_1_9_1","unstructured":"2023. [PATCH] fix for blk-mq racy attribute.. https:\/\/github.com\/torvalds\/linux\/commit\/49e60333d743ae32db3bdde2f93bc818482dd741"},{"key":"e_1_2_1_10_1","unstructured":"2023. [PATCH] Fix potential data race at PCM memory allocation helpers.. https:\/\/github.com\/torvalds\/linux\/commit\/bd55842ed998a622ba6611fe59b3358c9f76773d"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735970.1736040"},{"key":"e_1_2_1_12_1","volume-title":"Boolean functions: Theory, algorithms, and applications","author":"Crama Yves","unstructured":"Yves Crama and Peter L Hammer. 2011. Boolean functions: Theory, algorithms, and applications. Cambridge University Press."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542490"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477132.3483549"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594315"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2019.00017"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Zu-Ming Jiang Jia-Ju Bai Kangjie Lu and Shi-Min Hu. 2022. Context-Sensitive and Directional Concurrency Fuzzing for Data-Race Detection.","DOI":"10.14722\/ndss.2022.24296"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3140587.3062374"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103466"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Yishay Mansour. 1994. Learning Boolean functions via the Fourier transform. Theoretical advances in neural computation and learning 391\u2013424.","DOI":"10.1007\/978-1-4615-2696-4_11"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276515"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the ACM on Programming Languages, 5, POPL","author":"Mathur Umang","year":"2021","unstructured":"Umang Mathur, Andreas Pavlogiannis, and Mahesh Viswanathan. 2021. Optimal prediction of synchronization-preserving races. Proceedings of the ACM on Programming Languages, 5, POPL (2021), 1\u201329."},{"key":"e_1_2_1_24_1","volume-title":"Proc. Workshop on Parallel and Distributed Algorithms,.","author":"Mattern Friedemann","year":"1989","unstructured":"Friedemann Mattern. 1989. Virtual time and global states of distributed systems.. In Proc. Workshop on Parallel and Distributed Algorithms,."},{"key":"e_1_2_1_25_1","volume-title":"CHESS: A systematic testing tool for concurrent software. 16. https:\/\/www.microsoft.com\/en-us\/research\/publication\/chess-a-systematic-testing-tool-for-concurrent-software\/","author":"Musuvathi Madan","year":"2007","unstructured":"Madan Musuvathi, Shaz Qadeer, and Thomas Ball. 2007. CHESS: A systematic testing tool for concurrent software. 16. https:\/\/www.microsoft.com\/en-us\/research\/publication\/chess-a-systematic-testing-tool-for-concurrent-software\/"},{"key":"e_1_2_1_26_1","volume-title":"Detecting data races in parallel program executions","author":"Netzer Robert","unstructured":"Robert Netzer and Barton P Miller. 1989. Detecting data races in parallel program executions. University of Wisconsin-Madison Department of Computer Sciences."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/130616.130623"},{"key":"e_1_2_1_28_1","volume-title":"Analysis of boolean functions","author":"O\u2019Donnell Ryan","unstructured":"Ryan O\u2019Donnell. 2014. Analysis of boolean functions. Cambridge University Press."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the ACM on Programming Languages, 4, POPL","author":"Pavlogiannis Andreas","year":"2019","unstructured":"Andreas Pavlogiannis. 2019. Fast, sound, and effectively complete dynamic race prediction. Proceedings of the ACM on Programming Languages, 4, POPL (2019), 1\u201329."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385993"},{"key":"e_1_2_1_31_1","volume-title":"Precise Detection of Kernel Data Races with Probabilistic Lockset Analysis. In 2023 IEEE Symposium on Security and Privacy (SP).","author":"Ryan Gabriel","year":"2023","unstructured":"Gabriel Ryan, Abhishek Shah, Dongdong She, and Suman Jana. 2023. Precise Detection of Kernel Data Races with Probabilistic Lockset Analysis. In 2023 IEEE Symposium on Security and Privacy (SP)."},{"key":"e_1_2_1_32_1","volume-title":"NASA Formal Methods Symposium. 313\u2013327","author":"Said Mahmoud","year":"2011","unstructured":"Mahmoud Said, Chao Wang, Zijiang Yang, and Karem Sakallah. 2011. Generating data race witnesses by an SMT-based analysis. In NASA Formal Methods Symposium. 313\u2013327."},{"key":"e_1_2_1_33_1","volume-title":"International Conference on Runtime Verification. 136\u2013150","author":"\u015eerb\u0103nu\u0163\u0103 Traian Florin","year":"2012","unstructured":"Traian Florin \u015eerb\u0103nu\u0163\u0103, Feng Chen, and Grigore Ro\u015fu. 2012. Maximal causal models for sequentially consistent systems. In International Conference on Runtime Verification. 136\u2013150."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2103656.2103702"},{"key":"e_1_2_1_35_1","unstructured":"Peter Stobbe and Andreas Krause. 2012. Learning fourier sparse set functions. In Artificial Intelligence and Statistics. 1125\u20131133."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the ACM on Programming Languages, 7, POPL","author":"Thokair Mosaad Al","year":"2023","unstructured":"Mosaad Al Thokair, Minjian Zhang, Umang Mathur, and Mahesh Viswanathan. 2023. Dynamic Race Detection with O (1) Samples. Proceedings of the ACM on Programming Languages, 7, POPL (2023), 1308\u20131337."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531793.1531805"},{"key":"e_1_2_1_38_1","volume-title":"2020 IEEE Symposium on Security and Privacy (SP). 1643\u20131660","author":"Xu Meng","year":"2020","unstructured":"Meng Xu, Sanidhya Kashyap, Hanqing Zhao, and Taesoo Kim. 2020. Krace: Data race fuzzing for kernel file systems. In 2020 IEEE Symposium on Security and Privacy (SP). 1643\u20131660."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2015.15"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649840","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3649840","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:54:06Z","timestamp":1750287246000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649840"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,29]]},"references-count":39,"journal-issue":{"issue":"OOPSLA1","published-print":{"date-parts":[[2024,4,29]]}},"alternative-id":["10.1145\/3649840"],"URL":"https:\/\/doi.org\/10.1145\/3649840","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,29]]},"assertion":[{"value":"2024-04-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}