Differential Testing using Random Well-Typed Haskell Programs
Resumo
Haskell is a statically-typed, purely functional programming language with a strong academic foundation, widely recognized for its application in both research and industry for developing robust, high-assurance software. Nowadays, it is being adopted for a variety of projects, where applications reach a level of complexity where manual testing and human inspection are insufficient to ensure quality in software development. Even in the presence of automated unit testing, such methodologies infrequently encompass the entirety of significant code scenarios, which means that certain defects may remain undetected, particularly when the code is subjected to an identical set of validation criteria repetitively. Considering this context, this paper describes a type system guided algorithm to generate random and well-typed Haskell programs, which can be used for testing the compiler, development tools, and libraries.
Palavras-chave:
Code generation, Fuzzing, Haskell compiler, Differential Testing
Referências
Franco Bazzichi and Ippolito Spadafora. 1982. An automatic generator for compiler testing. IEEE Transactions on Software Engineering 4 (1982), 343–353.
Elton Maximo Cardoso, Daniel Freitas Pereira, Regina Sarah Monferrari Amorim De Paula, Leonardo Vieira Dos Santos Reis, and Rodrigo Geraldo Ribeiro. 2022. A Type-Directed Algorithm to Generate Random Well-Formed Parsing Expression Grammars. In Proceedings of the XXVI Brazilian Symposium on Programming Languages (, Virtual Event , Brazil , ) (SBLP ’22). Association for Computing Machinery, New York, NY, USA, 8–14. DOI: 10.1145/3561320.3561326
Augusto Celentano, S Crespi Reghizzi, P Della Vigna, Carlo Ghezzi, G Granata, and Florencia Savoretti. 1980. Compiler testing using a sentence generator. Software: Practice and Experience 10, 11 (1980), 897–918.
Koen Claessen and John Hughes. 2000. QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs. SIGPLAN Not. 35, 9 (sep 2000), 268–279. DOI: 10.1145/357766.351266
Chris Cummins, Pavlos Petoumenos, Alastair Murray, and Hugh Leather. 2018. Compiler Fuzzing through Deep Learning. In Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis (Amsterdam, Netherlands) (ISSTA 2018). Association for Computing Machinery, New York, NY, USA, 95–105. DOI: 10.1145/3213846.3213848
Dániel Drienyovszky, Dániel Horpácsi, and Simon Thompson. 2010. Quickchecking Refactoring Tools. In Proceedings of the 9th ACM SIGPLAN Workshop on Erlang (Baltimore, Maryland, USA) (Erlang ’10). ACM, New York, NY, USA, 75–80. DOI: 10.1145/1863509.1863521
Simon Marlow (Editor). 2010. Haskell 2010 Language Report. [link] Accessed: 2024-04-10.
Samuel Feitosa, Rodrigo Ribeiro, and Andre Du Bois. 2020. A type-directed algorithm to generate random well-typed Java 8 programs. Science of Computer Programming 196 (2020), 102494. DOI: 10.1016/j.scico.2020.102494
Samuel Feitosa, Rodrigo Ribeiro, and Andre Du Bois. 2020. A type-directed algorithm to generate random well-typed Java 8 programs. Science of Computer Programming 196 (2020), 102494. DOI: 10.1016/j.scico.2020.102494
Justin Frank, Benjamin Quiring, and Leonidas Lampropoulos. 2024. Generating Well-Typed Terms That Are Not “Useless”. Proc. ACM Program. Lang. 8, POPL, Article 77 (jan 2024), 22 pages. DOI: 10.1145/3632919
Andy Gill and Colin Runciman. 2007. Haskell Program Coverage. In Proceedings of the ACM SIGPLANWorkshop on HaskellWorkshop (Freiburg, Germany) (Haskell ’07). ACM, New York, NY, USA, 1–12. DOI: 10.1145/1291201.1291203
Jean-Yves Girard. 1986. The system F of variable types, fifteen years later. Theoretical Computer Science 45 (1986), 159–192. DOI: 10.1016/0304-3975(86)90044-7
Paul Hudak, John Hughes, Simon Peyton Jones, and Philip Wadler. 2007. A history of Haskell: being lazy with class. In Proceedings of the Third ACM SIGPLAN Conference on History of Programming Languages (San Diego, California) (HOPL III). Association for Computing Machinery, New York, NY, USA, 12–1–12–55. DOI: 10.1145/1238844.1238856
Graham Hutton. 2016. Programming in Haskell (2nd ed.). Cambridge University Press, USA.
SL Peyton Jones, K Hammond, WD Partain, PL Wadler, CV Hall, and Simon Peyton Jones. 1993. The Glasgow Haskell Compiler: a technical overview. In Proceedings of Joint Framework for Information Technology Technical Conference, Keele (proceedings of joint framework for information technology technical conference, keele ed.). DTI/SERC, 249–257. [link]
Casey Klein, Matthew Flatt, and Robert Bruce Findler. 2010. Random Testing for Higher-order, Stateful Programs. In Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications (Reno/Tahoe, Nevada, USA) (OOPSLA ’10). ACM, New York, NY, USA, 555–566. DOI: 10.1145/1869459.1869505
Xiao Liu, Xiaoting Li, Rupesh Prajapati, and Dinghao Wu. 2019. DeepFuzz: Automatic Generation of Syntax Valid C Programs for Fuzz Testing. Proceedings of the AAAI Conference on Artificial Intelligence 33, 01 (Jul. 2019), 1044–1051. DOI: 10.1609/aaai.v33i01.33011044
Vsevolod Livinskii, Dmitry Babokin, and John Regehr. 2020. Random Testing for C and C++ Compilers with YARPGen. Proc. ACM Program. Lang. 4, OOPSLA, Article 196 (Nov. 2020), 25 pages. DOI: 10.1145/3428264
Yunlong Lyu, Yuxuan Xie, Peng Chen, and Hao Chen. 2024. Prompt Fuzzing for Fuzz Driver Generation. arXiv:2312.17677
Claudio Agustin Mista and Alejandro Russo. 2019. Deriving Compositional Random Generators. In Proceedings of the 31st Symposium on Implementation and Application of Functional Languages (IFL ’19).
Michal H. Palka, Koen Claessen, Alejandro Russo, and John Hughes. 2011. Testing an Optimising Compiler by Generating Random Lambda Terms. In Proceedings of the 6th InternationalWorkshop on Automation of Software Test (Waikiki, Honolulu, HI, USA) (AST ’11). 91–97. [link]
Benjamin C. Pierce. 2002. Types and Programming Languages (1st ed.). The MIT Press.
Antal Spector-Zabusky, Joachim Breitner, Christine Rizkallah, and Stephanie Weirich. 2018. Total Haskell is reasonable Coq. In Proceedings of the 7th ACM SIGPLAN International Conference on Certified Programs and Proofs (Los Angeles, CA, USA) (CPP 2018). Association for Computing Machinery, New York, NY, USA, 14–27. DOI: 10.1145/3167092
Haskell Wiki. 2020. Haskell in industry. [link] Accessed: 2024-05-14.
Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. 2011. Finding and Understanding Bugs in C Compilers. SIGPLAN Not. 46, 6 (June 2011), 283–294. DOI: 10.1145/1993316.1993532
Elton Maximo Cardoso, Daniel Freitas Pereira, Regina Sarah Monferrari Amorim De Paula, Leonardo Vieira Dos Santos Reis, and Rodrigo Geraldo Ribeiro. 2022. A Type-Directed Algorithm to Generate Random Well-Formed Parsing Expression Grammars. In Proceedings of the XXVI Brazilian Symposium on Programming Languages (
Augusto Celentano, S Crespi Reghizzi, P Della Vigna, Carlo Ghezzi, G Granata, and Florencia Savoretti. 1980. Compiler testing using a sentence generator. Software: Practice and Experience 10, 11 (1980), 897–918.
Koen Claessen and John Hughes. 2000. QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs. SIGPLAN Not. 35, 9 (sep 2000), 268–279. DOI: 10.1145/357766.351266
Chris Cummins, Pavlos Petoumenos, Alastair Murray, and Hugh Leather. 2018. Compiler Fuzzing through Deep Learning. In Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis (Amsterdam, Netherlands) (ISSTA 2018). Association for Computing Machinery, New York, NY, USA, 95–105. DOI: 10.1145/3213846.3213848
Dániel Drienyovszky, Dániel Horpácsi, and Simon Thompson. 2010. Quickchecking Refactoring Tools. In Proceedings of the 9th ACM SIGPLAN Workshop on Erlang (Baltimore, Maryland, USA) (Erlang ’10). ACM, New York, NY, USA, 75–80. DOI: 10.1145/1863509.1863521
Simon Marlow (Editor). 2010. Haskell 2010 Language Report. [link] Accessed: 2024-04-10.
Samuel Feitosa, Rodrigo Ribeiro, and Andre Du Bois. 2020. A type-directed algorithm to generate random well-typed Java 8 programs. Science of Computer Programming 196 (2020), 102494. DOI: 10.1016/j.scico.2020.102494
Samuel Feitosa, Rodrigo Ribeiro, and Andre Du Bois. 2020. A type-directed algorithm to generate random well-typed Java 8 programs. Science of Computer Programming 196 (2020), 102494. DOI: 10.1016/j.scico.2020.102494
Justin Frank, Benjamin Quiring, and Leonidas Lampropoulos. 2024. Generating Well-Typed Terms That Are Not “Useless”. Proc. ACM Program. Lang. 8, POPL, Article 77 (jan 2024), 22 pages. DOI: 10.1145/3632919
Andy Gill and Colin Runciman. 2007. Haskell Program Coverage. In Proceedings of the ACM SIGPLANWorkshop on HaskellWorkshop (Freiburg, Germany) (Haskell ’07). ACM, New York, NY, USA, 1–12. DOI: 10.1145/1291201.1291203
Jean-Yves Girard. 1986. The system F of variable types, fifteen years later. Theoretical Computer Science 45 (1986), 159–192. DOI: 10.1016/0304-3975(86)90044-7
Paul Hudak, John Hughes, Simon Peyton Jones, and Philip Wadler. 2007. A history of Haskell: being lazy with class. In Proceedings of the Third ACM SIGPLAN Conference on History of Programming Languages (San Diego, California) (HOPL III). Association for Computing Machinery, New York, NY, USA, 12–1–12–55. DOI: 10.1145/1238844.1238856
Graham Hutton. 2016. Programming in Haskell (2nd ed.). Cambridge University Press, USA.
SL Peyton Jones, K Hammond, WD Partain, PL Wadler, CV Hall, and Simon Peyton Jones. 1993. The Glasgow Haskell Compiler: a technical overview. In Proceedings of Joint Framework for Information Technology Technical Conference, Keele (proceedings of joint framework for information technology technical conference, keele ed.). DTI/SERC, 249–257. [link]
Casey Klein, Matthew Flatt, and Robert Bruce Findler. 2010. Random Testing for Higher-order, Stateful Programs. In Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications (Reno/Tahoe, Nevada, USA) (OOPSLA ’10). ACM, New York, NY, USA, 555–566. DOI: 10.1145/1869459.1869505
Xiao Liu, Xiaoting Li, Rupesh Prajapati, and Dinghao Wu. 2019. DeepFuzz: Automatic Generation of Syntax Valid C Programs for Fuzz Testing. Proceedings of the AAAI Conference on Artificial Intelligence 33, 01 (Jul. 2019), 1044–1051. DOI: 10.1609/aaai.v33i01.33011044
Vsevolod Livinskii, Dmitry Babokin, and John Regehr. 2020. Random Testing for C and C++ Compilers with YARPGen. Proc. ACM Program. Lang. 4, OOPSLA, Article 196 (Nov. 2020), 25 pages. DOI: 10.1145/3428264
Yunlong Lyu, Yuxuan Xie, Peng Chen, and Hao Chen. 2024. Prompt Fuzzing for Fuzz Driver Generation. arXiv:2312.17677
Claudio Agustin Mista and Alejandro Russo. 2019. Deriving Compositional Random Generators. In Proceedings of the 31st Symposium on Implementation and Application of Functional Languages (IFL ’19).
Michal H. Palka, Koen Claessen, Alejandro Russo, and John Hughes. 2011. Testing an Optimising Compiler by Generating Random Lambda Terms. In Proceedings of the 6th InternationalWorkshop on Automation of Software Test (Waikiki, Honolulu, HI, USA) (AST ’11). 91–97. [link]
Benjamin C. Pierce. 2002. Types and Programming Languages (1st ed.). The MIT Press.
Antal Spector-Zabusky, Joachim Breitner, Christine Rizkallah, and Stephanie Weirich. 2018. Total Haskell is reasonable Coq. In Proceedings of the 7th ACM SIGPLAN International Conference on Certified Programs and Proofs (Los Angeles, CA, USA) (CPP 2018). Association for Computing Machinery, New York, NY, USA, 14–27. DOI: 10.1145/3167092
Haskell Wiki. 2020. Haskell in industry. [link] Accessed: 2024-05-14.
Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. 2011. Finding and Understanding Bugs in C Compilers. SIGPLAN Not. 46, 6 (June 2011), 283–294. DOI: 10.1145/1993316.1993532
Publicado
30/09/2024
Como Citar
FEITOSA, Samuel da Silva; RIBEIRO, Rodrigo Geraldo.
Differential Testing using Random Well-Typed Haskell Programs. In: SIMPÓSIO BRASILEIRO DE LINGUAGENS DE PROGRAMAÇÃO (SBLP), 28. , 2024, Curitiba/PR.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 26-34.
