Abstract Parsing: Static analysis of dynamically generated string output

摘要解析：动态生成字符串输出的静态分析

基本信息

批准号：
0939431
负责人：
David Schmidt
金额：
$ 29.93万
依托单位：
Kansas State University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2009
资助国家：
美国
起止时间：
2009-08-01 至 2012-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=0939431&HistoricalAwards=false
关键词：
Abstract Parsing Static analysis dynamically

项目摘要

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.

该项目提供了一种自动化的、基于形式方法的方法和工具，可以在执行之前分析和验证动态生成 HMTL、XML 和 SQL 文档的 PHP、Perl 或 Javascript 程序。此类文档生成器程序对于万维网因生成结构不良、错误且危险的文档而臭名昭著，这些文档会导致随后的服务器错误或安全漏洞。该方法集成了 LR(k) 解析、数据流分析和程序安全性技术综合程序分析。给定生成文档的程序（例如，PHP 脚本）并给定文档语言的上下文无关参考语法（例如，HTML 语法），分析工具生成 LR(k) 解析器参考语法并应用数据流分析来分析程序并预测程序生成的文档的上下文无关语法结构。该工具计算抽象解析堆栈，这是一种新颖且创新的结构，可编码生成的文档的上下文无关结构。接下来，该工具应用形式语义技术从抽象解析堆栈计算其上下文相关语义，即动态生成的文档的含义。动态生成的文档通常与用户提供的输入组装在一起，这分析可以对抽象解析堆栈进行注释，以识别用户输入可能出现的位置，并且语义分析可以跟踪用户输入对文档含义的影响。