research-article

Concolic testing with adaptively changing search heuristics

Authors:

Hakjoo OhAuthors Info & Claims

ESEC/FSE 2019: Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering

Pages 235 - 245

https://doi.org/10.1145/3338906.3338964

Published: 12 August 2019 Publication History

Abstract

We present Chameleon, a new approach for adaptively changing search heuristics during concolic testing. Search heuristics play a central role in concolic testing as they mitigate the path-explosion problem by focusing on particular program paths that are likely to increase code coverage as quickly as possible. A variety of techniques for search heuristics have been proposed over the past decade. However, existing approaches are limited in that they use the same search heuristics throughout the entire testing process, which is inherently insufficient to exercise various execution paths. Chameleon overcomes this limitation by adapting search heuristics on the fly via an algorithm that learns new search heuristics based on the knowledge accumulated during concolic testing. Experimental results show that the transition from the traditional non-adaptive approaches to ours greatly improves the practicality of concolic testing in terms of both code coverage and bug-finding.

References

[1]

Thanassis Avgerinos, Alexandre Rebert, Sang Kil Cha, and David Brumley. 2014. Enhancing Symbolic Execution with Veritesting. In Proceedings of the 36th International Conference on Software Engineering (ICSE ’14). 1083–1094.

Digital Library

[2]

James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. 2011. Algorithms for Hyper-parameter Optimization. In Proceedings of the 24th International Conference on Neural Information Processing Systems (NIPS’11). 2546–2554.

Digital Library

[3]

Jacob Burnim and Koushik Sen. 2008. Heuristics for Scalable Dynamic Test Generation. In Proceedings of 23rd IEEE/ACM International Conference on Automated Software Engineering (ASE ’08). 443–446.

Digital Library

[4]

Cristian Cadar, Daniel Dunbar, and Dawson Engler. 2008. KLEE: Unassisted and Automatic Generation of High-coverage Tests for Complex Systems Programs. In Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation (OSDI ’08). 209–224.

Digital Library

[5]

Sooyoung Cha, Seongjoon Hong, Junhee Lee, and Hakjoo Oh. 2018. Automatically Generating Search Heuristics for Concolic Testing. In Proceedings of the 40th International Conference on Software Engineering (ICSE ’18). 1244–1254.

Digital Library

[6]

Sooyoung Cha, Seonho Lee, and Hakjoo Oh. 2018. Template-guided Concolic Testing via Online Learning. In Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering (ASE ’18). 408–418.

Digital Library

[7]

Wontae Choi, George Necula, and Koushik Sen. 2013. Guided GUI Testing of Android Apps with Minimal Restart and Approximate Learning. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages &#38; Applications (OOPSLA ’13). 623–640.

Digital Library

[8]

CREST. A concolic test generation tool for C. 2008. https://github.com/jburnim/ crest.

[9]

Przemysław Daca, Ashutosh Gupta, and Thomas A. Henzinger. 2016. Abstractiondriven Concolic Testing. In Proceedings of the 17th International Conference on Verification, Model Checking, and Abstract Interpretation - Volume 9583 (VMCAI ’16). 328–347.

Digital Library

[10]

Drew Davidson, Benjamin Moench, Thomas Ristenpart, and Somesh Jha. 2013. FIE on Firmware: Finding Vulnerabilities in Embedded Systems Using Symbolic Execution. In Presented as part of the 22nd USENIX Security Symposium (USENIX Security ’13). 463–478.

Digital Library

[11]

Patrice Godefroid, Nils Klarlund, and Koushik Sen. 2005. DART: Directed Automated Random Testing. In Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’05). 213–223.

Digital Library

[12]

Patrice Godefroid, Michael Y Levin, and David A Molnar. 2008. Automated Whitebox Fuzz Testing. In Proceedings of the Symposium on Network and Distributed System Security (NDSS ’08). 151–166.

[13]

Patrice Godefroid, Hila Peleg, and Rishabh Singh. 2017. Learn&fuzz: Machine learning for input fuzzing. In Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE ’17). 50–59.

Digital Library

[14]

Grant Hernandez, Farhaan Fowze, Dave (Jing) Tian, Tuba Yavuz, and Kevin R.B. Butler. 2017. FirmUSB: Vetting USB Device Firmware Using Domain Informed Symbolic Execution. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS ’17). 2245–2262.

Digital Library

[15]

Dorit S. Hochbaum (Ed.). 1997. Approximation Algorithms for NP-hard Problems. PWS Publishing Co., Boston, MA, USA.

Digital Library

[16]

Gang Hu, Linjie Zhu, and Junfeng Yang. 2018. AppFlow: Using Machine Learning to Synthesize Robust, Reusable UI Tests. In Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE ’18). 269–282.

Digital Library

[17]

Joxan Jaffar, Vijayaraghavan Murali, and Jorge A. Navas. 2013. Boosting Concolic Testing via Interpolation. In Proceedings of the 9th Joint Meeting on Foundations of Software Engineering (ESEC/FSE ’13). 48–58.

Digital Library

[18]

