short-paper

SVF: interprocedural static value-flow analysis in LLVM

Authors:

Jingling XueAuthors Info & Claims

CC '16: Proceedings of the 25th International Conference on Compiler Construction

Pages 265 - 266

https://doi.org/10.1145/2892208.2892235

Published: 17 March 2016 Publication History

Abstract

This paper presents SVF, a tool that enables scalable and precise interprocedural Static Value-Flow analysis for C programs by leveraging recent advances in sparse analysis. SVF, which is fully implemented in LLVM, allows value-flow construction and pointer analysis to be performed in an iterative manner, thereby providing increasingly improved precision for both. SVF accepts points- to information generated by any pointer analysis (e.g., Andersen’s analysis) and constructs an interprocedural memory SSA form, in which the def-use chains of both top-level and address-taken variables are captured. Such value-flows can be subsequently exploited to support various forms of program analysis or enable more precise pointer analysis (e.g., flow-sensitive analysis) to be performed sparsely. By dividing a pointer analysis into three loosely coupled components: Graph, Rules and Solver, SVF provides an extensible interface for users to write their own solutions easily. SVF is publicly available at http://unsw-corg.github.io/SVF.

References

[1]

P. Anderson and T. Teitelbaum. Software inspection using codesurfer. In Workshop on Inspection in Software Engineering (WISE ’01), 2001.

[2]

J. R. Andrew Trick. FTL WebKit’s LLVM based JIT. In LLVM Developer Meeting 2014, 2014.

[3]

S. Arzt, S. Rasthofer, C. Fritz, E. Bodden, A. Bartel, J. Klein, Y. Le Traon, D. Octeau, and P. McDaniel. Flowdroid: Precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for android apps. PLDI ’14, 49(6):259–269, June 2014.

Digital Library

[4]

F. Chow, S. Chan, S. Liu, R. Lo, and M. Streich. Effective representation of aliases and indirect memory operations in SSA form. In CC ’96, pages 253–267.

Digital Library

[5]

N. K. Cristina Cifuentes Oracle Labs Australia, Oracle. Translating Java into LLVM IR to detect security vulnerabilities. In LLVM Developer Meeting 2014, 2014.

[6]

R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. An efficient method of computing static single assignment form. In POPL ’89, pages 25–35.

Digital Library

[7]

P. Di and Y. Sui. Accelerating dynamic data race detection using static thread interference analysis. In PMAM ’16, 2016.

Digital Library

[8]

J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependence graph and its use in optimization. TOPLAS ’87, 9(3):319–349, July 1987.

Digital Library

[9]

B. Hardekopf and C. Lin. Flow-sensitive pointer analysis for millions of lines of code. In CGO ’11, pages 289–298.

Digital Library

[10]

S. Horwitz, T. Reps, and D. Binkley. Interprocedural slicing using dependence graphs. In PLDI ’88, pages 35–46, 1988.

Digital Library

[11]

IBM. T.j. watson libraries for analysis (WALA).

[12]

P. Lam, E. Bodden, O. Lhoták, and L. Hendren. The Soot framework for Java program analysis: a retrospective. In in CETUS ’11, 2011.

[13]

C. Lattner and V. Adve. LLVM: A compilation framework for lifelong program analysis & transformation. In CGO ’’04, pages 75–86, 2014.

Digital Library

[14]

O. Lhoták and K.-C. A. Chung. Points-to analysis with efficient strong updates. In POPL ’11, pages 3–16.

[15]

V. B. Livshits and M. S. Lam. Tracking pointers with path and context sensitivity for bug detection in C programs. In FSE ’03, pages 317– 326.

Digital Library

[16]

D. Novillo and R. H. Canada. Memory SSA-a unified approach for sparsely representing memory operations. In Proc of the GCC Developers’ Summit. Citeseer, 2007.

[17]

H. Oh, K. Heo, W. Lee, W. Lee, and K. Yi. Design and implementation of sparse global analyses for C-like languages. In PLDI ’12, pages 229–238.

Digital Library

[18]

F. Pereira and D. Berlin. Wave propagation and deep propagation for pointer analysis. In CGO ’09, pages 126–135.

Digital Library

[19]

T. Reps, S. Horwitz, and M. Sagiv. Precise interprocedural dataflow analysis via graph reachability. In POPL ’95, pages 49–61, 1995.

Digital Library

[20]

Y. Sui, P. Di, and J. Xue. Sparse flow-sensitive pointer analysis for multithreaded programs. In CGO ’16, 2016.

Digital Library

[21]

Y. Sui, D. Ye, and J. Xue. Static memory leak detection using fullsparse value-flow analysis. In ISSTA ’12, pages 254–264.

Digital Library

[22]

Y. Sui, D. Ye, and J. Xue. Detecting memory leaks statically with full-sparse value-flow analysis. IEEE Transactions on Software Engineering, 40(2):107–122, 2014.

Digital Library

[23]

Y. Sui, S. Ye, J. Xue, and P. Yew. SPAS: Scalable path-sensitive pointer analysis on full-sparse SSA. In APLAS ’11, pages 155–171.

Digital Library

[24]

M. Weiser. Programmers use slices when debugging. Commun. ACM, 25(7):446–452, July 1982.

Digital Library

[25]

D. Ye, Y. Sui, and J. Xue. Accelerating dynamic detection of uses of undefined variables with static value-flow analysis. In CGO ’14, pages 154–164.

Digital Library

[26]

S. Ye, Y. Sui, and J. Xue. Region-based selective flow-sensitive pointer analysis. In SAS ’14, pages 319–336. Springer, 2014.

Cited By

