research-article

Randomized stress-testing of link-time optimizers

Authors:

Zhendong SuAuthors Info & Claims

ISSTA 2015: Proceedings of the 2015 International Symposium on Software Testing and Analysis

Pages 327 - 337

https://doi.org/10.1145/2771783.2771785

Published: 13 July 2015 Publication History

Abstract

Link-time optimization (LTO) is an increasingly important and adopted modern optimization technology. It is currently supported by many production compilers, including GCC, LLVM, and Microsoft Visual C/C++. Despite its complexity, but because it is more recent, LTO is relatively less tested compared to the more mature, traditional optimizations. To evaluate and help improve the quality of LTO, we present the first extensive effort to stress-test the LTO components of GCC and LLVM, the two most widely-used production C compilers. In 11 months, we have discovered and reported 37 bugs (12 in GCC; 25 in LLVM). Developers have confirmed 21 of our bugs, and fixed 11 of them. Our core technique is differential testing and realized in the tool Proteus. We leverage existing compiler testing tools (Csmith and Orion) to generate single-file test programs and address two important challenges specific for LTO testing. First, to thoroughly exercise LTO, Proteus automatically transforms a single-file program into multiple compilation units and stochastically assigns each an optimization level. Second, for effective bug reporting, we develop a practical mechanism to reduce LTO bugs involving multiple files. Our results clearly demonstrate Proteus’s utility; we plan to make ours a continuous effort in validating link-time optimizers.

References

[1]

ACE. SuperTest compiler test and validation suite. http://www.ace.nl/compiler/supertest.html.

[2]

B. Anckaert, F. Vandeputte, B. Bus, B. Sutter, and K. Bosschere. Link-time optimization of ia64 binaries. In M. Danelutto, M. Vanneschi, and D. Laforenza, editors, Euro-Par 2004 Parallel Processing, volume 3149 of Lecture Notes in Computer Science, pages 284–291. Springer Berlin Heidelberg, 2004.

[3]

A. Balestrat. CCG: A random C code generator. https://github.com/Merkil/ccg/.

[4]

Y. Chen, A. Groce, C. Zhang, W.-K. Wong, X. Fern, E. Eide, and J. Regehr. Taming compiler fuzzers. In Proceedings of the 2013 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 197–208, 2013.

Digital Library

[5]

B. De Sutter, L. Van Put, D. Chanet, B. De Bus, and K. De Bosschere. Link-time compaction and optimization of arm executables. ACM Trans. Embed. Comput. Syst., 6(1), Feb. 2007.

Digital Library

[6]

GCC Wiki. Finding miscompilations on large testcases. http://gcc.gnu.org/wiki/Analysing_Large_Testcases/.

[7]

A. Groce, C. Zhang, E. Eide, Y. Chen, and J. Regehr. Swarm testing. In International Symposium on Software Testing and Analysis (ISSTA), pages 78–88, 2012.

Digital Library

[8]

V. Le, M. Afshari, and Z. Su. Compiler validation via equivalence modulo inputs. In Proceedings of the 2014 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2014.

Digital Library

[9]

X. Leroy. Formal certification of a compiler back-end, or: programming a compiler with a proof assistant. In Proceedings of the 33rd ACM Symposium on Principles of Programming Languages (POPL), pages 42–54. ACM Press, 2006.

Digital Library

[10]

X. Leroy. A formally verified compiler back-end. Journal of Automated Reasoning, 43(4):363–446, 2009.

Digital Library

[11]

G. Malecha, G. Morrisett, A. Shinnar, and R. Wisnesky. Toward a verified relational database management system. In Proceedings of the 37th ACM SIGPLANSIGACT Symposium on Principles of Programming Languages, pages 237–248, 2010.

Digital Library

[12]

W. M. McKeeman. Differential testing for software. Digital Technical Journal, 10(1):100–107, 1998.

[13]

S. McPeak, D. S. Wilkerson, and S. Goldsmith. Berkeley Delta. http://delta.tigris.org/.

[14]

E. Nagai, H. Awazu, N. Ishiura, and N. Takeda. Random testing of C compilers targeting arithmetic optimization. In Workshop on Synthesis And System Integration of Mixed Information Technologies (SASIMI 2012), pages 48–53, 2012.

[15]

E. Nagai, A. Hashimoto, and N. Ishiura. Scaling up size and number of expressions in random testing of arithmetic optimization of C compilers. In Workshop on Synthesis And System Integration of Mixed Information Technologies (SASIMI 2013), pages 88–93, 2013.

[16]

G. C. Necula. Translation validation for an optimizing compiler. In Proceedings of the 2000 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 83–94, 2000.

Digital Library

[17]

Plum Hall, Inc. The Plum Hall Validation Suite for C. http://www.plumhall.com/stec.html.

[18]

A. Pnueli, M. Siegel, and E. Singerman. Translation validation. In Proceedings of the 4th International Conference on Tools and Algorithms for Construction and Analysis of Systems (TACAS), pages 151–166, London, UK, UK, 1998. Springer-Verlag.

Digital Library

[19]

J. Regehr, Y. Chen, P. Cuoq, E. Eide, C. Ellison, and X. Yang. Test-case reduction for C compiler bugs. In Proceedings of the 2012 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 335–346, 2012.

Digital Library

[20]

H. Samet. Automatically proving the correctness of translations involving optimized code. Phd thesis, Stanford University, May 1975.

Digital Library

[21]

R. Tate, M. Stepp, Z. Tatlock, and S. Lerner. Equality saturation: a new approach to optimization. In Proceedings of the 36th ACM SIGPLAN-SIGACT symposium on Principles of Programming Languages, pages 264–276, 2009.

Digital Library

[22]

The Clang Team. Clang 3.4 documentation: Libtooling. http://clang.llvm.org/docs/LibTooling.html.

[23]

J.-B. Tristan, P. Govereau, and G. Morrisett. Evaluating value-graph translation validation for LLVM. In Proceedings of the 2011 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 295–305, 2011.

Digital Library

[24]

J.-B. Tristan and X. Leroy. Formal verification of translation validators: A case study on instruction scheduling optimizations. In Proceedings of the 35th ACM Symposium on Principles of Programming Languages (POPL), pages 17–27. ACM Press, Jan. 2008.

Digital Library

[25]

X. Yang, Y. Chen, E. Eide, and J. Regehr. Finding and understanding bugs in C compilers. In Proceedings of the 2011 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 283–294, 2011.

Digital Library

[26]

J. Zhao, S. Nagarakatte, M. M. K. Martin, and S. Zdancewic. Formal verification of SSA-based optimizations for LLVM. In Proceedings of the 2013 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 175–186, 2013.

Digital Library

Cited By

Kim HKim SLee JCha SChristakis MPradel M(2024)AsFuzzer: Differential Testing of Assemblers with Error-Driven Grammar InferenceProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680345(1099-1111)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680345
Xia XFeng YShi QJones JZhang XXu B(2024)Enumerating Valid Non-Alpha-Equivalent Programs for Interpreter TestingACM Transactions on Software Engineering and Methodology10.1145/364799433:5(1-31)Online publication date: 4-Jun-2024
https://dl.acm.org/doi/10.1145/3647994
Sotiropoulos TChaliasos SSu Z(2024)API-Driven Program Synthesis for Testing Static Typing ImplementationsProceedings of the ACM on Programming Languages10.1145/36329048:POPL(1850-1881)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632904
Show More Cited By

Index Terms

Randomized stress-testing of link-time optimizers
1. Information systems
  1. Information retrieval
  2. Information storage systems
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging
  2. Software notations and tools
    1. General programming languages
      1. Language types

Recommendations

Finding compiler bugs via live code mutation
OOPSLA 2016: Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications

Validating optimizing compilers is challenging because it is hard to generate valid test programs (i.e., those that do not expose any undefined behavior). Equivalence Modulo Inputs (EMI) is an effective, promising methodology to tackle this problem. ...
Random testing for C and C++ compilers with YARPGen

Compilers should not crash and they should not miscompile applications. Random testing is an effective method for finding compiler bugs that have escaped other kinds of testing. This paper presents Yet Another Random Program Generator (YARPGen), a random ...
Taming compiler fuzzers
PLDI '13

Aggressive random testing tools ("fuzzers") are impressively effective at finding compiler bugs. For example, a single test-case generator has resulted in more than 1,700 bugs reported for a single JavaScript engine. However, fuzzers can be frustrating ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSTA 2015: Proceedings of the 2015 International Symposium on Software Testing and Analysis

July 2015

447 pages

ISBN:9781450336208

DOI:10.1145/2771783

General Chair:
Michal Young
University of Oregon, USA
,
Program Chair:
Tao Xie
University of Illinois at Urbana-Champaign, USA

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

SIGSOFT: ACM Special Interest Group on Software Engineering

In-Cooperation

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

ISSTA '15

Sponsor:

SIGSOFT

ISSTA '15: International Symposium on Software Testing and Analysis

July 13 - 17, 2015

MD, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 58 of 213 submissions, 27%

Upcoming Conference

ISSTA '25

Sponsor:
sigsoft

34th ACM SIGSOFT International Symposium on Software Testing and Analysis

June 25 - 28, 2025

Trondheim , Norway

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

42
Total Citations
View Citations
327
Total Downloads

Downloads (Last 12 months)25
Downloads (Last 6 weeks)4

Reflects downloads up to 06 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kim HKim SLee JCha SChristakis MPradel M(2024)AsFuzzer: Differential Testing of Assemblers with Error-Driven Grammar InferenceProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680345(1099-1111)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680345
Xia XFeng YShi QJones JZhang XXu B(2024)Enumerating Valid Non-Alpha-Equivalent Programs for Interpreter TestingACM Transactions on Software Engineering and Methodology10.1145/364799433:5(1-31)Online publication date: 4-Jun-2024
https://dl.acm.org/doi/10.1145/3647994
Sotiropoulos TChaliasos SSu Z(2024)API-Driven Program Synthesis for Testing Static Typing ImplementationsProceedings of the ACM on Programming Languages10.1145/36329048:POPL(1850-1881)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632904
Jiang HWang ZZhou ZLi XGuo SSun WZhang T(2024)A Testing Program and Pragma Combination Selection Based Framework for High-Level Synthesis Tool Pragma-Related Bug DetectionIEEE Transactions on Software Engineering10.1109/TSE.2024.336855350:4(937-955)Online publication date: Apr-2024
https://doi.org/10.1109/TSE.2024.3368553
Li XGuo SCheng HJiang H(2024)Simulink Compiler Testing via Configuration Diversification With Reinforcement LearningIEEE Transactions on Reliability10.1109/TR.2023.331764373:2(1060-1074)Online publication date: Jun-2024
https://doi.org/10.1109/TR.2023.3317643
Zheng YDou WTang LCui ZSong JCheng ZWang WWei JZhong HHuang T(2024)Differential Optimization Testing of Gremlin-Based Graph Database Systems2024 IEEE Conference on Software Testing, Verification and Validation (ICST)10.1109/ICST60714.2024.00012(25-36)Online publication date: 27-May-2024
https://doi.org/10.1109/ICST60714.2024.00012
Xu JLu KDu ZDing ZLi LWu QPayer MMao BCalandrino JTroncoso C(2023)Silent bugs matterProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620442(3655-3672)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620442
Yang YSun MWang YLi QWen MZhou YChandra SBlincoe KTonella P(2023)Heterogeneous Testing for Coverage Profilers Empowered with Debugging SupportProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616340(670-681)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616340
Wang TTian YDong YXu ZSun CAamodt TJerger NSwift M(2023)Compilation Consistency Modulo Debug InformationProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3575693.3575740(146-158)Online publication date: 27-Jan-2023
https://dl.acm.org/doi/10.1145/3575693.3575740
Tu HJiang HZhou ZTang YRen ZQiao LJiang L(2023)Detecting C++ Compiler Front-End Bugs via Grammar Mutation and Differential TestingIEEE Transactions on Reliability10.1109/TR.2022.317122072:1(343-357)Online publication date: Mar-2023
https://doi.org/10.1109/TR.2022.3171220
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