Fuzz testing or fuzzing is steadily gaining popularity as an efficient and cost-effective way of testing software applications. According to different security frameworks and standards, popular software products still contain various undiscovered vulnerabilities, caused especially by improper input validation, data processing errors and buffer overflows. Furthermore, remote attacks through imperfect implementations of network protocols are especially popular and severe. Using different fuzz testing approaches as well as various fuzzing frameworks these vulnerabilities can be revealed and consequently fixed.

Due to limitations concerning access to the network or its bandwidth, the duration of the fuzz testing should be reduced to a minimum. After analyzing different algorithms for comparing test data strings, the Levenshtein distance provides an effective way to reduce redundant and similar test cases to achieve a more distinct subset.

Using the Levenshtein distance in different approaches and implementations with numerous diverse parameters led to the conclusion that using an individual Levenshtein distance approach (comparing each test case to all others) combined with a total Levenshtein distance approach (comparing each test case’s total distance to all others) is the most effective and most balanced method in respect to data diversity and execution time.

Fuzz testing or fuzzing is steadily gaining popularity as an efficient and cost-effective way of testing software applications. According to different security frameworks and standards, popular software products still contain various undiscovered vulnerabilities, caused especially by improper input validation, data processing errors and buffer overflows. Furthermore, remote attacks through imperfect implementations of network protocols are especially popular and severe. Using different fuzz testing approaches as well as various fuzzing frameworks these vulnerabilities can be revealed and consequently fixed.

Due to limitations concerning access to the network or its bandwidth, the duration of the fuzz testing should be reduced to a minimum. After analyzing different algorithms for comparing test data strings, the Levenshtein distance provides an effective way to reduce redundant and similar test cases to achieve a more distinct subset.

Using the Levenshtein distance in different approaches and implementations with numerous diverse parameters led to the conclusion that using an individual Levenshtein distance approach (comparing each test case to all others) combined with a total Levenshtein distance approach (comparing each test case’s total distance to all others) is the most effective and most balanced method in respect to data diversity and execution time.

