파일 무결성 검사 (hashmap 방식 응용)

Hashmap을 uftrace에서 활용하기 위해 Android 구 버전에서 hashmap 구현을 복붙하는 과정에서,

 

https://github.com/ParkHanbum/android_c_hashmap

GitHub - ParkHanbum/android_c_hashmap: C collection hashmap from android (4.3)

Hashmap의 구현에 대해 조금 공부를 해보게 됐다.

Hashmap에 대해서는 이 블로그를 참고하면 좋을 것 같다.

Java HashMap은 어떻게 동작하는가? - D2

https://d2.naver.com/helloworld/831311

 

Hashmap을 공부해서 다음 링크의 코드 포함한 PR을 진행했었다.

https://github.com/namhyung/uftrace/blob/master/utils/hashmap.c

GitHub - namhyung/uftrace: Function graph tracer for C/C++/Rust

여기서 달라진 점은, uftrace라는 프로젝트에서는 특정 메모리 주소와 Symbol을 매칭시키기 위해서 hashmap을 사용한만큼 hashing을 할 필요가 없었다는 점이다. hashmap은 key를 hash하고 bucket만큼 앞 bit를 읽어 key index를 찾게 되는데 검색은 O(1)에 가깝지만 hash하는 비용이 추가된다. hashmap을 커마해서 hash 타임을 없앤만큼 O(1)에 가까운 hashmap아닌 hashmap 을 사용할 수 있게 됐다.

 

 

여튼 사설이 길었고, 본론인 파일 무결성 검사를 위의 경험을 토대로 hashmap과 유사 방식을 적용하는 방법을 공유하고자 할건데, 다음과 같은 경우에 효과적일 수 있다.

 

1. 고정된 파일들에 대한 해시를 보관하고 실행 전 해시 비교를 통한 무결성 검사를 하는 경우

 

 

관련 예제 코드는 다음 링크에 있다.

https://github.com/ParkHanbum/mystudy/tree/master/integrity

GitHub - ParkHanbum/mystudy

 

파일을 무결성을 검사하기 위해 파일이름과 파일내용의 해시를 pair로 보관할 자료형을 만든다.

struct hash_pair {
  unsigned char namehash[SHA256_DIGEST_LENGTH];
  unsigned char datahash[SHA256_DIGEST_LENGTH];
};

__attribute__((section("myhashes"),used))
struct hash_pair hashes[DEFINED_FILE_COUNT];

위처럼 특정 섹션을 지정한 배열변수를 선언한다.

위의 섹션은 컴파일하고 난 뒤 지정된 이름의 섹션을 생성하는데, 여기에 python으로 파일 해시들을 계산해서 써넣을 것이다. 예제에서는 실행파일로 컴파일하고 이름은 "integrity" 로 정해놨다.

 

다음은 빌드된 "integrity" 파일에 "myhashes" 섹션을 찾아서 지정된 경로에 존재하는 파일들의 파일명/파일데이터의 hash를 pair 로 기록하는 python code이다.

    f = open("integrity", "rb+")
    elf = ELFFile(f)
    pos = 0
    idx_pos = 0
    for section in elf.iter_sections():
        if section.name == "myhashes":
            pos = section['sh_offset']
        if section.name == "myhashes_index":
            idx_pos = section['sh_offset']

    hash_pair = []
    for path in filelist:
        pair = []
        # filename hash
        sha = hashlib.new('sha256')
        sha.update(path.encode('utf-8'))
        hex = sha.hexdigest()
        pair.append(hex)

        # filedata hash
        data = open(path, "rb+").read()
        sha = hashlib.new('sha256')
        sha.update(data)
        hex = sha.hexdigest()
        pair.append(hex)

        # keep the filename for logging
        pair.append(path)

        hash_pair.append(pair)

    # sort is required for use like hashmap
    hash_pair = sorted(hash_pair)
    for idx, el in enumerate(hash_pair):
        name_hash = el[0]
        data_hash = el[1]
        path = el[2]
        f.seek(pos, 0)
        f.write(bytes.fromhex(name_hash))
        pos += 32
        f.seek(pos, 0)
        f.write(bytes.fromhex(data_hash))
        pos += 32

 

