research-article

Open access

Test-case reduction and deduplication almost for free with transformation-based compiler testing

Authors:

Alastair F. Donaldson,

Stefano Milizia,

André Perez Maselco,

Antoni KarpińskiAuthors Info & Claims

PLDI 2021: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation

Pages 1017 - 1032

https://doi.org/10.1145/3453483.3454092

Published: 18 June 2021 Publication History

Abstract

Recent transformation-based approaches to compiler testing look for mismatches between the results of pairs of equivalent programs, where one program is derived from the other by randomly applying semantics-preserving transformations. We present a formulation of transformation-based compiler testing that provides effective test-case reduction almost for free: if transformations are designed to be as small and independent as possible, standard delta debugging can be used to shrink a bug-inducing transformation sequence to a smaller subsequence that still triggers the bug. The bug can then be reported as a delta between an original and minimally-transformed program. Minimized transformation sequences can also be used to heuristically deduplicate a set of bug-inducing tests, recommending manual investigation of those that involve disparate types of transformations and thus may have different root causes. We demonstrate the effectiveness of our approach via a new tool, spirv-fuzz, the first compiler-testing tool for the SPIR-V intermediate representation that underpins the Vulkan GPU programming model.

References

[1]

On a Test of Whether One of Two Random Variables is Stochastically Larger Than The Other. 1947. H.B. Mann and D.R. Whitney. Annals of Mathematical Statistics, 18 (1947), 50–60. https://doi.org/10.1214/aoms/1177730491

[2]

Android Authority. 2019. Qualcomm will let you update GPU drivers via the Play Store. https://www.androidauthority.com/qualcomm-gpu-driver-updates-1063096/

[3]

Junjie Chen, Wenxiang Hu, Dan Hao, Yingfei Xiong, Hongyu Zhang, Lu Zhang, and Bing Xie. 2016. An empirical comparison of compiler testing techniques. In Proceedings of the 38th International Conference on Software Engineering, ICSE 2016, Austin, TX, USA, May 14-22, 2016, Laura K. Dillon, Willem Visser, and Laurie Williams (Eds.). ACM, 180–190. isbn:978-1-4503-3900-1 https://doi.org/10.1145/2884781.2884878

Digital Library

[4]

Junjie Chen, Jibesh Patra, Michael Pradel, Yingfei Xiong, Hongyu Zhang, Dan Hao, and Lu Zhang. 2020. A Survey of Compiler Testing. ACM Comput. Surv., 53, 1 (2020), 4:1–4:36. https://doi.org/10.1145/3363562

Digital Library

[5]

Yang Chen, Alex Groce, Chaoqiang Zhang, Weng-Keen Wong, Xiaoli Z. Fern, Eric Eide, and John Regehr. 2013. Taming compiler fuzzers. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’13, Seattle, WA, USA, June 16-19, 2013, Hans-Juergen Boehm and Cormac Flanagan (Eds.). ACM, 197–208. isbn:978-1-4503-2014-6 https://doi.org/10.1145/2491956.2462173

Digital Library

[6]

Alastair Donaldson. 2019. GraphicsFuzz pull request: Fix issue where the reducer was replacing a dead code injection with its body. https://github.com/google/graphicsfuzz/pull/599

[7]

Alastair F. Donaldson, Hugues Evrard, Andrei Lascu, and Paul Thomson. 2017. Automated testing of graphics shader compilers. PACMPL, 1, OOPSLA (2017), 93:1–93:29. https://doi.org/10.1145/3133917

Digital Library

[8]

Alastair F. Donaldson, Hugues Evrard, and Paul Thomson. 2020. Putting Randomized Compiler Testing into Production (Experience Report). 22:1–22:29. isbn:978-3-95977-154-2 https://doi.org/10.4230/LIPIcs.ECOOP.2020.22

[9]

Freedesktop.org. 2021. The Mesa 3D Graphics Library. https://www.mesa3d.org/

[10]

Google. 2020. SwiftShader GitHub repository. https://github.com/google/SwiftShader

