1// Copyright 2017 The Fuchsia Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#include <digest/merkle-tree.h> 6 7#include <stdlib.h> 8 9#include <digest/digest.h> 10#include <zircon/assert.h> 11#include <zircon/status.h> 12#include <unittest/unittest.h> 13 14namespace { 15 16//////////////// 17// Test support. 18 19// Helper defines for the typical case of checking a zx_status_t 20#define BEGIN_TEST_WITH_RC \ 21 BEGIN_TEST; \ 22 zx_status_t rc 23#define ASSERT_ERR(expected, expr) \ 24 rc = (expr); \ 25 ASSERT_EQ(expected, rc, zx_status_get_string(rc)) 26#define ASSERT_OK(expr) ASSERT_ERR(ZX_OK, (expr)) 27 28// These unit tests are for the MerkleTree object in ulib/digest. 29using digest::Digest; 30using digest::MerkleTree; 31 32// The MerkleTree tests below are naturally sensitive to the shape of the Merkle 33// tree. These determine those sizes in a consistent way. The only requirement 34// here is that |kSmall * Digest::kLength| should be less than |kNodeSize|. 35const uint64_t kNodeSize = MerkleTree::kNodeSize; 36const uint64_t kSmall = 8 * kNodeSize; 37const uint64_t kLarge = ((kNodeSize / Digest::kLength) + 1) * kNodeSize; 38const uint64_t kUnalignedLarge = kLarge + (kNodeSize / 2); 39 40// The hard-coded trees used for testing were created by using sha256sum on 41// files generated using echo -ne, dd, and xxd 42struct Case { 43 size_t data_len; 44 size_t tree_len; 45 const char digest[(Digest::kLength * 2) + 1]; 46} kCases[] = { 47 {0, 0, "15ec7bf0b50732b49f8228e07d24365338f9e3ab994b00af08e5a3bffe55fd8b"}, 48 {1, 0, "0967e0f62a104d1595610d272dfab3d2fa2fe07be0eebce13ef5d79db142610e"}, 49 {kNodeSize / 2, 0, 50 "0a90612c255555469dead72c8fdc41eec06dfe04a30a1f2b7c480ff95d20c5ec"}, 51 {kNodeSize - 1, 0, 52 "f2abd690381bab3ce485c814d05c310b22c34a7441418b5c1a002c344a80e730"}, 53 {kNodeSize, 0, 54 "68d131bc271f9c192d4f6dcd8fe61bef90004856da19d0f2f514a7f4098b0737"}, 55 {kNodeSize + 1, kNodeSize, 56 "374781f7d770b6ee9c1a63e186d2d0ccdad10d6aef4fd027e82b1be5b70a2a0c"}, 57 {kSmall, kNodeSize, 58 "f75f59a944d2433bc6830ec243bfefa457704d2aed12f30539cd4f18bf1d62cf"}, 59 {kLarge, kNodeSize * 3, 60 "7d75dfb18bfd48e03b5be4e8e9aeea2f89880cb81c1551df855e0d0a0cc59a67"}, 61 {kUnalignedLarge, kNodeSize * 3, 62 "7577266aa98ce587922fdc668c186e27f3c742fb1b732737153b70ae46973e43"}, 63}; 64 65const size_t kNumCases = sizeof(kCases) / sizeof(struct Case); 66 67// These tests use anonymously scoped globals to reduce the amount of repetitive 68// test setup. 69uint8_t gData[kUnalignedLarge]; 70uint8_t gTree[kNodeSize * 3]; 71 72//////////////// 73// Test cases 74 75bool GetTreeLength(void) { 76 BEGIN_TEST; 77 for (size_t i = 0; i < kNumCases; ++i) { 78 ZX_DEBUG_ASSERT(kCases[i].data_len <= sizeof(gData)); 79 ZX_DEBUG_ASSERT(kCases[i].tree_len <= sizeof(gTree)); 80 ASSERT_EQ(kCases[i].tree_len, 81 MerkleTree::GetTreeLength(kCases[i].data_len), 82 "Wrong tree length"); 83 } 84 END_TEST; 85} 86 87bool CreateInit(void) { 88 BEGIN_TEST_WITH_RC; 89 size_t tree_len = MerkleTree::GetTreeLength(kLarge); 90 MerkleTree merkleTree; 91 ASSERT_OK(merkleTree.CreateInit(kLarge, tree_len)); 92 END_TEST; 93} 94 95bool CreateInitWithoutData(void) { 96 BEGIN_TEST_WITH_RC; 97 size_t tree_len = MerkleTree::GetTreeLength(kLarge); 98 MerkleTree merkleTree; 99 ASSERT_OK(merkleTree.CreateInit(0, tree_len)); 100 ASSERT_OK(merkleTree.CreateInit(0, 0)); 101 END_TEST; 102} 103 104bool CreateInitWithoutTree(void) { 105 BEGIN_TEST_WITH_RC; 106 MerkleTree merkleTree; 107 ASSERT_OK(merkleTree.CreateInit(kNodeSize, 0)); 108 END_TEST; 109} 110 111bool CreateInitTreeTooSmall(void) { 112 BEGIN_TEST_WITH_RC; 113 size_t tree_len = MerkleTree::GetTreeLength(kLarge); 114 MerkleTree merkleTree; 115 ASSERT_ERR(ZX_ERR_BUFFER_TOO_SMALL, 116 merkleTree.CreateInit(kLarge, tree_len - 1)); 117 END_TEST; 118} 119 120bool CreateUpdate(void) { 121 BEGIN_TEST_WITH_RC; 122 size_t tree_len = MerkleTree::GetTreeLength(kLarge); 123 MerkleTree merkleTree; 124 ASSERT_OK(merkleTree.CreateInit(kLarge, tree_len)); 125 ASSERT_OK(merkleTree.CreateUpdate(gData, kLarge, gTree)); 126 END_TEST; 127} 128 129bool CreateUpdateMissingInit(void) { 130 BEGIN_TEST_WITH_RC; 131 MerkleTree merkleTree; 132 ASSERT_ERR(ZX_ERR_BAD_STATE, merkleTree.CreateUpdate(gData, kLarge, gTree)); 133 END_TEST; 134} 135 136bool CreateUpdateMissingData(void) { 137 BEGIN_TEST_WITH_RC; 138 size_t tree_len = MerkleTree::GetTreeLength(kLarge); 139 MerkleTree merkleTree; 140 ASSERT_OK(merkleTree.CreateInit(kLarge, tree_len)); 141 ASSERT_ERR(ZX_ERR_INVALID_ARGS, 142 merkleTree.CreateUpdate(nullptr, kLarge, gTree)); 143 END_TEST; 144} 145 146bool CreateUpdateMissingTree(void) { 147 BEGIN_TEST_WITH_RC; 148 size_t tree_len = MerkleTree::GetTreeLength(kLarge); 149 MerkleTree merkleTree; 150 ASSERT_OK(merkleTree.CreateInit(kLarge, tree_len)); 151 ASSERT_ERR(ZX_ERR_INVALID_ARGS, 152 merkleTree.CreateUpdate(gData, kLarge, nullptr)); 153 END_TEST; 154} 155 156bool CreateUpdateWithoutData(void) { 157 BEGIN_TEST_WITH_RC; 158 size_t tree_len = MerkleTree::GetTreeLength(kLarge); 159 MerkleTree merkleTree; 160 ASSERT_OK(merkleTree.CreateInit(kLarge, tree_len)); 161 ASSERT_OK(merkleTree.CreateUpdate(gData, 0, gTree)); 162 ASSERT_OK(merkleTree.CreateUpdate(nullptr, 0, gTree)); 163 END_TEST; 164} 165 166bool CreateUpdateWithoutTree(void) { 167 BEGIN_TEST_WITH_RC; 168 MerkleTree merkleTree; 169 ASSERT_OK(merkleTree.CreateInit(kNodeSize, 0)); 170 ASSERT_OK(merkleTree.CreateUpdate(gData, kNodeSize, nullptr)); 171 END_TEST; 172} 173 174bool CreateUpdateTooMuchData(void) { 175 BEGIN_TEST_WITH_RC; 176 size_t tree_len = MerkleTree::GetTreeLength(kLarge); 177 MerkleTree merkleTree; 178 ASSERT_OK(merkleTree.CreateInit(kLarge, tree_len)); 179 ASSERT_ERR(ZX_ERR_OUT_OF_RANGE, 180 merkleTree.CreateUpdate(gData, kLarge + 1, gTree)); 181 END_TEST; 182} 183 184bool CreateFinalMissingInit(void) { 185 BEGIN_TEST_WITH_RC; 186 MerkleTree merkleTree; 187 Digest digest; 188 ASSERT_ERR(ZX_ERR_BAD_STATE, merkleTree.CreateFinal(gTree, &digest)); 189 END_TEST; 190} 191 192// Used by CreateFinalAll, CreateFinalWithoutData, and CreateFinalWithoutTree 193// below 194bool CreateFinal(size_t data_len, const char* digest, void* data, void* tree) { 195 zx_status_t rc; 196 size_t tree_len = MerkleTree::GetTreeLength(data_len); 197 MerkleTree merkleTree; 198 ASSERT_OK(merkleTree.CreateInit(data_len, tree_len)); 199 ASSERT_OK(merkleTree.CreateUpdate(data, data_len, tree)); 200 Digest actual; 201 ASSERT_OK(merkleTree.CreateFinal(tree, &actual)); 202 Digest expected; 203 ASSERT_OK(expected.Parse(digest, strlen(digest))); 204 ASSERT_TRUE(actual == expected, "Incorrect root digest"); 205 return true; 206} 207 208bool CreateFinalAll(void) { 209 BEGIN_TEST; 210 for (size_t i = 0; i < kNumCases; ++i) { 211 if (!CreateFinal(kCases[i].data_len, kCases[i].digest, gData, gTree)) { 212 unittest_printf_critical( 213 "CreateFinalAll failed with data length of %zu\n", 214 kCases[i].data_len); 215 } 216 } 217 END_TEST; 218} 219 220bool CreateFinalWithoutData(void) { 221 BEGIN_TEST; 222 bool found = false; 223 for (size_t i = 0; i < kNumCases; ++i) { 224 if (kCases[i].data_len != 0) { 225 continue; 226 } 227 if (!CreateFinal(kCases[i].data_len, kCases[i].digest, nullptr, 228 nullptr)) { 229 unittest_printf_critical( 230 "CreateFinalWithoutData failed with data length of %zu\n", 231 kCases[i].data_len); 232 } 233 found = true; 234 } 235 ASSERT_TRUE(found, "Unable to find test cases with length == 0"); 236 END_TEST; 237} 238 239bool CreateFinalWithoutTree(void) { 240 BEGIN_TEST; 241 bool found = false; 242 for (size_t i = 0; i < kNumCases; ++i) { 243 if (kCases[i].data_len > kNodeSize) { 244 continue; 245 } 246 if (!CreateFinal(kCases[i].data_len, kCases[i].digest, gData, 247 nullptr)) { 248 unittest_printf_critical( 249 "CreateFinalWithoutTree failed with data length of %zu\n", 250 kCases[i].data_len); 251 } 252 found = true; 253 } 254 ASSERT_TRUE(found, "Unable to find test cases with length <= kNodeSize"); 255 END_TEST; 256} 257 258bool CreateFinalMissingDigest(void) { 259 BEGIN_TEST_WITH_RC; 260 size_t tree_len = MerkleTree::GetTreeLength(kLarge); 261 MerkleTree merkleTree; 262 ASSERT_OK(merkleTree.CreateInit(kLarge, tree_len)); 263 ASSERT_OK(merkleTree.CreateUpdate(gData, kLarge, gTree)); 264 ASSERT_ERR(ZX_ERR_INVALID_ARGS, merkleTree.CreateFinal(gTree, nullptr)); 265 END_TEST; 266} 267 268bool CreateFinalIncompleteData(void) { 269 BEGIN_TEST_WITH_RC; 270 size_t tree_len = MerkleTree::GetTreeLength(kLarge); 271 MerkleTree merkleTree; 272 ASSERT_OK(merkleTree.CreateInit(kLarge, tree_len)); 273 ASSERT_OK(merkleTree.CreateUpdate(gData, kLarge - 1, gTree)); 274 Digest digest; 275 ASSERT_ERR(ZX_ERR_BAD_STATE, merkleTree.CreateFinal(gTree, &digest)); 276 END_TEST; 277} 278 279// Used by CreateAll below. 280bool Create(size_t data_len, const char* digest) { 281 zx_status_t rc; 282 size_t tree_len = MerkleTree::GetTreeLength(data_len); 283 Digest actual; 284 ASSERT_OK(MerkleTree::Create(gData, data_len, gTree, tree_len, &actual)); 285 Digest expected; 286 ASSERT_OK(expected.Parse(digest, strlen(digest))); 287 ASSERT_TRUE(actual == expected, "Incorrect root digest"); 288 return true; 289} 290 291bool CreateAll(void) { 292 BEGIN_TEST; 293 for (size_t i = 0; i < kNumCases; ++i) { 294 if (!Create(kCases[i].data_len, kCases[i].digest)) { 295 unittest_printf_critical( 296 "CreateAll failed with data length of %zu\n", 297 kCases[i].data_len); 298 } 299 } 300 END_TEST; 301} 302 303// Used by CreateFinalCAll below. 304bool CreateFinalC(size_t data_len, const char* digest) { 305 zx_status_t rc; 306 // Init 307 size_t tree_len = merkle_tree_get_tree_length(data_len); 308 merkle_tree_t* mt = nullptr; 309 ASSERT_OK(merkle_tree_create_init(data_len, tree_len, &mt)); 310 // Update 311 size_t i = 0; 312 while (data_len - i > kNodeSize) { 313 ASSERT_OK(merkle_tree_create_update(mt, gData + i, kNodeSize, gTree)); 314 i += kNodeSize; 315 } 316 ASSERT_OK(merkle_tree_create_update(mt, gData + i, data_len - i, gTree)); 317 // Final 318 uint8_t actual[Digest::kLength]; 319 ASSERT_OK(merkle_tree_create_final(mt, gTree, &actual, sizeof(actual))); 320 Digest expected; 321 ASSERT_OK(expected.Parse(digest, strlen(digest))); 322 ASSERT_TRUE(expected == actual, "Incorrect root digest"); 323 return true; 324} 325 326// See CreateFinalC above. 327bool CreateFinalCAll(void) { 328 BEGIN_TEST; 329 for (size_t i = 0; i < kNumCases; ++i) { 330 if (!CreateFinalC(kCases[i].data_len, kCases[i].digest)) { 331 unittest_printf_critical("CreateFinalCAll failed with " 332 "data length of %zu\n", 333 kCases[i].data_len); 334 } 335 } 336 END_TEST; 337} 338 339// Used by CreateCAll below. 340bool CreateC(size_t data_len, const char* digest) { 341 zx_status_t rc; 342 size_t tree_len = merkle_tree_get_tree_length(data_len); 343 uint8_t actual[Digest::kLength]; 344 ASSERT_OK(merkle_tree_create(gData, data_len, gTree, tree_len, &actual, 345 sizeof(actual))); 346 Digest expected; 347 ASSERT_OK(expected.Parse(digest, strlen(digest))); 348 ASSERT_TRUE(expected == actual, "Incorrect root digest"); 349 return true; 350} 351 352// See CreateC above. 353bool CreateCAll(void) { 354 BEGIN_TEST; 355 for (size_t i = 0; i < kNumCases; ++i) { 356 if (!CreateC(kCases[i].data_len, kCases[i].digest)) { 357 unittest_printf_critical( 358 "CreateCAll failed with data length of %zu\n", 359 kCases[i].data_len); 360 } 361 } 362 END_TEST; 363} 364 365bool CreateByteByByte(void) { 366 BEGIN_TEST_WITH_RC; 367 size_t tree_len = MerkleTree::GetTreeLength(kSmall); 368 MerkleTree merkleTree; 369 ASSERT_OK(merkleTree.CreateInit(kSmall, tree_len)); 370 for (uint64_t i = 0; i < kSmall; ++i) { 371 ASSERT_OK(merkleTree.CreateUpdate(gData + i, 1, gTree)); 372 } 373 Digest actual; 374 ASSERT_OK(merkleTree.CreateFinal(gTree, &actual)); 375 Digest expected; 376 ASSERT_OK(MerkleTree::Create(gData, kSmall, gTree, tree_len, &expected)); 377 ASSERT_TRUE(actual == expected, "Incorrect root digest"); 378 END_TEST; 379} 380 381bool CreateMissingData(void) { 382 BEGIN_TEST_WITH_RC; 383 size_t tree_len = MerkleTree::GetTreeLength(kSmall); 384 Digest digest; 385 ASSERT_ERR(ZX_ERR_INVALID_ARGS, 386 MerkleTree::Create(nullptr, kSmall, gTree, tree_len, &digest)); 387 END_TEST; 388} 389 390bool CreateMissingTree(void) { 391 BEGIN_TEST_WITH_RC; 392 Digest digest; 393 ASSERT_ERR(ZX_ERR_INVALID_ARGS, 394 MerkleTree::Create(gData, kSmall, nullptr, kNodeSize, &digest)); 395 END_TEST; 396} 397 398bool CreateTreeTooSmall(void) { 399 BEGIN_TEST_WITH_RC; 400 Digest digest; 401 ASSERT_ERR(ZX_ERR_BUFFER_TOO_SMALL, 402 MerkleTree::Create(gData, kSmall, nullptr, 0, &digest)); 403 ASSERT_ERR( 404 ZX_ERR_BUFFER_TOO_SMALL, 405 MerkleTree::Create(gData, kNodeSize * 257, gTree, kNodeSize, &digest)); 406 END_TEST; 407} 408 409// Used by VerifyAll below. 410bool Verify(size_t data_len) { 411 zx_status_t rc; 412 size_t tree_len = MerkleTree::GetTreeLength(data_len); 413 Digest digest; 414 ASSERT_OK(MerkleTree::Create(gData, data_len, gTree, tree_len, &digest)); 415 ASSERT_OK(MerkleTree::Verify(gData, data_len, gTree, tree_len, 0, data_len, 416 digest)); 417 return true; 418} 419 420// See Verify above. 421bool VerifyAll(void) { 422 BEGIN_TEST; 423 for (size_t i = 0; i < kNumCases; ++i) { 424 if (!Verify(kCases[i].data_len)) { 425 unittest_printf_critical( 426 "VerifyAll failed with data length of %zu\n", 427 kCases[i].data_len); 428 } 429 } 430 END_TEST; 431} 432 433// Used by VerifyCAll below. 434bool VerifyC(size_t data_len) { 435 zx_status_t rc; 436 size_t tree_len = merkle_tree_get_tree_length(data_len); 437 uint8_t digest[Digest::kLength]; 438 ASSERT_OK(merkle_tree_create(gData, data_len, gTree, tree_len, digest, 439 sizeof(digest))); 440 ASSERT_OK(merkle_tree_verify(gData, data_len, gTree, tree_len, 0, data_len, 441 digest, sizeof(digest))); 442 return true; 443} 444 445// See VerifyC above. 446bool VerifyCAll(void) { 447 BEGIN_TEST; 448 for (size_t i = 0; i < kNumCases; ++i) { 449 if (!VerifyC(kCases[i].data_len)) { 450 unittest_printf_critical( 451 "VerifyCAll failed with data length of %zu\n", 452 kCases[i].data_len); 453 } 454 } 455 END_TEST; 456} 457 458bool VerifyNodeByNode(void) { 459 BEGIN_TEST_WITH_RC; 460 size_t tree_len = MerkleTree::GetTreeLength(kSmall); 461 Digest digest; 462 ASSERT_OK(MerkleTree::Create(gData, kSmall, gTree, tree_len, &digest)); 463 for (uint64_t i = 0; i < kSmall; i += kNodeSize) { 464 ASSERT_OK(MerkleTree::Verify(gData, kSmall, gTree, tree_len, i, 465 kNodeSize, digest)); 466 } 467 END_TEST; 468} 469 470bool VerifyMissingData(void) { 471 BEGIN_TEST_WITH_RC; 472 size_t tree_len = MerkleTree::GetTreeLength(kSmall); 473 Digest digest; 474 ASSERT_OK(MerkleTree::Create(gData, kSmall, gTree, tree_len, &digest)); 475 ASSERT_ERR(ZX_ERR_INVALID_ARGS, 476 MerkleTree::Verify(nullptr, kSmall, gTree, tree_len, 0, kSmall, 477 digest)); 478 END_TEST; 479} 480 481bool VerifyMissingTree(void) { 482 BEGIN_TEST_WITH_RC; 483 size_t tree_len = MerkleTree::GetTreeLength(kSmall); 484 Digest digest; 485 ASSERT_OK(MerkleTree::Create(gData, kSmall, gTree, tree_len, &digest)); 486 ASSERT_ERR(ZX_ERR_INVALID_ARGS, 487 MerkleTree::Verify(gData, kNodeSize + 1, nullptr, tree_len, 0, 488 kNodeSize, digest)); 489 END_TEST; 490} 491 492bool VerifyUnalignedTreeLength(void) { 493 BEGIN_TEST_WITH_RC; 494 size_t tree_len = MerkleTree::GetTreeLength(kSmall); 495 Digest digest; 496 ASSERT_OK(MerkleTree::Create(gData, kSmall, gTree, tree_len, &digest)); 497 ASSERT_OK(MerkleTree::Verify(gData, kSmall, gTree, tree_len + 1, 0, kSmall, 498 digest)); 499 END_TEST; 500} 501 502bool VerifyUnalignedDataLength(void) { 503 BEGIN_TEST_WITH_RC; 504 size_t tree_len = MerkleTree::GetTreeLength(kSmall); 505 Digest digest; 506 ASSERT_OK(MerkleTree::Create(gData, kSmall, gTree, tree_len, &digest)); 507 ASSERT_OK(MerkleTree::Verify(gData, kSmall - 1, gTree, tree_len, 0, 508 kNodeSize, digest)); 509 END_TEST; 510} 511 512bool VerifyTreeTooSmall(void) { 513 BEGIN_TEST_WITH_RC; 514 size_t tree_len = MerkleTree::GetTreeLength(kSmall); 515 Digest digest; 516 ASSERT_OK(MerkleTree::Create(gData, kSmall, gTree, tree_len, &digest)); 517 tree_len = MerkleTree::GetTreeLength(kSmall); 518 ASSERT_ERR(ZX_ERR_BUFFER_TOO_SMALL, 519 MerkleTree::Verify(gData, kSmall, gTree, tree_len - 1, 0, kSmall, 520 digest)); 521 END_TEST; 522} 523 524bool VerifyUnalignedOffset(void) { 525 BEGIN_TEST_WITH_RC; 526 size_t tree_len = MerkleTree::GetTreeLength(kSmall); 527 Digest digest; 528 ASSERT_OK(MerkleTree::Create(gData, kSmall, gTree, tree_len, &digest)); 529 ASSERT_OK(MerkleTree::Verify(gData, kSmall, gTree, tree_len, kNodeSize - 1, 530 kNodeSize, digest)); 531 END_TEST; 532} 533 534bool VerifyUnalignedLength(void) { 535 BEGIN_TEST_WITH_RC; 536 size_t tree_len = MerkleTree::GetTreeLength(kSmall); 537 Digest digest; 538 ASSERT_OK(MerkleTree::Create(gData, kSmall, gTree, tree_len, &digest)); 539 ASSERT_OK(MerkleTree::Verify(gData, kSmall, gTree, tree_len, 0, kSmall - 1, 540 digest)); 541 END_TEST; 542} 543 544bool VerifyOutOfBounds(void) { 545 BEGIN_TEST_WITH_RC; 546 size_t tree_len = MerkleTree::GetTreeLength(kSmall); 547 Digest digest; 548 ASSERT_OK(MerkleTree::Create(gData, kSmall, gTree, tree_len, &digest)); 549 ASSERT_ERR(ZX_ERR_OUT_OF_RANGE, 550 MerkleTree::Verify(gData, kSmall, gTree, tree_len, 551 kSmall - kNodeSize, kNodeSize * 2, digest)); 552 END_TEST; 553} 554 555bool VerifyZeroLength(void) { 556 BEGIN_TEST_WITH_RC; 557 size_t tree_len = MerkleTree::GetTreeLength(kSmall); 558 Digest digest; 559 ASSERT_OK(MerkleTree::Create(gData, kSmall, gTree, tree_len, &digest)); 560 ASSERT_OK(MerkleTree::Verify(gData, kSmall, gTree, tree_len, 0, 0, digest)); 561 END_TEST; 562} 563 564bool VerifyBadRoot(void) { 565 BEGIN_TEST_WITH_RC; 566 size_t tree_len = MerkleTree::GetTreeLength(kLarge); 567 Digest digest; 568 ASSERT_OK(MerkleTree::Create(gData, kLarge, gTree, tree_len, &digest)); 569 // Modify digest 570 char str[(Digest::kLength * 2) + 1]; 571 ASSERT_OK(digest.ToString(str, sizeof(str))); 572 str[0] = (str[0] == '0' ? '1' : '0'); 573 rc = digest.Parse(str, strlen(str)); 574 ASSERT_EQ(rc, ZX_OK, zx_status_get_string(rc)); 575 // Verify 576 ASSERT_ERR( 577 ZX_ERR_IO_DATA_INTEGRITY, 578 MerkleTree::Verify(gData, kLarge, gTree, tree_len, 0, kLarge, digest)); 579 END_TEST; 580} 581 582// TODO 583bool VerifyGoodPartOfBadTree(void) { 584 BEGIN_TEST_WITH_RC; 585 size_t tree_len = MerkleTree::GetTreeLength(kLarge); 586 Digest digest; 587 ASSERT_OK(MerkleTree::Create(gData, kLarge, gTree, tree_len, &digest)); 588 gTree[0] ^= 1; 589 ASSERT_OK(MerkleTree::Verify(gData, kLarge, gTree, tree_len, 590 kLarge - kNodeSize, kNodeSize, digest)); 591 END_TEST; 592} 593 594bool VerifyBadTree(void) { 595 BEGIN_TEST_WITH_RC; 596 size_t tree_len = MerkleTree::GetTreeLength(kLarge); 597 Digest digest; 598 ASSERT_OK(MerkleTree::Create(gData, kLarge, gTree, tree_len, &digest)); 599 gTree[0] ^= 1; 600 ASSERT_ERR( 601 ZX_ERR_IO_DATA_INTEGRITY, 602 MerkleTree::Verify(gData, kLarge, gTree, tree_len, 0, 1, digest)); 603 END_TEST; 604} 605 606bool VerifyGoodPartOfBadLeaves(void) { 607 BEGIN_TEST_WITH_RC; 608 size_t tree_len = MerkleTree::GetTreeLength(kSmall); 609 Digest digest; 610 ASSERT_OK(MerkleTree::Create(gData, kSmall, gTree, tree_len, &digest)); 611 gData[0] ^= 1; 612 ASSERT_OK(MerkleTree::Verify(gData, kSmall, gTree, tree_len, kNodeSize, 613 kSmall - kNodeSize, digest)); 614 END_TEST; 615} 616 617bool VerifyBadLeaves(void) { 618 BEGIN_TEST_WITH_RC; 619 size_t tree_len = MerkleTree::GetTreeLength(kSmall); 620 Digest digest; 621 ASSERT_OK(MerkleTree::Create(gData, kSmall, gTree, tree_len, &digest)); 622 gData[0] ^= 1; 623 ASSERT_ERR( 624 ZX_ERR_IO_DATA_INTEGRITY, 625 MerkleTree::Verify(gData, kSmall, gTree, tree_len, 0, kSmall, digest)); 626 END_TEST; 627} 628 629bool CreateAndVerifyHugePRNGData(void) { 630 BEGIN_TEST_WITH_RC; 631 Digest digest; 632 uint8_t buffer[Digest::kLength]; 633 for (size_t data_len = kNodeSize; data_len <= sizeof(gData); 634 data_len <<= 1) { 635 // Generate random data 636 for (uint64_t i = 0; i < data_len; ++i) { 637 gData[i] = static_cast<uint8_t>(rand()); 638 } 639 // Create the Merkle tree 640 size_t tree_len = MerkleTree::GetTreeLength(data_len); 641 ASSERT_OK( 642 MerkleTree::Create(gData, data_len, gTree, tree_len, &digest)); 643 // Randomly pick one of the four cases below. 644 uint64_t n = (rand() % 16) + 1; 645 switch (rand() % 4) { 646 case 1: 647 ASSERT_OK(digest.CopyTo(buffer, sizeof(buffer))); 648 // Flip bits in root digest 649 for (uint64_t i = 0; i < n; ++i) { 650 uint8_t tmp = static_cast<uint8_t>(rand()) % 8; 651 buffer[rand() % Digest::kLength] ^= 652 static_cast<uint8_t>(1 << tmp); 653 } 654 digest = buffer; 655 ASSERT_ERR(ZX_ERR_IO_DATA_INTEGRITY, 656 MerkleTree::Verify(gData, data_len, gTree, tree_len, 0, 657 data_len, digest)); 658 break; 659 case 2: 660 // Flip bit in data 661 for (uint64_t i = 0; i < n; ++i) { 662 uint8_t tmp = static_cast<uint8_t>(rand()) % 8; 663 gData[rand() % data_len] ^= static_cast<uint8_t>(1 << tmp); 664 } 665 ASSERT_ERR(ZX_ERR_IO_DATA_INTEGRITY, 666 MerkleTree::Verify(gData, data_len, gTree, tree_len, 0, 667 data_len, digest)); 668 break; 669 case 3: 670 // Flip bit in tree (if large enough to have a tree) 671 for (uint64_t i = 0; i < n && tree_len > 0; ++i) { 672 uint8_t tmp = static_cast<uint8_t>(rand()) % 8; 673 gTree[rand() % tree_len] ^= static_cast<uint8_t>(1 << tmp); 674 } 675 rc = MerkleTree::Verify(gData, data_len, gTree, tree_len, 0, 676 data_len, digest); 677 678 if (tree_len <= kNodeSize) { 679 ASSERT_EQ(rc, ZX_OK, zx_status_get_string(rc)); 680 } else { 681 ASSERT_EQ(rc, ZX_ERR_IO_DATA_INTEGRITY, 682 zx_status_get_string(rc)); 683 } 684 break; 685 default: 686 // Normal verification without modification 687 ASSERT_OK(MerkleTree::Verify(gData, data_len, gTree, tree_len, 0, 688 data_len, digest)); 689 break; 690 } 691 } 692 END_TEST; 693} 694 695} // namespace 696 697BEGIN_TEST_CASE(MerkleTreeTests) 698// Do this global setup once 699memset(gData, 0xff, sizeof(gData)); 700RUN_TEST(GetTreeLength) 701RUN_TEST(CreateInit) 702RUN_TEST(CreateInitWithoutData) 703RUN_TEST(CreateInitWithoutTree) 704RUN_TEST(CreateInitTreeTooSmall) 705RUN_TEST(CreateUpdate) 706RUN_TEST(CreateUpdateMissingInit) 707RUN_TEST(CreateUpdateMissingData) 708RUN_TEST(CreateUpdateMissingTree) 709RUN_TEST(CreateUpdateWithoutData) 710RUN_TEST(CreateUpdateWithoutTree) 711RUN_TEST(CreateUpdateTooMuchData) 712RUN_TEST(CreateFinalMissingInit) 713RUN_TEST(CreateFinalAll) 714RUN_TEST(CreateFinalWithoutData) 715RUN_TEST(CreateFinalWithoutTree) 716RUN_TEST(CreateFinalMissingDigest) 717RUN_TEST(CreateFinalIncompleteData) 718RUN_TEST(CreateAll) 719RUN_TEST(CreateFinalCAll) 720RUN_TEST(CreateCAll) 721RUN_TEST(CreateByteByByte) 722RUN_TEST(CreateMissingData) 723RUN_TEST(CreateMissingTree) 724RUN_TEST(CreateTreeTooSmall) 725RUN_TEST(VerifyAll) 726RUN_TEST(VerifyCAll) 727RUN_TEST(VerifyNodeByNode) 728RUN_TEST(VerifyMissingData) 729RUN_TEST(VerifyMissingTree) 730RUN_TEST(VerifyUnalignedTreeLength) 731RUN_TEST(VerifyUnalignedDataLength) 732RUN_TEST(VerifyTreeTooSmall) 733RUN_TEST(VerifyUnalignedOffset) 734RUN_TEST(VerifyUnalignedLength) 735RUN_TEST(VerifyOutOfBounds) 736RUN_TEST(VerifyZeroLength) 737RUN_TEST(VerifyBadRoot) 738RUN_TEST(VerifyGoodPartOfBadTree) 739RUN_TEST(VerifyBadTree) 740RUN_TEST(VerifyGoodPartOfBadLeaves) 741RUN_TEST(VerifyBadLeaves) 742RUN_TEST(CreateAndVerifyHugePRNGData) 743END_TEST_CASE(MerkleTreeTests) 744