Yue Jia, Myra B. Cohen, Mark Harman, and Justyna Petke. 2015. Learning Combinatorial Interaction Test Generation Strategies Using Hyperheuristic Search. In Proceedings of the 37th International Conference on Software Engineering - Volume 1 (ICSE ’15). 540–550.

Digital Library

[19]

Su Yong Kim, Sangho Lee, Insu Yun, Wen Xu, Byoungyoung Lee, Youngtae Yun, and Taesoo Kim. 2017. CAB-Fuzz: Practical Concolic Testing Techniques for COTS Operating Systems. In 2017 USENIX Annual Technical Conference (USENIX ATC ’17). 689–701.

Digital Library

[20]

Yunho Kim, Yunja Choi, and Moonzoo Kim. 2018. Precise Concolic Unit Testing of C Programs Using Extended Units and Symbolic Alarm Filtering. In Proceedings of the 40th International Conference on Software Engineering (ICSE ’18). 315–326.

Digital Library

[21]

Yunho Kim and Moonzoo Kim. 2011. SCORE: A Scalable Concolic Testing Tool for Reliable Embedded Software. In Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering (ESEC/FSE ’11). 420–423.

Digital Library

[22]

Yunho Kim, Moonzoo Kim, YoungJoo Kim, and Yoonkyu Jang. 2012. Industrial Application of Concolic Testing Approach: A Case Study on Libexif by Using CREST-BV and KLEE. In Proceedings of the 34th International Conference on Software Engineering (ICSE ’12). 1143–1152.

Digital Library

[23]

Yavuz Koroglu, Alper Sen, Ozlem Muslu, Yunus Mete, Ceyda Ulker, Tolga Tanriverdi, and Yunus Donmez. 2018. QBE: QLearning-based exploration of android applications. In 2018 IEEE 11th International Conference on Software Testing, Verification and Validation (ICST ’18). 105–115.

[24]

Hongbo Li, Sihuan Li, Zachary Benavides, Zizhong Chen, and Rajiv Gupta. 2018. COMPI: Concolic Testing for MPI Applications. 2018 IEEE International Parallel and Distributed Processing Symposium (2018), 865–874.

[25]

Rupak Majumdar and Koushik Sen. 2007. Hybrid Concolic Testing. In Proceedings of the 29th International Conference on Software Engineering (ICSE ’07). 416–426.

Digital Library

[26]

Sangmin Park, B. M. Mainul Hossain, Ishtiaque Hussain, Christoph Csallner, Mark Grechanik, Kunal Taneja, Chen Fu, and Qing Xie. 2012. CarFast: Achieving Higher Statement Coverage Faster. In Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering (FSE ’12). 35:1–35:11.

Digital Library

[27]

Koushik Sen, Darko Marinov, and Gul Agha. 2005. CUTE: A Concolic Unit Testing Engine for C. In Proceedings of the 10th European Software Engineering Conference Held Jointly with 13th ACM SIGSOFT International Symposium on Foundations of Software Engineering (ESEC/FSE ’05). 263–272.

[28]

Hyunmin Seo and Sunghun Kim. 2014. How We Get There: A Context-guided Search Strategy in Concolic Testing. In Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE ’14). 413– 424.

Digital Library

[29]

Helge Spieker, Arnaud Gotlieb, Dusica Marijan, and Morten Mossige. 2017. Reinforcement Learning for Automatic Test Case Prioritization and Selection in Continuous Integration. In Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA ’17). 12–22.

Digital Library

[30]

Youcheng Sun, Min Wu, Wenjie Ruan, Xiaowei Huang, Marta Kwiatkowska, and Daniel Kroening. 2018. Concolic Testing for Deep Neural Networks. In Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering (ASE ’18). 109–119.

Digital Library

[31]

Junjie Wang, Bihuan Chen, Lei Wei, and Yang Liu. 2017. Skyfire: Data-driven seed generation for fuzzing. In 2017 IEEE Symposium on Security and Privacy (S&P ’17). 579–594.

[32]

Xinyu Wang, Jun Sun, Zhenbang Chen, Peixin Zhang, Jingyi Wang, and Yun Lin. 2018. Towards Optimal Concolic Testing. In Proceedings of the 40th International Conference on Software Engineering (ICSE ’18). 291–302.

Digital Library

[33]

Insu Yun, Sangho Lee, Meng Xu, Yeongjin Jang, and Taesoo Kim. 2018. QSYM : A Practical Concolic Execution Engine Tailored for Hybrid Fuzzing. In 27th USENIX Security Symposium (USENIX Security ’18). 745–761.

Digital Library

Cited By

Sun YYang GLv SLi ZSun LRoychoudhury APaiva AAbreu RStorey M(2024)Concrete Constraint Guided Symbolic ExecutionProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639078(1-12)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3639078
Nilizadeh FDashtbani HMouzarani M(2023)Parameterized Search Heuristic Prediction for Concolic Execution2023 30th Asia-Pacific Software Engineering Conference (APSEC)10.1109/APSEC60848.2023.00050(396-404)Online publication date: 4-Dec-2023
https://doi.org/10.1109/APSEC60848.2023.00050
Wang MFei WWang MCui J(2023)Reinforcement Learning Guided Symbolic Execution for Ethereum Smart Contracts2023 30th Asia-Pacific Software Engineering Conference (APSEC)10.1109/APSEC60848.2023.00019(91-100)Online publication date: 4-Dec-2023
https://doi.org/10.1109/APSEC60848.2023.00019
Show More Cited By

