DFTracker: detecting double-fetch bugs by multi-taint parallel tracking

Abstract

A race condition is a common trigger for concurrency bugs. As a special case, a race condition can also occur across the kernel and user space causing a doublefetch bug, which is a field that has received little research attention. In our work, we first analyzed real-world doublefetch bug cases and extracted two specific patterns for doublefetch bugs. Based on these patterns, we proposed an approach of multi-taint parallel tracking to detect double-fetch bugs. We also implemented a prototype called DFTracker (doublefetch bug tracker), and we evaluated it with our test suite. Our experiments demonstrated that it could effectively find all the double-fetch bugs in the test suite including eight realworld cases with no false negatives and minor false positives. In addition, we tested it on Linux kernel and found a new double-fetch bug. The execution overhead is approximately 2x for single-file cases and approximately 9x for the whole kernel test, which is acceptable. To the best of the authors’ knowledge, this work is the first to introduce multi-taint parallel tracking to double-fetch bug detection—an innovative method that is specific to double-fetch bug features—and has better path coverage as well as lower runtime overhead than the widely used dynamic approaches.

Keywords

multi-taint parallel tracking / double fetch / race condition between kernel and user / time of check to time of use / real-world case analysis / Clang Static Analyzer

References

[1] Leveson N G, Turner C S. An investigation of the therac-25 accidents. Computer, 1993, 26(7): 18–41

[2] Jesdanun A. General electric acknowledges northeastern blackout bug. 2004

[3] Net X. Nasdaq CEO blames software design for delayed facebook trading. China Securities Journal, 2012

[4] Kasikci B, Zamfir C, Candea G. Data races vs. data race bugs: telling the difference with portend. ACM SIGPLAN Notices, 2012, 47(4): 185–198

[5] Huang J, Meredith P O, Rosu G. Maximal sound predictive race detection with control flow abstraction. ACM SIGPLAN Notices, 2014, 49(6): 337–348

[6] Narayanasamy S, Wang Z, Tigani J, Edwards A, Calder B. Automatically classifying benign and harmful data races using replay analysis. ACM SIGPLAN Notices, 2007, 42(6): 22–31

[7] Dimitrov D, Raychev V, Vechev M, Koskinen E. Commutativity race detection. ACM SIGPLAN Notices, 2014, 49(6): 305–315

[8] Cai X, Gui Y, Johnson R. Exploiting unix file-system races via algorithmic complexity attacks. In: Proceedings of the 30th IEEE Symposium on Security and Privacy. 2009, 27–41

[9] Hsiao C H, Yu J, Narayanasamy S, Kong Z, Pereira C L, Pokam G A, Chen PM, Flinn J. Race detection for event-driven mobile applications. ACM SIGPLAN Notices, 2014, 49(6): 326–336

[10] Maiya P, Kanade A, Majumdar R. Race detection for android applications. ACM SIGPLAN Notices, 2014, 49(6): 316–325

[11] ChinaByte. Amazon EC2 reboot to cope with xen vulnerability. 2014

[12] Gunawi H S, Hao M, Leesatapornwongsa T, Patana-anake T, Do T, Adityatama J, Eliazar K J, Laksono A, Lukman J F, Martin V, Satria A D. What bugs live in the cloud? a study of 3000+ issues in cloud systems. In: Proceedings of the ACM Symposium on Cloud Computing. 2014

[13] Wu Z, Lu K, Wang X, Zhou X, Chen C. Detecting harmful data races through parallel verification. The Journal of Supercomputing, 2015, 71(8): 2922–2943

[14] Serna F J. Ms08-061: the case of the kernel mode double-fetch. 2008

[15] Jurczyk M, Coldwind G. Identifying and exploiting windows kernel race conditions via memory access patterns. Syscan 2013 Whitepaper, 2013

[16] Eckelmann S. [patch-resend] backports: fix double fetch in hlist_for_each_entry*_rcu, 2014

[17] Wilhelm F. Tracing privileged memory accesses to discover software vulnerabilities. Dissertation for the Master’s Degree. Karlsruher: Karlsruher Institut für Technologie, 2015

[18] Voung J W, Jhala R, Lerner S. Relay: static race detection on millions of lines of code. In: Proceedings of the 6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering. 2007, 205–214

[19] Pratikakis P, Foster J S, Hicks M. Locksmith: practical static race detection for C. ACM Transactions on Programming Languages and Systems, 2011, 33(1): 3