다음과 같은 테스트 코드로 데이터가 잘 입력됐는지 확인할 수 있다.

void testINTEGRITY1() {
  int i;
  for (i = 0; i < DEFINED_FILE_COUNT; i++) {
    struct hash_pair curr = hashes[i];
    printf("%d] ", i);
    print_hex(curr.namehash, SHA256_DIGEST_LENGTH);
    print_hex(curr.datahash, SHA256_DIGEST_LENGTH);
  }
}

아래처럼 데이터가 정상 입력됐다는걸 확인할 수 있다.

0] 13 49 15 23 a6 50 52 f2 05 f0 16 70 98 d8 9c cc dd 4a 10 30 12 36 34 c7 0e a8 ee 59 8c 9b ea eb  1d f5 ff 39 1f 84 3c ab 7f c8 53 1b cf 68 9d f6 c4 8d cb 30 4e 97 d9 76 09 87 a6 53 77 4c 5a 6a  1] 1b f0 6d 65 76 23 bd cc 2d e7 03 1d a1 d0 62 05 43 5c 1f 03 a6 a5 fc 1a 2b 93 73 3a a1 d2 8e 96  b1 09 14 c2 b8 c3 5e 98 f7 ee a1 be 11 40 dd 79 33 20 9f 03 c8 30 bc 3b 73 0c c3 a8 8e 29 ea d7  2] 20 e9 83 ae 83 42 46 98 43 c0 34 ec 81 f1 e5 17 a4 0a 9e 93 95 97 23 56 24 bb 8b 10 79 a5 b4 7f  d6 a1 46 a8 41 e2 b1 67 50 88 7a c9 ab 58 81 2e c1 9a f6 0b db 1f de 31 6d 2b cc e6 81 70 1f 28

 

데이터를 잘 써넣었다면, 이제 "integrity"에서 지정된 경로의 파일들의 파일명/파일데이터 hash를 hash_pair hashes 배열을 순환하며 검색해서 hash를 맞춰보면 첫 단계의 무결성 검증은 끝난 것이다.

 

위의 과정은 testINTEGRITY2를 통해 확인할 수 있다.

void testINTEGRITY2() {
  unsigned char namehash[SHA256_DIGEST_LENGTH] = {
      0,
  };
  unsigned char datahash[SHA256_DIGEST_LENGTH] = {
      0,
  };
  unsigned char path[PATH_MAX];
  int i;
  char *buf;
  FILE *fp;
  long size;

  DIR *dp;
  struct dirent *ep;
  dp = opendir("temp");
  while ((ep = readdir(dp)) != NULL) {
    if (ep->d_type == DT_REG) {
      snprintf(path, PATH_MAX, "temp/%s", ep->d_name);
      puts(path);

      fp = fopen(path, "r");
      fseek(fp, 0, SEEK_END);
      size = ftell(fp);
      rewind(fp);

      buf = malloc(size);
      fread(buf, 1, size, fp);
      fclose(fp);

      SHA256((unsigned char *)&path, strlen(path), (unsigned char *)&namehash);
      SHA256((unsigned char *)buf, size, (unsigned char *)&datahash);
      free(buf);

      for (i = 0; i < DEFINED_FILE_COUNT; i++) {
        struct hash_pair curr = hashes[i];
        if (memcmp(namehash, curr.namehash, SHA256_DIGEST_LENGTH) == 0) {
          printf("[%d] hash found! : ", i);
          print_hex(namehash, SHA256_DIGEST_LENGTH);
          if (memcmp(datahash, curr.datahash, SHA256_DIGEST_LENGTH) == 0) {
            printf("correct! : ");
            print_hex(datahash, SHA_DIGEST_LENGTH);
          } else {
            printf("hash tampering : ");
            print_hex(datahash, SHA256_DIGEST_LENGTH);
            print_hex(curr.datahash, SHA256_DIGEST_LENGTH);
          }
        }
      }
    }
  }
  closedir(dp);
}

 

