微信服务号

微信订阅号

2025年5月1日 11:16 星期四
首页 > 过刊浏览>2013年第24卷第1期 >37-49. DOI:10.3724/SP.J.1001.2013.04334
PDF HTML阅读 XML下载 导出引用 引用提醒
字符串分析研究进展
作者:
基金项目:

国家重点基础研究发展计划(973)(2009CB320703); 国家自然科学基金(60931160444, 91118004, 61225007)


Progress in Research on String Analysis
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [21]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    随着软件应用范围的不断扩大,尤其是数据库软件和Web软件的广泛应用,字符串变量在软件程序中扮演的角色日益重要.与此同时,针对字符串变量的程序分析技术——字符串分析,也取得了长足的发展,并在软件工程中的很多领域中得到了成功的应用.字符串分析的基本应用模式是首先使用字符串值分析获得字符串变量的所有可能取值,然后使用字符串约束求解判断这些变量的取值是否满足一定约束,从而对程序进行正确性验证.为了使得字符串分析能够应用在安全分析和软件维护应用中,研究人员对字符串分析进行了扩展,进一步分析字符串变量的数据来源.综述了字符串分析技术的研究进展,提出了字符串分析的问题构型,介绍了这一领域现在的主要研究内容:字符串值分析、字符串约束求解、字符串数据来源分析以及字符串分析在软件工程中的应用.

    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.

    参考文献
    [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
    引证文献
引用本文

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

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2012-06-29
  • 最后修改日期:2012-10-16
  • 在线发布日期: 2012-12-29
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号