假设您正在对软件进行逆向工程。该软件使用经过加密和加密的库。该库包含一个函数，称之为secret_function。此函数是一个纯函数（即，它没有任何副作用，当使用相同的参数调用时，它始终返回相同的输出）。

假设我可以调用secret_function我希望多少次，使用我想要的任何参数，但我无法看清实现，是否有可能用另一种语言（例如python）构建等效功能，而仅分析输入和输出值？

是secret_function的示例实现：



int secret_function(int a, int b) {
    if (a == 234) {
        return b*2 - a;
    }
    return a*b;
}


我想到的一种归档方法是使用每个可能的参数调用函数， （在示例2 ^ 32 * 2 ^ 32中，假设为32位int）并存储所有它们，以根据参数返回它们，例如巨型查找表。但这似乎不是很有效，如果可能的话。

UPDATE：
您可以假定该函数正在使用固定大小的参数。因此没有字符串或变长数组。

评论

我想您已经用您的示例回答了这个问题。如果不使用确切的输入来评估功能，就无法检测到特殊情况（234）。查找表也仅适用于具有定义范围的输入，使用字符串，您将永远无法创建查找表。

#1 楼

您的问题似乎与Sibyl的目的有关（https://github.com/cea-sec/Sibyl）。
它会基于函数的副作用（返回值，内存写入等）来尝试识别已知函数。
当然，您将需要一种数据库来“学习”功能！

#2 楼

如果您拥有所有可能的输入和所有预期的输出，并且它们与加密/压缩的数据没有区别，那么您可以找到比仅拥有一个大的查找表更有效的存储机制。即使是简单的遗传算法也可以很快使您“使用* * b，除非a == 234”（尽管在更一般的数学公式情况下，我实际上已经专门针对此类问题制作了求解器）。最后，这是一个相当普通的优化问题，您需要在平衡存储空间，计算和准备时间上取得正确的结果。更复杂的算法需要更长的时间才能解决，这是加密起作用的原因之一-这些算法经过专门设计，使其从一组已知的输入和输出到用于加密的私钥变得非常费力。

但是在任何情况下，为了确定性，您都必须尝试所有可能的输入。对于几个整数来说，这很容易（虽然肯定很费力），但很快就变得难以处理像字符串这样的东西。

评论

您引用的遗传算法听起来很有趣，您有任何例子吗？如果可能的输入数量增加，遗传算法是否仍然有效？

– Rocco Mancin
19年4月9日在14:41
@RoccoMancin输入的数量并不是真正使整个过程变慢的原因（除了验证）；当问题变得更加复杂（分支更多，操作更复杂）时，遗传算法往往需要更长的时间才能找到解决方案。但是，当然，对于您选择的任何算法，如果您需要100％的准确度，那么总会有一个步骤需要对照所有预期的输出检查所有可能的输入（即使如此，仅假设相同的输入始终产生相同的输入）输出）。

–罗安
19年4月9日在16:13
我在GitHub（github.com/Luaancz/SalemOptimizer）上有一个简单的遗传求解器；它改编自我前段时间编写的更通用的求解器。这个特定的操作只有一个“操作”（称为分支；今天我可能会使用“表达式”或“节点”），但这仅是因为问题只需要一个-相同的方法可以轻松地用于多个操作不过。对于数学求解器，这些将是加法，乘法等。

–罗安
19年4月9日在16:19

#3 楼

除非按照您的建议尝试所有输入可能性，否则您只能获得该函数的近似值。这基本上是机器学习领域中的基本问题之一，所以我会这样看，而不是尝试为2 ^ 32 * 2 ^ 32的值生成查找表。

您显然应该请注意，您将无法100％保证该函数是等效的，并且还请记住，在特定字段中，如何计算输出与输出本身同样重要。以加密功能为例：具有相同的输出，但是暴露出用于侧面通道攻击的信息（由于内存泄漏，电源使用高峰等），这意味着“等效”功能实际上比原始功能差很多（以至于它可能不会是合适的替代品。

#4 楼

这个问题从本质上描述了顺序分析和曲线拟合的领域。

如果您能够对模型需要利用的秘密函数的输入做出一些假设，则可以使用此模型指导您选择用于生成新值以尝试作为函数输入的算法。

如果您可以对函数的特征做出一些假设，则可以以此为指导来选择函数适合秘密函数的输出，这将决定当将结果函数接受尚未尝试的输入时，结果函数的行为。

即使给出的“简单”示例也可能会被解释这些领域的许多不同方式。例如：


如果您不能假设任何有关函数的信息，并且您的模型必须准确地再现正确的值，则别无选择，只能评估所有2 ^ 64种可能性。如果您正确地猜测一个可以使用正确的参数重现每个值的函数，则不一定要随便存储它们。
如果您知道a确实有一个值可以更改该函数，并且它是a和b的两个线性函数之一（取决于此值），那么您平均需要进行2 ^ 31次试验才能找到神奇的a值，从而大大缩小了问题的范围。
如果不需要精确的复制，然后您就可以从价值判断中开始推理可接受的错误。例如，一个完全错误的函数在2 ^ -32的时间可能是完全可以接受的，因此，如果您知道特殊情况不大于此，则可以选择一些随机值（几乎可以肯定不是偶然选择a = 234）并求解线性方程。
您可能不合理地知道该函数具有线性部分，但是知道它并不比其他函数复杂。当这个更复杂的函数的参数适合秘密函数的输出时，将产生一个函数，该函数与从该函数获得的值的线性行为相匹配，但不一定要保证对未经测试的值具有线性行为。因此，您选择适合的任何功能的可能行为都必须努力与在您的假设下被认为合理的行为范围相匹配。

这些领域很大，可能有很多选择可以利用您的问题的详细信息为您提供服务。