Systematic testing of post-quantum cryptographic implementations using metamorphic testing
Pages 2 - 8
Abstract
Cryptographic algorithms are usually complex, and their code is highly compact. Moreover, there is often no test oracle to easily test some of these algorithms. Together these attributes make it extremely challenging to run tests and to discover bugs in them. Structural coverage based approaches such as statement or branch coverage are typically not very effective in discovering bugs in these types of programs. In this paper, we investigate the effectiveness of a systematic testing approach for discovering bugs in highly complex cryptographic algorithm implementations. In this work, we identify metamorphic relations based on the specifications of the algorithms, and design test cases such that a systematic coverage of the input space is achieved. Our results show that this approach is highly effective in discovering faults in complex cryptographic implementations.
References
[1]
N. Mouha, M. Raunak, R. Kuhn, and R. Kacker, "Finding bugs in cryptographic hash function implementations," IEEE Transactions on Reliability, vol. 67, no. 3, pp. 870--884, July 2018.
[2]
NIST, "Submission requirements and evaluation criteria for the post-quantum cryptography standardization process," July 2016. {Online}. Available: https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf
[3]
P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer," SIAM Journal on Computing, vol. 26, no. 5, pp. 1484--1509, Oct 1997. {Online}. Available
[4]
NIST, "Announcing request for nominations for public-key post-quantum cryptographic algorithms," 82 Federal Register, pp. 62212--62220, December 2016.
[5]
NIST, "Request for comments on post-quantum cryptography requirements and evaluation criteria," 81 Federal Register, pp. 50 686--50 687, July 2016, https://www.govinfo.gov/content/pkg/FR-2016-08-02/pdf/2016-18150.pdf.
[6]
A. Braga and R. Dahab, "A Survey on Tools and Techniques for the Programming and Verification of Secure Cryptographic Software," Proceedings of XV SBSeg, pp. 30--43, 2015.
[7]
D. Lazar, H. Chen, X. Wang, and N. Zeldovich, "Why does cryptographic software fail? A case study and open problems," in Proceedings of 5th Asia-Pacific Workshop on Systems. ACM, 2014, p. 7.
[8]
C.-a. Sun, Z. Wang, and G. Wang, "A property-based testing framework for encryption programs," Frontiers of Computer Science, vol. 8, no. 3, pp. 478--489, 2014.
[9]
T. Y. Chen, F.-C. Kuo, W. Ma, W. Susilo, D. Towey, J. Voas, and Z. Q. Zhou, "Metamorphic Testing for Cybersecurity," Computer, vol. 49, no. 6, pp. 48--55, 2016.
[10]
J. Botella, F. Bouquet, J.-F. Capuron, F. Lebeau, B. Legeard, and F. Schadle, "Model-based testing of cryptographic components - lessons learned from experience," in IEEE Sixth International Conference on Software Testing, Verification and Validation (ICST). IEEE, 2013, pp. 192--201.
[11]
P. Kitsos, D. E. Simos, J. Torres-Jimenez, and A. G. Voyiatzis, "Exciting FPGA cryptographic Trojans using Combinatorial Testing," in Software Reliability Engineering (ISSRE), 2015 IEEE 26th International Symposium on. IEEE, 2015, pp. 69--76.
[12]
J.-P. Aumasson and Y. Romailler, "Automated testing of crypto software using differential fuzzing," in Black Hat USA 2017, July 2017.
[13]
T. Y. Chen, S. C. Cheung, and S. Yiu, "Metamorphic testing: a new approach for generating next test cases," Dept. of Computer Science, Hong Kong Univ. of Science and Technology, Tech. Rep. HKUST-CS98-01, 1998.
[14]
J. Hoffstein, J. Pipher, J. Schanck, J. Silverman, and W. Whyte, "Transcript secure signatures based on modular lattices," in Post-Quantum Cryptography - 6th International Workshop, PQCrypto 2014, October 2014, pp. 142--159.
[15]
K. Akiyama, Y. Goto, S. Okumura, T. Takagi, K. Nuida, G. Hanaoka, H. Shimizu, and Y. Ikematsu, "A public-key encryption scheme based on non-linear indeterminate equations (giophantus)," Cryptology ePrint Archive, Report 2017/1241, Tech. Rep., 2017.
[16]
H. Liu, F. C. Kuo, D. Towey, and T. Y. Chen, "How effectively does metamorphic testing alleviate the oracle problem?" IEEE Trans. Softw. Eng., vol. 40, no. 1, Sep 2013.
[17]
T. Y. Chen, F.-C. Kuo, H. Liu, P.-L. Poon, D. Towey, T. Tse, and Z. Q. Zhou, "Metamorphic testing: A review of challenges and opportunities," ACM Computing Surveys (CSUR), vol. 51, no. 1, p. 4, 2018.
[18]
A. Gotlieb and B. Botella, "Automated metamorphic testing," in Proceedings 27th Annual International Computer Software and Applications Conference. COMPAC 2003. IEEE, 2003, pp. 34--40.
[19]
T. Y. Chen, T. Tse, and Z. Q. Zhou, "Semi-proving: An integrated method for program proving, testing, and debugging," IEEE Transactions on Software Engineering, vol. 37, no. 1, pp. 109--125, 2011.
[20]
D. R. Kuhn and V. Okun, "Pseudo-exhaustive testing for software," in 2006 30th Annual IEEE/NASA Software Engineering Workshop.
[21]
R. Bartholomew, "An industry proof-of-concept demonstration of automated combinatorial test," in Proc. 8th Intl Workshop on Automation of Software Test. IEEE Press, 2013, pp. 118--124.
Recommendations
Self-Checked Metamorphic Testing of an Image Processing Program
SSIRI '10: Proceedings of the 2010 Fourth International Conference on Secure Software Integration and Reliability ImprovementMetamorphic testing is an effective technique for testing systems that do not have test oracles, for which it is practically impossible to know the correct output of an arbitrary test input. In metamorphic testing, instead of checking the correctness of ...
Feedback-Directed Metamorphic Testing
Over the past decade, metamorphic testing has gained rapidly increasing attention from both academia and industry, particularly thanks to its high efficacy on revealing real-life software faults in a wide variety of application domains. On the basis of a ...
Fault detection effectiveness of source test case generation strategies for metamorphic testing
MET '18: Proceedings of the 3rd International Workshop on Metamorphic TestingMetamorphic 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 ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- SIGSOFT: ACM Special Interest Group on Software Engineering
- IEEE-CS: Computer Society
Publisher
IEEE Press
Publication History
Published: 26 May 2019
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
ICSE '19
Sponsor:
- SIGSOFT
- IEEE-CS
Upcoming Conference
ISSTA '25
- Sponsor:
- sigsoft
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 77Total Downloads
- Downloads (Last 12 months)4
- Downloads (Last 6 weeks)1
Reflects downloads up to 06 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in