数据流分析和抽象解释有什么区别？它们是否用于相同的目的？相对于彼此，这两者的优缺点是什么。
数据流分析与抽象解释的区别是什么？
17
- MetallicPriest
3个回答
17
简而言之，它们属于不同的类别。这就像比较衣服和裤子。
抽象解释是一种框架，用抽象域和抽象传递函数来形式化固定点计算。如果满足某些条件，则抽象解释保证可以在有限步骤内找到固定点（详见：http://www.di.ens.fr/~cousot/COUSOTpapers/POPL77.shtml）。抽象解释的伟大之处在于widening和narrowing。由于它们的存在，抽象解释可以在无限域上计算出固定点。
个人认为，数据流分析只是抽象解释的一个实例。由于数据流分析使用的大多数具体域都是有限的，因此甚至不需要进行widening和narrowing。
- ihji
1
3我曾经从事过抽象解释器的工作，我认为这是一个很好的总结。 - Pascal Cuoq
2
我不确定这里的任何答案都真正回答了原始问题的意图，原始问题似乎是在寻求一个直观而非技术性的解释。数据流分析关注于获取给定位置某些信息的值。"信息"的例子包括哪些定义到达了给定位置，哪些变量在给定位置是活跃的，哪些表达式在给定位置是常量等。数据流框架通常要求值域形成有限格，传递函数是单调的（传递函数决定了信息如何从块的入口传播到出口），所有这些旨在能够计算数据流值的定点。它被用于编译器。
抽象解释（AI）则旨在构建语言的抽象解释器。目标是以抽象的方式确定“这段代码计算了什么？让我们尝试用抽象的方式回答这个问题”。例如，如果计算返回某个索引变量i的值，AI可以计算出i的范围，以便回答是否会有边界违规等问题。因此，抽象值的域略有不同，可能是一个范围域、一个多面体域等。由于所使用的域不需要是有限的，因此AI与数据流存在不同的约束：具体和抽象域通常需要通过称为Galois连接的东西相互关联，该连接将具体值集合与抽象值集合相关联。由于所使用的域不需要是有限的，因此AI在没有干预（以宽化/缩小操作的形式）的情况下不总是收敛。AI被用于形式验证工具。它们共同之处只是希望函数迭代收敛。因此，如果您想知道某个位置的某些内容的值，请使用数据流分析；如果您想知道程序在抽象意义上计算了什么，请使用AI。
数据流和AI可以一起使用。例如，反汇编工具Jakstab结合了两者——数据流用于确定间接跳转目标的值（即新计算的将要加载的PC的值），而AI用于抽象地评估二进制代码片段。
抽象解释（AI）则旨在构建语言的抽象解释器。目标是以抽象的方式确定“这段代码计算了什么？让我们尝试用抽象的方式回答这个问题”。例如，如果计算返回某个索引变量i的值，AI可以计算出i的范围，以便回答是否会有边界违规等问题。因此，抽象值的域略有不同，可能是一个范围域、一个多面体域等。由于所使用的域不需要是有限的，因此AI与数据流存在不同的约束：具体和抽象域通常需要通过称为Galois连接的东西相互关联，该连接将具体值集合与抽象值集合相关联。由于所使用的域不需要是有限的，因此AI在没有干预（以宽化/缩小操作的形式）的情况下不总是收敛。AI被用于形式验证工具。它们共同之处只是希望函数迭代收敛。因此，如果您想知道某个位置的某些内容的值，请使用数据流分析；如果您想知道程序在抽象意义上计算了什么，请使用AI。
数据流和AI可以一起使用。例如，反汇编工具Jakstab结合了两者——数据流用于确定间接跳转目标的值（即新计算的将要加载的PC的值），而AI用于抽象地评估二进制代码片段。
- Motorhead
0
问题在于“效率与准确性之间的平衡”。
数据流分析试图比抽象解释更多地合并路径数据。抽象解释遍历所有路径，保持数据值抽象。
- Michael Donohue
1
5这个答案是错误的。路径敏感性与抽象解释和数据流分析之间的区别无关。 - ihji
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接