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

research-article

CLOTHO: saving programs from malformed strings and incorrect string-handling

Authors:

Rahul Purandare,

Suresh RangaswamyAuthors Info & Claims

ESEC/FSE 2015: Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering

Pages 555 - 566

https://doi.org/10.1145/2786805.2786877

Published: 30 August 2015 Publication History

Abstract

Software is susceptible to malformed data originating from untrusted sources. Occasionally the programming logic or constructs used are inappropriate to handle the varied constraints imposed by legal and well-formed data. Consequently, softwares may produce unexpected results or even crash. In this paper, we present CLOTHO, a novel hybrid approach that saves such softwares from crashing when failures originate from malformed strings or inappropriate handling of strings. CLOTHO statically analyses a program to identify statements that are vulnerable to failures related to associated string data. CLOTHO then generates patches that are likely to satisfy constraints on the data, and in case of failures produces program behavior which would be close to the expected. The precision of the patches is improved with the help of a dynamic analysis. We have implemented CLOTHO for the JAVA String API, and our evaluation based on several popular open-source libraries shows that CLOTHO generates patches that are semantically similar to the patches generated by the programmers in the later versions. Additionally, these patches are activated only when a failure is detected, and thus CLOTHO incurs no runtime overhead during normal execution, and negligible overhead in case of failures.

References

[1]

Amazon sellers hit by nightmare before Christmas as glitch cuts prices to 1p. http://www.theguardian.com/money/2014/dec/14/ amazon-glitch-prices-penny-repricerexpress.

[2]

Nike Rebounds: How (and Why) Nike Recovered from Its Supply Chain Disaster. http://www.cio.com/article/2439601/supplychain-management/nike-rebounds--how--andwhy--nike-recovered-from-its-supply-chaindisaster.html.

[3]

Supply Chain: Hershey’s Bittersweet Lesson. http://www.cio.com/article/2440386/supplychain-management/supply-chain---hershey-sbittersweet-lesson.html.

[4]

When Bad Things Happen to Good Projects. http://www.cio.com/article/2439385/projectmanagement/when-bad-things-happen-to-goodprojects.html.

[5]

ARIES-1204. Stringindexoutofbounds for blueprint apps that have constructors with multiple exceptions. https://issues.apache.org/jira/browse/ARIES- 1204, 2014.

[6]

Michael Carbin, Sasa Misailovic, Michael Kling, and Martin C. Rinard. Detecting and escaping infinite loops with jolt. In Proceedings of the 25th European Conference on Object-oriented Programming, ECOOP’11, pages 609–633, Berlin, Heidelberg, 2011. Springer-Verlag.

Digital Library

[7]

Pavol Cerny, ThomasA. Henzinger, Arjun Radhakrishna, Leonid Ryzhyk, and Thorsten Tarrach. Regression-free synthesis for concurrency. In Armin Biere and Roderick Bloem, editors, Computer Aided Verification, volume 8559 of Lecture Notes in Computer Science, pages 568–584. Springer International Publishing, 2014.

Digital Library

[8]

CLI-46. java.lang.stringindexoutofboundsexception. https://issues.apache.org/jira/browse/CLI-46, 2007.

[9]

CLI193. Stringindexoutofboundsexception in helpformatter.findwrappos. https://issues.apache.org/jira/browse/CLI-193, 2010.

[10]

COMPRESS-26. Tararchiveentry(file) now crashes on file system roots. https://issues.apache.org/jira/browse/ COMPRESS-26, 2009.

[11]

Brian Demsky, Michael D. Ernst, Philip J. Guo, Stephen McCamant, Jeff H. Perkins, and Martin C. Rinard. Inference and enforcement of data structure consistency specifications. In Proceedings of the ACM/SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2006, Portland, Maine, USA, July 17-20, 2006, pages 233–244, 2006.

Digital Library

[12]

Brian Demsky and Martin Rinard. Automatic data structure repair for self-healing systems. In In Proceedings of the 1st Workshop on Algorithms and Architectures for Self-Managing Systems, 2003.

[13]

Brian Demsky and Martin C. Rinard. Automatic detection and repair of errors in data structures. In Proceedings of the 2003 ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications, OOPSLA 2003, October 26-30, 2003, Anaheim, CA, USA, pages 78–95, 2003.

Digital Library

[14]

Brian Demsky and Martin C. Rinard. Static specification analysis for termination of specification-based data structure repair. In 14th International Symposium on Software Reliability Engineering (ISSRE 2003), 17-20 November 2003, Denver, CO, USA, pages 71–84, 2003.

Digital Library

[15]