[11]

Google. 2021. Protocol Buffers. https://developers.google.com/protocol-buffers

[12]

GPUOpen Drivers. 2020. LLVM-Based Pipeline Compiler GitHub repository. https://github.com/GPUOpen-Drivers/llpc

[13]

GraphicsFuzz project authors. 2021. GraphicsFuzz. https://github.com/google/graphicsfuzz

[14]

GraphicsFuzz project authors. 2021. Script for extracting crash signatures. https://github.com/google/graphicsfuzz/blob/master/gfauto/gfauto/signature_util.py

[15]

The Khronos Vulkan Working Group. 2019. Vulkan 1.1.141 - A Specification (with all registered Vulkan extensions). The Khronos Group. https://www.khronos.org/registry/vulkan/specs/1.1-extensions/pdf/vkspec.pdf

[16]

2020. 34th European Conference on Object-Oriented Programming, ECOOP 2020, November 15-17, 2020, Berlin, Germany (Virtual Conference), Robert Hirschfeld and Tobias Pape (Eds.) (LIPIcs, Vol. 166). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. isbn:978-3-95977-154-2

[17]

2019. SPIR-V Specification, Version 1.5, Revision 2, Unified, John Kessenich, Boaz Ouriel, and Raun Krisch (Eds.). The Khronos Group. https://www.khronos.org/registry/spir-v/specs/unified1/SPIRV.pdf

[18]

Khronos Group. 2020. glslang GitHub repository. https://github.com/KhronosGroup/glslang

[19]

Khronos Group. 2020. Khronos Vulkan, OpenGL, and OpenGL ES Conformance Tests GitHub repository. https://github.com/KhronosGroup/VK-GL-CTS

[20]

Khronos Group. 2020. SPIR-V Tools GitHub repository. https://github.com/KhronosGroup/SPIRV-Tools

[21]

Andrei Lascu, Matt Windsor, Alastair F. Donaldson, Tobias Grosser, and John Wickerson. 2021. Dreaming up Metamorphic Relations: Experiences from Three Fuzzer Tools. In Proceedings of the 1st International Workshop on Metamorphic Testing, MET@ICSE 2021, Online, June 2, 2021. To appear.

[22]

Vu Le, Mehrdad Afshari, and Zhendong Su. 2014. Compiler validation via equivalence modulo inputs. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’14, Edinburgh, United Kingdom - June 09 - 11, 2014, Michael F. P. O’Boyle and Keshav Pingali (Eds.). ACM, 216–226. isbn:978-1-4503-2784-8 https://doi.org/10.1145/2594291.2594334

Digital Library

[23]

Vu Le, Chengnian Sun, and Zhendong Su. 2015. Finding deep compiler bugs via guided stochastic program mutation. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2015, part of SPLASH 2015, Pittsburgh, PA, USA, October 25-30, 2015, Jonathan Aldrich and Patrick Eugster (Eds.). ACM, 386–399. isbn:978-1-4503-3689-5 https://doi.org/10.1145/2814270.2814319

Digital Library

[24]

Xavier Leroy. 2009. A Formally Verified Compiler Back-end. J. Autom. Reason., 43, 4 (2009), 363–446. https://doi.org/10.1007/s10817-009-9155-4

Digital Library

[25]

Christopher Lidbury, Andrei Lascu, Nathan Chong, and Alastair F. Donaldson. 2015. Many-core compiler fuzzing. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, Portland, OR, USA, June 15-17, 2015, David Grove and Steve Blackburn (Eds.). ACM, 65–76. isbn:978-1-4503-3468-6 https://doi.org/10.1145/2737924.2737986

Digital Library

[26]

Vsevolod Livinskii, Dmitry Babokin, and John Regehr. 2020. Random testing for C and C++ compilers with YARPGen. Proc. ACM Program. Lang., 4, OOPSLA (2020), 196:1–196:25. https://doi.org/10.1145/3428264

Digital Library

[27]

Martin Liška. 2021. C-Vise. https://github.com/marxin/cvise

[28]