결과는 다음과 같이 확인 가능하다.

[21] hash found! : bf 2a fa e4 16 55 e7 dd dd 65 36 2c 31 ba ef 83 ea 66 5b 93 0b 18 26 ac b1 d6 4c b1 7d 79 5f fa  correct! : 79 3c 72 a2 d4 98 92 10 d8 a4 da 65 e2 27 91 47 e8 32 9c b4  temp/temporary-31 [30] hash found! : e1 34 15 ca 97 ae 9d dc 2b 0c b8 ec c1 54 4f c5 31 dc 92 88 28 45 8a 3b 52 ae 2a 73 2a c9 78 be  correct! : 8b cc 90 d1 3f 00 e2 2b 0b 05 d7 aa 5c 19 e6 16 70 9d 70 35  temp/temporary-4

 

 

여기까지 왔으면 이제 hashes 배열을 그대로 둔 채로, 이를 indexing하는 방식을 추가하여 hashmap과 유사한 효과를 노려볼 것이다. 먼저 hashes 배열을 인덱싱하기 위한 구조체와 배열을 선언하고 여기에 python으로 계산된 indexing 데이터를 기록하도록 하자.

 

struct index {
    int hash_idx;
    int count;
};

__attribute__((section("myhashes_index"),used))
struct index ind[BUCKET_COUNT];

hashes를 인덱싱하기 위한 자료구조를 만들고 myhashes_index 에  할당되도록 한다.

여기부터가 hashmap 관련된 로직이 들어간다.

    # hash index generate
    hashbit = len(bin(bucketcount - 1)[2:])
    hashbook = {}
    pos = 0
    for idx, el in enumerate(hash_pair):
        name_hash = el[0]
        data_hash = el[1]
        path = el[2]

        # calculate hash index
        v = int(name_hash, 16)
        # key index
        key_idx = v >> (256 - hashbit)
        if key_idx in hashbook:
            el = hashbook[key_idx]
            el["count"] = el["count"] + 1
        else:
            hashbook[key_idx] = {"hash_idx":idx, "count": 1}


    for key_idx, item in hashbook.items():
        # since it has sorted it before, this work can sequentially
        pos = idx_pos + (8 * key_idx)
        f.seek(pos, 0)
        f.write((item["hash_idx"]).to_bytes(4, byteorder="little"))
        pos = pos + 4
        f.seek(pos, 0)
        f.write((item["count"]).to_bytes(4, byteorder="little"))

 

python 코드이다. 여기서 하는일은 먼저 indexing에 사용될 ind 배열의 크기를 구하는 것이다.

    hashbit = len(bin(bucketcount - 1)[2:])

hashmap 에 대한 링크를 참고하지 않은 분을 위해 설명을 덧붙이자면, hashmap이란 자료구조는 key 값의 hash를 바로 index로 사용함을 통해 탐색시간을 O(1)에 가깝게 유지하는 것이 목적이다. 이건 어떤 방식으로 가능한지 예제 데이터를 통해 설명하도록 하겠다.

0]temp/temporary-9 13491523a65052f205f0167098d89cccdd4a1030123634c70ea8ee598c9beaeb 1]temp/temporary-19 1bf06d657623bdcc2de7031da1d06205435c1f03a6a5fc1a2b93733aa1d28e96 2]temp/temporary-13 20e983ae8342469843c034ec81f1e517a40a9e939597235624bb8b1079a5b47f 3]temp/temporary-10 2eb65f2b2db057657f206d1c108576e71d2b9ea899320bdb8483ed731ede84d9 4]temp/temporary-25 2f35a6ca33b23b859c9c97fc68657b3c3c9bc59d57cc2575068ca42e5e45b399 5]temp/temporary-12 3f6e8dce30fb1cc086ce3098d9df38bc1ef997c05feaa4c0994be28162faad14 6]temp/temporary-3 4a311e2eb5c238b271ba29f213bbbd5ea0f3c5810121a02e87607fab46b349e0 7]temp/temporary-29 4ad14317f4384f1c9476c81ae3304f4549e451bb460427d603b939e187cd3dd0 8]temp/temporary-0 50bc8250bb1de8627c66ff972bcbcc4db5f498d5a4cca655954efd1deb3c43c7 9]temp/temporary-28 515a3cb5ba5026c1a34b88d92f9a236c6f670d83fceff02aa9e71fd0b3014f9a 10]temp/temporary-5 63b785112f0a3879d76c69eac9362a631fe89ea7e9aade5c4dca2dfcfe64bd78 11]temp/temporary-18 83e8d3991f95a3a78442c88797ca95256f628e38f6df4cf9932a01e7a1a95dbe 12]temp/temporary-15 844b992b7d1bb18eff46c3e32aac7435fd0e237972aab175787a8ee9394f61d8 13]temp/temporary-1 881003f79207ad3887182162b4a3429d6a4c37f6d6ca2f02b4f3f6ac0d2ba631 14]temp/temporary-4 8d889d0cf06f505adb1dccc88129e920f91c3aa8b8454558d9627fd42ecece78 15]temp/temporary-24 9ee759e7dd7d01ffb18d058bd0206b744626e66c595ca15b6e5d493619ba4730 16]temp/temporary-16 a11428e5de68ccda1d4774fe0f04ac25b4ab7591b8eba8a28b80359cc95f012b 17]temp/temporary-11 a985f43b92ffef95c3fd5324f7d908620ad69a12d50307179e49ea90ada56d44 18]temp/temporary-23 b1c96e0a747932173514485ee09da6dc695c79290284ac3f7b17979dfe62e0f9 19]temp/temporary-8 bc5a4fef1c9613f0023630a086cd73fb93088b1dc30f69be327bfaa0ade061dc 20]temp/temporary-17 bdc3fc7c581efb5fa60370e12a4808ad67d4e2943f3510b6296878b54c94a997 21]temp/temporary-22 bf2afae41655e7dddd65362c31baef83ea665b930b1826acb1d64cb17d795ffa 22]temp/temporary-21 cf509969e598e355ee241aa4991382cf1180545d3dfaab95c11faa0864dedf9b 23]temp/temporary-26 d02db5efc447fc50062accd8e54b95e7c040da166dc2f7f6bc72a35a5ca41db7 24]temp/temporary-20 d06f08438fd1f0c7fc0c5e4679b310053c3fe808e984b4f55935a4d01762fe97 25]temp/temporary-27 d0da0fbf175e672f250a6e25248501be509c8342511e0e6a5989aafae0c373ee 26]temp/temporary-7 d171243c0ff82e0fb316b58d126ed16509983f752d0322cc9b0326d3bfe8aeb1 27]temp/temporary-6 d494a51c2cd5b34bcb69ac5db4157456952058d9e16d1b95bbb22eb558554881 28]temp/temporary-14 d9e5153e4f9ba7157b9cbf0448356c263e7368bb1397ac08923c19cce33ac75a 29]temp/temporary-30 ddf430b6f4ec4145bc5dadff7b1343e34da48126d8804edc34870623e976e6d1 30]temp/temporary-31 e13415ca97ae9ddc2b0cb8ecc1544fc531dc928828458a3b52ae2a732ac978be 31]temp/temporary-2 e86f90ee407d40a284a5972e73ed81109a07d2f07807f3cab666f18ef5e97e5f

위와 같은 데이터 샘플이 존재한다고 했을때 key의 길이가 길기 때문에 key 전체를 index로 사용하게 되면 말도 안되는 규모의 메모리 공간을 할당해야 한다.범위가 0x0부터 0xFF * 32 까지이다. 그러므로 hashmap은 전략적으로 key의 상단부만 사용하는 방식으로 데이터의 총 수 따라 index에 필요한 메모리 공간을 조절한다.

 

