A Testing Program and Pragma Combination Selection Based Framework for High-Level Synthesis Tool Pragma-Related Bug Detection
Authors: 
He Jiang, Zun Wang, Zhide Zhou, Xiaochen Li, Shikai Guo, Weifeng Sun, Tao ZhangAuthors Info & Claims
Pages 937 - 955
Abstract
High-Level Synthesis (HLS) tools convert C/C++ design code into Hardware Description Language (HDL) code automatically, which are often used for Field Programmable Gate Array (FPGA) design. HLS tools provide many pragmas, which are a kind of directive to be inserted into C/C++ code, for designers to efficiently control the synthesis of code components (e.g., arrays and loops) to generate FPGA implementations with varying performances and costs. However, the use of some pragmas may trigger HLS tool bugs (e.g., tool crashes). Although many formal methods have been proposed to verify the correctness of various HLS phases, no relevant work addresses the problem on detecting HLS tool pragma-related bugs. To resolve this problem, two challenges need to be addressed, namely the selection of testing programs and the acquisition of pragma combinations, due to the enormous number of testing programs and pragma combinations. In this paper, we propose TEPACS, a TEsting Program and prAgma Combination Selection-based framework, to construct diverse testing programs with pragmas for effectively detecting HLS tool pragma-related bugs. TEPACS follows the idea of fuzzing, which is a widely used technique in software testing. First, TEPACS selects the representative testing program according to the cosine distance between the code component vectors of testing programs. Then, for a selected program, TEPACS generates its golden output and uses the pragma combination selection method based on combinatorial testing to generate a set of programs with different pragmas. TEPACS uses the HLS tool under test to convert these testing programs into HDL codes and obtains the simulation results of the HDL code. Finally, based on differential testing, TEPACS identifies HLS tool bugs triggered if the simulation result and golden output are inconsistent. We evaluate TEPACS and its five variants on Vitis HLS, a widely used FPGA HLS tool. Experimental results show that TEPACS outperforms the baselines by at least 11.17% in terms of the bug-finding capability. In one month, TEPACS detected 34 bugs on the latest version of Vitis HLS, of which 9 bugs have been confirmed.
References
[1]
H. Jiang, H. Li, T. Liu, P. Zhang, and J. Lu, “A fast method for RGB to YCrCb conversion based on FPGA,” in Proc. 3rd Int. Conf. Comput. Sci. Netw. Technol., Piscataway, NJ, USA: IEEE Press, 2013, pp. 588–591.
[2]
K. F. Zhang, S. F. Chen, and S. Z. Xiao, “Anti-radiation design and irradiation test of antifuse FPGA,” in Applied Mechanics and Materials, vol. 380. Switzerland: Trans Tech Publ, 2013, pp. 3249–3253.
[3]
C. Li, T. Li, J. Li, Z. Shi, and B. Wang, “Update latency optimization of packet classification for SDN switch on FPGA,” in Proc. IEEE 28th Annu. Int. Symp. Field-Programmable Custom Comput. Mach. (FCCM), Piscataway, NJ, USA: IEEE Press, 2020, pp. 213–213.
[4]
G. Martin and G. Smith, “High-level synthesis: Past, present, and future,” IEEE Des. Test Comput., vol. 26, no. 4, pp. 18–25, 2009.
[5]
N. Pundir, F. Farahmandi, and M. Tehranipoor, “Secure high-level synthesis: Challenges and solutions,” in Proc. 22nd Int. Symp. Qual. Electron. Des. (ISQED), Piscataway, NJ, USA: IEEE Press, 2021, pp. 164–171.
[6]
D. J. Warne, N. A. Kelson, and R. F. Hayward, “Comparison of high level FPGA hardware design for solving tri-diagonal linear systems,” Procedia Comput. Sci., vol. 29, pp. 95–101, 2014.
[7]
B. C. Schafer, “Parallel high-level synthesis design space exploration for behavioral IPs of exact latencies,” ACM Trans. Des. Automat. Electron. Syst. (TODAES), vol. 22, no. 4, pp. 1–20, 2017.
[8]
L. Ferretti, J. Kwon, G. Ansaloni, G. Di Guglielmo, L. P. Carloni, and L. Pozzi, “Leveraging prior knowledge for effective design-space exploration in high-level synthesis,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 39, no. 11, pp. 3736–3747, Nov. 2020.
[9]
T. Santos and J. M. Cardoso, “Automatic selection and insertion of hls directives via a source-to-source compiler,” in Proc. Int. Conf. Field-Programmable Technol. (ICFPT), Piscataway, NJ, USA: IEEE Press, 2020, pp. 227–232.
[10]
T. Yue, Y. Tang, B. Yu, P. Wang, and E. Wang, “LearnAFL: Greybox fuzzing with knowledge enhancement,” IEEE Access, vol. 7, pp. 117029–117043, 2019.
[11]
X. Yang, Y. Chen, E. Eide, and J. Regehr, “Finding and understanding bugs in C compilers,” in Proc. 32nd ACM SIGPLAN Conf. Program. Lang. Des. Implementation, 2011, pp. 283–294.
[12]
V. Le, M. Afshari, and Z. Su, “Compiler validation via equivalence modulo inputs,” ACM SIGPLAN Notices, vol. 49, no. 6, pp. 216–226, 2014.
[13]
Q. Zhang, C. Sun, and Z. Su, “Skeletal program enumeration for rigorous compiler testing,” in Proc. 38th ACM SIGPLAN Conf. Program. Lang. Des. Implementation, 2017, pp. 347–361.
[14]
H. Jiang, Z. Zhou, Z. Ren, J. Zhang, and X. Li, “CTOS: Compiler testing for optimization sequences of LLVM,” IEEE Trans. Softw. Eng., vol. 48, no. 7, pp. 2339–2358, Jul. 2022.
[15]
Y. Tang, H. Jiang, Z. Zhou, X. Li, Z. Ren, and W. Kong, “Detecting compiler warning defects via diversity-guided program mutation,” IEEE Trans. Softw. Eng., vol. 48, no. 11, pp. 4411–4432, Nov. 2022.
[16]
Y. Herklotz, Z. Du, N. Ramanathan, and J. Wickerson, “An empirical study of the reliability of high-level synthesis tools,” in Proc. IEEE 29th Annu. Int. Symp. Field-Programmable Custom Comput. Mach. (FCCM), Piscataway, NJ, USA: IEEE Press, 2021, pp. 219–223.
[17]
H. Liang, X. Pei, X. Jia, W. Shen, and J. Zhang, “Fuzzing: State of the art,” IEEE Trans. Rel., vol. 67, no. 3, pp. 1199–1218, Sep. 2018.
[18]
S. Kundu, S. Lerner, and R. K. Gupta, “Translation validation of high-level synthesis,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 29, no. 4, pp. 566–579, Apr. 2010.
[19]
K. Banerjee, C. Karfa, D. Sarkar, and C. Mandal, “Verification of code motion techniques using value propagation,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 33, no. 8, pp. 1180–1193, Aug. 2014.
[20]
A. Leung, D. Bounov, and S. Lerner, “C-to-Verilog translation validation,” in Proc. ACM/IEEE Int. Conf. Formal Methods Models Codes. (MEMOCODE), Piscataway, NJ, USA: IEEE Press, 2015, pp. 42–47.
[21]
V. Livinskii, D. Babokin, and J. Regehr, “Random testing for C and C++ compilers with YARPGen,” Proc. ACM Program. Lang., 2020, vol. 4, no. OOPSLA, pp. 1–25.
[22]
K. S. Sree and D. J. Murthy, “Clustering based on cosine similarity measure,” Int. J. Eng. Sci. Adv. Technol., vol. 2, no. 3, pp. 508–512, 2012.
[23]
C. Nie and H. Leung, “A survey of combinatorial testing,” ACM Comput. Surv. (CSUR), vol. 43, no. 2, pp. 1–29, 2011.
[24]
J. Czerwonka, “Pairwise testing in the real world: Practical extensions to test-case scenarios,” in Proc. 24th Pacific Northwest Softw. Qual. Conf.. Citeseer, 2006, pp. 419–430.
[25]
C. Lidbury, A. Lascu, N. Chong, and A. F. Donaldson, “Many-core compiler fuzzing,” ACM SIGPLAN Notices, vol. 50, no. 6, pp. 65–76, 2015.
[26]
L. Huang, D.-L. Li, K.-P. Wang, T. Gao, and A. Tavares, “A survey on performance optimization of high-level synthesis tools,” J. Comput. Sci. Technol., vol. 35, no. 3, pp. 697–720, 2020.
[27]
J. Chen et al., “A survey of compiler testing,” ACM Comput. Surv. (CSUR), vol. 53, no. 1, pp. 1–36, 2020.
[28]
V. Le, C. Sun, and Z. Su, “Finding deep compiler bugs via guided stochastic program mutation,” ACM SIGPLAN Notices, vol. 50, no. 10, pp. 386–399, 2015.
[29]
J. Chen, G. Wang, D. Hao, Y. Xiong, H. Zhang, and L. Zhang, “History-guided configuration diversification for compiler test-program generation,” in Proc. 34th IEEE/ACM Int. Conf. Automated Softw. Eng. (ASE), Piscataway, NJ, USA: IEEE Press, 2019, pp. 305–316.
[30]
Z. Chen et al., “Exploring better black-box test case prioritization via log analysis,” ACM Trans. Softw. Eng. Methodol., vol. 32, no. 3, pp. 1–32, 2023.
[31]
D. R. Kuhn et al., “Practical combinatorial testing,” NIST Special Publication 800-142, 2010.
[32]
Y.-k. Choi, P. Zhang, P. Li, and J. Cong, “HLScope+: Fast and accurate performance estimation for FPGA HLS,” in Proc. IEEE/ACM Int. Conf. Comput.-Aided Des. (ICCAD), Piscataway, NJ, USA: IEEE Press, 2017, pp. 691–698.
[33]
S. Marathe, “A generic approach for neural networks on FPGA,” in – Proc. Syst. Rel., Quality Control, Safety, Maintenance Manage: Appl. Elect., Electron. Comput. Sci. Eng. (ICICCT), New York, NY, USA: Springer-Verlag, 2020, pp. 82–91.
[34]
A. Cilardo and L. Gallo, “Interplay of loop unrolling and multidimensional memory partitioning in HLS,” in Proc. Des., Automat. Test Eur. Conf. Exhib. (DATE). IEEE, 2015, pp. 163–168.
[35]
J. Kwon and L. P. Carloni, “Transfer learning for design-space exploration with high-level synthesis,” in Proc. ACM/IEEE 2nd Workshop Mach. Learn. CAD (MLCAD), Piscataway, NJ, USA: IEEE Press, 2020, pp. 163–168.
[36]
L. Ferretti, G. Ansaloni, and L. Pozzi, “Cluster-based heuristic for high level synthesis design space exploration,” IEEE Trans. Emerg. Topics Comput., vol. 9, no. 1, pp. 35–43, Jan.–Mar. 2021.
[37]
J. Zhao, L. Feng, S. Sinha, W. Zhang, Y. Liang, and B. He, “COMBA: A comprehensive model-based analysis framework for high level synthesis of real applications,” in Proc. IEEE/ACM Int. Conf. Comput.-Aided Des. (ICCAD), Piscataway, NJ, USA: IEEE Press, 2017, pp. 430–437.
[38]
A. Balestrat, “CCG: A random C code generator.” GitHub. Accessed: Apr. 1, 2023. [Online]. Available: https://github.com/Merkil/ccg
[39]
V. Le, C. Sun, and Z. Su, “Randomized stress-testing of link-time optimizers,” in Proc. Int. Symp. Softw. Testing Anal., 2015, pp. 327–337.
[40]
C. Sun, V. Le, and Z. Su, “Finding compiler bugs via live code mutation,” in Proc. ACM SIGPLAN Int. Conf. Object-Oriented Program., Syst., Lang., Appl., 2016, pp. 849–863.
[41]
H. Tu, H. Jiang, X. Li, Z. Ren, Z. Zhou, and L. Jiang, “RemGen: Remanufacturing a random program generator for compiler testing,” in Proc. IEEE 33rd Int. Symp. Softw. Rel. Eng. (ISSRE), Piscataway, NJ, USA: IEEE Press, 2022, pp. 529–540.
[42]
M. Soltani, A. Panichella, and A. van Deursen, “A guided genetic algorithm for automated crash reproduction,” in Proc. IEEE/ACM 39th Int. Conf. Softw. Eng. (ICSE), 2017, pp. 209–220.
[43]
J. Castelein, M. F. Aniche, M. Soltani, A. Panichella, and A. van Deursen, “Search-based test data generation for SQL queries,” in Proc. 40th Int. Conf. Softw. Eng. (ICSE), USA: ACM, 2018, pp. 1220–1230.
[44]
Z. Zhou, H. Jiang, Z. Ren, Y. Chen, and L. Qiao, “LocSeq: Automated localization for compiler optimization sequence bugs of LLVM,” IEEE Trans. Rel., vol. 71, no. 2, pp. 896–910, Jun. 2022.
[45]
C. Cummins, P. Petoumenos, A. Murray, and H. Leather, “Compiler fuzzing through deep learning,” in Proc. 27th ACM SIGSOFT Int. Symp. Softw. Testing Anal., 2018, pp. 95–105.
[46]
J. Ye, B. Zhang, R. Li, C. Feng, and C. Tang, “Program state sensitive parallel fuzzing for real world software,” IEEE Access, vol. 7, pp. 42557–42564, 2019.
[47]
Y. Wang, Z. Wu, Q. Wei, and Q. Wang, “Field-aware evolutionary fuzzing based on input specifications and vulnerability metrics,” in Proc. IEEE 10th Int. Conf. Softw. Eng. Service Sci. (ICSESS), Piscataway, NJ, USA: IEEE Press, 2019, pp. 1–7.
[48]
B. C. Schafer and Z. Wang, “High-level synthesis design space exploration: Past, present, and future,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 39, no. 10, pp. 2628–2639, Oct. 2019.
[49]
B. C. Schafer, “Probabilistic multiknob high-level synthesis design space exploration acceleration,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 35, no. 3, pp. 394–406, Mar. 2016.
[50]
G. Zacharopoulos, A. Barbon, G. Ansaloni, and L. Pozzi, “Machine learning approach for loop unrolling factor prediction in high level synthesis,” in Proc. Int. Conf. High Perform. Comput. Simul. (HPCS), Piscataway, NJ, USA: IEEE Press, 2018, pp. 91–97.
[51]
R. Chouksey, C. Karfa, and P. Bhaduri, “Translation validation of loop invariant code optimizations involving false computations,” in Proc. Int. Symp. VLSI Des. Test, New York, NY, USA: Springer-Verlag, 2017, pp. 767–778.
[52]
R. Chouksey and C. Karfa, “Verification of scheduling of conditional behaviors in high-level synthesis,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 28, no. 7, pp. 1638–1651, Jul. 2020.
[53]
P. Fezzardi and F. Ferrandi, “Automated bug detection for pointers and memory accesses in high-level synthesis compilers,” in Proc. 26th Int. Conf. Field Programmable Log. Appl. (FPL), Piscataway, NJ, USA: IEEE Press, 2016, pp. 1–9.
[54]
A. Calvagna, A. Fornaia, and E. Tramontana, “Combinatorial interaction testing of a Java Card static verifier,” in Proc. IEEE 7th Int. Conf. Softw. Testing, Verification Validation Workshops, Piscataway, NJ, USA: IEEE Press, 2014, pp. 84–87.
[55]
Y. Li and F. Wotawa, “On using ontologies for testing compilers,” in Proc. IEEE Int. Conf. Softw. Testing, Verification Validation Workshops (ICSTW), Piscataway, NJ, USA: IEEE Press, 2020, pp. 181–184.
[56]
J. De Kleer, “An assumption-based TMS,” Artif. Intell., vol. 28, no. 2, pp. 127–162, 1986.
[57]
L. Ma et al., “DeepCT: Tomographic combinatorial testing for deep learning systems,” in Proc. IEEE 26th Int. Conf. Softw. Anal., Evolution Reeng. (SANER), Piscataway, NJ, USA: IEEE Press, 2019, pp. 614–618.
[58]
H. Wu, L. Xu, X. Niu, and C. Nie, “Combinatorial testing of RESTful APIs,” in Proc. IEEE/ACM 44th Int. Conf. Softw. Eng. (ICSE), 2022, pp. 426–437.
[59]
X. Wang, P. Arcaini, T. Yue, and S. Ali, “Application of combinatorial testing to quantum programs,” in Proc. IEEE 21st Int. Conf. Softw. Qual., Rel. Secur. (QRS), Piscataway, NJ, USA: IEEE Press, 2021, pp. 179–188.
Recommendations
High-Level Test Synthesis: A Survey from Synthesis Process Flow Perspective
High-level test synthesis is a special class of high-level synthesis having testability as one of the important components. This article presents a detailed survey on recent developments in high-level test synthesis from a synthesis process flow ...
Fuzzing High-Level Synthesis Tools
FPGA '21: The 2021 ACM/SIGDA International Symposium on Field-Programmable Gate ArraysHigh-level synthesis (HLS) is becoming an increasingly important part of the computing landscape, even in safety-critical domains where correctness is key. As such, HLS tools are increasingly relied upon. But are they trustworthy?
We have subjected ...
An Introduction to High-Level Synthesis
Editor's note:High-level synthesis raises the design abstraction level and allows rapid generation of optimized RTL hardware for performance, area, and power requirements. This article gives an overview of state-of-the-art HLS techniques and tools.—Tim ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
0098-5589 © 2024 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Press
Publication History
Published: 22 February 2024
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 09 Jan 2025