Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2019, Vol. 13 Issue (2) : 247-263    https://doi.org/10.1007/s11704-016-6383-8
RESEARCH ARTICLE
DFTracker: detecting double-fetch bugs by multi-taint parallel tracking
Pengfei WANG1,2,3(), Kai LU1,2,3, Gen LI1,2,3, Xu ZHOU1,2,3
1. Science and Technology on Parallel and Distributed Processing Laboratory, National University of Defense Technology, Changsha 410073, China
2. College of Computer, National University of Defense Technology, Changsha 410073, China
3. Collaborative Innovation Center of High Performance Computing, National University of Defense Technology, Changsha 410073, China
 Download: PDF(1166 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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     
Corresponding Author(s): Pengfei WANG   
Just Accepted Date: 19 December 2016   Online First Date: 06 March 2018    Issue Date: 08 April 2019
 Cite this article:   
Pengfei WANG,Kai LU,Gen LI, et al. DFTracker: detecting double-fetch bugs by multi-taint parallel tracking[J]. Front. Comput. Sci., 2019, 13(2): 247-263.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-016-6383-8
https://academic.hep.com.cn/fcs/EN/Y2019/V13/I2/247
1 N GLeveson, C STurner. An investigation of the therac-25 accidents. Computer, 1993, 26(7): 18–41
https://doi.org/10.1109/MC.1993.274940
2 AJesdanun. General electric acknowledges northeastern blackout bug. 2004
3 XNet. Nasdaq CEO blames software design for delayed facebook trading. China Securities Journal, 2012
4 BKasikci, CZamfir, GCandea. Data races vs. data race bugs: telling the difference with portend. ACM SIGPLAN Notices, 2012, 47(4): 185–198
https://doi.org/10.1145/2150976.2150997
5 JHuang, P O Meredith, GRosu. Maximal sound predictive race detection with control flow abstraction. ACM SIGPLAN Notices, 2014, 49(6): 337–348
https://doi.org/10.1145/2666356.2594315
6 SNarayanasamy, ZWang, JTigani, A Edwards, BCalder. Automatically classifying benign and harmful data races using replay analysis. ACM SIGPLAN Notices, 2007, 42(6): 22–31
https://doi.org/10.1145/1273442.1250738
7 DDimitrov, V Raychev, MVechev, EKoskinen. Commutativity race detection. ACM SIGPLAN Notices, 2014, 49(6): 305–315
https://doi.org/10.1145/2666356.2594322
8 XCai, YGui, RJohnson. Exploiting unix file-system races via algorithmic complexity attacks. In: Proceedings of the 30th IEEE Symposium on Security and Privacy. 2009, 27–41
https://doi.org/10.1109/SP.2009.10
9 C HHsiao, JYu, SNarayanasamy, ZKong, C L Pereira, G APokam, PMChen, JFlinn. Race detection for event-driven mobile applications. ACM SIGPLAN Notices, 2014, 49(6): 326–336
https://doi.org/10.1145/2666356.2594330
10 PMaiya, AKanade, RMajumdar. Race detection for android applications. ACM SIGPLAN Notices, 2014, 49(6): 316–325
https://doi.org/10.1145/2666356.2594311
11 ChinaByte. Amazon EC2 reboot to cope with xen vulnerability. 2014
12 H SGunawi, MHao, TLeesatapornwongsa, TPatana-anake, TDo , JAdityatama, K JEliazar, A Laksono, J FLukman, VMartin, A DSatria. 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 ZWu, KLu, XWang, X Zhou, CChen. Detecting harmful data races through parallel verification. The Journal of Supercomputing, 2015, 71(8): 2922–2943
https://doi.org/10.1007/s11227-015-1418-8
14 F JSerna. Ms08-061: the case of the kernel mode double-fetch. 2008
15 MJurczyk, G Coldwind. Identifying and exploiting windows kernel race conditions via memory access patterns. Syscan 2013 Whitepaper, 2013
16 SEckelmann. [patch-resend] backports: fix double fetch in hlist_for_each_entry*_rcu, 2014
17 FWilhelm . Tracing privileged memory accesses to discover software vulnerabilities. Dissertation for the Master’s Degree. Karlsruher: Karlsruher Institut für Technologie, 2015
18 J WVoung, RJhala, SLerner. 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
https://doi.org/10.1145/1287624.1287654
19 PPratikakis, J SFoster, MHicks. Locksmith: practical static race detection for C. ACM Transactions on Programming Languages and Systems, 2011, 33(1): 3
https://doi.org/10.1145/1889997.1890000
20 JHuang, CZhang. Persuasive prediction of concurrency access anomalies. In: Proceedings of the International Symposium on Software Testing and Analysis. 2011, 144–154
https://doi.org/10.1145/2001420.2001438
21 JChen, S MacDonald. 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 DEngler, K Ashcraft. Racerx: effective, static detection of race conditions and deadlocks. ACM SIGOPS Operating Systems Review, 2003, 37(5): 237–252
https://doi.org/10.1145/1165389.945468
23 KSen. Race directed random testing of concurrent programs. ACM SIGPLAN Notices, 2008, 43(6): 11–21
https://doi.org/10.1145/1379022.1375584
24 BKasikci, CZamfir, GCandea. Racemob: crowdsourced data race detection. In: Proceedings of the 24th ACM Symposium on Operating Systems Principles. 2013, 406–422
https://doi.org/10.1145/2517349.2522736
25 WZhang, CSun, SLu. ConMem: detecting severe concurrency bugs through an effect-oriented approach. ACM SIGARCH Computer Architecture News, 2010, 38(1): 179–192
https://doi.org/10.1145/1735970.1736041
26 WZhang, JLim, ROlichandran, JScherpelz, GJin, SLu, TReps. ConSeq: detecting concurrency bugs through sequential errors. ACM SIGPLAN Notices, 2011, 46(3): 251–264
https://doi.org/10.1145/1961296.1950395
27 JYu, S Narayanasamy, CPereira, GPokam. Maple: a coveragedriven testing tool for multithreaded programs. ACM SIGPLAN Notices, 2012, 47(10): 485–502
https://doi.org/10.1145/2398857.2384651
28 MBishop, MDilger. Checking for race conditions in file accesses. Computing Systems, 1996, 2(2): 131–152
29 R NWatson. Exploiting concurrency vulnerabilities in system call wrappers. In: Proceedings of the 1st USENIX Workshop on Offensive Technologies. 2007
30 JYang, ACui, SStolfo, S Sethumadhavan. Concurrency attacks. In: Proceedings of the 4th USENIX Workshop on Hot Topics in Parallelism. 2012
31 HChen, DWagner. Mops: an infrastructure for examining security properties of software. In: Proceedings of the 9th ACM Conference on Computer and Communications Security. 2002, 235–244
https://doi.org/10.1145/586110.586142
32 CCowan, S Beattie, CWright, GKroah-Hartman. RaceGuard: kernel protection from temporary file race vulnerabilities. In: Proceedings of USENIX Security Symposium. 2001, 165–176
33 K SLhee, S JChapin. Detection of file-based race conditions. International Journal of Information Security, 2005, 4(1–2): 105–119
https://doi.org/10.1007/s10207-004-0068-2
34 MPayer, T RGross. Protecting applications against tocttou races by user-space caching of file metadata. ACM SIGPLAN Notices, 2012, 47(7): 215–226
https://doi.org/10.1145/2365864.2151052
35 M JCox. Bug 166248- can-2005-2490 sendmsg compat stack overflow, 2005
36 PWang. Double-fetch bug in drivers/misc/mic/host/mic_virtio.c of linux-4.5, 2016
37 PWang. Double-fetch bug in drivers/s390/char/sclp_ctl.c of linux-4.5, 2016
38 PWang. Double-fetch bug in drivers/platform/chrome/cros_ec_dev.c of linux-4.6, 2016
39 PWang. Double-fetch bug in kernel/auditsc.c of linux-4.6, 2016
40 PWang. Double-fetch bug in drivers/scsi/aacraid/commctrl.c of linux-4.5, 2016
41 JErickson, M Musuvathi, SBurckhardt, KOlynyk. Effective data-race detection for the kernel. In: Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation. 2010, 1–16
42 PFonseca, R Rodrigues, B BBrandenburg. 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 JYang, PTwohey, DEngler, M Musuvathi. Using model checking to find serious file system errors. ACM Transactions on Computer Systems, 2006, 24(4): 393–423
https://doi.org/10.1145/1189256.1189259
44 DEngler, M Musuvathi. 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
https://doi.org/10.1007/978-3-540-24622-0_17
45 YXie, AChou , DEngler. Archer: using symbolic, path-sensitive analysis to detect memory access errors. ACM SIGSOFT Software Engineering Notes, 2003, 28(5): 327–336
https://doi.org/10.1145/949952.940115
46 ZWu, KLu, XWang, X Zhou. Collaborative technique for concurrency bug detection. International Journal of Parallel Programming, 2015, 43(2): 260–285
https://doi.org/10.1007/s10766-014-0304-y
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed