research-article

On the construction of soundness oracles

Authors:

Amjed TahirAuthors Info & Claims

SOAP 2017: Proceedings of the 6th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis

Pages 37 - 42

https://doi.org/10.1145/3088515.3088520

Published: 18 June 2017 Publication History

Abstract

One of the inherent advantages of static analysis is that it can create and reason about models of an entire program. However, mainstream languages such as Java use numerous dynamic language features designed to boost programmer productivity, but these features are notoriously difficult to capture by static analysis, leading to unsoundness in practice. While existing research has focused on providing sound handling for selected language features (mostly reflection) based on anecdotal evidence and case studies, there is little empirical work to investigate the extent to which particular features cause unsoundness of static analysis in practice. In this paper, we (1) discuss language features that may cause unsoundness and (2) discuss a methodology that can be used to check the (un)soundness of a particular static analysis, call-graph construction, based on soundness oracles. These oracles can also be used for hybrid analyses.

References

[1]

JSR 199: Java Compiler API, 2006. https://jcp.org/en/ jsr/detail?id=199 {accessed 12 March 17}.

[2]

JSR 223: Scripting for the Java Platform, 2006. https: //jcp.org/en/jsr/detail?id=223 {accessed 12 March 17}.

[3]

Kent Beck. Test-driven development: by example. Addison-Wesley Professional, 2003.

Digital Library

[4]

Stephen M Blackburn, Robin Garner, Chris Hoffmann, Asjad M Khang, Kathryn S McKinley, Rotem Bentzur, Amer Diwan, Daniel Feinberg, Daniel Frampton, Samuel Z Guyer, et al. The dacapo benchmarks: Java benchmarking development and analysis. In Proceedings OOPSLA’06. ACM, 2006.

Digital Library

[5]

Eric Bodden. Invokedynamic support in soot. In Proceedings SOAP’12. ACM, 2012.

Digital Library

[6]

Eric Bodden, Andreas Sewe, Jan Sinschek, Hela Oueslati, and Mira Mezini. Taming reflection: Aiding static analysis in the presence of reflection and custom class loaders. In Proceedings ICSE’11. ACM, 2011.

Digital Library

[7]

Martin Bravenboer and Yannis Smaragdakis. Strictly declarative specification of sophisticated points-to analyses. In Proceedings OOPSLA’09. ACM, 2009.

Digital Library

[8]

Jens Dietrich, Henrik Schole, Li Sui, and Ewan Tempero. XCorpus An executable Corpus of Java Programs, 2017.

[9]

https://goo.gl/kGk7x3 {preprint, accessed 16 March 17}.

[10]

Michael D Ernst. Static and dynamic analysis: Synergy and duality. In Proceedings WODA’03, 2003.

[11]

Martin Fowler. Inversion of control containers and the dependency injection pattern, 2004. https://martinfowler. com/articles/injection.html {accessed 12 March 17}.

[12]

Martin Fowler. Domain-specific languages. Pearson Education, 2010.

Digital Library

[13]

Gordon Fraser and Andrea Arcuri. Evosuite: automatic test suite generation for object-oriented software. In Proceedings FSE’11. ACM, 2011.

Digital Library

[14]

Chris Frohoff. ysoserial – A proof-of-concept tool for generating payloads that exploit unsafe Java object deserialization, 2016.

[15]

https://github.com/frohoff/ysoserial {accessed 16 March 17}.

[16]

Kamil Jezek and Jens Dietrich. Magic with dynamo–flexible cross-component linking for java with invokedynamic. In Proceedings ECOOP’16. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.

[17]

Franz Kafka. The metamorphosis. WW Norton & Company, 2015.

[18]

Gregor Kiczales, John Lamping, Anurag Mendhekar, Chris Maeda, Cristina Lopes, Jean-Marc Loingtier, and John Irwin. Aspect-oriented programming. In Proceedings ECOOP’97. Springer, 1997.

[19]

Davy Landman, Alexander Serebrenik, and Jurgen Vinju. Challenges for static analysis of java reflection – literature review and empirical study. In Proceedings ICSE’17. ACM, 2017.

Digital Library

[20]

Benjamin Livshits, Manu Sridharan, Yannis Smaragdakis, Ondrej Lhoták, José Nelson Amaral, Bor-Yuh Evan Chang, Samuel Z Guyer, Uday P Khedker, Anders Møller, and Dimitrios Vardoulakis. In defense of soundiness: a manifesto. Commun. ACM, 58(2):44–46, 2015.

Digital Library

[21]

Benjamin Livshits, John Whaley, and Monica S. Lam. Reflection analysis for java. In Proceedings APLAS’05. Springer, 2005.

Digital Library

[22]

Luis Mastrangelo, Luca Ponzanelli, Andrea Mocci, Michele Lanza, Matthias Hauswirth, and Nathaniel Nystrom. Use at your own risk: the java unsafe api in the wild. In Proceedings OOPSLA’15. ACM, 2015.

Digital Library

[23]

Edward Miller and William E Howden. Tutorial: software testing & validation techniques. IEEE Computer Society Press, 1981.

[24]

Carlos Pacheco and Michael D Ernst. Randoop: feedbackdirected random testing for java. In Proceedings OOPSLA’07. ACM, 2007.

Digital Library

[25]

Olin Shivers. Control-flow analysis of higher-order languages. PhD thesis, Carnegie Mellon, 1991.

Digital Library

[26]

Yannis Smaragdakis, George Balatsouras, George Kastrinis, and Martin Bravenboer. More sound static handling of java reflection. In Proceedings APLAS’15. Springer, 2015.

