微信服务号

微信订阅号

2025-4-21- 20
Home > Archive>Volume 24, Issue 1, 2013 >37-49. DOI:10.3724/SP.J.1001.2013.04334
PDF HTML XML Export Cite reminder
Progress in Research on String Analysis
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [21]
    • |
  • Related
    • |
  • Cited by [1]
    • | |
  • Comments
    Abstract:

    With the ubiquitous software application, especially the wide usage of database applications and Web applications, strings have become a more important role in the software programs. At the same time, the program analysis techniques that consider the specialty of strings have been developed, and have been applied to various areas in software engineering. Usually, string value analysis is applied to acquire the possible values of a given string variable. Next, a constraint solver is applied to check whether the values satisfy predefined specifications, so that the correctness of the given string variable can be checked. To further apply string analysis to some security analysis and software maintenance problems, the string analysis is further improved to analyze the possible data origins of a given string variable. This paper presents a survey on string analysis, which mainly introduces the string value analysis, string constraint solving, string data origin analysis, and the applications of string analysis in software engineering.

    Reference
    [1] Ratschiller T, Gerken T. Web Application Development with PHP 4.0. Vancouver: Sams Publishing, 2000. 1-416.
    [2] Stiefel M, Oberg R. Application Development Using C# and .NET. Prentice Hall Professional, 2001. 1-623.
    [3] Tymann P, Schneider GM. Modern Software Development Using Java. 2nd ed., Stamford: Course Technology, 2007. 1-960.
    [4] Welling L, Thomson L. PHP and MySQL Web Development. 4th ed., Boston: Addison-Wesley, 2008. 1-1008.
    [5] Moser A, Kruegel C, Kirda E. Limits of static analysis for malware detection. In: Samarati P, Payne C, eds. Proc. of the 23rd Annual Computing Security Applications Conf. Washington: IEEE Computer Society Press, 2007. 421-430. [doi: 10.1109/ACSAC. 2007.21]
    [6] Cousot P. Abstract interpretation. ACM Computing Surveys, 1996,28(2):324-328. [doi: 10.1145/234528.234740]
    [7] Christensen A, Moller A, Schwartzbach M. Precise analysis of string expressions. In: Cousot R, ed. Proc. of the Static Analysis Symp. Heidelberg: Springer-Verlag, 2003. 1-18.
    [8] Gould C, Su Z, Devanbu P. Static checking of dynamically generated queries in database applications. In: Estublier J, Rosenblum D, eds. Proc. of the Int''l Conf. on Software Engineering. Washington: IEEE Computer Society Press, 2004. 645-654. [doi: 10.1145/ 1276933.1276935]
    [9] Maule A, Emmerich W, Rosenblum DS. Impact analysis of database schema changes. In: Schafer W, Dwyer M, Gruhn V, eds. Proc. of the 30th Int''l Conf. on Software Engineering. New York: ACM Press, 2008. 451-460. [doi: 10.1145/1368088.1368150]
    [10] Wassermann G, Su Z. Sound and precise analysis of Web applications for injection vulnerabilities. In: Ferrante J, McKinley K, eds. Proc. of the ACM SIGPLAN Conf. on Programming Languages Design and Implementation. New York: ACM Press, 2007. 32-41. [doi: 10.1145/1273442.1250739]
    [11] Cytron R, Ferrante J, Rosen B, Wegman M, Zadek K. Efficiently computing static single assignment form and the control dependence graph. ACM Trans. on Programming Languages and Systems, 1991,13(4):451-490. [doi: 10.1145/115372.115320]
    [12] Mohri M, Nederhof M. Robustness in Language and Speech Technology. Dordrecht: Kluwen Academic Publishers, 2001. 1-268.
    [13] Yu F, Bultan T, Cova M, Ibarra O. Symbolic string verification: An automata-based approach. In: Havelund K, Majumdar R, Palsberg J, eds. Proc. of the 15th Int''l Workshop on Model Checking Software. Heidelberg: Springer-Verlag, 2008. 306-324. [doi: 10.1007/978-3-540-85114-1_21]
    [14] Yu F, Alkhalaf M, Bultan T. Stranger: An automata-based string analysis tool for PHP. In: Esparza J, Majumdar R, eds. Proc. of the 16th Int''l Conf. on Tools and Algorithms for the Construction and Analysis of Systems. Heidelberg: Springer-Verlag, 2010. 154-157. [doi: 10.1007/978-3-642-12002-2_13]
    [15] Minamide Y. Static approximation of dynamically generated Web pages. In: Ellis A, Hagino T, eds. Proc. of the 14th Int''l Conf. on World Wide Web. New York: ACM Press, 2005. 432-441. [doi: 10.1145/1060745.1060809]
    [16] Berstel J. Transductions and Context-Free Languages. Stuttgart: Teubner Studienbucher, 1979. 1-278.
    [17] Hopcroft J, Motwani R, Ullman J. Introduction to Automata Theory, Languages, and Computation. 3rd ed., Prentice Hall, 2006. 1-750.
    [18] Tateishi T, Pistoia M, Tripp O. Path- and index-sensitive string analysis based on monadic second-order logic. In: Dwyer M, Tip F, eds. Proc. of the Int''l Symp. on Software Testing and Analysis. New York: ACM Press, 2011. 166-176. [doi: 10.1145/2001420. 2001441]
    [19] Muller D, Schupp P. The theory of ends, pushdown automata, and second-order logic. Theoretical Computer Science, 1985,37(1): 51-75. [doi: 10.1016/0304-3975(85)90087-8]
    [20] Bolliq B. Formal Models of Communicating Systems: Languages, Automata, and Monadic Second-Order Logic. Heidelberg: Springer-Verlag, 2010. 1-182.
    [21] Klarlund N. Mona
    Related
    Comments
    Comments
    分享到微博
    Submit
Get Citation

梅宏,王啸吟,张路.字符串分析研究进展.软件学报,2013,24(1):37-49

Copy
Share
Article Metrics
  • Abstract:8918
  • PDF: 11197
  • HTML: 0
  • Cited by: 0
History
  • Received:June 29,2012
  • Revised:October 16,2012
  • Online: December 29,2012
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2036773Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063