Wang WFeng LShi ZZhuo CChen J(2024)Hardware-Assisted Control-Flow Integrity Enhancement for IoT Devices2024 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE58400.2024.10546789(1-6)Online publication date: 25-Mar-2024
https://doi.org/10.23919/DATE58400.2024.10546789
Balaji SCharumathi DAhmed MAppu A(2024)The influence of job satisfaction on retention of primary healthcare professionals in Tamil NaduInternational Journal of ADVANCED AND APPLIED SCIENCES10.21833/ijaas.2024.02.02511:2(238-247)Online publication date: Feb-2024
https://doi.org/10.21833/ijaas.2024.02.025
Kasten FZieris PHorsch J(2024)Integrating Static Analyses for High-Precision Control-Flow IntegrityProceedings of the 27th International Symposium on Research in Attacks, Intrusions and Defenses10.1145/3678890.3678920(419-434)Online publication date: 30-Sep-2024
https://dl.acm.org/doi/10.1145/3678890.3678920
Show More Cited By

Index Terms

SVF: interprocedural static value-flow analysis in LLVM
1. Theory of computation
  1. Semantics and reasoning
    1. Program semantics

Recommendations

Integrating Static Analyses for High-Precision Control-Flow Integrity
RAID '24: Proceedings of the 27th International Symposium on Research in Attacks, Intrusions and Defenses

Memory corruptions are still one of the most prevalent and severe security vulnerabilities in today’s programs. For this reason, several techniques for mitigating software vulnerabilities exist and are used in production systems. An important mitigation ...
Interprocedural Pointer Analysis in Goanna

Goanna is an industrial-strength static analysis tool used in academia and industry alike to find bugs in C/C++ programs. Unlike existing approaches, Goanna uses the off-the-shelf model checker NuSMV as its core analysis engine on a syntactic flow-...
Semi-sparse flow-sensitive pointer analysis
POPL '09

Pointer analysis is a prerequisite for many program analyses, and the effectiveness of these analyses depends on the precision of the pointer information they receive. Two major axes of pointer analysis precision are flow-sensitivity and context-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CC '16: Proceedings of the 25th International Conference on Compiler Construction

March 2016

270 pages

ISBN:9781450342414

DOI:10.1145/2892208

General Chair:
Ayal Zaks
Intel, Israel / Technion, Israel
,
Program Chair:
Manuel Hermenegildo
IMDEA SW Institute, Spain / T.U. Madrid-UPM, Spain

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]

Sponsors

In-Cooperation

IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 March 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper

Conference

CGO '16

Sponsor:

CGO '16: 14th Annual IEEE/ACM International Symposium on Code Generation and Optimization

March 17 - 18, 2016

Barcelona, Spain

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

270
Total Citations
View Citations
2,077
Total Downloads

Downloads (Last 12 months)335
Downloads (Last 6 weeks)22

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang WFeng LShi ZZhuo CChen J(2024)Hardware-Assisted Control-Flow Integrity Enhancement for IoT Devices2024 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE58400.2024.10546789(1-6)Online publication date: 25-Mar-2024
https://doi.org/10.23919/DATE58400.2024.10546789
Balaji SCharumathi DAhmed MAppu A(2024)The influence of job satisfaction on retention of primary healthcare professionals in Tamil NaduInternational Journal of ADVANCED AND APPLIED SCIENCES10.21833/ijaas.2024.02.02511:2(238-247)Online publication date: Feb-2024
https://doi.org/10.21833/ijaas.2024.02.025
Kasten FZieris PHorsch J(2024)Integrating Static Analyses for High-Precision Control-Flow IntegrityProceedings of the 27th International Symposium on Research in Attacks, Intrusions and Defenses10.1145/3678890.3678920(419-434)Online publication date: 30-Sep-2024
https://dl.acm.org/doi/10.1145/3678890.3678920
Busse FNowack MCadar CBöhme MNoller YSzekeres L(2024)Sparse Symbolic Loop Execution (Registered Report)Proceedings of the 3rd ACM International Fuzzing Workshop10.1145/3678722.3685535(61-69)Online publication date: 13-Sep-2024
https://dl.acm.org/doi/10.1145/3678722.3685535
Dang YXia ZLi HSekar VYu MSeneviratne AVeitch D(2024)POSTER: Bring I-Cache to Light in Data Plane ApplicationsProceedings of the ACM SIGCOMM 2024 Conference: Posters and Demos10.1145/3672202.3673724(28-30)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3672202.3673724
Xu RChen LZhang RZhang YXiao WZhou HMao X(2024)Accelerating Static Null Pointer Dereference Detection with Parallel ComputingProceedings of the 15th Asia-Pacific Symposium on Internetware10.1145/3671016.3671385(135-144)Online publication date: 24-Jul-2024
https://dl.acm.org/doi/10.1145/3671016.3671385
He WDi PMing MZhang CSu TLi SSui Y(2024)Finding and Understanding Defects in Static Analyzers by Constructing Automated OraclesProceedings of the ACM on Software Engineering10.1145/36607811:FSE(1656-1678)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3660781
Zou CHe DSui YXue J(2024)TIPS: Tracking Integer-Pointer Value Flows for C++ Member Function PointersProceedings of the ACM on Software Engineering10.1145/36607791:FSE(1609-1631)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3660779
Lei YBossut CSui YZhang Q(2024)Context-Free Language Reachability via Skewed TabulationProceedings of the ACM on Programming Languages10.1145/36564518:PLDI(1830-1853)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656451
Sun WFang CGe YHu YChen YZhang QGe XLiu YChen Z(2024)A Survey of Source Code Search: A 3-Dimensional PerspectiveACM Transactions on Software Engineering and Methodology10.1145/365634133:6(1-51)Online publication date: 28-Jun-2024
https://dl.acm.org/doi/10.1145/3656341
Show More Cited By

View Options

Get Access

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.

Media

Figures

Other

Tables

View Table of Contents