research-article

Open access

Program Reconditioning: Avoiding Undefined Behaviour When Finding and Reducing Compiler Bugs

Authors:

Bastien Lecoeur,

Alastair F. DonaldsonAuthors Info & Claims

Proceedings of the ACM on Programming Languages, Volume 7, Issue PLDI

Article No.: 180, Pages 1801 - 1825

https://doi.org/10.1145/3591294

Published: 06 June 2023 Publication History

Abstract

We introduce program reconditioning, a method for allowing program generation and differential testing to be used to find miscompilation bugs, and test-case reduction to be used to simplify bug-triggering programs, even when (a) the programming language of interest features undefined behaviour (UB) and (b) no tools exist to detect and avoid this UB. We present two program generation tools based on our reconditioning idea: GLSLsmith for the OpenGL Shading Language (GLSL), a widely-used language for graphics programming, and WGSLsmith for the WebGPU Shading Language (WGSL), a new language for web-based graphics rendering. GLSL features many UBs, but unlike for languages such as C and C++ no tools exist to detect them automatically. While the WGSL language specification features very limited UB, early WGSL implementations do exhibit UB, for reasons of initial implementation simplicity, making it challenging to test them to quickly detect and eliminate unrelated miscompilation bugs. Thanks to reconditioning, we show that GLSLsmith and WGSLsmith allow differential testing and test-case reduction to be applied to compilers for GLSL and WGSL for the first time, despite the unavailability of UB detection techniques for these languages. Through a large testing campaign, we have found 24 and 33 bugs in GLSL and WGSL compilers, respectively. We present experiments showing that when reconditioning is disabled, compiler testing leads to a high rate of test programs that appear to trigger miscompilation bugs, but actually just feature UB. We also present a novel approach to managing floating-point roundoff error using reconditioning, implemented for both GLSL and WGSL.

References

[1]

Apple. 2022. Metal Shading Language Specification. https://developer.apple.com/metal/Metal-Shading-Language-Specification.pdf

[2]

Apple. 2023. Metal. https://developer.apple.com/metal/

[3]

C-Reduce Project. 2023. Using C-Reduce. https://embed.cs.utah.edu/creduce/using/

[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]

Junjie Chen, Guancheng Wang, Dan Hao, Yingfei Xiong, Hongyu Zhang, and Lu Zhang. 2019. History-Guided Configuration Diversification for Compiler Test-Program Generation. In 34th IEEE/ACM International Conference on Automated Software Engineering, ASE 2019, San Diego, CA, USA, November 11-15, 2019. IEEE, 305–316. https://doi.org/10.1109/ASE.2019.00037

Digital Library

[6]

Junjie Chen, Guancheng Wang, Dan Hao, Yingfei Xiong, Hongyu Zhang, Lu Zhang, and Bing Xie. 2021. Coverage Prediction for Accelerating Compiler Testing. IEEE Trans. Software Eng., 47, 2 (2021), 261–278. https://doi.org/10.1109/TSE.2018.2889771

Digital Library

[7]

T.Y. Chen, S.C. Cheung, and S.M. Yiu. 1998. Metamorphic Testing: a New Approach for Generating Next Test Cases. Department of Computer Science, The Hong Kong University of Science and Technology.

[8]

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

[9]

Pascal Cuoq, Florent Kirchner, Nikolai Kosmatov, Virgile Prevosto, Julien Signoles, and Boris Yakobowski. 2012. Frama-C - A Software Analysis Perspective. In Software Engineering and Formal Methods - 10th International Conference, SEFM 2012, Thessaloniki, Greece, October 1-5, 2012. Proceedings, George Eleftherakis, Mike Hinchey, and Mike Holcombe (Eds.) (Lecture Notes in Computer Science, Vol. 7504). Springer, 233–247. https://doi.org/10.1007/978-3-642-33826-7_16

Digital Library

[10]

Alastair F. Donaldson, Ben Clayton, Ryan Harrison, Hasan Mohsin, David Neto, Vasyl Teliman, and Hana Watson. 2023. Industrial Deployment of Compiler Fuzzing Techniques for Two GPU Shading Languages. In Proceedings of the 16th IEEE International Conference on Software Testing, Verification and Validation, ICST 2023, Dublin, Ireland, June 16-20, 2023. IEEE. To appear

[11]

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

[12]

Alastair F. Donaldson, Paul Thomson, Vasyl Teliman, Stefano Milizia, André Perez Maselco, and Antoni Karpinski. 2021. Test-case reduction and deduplication almost for free with transformation-based compiler testing. In PLDI ’21: 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, Virtual Event, Canada, June 20-25, 20211, Stephen N. Freund and Eran Yahav (Eds.). ACM, 1017–1032. https://doi.org/10.1145/3453483.3454092

Digital Library

[13]

Karine Even-Mendoza, Cristian Cadar, and Alastair F. Donaldson. 2020. Closer to the Edge: Testing Compilers More Thoroughly by Being Less Conservative About Undefined Behaviour. In 35th IEEE/ACM International Conference on Automated Software Engineering, ASE 2020, Melbourne, Australia, September 21-25, 2020. IEEE, 1219–1223. https://doi.org/10.1145/3324884.3418933

Digital Library

[14]

Karine Even-Mendoza, Cristian Cadar, and Alastair F. Donaldson. 2022. CsmithEdge: more effective compiler testing by handling undefined behaviour less conservatively. Empir. Softw. Eng., 27, 6 (2022), 129. https://doi.org/10.1007/s10664-022-10146-1

Digital Library

[15]

Freedesktop.org. 2021. Miscompilation of a switch case. https://gitlab.freedesktop.org/mesa/mesa/-/issues/5185

[16]

Google. 2023. ANGLE. https://opensource.google/projects/angle

[17]

Google. 2023. Dawn, a WebGPU implementation. https://dawn.googlesource.com/dawn/+/refs/heads/main/README.md

[18]

Google. 2023. ShaderTrap GitHub repository. https://github.com/google/shadertrap

[19]

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

[20]

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

[21]

Yann Herklotz and John Wickerson. 2020. Finding and Understanding Bugs in FPGA Synthesis Tools. In FPGA ’20: The 2020 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, Seaside, CA, USA, February 23-25, 2020, Stephen Neuendorffer and Lesley Shannon (Eds.). ACM, 277–287. https://doi.org/10.1145/3373087.3375310

Digital Library

[22]

IEEE. 1985. IEEE Standard for Binary Floating-Point Arithmetic.

[23]

2019. The OpenGL Shading Language Version 4.60.7, John Kessenich (Ed.). Khronos Group. https://www.khronos.org/registry/OpenGL/specs/gl/GLSLangSpec.4.60.pdf

[24]

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

[25]

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

[26]

Khronos Group. 2023. The OpenCL Specification. https://registry.khronos.org/OpenCL/specs/3.0-unified/pdf/OpenCL_API.pdf

[27]

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

[28]

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

[29]

Bastien Lecoeur. 2023. GLSLsmith GitHub repository. https://github.com/AaronGhost/glslsmith

[30]

Bastien Lecoeur, Hasan Mohsin, and Alastair F. Donaldson. 2023. Artifact for “Program Reconditioning: Avoiding Undefined Behaviour When Finding and Reducing Compiler Bugs”, PLDI 2023. https://doi.org/10.5281/zenodo.7819755

Digital Library

[31]

2019. OpenGL ES Version 3.2, Jon Leech (Ed.). Khronos Group. https://www.khronos.org/registry/OpenGL/specs/es/3.2/es_spec_3.2.pdf

[32]

Xavier Leroy. 2023. The CompCert C verified compiler: Documentation and user’s manual. https://compcert.org/man/manual004.html

[33]

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

[34]

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

[35]

LLVM. 2023. UndefinedBehaviorSanitizer. https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html

[36]

William M. McKeeman. 1998. Differential Testing for Software. Digital Technical Journal, 10, 1 (1998), 100–107.

[37]

Microsoft. 2019. Reference for HLSL. https://docs.microsoft.com/en-us/windows/win32/direct3dhlsl/dx-graphics-hlsl-reference

[38]

Microsoft. 2021. Direct3D 12 graphics. https://learn.microsoft.com/en-us/windows/win32/direct3d12/direct3d-12-graphics

[39]

Ghassan Misherghi and Zhendong Su. 2006. HDD: hierarchical Delta Debugging. In 28th International Conference on Software Engineering (ICSE 2006), Shanghai, China, May 20-28, 2006, Leon J. Osterweil, H. Dieter Rombach, and Mary Lou Soffa (Eds.). ACM, 142–151. isbn:1-59593-375-1 https://doi.org/10.1145/1134285.1134307

Digital Library

[40]

Hasan Mohsin. 2023. WGSLsmith GitHub repository. https://github.com/wgslsmith/wgslsmith

[41]

Eriko Nagai, Atsushi Hashimoto, and Nagisa Ishiura. 2014. Reinforcing Random Testing of Arithmetic Optimization of C Compilers by Scaling up Size and Number of Expressions. IPSJ Trans. Syst. LSI Des. Methodol., 7 (2014), 91–100. https://doi.org/10.2197/ipsjtsldm.7.91

[42]

Nvidia. 2021. CUDA C++ Programming Guide, Version 11.2.1. https://docs.nvidia.com/cuda/archive/11.2.1/cuda-c-programming-guide/

[43]

Terence Parr. 2023. ANTLR. https://www.antlr.org/

[44]

pest project authors. 2023. pest. The Elegant Parser. https://github.com/pest-parser/pest

[45]

Moritz Pflanzer, Alastair F. Donaldson, and Andrei Lascu. 2016. Automatic Test Case Reduction for OpenCL. In Proceedings of the 4th International Workshop on OpenCL, IWOCL 2016, Vienna, Austria, April 19-21, 2016. ACM, 1:1–1:12. https://doi.org/10.1145/2909437.2909439

Digital Library

[46]

Picire Project. 2012. Picire: Parallel Delta Debugging Framework. https://github.com/renatahodovan/picire

[47]

John Regehr. 2012. Responsible and Effective Bugfinding. https://blog.regehr.org/archives/1679

[48]

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

[49]

Rust Graphics Mages. 2022. Invalid result when using implicitly initialized array. https://github.com/gfx-rs/naga/issues/1748

[50]

Rust Graphics Mages. 2023. The wgpu project. https://github.com/gfx-rs/wgpu

[51]

2019. The OpenGL Graphics System: A Specification Version 4.6 (Core Profile), Mark Segal and Kurt Akeley (Eds.). Khronos Group. https://www.khronos.org/registry/OpenGL/specs/gl/glspec46.core.pdf

[52]

Konstantin Serebryany, Derek Bruening, Alexander Potapenko, and Dmitriy Vyukov. 2012. AddressSanitizer: A Fast Address Sanity Checker. In 2012 USENIX Annual Technical Conference, Boston, MA, USA, June 13-15, 2012, Gernot Heiser and Wilson C. Hsieh (Eds.). USENIX Association, 309–318. https://www.usenix.org/conference/atc12/technical-sessions/presentation/serebryany

Digital Library

[53]

2019. The OpenGL ES Shading Language Version 3.20.6, Robert J. Simpson and John Kessenich (Eds.). Khronos Group. https://www.khronos.org/registry/OpenGL/specs/es/3.2/GLSL_ES_Specification_3.20.pdf

[54]

Tyler Sorensen and Alastair F. Donaldson. 2016. The Hitchhiker’s Guide to Cross-Platform OpenCL Application Development. In Proceedings of the 4th International Workshop on OpenCL, IWOCL 2016, Vienna, Austria, April 19-21, 2016. ACM, 2:1–2:12. https://doi.org/10.1145/2909437.2909440

Digital Library

[55]

Evgeniy Stepanov and Konstantin Serebryany. 2015. MemorySanitizer: fast detector of uninitialized memory use in C++. In Proceedings of the 13th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2015, San Francisco, CA, USA, February 07 - 11, 2015, Kunle Olukotun, Aaron Smith, Robert Hundt, and Jason Mars (Eds.). IEEE Computer Society, 46–55. https://doi.org/10.1109/CGO.2015.7054186

[56]

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

[57]

Chengnian Sun, Yuanbo Li, Qirun Zhang, Tianxiao Gu, and Zhendong Su. 2018. Perses: syntax-guided program reduction. In Proceedings of the 40th International Conference on Software Engineering, ICSE 2018, Gothenburg, Sweden, May 27 - June 03, 2018, Michel Chaudron, Ivica Crnkovic, Marsha Chechik, and Mark Harman (Eds.). ACM, 361–371. https://doi.org/10.1145/3180155.3180236

Digital Library

[58]

W3C. 2023. WebGPU Shading Language W3C Working Draft. https://www.w3.org/TR/WGSL/

[59]

W3C. 2023. WebGPU W3C Working Draft. https://www.w3.org/TR/webgpu/

[60]

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

[61]

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

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
Chen HFilkov VRay BZhou M(2024)Efficient Code Causes Inefficiency in Compiler OptimizationsProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695369(2426-2428)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695369
Tan JRigger MChristakis MPradel M(2024)Inconsistencies in TeX-Produced DocumentsProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680370(1415-1427)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680370
Show More Cited By

Index Terms

Program Reconditioning: Avoiding Undefined Behaviour When Finding and Reducing Compiler Bugs
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

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 ...
Taming compiler fuzzers
PLDI '13: Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation

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 ...
Toward understanding compiler bugs in GCC and LLVM
ISSTA 2016: Proceedings of the 25th International Symposium on Software Testing and Analysis

Compilers are critical, widely-used complex software. Bugs in them have significant impact, and can cause serious damage when they silently miscompile a safety-critical application. An in-depth understanding of compiler bugs can help detect and fix ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Programming Languages

Proceedings of the ACM on Programming Languages Volume 7, Issue PLDI

June 2023

2020 pages

EISSN:2475-1421

DOI:10.1145/3554310

Editor:
Michael Hicks
Amazon, USA

Issue’s Table of Contents

Copyright © 2023 Owner/Author.

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2023

Published in PACMPL Volume 7, Issue PLDI

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
533
Total Downloads

Downloads (Last 12 months)371
Downloads (Last 6 weeks)65

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
Chen HFilkov VRay BZhou M(2024)Efficient Code Causes Inefficiency in Compiler OptimizationsProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695369(2426-2428)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695369
Tan JRigger MChristakis MPradel M(2024)Inconsistencies in TeX-Produced DocumentsProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680370(1415-1427)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680370
Suo CChen JLiu SJiang JZhao YWang JChristakis MPradel M(2024)Fuzzing MLIR Compiler Infrastructure via Operation Dependency AnalysisProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680360(1287-1299)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680360
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
Tian YZhang XDong YXu ZZhang MJiang YCheung SSun C(2023)On the Caching Schemes to Speed Up Program ReductionACM Transactions on Software Engineering and Methodology10.1145/361717233:1(1-30)Online publication date: 24-Nov-2023
https://dl.acm.org/doi/10.1145/3617172

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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents