SHF: Small: S3: Statistical and Structural Analysis for Spreadsheets

电子表格是世界上最常用的编程环境；仅Microsoft Excel就有超过7.5亿用户。电子表格广泛用于政府、科学和金融环境；超过95%的美国公司使用电子表格进行财务报告，85%的公司使用电子表格进行预算和预测。不幸的是，错误是电子表格的通病；最近的一项研究发现，错误率超过95%。电子表格错误造成了灾难性的后果，导致了数十亿美元的损失。该项目使用专门为电子表格设计的自动分析技术，以(A)自动检测并帮助防止电子表格中的错误，显著提高其计算的可靠性，(B)降低严重错误的风险，以及(C)潜在地为经济节省数百万美元(如果不是数十亿美元的话)。电子表格具有独特的功能，使它们不同于标准编程语言，因此需要利用它们的特点进行新的程序分析。S3对电子表格公式的空间和深层结构进行统计分析，以识别高度异常并因此可能出错的电子表格单元格。S3通过一种结合了空间和结构信息(包括依赖模式)的新型向量表示，将查找数据和公式错误的问题简化为查找异常结构的问题。然后，通过对这些向量进行统计分析，可以确定在任何维度上都非常不寻常的公式，因此很可能是错误的。S3既在单个电子表格级别运行，又结合了从大量现有电子表格中学习到的电子表格使用模型，以调整分析条件并进一步降低误检率。

Spreadsheets are the most commonly used programming environment in the world; there are more than 750 million users of Microsoft Excel alone. Spreadsheets are widely used in government, scientific, and financial settings; over 95% of US firms use them for financial reporting and 85% use them for budgeting and forecasting. Unfortunately, errors are endemic to spreadsheets; a recent study found an error rate of over 95%. Spreadsheet errors have had catastrophic consequences, leading to losses of billions of dollars. This project uses automatic analysis techniques designed specifically for spreadsheets to (a) automatically detect and help prevent errors in spreadsheets, dramatically increasing the reliability of their calculations, (b) reduce the risks of serious mistakes, and (c) potentially save the economy millions if not billions of dollars.This project develops statistical and structural analyses for spreadsheets (S3). Spreadsheets have unique features that make them different from standard programming languages, and thus demand new program analyses that exploit their characteristics. S3 employs statistical analyses over the spatial and deep structure of spreadsheet formulas to identify spreadsheet cells that are highly anomalous and thus likely to be wrong. S3 reduces the problem of finding data and formula errors to that of finding anomalous structures via a novel vector representation that combines spatial and structural information (including patterns of dependencies). Applying statistical analyses across these vectors can then identify formulas that are highly unusual in any dimension, and thus likely to be wrong. S3 operates both at an individual spreadsheet level and also incorporates learned models of spreadsheet usage from large bodies of existing spreadsheets to condition the analysis and further reduce false positive rates.