1. NCCU Academic Hub
  2. Publications
  3. College of Commerce
  4. Theses
  5. Item

Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 網頁弱點最佳化補強
Patching web application vulnerabilities with optimal word correction algorithm
作者 薛慶源
Shueh, Ching Yuan
貢獻者 郁方
Yu, Fang
薛慶源
Shueh, Ching Yuan
關鍵詞 網路安全
弱點補強
文字修正
文字分析
Web Security
Patch Synthesis
Word Correction
Word Analysis
日期 2013
上傳時間 6-Aug-2014 17:29:21 (UTC+8)
摘要 在這篇論文中我們利用程式碼補強達到使有害的攻擊字串用最小的編輯成本去修正成無害的一般字串,主要分為兩個階段,第一階段,我們利用一個安全性分析工具Stranger來分析使用者的PHP原始碼,藉此找到可能被程式碼注入的攻擊點,並產生基於確定有限狀態自動機基礎的安全特徵,這個安全特徵包含了所有可被接受的無害字串可以當作攻擊過濾器使用,第二階段,我們採取基於文字與自動機之間最短編輯距離的演算法來以最少成本修正攻擊字串,有害的攻擊字串會被一個最少變動的無害字串所取代,我們結合所提出的方法來測試一些網頁跟回報實驗結果
The security problems of web application are always questioned and
concerned by users because that can cause huge loss of financial 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
filter 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 find 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.
參考文獻 [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 Moller, 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 effective 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 declassifiers. 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 Verification Using Multi-Track Automata. In CIAA, pages 290{299, 2010. 4
描述 碩士
國立政治大學
資訊管理研究所
101356020
102
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0101356020
資料類型 thesis
dc.contributor.advisor 郁方zh_TW
dc.contributor.advisor Yu, Fangen_US
dc.contributor.author (Authors) 薛慶源zh_TW
dc.contributor.author (Authors) Shueh, Ching Yuanen_US
dc.creator (作者) 薛慶源zh_TW
dc.creator (作者) Shueh, Ching Yuanen_US
dc.date (日期) 2013en_US
dc.date.accessioned 6-Aug-2014 17:29:21 (UTC+8)-
dc.date.available 6-Aug-2014 17:29:21 (UTC+8)-
dc.date.issued (上傳時間) 6-Aug-2014 17:29:21 (UTC+8)-
dc.identifier (Other Identifiers) G0101356020en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/68380-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊管理研究所zh_TW
dc.description (描述) 101356020zh_TW
dc.description (描述) 102zh_TW
dc.description.abstract (摘要) 在這篇論文中我們利用程式碼補強達到使有害的攻擊字串用最小的編輯成本去修正成無害的一般字串,主要分為兩個階段,第一階段,我們利用一個安全性分析工具Stranger來分析使用者的PHP原始碼,藉此找到可能被程式碼注入的攻擊點,並產生基於確定有限狀態自動機基礎的安全特徵,這個安全特徵包含了所有可被接受的無害字串可以當作攻擊過濾器使用,第二階段,我們採取基於文字與自動機之間最短編輯距離的演算法來以最少成本修正攻擊字串,有害的攻擊字串會被一個最少變動的無害字串所取代,我們結合所提出的方法來測試一些網頁跟回報實驗結果zh_TW
dc.description.abstract (摘要) The security problems of web application are always questioned and
concerned by users because that can cause huge loss of financial 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
filter 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 find 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.		en_US
dc.description.tableofcontents 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 Effect . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.3 Attack Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6 Conclusions 41
References 42		zh_TW
dc.format.extent 3428229 bytes-
dc.format.mimetype application/pdf-
dc.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0101356020en_US
dc.subject (關鍵詞) 網路安全zh_TW
dc.subject (關鍵詞) 弱點補強zh_TW
dc.subject (關鍵詞) 文字修正zh_TW
dc.subject (關鍵詞) 文字分析zh_TW
dc.subject (關鍵詞) Web Securityen_US
dc.subject (關鍵詞) Patch Synthesisen_US
dc.subject (關鍵詞) Word Correctionen_US
dc.subject (關鍵詞) Word Analysisen_US
dc.title (題名) 網頁弱點最佳化補強zh_TW
dc.title (題名) Patching web application vulnerabilities with optimal word correction algorithmen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [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 Moller, 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 effective 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 declassifiers. 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 Verification Using Multi-Track Automata. In CIAA, pages 290{299, 2010. 4		zh_TW