|
|
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 |
|
|
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
|
|
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 |
|
|
|
|