使用带 Z3 的 SMT 约束时获取合法范围信息的（次）最佳方法
(Sub)optimal way to get a legit range info when using a SMT constraint with Z3
这个问题与我之前的问题有关
所以看起来 "efficiently" 找到最大范围信息是不合适的，给定典型的 32 位向量等等。但另一方面，我在考虑是否可以找到某些 "sub-maximum" 范围信息，希望这会变得更有效率。另一件事是我们可能希望有一定的 "safe" 保证，比如对于次最大范围内的所有元素，它们必须满足约束，但可能存在其他一些也满足约束的解决方案。
我目前正在探索 model counting 技术在这种情况下是否有意义。任何想法将不胜感激。谢谢。
一般情况
这不仅仅是效率的问题。考虑一个问题，您有两个变量 a 和 b，以及一个约束：
a != b
b的范围是多少？ （最大还是其他？）
你可以说所有的值都是合法的。但那是错误的，因为 a 的选择显然会影响 b 的选择。你周围的变量越多，问题就会变得越复杂。我认为在这种情况下问题甚至没有得到很好的定义，因此寻找解决方案（有效或其他方式）没有多大意义。
单变量假设
话虽如此，如果您假设系统中恰好有一个变量，我认为您可以想出一个解决方案。 （或者，或者，如果您将所有其他变量固定为一些预定义的常量。）如果您愿意沿着这条路走下去，那么您可以通过简单地证明量化公式
Exists([b], And(b >= minBound, b <= maxBound, Not(constraints)))
一旦你为此获得 unsat，你就有了你的射程。只要你得到sat，你就可以调整你的minBound/maxBound在更小的范围内搜索。在最坏的情况下，这可能会变成直线行走，但您可以 "cut-down" 通过确保在每一步中缩小一个显着尺寸来进行此搜索。这可能是整个搜索的一个参数，具体取决于您希望间隔有多大。必须在尝试找到最大范围和您希望在此搜索中花费多长时间之间做出选择。当然，如果你削减太多，你可能会错过一个很大的区间，但这是效率的代价。
Example1（好案例）有一个约束表示 b != 5。然后您的搜索将很快并且取决于您要去的分支，您将找到 [0, 4] 或 [6, 255] 假设 8 位字。
Example2（坏的情况）有一个约束说 b is even。那么您的搜索将表现出最坏情况的行为，如果您的 "cut-down" 大小为 1，则您可能会迭代 255 次，然后才能确定 [0, 0]；假设 z3 给你每次通话中的最大奇数。
我希望这能说明问题。不过，总的来说，我假设您在实际应用中会更接近 "good case"，即使您的缩减尺寸很小，您也很可能在几次迭代中收敛。当然，这完全取决于您的问题领域，但我希望它适用于一般的软件分析。
这个问题与我之前的问题有关
所以看起来 "efficiently" 找到最大范围信息是不合适的，给定典型的 32 位向量等等。但另一方面，我在考虑是否可以找到某些 "sub-maximum" 范围信息，希望这会变得更有效率。另一件事是我们可能希望有一定的 "safe" 保证，比如对于次最大范围内的所有元素，它们必须满足约束，但可能存在其他一些也满足约束的解决方案。
我目前正在探索 model counting 技术在这种情况下是否有意义。任何想法将不胜感激。谢谢。
一般情况
这不仅仅是效率的问题。考虑一个问题，您有两个变量 a 和 b，以及一个约束：
a != b
b的范围是多少？ （最大还是其他？）
你可以说所有的值都是合法的。但那是错误的，因为 a 的选择显然会影响 b 的选择。你周围的变量越多，问题就会变得越复杂。我认为在这种情况下问题甚至没有得到很好的定义，因此寻找解决方案（有效或其他方式）没有多大意义。
单变量假设
话虽如此，如果您假设系统中恰好有一个变量，我认为您可以想出一个解决方案。 （或者，或者，如果您将所有其他变量固定为一些预定义的常量。）如果您愿意沿着这条路走下去，那么您可以通过简单地证明量化公式
Exists([b], And(b >= minBound, b <= maxBound, Not(constraints)))
一旦你为此获得 unsat，你就有了你的射程。只要你得到sat，你就可以调整你的minBound/maxBound在更小的范围内搜索。在最坏的情况下，这可能会变成直线行走，但您可以 "cut-down" 通过确保在每一步中缩小一个显着尺寸来进行此搜索。这可能是整个搜索的一个参数，具体取决于您希望间隔有多大。必须在尝试找到最大范围和您希望在此搜索中花费多长时间之间做出选择。当然，如果你削减太多，你可能会错过一个很大的区间，但这是效率的代价。
Example1（好案例）有一个约束表示 b != 5。然后您的搜索将很快并且取决于您要去的分支，您将找到 [0, 4] 或 [6, 255] 假设 8 位字。
Example2（坏的情况）有一个约束说 b is even。那么您的搜索将表现出最坏情况的行为，如果您的 "cut-down" 大小为 1，则您可能会迭代 255 次，然后才能确定 [0, 0]；假设 z3 给你每次通话中的最大奇数。
我希望这能说明问题。不过，总的来说，我假设您在实际应用中会更接近 "good case"，即使您的缩减尺寸很小，您也很可能在几次迭代中收敛。当然，这完全取决于您的问题领域，但我希望它适用于一般的软件分析。