[20] Huang J, Zhang C. Persuasive prediction of concurrency access anomalies. In: Proceedings of the International Symposium on Software Testing and Analysis. 2011, 144–154

[21] Chen J, MacDonald S. Towards a better collaboration of static and dynamic analyses for testing concurrent programs. In: Proceedings of the 6th Workshop on Parallel and Distributed Systems: Testing, Analysis, and Debugging. 2008

[22] Engler D, Ashcraft K. Racerx: effective, static detection of race conditions and deadlocks. ACM SIGOPS Operating Systems Review, 2003, 37(5): 237–252

[23] Sen K. Race directed random testing of concurrent programs. ACM SIGPLAN Notices, 2008, 43(6): 11–21

[24] Kasikci B, Zamfir C, Candea G. Racemob: crowdsourced data race detection. In: Proceedings of the 24th ACM Symposium on Operating Systems Principles. 2013, 406–422

[25] Zhang W, Sun C, Lu S. ConMem: detecting severe concurrency bugs through an effect-oriented approach. ACM SIGARCH Computer Architecture News, 2010, 38(1): 179–192

[26] Zhang W, Lim J, Olichandran R, Scherpelz J, Jin G, Lu S, Reps T. ConSeq: detecting concurrency bugs through sequential errors. ACM SIGPLAN Notices, 2011, 46(3): 251–264

[27] Yu J, Narayanasamy S, Pereira C, Pokam G. Maple: a coveragedriven testing tool for multithreaded programs. ACM SIGPLAN Notices, 2012, 47(10): 485–502

[28] Bishop M, Dilger M. Checking for race conditions in file accesses. Computing Systems, 1996, 2(2): 131–152

[29] Watson R N. Exploiting concurrency vulnerabilities in system call wrappers. In: Proceedings of the 1st USENIX Workshop on Offensive Technologies. 2007

[30] Yang J, Cui A, Stolfo S, Sethumadhavan S. Concurrency attacks. In: Proceedings of the 4th USENIX Workshop on Hot Topics in Parallelism. 2012

[31] Chen H, Wagner D. Mops: an infrastructure for examining security properties of software. In: Proceedings of the 9th ACM Conference on Computer and Communications Security. 2002, 235–244

[32] Cowan C, Beattie S, Wright C, Kroah-Hartman G. RaceGuard: kernel protection from temporary file race vulnerabilities. In: Proceedings of USENIX Security Symposium. 2001, 165–176

[33] Lhee K S, Chapin S J. Detection of file-based race conditions. International Journal of Information Security, 2005, 4(1–2): 105–119

[34] Payer M, Gross T R. Protecting applications against tocttou races by user-space caching of file metadata. ACM SIGPLAN Notices, 2012, 47(7): 215–226

[35] Cox M J. Bug 166248- can-2005-2490 sendmsg compat stack overflow, 2005

[36] Wang P. Double-fetch bug in drivers/misc/mic/host/mic_virtio.c of linux-4.5, 2016

[37] Wang P. Double-fetch bug in drivers/s390/char/sclp_ctl.c of linux-4.5, 2016

[38] Wang P. Double-fetch bug in drivers/platform/chrome/cros_ec_dev.c of linux-4.6, 2016

[39] Wang P. Double-fetch bug in kernel/auditsc.c of linux-4.6, 2016

[40] Wang P. Double-fetch bug in drivers/scsi/aacraid/commctrl.c of linux-4.5, 2016

[41] Erickson J, Musuvathi M, Burckhardt S, Olynyk K. Effective data-race detection for the kernel. In: Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation. 2010, 1–16

[42] Fonseca P, Rodrigues R, Brandenburg B B. Ski: exposing kernel concurrency bugs through systematic schedule exploration. In: Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation. 2014, 415–431

[43] Yang J, Twohey P, Engler D, Musuvathi M. Using model checking to find serious file system errors. ACM Transactions on Computer Systems, 2006, 24(4): 393–423

[44] Engler D, Musuvathi M. Static analysis versus software model checking for bug finding. In: Proceedings of the International Workshop on Verification, Model Checking, and Abstract Interpretation. 2004, 191–210

[45] Xie Y, Chou A, Engler D. Archer: using symbolic, path-sensitive analysis to detect memory access errors. ACM SIGSOFT Software Engineering Notes, 2003, 28(5): 327–336

[46] Wu Z, Lu K, Wang X, Zhou X. Collaborative technique for concurrency bug detection. International Journal of Parallel Programming, 2015, 43(2): 260–285

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature