Abstract Parsing: Static analysis of dynamically generated string output

点击翻译按钮获取中文摘要

This project provides an automated, formal-methods-based methodology and toolthat analyzes and validates, in advance of its execution,PHP, Perl, or Javascript programs that dynamically generateHMTL, XML, and SQL documents.Such document-generator programs are common to the World Wide Web and arenotorious for generating ill-structured, faulty, and dangerousdocuments that cause subsequent server errors or security breaches.The methodology integrates techniques fromLR(k)-parsing, data-flow analysis, and program securityto synthesize the program-analysis.Given the program (e.g., a PHP script) that generates documents and given thecontext-free reference grammar for the document language(e.g., a grammar for HTML),the analysis tool generates an LR(k) parser for the reference grammarand applies a data-flow analysis to analyze the program andpredict the context-free grammatical structure of thedocuments to be generated by the program.The tool computes abstract parse stacks, a novel and innovative structurethat encodes a generated document's context-free structure.Next, the tool applies formal semantics techniques to compute froman abstract parse stack its context-sensitive semantics, that is, themeaning of the dynamically generated document.Dynamically generated documents are often assembledwith user-supplied input, which can be erroneous or malicious.The analysis annotates the abstract parse stacks to identitywhere user input might appear,and the semantic analysis tracks the influenceof the user input upon the document's meaning.