예를 들어, 위의 데이터는 32개이고, 32개의 데이터는 이상적으로 key의 상위 5bit 만 사용하면 모든 데이터를 indexing 할 수 있다. 물론 아래에 보겠지만 그렇게 되진 않는다. key의 상위 5bit로 index하기 위해서, 미리 ind 를 선언해뒀으며, ind는 hash가 존재하는 hahes의 index와 count  를 함께 저장한다.

 

key의 상위 5bit 를 계산하여 ind에 보관하면 다음과 같은 형태가 된다.

2 0 1 13491523a65052f205f0167098d89cccdd4a1030123634c70ea8ee598c9beaeb 3 1 1 1bf06d657623bdcc2de7031da1d06205435c1f03a6a5fc1a2b93733aa1d28e96 4 2 1 20e983ae8342469843c034ec81f1e517a40a9e939597235624bb8b1079a5b47f 5 3 2 2eb65f2b2db057657f206d1c108576e71d2b9ea899320bdb8483ed731ede84d9 7 5 1 3f6e8dce30fb1cc086ce3098d9df38bc1ef997c05feaa4c0994be28162faad14 9 6 2 4a311e2eb5c238b271ba29f213bbbd5ea0f3c5810121a02e87607fab46b349e0 10 8 2 50bc8250bb1de8627c66ff972bcbcc4db5f498d5a4cca655954efd1deb3c43c7 12 10 1 63b785112f0a3879d76c69eac9362a631fe89ea7e9aade5c4dca2dfcfe64bd78 16 11 2 83e8d3991f95a3a78442c88797ca95256f628e38f6df4cf9932a01e7a1a95dbe 17 13 2 881003f79207ad3887182162b4a3429d6a4c37f6d6ca2f02b4f3f6ac0d2ba631 19 15 1 9ee759e7dd7d01ffb18d058bd0206b744626e66c595ca15b6e5d493619ba4730 20 16 1 a11428e5de68ccda1d4774fe0f04ac25b4ab7591b8eba8a28b80359cc95f012b 21 17 1 a985f43b92ffef95c3fd5324f7d908620ad69a12d50307179e49ea90ada56d44 22 18 1 b1c96e0a747932173514485ee09da6dc695c79290284ac3f7b17979dfe62e0f9 23 19 3 bc5a4fef1c9613f0023630a086cd73fb93088b1dc30f69be327bfaa0ade061dc 25 22 1 cf509969e598e355ee241aa4991382cf1180545d3dfaab95c11faa0864dedf9b 26 23 5 d02db5efc447fc50062accd8e54b95e7c040da166dc2f7f6bc72a35a5ca41db7 27 28 2 d9e5153e4f9ba7157b9cbf0448356c263e7368bb1397ac08923c19cce33ac75a 28 30 1 e13415ca97ae9ddc2b0cb8ecc1544fc531dc928828458a3b52ae2a732ac978be 29 31 1 e86f90ee407d40a284a5972e73ed81109a07d2f07807f3cab666f18ef5e97e5f

맨 앞 숫자는 ind 의 index

두 번째 숫자는 hashes 의 index

세 번째 숫자는 count 이다.

2 0 1 13491523a65052f205f0167098d89cccdd4a1030123634c70ea8ee598c9beaeb

맨 상단의 데이터를 분해해보자.

2 = ind의 index이다. 이는 앞서 말했듯 32개의 데이터를 모두 indexing 할 수 있는 최소의 bit 수 5개를 key인 namehash 에서 추출한 값이다.

 

즉, 특정 경로에 존재하는 파일명을 hash한 뒤 상위 5bit를 추출하면 2가 나오므로 ind[2] 에는 hashes[0] 의 index와 count 1를 저장한다. 그러면 파일명 hash를 통해 바로 파일데이터 hash index를 찾아갈 수 있게 되므로 O(1)의 탐색시간을 보장하는 것이다.

 

