research-article

Making symbolic execution promising by learning aggressive state-pruning strategy

Authors:

Hakjoo OhAuthors Info & Claims

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

Pages 147 - 158

https://doi.org/10.1145/3368089.3409755

Published: 08 November 2020 Publication History

Abstract

We present HOMI, a new technique to enhance symbolic execution by maintaining only a small number of promising states. In practice, symbolic execution typically maintains as many states as possible in a fear of losing important states. In this paper, however, we show that only a tiny subset of the states plays a significant role in increasing code coverage or reaching bug points. Based on this observation, HOMI aims to minimize the total number of states while keeping “promising” states during symbolic execution. We identify promising states by a learning algorithm that continuously updates the probabilistic pruning strategy based on data accumulated during the testing process. Experimental results show that HOMI greatly increases code coverage and the ability to find bugs of KLEE on open-source C programs.

Supplementary Material

Auxiliary Teaser Video (fse20main-p667-p-teaser.mp4)

We present HOMI, a new technique to enhance symbolic execution by maintaining only a small number of promising states. In practice, symbolic execution typically maintains as many states as possible in a fear of losing important states. In this paper, however, we show that only a tiny subset of the states plays a significant role in increasing code coverage or reaching bug points. Based on this observation, HOMI aims to minimize the total number of states while keeping “promising” states during symbolic execution. We identify promising states by a learning algorithm that continuously updates the probabilistic pruning strategy based on data accumulated during the testing process. Experimental results show that HOMI greatly increases code coverage and the ability to find bugs of KLEE on open-source C programs.

Download
6.01 MB

Auxiliary Presentation Video (fse20main-p667-p-video.mp4)

We present HOMI, a new technique to enhance symbolic execution by maintaining only a small number of promising states. In practice, symbolic execution typically maintains as many states as possible in a fear of losing important states. In this paper, however, we show that only a tiny subset of the states plays a significant role in increasing code coverage or reaching bug points. Based on this observation, HOMI aims to minimize the total number of states while keeping “promising” states during symbolic execution. We identify promising states by a learning algorithm that continuously updates the probabilistic pruning strategy based on data accumulated during the testing process. Experimental results show that HOMI greatly increases code coverage and the ability to find bugs of KLEE on open-source C programs.

Download
50.72 MB

References

[1]