Brian Demsky and Martin C. Rinard. Data structure repair using goal-directed reasoning. In 27th International Conference on Software Engineering (ICSE 2005), 15-21 May 2005, St. Louis, Missouri, USA, pages 176–185, 2005.

Digital Library

[16]

DERBY-4748. Stringindexoutofboundsexception on syntax error (invalid commit). https://issues.apache.org/jira/browse/DERBY- 4748, 2010.

[17]

Robert Dyer, Hridesh Rajan, Hoan Anh Nguyen, and Tien N. Nguyen. A Large-scale Empirical Study of Java Language Feature Usage. http://lib.dr.iastate.edu/cgi/viewcontent.cgi? article=1284&context=cs_techreports.

[18]

Eclipse Bug 333066. Bug 333066 - stringindexoutofboundsexception during compilation. https://bugs.eclipse.org/bugs/ show_bug.cgi?id=333066, 2014.

[19]

Eclipse Bug 432874. Bug 432874 - stringindexoutofboundsexception after adding project to inpath. https://bugs.eclipse.org/ bugs/show_bug.cgi?id=432874, 2014.

[20]

Bassem Elkarablieh, Sarfraz Khurshid, Duy Vu, and Kathryn S. McKinley. Starc: static analysis for efficient repair of complex data. In Proceedings of the 22nd Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2007, October 21-25, 2007, Montreal, Quebec, Canada, pages 387–404, 2007.

Digital Library

[21]

Michael D. Ernst, Jeff H. Perkins, Philip J. Guo, Stephen McCamant, Carlos Pacheco, Matthew S. Tschantz, and Chen Xiao. The daikon system for dynamic detection of likely invariants. Sci. Comput. Program., 69(1-3):35–45, 2007.

Digital Library

[22]

Claire Le Goues, Michael Dewey-Vogt, Stephanie Forrest, and Westley Weimer. A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each. In 34th International Conference on Software Engineering, ICSE 2012, June 2-9, 2012, Zurich, Switzerland, pages 3–13, 2012.

Digital Library

[23]

Claire Le Goues, ThanhVu Nguyen, Stephanie Forrest, and Westley Weimer. Genprog: A generic method for automatic software repair. IEEE Trans. Software Eng., 38(1):54–72, 2012.

Digital Library

[24]

Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’11, pages 317–330, New York, NY, USA, 2011. ACM.

Digital Library

[25]

HAMA-212. When the index is zero, bytesutil.getrowindex will throws the indexoutofbound. https://issues.apache.org/jira/browse/HAMA- 212, 2009.

[26]

HBASE-4481. Testmergetool failed in 0.92 build 20. https://issues.apache.org/jira/browse/HBASE- 4481, 2011.

[27]

HIVE-6986. Matchpath fails with small resultexprstring. https://issues.apache.org/jira/browse/HIVE- 6986, 2014.

[28]

HTTPCLIENT-150. Stringindexoutofbound exception in rfc2109 cookie validate when host name contains no domain information and is short in length than the cookie domain. https://issues. apache.org/jira/browse/HTTPCLIENT-150, 2003.

[29]

IO-179. Stringindexoutofbounds exception on filenameutils.getpathnoendseparator. https://issues.apache.org/jira/browse/IO-179, 2008.

[30]

JUDDI-292. <faultstring>string index out of range: 35</faultstring>. https://issues.apache.org/jira/browse/JUDDI- 292, 2011.

[31]

Kiyokuni Kawachiya, Kazunori Ogata, and Tamiya Onodera. A Quantitative Analysis of Space Waste from Java Strings and its Elimination at Garbage Collection Time. http://domino.watson.ibm.com/library/cyberdig. nsf/papers/F2BBE159220ADDF3852573990006DBF2/ $File/RT0750.pdf.

[32]

Kiyokuni Kawachiya, Kazunori Ogata, and Tamiya Onodera. Analysis and reduction of memory inefficiencies in java strings. In Proceedings of the 23rd ACM SIGPLAN Conference on Object-oriented Programming Systems Languages and Applications, OOPSLA ’08, pages 385–402, New York, NY, USA, 2008. ACM.

Digital Library

[33]

LANG-457. Numberutils createnumber thows a stringindexoutofboundsexception when only an "l" is passed in. https://issues.apache.org/jira/browse/LANG- 457, 2008.

[34]

LOG4J2-448. {log4j2-448} stringindexoutofbounds when using property substitution - asf jira. https://issues.apache.org/jira/browse/LOG4J2- 448, 2013.

[35]

Fan Long and Martin Rinard. Staged Program Repair in SPR. http://dspace.mit.edu/handle/1721.1/95963.

[36]

Fan Long, Stelios Sidiroglou-Douskos, and Martin C. Rinard. Automatic runtime error repair and containment via recovery shepherding. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’14, Edinburgh, United Kingdom - June 09 - 11, 2014, page 26, 2014.

Digital Library

[37]

MATH-198. java.lang.stringindexoutofboundsexception in complexformat.parse(string source, parseposition pos). https://issues.apache.org/jira/browse/MATH- 198, 2008.

[38]

MYFACES-416. Stringindexoutofboundsexception in addresource. https://issues.apache.org/jira/browse/MYFACES- 416, 2005.

[39]

NET-442. Stringindexoutofboundsexception: String index out of range: -1 if server respond with root is current directory. https://issues.apache.org/jira/browse/NET-442, 2012.

[40]

NUTCH-1547. Basicindexingfilter - problem to index full title. https://issues.apache.org/jira/browse/NUTCH- 1547, 2013.

[41]

OFBIZ-4237. shutdown exception if invalid string entered. https://issues.apache.org/jira/browse/OFBIZ- 4237, 2011.

[42]

PDFBOX-467. index out of bounds exception. https://issues.apache.org/jira/browse/PDFBOX- 467, 2009.

[43]

Jeff H. Perkins, Sunghun Kim, Samuel Larsen, Saman P. Amarasinghe, Jonathan Bachrach, Michael Carbin, Carlos Pacheco, Frank Sherwood, Stelios Sidiroglou, Greg Sullivan, Weng-Fai Wong, Yoav Zibin, Michael D. Ernst, and Martin C. Rinard. Automatically patching errors in deployed software. In Proceedings of the 22nd ACM Symposium on Operating Systems Principles 2009, SOSP 2009, Big Sky, Montana, USA, October 11-14, 2009, pages 87–102, 2009.

Digital Library

[44]

Hesam Samimi, Max Schäfer, Shay Artzi, Todd D. Millstein, Frank Tip, and Laurie J. Hendren. Automated repair of HTML generation errors in PHP applications using string constraint solving. In 34th International Conference on Software Engineering, ICSE 2012, June 2-9, 2012, Zurich, Switzerland, pages 277–287, 2012.

Digital Library

[45]

SDK-14417. Stringindexoutofboundsexception when using a properties-file. http://bugs.adobe.com/jira/browse/SDK- 14417, https://issues.apache.org/jira/browse/ FLEX-13823, 2008.

[46]

Rishabh Singh and Sumit Gulwani. Learning semantic string transformations from examples. Proc. VLDB Endow., 5(8):740–751, April 2012.

Digital Library

[47]

SLING-3095. Stringindexoutofboundsexception within contentxmlhandler.java:210. https://issues.apache.org/jira/browse/SLING- 3095, 2013.

[48]

SOAP-130. String indexoutofbounds in soapcontext. https://issues.apache.org/jira/browse/SOAP- 130, 2004.

[49]

SOLR-331. Stringindexoutofboundsexception when using synonyms and highlighting. https://issues.apache.org/jira/browse/SOLR- 331, 2007.

[50]

Soot. Soot: a java optimization framework. http://www.sable.mcgill.ca/soot/.

[51]

Soot-infoflow. secure-software-engineering/soot-infoflow. https://github.com/secure-softwareengineering/soot-infoflow.

[52]

StackOverflow. Stack exchange data dump : Stack exchange, inc. : Free download & streaming : Internet archive. https://archive.org/details/stackexchange, 2013.

[53]

TAP5-1770. Pagetester causes stringindexoutofboundsexception for any page request path with query parameter. https://issues.apache.org/jira/browse/TAP5- 1770, 2011.

[54]

Zachary Tatlock, Chris Tucker, David Shuffelton, Ranjit Jhala, and Sorin Lerner. Deep typechecking and refactoring. SIGPLAN Not., 43(10):37–52, October 2008.

Digital Library

[55]

VFS-338. Possible crash in extractwindowsrootprefix method. https://issues.apache.org/jira/browse/VFS-338, 2010.

[56]

Yi Wei, Yu Pei, Carlo A. Furia, Lucas S. Silva, Stefan Buchholz, Bertrand Meyer, and Andreas Zeller. Automated fixing of programs with contracts. In ISSTA 2010: Proceedings of the 19th international symposium on Software testing and analysis, pages 61–72, New York, NY, July 2010. ACM.

Digital Library

[57]

Westley Weimer, Stephanie Forrest, Claire Le Goues, and ThanhVu Nguyen. Automatic program repair with evolutionary computation. Commun. ACM, 53(5):109–116, 2010.

Digital Library

[58]

WICKET-4387. Stringindexoutofboundsexception when forwarding requests. https://issues.apache.org/jira/browse/WICKET- 4387, 2012.

[59]

WW-650. Cooluriservletdispatcher throws stringindexoutofboundsexception. https://issues.apache.org/jira/browse/WW-650, 2005.

[60]

XALANJ-836. Exception in org.apache.xalan.xsltc.compiler.util.util.tojavaname(string). https://issues.apache.org/jira/browse/XALANJ- 836, 2004.

Cited By

Kechagia MMechtaev SSarro FHarman M(2022)Evaluating Automatic Program Repair Capabilities to Repair API MisusesIEEE Transactions on Software Engineering10.1109/TSE.2021.306715648:7(2658-2679)Online publication date: 1-Jul-2022
https://doi.org/10.1109/TSE.2021.3067156
Motwani MSoto MBrun YJust RLe Goues C(2022)Quality of Automated Program Repair on Real-World DefectsIEEE Transactions on Software Engineering10.1109/TSE.2020.299878548:2(637-661)Online publication date: 1-Feb-2022
https://doi.org/10.1109/TSE.2020.2998785
Zhang JWang XZhang HSun HPu YLiu XGrundy JLe Goues CLo D(2020)Learning to handle exceptionsProceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering10.1145/3324884.3416568(29-41)Online publication date: 21-Dec-2020
https://dl.acm.org/doi/10.1145/3324884.3416568
Show More Cited By

Index Terms

CLOTHO: saving programs from malformed strings and incorrect string-handling
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

Prefix Reversals on Binary and Ternary Strings

Given a permutation $\pi$, the application of prefix reversal $f^{(i)}$ to $\pi$ reverses the order of the first $i$ elements of $\pi$. The problem of sorting by prefix reversals (also known as pancake flipping), made famous by Gates and Papadimitriou (...
A d-step approach to the maximum number of distinct squares and runs in strings

Fraenkel and Simpson conjectured in 1998 that the number of distinct squares in a string is at most its length. Kolpakov and Kucherov conjectured in 1999 that the number of runs in a string is also at most its length. Since then, both conjectures ...
Modeling and Coverage Analysis of Programs with Exception Handling
ISEC '19: Proceedings of the 12th Innovations in Software Engineering Conference (formerly known as India Software Engineering Conference)

Test coverage analysis of exception handling features is a non-trivial task, since exception handling constructs introduce implicit control flow in programs. In this paper, we present a model-based technique for coverage analysis of exception handling ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ESEC/FSE 2015: Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering

August 2015

1068 pages

ISBN:9781450336758

DOI:10.1145/2786805

General Chair:
Elisabetta Di Nitto
Politecnico di Milano, Italy
,
Program Chairs:
Mark Harman
University College London, UK
,
Patrick Heymans
University of Namur, Belgium

Copyright © 2015 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: 30 August 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ESEC/FSE'15

Sponsor:

SIGSOFT

ESEC/FSE'15: Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering

August 30 - September 4, 2015

Bergamo, Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
350
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kechagia MMechtaev SSarro FHarman M(2022)Evaluating Automatic Program Repair Capabilities to Repair API MisusesIEEE Transactions on Software Engineering10.1109/TSE.2021.306715648:7(2658-2679)Online publication date: 1-Jul-2022
https://doi.org/10.1109/TSE.2021.3067156
Motwani MSoto MBrun YJust RLe Goues C(2022)Quality of Automated Program Repair on Real-World DefectsIEEE Transactions on Software Engineering10.1109/TSE.2020.299878548:2(637-661)Online publication date: 1-Feb-2022
https://doi.org/10.1109/TSE.2020.2998785
Zhang JWang XZhang HSun HPu YLiu XGrundy JLe Goues CLo D(2020)Learning to handle exceptionsProceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering10.1145/3324884.3416568(29-41)Online publication date: 21-Dec-2020
https://dl.acm.org/doi/10.1145/3324884.3416568
Schürmann JTegeler TSteffen B(2020)Guaranteeing Type Consistency in Collective Adaptive SystemsLeveraging Applications of Formal Methods, Verification and Validation: Engineering Principles10.1007/978-3-030-61470-6_19(311-328)Online publication date: 27-Oct-2020
https://doi.org/10.1007/978-3-030-61470-6_19
Monperrus M(2018)Automatic Software RepairACM Computing Surveys10.1145/310590651:1(1-24)Online publication date: 23-Jan-2018
https://dl.acm.org/doi/10.1145/3105906
Trautsch FHerbold SMakedonski PGrabowski J(2018)Addressing problems with replicability and validity of repository mining studies through a smart data platformEmpirical Software Engineering10.1007/s10664-017-9537-x23:2(1036-1083)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s10664-017-9537-x

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