NDLI: Graspan:A Single-machine Disk-based Graph System for Interprocedural Static Analyses of Large-scale Systems Code (OPSR, Vol. 51, Issue. 2)

Content Provider	ACM Digital Library
Author	Hussain, Aftab Wang, Kai Zuo, Zhiqiang Xu, Guoqing Amiri Sani, Ardalan
Abstract	There is more than a decade-long history of using static analysis to find bugs in systems such as Linux. Most of the existing static analyses developed for these systems are simple checkers that find bugs based on pattern matching. Despite the presence of many sophisticated interprocedural analyses, few of them have been employed to improve checkers for systems code due to their complex implementations and poor scalability. In this paper, we revisit the scalability problem of interprocedural static analysis from a "Big Data" perspective. That is, we turn sophisticated code analysis into Big Data analytics and leverage novel data processing techniques to solve this traditional programming language problem. We develop Graspan, a disk-based parallel graph system that uses an edge-pair centric computation model to compute dynamic transitive closures on very large program graphs. We implement context-sensitive pointer/alias and dataflow analyses on Graspan. An evaluation of these analyses on large codebases such as Linux shows that their Graspan implementations scale to millions of lines of code and are much simpler than their original implementations. Moreover, we show that these analyses can be used to augment the existing checkers; these augmented checkers uncovered 132 new NULL pointer bugs and 1308 unnecessary NULL tests in Linux 4.4.0-rc5, PostgreSQL 8.3.9, and Apache httpd 2.2.18.
Starting Page	389
Ending Page	404
Page Count	16
File Format	PDF
ISSN	01635980
DOI	10.1145/3093315.3037744
Journal	ACM SIGOPS Operating Systems Review (OPSR)
Volume Number	51
Issue Number	2
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1975-04-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Disk-based systems Graph processing Static analysis
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Information Systems

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Graspan:A Single-machine Disk-based Graph System for Interprocedural Static Analyses of Large-scale Systems Code (CARN, Vol. 45, Issue. 1)

Graspan:A Single-machine Disk-based Graph System for Interprocedural Static Analyses of Large-scale Systems Code (SIGP, Vol. 52, Issue. 4)

Graspan: A Single-machine Disk-based Graph System for Interprocedural Static Analyses of Large-scale Systems Code

CoRAL:Confined Recovery in Distributed Asynchronous Graph Processing (OPSR, Vol. 51, Issue. 2)

Verification of a Practical Hardware Security Architecture Through Static Information Flow Analysis (OPSR, Vol. 51, Issue. 2)

KickStarter:Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations (OPSR, Vol. 51, Issue. 2)

AMNESIAC:Amnesic Automatic Computer (OPSR, Vol. 51, Issue. 2)

Mallacc:Accelerating Memory Allocation (OPSR, Vol. 51, Issue. 2)

Translation-Triggered Prefetching (OPSR, Vol. 51, Issue. 2)

Graspan:A Single-machine Disk-based Graph System for Interprocedural Static Analyses of Large-scale Systems Code (OPSR, Vol. 51, Issue. 2)

Similar Documents

Graspan:A Single-machine Disk-based Graph System for Interprocedural Static Analyses of Large-scale Systems Code (CARN, Vol. 45, Issue. 1)

Graspan:A Single-machine Disk-based Graph System for Interprocedural Static Analyses of Large-scale Systems Code (SIGP, Vol. 52, Issue. 4)

Graspan: A Single-machine Disk-based Graph System for Interprocedural Static Analyses of Large-scale Systems Code

CoRAL:Confined Recovery in Distributed Asynchronous Graph Processing (OPSR, Vol. 51, Issue. 2)

Verification of a Practical Hardware Security Architecture Through Static Information Flow Analysis (OPSR, Vol. 51, Issue. 2)

KickStarter:Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations (OPSR, Vol. 51, Issue. 2)

AMNESIAC:Amnesic Automatic Computer (OPSR, Vol. 51, Issue. 2)

Mallacc:Accelerating Memory Allocation (OPSR, Vol. 51, Issue. 2)

Translation-Triggered Prefetching (OPSR, Vol. 51, Issue. 2)

Graspan:A Single-machine Disk-based Graph System for Interprocedural Static Analyses of Large-scale Systems Code (OPSR, Vol. 51, Issue. 2)