research-article

RID: Finding Reference Count Bugs with Inconsistent Path Pair Checking

Authors:

Yuanchun ShiAuthors Info & Claims

ACM SIGARCH Computer Architecture News, Volume 44, Issue 2

Pages 531 - 544

https://doi.org/10.1145/2980024.2872389

Published: 25 March 2016 Publication History

Abstract

Reference counts are widely used in OS kernels for resource management. However, reference counts are not trivial to be used correctly in large scale programs because it is left to developers to make sure that an increment to a reference count is always paired with a decrement. This paper proposes inconsistent path pair checking, a novel technique that can statically discover bugs related to reference counts without knowing how reference counts should be changed in a function. A prototype called RID is implemented and evaluations show that RID can discover more than 80 bugs which were confirmed by the developers in the latest Linux kernel. The results also show that RID tends to reveal bugs caused by developers' misunderstanding on API specifications or error conditions that are not handled properly.

References

[1]

Clark Barrett, Pascal Fontaine, and Cesare Tinelli. The smt-lib standard version 2.5. http://smtlib.cs.uiowa.edu/papers/smt-lib-reference-v2.5-r2015-06--28.pdf.

[2]

Peter Baumgartner, Alexander Fuchs, and Cesare Tinelli. (lia) - model evolution with linear integer arithmetic constraints. In Iliano Cervesato, Helmut Veith, and Andrei Voronkov, editors, Logic for Programming, Artificial Intelligence, and Reasoning, volume 5330 of Lecture Notes in Computer Science, pages 258--273. Springer Berlin Heidelberg, 2008.

[3]

Isil Dillig, Thomas Dillig, and Alex Aiken. Static error detection using semantic inconsistency inference. In ACM SIGPLAN Notices, volume 42, pages 435--445, June 2007.

Digital Library

[4]

Michael Emmi, Ranjit Jhala, Eddie Kohler, and Rupak Majumdar. Verifying reference counting implementations. In Stefan Kowalewski and Anna Philippou, editors, Tools and Algorithms for the Construction and Analysis of Systems, 15th International Conference, TACAS 2009, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009, York, UK, March 22--29, 2009. Proceedings, volume 5505 of Lecture Notes in Computer Science, pages 352--367. Springer, 2009.

[5]

Dawson R. Engler, Benjamin Chelf, Andy Chou, and Seth Hallem. Checking system rules using system-specific, programmer-written compiler extensions. In Michael B. Jones and M. Frans Kaashoek, editors, 4th Symposium on Operating System Design and Implementation (OSDI 2000), San Diego, California, USA, October 23--25, 2000, pages 1--16. USENIX Association, 2000.

[6]

Dawson R. Engler, David Yu Chen, and Andy Chou. Bugs as inconsistent behavior: A general approach to inferring errors in systems code. In SOSP, pages 57--72, 2001.

Digital Library

[7]

Mark Gabel, Junfeng Yang, Yuan Yu, Moises Goldszmidt, and Zhendong Su. Scalable and systematic detection of buggy inconsistencies in source code. ACM SIGPLAN Notices, 45(10):175--190, October 2010.

Digital Library

[8]

Claire Le Goues and Westley Weimer. Specification mining with few false positives. In Stefan Kowalewski and Anna Philippou, editors, Tools and Algorithms for the Construction and Analysis of Systems, 15th International Conference, TACAS 2009, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009, York, UK, March 22--29, 2009. Proceedings, volume 5505 of Lecture Notes in Computer Science, pages 292--306. Springer, 2009.

[9]

Seth Hallem, Benjamin Chelf, Yichen Xie, and Dawson R. Engler. A system and language for building system-specific, static analyses. In Jens Knoop and Laurie J. Hendren, editors, Proceedings of the 2002 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), Berlin, Germany, June 17--19, 2002, pages 69--82. ACM, 2002.

Digital Library

[10]

Mateus Jurczyk. Windows kernel reference count vulnerabilities - case study. http://j00ru.vexillium.org/dump/zn_slides.pdf.

[11]

Vineet Kahlon. Bootstrapping: a technique for scalable flow and context-sensitive pointer alias analysis. In Rajiv Gupta and Saman P. Amarasinghe, editors, Proceedings of the ACM SIGPLAN 2008 Conference on Programming Language Design and Implementation, Tucson, AZ, USA, June 7--13, 2008, pages 249--259. ACM, 2008.

Digital Library

[12]

Akash Lal and Ganesh Ramalingam. Reference count analysis with shallow aliasing. Information Processing Letters, 111(2):57--63, 2010.

Digital Library

[13]

Siliang Li and Gang Tan. Finding reference-counting errors in python/C programs with affine analysis. In Richard Jones, editor, ECOOP 2014 - Object-Oriented Programming - 28th European Conference, Uppsala, Sweden, July 28 - August 1, 2014. Proceedings, volume 8586 of Lecture Notes in Computer Science, pages 80--104. Springer, 2014.

[14]

