在這篇論文中我們利用程式碼補強達到使有害的攻擊字串用最小的編輯成本去修正成無害的一般字串,主要分為兩個階段,第一階段,我們利用一個安全性分析工具Stranger來分析使用者的PHP原始碼,藉此找到可能被程式碼注入的攻擊點,並產生基於確定有限狀態自動機基礎的安全特徵,這個安全特徵包含了所有可被接受的無害字串可以當作攻擊過濾器使用,第二階段,我們採取基於文字與自動機之間最短編輯距離的演算法來以最少成本修正攻擊字串,有害的攻擊字串會被一個最少變動的無害字串所取代,我們結合所提出的方法來測試一些網頁跟回報實驗結果

The security problems of web application are always questioned and
concerned by users because that can cause huge loss of nancial and
privacy. We want to provide a online service that is open to public
users, who can access and upload their codes to check for potential vulnerabilities.
Moreover, if there exist vulnerabilities and may be cause
damages, it will guide users how they can edit their codes through a
easy way step by step.
In this paper, we propose an optimal word correction approach for
patching string related vulnerabilities in web applications. To be brief,
we synthesize patches that sanitize malicious inputs to normal ones
with the shortest edit distance. The analysis consists of two phases:
First, we use automata based static string analysis techniques called
Stranger to detect vulnerabilities in web applications, and generate
sanitization signatures that accept un-malicious inputs as an input
lter that ensures the vulnerabilities are not exploited with respect
to given attack patterns. Second, we adopt the shortest edit-distance
algorithms between words and automata to nd a minimum way on
the cost of edit distance to patch malicious inputs. A malicious input
(not accepted by the sanitization signature) is replaced with an unmalicious
string and has the minimum change of character from the
original input. We integrate the presented approach with Stranger
and report the result of experiments on various web applications.

List of Figures v
List of Tables vii
1 Introduction 1
1.1 Background and Motivation . . . . . . . . . . . . . . . . . . . . . 1
1.2 Patching Vulnerabilities Online . . . . . . . . . . . . . . . . . . . 2
1.3 Word Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Content Organization . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Related Work 4
2.1 String Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Word Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Patch Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Overview 9
3.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.1.1 Vulnerability Analysis and Sanitization Generation . . . . 10
3.1.2 Sanitization Patching . . . . . . . . . . . . . . . . . . . . . 11
3.2 A multi-track example . . . . . . . . . . . . . . . . . . . . . . . . 12
4 Algorithm 15
4.1 Automata composition . . . . . . . . . . . . . . . . . . . . . . . . 16
4.1.1 Extension to Multi-track . . . . . . . . . . . . . . . . . . . 20
4.2 Character composition . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2.1 Extension to Multi-track . . . . . . . . . . . . . . . . . . . 27
iii
CONTENTS
4.2.2 Pre-Computation of Shortest Distance . . . . . . . . . . . 31
5 Experiment 33
5.1 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.2 Correction Eect . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.3 Attack Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6 Conclusions 41
References 42