[27]

Manu Sridharan, Shay Artzi, Marco Pistoia, Salvatore Guarnieri, Omer Tripp, and Ryan Berg. F4f: taint analysis of framework-based web applications. In Proceedings OOPSLA’11. ACM, 2011.

Digital Library

[28]

Nikolai Tillmann and Jonathan De Halleux. Pex–white box test generation for .net. In Proceedings TAP’08. Springer, 2008.

Digital Library

[29]

Raja Vallée-Rai, Phong Co, Etienne Gagnon, Laurie Hendren, Patrick Lam, and Vijay Sundaresan. Soot-a java bytecode optimization framework. In Proceedings CASCON’99. IBM, 1999.

Digital Library

Cited By

Ganz TRall PHärterich MRieck K(2023)Hunting for Truth: Analyzing Explanation Methods in Learning-based Vulnerability Discovery2023 IEEE 8th European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP57164.2023.00038(524-541)Online publication date: Jul-2023
https://doi.org/10.1109/EuroSP57164.2023.00038
Sui LRasheed STahir ADietrich JRastogi ATufano RBavota GArnaoudova VHaiduc S(2022)A study of single statement bugs involving dynamic language featuresProceedings of the 30th IEEE/ACM International Conference on Program Comprehension10.1145/3524610.3527883(494-498)Online publication date: 16-May-2022
https://dl.acm.org/doi/10.1145/3524610.3527883
Fourtounis GTriantafyllou LSmaragdakis YKhurshid SPăsăreanu C(2020)Identifying Java calls in native code via binary scanningProceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3395363.3397368(388-400)Online publication date: 18-Jul-2020
https://dl.acm.org/doi/10.1145/3395363.3397368
Show More Cited By

Index Terms

On the construction of soundness oracles
1. Software and its engineering
  1. Software organization and properties
    1. Software functional properties
      1. Formal methods
        Automated static analysis
        Dynamic analysis

Recommendations

Systematic approaches for increasing soundness and precision of static analyzers
SOAP 2017: Proceedings of the 6th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis

Building static analyzers for modern programming languages is difficult. Often soundness is a requirement, perhaps with some well-defined exceptions, and precision must be adequate for producing useful results on realistic input programs. Formally ...
On the unsoundness of static analysis for Android GUIs
SOAP 2016: Proceedings of the 5th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis

Android software presents exciting new challenges for the static analysis community. However, static analyses for Android are typically unsound. This is due to the lack of specification of the Android framework, the continuous evolution of framework ...
Testing static analyses for precision and soundness
CGO '20: Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization

Static analyses compute properties of programs that are true in all executions, and compilers use these properties to justify optimizations such as dead code elimination. Each static analysis in a compiler should be as precise as possible while remaining ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SOAP 2017: Proceedings of the 6th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis

June 2017

48 pages

ISBN:9781450350723

DOI:10.1145/3088515

General Chairs:
Karim Ali
University of Alberta, Canada
,
Cristina Cifuentes
Oracle Labs, Australia

Copyright © 2017 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

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 June 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PLDI '17

Sponsor:

SIGPLAN

PLDI '17: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 18, 2017

Barcelona, Spain

Acceptance Rates

Overall Acceptance Rate 11 of 11 submissions, 100%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
136
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ganz TRall PHärterich MRieck K(2023)Hunting for Truth: Analyzing Explanation Methods in Learning-based Vulnerability Discovery2023 IEEE 8th European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP57164.2023.00038(524-541)Online publication date: Jul-2023
https://doi.org/10.1109/EuroSP57164.2023.00038
Sui LRasheed STahir ADietrich JRastogi ATufano RBavota GArnaoudova VHaiduc S(2022)A study of single statement bugs involving dynamic language featuresProceedings of the 30th IEEE/ACM International Conference on Program Comprehension10.1145/3524610.3527883(494-498)Online publication date: 16-May-2022
https://dl.acm.org/doi/10.1145/3524610.3527883
Fourtounis GTriantafyllou LSmaragdakis YKhurshid SPăsăreanu C(2020)Identifying Java calls in native code via binary scanningProceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3395363.3397368(388-400)Online publication date: 18-Jul-2020
https://dl.acm.org/doi/10.1145/3395363.3397368
Sui LDietrich JTahir AFourtounis GRothermel GBae D(2020)On the recall of static call graph construction in practiceProceedings of the ACM/IEEE 42nd International Conference on Software Engineering10.1145/3377811.3380441(1049-1060)Online publication date: 27-Jun-2020
https://dl.acm.org/doi/10.1145/3377811.3380441
Palsberg JLopes CDolby JHalfond WMishra A(2018)NJRCompanion Proceedings for the ISSTA/ECOOP 2018 Workshops10.1145/3236454.3236501(100-106)Online publication date: 16-Jul-2018
https://dl.acm.org/doi/10.1145/3236454.3236501
Sui LDietrich JEmery MRasheed STahir A(2018)On the Soundness of Call Graph Construction in the Presence of Dynamic Language Features - A Benchmark and Tool EvaluationProgramming Languages and Systems10.1007/978-3-030-02768-1_4(69-88)Online publication date: 22-Oct-2018
https://doi.org/10.1007/978-3-030-02768-1_4
Sui LDietrich JTahir A(2017)On the Use of Mined Stack Traces to Improve the Soundness of Statically Constructed Call Graphs2017 24th Asia-Pacific Software Engineering Conference (APSEC)10.1109/APSEC.2017.83(672-676)Online publication date: Dec-2017
https://doi.org/10.1109/APSEC.2017.83

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