Zhenmin Li and Yuanyuan Zhou. PR-miner: automatically extracting implicit programming rules and detecting violations in large software code. In Michel Wermelinger and Harald C. Gall, editors, Proceedings of the 10th European Software Engineering Conference held jointly with 13th ACM SIGSOFT International Symposium on Foundations of Software Engineering, 2005, Lisbon, Portugal, September 5--9, 2005, pages 306--315. ACM, 2005.

[15]

Huqiu Liu, Yuping Wang, Lingbo Jiang, and Shimin Hu. PF-miner: A new paired functions mining method for android kernel in error paths. In COMPSAC, pages 33--42. IEEE, 2014.

Digital Library

[16]

Shan Lu, Soyeon Park, Chongfeng Hu, Xiao Ma, Weihang Jiang, Zhenmin Li, Raluca A. Popa, and Yuanyuan Zhou. MUVI: automatically inferring multi-variable access correlations and detecting related semantic and concurrency bugs. In Thomas C. Bressoud and M. Frans Kaashoek, editors, Proceedings of the 21st ACM Symposium on Operating Systems Principles 2007, SOSP 2007, Stevenson, Washington, USA, October 14--17, 2007, pages 103--116. ACM, 2007.

[17]

D. Malcom. a static analysis tool for cpython extension code. https://gcc-python-plugin.readthedocs.org/en/latest/cpychecker.html.

[18]

Paul E. McKenney. Overview of linux-kernel reference counting. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2167.pdf.

[19]

Paul E. McKenney and Jack Slingwine. Read-copy update: Using execution history to solve concurrency problems. In 10th IASTED International Conference on Parallel and Distributed Computing and Systems, October 1998.

[20]

Leonardo Mendona De Moura and Nikolaj Bjorner. Z3: An Efficient SMT Solver. Springer, 2008.

[21]

Robert Oehlmann. Static single-assignment for program slicing on binary intermediate language. Master's thesis, Hamburg University of Technology, 2013.

[22]

Abhinav Pathak, Abhilash Jindal, Y. Charlie Hu, and Samuel P. Midkiff. What is keeping my phone awake?: characterizing and detecting no-sleep energy bugs in smartphone apps. In Nigel Davies, Srinivasan Seshan, and Lin Zhong, editors, The 10th International Conference on Mobile Systems, Applications, and Services, MobiSys'12, Ambleside, United Kingdom - June 25 - 29, 2012, pages 267--280. ACM, 2012.

Digital Library

[23]

Python/c api reference manual. https://docs.python.org/2/c-api/.

[24]

Refcount behavior of python/c apis. http://svn.python.org/projects/python/trunk/Doc/data/refcounts.dat.

[25]

Suman Saha, Jean-Pierre Lozi, Gaël Thomas, Julia Lawall, and Gilles Muller. Hector: Detecting resource-release omission faults in error-handling code for systems software. In Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2013, June 2013.

Digital Library

[26]

Martin Schaf, Daniel Schwartz-Narbonne, and Thomas Wies. Explaining inconsistent code. In Bertrand Meyer, Luciano Baresi, and Mira Mezini, editors, Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE'13, Saint Petersburg, Russian Federation, August 18--26, 2013, pages 521--531. ACM, 2013.

[27]

Lin Tan, Chen Liu, Zhenmin Li, Xuanhui Wang, Yuanyuan Zhou, and ChengXiang Zhai. Bug characteristics in open source software. Empirical Software Engineering, 19(6):1665--1705, 2014.

Digital Library

[28]

Aaron Tomb and Cormac Flanagan. Detecting inconsistencies via universal reachability analysis. In Mats Per Erik Heimdahl and Zhendong Su, editors, International Symposium on Software Testing and Analysis, ISSTA 2012, Minneapolis, MN, USA, July 15--20, 2012, pages 287--297. ACM, 2012.

Digital Library

[29]

Security Tracker. Linux kernel memory leak in inotify\_init() lets local users deny service. http://www.securitytracker.com/id/1025321.

[30]

Westley Weimer and George C. Necula. Mining temporal specifications for error detection. In Nicolas Halbwachs and Lenore D. Zuck, editors, Tools and Algorithms for the Construction and Analysis of Systems, 11th International Conference, TACAS 2005, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2005, Edinburgh, UK, April 4--8, 2005, Proceedings, volume 3440 of Lecture Notes in Computer Science, pages 461--476. Springer, 2005.

[31]

Mark Weiser. Program slicing. IEEE Transactions on Software Engineering, SE-10(4):352--357, July 1984.

Digital Library

Cited By

Suzuki KIshiguro KKono KBagchi SZhang Y(2024)Balancing analysis time and bug detectionProceedings of the 2024 USENIX Conference on Usenix Annual Technical Conference10.5555/3691992.3692023(493-508)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.5555/3691992.3692023
Lu KPakki AWu Q(2019)Automatically Identifying Security Checks for Detecting Kernel Semantic BugsComputer Security – ESORICS 201910.1007/978-3-030-29962-0_1(3-25)Online publication date: 23-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-29962-0_1
Bai SZhang ZHu HLuo BLiao XXu JKirda ELie D(2024)CountDown: Refcount-guided Fuzzing for Exposing Temporal Memory Errors in Linux KernelProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690320(1315-1329)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690320
Show More Cited By

Index Terms

RID: Finding Reference Count Bugs with Inconsistent Path Pair Checking
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Power management
    2. Software functional properties
      1. Formal methods
        Automated static analysis

Recommendations

RID: Finding Reference Count Bugs with Inconsistent Path Pair Checking
ASPLOS '16: Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems

Reference counts are widely used in OS kernels for resource management. However, reference counts are not trivial to be used correctly in large scale programs because it is left to developers to make sure that an increment to a reference count is always ...
RID: Finding Reference Count Bugs with Inconsistent Path Pair Checking
ASPLOS '16

Reference counts are widely used in OS kernels for resource management. However, reference counts are not trivial to be used correctly in large scale programs because it is left to developers to make sure that an increment to a reference count is always ...
Static error detection using semantic inconsistency inference
PLDI '07: Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation

Inconsistency checking is a method for detecting software errors that relies only on examining multiple uses of a value. We propose that inconsistency inference is best understood as a variant of the older and better understood problem of type ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGARCH Computer Architecture News

ACM SIGARCH Computer Architecture News Volume 44, Issue 2

ASPLOS'16

May 2016

774 pages

ISSN:0163-5964

DOI:10.1145/2980024

Editor:
Doug DeGroot
acm dot org

Issue’s Table of Contents

ASPLOS '16: Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems
March 2016
824 pages
ISBN:9781450340915
DOI:10.1145/2872362
General Chair:
Tom Conte
Georgia Tech, USA
,
Program Chair:
Yuanyuan Zhou
University of California, San Diego, USA

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 March 2016

Published in SIGARCH Volume 44, Issue 2

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Natural Science Foundation of China
National High Technology Research and Development Program of China
National Science and Technology Major Project of China

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
830
Total Downloads

Downloads (Last 12 months)52
Downloads (Last 6 weeks)1

Reflects downloads up to 08 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Suzuki KIshiguro KKono KBagchi SZhang Y(2024)Balancing analysis time and bug detectionProceedings of the 2024 USENIX Conference on Usenix Annual Technical Conference10.5555/3691992.3692023(493-508)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.5555/3691992.3692023
Lu KPakki AWu Q(2019)Automatically Identifying Security Checks for Detecting Kernel Semantic BugsComputer Security – ESORICS 201910.1007/978-3-030-29962-0_1(3-25)Online publication date: 23-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-29962-0_1
Bai SZhang ZHu HLuo BLiao XXu JKirda ELie D(2024)CountDown: Refcount-guided Fuzzing for Exposing Temporal Memory Errors in Linux KernelProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690320(1315-1329)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690320
Chen ZLiu DXiao JWang H(2023)All Use-After-Free Vulnerabilities Are Not Created Equal: An Empirical Study on Their Characteristics and DetectabilityProceedings of the 26th International Symposium on Research in Attacks, Intrusions and Defenses10.1145/3607199.3607229(623-638)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3607199.3607229
Hu MZhao QZhang YXiong Y(2023)Cross-Language Call Graph Construction Supporting Different Host Languages2023 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER56733.2023.00024(155-166)Online publication date: Mar-2023
https://doi.org/10.1109/SANER56733.2023.00024
Ma XYan JZhang HYan JZhang JBissyandé TKlein JBird CSarro F(2023)Detecting Memory Errors in Python Native Code by Tracking Object Lifecycle with Reference CountProceedings of the 38th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE56229.2023.00198(1429-1440)Online publication date: 11-Nov-2023
https://dl.acm.org/doi/10.1109/ASE56229.2023.00198
Zhou QWu QLiu DJi SLu KYin HStavrou ACremers CShi E(2022)Non-Distinguishable Inconsistencies as a Deterministic Oracle for Detecting Security BugsProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security10.1145/3548606.3560661(3253-3267)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3548606.3560661
Lin XHua BFan Q(2022)On the Security of Python Virtual Machines: An Empirical Study2022 IEEE International Conference on Software Maintenance and Evolution (ICSME)10.1109/ICSME55016.2022.00028(223-234)Online publication date: Oct-2022
https://doi.org/10.1109/ICSME55016.2022.00028
Liu DWu QJi SLu KLiu ZChen JHe QKim YKim JVigna GShi E(2021)Detecting Missed Security Operations Through Differential Checking of Object-based Similar PathsProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security10.1145/3460120.3485373(1627-1644)Online publication date: 12-Nov-2021
https://dl.acm.org/doi/10.1145/3460120.3485373
Jiang CHua BOuyang WFan QPan Z(2021)PyGuard: Finding and Understanding Vulnerabilities in Python Virtual Machines2021 IEEE 32nd International Symposium on Software Reliability Engineering (ISSRE)10.1109/ISSRE52982.2021.00055(468-475)Online publication date: Oct-2021
https://doi.org/10.1109/ISSRE52982.2021.00055
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents