? Automated String Constraints Solving for Programs Containing String Manipulation Functions
Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | FAQ
 
Indexed by   SCIE, EI ...
Bimonthly    Since 1986
Journal of Computer Science and Technology 2017, Vol. 32 Issue (6) :1125-1135    DOI: 10.1007/s11390-017-1787-y
Special Section on Software Systems 2017 Current Issue | Archive | Adv Search << Previous Articles | Next Articles >>
Automated String Constraints Solving for Programs Containing String Manipulation Functions
Xu-Zhou Zhang1, Yun-Zhan Gong1, Member, CCF, Ya-Wen Wang1, Member, CCF, Ying Xing2, Member, CCF, Ming-Zhe Zhang1
1 State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications Beijing 100876, China;
2 Automation School, Beijing University of Posts and Telecommunications, Beijing 100876, China

Abstract
Reference
Related Articles
Download: [PDF 819KB]     Export: BibTeX or EndNote (RIS)  
Abstract The ability to solve various constraints is a principal factor of automatic constraint solvers. Most object-oriented languages treat a character string as a primitive data type which is manipulated by string library functions. Most constraint solvers have limitations on their input constraints, such as strong restrictions on the expressiveness of constraints or lack of the ability to solve hybrid constraints. These limitations hinder applying automated constraint solvers on program analysis techniques for programs containing strings and string manipulation functions. We propose an approach to automatically solve program constraints involving strings and string manipulation functions. Based on the character array model, we design a constraint language which contains primitive operations to precisely describe the constraints of commonly used string manipulation functions. The translated string constraints together with numeric constraints are then solved by a twophase test generation procedure:firstly, a partial solution is obtained to satisfy the arithmetic constraints of the position variables, and the solution is utilized to simplify the string constraints into pure character array constraints; secondly, the pure array constraints are solved by an off-the-shelf array-specific theory based constraint solver. We integrate the approach into an automated testing tool to support the generation of string test cases, and then perform experiments. The results of the experiments prove that the integration of the proposed approach promotes the testing coverage of the existing testing tool, and the integrated tool has an advantage of handling specific string manipulation functions compared with an existing string solver.
Articles by authors
Keywordsstring constraints solving   satisfaction module theory   program analysis   software testing   automated test input generation     
Received 2017-04-27;
Fund:

This work was partially supported by the National Natural Science Foundation of China under Grant Nos. 61202080, 61702044, and 61502029.

Corresponding Authors: 10.1007/s11390-017-1787-y   
About author: Xu-Zhou Zhang received his B.S.degree in computer science and technology from Huazhong University of Science and Technology,Wuhan,in 2010.He is currently a Ph.D.candidate in the State Key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications,Beijing.His research interest is program analysis and software testing.
Cite this article:   
Xu-Zhou Zhang, Yun-Zhan Gong, Ya-Wen Wang, Ying Xing, Ming-Zhe Zhang.Automated String Constraints Solving for Programs Containing String Manipulation Functions[J]  Journal of Computer Science and Technology, 2017,V32(6): 1125-1135
URL:  
http://jcst.ict.ac.cn:8080/jcst/EN/10.1007/s11390-017-1787-y
Copyright 2010 by Journal of Computer Science and Technology