Paper Info
Title
Tainted flow analysis on e-SSA-form programs
Abstract
Tainted flow attacks originate from program inputs maliciously crafted to exploit software vulnerabilities. These attacks are common in server-side scripting languages, such as PHP. In 1997, ørbæk and Palsberg formalized the problem of detecting these exploits as an instance of type-checking, and gave an O(V3) algorithm to solve it, where V is the number of program variables. A similar algorithm was, ten years later, implemented on the Pixy tool. In this paper we give an O(V2) solution to the same problem. Our solution uses Bodik et al.'s extended Static Single Assignment (e-SSA) program representation. The e-SSA form can be efficiently computed and it enables us to solve the problem via a sparse data-flow analysis. Using the same infrastructure, we compared a state-of-the-art data-flow solution with our technique. Both approaches have detected 36 vulnerabilities in well known PHP programs. Our results show that our approach tends to outperform the data-flow algorithm for bigger inputs. We have reported the bugs that we found, and an implementation of our algorithm is now publicly available.
Year
DOI
Venue
2011
10.1007/978-3-642-19861-8_8
CC
Keywords
Field
DocType
e-ssa form,state-of-the-art data-flow solution,program representation,similar algorithm,pixy tool,program input,sparse data-flow analysis,program variable,e-ssa-form program,data-flow algorithm,tainted flow analysis,php program,sparse data,static single assignment,scripting language,flow analysis,data flow
Programming language,Computer science,Exploit,Theoretical computer science,Software,Symbolic execution,Static single assignment form,Scripting language
Conference
Volume
ISSN
Citations 
6601
0302-9743
4
PageRank 
References 
Authors
0.43
19
3
Name
Order
Citations
PageRank
Andrei Rimsa1131.98
Marcelo d'Amorim245329.07
Fernando Magno Quintão Pereira321620.03