Index Terms

Concolic testing with adaptively changing search heuristics
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

Automatically generating search heuristics for concolic testing
ICSE '18: Proceedings of the 40th International Conference on Software Engineering

We present a technique to automatically generate search heuristics for concolic testing. A key challenge in concolic testing is how to effectively explore the program's execution paths to achieve high code coverage in a limited time budget. Concolic ...
Grey-box concolic testing on binary code
ICSE '19: Proceedings of the 41st International Conference on Software Engineering

We present grey-box concolic testing, a novel path-based test case generation method that combines the best of both white-box and grey-box fuzzing. At a high level, our technique systematically explores execution paths of a program under test as in white-...
Template-guided concolic testing via online learning
ASE '18: Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering

We present template-guided concolic testing, a new technique for effectively reducing the search space in concolic testing. Addressing the path-explosion problem has been a significant challenge in concolic testing. Diverse search heuristics have been ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ESEC/FSE 2019: Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering

August 2019

1264 pages

ISBN:9781450355728

DOI:10.1145/3338906

General Chairs:
Marlon Dumas
University of Tartu, Estonia
,
Dietmar Pfahl
University of Tartu, Estonia
,
Program Chairs:
Sven Apel
Saarland University, Germany
,
Alessandra Russo
Imperial College, UK

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 August 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ESEC/FSE '19

Sponsor:

SIGSOFT

ESEC/FSE '19: 27th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering

August 26 - 30, 2019

Tallinn, Estonia

Acceptance Rates

Overall Acceptance Rate 112 of 543 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
395
Total Downloads

Downloads (Last 12 months)43
Downloads (Last 6 weeks)3

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sun YYang GLv SLi ZSun LRoychoudhury APaiva AAbreu RStorey M(2024)Concrete Constraint Guided Symbolic ExecutionProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639078(1-12)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3639078
Nilizadeh FDashtbani HMouzarani M(2023)Parameterized Search Heuristic Prediction for Concolic Execution2023 30th Asia-Pacific Software Engineering Conference (APSEC)10.1109/APSEC60848.2023.00050(396-404)Online publication date: 4-Dec-2023
https://doi.org/10.1109/APSEC60848.2023.00050
Wang MFei WWang MCui J(2023)Reinforcement Learning Guided Symbolic Execution for Ethereum Smart Contracts2023 30th Asia-Pacific Software Engineering Conference (APSEC)10.1109/APSEC60848.2023.00019(91-100)Online publication date: 4-Dec-2023
https://doi.org/10.1109/APSEC60848.2023.00019
Baradaran SHeidari MKamali AMouzarani M(2023)A unit-based symbolic execution method for detecting memory corruption vulnerabilities in executable codesInternational Journal of Information Security10.1007/s10207-023-00691-122:5(1277-1290)Online publication date: 7-May-2023
https://doi.org/10.1007/s10207-023-00691-1
Cha SLee MLee SOh HDwyer MDamian DZeller A(2022)SymTunerProceedings of the 44th International Conference on Software Engineering10.1145/3510003.3510185(2068-2079)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510003.3510185
Cha SHong SBak JKim JLee JOh H(2022)Enhancing Dynamic Symbolic Execution by Automatically Learning Search HeuristicsIEEE Transactions on Software Engineering10.1109/TSE.2021.310187048:9(3640-3663)Online publication date: 1-Sep-2022
https://doi.org/10.1109/TSE.2021.3101870
Zhang GChen ZShuai ZZhang YWang J(2022)Synergizing Symbolic Execution and Fuzzing By Function-level Selective Symbolization2022 29th Asia-Pacific Software Engineering Conference (APSEC)10.1109/APSEC57359.2022.00045(328-337)Online publication date: Dec-2022
https://doi.org/10.1109/APSEC57359.2022.00045
Mouzarani MKamali ABaradaran SHeidari M(2022)A Unit-Based Symbolic Execution Method for Detecting Heap Overflow Vulnerability in Executable CodesTests and Proofs10.1007/978-3-031-09827-7_6(89-105)Online publication date: 22-Jun-2022
https://doi.org/10.1007/978-3-031-09827-7_6
Luo CSun BQiao BChen JZhang HLin JLin QZhang DSpinellis DGousios GChechik MDi Penta M(2021)LS-sampling: an effective local search based sampling approach for achieving high t-wise coverageProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468622(1081-1092)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468622
He JSivanrupan GTsankov PVechev MKim YKim JVigna GShi E(2021)Learning to Explore Paths for Symbolic ExecutionProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security10.1145/3460120.3484813(2526-2540)Online publication date: 12-Nov-2021
https://dl.acm.org/doi/10.1145/3460120.3484813
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents