summaryrefslogtreecommitdiffhomepage
path: root/pkg/merkletree
diff options
context:
space:
mode:
Diffstat (limited to 'pkg/merkletree')
-rw-r--r--pkg/merkletree/BUILD23
-rw-r--r--pkg/merkletree/merkletree.go533
-rw-r--r--pkg/merkletree/merkletree_test.go1160
3 files changed, 0 insertions, 1716 deletions
diff --git a/pkg/merkletree/BUILD b/pkg/merkletree/BUILD
deleted file mode 100644
index 501a9ef21..000000000
--- a/pkg/merkletree/BUILD
+++ /dev/null
@@ -1,23 +0,0 @@
-load("//tools:defs.bzl", "go_library", "go_test")
-
-package(licenses = ["notice"])
-
-go_library(
- name = "merkletree",
- srcs = ["merkletree.go"],
- visibility = ["//pkg/sentry:internal"],
- deps = [
- "//pkg/abi/linux",
- "//pkg/usermem",
- ],
-)
-
-go_test(
- name = "merkletree_test",
- srcs = ["merkletree_test.go"],
- library = ":merkletree",
- deps = [
- "//pkg/abi/linux",
- "//pkg/usermem",
- ],
-)
diff --git a/pkg/merkletree/merkletree.go b/pkg/merkletree/merkletree.go
deleted file mode 100644
index d7209ace3..000000000
--- a/pkg/merkletree/merkletree.go
+++ /dev/null
@@ -1,533 +0,0 @@
-// Copyright 2020 The gVisor Authors.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-// Package merkletree implements Merkle tree generating and verification.
-package merkletree
-
-import (
- "bytes"
- "crypto/sha256"
- "crypto/sha512"
- "encoding/gob"
- "fmt"
- "io"
-
- "gvisor.dev/gvisor/pkg/abi/linux"
- "gvisor.dev/gvisor/pkg/usermem"
-)
-
-const (
- // sha256DigestSize specifies the digest size of a SHA256 hash.
- sha256DigestSize = 32
- // sha512DigestSize specifies the digest size of a SHA512 hash.
- sha512DigestSize = 64
-)
-
-// DigestSize returns the size (in bytes) of a digest.
-// TODO(b/156980949): Allow config SHA384.
-func DigestSize(hashAlgorithm int) int {
- switch hashAlgorithm {
- case linux.FS_VERITY_HASH_ALG_SHA256:
- return sha256DigestSize
- case linux.FS_VERITY_HASH_ALG_SHA512:
- return sha512DigestSize
- default:
- return -1
- }
-}
-
-// Layout defines the scale of a Merkle tree.
-type Layout struct {
- // blockSize is the size of a data block to be hashed.
- blockSize int64
- // digestSize is the size of a generated hash.
- digestSize int64
- // levelOffset contains the offset of the beginning of each level in
- // bytes. The number of levels in the tree is the length of the slice.
- // The leaf nodes (level 0) contain hashes of blocks of the input data.
- // Each level N contains hashes of the blocks in level N-1. The highest
- // level is the root hash.
- levelOffset []int64
-}
-
-// InitLayout initializes and returns a new Layout object describing the structure
-// of a tree. dataSize specifies the size of input data in bytes.
-func InitLayout(dataSize int64, hashAlgorithms int, dataAndTreeInSameFile bool) (Layout, error) {
- layout := Layout{
- blockSize: usermem.PageSize,
- }
-
- // TODO(b/156980949): Allow config SHA384.
- switch hashAlgorithms {
- case linux.FS_VERITY_HASH_ALG_SHA256:
- layout.digestSize = sha256DigestSize
- case linux.FS_VERITY_HASH_ALG_SHA512:
- layout.digestSize = sha512DigestSize
- default:
- return Layout{}, fmt.Errorf("unexpected hash algorithms")
- }
-
- // treeStart is the offset (in bytes) of the first level of the tree in
- // the file. If data and tree are in different files, treeStart should
- // be zero. If data is in the same file as the tree, treeStart points
- // to the block after the last data block (which may be zero-padded).
- var treeStart int64
- if dataAndTreeInSameFile {
- treeStart = dataSize
- if dataSize%layout.blockSize != 0 {
- treeStart += layout.blockSize - dataSize%layout.blockSize
- }
- }
-
- numBlocks := (dataSize + layout.blockSize - 1) / layout.blockSize
- level := 0
- offset := int64(0)
-
- // Calculate the number of levels in the Merkle tree and the beginning
- // offset of each level. Level 0 consists of the leaf nodes that
- // contain the hashes of the data blocks, while level numLevels - 1 is
- // the root.
- for numBlocks > 1 {
- layout.levelOffset = append(layout.levelOffset, treeStart+offset*layout.blockSize)
- // Round numBlocks up to fill up a block.
- numBlocks += (layout.hashesPerBlock() - numBlocks%layout.hashesPerBlock()) % layout.hashesPerBlock()
- offset += numBlocks / layout.hashesPerBlock()
- numBlocks = numBlocks / layout.hashesPerBlock()
- level++
- }
- layout.levelOffset = append(layout.levelOffset, treeStart+offset*layout.blockSize)
-
- return layout, nil
-}
-
-// hashesPerBlock() returns the number of digests in each block. For example,
-// if blockSize is 4096 bytes, and digestSize is 32 bytes, there will be 128
-// hashesPerBlock. Therefore 128 hashes in one level will be combined in one
-// hash in the level above.
-func (layout Layout) hashesPerBlock() int64 {
- return layout.blockSize / layout.digestSize
-}
-
-// numLevels returns the total number of levels in the Merkle tree.
-func (layout Layout) numLevels() int {
- return len(layout.levelOffset)
-}
-
-// rootLevel returns the level of the root hash.
-func (layout Layout) rootLevel() int {
- return layout.numLevels() - 1
-}
-
-// digestOffset finds the offset of a digest from the beginning of the tree.
-// The target digest is at level of the tree, with index from the beginning of
-// the current level.
-func (layout Layout) digestOffset(level int, index int64) int64 {
- return layout.levelOffset[level] + index*layout.digestSize
-}
-
-// blockOffset finds the offset of a block from the beginning of the tree. The
-// target block is at level of the tree, with index from the beginning of the
-// current level.
-func (layout Layout) blockOffset(level int, index int64) int64 {
- return layout.levelOffset[level] + index*layout.blockSize
-}
-
-// VerityDescriptor is a struct that is serialized and hashed to get a file's
-// root hash, which contains the root hash of the raw content and the file's
-// meatadata.
-type VerityDescriptor struct {
- Name string
- FileSize int64
- Mode uint32
- UID uint32
- GID uint32
- Children map[string]struct{}
- SymlinkTarget string
- RootHash []byte
-}
-
-func (d *VerityDescriptor) String() string {
- b := new(bytes.Buffer)
- e := gob.NewEncoder(b)
- e.Encode(d.Children)
- return fmt.Sprintf("Name: %s, Size: %d, Mode: %d, UID: %d, GID: %d, Children: %v, Symlink: %s, RootHash: %v", d.Name, d.FileSize, d.Mode, d.UID, d.GID, b.Bytes(), d.SymlinkTarget, d.RootHash)
-}
-
-// verify generates a hash from d, and compares it with expected.
-func (d *VerityDescriptor) verify(expected []byte, hashAlgorithms int) error {
- h, err := hashData([]byte(d.String()), hashAlgorithms)
- if err != nil {
- return err
- }
- if !bytes.Equal(h[:], expected) {
- return fmt.Errorf("unexpected root hash")
- }
- return nil
-
-}
-
-// hashData hashes data and returns the result hash based on the hash
-// algorithms.
-func hashData(data []byte, hashAlgorithms int) ([]byte, error) {
- var digest []byte
- switch hashAlgorithms {
- case linux.FS_VERITY_HASH_ALG_SHA256:
- digestArray := sha256.Sum256(data)
- digest = digestArray[:]
- case linux.FS_VERITY_HASH_ALG_SHA512:
- digestArray := sha512.Sum512(data)
- digest = digestArray[:]
- default:
- return nil, fmt.Errorf("unexpected hash algorithms")
- }
- return digest, nil
-}
-
-// GenerateParams contains the parameters used to generate a Merkle tree for a
-// given file.
-type GenerateParams struct {
- // File is a reader of the file to be hashed.
- File io.ReaderAt
- // Size is the size of the file.
- Size int64
- // Name is the name of the target file.
- Name string
- // Mode is the mode of the target file.
- Mode uint32
- // UID is the user ID of the target file.
- UID uint32
- // GID is the group ID of the target file.
- GID uint32
- // Children is a map of children names for a directory. It should be
- // empty for a regular file.
- Children map[string]struct{}
- // SymlinkTarget is the target path of a symlink file, or "" if the file is not a symlink.
- SymlinkTarget string
- // HashAlgorithms is the algorithms used to hash data.
- HashAlgorithms int
- // TreeReader is a reader for the Merkle tree.
- TreeReader io.ReaderAt
- // TreeWriter is a writer for the Merkle tree.
- TreeWriter io.Writer
- // DataAndTreeInSameFile is true if data and Merkle tree are in the same
- // file, or false if Merkle tree is a separate file from data.
- DataAndTreeInSameFile bool
-}
-
-// Generate constructs a Merkle tree for the contents of params.File. The
-// output is written to params.TreeWriter.
-//
-// Generate returns a hash of a VerityDescriptor, which contains the file
-// metadata and the hash from file content.
-func Generate(params *GenerateParams) ([]byte, error) {
- descriptor := VerityDescriptor{
- FileSize: params.Size,
- Name: params.Name,
- Mode: params.Mode,
- UID: params.UID,
- GID: params.GID,
- SymlinkTarget: params.SymlinkTarget,
- }
-
- // If file is a symlink do not generate root hash for file content.
- if params.SymlinkTarget != "" {
- return hashData([]byte(descriptor.String()), params.HashAlgorithms)
- }
-
- layout, err := InitLayout(params.Size, params.HashAlgorithms, params.DataAndTreeInSameFile)
- if err != nil {
- return nil, err
- }
-
- numBlocks := (params.Size + layout.blockSize - 1) / layout.blockSize
-
- // If the data is in the same file as the tree, zero pad the last data
- // block.
- bytesInLastBlock := params.Size % layout.blockSize
- if params.DataAndTreeInSameFile && bytesInLastBlock != 0 {
- zeroBuf := make([]byte, layout.blockSize-bytesInLastBlock)
- if _, err := params.TreeWriter.Write(zeroBuf); err != nil {
- return nil, err
- }
- }
-
- var root []byte
- for level := 0; level < layout.numLevels(); level++ {
- for i := int64(0); i < numBlocks; i++ {
- buf := make([]byte, layout.blockSize)
- var (
- n int
- err error
- )
- if level == 0 {
- // Read data block from the target file since level 0 includes hashes
- // of blocks in the input data.
- n, err = params.File.ReadAt(buf, i*layout.blockSize)
- } else {
- // Read data block from the tree file since levels higher than 0 are
- // hashing the lower level hashes.
- n, err = params.TreeReader.ReadAt(buf, layout.blockOffset(level-1, i))
- }
-
- // err is populated as long as the bytes read is smaller than the buffer
- // size. This could be the case if we are reading the last block, and
- // break in that case. If this is the last block, the end of the block
- // will be zero-padded.
- if n == 0 && err == io.EOF {
- break
- } else if err != nil && err != io.EOF {
- return nil, err
- }
- // Hash the bytes in buf.
- digest, err := hashData(buf, params.HashAlgorithms)
- if err != nil {
- return nil, err
- }
-
- if level == layout.rootLevel() {
- root = digest
- }
-
- // Write the generated hash to the end of the tree file.
- if _, err = params.TreeWriter.Write(digest[:]); err != nil {
- return nil, err
- }
- }
- // If the generated digests do not round up to a block, zero-padding the
- // remaining of the last block. But no need to do so for root.
- if level != layout.rootLevel() && numBlocks%layout.hashesPerBlock() != 0 {
- zeroBuf := make([]byte, layout.blockSize-(numBlocks%layout.hashesPerBlock())*layout.digestSize)
- if _, err := params.TreeWriter.Write(zeroBuf[:]); err != nil {
- return nil, err
- }
- }
- numBlocks = (numBlocks + layout.hashesPerBlock() - 1) / layout.hashesPerBlock()
- }
- descriptor.RootHash = root
- return hashData([]byte(descriptor.String()), params.HashAlgorithms)
-}
-
-// VerifyParams contains the params used to verify a portion of a file against
-// a Merkle tree.
-type VerifyParams struct {
- // Out will be filled with verified data.
- Out io.Writer
- // File is a handler on the file to be verified.
- File io.ReaderAt
- // tree is a handler on the Merkle tree used to verify file.
- Tree io.ReaderAt
- // Size is the size of the file.
- Size int64
- // Name is the name of the target file.
- Name string
- // Mode is the mode of the target file.
- Mode uint32
- // UID is the user ID of the target file.
- UID uint32
- // GID is the group ID of the target file.
- GID uint32
- // Children is a map of children names for a directory. It should be
- // empty for a regular file.
- Children map[string]struct{}
- // SymlinkTarget is the target path of a symlink file, or "" if the file is not a symlink.
- SymlinkTarget string
- // HashAlgorithms is the algorithms used to hash data.
- HashAlgorithms int
- // ReadOffset is the offset of the data range to be verified.
- ReadOffset int64
- // ReadSize is the size of the data range to be verified.
- ReadSize int64
- // Expected is a trusted hash for the file. It is compared with the
- // calculated root hash to verify the content.
- Expected []byte
- // DataAndTreeInSameFile is true if data and Merkle tree are in the same
- // file, or false if Merkle tree is a separate file from data.
- DataAndTreeInSameFile bool
-}
-
-// verifyMetadata verifies the metadata by hashing a descriptor that contains
-// the metadata and compare the generated hash with expected.
-//
-// For verifyMetadata, params.data is not needed. It only accesses params.tree
-// for the raw root hash.
-func verifyMetadata(params *VerifyParams, layout *Layout) error {
- var root []byte
- // Only read the root hash if we expect that the file is not a symlink and its
- // Merkle tree file is non-empty.
- if params.Size != 0 && params.SymlinkTarget == "" {
- root = make([]byte, layout.digestSize)
- if _, err := params.Tree.ReadAt(root, layout.blockOffset(layout.rootLevel(), 0 /* index */)); err != nil {
- return fmt.Errorf("failed to read root hash: %w", err)
- }
- }
- descriptor := VerityDescriptor{
- Name: params.Name,
- FileSize: params.Size,
- Mode: params.Mode,
- UID: params.UID,
- GID: params.GID,
- Children: params.Children,
- SymlinkTarget: params.SymlinkTarget,
- RootHash: root,
- }
- return descriptor.verify(params.Expected, params.HashAlgorithms)
-}
-
-// Verify verifies the content read from data with offset. The content is
-// verified against tree. If content spans across multiple blocks, each block is
-// verified. Verification fails if the hash of the data does not match the tree
-// at any level, or if the final root hash does not match expected.
-// Once the data is verified, it will be written using params.Out.
-//
-// Verify checks for both target file content and metadata. If readSize is 0,
-// only metadata is checked.
-func Verify(params *VerifyParams) (int64, error) {
- if params.ReadSize < 0 {
- return 0, fmt.Errorf("unexpected read size: %d", params.ReadSize)
- }
- layout, err := InitLayout(int64(params.Size), params.HashAlgorithms, params.DataAndTreeInSameFile)
- if err != nil {
- return 0, err
- }
- if params.ReadSize == 0 {
- return 0, verifyMetadata(params, &layout)
- }
-
- // Calculate the index of blocks that includes the target range in input
- // data.
- firstDataBlock := params.ReadOffset / layout.blockSize
- lastDataBlock := (params.ReadOffset + params.ReadSize - 1) / layout.blockSize
-
- buf := make([]byte, layout.blockSize)
- var readErr error
- total := int64(0)
- for i := firstDataBlock; i <= lastDataBlock; i++ {
- // Read a block that includes all or part of target range in
- // input data.
- bytesRead, err := params.File.ReadAt(buf, i*layout.blockSize)
- readErr = err
- // If at the end of input data and all previous blocks are
- // verified, return the verified input data and EOF.
- if readErr == io.EOF && bytesRead == 0 {
- break
- }
- if readErr != nil && readErr != io.EOF {
- return 0, fmt.Errorf("read from data failed: %w", err)
- }
- // If this is the end of file, zero the remaining bytes in buf,
- // otherwise they are still from the previous block.
- // TODO(b/162908070): Investigate possible issues with zero
- // padding the data.
- if bytesRead < len(buf) {
- for j := bytesRead; j < len(buf); j++ {
- buf[j] = 0
- }
- }
- descriptor := VerityDescriptor{
- Name: params.Name,
- FileSize: params.Size,
- Mode: params.Mode,
- UID: params.UID,
- GID: params.GID,
- SymlinkTarget: params.SymlinkTarget,
- Children: params.Children,
- }
- if err := verifyBlock(params.Tree, &descriptor, &layout, buf, i, params.HashAlgorithms, params.Expected); err != nil {
- return 0, err
- }
-
- // startOff is the beginning of the read range within the
- // current data block. Note that for all blocks other than the
- // first, startOff should be 0.
- startOff := int64(0)
- if i == firstDataBlock {
- startOff = params.ReadOffset % layout.blockSize
- }
- // endOff is the end of the read range within the current data
- // block. Note that for all blocks other than the last, endOff
- // should be the block size.
- endOff := layout.blockSize
- if i == lastDataBlock {
- endOff = (params.ReadOffset+params.ReadSize-1)%layout.blockSize + 1
- }
- // If the provided size exceeds the end of input data, we should
- // only copy the parts in buf that's part of input data.
- if startOff > int64(bytesRead) {
- startOff = int64(bytesRead)
- }
- if endOff > int64(bytesRead) {
- endOff = int64(bytesRead)
- }
- n, err := params.Out.Write(buf[startOff:endOff])
- if err != nil {
- return total, err
- }
- total += int64(n)
-
- }
- return total, readErr
-}
-
-// verifyBlock verifies a block against tree. index is the number of block in
-// original data. The block is verified through each level of the tree. It
-// fails if the calculated hash from block is different from any level of
-// hashes stored in tree. And the final root hash is compared with
-// expected.
-func verifyBlock(tree io.ReaderAt, descriptor *VerityDescriptor, layout *Layout, dataBlock []byte, blockIndex int64, hashAlgorithms int, expected []byte) error {
- if len(dataBlock) != int(layout.blockSize) {
- return fmt.Errorf("incorrect block size")
- }
-
- expectedDigest := make([]byte, layout.digestSize)
- treeBlock := make([]byte, layout.blockSize)
- var digest []byte
- for level := 0; level < layout.numLevels(); level++ {
- // Calculate hash.
- if level == 0 {
- h, err := hashData(dataBlock, hashAlgorithms)
- if err != nil {
- return err
- }
- digest = h
- } else {
- // Read a block in previous level that contains the
- // hash we just generated, and generate a next level
- // hash from it.
- if _, err := tree.ReadAt(treeBlock, layout.blockOffset(level-1, blockIndex)); err != nil {
- return err
- }
- h, err := hashData(treeBlock, hashAlgorithms)
- if err != nil {
- return err
- }
- digest = h
- }
-
- // Read the digest for the current block and store in
- // expectedDigest.
- if _, err := tree.ReadAt(expectedDigest, layout.digestOffset(level, blockIndex)); err != nil {
- return err
- }
-
- if !bytes.Equal(digest, expectedDigest) {
- return fmt.Errorf("verification failed")
- }
- blockIndex = blockIndex / layout.hashesPerBlock()
- }
-
- // Verification for the tree succeeded. Now hash the descriptor with
- // the root hash and compare it with expected.
- descriptor.RootHash = digest
- return descriptor.verify(expected, hashAlgorithms)
-}
diff --git a/pkg/merkletree/merkletree_test.go b/pkg/merkletree/merkletree_test.go
deleted file mode 100644
index e3a88b3a3..000000000
--- a/pkg/merkletree/merkletree_test.go
+++ /dev/null
@@ -1,1160 +0,0 @@
-// Copyright 2020 The gVisor Authors.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-package merkletree
-
-import (
- "bytes"
- "errors"
- "fmt"
- "io"
- "math/rand"
- "testing"
- "time"
-
- "gvisor.dev/gvisor/pkg/abi/linux"
- "gvisor.dev/gvisor/pkg/usermem"
-)
-
-func TestLayout(t *testing.T) {
- testCases := []struct {
- name string
- dataSize int64
- hashAlgorithms int
- dataAndTreeInSameFile bool
- expectedDigestSize int64
- expectedLevelOffset []int64
- }{
- {
- name: "SmallSizeSHA256SeparateFile",
- dataSize: 100,
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- expectedDigestSize: 32,
- expectedLevelOffset: []int64{0},
- },
- {
- name: "SmallSizeSHA512SeparateFile",
- dataSize: 100,
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- expectedDigestSize: 64,
- expectedLevelOffset: []int64{0},
- },
- {
- name: "SmallSizeSHA256SameFile",
- dataSize: 100,
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- expectedDigestSize: 32,
- expectedLevelOffset: []int64{usermem.PageSize},
- },
- {
- name: "SmallSizeSHA512SameFile",
- dataSize: 100,
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- expectedDigestSize: 64,
- expectedLevelOffset: []int64{usermem.PageSize},
- },
- {
- name: "MiddleSizeSHA256SeparateFile",
- dataSize: 1000000,
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- expectedDigestSize: 32,
- expectedLevelOffset: []int64{0, 2 * usermem.PageSize, 3 * usermem.PageSize},
- },
- {
- name: "MiddleSizeSHA512SeparateFile",
- dataSize: 1000000,
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- expectedDigestSize: 64,
- expectedLevelOffset: []int64{0, 4 * usermem.PageSize, 5 * usermem.PageSize},
- },
- {
- name: "MiddleSizeSHA256SameFile",
- dataSize: 1000000,
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- expectedDigestSize: 32,
- expectedLevelOffset: []int64{245 * usermem.PageSize, 247 * usermem.PageSize, 248 * usermem.PageSize},
- },
- {
- name: "MiddleSizeSHA512SameFile",
- dataSize: 1000000,
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- expectedDigestSize: 64,
- expectedLevelOffset: []int64{245 * usermem.PageSize, 249 * usermem.PageSize, 250 * usermem.PageSize},
- },
- {
- name: "LargeSizeSHA256SeparateFile",
- dataSize: 4096 * int64(usermem.PageSize),
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- expectedDigestSize: 32,
- expectedLevelOffset: []int64{0, 32 * usermem.PageSize, 33 * usermem.PageSize},
- },
- {
- name: "LargeSizeSHA512SeparateFile",
- dataSize: 4096 * int64(usermem.PageSize),
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- expectedDigestSize: 64,
- expectedLevelOffset: []int64{0, 64 * usermem.PageSize, 65 * usermem.PageSize},
- },
- {
- name: "LargeSizeSHA256SameFile",
- dataSize: 4096 * int64(usermem.PageSize),
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- expectedDigestSize: 32,
- expectedLevelOffset: []int64{4096 * usermem.PageSize, 4128 * usermem.PageSize, 4129 * usermem.PageSize},
- },
- {
- name: "LargeSizeSHA512SameFile",
- dataSize: 4096 * int64(usermem.PageSize),
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- expectedDigestSize: 64,
- expectedLevelOffset: []int64{4096 * usermem.PageSize, 4160 * usermem.PageSize, 4161 * usermem.PageSize},
- },
- }
-
- for _, tc := range testCases {
- t.Run(tc.name, func(t *testing.T) {
- l, err := InitLayout(tc.dataSize, tc.hashAlgorithms, tc.dataAndTreeInSameFile)
- if err != nil {
- t.Fatalf("Failed to InitLayout: %v", err)
- }
- if l.blockSize != int64(usermem.PageSize) {
- t.Errorf("Got blockSize %d, want %d", l.blockSize, usermem.PageSize)
- }
- if l.digestSize != tc.expectedDigestSize {
- t.Errorf("Got digestSize %d, want %d", l.digestSize, sha256DigestSize)
- }
- if l.numLevels() != len(tc.expectedLevelOffset) {
- t.Errorf("Got levels %d, want %d", l.numLevels(), len(tc.expectedLevelOffset))
- }
- for i := 0; i < l.numLevels() && i < len(tc.expectedLevelOffset); i++ {
- if l.levelOffset[i] != tc.expectedLevelOffset[i] {
- t.Errorf("Got levelStart[%d] %d, want %d", i, l.levelOffset[i], tc.expectedLevelOffset[i])
- }
- }
- })
- }
-}
-
-const (
- defaultName = "merkle_test"
- defaultMode = 0644
- defaultUID = 0
- defaultGID = 0
- defaultSymlinkPath = "merkle_test_link"
-)
-
-// bytesReadWriter is used to read from/write to/seek in a byte array. Unlike
-// bytes.Buffer, it keeps the whole buffer during read so that it can be reused.
-type bytesReadWriter struct {
- // bytes contains the underlying byte array.
- bytes []byte
- // readPos is the currently location for Read. Write always appends to
- // the end of the array.
- readPos int
-}
-
-func (brw *bytesReadWriter) Write(p []byte) (int, error) {
- brw.bytes = append(brw.bytes, p...)
- return len(p), nil
-}
-
-func (brw *bytesReadWriter) ReadAt(p []byte, off int64) (int, error) {
- bytesRead := copy(p, brw.bytes[off:])
- if bytesRead == 0 {
- return bytesRead, io.EOF
- }
- return bytesRead, nil
-}
-
-func TestGenerate(t *testing.T) {
- // The input data has size dataSize. It starts with the data in startWith,
- // and all other bytes are zeroes.
- testCases := []struct {
- name string
- data []byte
- hashAlgorithms int
- dataAndTreeInSameFile bool
- expectedHash []byte
- }{
- {
- name: "OnePageZeroesSHA256SeparateFile",
- data: bytes.Repeat([]byte{0}, usermem.PageSize),
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- expectedHash: []byte{9, 115, 238, 230, 38, 140, 195, 70, 207, 144, 202, 118, 23, 113, 32, 129, 226, 239, 177, 69, 161, 26, 14, 113, 16, 37, 30, 96, 19, 148, 132, 27},
- },
- {
- name: "OnePageZeroesSHA256SameFile",
- data: bytes.Repeat([]byte{0}, usermem.PageSize),
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- expectedHash: []byte{9, 115, 238, 230, 38, 140, 195, 70, 207, 144, 202, 118, 23, 113, 32, 129, 226, 239, 177, 69, 161, 26, 14, 113, 16, 37, 30, 96, 19, 148, 132, 27},
- },
- {
- name: "OnePageZeroesSHA512SeparateFile",
- data: bytes.Repeat([]byte{0}, usermem.PageSize),
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- expectedHash: []byte{127, 8, 95, 11, 83, 101, 51, 39, 170, 235, 39, 43, 135, 243, 145, 118, 148, 58, 27, 155, 182, 205, 44, 47, 5, 223, 215, 17, 35, 16, 43, 104, 43, 11, 8, 88, 171, 7, 249, 243, 14, 62, 126, 218, 23, 159, 237, 237, 42, 226, 39, 25, 87, 48, 253, 191, 116, 213, 37, 3, 187, 152, 154, 14},
- },
- {
- name: "OnePageZeroesSHA512SameFile",
- data: bytes.Repeat([]byte{0}, usermem.PageSize),
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- expectedHash: []byte{127, 8, 95, 11, 83, 101, 51, 39, 170, 235, 39, 43, 135, 243, 145, 118, 148, 58, 27, 155, 182, 205, 44, 47, 5, 223, 215, 17, 35, 16, 43, 104, 43, 11, 8, 88, 171, 7, 249, 243, 14, 62, 126, 218, 23, 159, 237, 237, 42, 226, 39, 25, 87, 48, 253, 191, 116, 213, 37, 3, 187, 152, 154, 14},
- },
- {
- name: "MultiplePageZeroesSHA256SeparateFile",
- data: bytes.Repeat([]byte{0}, 128*usermem.PageSize+1),
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- expectedHash: []byte{247, 158, 42, 215, 180, 106, 0, 28, 77, 64, 132, 162, 74, 65, 250, 161, 243, 66, 129, 44, 197, 8, 145, 14, 94, 206, 156, 184, 145, 145, 20, 185},
- },
- {
- name: "MultiplePageZeroesSHA256SameFile",
- data: bytes.Repeat([]byte{0}, 128*usermem.PageSize+1),
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- expectedHash: []byte{247, 158, 42, 215, 180, 106, 0, 28, 77, 64, 132, 162, 74, 65, 250, 161, 243, 66, 129, 44, 197, 8, 145, 14, 94, 206, 156, 184, 145, 145, 20, 185},
- },
- {
- name: "MultiplePageZeroesSHA512SeparateFile",
- data: bytes.Repeat([]byte{0}, 128*usermem.PageSize+1),
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- expectedHash: []byte{100, 121, 14, 30, 104, 200, 142, 182, 190, 78, 23, 68, 157, 174, 23, 75, 174, 250, 250, 25, 66, 45, 235, 103, 129, 49, 78, 127, 173, 154, 121, 35, 37, 115, 60, 217, 26, 205, 253, 253, 236, 145, 107, 109, 232, 19, 72, 92, 4, 191, 181, 205, 191, 57, 234, 177, 144, 235, 143, 30, 15, 197, 109, 81},
- },
- {
- name: "MultiplePageZeroesSHA512SameFile",
- data: bytes.Repeat([]byte{0}, 128*usermem.PageSize+1),
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- expectedHash: []byte{100, 121, 14, 30, 104, 200, 142, 182, 190, 78, 23, 68, 157, 174, 23, 75, 174, 250, 250, 25, 66, 45, 235, 103, 129, 49, 78, 127, 173, 154, 121, 35, 37, 115, 60, 217, 26, 205, 253, 253, 236, 145, 107, 109, 232, 19, 72, 92, 4, 191, 181, 205, 191, 57, 234, 177, 144, 235, 143, 30, 15, 197, 109, 81},
- },
- {
- name: "SingleASHA256SeparateFile",
- data: []byte{'a'},
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- expectedHash: []byte{90, 124, 194, 100, 206, 242, 75, 152, 47, 249, 16, 27, 136, 161, 223, 228, 121, 241, 126, 158, 126, 122, 100, 120, 117, 15, 81, 78, 201, 133, 119, 111},
- },
- {
- name: "SingleASHA256SameFile",
- data: []byte{'a'},
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- expectedHash: []byte{90, 124, 194, 100, 206, 242, 75, 152, 47, 249, 16, 27, 136, 161, 223, 228, 121, 241, 126, 158, 126, 122, 100, 120, 117, 15, 81, 78, 201, 133, 119, 111},
- },
- {
- name: "SingleASHA512SeparateFile",
- data: []byte{'a'},
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- expectedHash: []byte{24, 10, 13, 25, 113, 62, 169, 99, 151, 70, 166, 113, 81, 81, 163, 85, 5, 25, 29, 15, 46, 37, 104, 120, 142, 218, 52, 178, 187, 83, 30, 166, 101, 87, 70, 196, 188, 61, 123, 20, 13, 254, 126, 52, 212, 111, 75, 203, 33, 233, 233, 47, 181, 161, 43, 193, 131, 41, 99, 33, 164, 73, 89, 152},
- },
- {
- name: "SingleASHA512SameFile",
- data: []byte{'a'},
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- expectedHash: []byte{24, 10, 13, 25, 113, 62, 169, 99, 151, 70, 166, 113, 81, 81, 163, 85, 5, 25, 29, 15, 46, 37, 104, 120, 142, 218, 52, 178, 187, 83, 30, 166, 101, 87, 70, 196, 188, 61, 123, 20, 13, 254, 126, 52, 212, 111, 75, 203, 33, 233, 233, 47, 181, 161, 43, 193, 131, 41, 99, 33, 164, 73, 89, 152},
- },
- {
- name: "OnePageASHA256SeparateFile",
- data: bytes.Repeat([]byte{'a'}, usermem.PageSize),
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- expectedHash: []byte{132, 54, 112, 142, 156, 19, 50, 140, 138, 240, 192, 154, 100, 120, 242, 69, 64, 217, 62, 166, 127, 88, 23, 197, 100, 66, 255, 215, 214, 229, 54, 1},
- },
- {
- name: "OnePageASHA256SameFile",
- data: bytes.Repeat([]byte{'a'}, usermem.PageSize),
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- expectedHash: []byte{132, 54, 112, 142, 156, 19, 50, 140, 138, 240, 192, 154, 100, 120, 242, 69, 64, 217, 62, 166, 127, 88, 23, 197, 100, 66, 255, 215, 214, 229, 54, 1},
- },
- {
- name: "OnePageASHA512SeparateFile",
- data: bytes.Repeat([]byte{'a'}, usermem.PageSize),
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- expectedHash: []byte{165, 46, 176, 116, 47, 209, 101, 193, 64, 185, 30, 9, 52, 22, 24, 154, 135, 220, 232, 168, 215, 45, 222, 226, 207, 104, 160, 10, 156, 98, 245, 250, 76, 21, 68, 204, 65, 118, 69, 52, 210, 155, 36, 109, 233, 103, 1, 40, 218, 89, 125, 38, 247, 194, 2, 225, 119, 155, 65, 99, 182, 111, 110, 145},
- },
- {
- name: "OnePageASHA512SameFile",
- data: bytes.Repeat([]byte{'a'}, usermem.PageSize),
- hashAlgorithms: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- expectedHash: []byte{165, 46, 176, 116, 47, 209, 101, 193, 64, 185, 30, 9, 52, 22, 24, 154, 135, 220, 232, 168, 215, 45, 222, 226, 207, 104, 160, 10, 156, 98, 245, 250, 76, 21, 68, 204, 65, 118, 69, 52, 210, 155, 36, 109, 233, 103, 1, 40, 218, 89, 125, 38, 247, 194, 2, 225, 119, 155, 65, 99, 182, 111, 110, 145},
- },
- }
-
- for _, tc := range testCases {
- t.Run(fmt.Sprintf(tc.name), func(t *testing.T) {
- var tree bytesReadWriter
- params := GenerateParams{
- Size: int64(len(tc.data)),
- Name: defaultName,
- Mode: defaultMode,
- UID: defaultUID,
- GID: defaultGID,
- Children: make(map[string]struct{}),
- HashAlgorithms: tc.hashAlgorithms,
- TreeReader: &tree,
- TreeWriter: &tree,
- DataAndTreeInSameFile: tc.dataAndTreeInSameFile,
- }
- if tc.dataAndTreeInSameFile {
- tree.Write(tc.data)
- params.File = &tree
- } else {
- params.File = &bytesReadWriter{
- bytes: tc.data,
- }
- }
- hash, err := Generate(&params)
- if err != nil {
- t.Fatalf("Got err: %v, want nil", err)
- }
- if !bytes.Equal(hash, tc.expectedHash) {
- t.Errorf("Got hash: %v, want %v", hash, tc.expectedHash)
- }
- })
- }
-}
-
-// prepareVerify generates test data and corresponding Merkle tree, and returns
-// the prepared VerifyParams.
-// The test data has size dataSize. The data is hashed with hashAlgorithm. The
-// portion to be verified is the range [verifyStart, verifyStart + verifySize).
-func prepareVerify(t *testing.T, dataSize int64, hashAlgorithm int, dataAndTreeInSameFile, isSymlink bool, verifyStart, verifySize int64, out io.Writer) ([]byte, VerifyParams) {
- t.Helper()
- data := make([]byte, dataSize)
- // Generate random bytes in data.
- rand.Read(data)
-
- var tree bytesReadWriter
- genParams := GenerateParams{
- Size: int64(len(data)),
- Name: defaultName,
- Mode: defaultMode,
- UID: defaultUID,
- GID: defaultGID,
- Children: make(map[string]struct{}),
- HashAlgorithms: hashAlgorithm,
- TreeReader: &tree,
- TreeWriter: &tree,
- DataAndTreeInSameFile: dataAndTreeInSameFile,
- }
- if dataAndTreeInSameFile {
- tree.Write(data)
- genParams.File = &tree
- } else {
- genParams.File = &bytesReadWriter{
- bytes: data,
- }
- }
-
- if isSymlink {
- genParams.SymlinkTarget = defaultSymlinkPath
- }
- hash, err := Generate(&genParams)
- if err != nil {
- t.Fatalf("could not generate Merkle tree:%v", err)
- }
-
- return data, VerifyParams{
- Out: out,
- File: bytes.NewReader(data),
- Tree: &tree,
- Size: dataSize,
- Name: defaultName,
- Mode: defaultMode,
- UID: defaultUID,
- GID: defaultGID,
- Children: make(map[string]struct{}),
- HashAlgorithms: hashAlgorithm,
- ReadOffset: verifyStart,
- ReadSize: verifySize,
- Expected: hash,
- DataAndTreeInSameFile: dataAndTreeInSameFile,
- }
-}
-
-func TestVerifyInvalidRange(t *testing.T) {
- testCases := []struct {
- name string
- verifyStart int64
- verifySize int64
- }{
- // Verify range starts outside data range.
- {
- name: "StartOutsideRange",
- verifyStart: usermem.PageSize,
- verifySize: 1,
- },
- // Verify range ends outside data range.
- {
- name: "EndOutsideRange",
- verifyStart: 0,
- verifySize: 2 * usermem.PageSize,
- },
- // Verify range with negative size.
- {
- name: "NegativeSize",
- verifyStart: 1,
- verifySize: -1,
- },
- }
- for _, tc := range testCases {
- t.Run(tc.name, func(t *testing.T) {
- var buf bytes.Buffer
- _, params := prepareVerify(t, usermem.PageSize /* dataSize */, linux.FS_VERITY_HASH_ALG_SHA256, false /* dataAndTreeInSameFile */, false /* isSymlink */, tc.verifyStart, tc.verifySize, &buf)
- if _, err := Verify(&params); errors.Is(err, nil) {
- t.Errorf("Verification succeeded when expected to fail")
- }
- })
- }
-}
-
-// TODO(b/179422935): Cleanup merkletree verify tests.
-func TestVerifyUnmodifiedMetadata(t *testing.T) {
- testCases := []struct {
- name string
- hashAlgorithm int
- dataAndTreeInSameFile bool
- isSymlink bool
- }{
- {
- name: "SHA256SeparateFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- isSymlink: true,
- },
- {
- name: "SHA512SeparateFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- isSymlink: false,
- },
- {
- name: "SHA256SameFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- isSymlink: false,
- },
- {
- name: "SHA512SameFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- isSymlink: false,
- },
- }
- for _, tc := range testCases {
- t.Run(tc.name, func(t *testing.T) {
- var buf bytes.Buffer
- _, params := prepareVerify(t, usermem.PageSize /* dataSize */, tc.hashAlgorithm, tc.dataAndTreeInSameFile, tc.isSymlink, 0 /* verifyStart */, 0 /* verifySize */, &buf)
- if tc.isSymlink {
- params.SymlinkTarget = defaultSymlinkPath
- }
- if _, err := Verify(&params); !errors.Is(err, nil) {
- t.Errorf("Verification failed when expected to succeed: %v", err)
- }
- })
- }
-}
-
-func TestVerifyModifiedName(t *testing.T) {
- testCases := []struct {
- name string
- hashAlgorithm int
- dataAndTreeInSameFile bool
- }{
- {
- name: "SHA256SeparateFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- },
- {
- name: "SHA512SeparateFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- },
- {
- name: "SHA256SameFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- },
- {
- name: "SHA512SameFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- },
- }
- for _, tc := range testCases {
- t.Run(tc.name, func(t *testing.T) {
- var buf bytes.Buffer
- _, params := prepareVerify(t, usermem.PageSize /* dataSize */, tc.hashAlgorithm, tc.dataAndTreeInSameFile, false /* isSymlink */, 0 /* verifyStart */, 0 /* verifySize */, &buf)
- params.Name += "abc"
- if _, err := Verify(&params); errors.Is(err, nil) {
- t.Errorf("Verification succeeded when expected to fail")
- }
- })
- }
-}
-
-func TestVerifyModifiedSize(t *testing.T) {
- testCases := []struct {
- name string
- hashAlgorithm int
- dataAndTreeInSameFile bool
- }{
- {
- name: "SHA256SeparateFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- },
- {
- name: "SHA512SeparateFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- },
- {
- name: "SHA256SameFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- },
- {
- name: "SHA512SameFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- },
- }
- for _, tc := range testCases {
- t.Run(tc.name, func(t *testing.T) {
- var buf bytes.Buffer
- _, params := prepareVerify(t, usermem.PageSize /* dataSize */, tc.hashAlgorithm, tc.dataAndTreeInSameFile, false /* isSymlink */, 0 /* verifyStart */, 0 /* verifySize */, &buf)
- params.Size--
- if _, err := Verify(&params); errors.Is(err, nil) {
- t.Errorf("Verification succeeded when expected to fail")
- }
- })
- }
-}
-
-func TestVerifyModifiedMode(t *testing.T) {
- testCases := []struct {
- name string
- hashAlgorithm int
- dataAndTreeInSameFile bool
- }{
- {
- name: "SHA256SeparateFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- },
- {
- name: "SHA512SeparateFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- },
- {
- name: "SHA256SameFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- },
- {
- name: "SHA512SameFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- },
- }
- for _, tc := range testCases {
- t.Run(tc.name, func(t *testing.T) {
- var buf bytes.Buffer
- _, params := prepareVerify(t, usermem.PageSize /* dataSize */, tc.hashAlgorithm, tc.dataAndTreeInSameFile, false /* isSymlink */, 0 /* verifyStart */, 0 /* verifySize */, &buf)
- params.Mode++
- if _, err := Verify(&params); errors.Is(err, nil) {
- t.Errorf("Verification succeeded when expected to fail")
- }
- })
- }
-}
-
-func TestVerifyModifiedUID(t *testing.T) {
- testCases := []struct {
- name string
- hashAlgorithm int
- dataAndTreeInSameFile bool
- }{
- {
- name: "SHA256SeparateFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- },
- {
- name: "SHA512SeparateFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- },
- {
- name: "SHA256SameFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- },
- {
- name: "SHA512SameFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- },
- }
- for _, tc := range testCases {
- t.Run(tc.name, func(t *testing.T) {
- var buf bytes.Buffer
- _, params := prepareVerify(t, usermem.PageSize /* dataSize */, tc.hashAlgorithm, tc.dataAndTreeInSameFile, false /* isSymlink */, 0 /* verifyStart */, 0 /* verifySize */, &buf)
- params.UID++
- if _, err := Verify(&params); errors.Is(err, nil) {
- t.Errorf("Verification succeeded when expected to fail")
- }
- })
- }
-}
-
-func TestVerifyModifiedGID(t *testing.T) {
- testCases := []struct {
- name string
- hashAlgorithm int
- dataAndTreeInSameFile bool
- }{
- {
- name: "SHA256SeparateFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- },
- {
- name: "SHA512SeparateFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- },
- {
- name: "SHA256SameFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- },
- {
- name: "SHA512SameFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- },
- }
- for _, tc := range testCases {
- t.Run(tc.name, func(t *testing.T) {
- var buf bytes.Buffer
- _, params := prepareVerify(t, usermem.PageSize /* dataSize */, tc.hashAlgorithm, tc.dataAndTreeInSameFile, false /* isSymlink */, 0 /* verifyStart */, 0 /* verifySize */, &buf)
- params.GID++
- if _, err := Verify(&params); errors.Is(err, nil) {
- t.Errorf("Verification succeeded when expected to fail")
- }
- })
- }
-}
-
-func TestVerifyModifiedChildren(t *testing.T) {
- testCases := []struct {
- name string
- hashAlgorithm int
- dataAndTreeInSameFile bool
- }{
- {
- name: "SHA256SeparateFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- },
- {
- name: "SHA512SeparateFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- },
- {
- name: "SHA256SameFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- },
- {
- name: "SHA512SameFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- },
- }
- for _, tc := range testCases {
- t.Run(tc.name, func(t *testing.T) {
- var buf bytes.Buffer
- _, params := prepareVerify(t, usermem.PageSize /* dataSize */, tc.hashAlgorithm, tc.dataAndTreeInSameFile, false /* isSymlink */, 0 /* verifyStart */, 0 /* verifySize */, &buf)
- params.Children["abc"] = struct{}{}
- if _, err := Verify(&params); errors.Is(err, nil) {
- t.Errorf("Verification succeeded when expected to fail")
- }
- })
- }
-}
-
-func TestVerifyModifiedSymlink(t *testing.T) {
- testCases := []struct {
- name string
- hashAlgorithm int
- dataAndTreeInSameFile bool
- }{
- {
- name: "SHA256SeparateFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- },
- {
- name: "SHA512SeparateFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- },
- {
- name: "SHA256SameFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- },
- {
- name: "SHA512SameFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- },
- }
- for _, tc := range testCases {
- t.Run(tc.name, func(t *testing.T) {
- var buf bytes.Buffer
- _, params := prepareVerify(t, usermem.PageSize /* dataSize */, tc.hashAlgorithm, tc.dataAndTreeInSameFile, true /* isSymlink */, 0 /* verifyStart */, 0 /* verifySize */, &buf)
- params.SymlinkTarget = "merkle_modified_test_link"
- if _, err := Verify(&params); err == nil {
- t.Errorf("Verification succeeded when expected to fail")
- }
- })
- }
-}
-
-func TestModifyOutsideVerifyRange(t *testing.T) {
- testCases := []struct {
- name string
- // The byte with index modifyByte is modified.
- modifyByte int64
- hashAlgorithm int
- dataAndTreeInSameFile bool
- }{
- {
- name: "BeforeRangeSHA256SeparateFile",
- modifyByte: 4*usermem.PageSize - 1,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- },
- {
- name: "BeforeRangeSHA512SeparateFile",
- modifyByte: 4*usermem.PageSize - 1,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- },
- {
- name: "BeforeRangeSHA256SameFile",
- modifyByte: 4*usermem.PageSize - 1,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- },
- {
- name: "BeforeRangeSHA512SameFile",
- modifyByte: 4*usermem.PageSize - 1,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- },
- {
- name: "AfterRangeSHA256SeparateFile",
- modifyByte: 5 * usermem.PageSize,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- },
- {
- name: "AfterRangeSHA512SeparateFile",
- modifyByte: 5 * usermem.PageSize,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- },
- {
- name: "AfterRangeSHA256SameFile",
- modifyByte: 5 * usermem.PageSize,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- },
- {
- name: "AfterRangeSHA256SameFile",
- modifyByte: 5 * usermem.PageSize,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- },
- }
- for _, tc := range testCases {
- t.Run(tc.name, func(t *testing.T) {
- dataSize := int64(8 * usermem.PageSize)
- verifyStart := int64(4 * usermem.PageSize)
- verifySize := int64(usermem.PageSize)
- var buf bytes.Buffer
- // Modified byte is outside verify range. Verify should succeed.
- data, params := prepareVerify(t, dataSize, tc.hashAlgorithm, tc.dataAndTreeInSameFile, false /* isSymlink */, verifyStart, verifySize, &buf)
- // Flip a bit in data and checks Verify results.
- data[tc.modifyByte] ^= 1
- n, err := Verify(&params)
- if !errors.Is(err, nil) {
- t.Errorf("Verification failed when expected to succeed: %v", err)
- }
- if n != verifySize {
- t.Errorf("Got Verify output size %d, want %d", n, verifySize)
- }
- if int64(buf.Len()) != verifySize {
- t.Errorf("Got Verify output buf size %d, want %d,", buf.Len(), verifySize)
- }
- if !bytes.Equal(data[verifyStart:verifyStart+verifySize], buf.Bytes()) {
- t.Errorf("Incorrect output buf from Verify")
- }
- })
- }
-}
-
-func TestModifyInsideVerifyRange(t *testing.T) {
- testCases := []struct {
- name string
- verifyStart int64
- verifySize int64
- // The byte with index modifyByte is modified.
- modifyByte int64
- hashAlgorithm int
- dataAndTreeInSameFile bool
- }{
- // Test a block-aligned verify range.
- // Modifying a byte in the verified range should cause verify
- // to fail.
- {
- name: "BlockAlignedRangeSHA256SeparateFile",
- verifyStart: 4 * usermem.PageSize,
- verifySize: usermem.PageSize,
- modifyByte: 4 * usermem.PageSize,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- },
- {
- name: "BlockAlignedRangeSHA512SeparateFile",
- verifyStart: 4 * usermem.PageSize,
- verifySize: usermem.PageSize,
- modifyByte: 4 * usermem.PageSize,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- },
- {
- name: "BlockAlignedRangeSHA256SameFile",
- verifyStart: 4 * usermem.PageSize,
- verifySize: usermem.PageSize,
- modifyByte: 4 * usermem.PageSize,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- },
- {
- name: "BlockAlignedRangeSHA512SameFile",
- verifyStart: 4 * usermem.PageSize,
- verifySize: usermem.PageSize,
- modifyByte: 4 * usermem.PageSize,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- },
- // The tests below use a non-block-aligned verify range.
- // Modifying a byte at strat of verify range should cause
- // verify to fail.
- {
- name: "ModifyStartSHA256SeparateFile",
- verifyStart: 4*usermem.PageSize + 123,
- verifySize: 2 * usermem.PageSize,
- modifyByte: 4*usermem.PageSize + 123,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- },
- {
- name: "ModifyStartSHA512SeparateFile",
- verifyStart: 4*usermem.PageSize + 123,
- verifySize: 2 * usermem.PageSize,
- modifyByte: 4*usermem.PageSize + 123,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- },
- {
- name: "ModifyStartSHA256SameFile",
- verifyStart: 4*usermem.PageSize + 123,
- verifySize: 2 * usermem.PageSize,
- modifyByte: 4*usermem.PageSize + 123,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- },
- {
- name: "ModifyStartSHA512SameFile",
- verifyStart: 4*usermem.PageSize + 123,
- verifySize: 2 * usermem.PageSize,
- modifyByte: 4*usermem.PageSize + 123,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- },
- // Modifying a byte at the end of verify range should cause
- // verify to fail.
- {
- name: "ModifyEndSHA256SeparateFile",
- verifyStart: 4*usermem.PageSize + 123,
- verifySize: 2 * usermem.PageSize,
- modifyByte: 6*usermem.PageSize + 123,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- },
- {
- name: "ModifyEndSHA512SeparateFile",
- verifyStart: 4*usermem.PageSize + 123,
- verifySize: 2 * usermem.PageSize,
- modifyByte: 6*usermem.PageSize + 123,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- },
- {
- name: "ModifyEndSHA256SameFile",
- verifyStart: 4*usermem.PageSize + 123,
- verifySize: 2 * usermem.PageSize,
- modifyByte: 6*usermem.PageSize + 123,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- },
- {
- name: "ModifyEndSHA512SameFile",
- verifyStart: 4*usermem.PageSize + 123,
- verifySize: 2 * usermem.PageSize,
- modifyByte: 6*usermem.PageSize + 123,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- },
- // Modifying a byte in the middle verified block should cause
- // verify to fail.
- {
- name: "ModifyMiddleSHA256SeparateFile",
- verifyStart: 4*usermem.PageSize + 123,
- verifySize: 2 * usermem.PageSize,
- modifyByte: 5*usermem.PageSize + 123,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- },
- {
- name: "ModifyMiddleSHA512SeparateFile",
- verifyStart: 4*usermem.PageSize + 123,
- verifySize: 2 * usermem.PageSize,
- modifyByte: 5*usermem.PageSize + 123,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- },
- {
- name: "ModifyMiddleSHA256SameFile",
- verifyStart: 4*usermem.PageSize + 123,
- verifySize: 2 * usermem.PageSize,
- modifyByte: 5*usermem.PageSize + 123,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- },
- {
- name: "ModifyMiddleSHA512SameFile",
- verifyStart: 4*usermem.PageSize + 123,
- verifySize: 2 * usermem.PageSize,
- modifyByte: 5*usermem.PageSize + 123,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- },
- // Modifying a byte in the first block in the verified range
- // should cause verify to fail, even the modified bit itself is
- // out of verify range.
- {
- name: "ModifyFirstBlockSHA256SeparateFile",
- verifyStart: 4*usermem.PageSize + 123,
- verifySize: 2 * usermem.PageSize,
- modifyByte: 4*usermem.PageSize + 122,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- },
- {
- name: "ModifyFirstBlockSHA512SeparateFile",
- verifyStart: 4*usermem.PageSize + 123,
- verifySize: 2 * usermem.PageSize,
- modifyByte: 4*usermem.PageSize + 122,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- },
- {
- name: "ModifyFirstBlockSHA256SameFile",
- verifyStart: 4*usermem.PageSize + 123,
- verifySize: 2 * usermem.PageSize,
- modifyByte: 4*usermem.PageSize + 122,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- },
- {
- name: "ModifyFirstBlockSHA512SameFile",
- verifyStart: 4*usermem.PageSize + 123,
- verifySize: 2 * usermem.PageSize,
- modifyByte: 4*usermem.PageSize + 122,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- },
- // Modifying a byte in the last block in the verified range
- // should cause verify to fail, even the modified bit itself is
- // out of verify range.
- {
- name: "ModifyLastBlockSHA256SeparateFile",
- verifyStart: 4*usermem.PageSize + 123,
- verifySize: 2 * usermem.PageSize,
- modifyByte: 6*usermem.PageSize + 124,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- },
- {
- name: "ModifyLastBlockSHA512SeparateFile",
- verifyStart: 4*usermem.PageSize + 123,
- verifySize: 2 * usermem.PageSize,
- modifyByte: 6*usermem.PageSize + 124,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- },
- {
- name: "ModifyLastBlockSHA256SameFile",
- verifyStart: 4*usermem.PageSize + 123,
- verifySize: 2 * usermem.PageSize,
- modifyByte: 6*usermem.PageSize + 124,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- },
- {
- name: "ModifyLastBlockSHA512SameFile",
- verifyStart: 4*usermem.PageSize + 123,
- verifySize: 2 * usermem.PageSize,
- modifyByte: 6*usermem.PageSize + 124,
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- },
- }
- for _, tc := range testCases {
- t.Run(tc.name, func(t *testing.T) {
- dataSize := int64(8 * usermem.PageSize)
- var buf bytes.Buffer
- data, params := prepareVerify(t, dataSize, tc.hashAlgorithm, tc.dataAndTreeInSameFile, false /* isSymlink */, tc.verifyStart, tc.verifySize, &buf)
- // Flip a bit in data and checks Verify results.
- data[tc.modifyByte] ^= 1
- if _, err := Verify(&params); errors.Is(err, nil) {
- t.Errorf("Verification succeeded when expected to fail")
- }
- })
- }
-}
-
-func TestVerifyRandom(t *testing.T) {
- testCases := []struct {
- name string
- hashAlgorithm int
- dataAndTreeInSameFile bool
- }{
- {
- name: "SHA256SeparateFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: false,
- },
- {
- name: "SHA512SeparateFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: false,
- },
- {
- name: "SHA256SameFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA256,
- dataAndTreeInSameFile: true,
- },
- {
- name: "SHA512SameFile",
- hashAlgorithm: linux.FS_VERITY_HASH_ALG_SHA512,
- dataAndTreeInSameFile: true,
- },
- }
- for _, tc := range testCases {
- t.Run(tc.name, func(t *testing.T) {
- rand.Seed(time.Now().UnixNano())
- // Use a random dataSize. Minimum size 2 so that we can pick a random
- // portion from it.
- dataSize := rand.Int63n(200*usermem.PageSize) + 2
-
- // Pick a random portion of data.
- start := rand.Int63n(dataSize - 1)
- size := rand.Int63n(dataSize) + 1
-
- var buf bytes.Buffer
- data, params := prepareVerify(t, dataSize, tc.hashAlgorithm, tc.dataAndTreeInSameFile, false /* isSymlink */, start, size, &buf)
-
- // Checks that the random portion of data from the original data is
- // verified successfully.
- n, err := Verify(&params)
- if err != nil && err != io.EOF {
- t.Errorf("Verification failed for correct data: %v", err)
- }
- if size > dataSize-start {
- size = dataSize - start
- }
- if n != size {
- t.Errorf("Got Verify output size %d, want %d", n, size)
- }
- if int64(buf.Len()) != size {
- t.Errorf("Got Verify output buf size %d, want %d", buf.Len(), size)
- }
- if !bytes.Equal(data[start:start+size], buf.Bytes()) {
- t.Errorf("Incorrect output buf from Verify")
- }
-
- // Verify that modified metadata should fail verification.
- buf.Reset()
- params.Name = defaultName + "abc"
- if _, err := Verify(&params); errors.Is(err, nil) {
- t.Error("Verify succeeded for modified metadata, expect failure")
- }
-
- // Flip a random bit in randPortion, and check that verification fails.
- buf.Reset()
- randBytePos := rand.Int63n(size)
- data[start+randBytePos] ^= 1
- params.File = bytes.NewReader(data)
- params.Name = defaultName
-
- if _, err := Verify(&params); errors.Is(err, nil) {
- t.Error("Verification succeeded for modified data, expect failure")
- }
- })
- }
-}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-27 05:25:44 +0000