tiny.closure.link.cover

1const binary = @import("../binary/root.zig");2const std = @import("std");34pub const attributions_max: usize = 64;5pub const padding_ranges_max: usize = 64;67pub const Kind = enum(u8) {8    root,9    primitive,10};1112pub const Attribution = struct {13    kind: Kind,14    offset: u64,15    address: u64,16    length: u64,17    source_offset: u64 = 0,18    relocation_count: u32 = 0,19    source_sha256: [32]u8,20};2122pub const Padding = struct {23    offset: u64,24    address: u64,25    length: u16,26};2728pub const Policy = struct {29    padding_bytes_max: u16 = 15,30    padding_byte: u8 = 0xcc,31};3233pub const Scratch = struct {34    ordered: []Attribution,35    padding: []Padding,36};3738pub const Report = struct {39    attributions: []const Attribution,40    padding: []const Padding,41    root_bytes: u64,42    primitive_bytes: u64,43    padding_bytes: u64,44    executable_bytes: u64,45    executable_sha256: [32]u8,46    work: u64,47};4849const CoverError = error{50    AttributionCapacityExceeded,51    AttributionDigestMissing,52    AttributionOutsideExecutable,53    AttributionOverlap,54    ExecutableCoverageMissing,55    PaddingCapacityExceeded,56    PaddingInvalid,57};5859pub const Error = binary.strict.Error || CoverError;6061pub fn verify(62    bytes: []const u8,63    image: binary.strict.Report,64    input: []const Attribution,65    policy: Policy,66    scratch: Scratch,67) Error!Report {68    if (input.len > scratch.ordered.len or69        input.len > attributions_max or70        scratch.padding.len > padding_ranges_max)71    {72        return error.AttributionCapacityExceeded;73    }74    @memcpy(scratch.ordered[0..input.len], input);75    const ordered = scratch.ordered[0..input.len];76    sort(ordered);77    var work: u64 = input.len;78    try validateAttributions(image, ordered, &work);79    var padding_count: usize = 0;80    var root_bytes: u64 = 0;81    var primitive_bytes: u64 = 0;82    var padding_bytes: u64 = 0;83    var executable_bytes: u64 = 0;84    var attributed_count: usize = 0;85    var hasher = std.crypto.hash.sha2.Sha256.init(.{});86    for (image.loads) |load| {87        if (!load.executable) continue;88        const start = toOffset(load.offset) catch89            return error.AttributionOutsideExecutable;90        const length = toOffset(load.content_bytes) catch91            return error.AttributionOutsideExecutable;92        const contents = try take(bytes, start, length);93        hasher.update(contents);94        executable_bytes = try added(executable_bytes, load.content_bytes);95        var cursor = load.offset;96        const end = try added(load.offset, load.content_bytes);97        for (ordered) |attribution| {98            work += 1;99            if (attribution.offset < load.offset or100                attribution.offset >= end)101            {102                continue;103            }104            const gap = attribution.offset - cursor;105            if (gap != 0) {106                try appendPadding(107                    bytes,108                    load,109                    cursor,110                    gap,111                    policy,112                    scratch.padding,113                    &padding_count,114                    &padding_bytes,115                    &work,116                );117            }118            switch (attribution.kind) {119                .root => root_bytes =120                    try added(root_bytes, attribution.length),121                .primitive => primitive_bytes =122                    try added(primitive_bytes, attribution.length),123            }124            cursor = try added(attribution.offset, attribution.length);125            attributed_count += 1;126        }127        if (cursor < end) {128            try appendPadding(129                bytes,130                load,131                cursor,132                end - cursor,133                policy,134                scratch.padding,135                &padding_count,136                &padding_bytes,137                &work,138            );139        }140        if (cursor > end) return error.AttributionOverlap;141    }142    if (attributed_count != ordered.len) {143        return error.AttributionOutsideExecutable;144    }145    const accounted = try added(146        try added(root_bytes, primitive_bytes),147        padding_bytes,148    );149    if (accounted != executable_bytes) {150        return error.ExecutableCoverageMissing;151    }152    var digest: [32]u8 = undefined;153    hasher.final(&digest);154    return .{155        .attributions = ordered,156        .padding = scratch.padding[0..padding_count],157        .root_bytes = root_bytes,158        .primitive_bytes = primitive_bytes,159        .padding_bytes = padding_bytes,160        .executable_bytes = executable_bytes,161        .executable_sha256 = digest,162        .work = work,163    };164}165166fn validateAttributions(167    image: binary.strict.Report,168    ordered: []const Attribution,169    work: *u64,170) Error!void {171    var previous_end: u64 = 0;172    for (ordered, 0..) |attribution, index| {173        work.* += 1;174        if (attribution.length == 0 or175            !digestKnown(attribution.source_sha256))176        {177            return error.AttributionDigestMissing;178        }179        if (index != 0 and attribution.offset < previous_end) {180            return error.AttributionOverlap;181        }182        const end = try added(attribution.offset, attribution.length);183        var admitted = false;184        for (image.loads) |load| {185            work.* += 1;186            if (!load.executable) continue;187            const load_end = try added(load.offset, load.content_bytes);188            if (attribution.offset < load.offset or end > load_end) continue;189            const relative = attribution.offset - load.offset;190            if (attribution.address != try added(load.address, relative)) {191                return error.AttributionOutsideExecutable;192            }193            admitted = true;194            break;195        }196        if (!admitted) return error.AttributionOutsideExecutable;197        previous_end = end;198    }199}200201fn appendPadding(202    bytes: []const u8,203    load: binary.strict.Load,204    offset: u64,205    length: u64,206    policy: Policy,207    output: []Padding,208    count: *usize,209    total: *u64,210    work: *u64,211) Error!void {212    if (length == 0 or length > policy.padding_bytes_max) {213        return error.PaddingInvalid;214    }215    if (count.* == output.len) return error.PaddingCapacityExceeded;216    const start = toOffset(offset) catch return error.PaddingInvalid;217    const length_usize = toOffset(length) catch return error.PaddingInvalid;218    const contents = try take(bytes, start, length_usize);219    for (contents) |byte| {220        work.* += 1;221        if (byte != policy.padding_byte) return error.PaddingInvalid;222    }223    output[count.*] = .{224        .offset = offset,225        .address = try added(load.address, offset - load.offset),226        .length = @intCast(length),227    };228    count.* += 1;229    total.* = try added(total.*, length);230}231232fn sort(values: []Attribution) void {233    var index: usize = 1;234    while (index < values.len) : (index += 1) {235        const value = values[index];236        var cursor = index;237        while (cursor > 0 and values[cursor - 1].offset > value.offset) {238            values[cursor] = values[cursor - 1];239            cursor -= 1;240        }241        values[cursor] = value;242    }243}244245fn digestKnown(digest: [32]u8) bool {246    for (digest) |byte| {247        if (byte != 0) return true;248    }249    return false;250}251252fn take(253    bytes: []const u8,254    offset: usize,255    length: usize,256) Error![]const u8 {257    const end = std.math.add(usize, offset, length) catch258        return error.BinaryArithmeticOverflow;259    if (end > bytes.len) return error.TruncatedBinary;260    return bytes[offset..end];261}262263fn toOffset(value: u64) Error!usize {264    return std.math.cast(usize, value) orelse265        error.BinaryArithmeticOverflow;266}267268fn added(left: anytype, right: anytype) Error!u64 {269    return std.math.add(270        u64,271        @intCast(left),272        @intCast(right),273    ) catch error.BinaryArithmeticOverflow;274}275276test "coverage attributes every executable byte with bounded padding" {277    var bytes: [32]u8 = @splat(0);278    @memset(bytes[4..8], 0x11);279    @memset(bytes[8..11], 0xcc);280    @memset(bytes[11..15], 0x22);281    const loads = [_]binary.strict.Load{.{282        .offset = 4,283        .address = 0x1000,284        .file_bytes = 16,285        .content_bytes = 11,286        .memory_bytes = 16,287        .readable = true,288        .writable = false,289        .executable = true,290    }};291    const image = binary.strict.Report{292        .kind = .elf64,293        .loads = &loads,294        .relocations = &.{},295        .executable_bytes = 11,296        .initialized_bytes = 0,297        .memory_bytes = 16,298        .stack_bytes = 0,299        .timestamp = 0,300        .image_base = 0,301        .work = 1,302    };303    const digest: [32]u8 = @splat(1);304    const input = [_]Attribution{305        .{306            .kind = .primitive,307            .offset = 11,308            .address = 0x1007,309            .length = 4,310            .source_sha256 = digest,311        },312        .{313            .kind = .root,314            .offset = 4,315            .address = 0x1000,316            .length = 4,317            .source_sha256 = digest,318        },319    };320    var ordered: [2]Attribution = undefined;321    var padding: [1]Padding = undefined;322    const report = try verify(323        &bytes,324        image,325        &input,326        .{},327        .{ .ordered = &ordered, .padding = &padding },328    );329    try std.testing.expectEqual(@as(u64, 4), report.root_bytes);330    try std.testing.expectEqual(@as(u64, 4), report.primitive_bytes);331    try std.testing.expectEqual(@as(u64, 3), report.padding_bytes);332    try std.testing.expectEqual(@as(u64, 11), report.executable_bytes);333}334335test "coverage fails closed on foreign and excessive gaps" {336    var bytes: [32]u8 = @splat(0xcc);337    const loads = [_]binary.strict.Load{.{338        .offset = 4,339        .address = 0x1000,340        .file_bytes = 16,341        .content_bytes = 16,342        .memory_bytes = 16,343        .readable = true,344        .writable = false,345        .executable = true,346    }};347    const image = binary.strict.Report{348        .kind = .elf64,349        .loads = &loads,350        .relocations = &.{},351        .executable_bytes = 16,352        .initialized_bytes = 0,353        .memory_bytes = 16,354        .stack_bytes = 0,355        .timestamp = 0,356        .image_base = 0,357        .work = 1,358    };359    const digest: [32]u8 = @splat(1);360    const input = [_]Attribution{.{361        .kind = .root,362        .offset = 4,363        .address = 0x1000,364        .length = 1,365        .source_sha256 = digest,366    }};367    var ordered: [1]Attribution = undefined;368    var padding: [1]Padding = undefined;369    try std.testing.expectError(370        error.PaddingInvalid,371        verify(372            &bytes,373            image,374            &input,375            .{ .padding_bytes_max = 14 },376            .{ .ordered = &ordered, .padding = &padding },377        ),378    );379    bytes[5] = 0x90;380    const full = [_]Attribution{.{381        .kind = .root,382        .offset = 6,383        .address = 0x1002,384        .length = 14,385        .source_sha256 = digest,386    }};387    try std.testing.expectError(388        error.PaddingInvalid,389        verify(390            &bytes,391            image,392            &full,393            .{},394            .{ .ordered = &ordered, .padding = &padding },395        ),396    );397}

1pub const cover = @import("cover.zig");