[1] Ari Takanen, Jared DeMott, and Charlie Miller, Fuzzing for Software Security Testing and Quality Assurance. Norwood, MA: Artech House, 2008.
[2] Joe Duran and Simeon Ntafos, “A report on random testing,” in ICSE '81 Proceedings of the 5th international conference on Software engineering, San Diego, CA, 1981.
[3] Barton Miller, Louis Fredriksen, and Bryan So, “An empirical study of the reliability of UNIX utilities,” Communications of the ACM, vol. 33, no. 12, pp. 32 - 44, 1990.
[4] Barton Miller, David Koski, Cjin Pheow Lee, and Vivekananda Maganty, “Fuzz Revisited - A re-examination of the reliability of UNIX utilities and services,” Technical report, University of Wisconsin - Madison, vol. 1525, pp. 1 - 23, 1995.
[5] S. K. Cha, M. Woo, and D. Brumley, “Program-Adaptive Mutational Fuzzing,” in IEEE Symposium on Security and Privacy, San Jose, CA, 2015.
[6] Michael Howard and Steve Lipner, “Stage 7: Secure Testing Policies,” in The Security Development Lifecycle. Redmond, WA: Microsoft Press, 2006, pp. 153 - 168.
[7] Micosoft. Microsoft Security Development Lifecycle. [Online]. https://www.microsoft.com/en-us/sdl/process/verification.aspx
[8] Jie Liang, Mingzhe Wang, Yuanliang Chen, Yu Jiang, and Renwei Zhang, “Fuzz testing in practice: Obstacles and solutions,” in IEEE 25th International Conference on Software Analysis, Evolution and Reengineering (SANER), Campobasso, 2018.
[9] Mike Aizatsky, Kostya Serebryany, Oliver Chang, Abhishek Arya, and Meredith Whittaker. (2016, December) Announcing OSS-Fuzz: Continuous Fuzzing for Open Source Software. [Online]. https://testing.googleblog.com/2016/12/announcing-oss- fuzz-continuous-fuzzing.html
[10] Petar Tsankov, Mohammad Torabi Dashti, and David Basin, “In-depth fuzz testing of IKE implementations,” Technical report / Systems Group, Department of Computer Science, ETH Zürich, vol. 747, 2011.
[11] Matthew Finifter, Devdatta Akhawe, and David Wagner, “An Empirical Study of Vulnerability Rewards Programs,” in 22nd USENIX Security Symposium, Washington, DC, 2013.
[12] Michael Sutton, Adam Greene, and Pedram Amini, Fuzzing: Brute Force Vulnerability Discovery. Boston, MA: Addison-Wesley, 2007.
[13]John Neystadt. (2008, February) Automated Penetration Testing with White-Box Fuzzing. [Online]. https://msdn.microsoft.com/en-us/library/cc162782.aspx
[14] P. Tsankov, M. T. Dashti, and D. Basin, “SECFUZZ: Fuzz-testing security protocols,” in 7th International Workshop on Automation of Software Test (AST), Zurich, 2012.
[15] Ai Fen Sui, Wen Tang, Jian Jun Hu, and Ming Zhu Li, “An effective fuzz input generation method for protocol testing,” in IEEE 13th International Conference on Communication Technology, Jinan, 2011.
[16] Fan Pan, Ying Hou, Zheng Hong, Lifa Wu, and Haiguang Lai, “Efficient Model-based Fuzz Testing Using Higher-order Attribute Grammars ,” Journal of Software, vol. 8,
37
no. 3, pp. 645 - 651, 2013.
[17] Greg Banks, Marco Cova, Viktoria Felmetsger, Keven Almeroth, Richard Kemmerer, and Giovanni Viga, “SNOOZE: Toward a Stateful NetwOrk prOtocol fuzZEr,” in 9th International Information Security Conference (ISC), Samos Island, 2006.
[18] María Villalba, Santiago Hernández, and Raquel Lacuesta, “MQTT security: A novel fuzzing approach,” Wireless Communications and Mobile Computing, vol. 2018, 2018.
[19] Aki Helin. radamsa - a general-purpose fuzzer. [Online]. https://gitlab.com/akihe/radamsa
[20] Peach Tech. Peach Fuzzer: Discover unknown vulnerabilities. [Online]. https://www.peach.tech/
[21] D Fowler, J Bryans, and S Shaikh, “Automating fuzz test generation to improve the security of the Controller Area Network,” in ACM Chapters Computer Science in Cars Symposium (CSCS), Munich, 2017.
[22] Zhao Zhang, Qiao Yan Wen, and Wen Tang, “An Efficient Mutation-based Fuzz Testing Approach for Detecting Flaws of Network Protocol,” in International Conference on Computer Science and Service System (CSSS), Beijing, 2012.
[23] X. Han, Q. Wen, and Z. Zhang, “A mutation-based fuzz testing approach for network protocol vulnerability detection,” in 2nd International Conference on Computer Science and Network Technology (ICCSNT), Changchun, 2012.
[24] Nikolas Havrikov, “Efficient Fuzz Testing Leveraging Input, Code, and Execution,” in 2017 IEEE/ACM 39th International Conference on Software Engineering Companion, Buenos Aires, 2017, pp. 417 - 420.
[25]Joshua Pereyda. boofuzz: Network Protocol Fuzzing for Humans. [Online]. https://github.com/jtpereyda/boofuzz
[26] MITRE. CWE - Common Weakness Enumeration. [Online]. https://cwe.mitre.org/
[27] MITRE. CVE - Common Vulnerabilities and Exposures. [Online]. https://cve.mitre.org/
[28] Zakir Durumeric, Frank Li, James Kasten, Johanna Amann, Jethro Beekman, Mathias Payer, Nicolas Weaver, David Adrian, Vern Paxson, Michael Balley, and J. Alex Halderman, “The Matter of Heartbleed,” in Conference on Internet Measurement Conference (IMC), New York, NY, 2014.
[29] FIRST. Common Vulnerability Scoring System SIG. [Online]. https://www.first.org/cvss/
[30] NIST Computer Security Division. National Vulnerability Database (NVD). [Online]. https://nvd.nist.gov/
[31] Tewodros Legesse Munea, Hyunwoo Lim, and Taeshik Shon, “Network protocol fuzz testing for information systems and applications: a survey and taxonomy,” Multimedia Tools and Applications, vol. 75, no. 22, pp. 14745 - 14757, 2016.
[32] S. Zamfir, T. Balan, I. Iliescu, and F. Sandu, “A security analysis on standard IoT protocols,” in International Conference on Applied and Theoretical Electricity
38

