2Centro de Informática – UFPE

Abstract. Tainted variable attacks, common in server-side scripting languages, such as PHP, originate from program inputs maliciously crafted to exploit soft-ware vulnerabilities. These vulnerabilities can be detected via data-flow analy-ses, which iteratively compute the abstract state (“tainted ” or “clean”) associ-ated to every program variable at each program point. Existing algorithms for this problem have a worst-case cubic time on the number of program variables – an issue for large programs. This paper presents a quadratic-time algorithm to tackle the tainted flow problem. We have implemented our analysis on top of phc, an open source PHP compiler, and have scanned over 13 thousand PHP files, obtaining 130 warnings, out of which 41 are actual security vulnerabilities. 1