有限状态自动机在概率符号执行中的字符串约束建模有效性研究

有限状态自动机在概率符号执行中的应用是计算机科学硕士论文的重要研究方向，特别是在处理字符串约束时。论文标题《有限状态自动机在概率符号执行中对字符串约束进行建模的适用性》探讨了在概率符号执行（PSE）这一动态程序分析技术中，如何有效地利用自动机来表示和计算复杂数据类型如字符串的约束概率。 PSE相较于传统的符号执行（SE），增加了对程序路径概率的计算，这要求符号模型不仅要准确表达程序行为，还要适应字符串数据。以往的SE工具常使用有限状态自动机作为符号字符串模型的基础，以捕获字符串操作的动态特性。然而，对于如何在PSE的背景下优化和评估这些基于自动机的符号字符串模型，目前的研究尚存在空白。 作者Andrew Harris在本论文中提出了四种不同的基于有限状态自动机的PSE符号字符串模型，着重分析了它们在准确性（即模型计算出的概率与实际概率的匹配程度）和性能（包括计算时间）方面的表现。通过对两个标准软件程序的分析，结果揭示了模型间的差异：没有一种模型能够始终如一地精确计算，而是受软件程序特定特性的显著影响。 论文的核心工作包括模型的设计、实施实验、比较不同模型的表现，并且深入探讨了影响模型适用性的因素。这些发现对于理解如何优化PSE以处理字符串约束具有理论价值和实践指导意义，尤其是在开发更为精确且高效的自动机模型方面。 论文提交者Andrew Harris完成了硕士学位论文的撰写，并在2019年8月提交给Boise State University，得到了包括Elena Sherman博士在内的评审委员会的高度评价。他们的最终口头考试结果显示，论文达到了硕士毕业的要求，证明了有限状态自动机在概率符号执行中对字符串约束建模的潜在价值。 这篇论文为理解和改进PSE中的字符串处理策略提供了新的视角，展示了有限状态自动机在这一领域的潜在应用前景。对于那些关注程序分析、动态语义或复杂数据类型处理的读者来说，这是一个深入了解和扩展现有方法的重要参考文献。