(ICATE), Craiova, 2016.
[33] MQTT. MQTT.org. [Online]. http://mqtt.org/
[34] International Organization for Standardization (ISO). ISO/IEC 20922:2016. [Online]. https://www.iso.org/standard/69466.html
[35] Kristiyan Mladenov. (2017) Formal verification of the implementation of the MQTT protocol in IoT devices. [Online]. https://pdfs.semanticscholar.org/09b9/a4a351eb29f5701e03a31caf14605379f32e.pdf
[36] OASIS. (2014, Oct.) MQTT Version 3.1.1 becomes an OASIS Standard. [Online]. https://www.oasis-open.org/news/announcements/mqtt-version-3-1-1-becomes-an- oasis-standard
[37] The Eclipse Foundation. iot.eclipse.org. [Online]. https://iot.eclipse.org/resources/case- studies/Eclipse%20IoT%20Success%20Story%20-%20DB.pdf
[38] Lucy Zhang. (2011, Aug.) Building Facebook Messenger. [Online]. https://www.facebook.com/notes/facebook-engineering/building-facebook- messenger/10150259350998920
[39] OASIS. (2018, May) MQTT Version 5.0. [Online]. https://docs.oasis- open.org/mqtt/mqtt/v5.0/mqtt-v5.0.html
[40] Roger Light. MQTT man page. [Online]. https://mosquitto.org/man/mqtt-7.html
[41] Zach Shelby, Klaus Hartke, and Carsten Bormann. (2014, June) RFC 7252 - The Constrained Application Protocol (CoAP). [Online]. https://tools.ietf.org/html/rfc7252
[42] B. C. Villaverde, D. Pesch, R. De Paz Alberola, S. Fedor, and M. Boubekeur, “Constrained Application Protocol for Low Power Embedded Networks: A Survey,” in Sixth International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing, Palermo, 2012.
[43] T. A. Alghamdi, A. Lasebae, and M. Aiash, “Security analysis of the constrained application protocol in the Internet of Things,” in Second International Conference on Future Generation Communication Technologies (FGCT), London, 2013.
[44] R. W. Hamming, “Error detecting and error correcting codes,” The Bell System Technical Journal, vol. 29, no. 2, pp. 147 - 160, 1950.
[45] A. X. Liu, K. Shen, and E. Torng, “Large scale Hamming distance query processing,” in IEEE 27th International Conference on Data Engineering, Hannover, 2011.
[46] Matthew A. Jaro, “Advances in Record-Linkage Methodology as Applied to Matching the 1985 Census of Census of Tampa, Florida,” Journal of the American Statistical Association, vol. 84, no. 406, pp. 414 - 420, 1989.
[47] T. N. Herzog, F. J. Scheuren, and W. E. Winkler, Data quality and record linkage techniques. New York, NY: Springer Science & Business Media, 2007.
[48] W. E. Winkler, “String Comparator Metrics and Enhanced Decision Rules in the Fellegi-Sunter Model of Record Linkage,” in Proceedings of the Section on Survey Research Methods, American Statistical Association, Washington, DC, 1990.
[49] William Cohen, Pradeep Ravikumar, and Stephen Fienberg, “A Comparison of String 39

Distance Metrics for Name-Matching Tasks,” in International Conference on Information Integration on the Web (IIWEB), Acapulco, 2003.
[50] Peter Christen, Data matching: concepts and techniques for record linkage, entity resolution, and duplicate detection. Berlin Heidelberg: Springer Science & Business Media, 2012.
[51] Vladimir I. Levenshtein, “Binary codes capable of correcting deletions, inserations, and reversals,” Soviet Physics Doklady, vol. 10, no. 8, pp. 707 - 710, 1966.
[52] Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze, Introduction to Information Retrieval. Cambridge: Cambridge University Press, 2008.
[53] L. Y ujian and L. Bo, “A Normalized Levenshtein Distance Metric,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, no. 6, pp. 1091 - 1095, 2007.
[54] A. Weigel and F. Fein, “Normalizing the Weighted Edit Distance,” in 12th IAPR International Conference on Pattern Recognition, Jerusalem, 1994.
[55]Daniel Jurafsky and James H. Martin, “Chapter 5: Probabilistic Models of Pronunciation and Spelling,” in Speech and Language Processing, 1st ed. Englewood Cliffs, NJ: Prentice Hall, Inc., 2000, pp. 139 - 187.
[56] NIST Computer Security Division. Common Vulnerability Scoring System Calculator Version 3. [Online]. https://nvd.nist.gov/vuln-metrics/cvss/v3- calculator?vector=AV:N/AC:L/PR:N/UI:N/S:U/C:H/I:N/A:N
[57]Tuomas Haanpää, “Fuzz Testing Coverage Measurement Based On Error Log Analysis,” Oulu, 2016.