[1] Cyril Allauzen and Mehryar Mohri. Linear-Space Computation of the Edit-Distance be-
tween a String and a Finite Automaton. CoRR, abs/0904.4686,2009. 6, 15, 17, 23
[2] Aske Simon Christensen, Anders Mller, and Michael I.
Schwartzbach. Precise Analysis of String Expressions. In SAS,pages 1{18, 2003. 4
[3] Manuel Costa, Miguel Castro,Lidong Zhou, Lintao Zhang,and Marcus Peinado. Bouncer:securing software by blocking bad input. In SOSP, pages 117{130, 2007. 6
[4] Silviu Cucerzan and Eric Brill. Spelling Correction as an
Iterative Process that Exploits the Collective Knowledge of Web Users. In Dekang Lin and Dekai Wu, editors, Proceedings of EMNLP 2004, pages 293{300, Barcelona, Spain, July 2004. Association for Computational Linguistics.
[5] Adam Doupe, Weidong Cui, Mariusz H. Jakubowski, Marcus Peinado, Christopher Kruegel, and Giovanni Vigna. deDacota: toward preventing server-side XSS via automatic code and data separation. In Proceedings of the 2013 ACM SIGSAC conference on Computer &; communications security, CCS '13, pages 1205{1216, New
York, NY, USA, 2013. ACM. Available from: http://doi.acm.org/10.1145/2508859.2516708. 7
[6] Xiang Fu, Xin Lu, Boris Peltsverger, Shijun Chen,
Kai Qian, and Lixin Tao. A Static Analysis Framework
For Detecting SQL Injection Vulnerabilities. In COMPSAC,
pages 87{96, 2007. 4
[7] Carl Gould, Zhendong Su, and Premkumar Devanbu. Static Checking of Dynamically Generated Queries in Database Applications. In ICSE, pages 645{654, 2004. 4
[8] Timothy L. Hinrichs, Daniele Rossetti, Gabriele REFERENCES Petronella, V. N. Venkatakrishnan, A. Prasad Sistla, and Lenore D. Zuck. WEBLOG: A Declarative Language for Secure Web Development. In Proceedings of the Eighth ACM SIGPLAN Workshop on Programming Languages and Analysis for Security, PLAS '13, pages 59{70, New York, NY, USA, 2013. ACM. Available from: http://doi.acm.org/10.1145/2465106.2465119. 8
[9] Rangasami L. Kashyap and B. John Oommen. An eective algorithm for string correction using generalized edit distance - II. Computational complexity of the algorithm and some applications. Inf. Sci., 23(3):201{217,
1981. 5
[10] Adam Kiezun, Vijay Ganesh, Philip J. Guo, Pieter Hooimeijer, and Michael D. Ernst. HAMPI: a solver for string constraints. In ISSTA, pages 105{116,
2009. 4
[11] Benjamin Livshits and Stephen Chong. Towards fully automatic placement of security sanitizers and declassiers. In Proceedings of the 40th annual ACM SIGPLANSIGACT symposium on Principles of programming languages, POPL '13, pages 385{398, 2013. 7
[12] Yasuhiko Minamide. Static Approximation of Dynamically Generated Web Pages. In WWW, pages 432{441, 2005. 4
[13] Kemal Oflazer. Error-tolerant finite-state recognition with applications to morphological analysis and spelling correction. Comput. Linguist., 22(1):73{89, March 1996. 5
[14] Mike Samuel, Prateek Saxena, and Dawn Song. Context-sensitive auto-sanitization in web templating languages using type qualiers. In Proceedings of
the 18th ACM conference on Computer and communications security, CCS '11, pages 587{600, 2011. 7
[15] Prateek Saxena, David Molnar, and Benjamin Livshits.
SCRIPTGARD: automatic context-sensitive sanitization
for large-scale legacy web applications. In CCS, pages 601{614,2011. 6
[16] Daryl Shannon, Sukant Hajra, Alison Lee, Daiqian Zhan, and Sarfraz Khurshid. Abstracting Symbolic Execution with String Analysis. In TAICPART-MUTATION, pages 13{22, 2007. 4
[17] Zhendong Su and Gary Wassermann. The essence of command REFERENCES injection attacks in web applications. In Proceedings of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, POPL '06, pages 372{382, New York, NY,
USA, 2006. ACM. Available from: http://doi.acm.org/10.1145/
1111037.1111070. 6
[18] Robert A. Wagner. Order-n correction for regular
languages. Commun. ACM,17(5):265{268, May 1974. 5
[19] Gary Wassermann and Zhen-dong Su. Sound and precise analysis of web applications for injection vulnerabilities. In PLDI, pages 32{41, 2007. 4
[20] Gary Wassermann and Zhen-dong Su. Static detection of cross-site scripting vulnerabilities. In ICSE, pages 171{180, 2008.4
[21] Fang Yu, Muath Alkhalaf, and Tevfik Bultan. Generating Vulnerability Signatures for String
Manipulating Programs Using Automata-based Forward and Backward Symbolic Analyses. In ASE, pages 605{609, 2009. 4
[22] Fang Yu, Muath Alkhalaf, and Tevfik Bultan. Stranger: An Automata-based String Analysis Tool for PHP. In TACAS, pages 154{157, 2010. 4, 10
[23] Fang Yu, Muath Alkhalaf, and Tevfik Bultan. Patching
vulnerabilities with sanitization synthesis. In ICSE, pages 251{260, 2011. 4
[24] Fang Yu, Tevfik Bultan, Marco Cova, and Oscar H.
Ibarra. Symbolic String Verification: An Automata-Based
Approach. In SPIN, pages 306{324, 2008. 4
[25] Fang Yu, Tevfik Bultan, and Oscar H. Ibarra. Relational
String Verication Using Multi-Track Automata. In CIAA, pages 290{299, 2010. 4