More Web Proxy on the site http://driver.im/

research-article

Directed test generation using symbolic grammars

Authors:

Rupak Majumdar,

Ru-Gang XuAuthors Info & Claims

ASE '07: Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering

Pages 134 - 143

https://doi.org/10.1145/1321631.1321653

Published: 05 November 2007 Publication History

Abstract

We present CESE, a tool that combines exhaustive enumeration of test inputs from a structured domain with symbolic execution driven test generation. We target programs whose valid inputs are determined by some context free grammar. We abstract the concrete input syntax with symbolic grammars, where some original tokens are replaced with symbolic constants. This reduces the set of input strings that must be enumerated exhaustively. For each enumerated input string, which may contain symbolic constants, symbolic execution based test generation instantiates the constants based on program execution paths. The "template" generated by enumerating valid strings reduces the burden on the symbolic execution to generate syntactically valid inputs and helps exercise interesting code paths. Together, symbolic grammars provide a link between exhaustive enumeration of valid inputs and execution-directed symbolic test generation

Preliminary experiments with CESE show that the combination achieves better coverage than both pure enumerative test generation and pure directed symbolic test generation, in orders of magnitude less time and number of generated inputs. In addition, CESE is able to automatically generate inputs that achieve coverage within 10% of manually constructed tests.

References

[1]

M. Berkelaar, J. Dirks, K. Eikland, and P. Notebaert. lp_solve (5.5.0.10). 2007.

[2]

A. Bertolino, J. Gao, E. Marchetti, and A. Polini. Systematic generation of XML instances to test complex software applications. In RISE, 2006.

Digital Library

[3]

D. Beyer, A. J. Chlipala, T. A. Henzinger, R. Jhala, and R. Majumdar. Generating tests from counterexamples. In ICSE, 2004.

Digital Library

[4]

D. L. Bird and C. U. Munoz. Automatic generation of random self-checking test cases. IBM Systems Journal, 22(3):229--245, 1983.

Digital Library

[5]

C. Boyapati, S. Khurshid, and D. Marinov. Korat: automated testing based on Java predicates. In ISSTA, 2002.

Digital Library

[6]

C. Cadar, V. Ganesh, P. M. Pawlowski, D. L. Dill, and D. R. Engler. EXE: automatically generating inputs of death. In CCS, 2006.

Digital Library

[7]

K. Claessen and J. Hughes. Quickcheck: a lightweight tool for random testing of Haskell programs. In ICFP, 2000.

Digital Library

[8]

L. Clarke. A system to generate test data and symbolically execute programs. IEEE Trans.Software Eng., 2:215--222, 1976.

Digital Library

[9]

D. Coppit and J. Lian. yagg: an easy-to-use generator for structured test inputs. In ASE, 2005.

Digital Library

[10]

C. Csallner and Y. Smaragdakis. J. Crasher: An automatic robustness tester for Java. Software Practice & Experience, 34(11):1025--1050, 2004.

Digital Library

[11]

C. Csallner and Y. Smaragdakis. Check 'n' Crash: combining static checking and testing. In ICSE, 2005.

Digital Library

[12]

C. Csallner and Y. Smaragdakis. DSD-Crasher: a hybrid analysis tool for bug finding. In ISSTA, 2006.

Digital Library

[13]

N. Dor, M. Rodeh, and S. Sagiv. CSSV: towards a realistic tool for statically detecting all buffer overflows in c. In PLDI, 2003.

Digital Library

[14]

P. Godefroid. Compositional dynamic test generation. In POPL, 2007.

Digital Library

[15]

P. Godefroid, N. Klarlund, and K. Sen. DART: directed automated random testing. In PLDI, 2005.

Digital Library

[16]

J. B. Goodenough and S. L. Gerhart. Toward a theory of test data selection. IEEE Trans. Software Eng., 1(2):156--173, 1975.

Digital Library

[17]

R. Hamlet. Random testing. In Encyclopedia of Software Engineering, pages 970--978. Wiley, 1994.

[18]

S. C. Johnson. YACC - yet another compiler-compiler. Bell Labs Tehnical Report, (32), 1975.

[19]

S. Khurshid and D. Marinov. TestEra: Specification-based testing of Java programs using SAT. Autom. Softw. Eng., 11(4):403--434, 2004.

Digital Library

[20]

J. C. King. Symbolic execution and program testing. Commun. ACM, 19(7):385--394, 1976.

Digital Library

[21]

R. Lämmel and W. Schulte. Controllable combinatorial coverage in grammar-based testing. In TestCom, 2006.

Digital Library

[22]

M. E. Lesk and E. Schmidt. Lex - a lexical analyser generator. Bell Labs Tehnical Report, (39), 1975.

[23]

R. Majumdar and K. Sen. Hybrid concolic testing. In ICSE, 2007.

Digital Library

[24]

P. M. Maurer. Generating test data with enhanced context-free grammars. IEEE Software, 7(4):50--55, 1990.

Digital Library

[25]

W. M. McKeeman. Differential testing for software. Digital Technical Journal, 10(1):100--107, 1998.

[26]

B. P. Miller, G. Cooksey, and F. Moore. An empirical study of the robustness of macos applications using random testing. In Random Testing, 2006.

Digital Library

[27]

B. P. Miller, L. Fredriksen, and B. So. An empirical study of the reliability of unix utilities. Commun. ACM, 33(12):32--44, 1990.

Digital Library

[28]

A. J. Offutt and J. H. Hayes. A semantic model of program faults. In ISSTA, 1996.

Digital Library

[29]

C. Pacheco and M. D. Ernst. Eclat: Automatic generation and classification of test inputs. In ECOOP, 2005.

Digital Library

[30]

C. Pacheco, S. K. Lahiri, M. D. Ernst, and T. Ball. Feedback-directed random test generation. In ICSE, 2007.

Digital Library

[31]

K. Sen, D. Marinov, and G. Agha. Cute: a concolic unit testing engine for c. In FSE, 2005.

Digital Library

[32]

M. Sipser. Introduction to the theory of computation. pages 91--101, 1997.

Digital Library

[33]

E. Sirer and B. N. Bershad. Using production grammars in software testing. In DSL, 1999.

Digital Library

[34]

D. R. Slutz. Massive stochastic testing of SQL. In VLDB, 1998.

Digital Library

[35]

W. Visser, C. S. Pasareanu, and S. Khurshid. Test input generation with Java PathFinder. In ISSTA, 2004.

Digital Library

Cited By

Jiang ZWen MCao JShi XJin HFilkov VRay BZhou M(2024)Towards Understanding the Effectiveness of Large Language Models on Directed Test Input GenerationProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695513(1408-1420)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695513
Liu JZhu FHe F(2023)Automated Ambiguity Detection in Layout-Sensitive GrammarsProceedings of the ACM on Programming Languages10.1145/36228387:OOPSLA2(1150-1175)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622838
Ye GHu TTang ZFan ZTan SZhang BQian WWang ZChandra SBlincoe KTonella P(2023)A Generative and Mutational Approach for Synthesizing Bug-Exposing Test Cases to Guide Compiler FuzzingProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616332(1127-1139)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616332
Show More Cited By

Index Terms

Directed test generation using symbolic grammars
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

Directed test generation using symbolic grammars
ESEC-FSE '07: Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering

We present CESI, an algorithm that combines exhaustive enumeration of test inputs from a structured domain with symbolic execution driven test generation. We target programs whose valid inputs are determined by some context free grammar. We introduce ...
Directed test generation using symbolic grammars
ESEC-FSE companion '07: The 6th Joint Meeting on European software engineering conference and the ACM SIGSOFT symposium on the foundations of software engineering: companion papers

We present CESI, an algorithm that combines exhaustive enumeration of test inputs from a structured domain with symbolic execution driven test generation. CESI is a hybrid of two predominant techniques: specification-based enumerative test generation (...
Concolic testing
ASE '07: Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering

Concolic testing automates test input generation by combining the concrete and symbolic (concolic) execution of the code under test. Traditional test input generation techniques use either (1) concrete execution or (2) symbolic execution that builds ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASE '07: Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering

November 2007

590 pages

ISBN:9781595938824

DOI:10.1145/1321631

General Chair:
Kurt Stirewalt
Michigan State University, USA
,
Program Chairs:
Alexander Egyed
Teknowledge Corporation, USA
,
Bernd Fischer
University of Southampton, UK

Copyright © 2007 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ASE07

Sponsor:

ASE07: International Conference on Automated Software Engineering 2007

November 5 - 9, 2007

Georgia, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 82 of 337 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

67
Total Citations
View Citations
762
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)2

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jiang ZWen MCao JShi XJin HFilkov VRay BZhou M(2024)Towards Understanding the Effectiveness of Large Language Models on Directed Test Input GenerationProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695513(1408-1420)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695513
Liu JZhu FHe F(2023)Automated Ambiguity Detection in Layout-Sensitive GrammarsProceedings of the ACM on Programming Languages10.1145/36228387:OOPSLA2(1150-1175)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622838
Ye GHu TTang ZFan ZTan SZhang BQian WWang ZChandra SBlincoe KTonella P(2023)A Generative and Mutational Approach for Synthesizing Bug-Exposing Test Cases to Guide Compiler FuzzingProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616332(1127-1139)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616332
Candea GGodefroid P(2022)Automated Software Test Generation: Some Challenges, Solutions, and Recent AdvancesComputing and Software Science10.1007/978-3-319-91908-9_24(505-531)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-319-91908-9_24
Heinricher AWilliams RKlingbeil AJordan ADo LUrban C(2021)Weldr: fusing binaries for simplified analysisProceedings of the 10th ACM SIGPLAN International Workshop on the State Of the Art in Program Analysis10.1145/3460946.3464320(25-30)Online publication date: 22-Jun-2021
https://dl.acm.org/doi/10.1145/3460946.3464320
Pan WChen ZZhang GLuo YZhang YWang JCadar CZhang X(2021)Grammar-agnostic symbolic execution by token symbolizationProceedings of the 30th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3460319.3464845(374-387)Online publication date: 11-Jul-2021
https://dl.acm.org/doi/10.1145/3460319.3464845
Ye GTang ZTan SHuang SFang DSun XBian LWang HWang ZFreund SYahav E(2021)Automated conformance testing for JavaScript engines via deep compiler fuzzingProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454054(435-450)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454054
Wu ZJohnson EYang WBastani OSong DPeng JXie TDumas MPfahl DApel SRusso A(2019)REINAM: reinforcement learning for input-grammar inferenceProceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3338906.3338958(488-498)Online publication date: 12-Aug-2019
https://dl.acm.org/doi/10.1145/3338906.3338958
Atlidakis VGodefroid PPolishchuk MAtlee JBultan TWhittle J(2019)RESTlerProceedings of the 41st International Conference on Software Engineering10.1109/ICSE.2019.00083(748-758)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.1109/ICSE.2019.00083
Lin CHuang CTien C(2019)Boosting Fuzzing Performance with Differential Seed Scheduling2019 14th Asia Joint Conference on Information Security (AsiaJCIS)10.1109/AsiaJCIS.2019.000-3(72-79)Online publication date: Aug-2019
https://doi.org/10.1109/AsiaJCIS.2019.000-3
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