Saswat Anand, Mayur Naik, Mary Jean Harrold, and Hongseok Yang. 2012. Automated Concolic Testing of Smartphone Apps. In Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering (FSE '12). 1-11.

Digital Library

[2]

Peter Boonstoppel, Cristian Cadar, and Dawson Engler. 2008. RWset: Attacking path explosion in constraint-based test generation. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS '08). 351-366.

[3]

Suhabe Bugrara and Dawson Engler. 2013. Redundant State Detection for Dynamic Symbolic Execution. In Proceedings of the 2013 USENIX Conference on Annual Technical Conference (USENIX ATC'13). 199-212.

[4]

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

[5]

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.

[6]

Cristian Cadar and Dawson Engler. 2005. Execution Generated Test Cases: How to Make Systems Code Crash Itself. In Proceedings of the 12th International Conference on Model Checking Software (SPIN'05). 2-23.

Digital Library

[7]

Cristian Cadar, Vijay Ganesh, Peter M. Pawlowski, David L. Dill, and Dawson R. Engler. 2008. EXE: Automatically Generating Inputs of Death. ACM Trans. Inf. Syst. Secur. 12, 2 ( 2008 ), 10 : 1-10 : 38.

Digital Library

[8]

Cristian Cadar and Koushik Sen. 2013. Symbolic Execution for Software Testing: Three Decades Later. Commun. ACM 56, 2 ( 2013 ), 82-90.

[9]

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

[10]

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

[11]

Sooyoung Cha and Hakjoo Oh. 2019. Concolic Testing with Adaptively Changing Search Heuristics. In Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE '19). 235-245.

Digital Library

[12]

Junjie Chen, Wenxiang Hu, Lingming Zhang, Dan Hao, Sarfraz Khurshid, and Lu Zhang. 2018. Learning to accelerate symbolic execution via code transformation. In 32nd European Conference on Object-Oriented Programming (ECOOP '18).

[13]

Vijay Ganesh and David L. Dill. 2007. A Decision Procedure for Bit-Vectors and Arrays. In Proceedings of the 19th International Conference on Computer Aided Verification (CAV'07). 519-531.

[14]

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

[15]

Joxan Jafar, 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.

[16]

Richard M Karp. 1972. Reducibility among combinatorial problems. In Complexity of computer computations. 85-103.

[17]

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.

[18]

Xin Li, Yongjuan Liang, Hong Qian, Yi-Qi Hu, Lei Bu, Yang Yu, Xin Chen, and Xuandong Li. 2016. Symbolic Execution of Complex Program Driven by Machine Learning Based Constraint Solving. In Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering (ASE '16). 554-559.

Digital Library

[19]

You Li, Zhendong Su, Linzhang Wang, and Xuandong Li. 2013. Steering Symbolic Execution to Less Traveled Paths. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages, and Applications (OOPSLA '13). 19-32.

Digital Library

[20]

Loi Luu, Duc-Hiep Chu, Hrishi Olickel, Prateek Saxena, and Aquinas Hobor. 2016. Making Smart Contracts Smarter. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS '16). 254-269.

Digital Library

[21]

Sergey Mechtaev, Alberto Griggio, Alessandro Cimatti, and Abhik Roychoudhury. 2018. Symbolic Execution with Existential Second-Order Constraints. 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). 389-399.

Digital Library

[22]

Ivica Nikoliundefined, Aashish Kolluri, Ilya Sergey, Prateek Saxena, and Aquinas Hobor. 2018. Finding The Greedy, Prodigal, and Suicidal Contracts at Scale. In Proceedings of the 34th Annual Computer Security Applications Conference (ACSAC '18). 653-663.

[23]

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.

[24]

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

[25]

Shiqi Shen, Shweta Shinde, Soundarya Ramesh, Abhik Roychoudhury, and Prateek Saxena. 2019. Neuro-Symbolic Execution: Augmenting Symbolic Execution with Neural Constraints. In Proceedings of the Symposium on Network and Distributed System Security (NDSS '19).

[26]

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

[27]

David Trabish, Andrea Mattavelli, Noam Rinetzky, and Cristian Cadar. 2018. Chopped Symbolic Execution. In Proceedings of the 40th International Conference on Software Engineering (ICSE '18). 350-360.

Digital Library

[28]

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

[29]

E. Wong, L. Zhang, S. Wang, T. Liu, and L. Tan. 2015. DASE: DocumentAssisted Symbolic Execution for Improving Automated Software Testing. In 2015 IEEE/ACM 37th IEEE International Conference on Software Engineering (ICSE '15). 620-631.

[30]

Qiuping Yi, Zijiang Yang, Shengjian Guo, Chao Wang, Jian Liu, and Chen Zhao. 2015. Postconditioned Symbolic Execution. In 2015 IEEE 8th International Conference on Software Testing, Verification and Validation (ICST '15). 1-10.

[31]

Qiuping Yi, Zijiang Yang, Shengjian Guo, Chao Wang, Jian Liu, and Chen Zhao. 2018. Eliminating Path Redundancy via Postconditioned Symbolic Execution. IEEE Transactions on Software Engineering ( 2018 ), 25-43.

Digital Library

Cited By

Yoon JCha S(2024)FeatMaker: Automated Feature Engineering for Search Strategy of Symbolic ExecutionProceedings of the ACM on Software Engineering10.1145/36608151:FSE(2447-2468)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3660815
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
Yang MLie DPapernot N(2024)Exploring Strategies for Guiding Symbolic Analysis with Machine Learning Prediction2024 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER60148.2024.00073(659-669)Online publication date: 12-Mar-2024
https://doi.org/10.1109/SANER60148.2024.00073
Show More Cited By

Index Terms

Making symbolic execution promising by learning aggressive state-pruning strategy
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

Targeted program transformations for symbolic execution
ESEC/FSE 2015: Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering

Semantics-preserving program transformations, such as refactorings and optimisations, can have a significant impact on the effectiveness of symbolic execution testing and analysis. Furthermore, semantics-preserving transformations that increase the ...
Experience report: how is dynamic symbolic execution different from manual testing? a study on KLEE
ISSTA 2015: Proceedings of the 2015 International Symposium on Software Testing and Analysis

Software testing has been the major approach to software quality assurance for decades, but it typically involves intensive manual efforts. To reduce manual efforts, researchers have proposed numerous approaches to automate test-case generation, which ...
Veritesting Challenges in Symbolic Execution of Java

Scaling symbolic execution to industrial-sized programs is an important open research problem. Veritesting is a promising technique that improves scalability by combining the advantages of static symbolic execution with those of dynamic symbolic ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

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

November 2020

1703 pages

ISBN:9781450370431

DOI:10.1145/3368089

General Chair:
Prem Devanbu
University of California at Davis, USA
,
Program Chairs:
Myra Cohen
Iowa State University, USA
,
Thomas Zimmermann
Microsoft Research, USA

Copyright © 2020 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: 08 November 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Conference

ESEC/FSE '20

Sponsor:

SIGSOFT

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

November 8 - 13, 2020

Virtual Event, USA

Acceptance Rates

Overall Acceptance Rate 112 of 543 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
472
Total Downloads

Downloads (Last 12 months)97
Downloads (Last 6 weeks)8

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yoon JCha S(2024)FeatMaker: Automated Feature Engineering for Search Strategy of Symbolic ExecutionProceedings of the ACM on Software Engineering10.1145/36608151:FSE(2447-2468)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3660815
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
Yang MLie DPapernot N(2024)Exploring Strategies for Guiding Symbolic Analysis with Machine Learning Prediction2024 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER60148.2024.00073(659-669)Online publication date: 12-Mar-2024
https://doi.org/10.1109/SANER60148.2024.00073
Sun YLi ZLv SSun L(2023)Spenny: Extensive ICS Protocol Reverse Analysis via Field Guided Symbolic ExecutionIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2022.322807620:6(4502-4518)Online publication date: Nov-2023
https://doi.org/10.1109/TDSC.2022.3228076
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
Zhang ZChen LWei HDong GZhang YNie XShi G(2022)Binary-level Directed Symbolic Execution Through Pattern Learning2022 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom)10.1109/ISPA-BDCloud-SocialCom-SustainCom57177.2022.00014(50-57)Online publication date: Dec-2022
https://doi.org/10.1109/ISPA-BDCloud-SocialCom-SustainCom57177.2022.00014
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
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

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