다른 데이터를 한번 더 살펴보자.

26 23 5 d02db5efc447fc50062accd8e54b95e7c040da166dc2f7f6bc72a35a5ca41db7

이 데이터는 ind[26] = { hash_idx : 23, count : 5 } 를 나타낸다.

여기서 주목할 것은 count 이다. 앞서 우리가 최소한의 메모리 공간으로 데이터를 모두 indexing 할 수 있는 bit 수가 5라고 계산했는데, 이렇게 타이트하게 하면 5 bit 안에서 중복되는 데이터들이 존재하게 된다. 이 중복데이터들이 count이다.

 

아래가 그 중복의 원흉들이다.

temp/temporary-26 26 d02db5efc447fc50062accd8e54b95e7c040da166dc2f7f6bc72a35a5ca41db7 temp/temporary-20 26 d06f08438fd1f0c7fc0c5e4679b310053c3fe808e984b4f55935a4d01762fe97 temp/temporary-27 26 d0da0fbf175e672f250a6e25248501be509c8342511e0e6a5989aafae0c373ee temp/temporary-7 26 d171243c0ff82e0fb316b58d126ed16509983f752d0322cc9b0326d3bfe8aeb1 temp/temporary-6 26 d494a51c2cd5b34bcb69ac5db4157456952058d9e16d1b95bbb22eb558554881

5bit 만 쓰다보니 앞 8bit 가 d 인 친구들은 모두가 중복 key를 갖게 된다.

 

때문에 hashmap 유사한 구현은 중복 데이터를 수작업으로 검색해야 한다.

D2 의 링크글처럼 상용 hashmap 자료형들은 중복되는 key 의 검색도 최적화 하기 위해 rbtree같은 여러 자료형을 사용한다고 한다. 어쨌든, 여기서는 제한된 환경, 말하자면 데이터를 로드하고 다시 자료구조화 할 시간도 아깝기 때문에 FIXED 된 데이터 배열에서 최대의 효율을 내는 것을 목표로 해봤다.

 

대부분의 코드가 배열을 순차탐색하는 방식과 동일한 hashmap 유사방식을 살펴보자.

int count = BUCKET_COUNT - 1;
int hashbit = 0;
while (count > 0) {
	count >>= 1;
	hashbit++;
}

...
// calculate index
uint32_t key_idx = namehash[0] << 24;
key_idx += namehash[1] << 16;
key_idx += namehash[2] << 8;
key_idx += namehash[3];
key_idx = key_idx >> (32 - hashbit);
struct index idx = ind[key_idx];
printf("%d] hash index -> %d, count -> %d \n", key_idx, idx.hash_idx, idx.count);

// searching data
for (i = 0; i < idx.count; i++) {
	struct hash_pair p = hashes[idx.hash_idx + i];
	if (memcmp(p.namehash, namehash, SHA256_DIGEST_LENGTH) == 0) {
		if (memcmp(p.namehash, namehash, SHA256_DIGEST_LENGTH) == 0) {
    		printf("correct!\n");
    		break;
  		} 
        else
    		printf("data mismatched!\n");
	} 
    else
  		printf("key mismatched!\n");
}

파일 경로의 hash를 앞 4byte 떼네서 미리 주입한 bit 크기만큼 읽어 ind index를 구하고 이후 과정은 설명한대로 ind[index]에 존재하는 hashes의 index와 count 로 hashes[index] 부터 hashes[index+count] 까지 탐색하여 보관된 파일데이터 해쉬를 찾는다.

 

 

이를 통해 O(1)에 가까운 hashmap method 만 취해서 빠른 무결성 검사를 할 수 있다.

 

다음은 UFTRACE를 통해 간단히 벤치를 수행한 결과이다. 파일 수는 10만개를 지정했다.

ARAY순차탐색과 ARRAY를 indexing하여 hashmap 유사 탐색 방식 간의 성능차이