优化字节数组简单模式匹配

Question

为了练习，我不得不在字节数组中寻找特定的字节模式，这很简单，但我想知道是否可以简化甚至优化代码：

package anti_virus;

import java.nio.file.Files;
import java.nio.file.Paths;

public class Main {

    public static void main(String[] args) throws Exception {
        byte[] virus = Files.readAllBytes(Paths.get("C:/Users/Nick/Desktop/Uni/infected.com"));

        byte[] payload = new byte[]{0x56, 0x69, 0x72, 0x75, 0x73, (byte)0xB4, 0x40, (byte) 0xBB, 0x01,
                0x00, (byte) 0xB9, 0x05, 0x00, (byte) 0xBA, 0x0, 0x0, (byte) 0xCD, 0x21};

        // payload[14] and payload[14] have varying values

        for (int i = 0; i < virus.length; i++) {
            if ((virus[i] == payload[0]) && (virus[i+1] == payload[1]) && (virus[i+2] == payload[2]) &&
                (virus[i+3] == payload[3]) && (virus[i+4] == payload[4]) && (virus[i+5] == payload[5]) &&
                (virus[i+6] == payload[6]) && (virus[i+7] == payload[7]) && (virus[i+8] == payload[8]) &&
                (virus[i+9] == payload[9]) && (virus[i+10] == payload[10]) && (virus[i+11] == payload[11]) &&
                (virus[i+12] == payload[12]) && (virus[i+13] == payload[13]) && (virus[i+16] == payload[16]) &&
                (virus[i+17] == payload[17])) {
                  System.out.println("This file is probably a Virus!");
                  return;
            }
        }

        System.out.println("This file is no Virus.");
    }
}

Answer 1

像这样的东西会检查数组中任何地方的签名，虽然还没有经过彻底测试

public static void main(String[] args) throws Exception {
    byte[] virus = FileUtil.readBytes(new File("c:/x.txt"));
    byte[] payload = "def".getBytes();

    for (int i = 0; i < virus.length; i++) {
        if ((i + payload.length) <= virus.length) {
            boolean found = true;
            for (int j = 0; j < payload.length; j++) {
                if (virus[i + j] != payload[j]) {
                    found = false;
                    break;
                }
            }

            if (found) {
                System.out.println("This file is probably a Virus!");
                return;
            }
        } else {
            break;
        }
    }

    System.out.println("This file is no Virus.");
}

Answer 2

是的，可以是simplified/optimized:

您可以使用 KMP algorithm（前 14 个字节）。该算法在 O(payload.length + virus.length) 中运行任意 payload 而不是 O(payload.length * virus.length)。（您的代码比 O(payload.length * virus.length) 更有效，原因只有一个：0x56 仅作为数组的第一个元素出现）
即使您选择保留算法，我也会使用循环来使代码更短且更易读。我还会在你的循环中修复 ArrayIndexOutOfBoundsException 的来源（你可以访问 virus 数组的索引 i, ..., i+13, i+16, i+17 并且你的循环条件允许 i 变得与 virus.length-1).

Answer 3

（这里我假设virus是病毒签名，payload是任何数据。我看到你的代码可能是错误的。）

必须在 [0, payload.length - virus.length] (!) 中遍历 paylöadIndex 的有效负载数组，并在 for 循环中的每一步再次检查病毒数组，使用一个病毒索引。

问题解决策略。想想你会如何在纸上做到这一点。您可以将病毒阵列转移到有效负载阵列上。

Answer 4

您的代码非常好，它在非病毒 6 MB 文件上给出了合理的 21 毫秒。但我发现最好为前 14 个字节做一些预循环。此外，您必须注意结尾字节。

begin = System.currentTimeMillis();
for (i = 0; i < virus.length-payload.length; i++) {
    for (j = 0; j < 14; j++) {
        // payload[14] and payload[15] have varying values
        if (virus[i+j] != payload[j]) {
            bFound = false;
            break;
        }
    }
    if ((bFound) && (virus[i+16] == payload[16]) && (virus[i+17] == payload[17])) {
        end = System.currentTimeMillis();
        System.out.println("time : "+(end-begin)+" ms");
        System.out.println("This file is probably a Virus!");
        return;
    }
}
end = System.currentTimeMillis();
System.out.println("time : "+(end-begin)+" ms");
System.out.println("This file is not a Virus.");

第一个优化给出了合理的 14 毫秒（CPU 的 -33%）。

另一个优化，如果你能负担得起以整数形式读取你的文件，那就是一次进行宽比较（4 个字节）。您还应该将有效载荷填充为 4 的倍数。

begin = System.currentTimeMillis();
for (i = 0; i < virusInt.length-payloadInt.length; i++) {
    if ((virusInt[i] == payloadInt[0]) && 
        (virusInt[i+1] == payloadInt[1]) && 
        (virusInt[i+2] == payloadInt[2]) &&
        ((virusInt[i+3]&0xFFFF0000) == payloadInt[3]) && 
        ((virusInt[i+4]&0xFFFF0000) == payloadInt[4])) {
           end = System.currentTimeMillis();
           System.out.println("time : "+(end-begin)+" ms");
           System.out.println("This file is probably a Virus!");
           return;
       }
}
end = System.currentTimeMillis();
System.out.println("time : "+(end-begin)+" ms");
System.out.println("This file is not a Virus.");

这给了我更合理的 2 毫秒（CPU 的 -90%）。当然，我没有计算转换为 int 数组的时间，因为我假设您加载为 int 数组并且您的有效负载也是一个 int 数组。我没有尝试过 long（在 JAVA 中是 64 位）但它可能会快一点。

优化字节数组简单模式匹配

Optimize byte array simple pattern matching

java

bytearray

pattern-matching