LLVM Project. 2021. libFuzzer – a library for coverage-guided fuzz testing. http://llvm.org/docs/LibFuzzer.html

[29]

David Maciver and Alastair F. Donaldson. 2020. Test-Case Reduction via Test-Case Generation: Insights from the Hypothesis Reducer (Tool Insights Paper). 13:1–13:27. isbn:978-3-95977-154-2 https://doi.org/10.4230/LIPIcs.ECOOP.2020.13

[30]

David R. MacIver, Zac Hatfield-Dodds, and Many Other Contributors. 2019. Hypothesis: A new approach to property-based testing. Journal of Open Source Software, 4, 43 (2019), 1891. https://doi.org/10.21105/joss.01891

[31]

John Regehr. 2020. Responsible and Effective Bugfinding. https://blog.regehr.org/archives/2037

[32]

John Regehr, Yang Chen, Pascal Cuoq, Eric Eide, Chucky Ellison, and Xuejun Yang. 2012. Test-case reduction for C compiler bugs. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’12, Beijing, China - June 11 - 16, 2012, Jan Vitek, Haibo Lin, and Frank Tip (Eds.). ACM, 335–346. isbn:978-1-4503-1205-9 https://doi.org/10.1145/2254064.2254104

Digital Library

[33]

Chengnian Sun, Vu Le, and Zhendong Su. 2016. Finding compiler bugs via live code mutation. In Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2016, part of SPLASH 2016, Amsterdam, The Netherlands, October 30 - November 4, 2016, Eelco Visser and Yannis Smaragdakis (Eds.). ACM, 849–863. isbn:978-1-4503-4444-9 https://doi.org/10.1145/2983990.2984038

Digital Library

[34]

The Khronos Group. 2021. source code. https://github.com/KhronosGroup/SPIRV-Tools#fuzzer

[35]

The LLVM compiler infrastructure. 2021. Clang Static Analyzer. https://clang-analyzer.llvm.org/

[36]

The LLVM compiler infrastructure. 2021. How to submit an LLVM bug report. https://llvm.org/docs/HowToSubmitABug.html

[37]

David B. Whalley. 1994. Automatic Isolation of Compiler Errors. ACM Trans. Program. Lang. Syst., 16, 5 (1994), 1648–1659. https://doi.org/10.1145/186025.186103

Digital Library

[38]

Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. 2011. Finding and understanding bugs in C compilers. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2011, San Jose, CA, USA, June 4-8, 2011, Mary W. Hall and David A. Padua (Eds.). ACM, 283–294. isbn:978-1-4503-0663-8 https://doi.org/10.1145/1993498.1993532

Digital Library

[39]

Michal Zalewski. 2014. Technical “whitepaper” for afl-fuzz. https://lcamtuf.coredump.cx/afl/technical_details.txt

[40]

Andreas Zeller and Ralf Hildebrandt. 2002. Simplifying and Isolating Failure-Inducing Input. IEEE Trans. Software Eng., 28, 2 (2002), 183–200. https://doi.org/10.1109/32.988498

Digital Library

[41]

Thomas Zimmermann, Rahul Premraj, Nicolas Bettenburg, Sascha Just, Adrian Schröter, and Cathrin Weiss. 2010. What Makes a Good Bug Report? IEEE Trans. Software Eng., 36, 5 (2010), 618–643. https://doi.org/10.1109/TSE.2010.63

Digital Library

Cited By

Gao FChen HZhou YWang KFilkov VRay BZhou M(2024)Shoot Yourself in the Foot — Efficient Code Causes Inefficiency in Compiler OptimizationsProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695548(1846-1857)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695548
Yang CDeng YLu RYao JLiu JJabbarvand RZhang L(2024)WhiteFox: White-Box Compiler Fuzzing Empowered by Large Language ModelsProceedings of the ACM on Programming Languages10.1145/36897368:OOPSLA2(709-735)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689736
Zhang MTian YXu ZDong YTan SSun CChristakis MPradel M(2024)LPR: Large Language Models-Aided Program ReductionProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3652126(261-273)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3652126
Show More Cited By

Index Terms

Test-case reduction and deduplication almost for free with transformation-based compiler testing
1. 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. Compilers

Recommendations

Fault detection effectiveness of source test case generation strategies for metamorphic testing
MET '18: Proceedings of the 3rd International Workshop on Metamorphic Testing

Metamorphic testing is a well known approach to tackle the oracle problem in software testing. This technique requires the use of source test cases that serve as seeds for the generation of follow-up test cases. Systematic design of test cases is ...
MD-ART: a test case generation method without test oracle problem
SCTDCP 2016: Proceedings of the 1st International Workshop on Specification, Comprehension, Testing, and Debugging of Concurrent Programs

Adaptive random testing (ART), as an improved random testing method, preserves the advantages of traditional random test method and overcomes the blindness of traditional random testing method. But it is usually not easy to validate the correctness of ...
Faster mutation testing inspired by test prioritization and reduction
ISSTA 2013: Proceedings of the 2013 International Symposium on Software Testing and Analysis

Mutation testing is a well-known but costly approach for determining test adequacy. The central idea behind the approach is to generate mutants, which are small syntactic transformations of the program under test, and then to measure for a given test ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI 2021: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation

June 2021

1341 pages

ISBN:9781450383912

DOI:10.1145/3453483

General Chair:
Stephen N. Freund
Williams College, USA
,
Program Chair:
Eran Yahav
Technion, Israel

Copyright © 2021 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

Engineering and Physical Sciences Research Council

Conference

PLDI '21

Sponsor:

SIGPLAN

PLDI '21: 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation

June 20 - 25, 2021

Virtual, Canada

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
1,214
Total Downloads

Downloads (Last 12 months)390
Downloads (Last 6 weeks)76

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gao FChen HZhou YWang KFilkov VRay BZhou M(2024)Shoot Yourself in the Foot — Efficient Code Causes Inefficiency in Compiler OptimizationsProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695548(1846-1857)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695548
Yang CDeng YLu RYao JLiu JJabbarvand RZhang L(2024)WhiteFox: White-Box Compiler Fuzzing Empowered by Large Language ModelsProceedings of the ACM on Programming Languages10.1145/36897368:OOPSLA2(709-735)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689736
Zhang MTian YXu ZDong YTan SSun CChristakis MPradel M(2024)LPR: Large Language Models-Aided Program ReductionProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3652126(261-273)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3652126
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
Donaldson ASheth DTristan JUsher A(2024)Randomised Testing of the Compiler for a Verification-Aware Programming Language2024 IEEE Conference on Software Testing, Verification and Validation (ICST)10.1109/ICST60714.2024.00044(407-418)Online publication date: 27-May-2024
https://doi.org/10.1109/ICST60714.2024.00044
Yang CChen JFan XJiang JSun JJust RFraser G(2023)Silent Compiler Bug De-duplication via Three-Dimensional AnalysisProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598087(677-689)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598087
Gharachorlu GSumner NJust RFraser G(2023)Type Batched Program ReductionProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598065(398-410)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598065
Lecoeur BMohsin HDonaldson A(2023)Program Reconditioning: Avoiding Undefined Behaviour When Finding and Reducing Compiler BugsProceedings of the ACM on Programming Languages10.1145/35912947:PLDI(1801-1825)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591294
Klimis VClark JBaker ANeto DWickerson JDonaldson A(2023)Taking Back Control in an Intermediate Representation for GPU ComputingProceedings of the ACM on Programming Languages10.1145/35712537:POPL(1740-1769)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571253
Donaldson AClayton BHarrison RMohsin HNeto DTeliman VWatson H(2023)Industrial Deployment of Compiler Fuzzing Techniques for Two GPU Shading Languages2023 IEEE Conference on Software Testing, Verification and Validation (ICST)10.1109/ICST57152.2023.00042(374-385)Online publication date: Apr-2023
https://doi.org/10.1109/ICST57152.2023.00042
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents