Table of Links Abstract and 1 Introduction Abstract and 1 Introduction 2 Background 2 Background 3 Approach and 3.1 Differential Testing for XML Processors 3 Approach and 3.1 Differential Testing for XML Processors 3.2 XPath Expression Generation 3.2 XPath Expression Generation 3.3 XML Generation 3.3 XML Generation 4 Evaluation 4 Evaluation 4.1 Effectiveness 4.1 Effectiveness 4.2 Efficiency 4.2 Efficiency 4.3 Comparison to the State of the Art 4.3 Comparison to the State of the Art 4.4 Analysis of BaseX Historical Bug Reports 4.4 Analysis of BaseX Historical Bug Reports 5 Related Work 5 Related Work 6 Conclusion, Acknowledgments, and References 6 Conclusion, Acknowledgments, and References 6 CONCLUSION This paper has presented a general automated testing approach for detecting XPath-related logic bugs in XML processors. We demonstrate that differential testing is applicable in this domain, since XML processors widely adhere to the XPath standards. To generate interesting XPath queries, our approach selects a so-called targeted node to guide predicate generation and predicate rectification to ensure the inclusion of that node. Our evaluation shows that this improves the number of bugs detected in 24 hours to 2× as compared to random generation. More importantly, we have successfully detected 27 previously unknown, unique bugs in six mature XML processing systems. We believe that this high number is surprising, given that XML processors are an essential part of our computing infrastructure, with the first XPath standard having been proposed more than 20 years ago, and the systems that we have tested having been maintained for at least 15 years. We believe that XPress, given its simplicity and generality, has a high chance of being integrated into the toolbox of XML processor developers. Furthermore, we believe that our work might inspire testing approaches for other XML standards, such as XQuery or XSLT. ACKNOWLEDGMENTS This research was supported by a Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 1 grant. REFERENCES [1] 1999. XML Path Language (XPath) Version 1.0 W3C Recommendation. Retrieved July 17, 2023 from https://www.w3.org/TR/1999/REC-xpath-19991116/ [2] 2004. XML Schema Part 2: Datatypes Second Edition - Built-in datatypes. Retrieved July 17, 2023 from https://www.w3.org/TR/xmlschema-2/#built-in-datatypes [3] 2008. EBNF notation from the W3C Extensible Markup Language (XML) 1.0 (Fifth Edition). Retrieved July 17, 2023 from https://www.w3.org/TR/REC-xml/ [4] 2014. XML Path Language (XPath) 3.0 W3C Recommendation. Retrieved July 17, 2023 from https://www.w3.org/TR/xpath-30/ [5] 2014. XPath and XQuery Functions and Operators 3.0 W3C Recommendation. Retrieved July 17, 2023 from https://www.w3.org/TR/xpath-functions-30/ [6] 2017. XQuery 3.1: An XML Query Language W3C Recommendation. Retrieved July 17, 2023 from https://www.w3.org/TR/xquery-31/ [7] 2017. XSL Transformations (XSLT) Version 3.0 W3C Recommendation. Retrieved July 17, 2023 from https://www.w3.org/TR/xslt-30/ [8] 2023. BaseX. Retrieved July 31, 2023 from https://basex.org/ [9] 2023. DB-Engines Ranking. Retrieved July 6, 2023 from https://db-engines.com/ en/ranking [10] 2023. eXist-DB. Retrieved July 31, 2023 from http://exist-db.org/exist/apps/ homepage/index.html [11] 2023. eXist DB reference page. Retrieved July 6, 2023 from http://exist-db.org/ exist/apps/homepage/references.html [12] 2023. libXML2. Retrieved July 31, 2023 from https://gitlab.gnome.org/GNOME/ libxml2 [13] 2023. MySQL. Retrieved July 31, 2023 from https://www.mysql.com/ [14] 2023. Oracle Database. Retrieved July 31, 2023 from https://www.oracle.com/ database/ [15] 2023. PostgreSQL. Retrieved July 31, 2023 from https://www.postgresql.org/ [16] 2023. Saxon home page. Retrieved July 6, 2023 from https://saxonica.com/html/ welcome/welcome.html [17] 2023. Saxon XQuery 3.1 conformance page. Retrieved July 13, 2023 from https: //www.saxonica.com/documentation12/#!conformance/xquery31 [18] 2023. Saxonica. Retrieved July 31, 2023 from https://saxonica.com/ [19] 2023. W3C qt3 test suite github repository. Retrieved July 11, 2023 from https: //github.com/w3c/qt3tests [20] Jeffrey F. Naughton Aboulnaga, Ashraf and Chun Zhang. 2001. Generating Synthetic Complex-Structured XML Data. WebDB. 1 (2001), 79–84. [21] Alexandr Andoni, Dumitru Daniliuc, Sarfraz Khurshid, and Darko Marinov. 2003. Evaluating the “small scope hypothesis”. [22] Jinsheng Ba and Manuel Rigger. 2023. Testing Database Engines via Query Plan Guidance. In 2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE). 2060–2071. https://doi.org/10.1109/ICSE48619.2023.00174 [23] Yuting Chen, Ting Su, Chengnian Sun, Zhendong Su, and Jianjun Zhao. 2016. Coverage-Directed Differential Testing of JVM Implementations. In Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation (Santa Barbara, CA, USA) (PLDI ’16). Association for Computing Machinery, New York, NY, USA, 85–99. https://doi.org/10.1145/2908080.2908095 [24] Timothy Dyck. 2002. DB Test Pioneer Makes History. Retrieved July 31, 2023 from https://www.eweek.com/development/db-test-pioneer-makes-history/ [25] Massimo Franceschet. 2005. XPathMark: An XPath Benchmark for the XMark Generated Data. In Database and XML Technologies, Stéphane Bressan, Stefano Ceri, Ela Hunt, Zachary G. Ives, Zohra Bellahsène, Michael Rys, and Rainer Unland (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 129–143. [26] Ziyue Hua, Wei Lin, Luyao Ren, Zongyang Li, Lu Zhang, Wenpin Jiao, and Tao Xie. 2023. GDsmith: Detecting Bugs in Cypher Graph Database Engines. Association for Computing Machinery, New York, NY, USA. https://doi.org/10.1145/3597926. 3598046 [27] Zu-Ming Jiang, Jia-Ju Bai, and Zhendong Su. 2023. DynSQL: Stateful Fuzzing for Database Management Systems with Complex and Valid SQL Query Generation. In Proceedings of the 32nd USENIX Conference on Security Symposium (Anaheim, CA, USA) (SEC ’23). USENIX Association, USA, Article 277, 17 pages. [28] Jinho Jung, Hong Hu, Joy Arulraj, Taesoo Kim, and Woonhak Kang. 2019. APOLLO: Automatic Detection and Diagnosis of Performance Regressions in Database Systems. Proc. VLDB Endow. 13, 1 (sep 2019), 57–70. https: //doi.org/10.14778/3357377.3357382 [29] Matteo Kamm, Manuel Rigger, Chengyu Zhang, and Zhendong Su. 2023. Testing Graph Database Engines via Query Partitioning. Association for Computing Machinery, New York, NY, USA. https://doi.org/10.1145/3597926.3598044 [30] George Klees, Andrew Ruef, Benji Cooper, Shiyi Wei, and Michael Hicks. 2018. Evaluating Fuzz Testing. Proceedings of the 2018 ACM SIGSAC conference on computer and communications security (2018). https://doi.org/10.1145/3243734. 3243804 [31] Quanzhong Li and Bongki Moon. 2001. Indexing and Querying XML Data for Regular Path Expressions. In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB ’01). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 361–370. [32] Vsevolod Livinskii, Dmitry Babokin, and John Regehr. 2023. Fuzzing Loop Optimizations in Compilers for C++ and Data-Parallel Languages. Proc. ACM Program. Lang. 7, PLDI, Article 181 (jun 2023), 22 pages. https://doi.org/10.1145/3591295 [33] Jayashree Mohan, Ashlie Martinez, Soujanya Ponnapalli, Pandian Raju, and Vijay Chidambaram. 2018. Finding Crash-Consistency Bugs with Bounded Black-Box Crash Testing. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18). 33–50. [34] Manuel Rigger and Zhendong Su. 2020. Detecting Optimization Bugs in Database Engines via Non-Optimizing Reference Engine Construction. In Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (Virtual Event, USA) (ESEC/FSE 2020). Association for Computing Machinery, New York, NY, USA, 1140–1152. https://doi.org/10.1145/3368089.3409710 [35] Manuel Rigger and Zhendong Su. 2020. Finding Bugs in Database Systems via Query Partitioning. Proc. ACM Program. Lang. 4, OOPSLA, Article 211 (nov 2020), 30 pages. https://doi.org/10.1145/3428279 [36] Manuel Rigger and Zhendong Su. 2020. Testing Database Engines via Pivoted Query Synthesis. In Proceedings of the 14th USENIX Conference on Operating Systems Design and Implementation (OSDI’20). USENIX Association, USA, Article 38, 16 pages. [37] Dušan Rychnovský and Holubová. 2015. Generating XML Data for XPath Queries. Association for Computing Machinery. (2015). https://doi.org/10.1145/2695664. 2695691 [38] Donald R. Slutz. 1998. Massive Stochastic Testing of SQL. In Proceedings of the 24rd International Conference on Very Large Data Bases (VLDB ’98). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 618–622. [39] Thodoris Sotiropoulos, Stefanos Chaliasos, Vaggelis Atlidakis, Dimitris Mitropoulos, and Diomidis Spinellis. 2021. Data-Oriented Differential Testing of ObjectRelational Mapping Systems. In 2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE). 1535–1547. https://doi.org/10.1109/ICSE43902.2021. 00137 [40] Ting Su, Yichen Yan, Jue Wang, Jingling Sun, Yiheng Xiong, Geguang Pu, Ke Wang, and Zhendong Su. 2021. Fully Automated Functional Fuzzing of Android Apps for Detecting Non-Crashing Logic Bugs. Proc. ACM Program. Lang. 5, OOPSLA, Article 156 (oct 2021), 31 pages. https://doi.org/10.1145/3485533 [41] Milos Todic and Branislav Uzelac. 2012. Combined XML/XQuery generator. Proceedings of the Fifth International Workshop on Testing Database Systems (2012). https://doi.org/10.1145/2304510.2304519 [42] Yuqing Wu, Namrata Lele, Rashmi Aroskar, Sharanya Chinnusamy, and Sofia Brenes. 2009. XQGen: An Algebra-Based XPath Query Generator for MicroBenchmarking. In Proceedings of the 18th ACM Conference on Information and Knowledge Management (Hong Kong, China) (CIKM ’09). Association for Computing Machinery, New York, NY, USA, 2109–2110. https://doi.org/10.1145/1645953. 1646328 [43] Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. 2011. Finding and Understanding Bugs in C Compilers. Association for Computing Machinery, New York, NY, USA. https://doi.org/10.1145/1993498.1993532 [44] Hua Z, Lin W, Ren L, Li Z, Zhang L, Jiao W, and Xie T. 2023. GDsmith: Detecting bugs in Cypher graph database engines. Proceedings of ACM SIGSOFT International Symposium on Software Testing and Analysis (2023). https: //doi.org/10.48550/arXiv.2206.08530 [45] Qirun Zhang, Chengnian Sun, and Zhendong Su. 2017. Skeletal Program Enumeration for Rigorous Compiler Testing. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation (Barcelona, Spain) (PLDI 2017). Association for Computing Machinery, New York, NY, USA, 347–361. https://doi.org/10.1145/3062341.3062379 [46] Yingying Zheng, Wensheng Dou, Yicheng Wang, Zheng Qin, Lei Tang, Yu Gao, Dong Wang, Wei Wang, and Jun Wei. 2022. Finding bugs in Gremlin-based graph database systems via randomized differential testing. Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis (2022). https://doi.org/10.1145/3533767.3534409 [47] Rui Zhong, Yongheng Chen, Hong Hu, Hangfan Zhang, Wenke Lee, and Dinghao Wu. 2020. Squirrel: Testing database management systems with language validity and coverage feedback. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. 955–970. This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv Authors:
(1) Shuxin Li, Southern University of Science and Technology China and Work done during an internship at the National University of Singapore (shuxin.li.lv@gmail.com);
(2) Manuel Rigger, National University of Singapore Singapore (rigger@nus.edu.sg). Authors: Authors: (1) Shuxin Li, Southern University of Science and Technology China and Work done during an internship at the National University of Singapore (shuxin.li.lv@gmail.com); (2) Manuel Rigger, National University of Singapore Singapore (rigger@nus.edu.sg).

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Abstract

Gremlin

Kong

Loop

Massive

Oracle

Path

Southern

Finding XPath Bugs in XML Document Processors: Testing XPath Functionality and Other Related Work

Read My Stories

Too Long; Didn't Read

Presenting A General Automated Testing Approach for Detecting XPath-Related Logic Bugs

Presenting A General Automated Testing Approach for Detecting XPath-Related Logic Bugs

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

An Analysis of BaseX Historical Bug Reports

Showing XPress’ Effectiveness Through the Number of Bugs Found, Developer Feedback, etc.

Index Support in BaseX, eXist-DB, Saxon, and libxml2: Explained

An Analysis of BaseX Historical Bug Reports

Finding XPath Bugs in XML Document Processors via Differential Testing

XML, XPath, XPath Structure, and More Explained

An Analysis of BaseX Historical Bug Reports

Showing XPress’ Effectiveness Through the Number of Bugs Found, Developer Feedback, etc.

Index Support in BaseX, eXist-DB, Saxon, and libxml2: Explained

An Analysis of BaseX Historical Bug Reports

Finding XPath Bugs in XML Document Processors via Differential Testing

XML, XPath, XPath Structure, and More Explained

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps